Data Structures for Image Analysis: Levels & Representation

CS654: Digital Image Analysis Lecture 3: Data Structure for Image Analysis

Recap of Lecture 2 Image digitization Image acquisition Sampling Quantization

Todays topic Data structures for image analysis Levels of image data representation Traditional image data structures Hierarchical data structures

Introduction Data and an algorithm are the two basic related parts of any program. Data organization often considerably affects the simplicity of the selection Choice of data structures is a fundamental question when writing a program Relations between different types of representations of image data will then be clearer.

Levels of image data representation The aim of image analysis task is to find a relation between an input image and models of the real world. Image information becomes denser and semantic knowledge about the interpretation of image data is used more and more. Several levels of visual information representation are defined on the way between the input image and the model Intermediate representations (data structures). Algorithms used for the creation of representations and introduction of relations between them.

Four levels of representation Relational Geometric Segmented Iconic

Iconic images The first, lowest representational level. Consists of images containing original data. Integer matrices with data about pixel brightness. Outputs of pre-processing operations (e.g., filtration or edge sharpening) Used for highlighting some aspects of the image important for further analysis

Segmented images The second level of representation Parts of the image are joined into groups that probably belong to the same objects. It is useful to know something about the application domain while doing image segmentation. It is then easier to deal with noise and other problems associated with erroneous image data.

Geometric representation The third level of representation The quantification of a shape - holding knowledge about 2D and 3D shapes. Useful while doing general and complex simulations of the influence of illumination and motion in real objects. Also useful for content based image retrieval, shape matching, object recognition etc.

Relational models The fourth level of representation They give us the ability to treat data more efficiently and at a higher level of abstraction. A priori knowledge about the case being solved is usually used in processing of this kind Artificial Intelligence techniques are often explored

Traditional image data structures: Matrices The most common data structure for low-level representation Elements of the matrix are integer numbers representing Direct output of the image-capturing device The matrix is a full representation of the image, independent of the contents of image data Contains spatial relations among semantically important parts of the image.

Integral Images Another matrix representation that holds global image information It is constructed so that ????(?,?) represent the sums of all the original image pixel-values left of and above (?,?): y ???? ?,? = ?(?,?) ? ? ? ? Recurrence relation ?? ????(?,?) ? ?,? = ? ? 1,? + ? ?,? x ???? ?,? = ???? ?,? 1 + ? ?,?

Filter design using Integral Images y ?1 ?2 ? ?4 ?3 x The set of rectangular filters used by Viola and Jones, 2001

Topological data structures Topological data structures describe the image as a set of elements and their relations Relations are often represented using graphs. An evaluated graph is a graph in which values are assigned to arcs, to nodes, or to both The region adjacency graph is typical of this class of data structures,

Region Adjacency Graph (RAG) Nodes correspond to regions Neighbouring regions are connected by an arc. 0 0 2 1 2 1 3 4 5 4 3 5

Region Adjacency Graph (RAG) It is usually created from the region map Elements of a region map are identification labels of the regions. To create the region adjacency graph, borders of all regions in the image are traced, and labels of all neighbouring regions are stored. Application: matching, region merging, etc.

Hierarchical data structures By its nature very computationally expensive Must process considerable quantities of image data. One of the solutions is to use parallel computers Hierarchical data structures make it possible to use algorithms which decide a strategy for processing on the basis of relatively small quantities of data. At the finest resolution only with those parts of the image for which it is essential

Pyramids Pyramids are among the simplest hierarchical data structures. M-pyramids (matrix-pyramids) and T-pyramids (tree-pyramids). M-pyramids are used when it is necessary to work with an image at different resolutions simultaneously. To use several resolutions simultaneously rather than choose just one image from the M-pyramid, we use T-pyramids.

T-Pyramid Let 2? be the size of the full resolution image T- pyramid is defined by 1. A set of nodes ? = ? = ?,?,? , ? 0,? ;?,? [0,2? 1]} 2. There is a mapping ? between subsequent nodes ?? 1and ?? ? ?,?,? = (? 1,?/2,?/2) 3. A function ? that maps a node of the pyramid ? to ?, ? ??? ? = {0, ,255}

T Pyramid: Example Level 0 Level 1 Level 2

Quadtree A quad tree is a tree whose nodes either are leaves or have 4 children The key is to "Divide and Conquer". We divide the picture area into 4 sections. Those 4 sections are then further divided into 4 subsections. . A pixel is the smallest subsection of the quad tree. A square or quadrant in the picture is either: entirely one colour composed of 4 smaller sub-squares

Quadtree: Example

Usefulness of Quadtrees Advantages To store recursive definition Disadvantages Take up a lot of space. Zooming to a particular quadrant in the tree is a one step operation. Dependence on the position, orientation, and relative size of objects. Accessing particular regions of the image is a very fast operation.

Other pyramidal structures Modified M-pyramids Reduction window If the images are constructed such that all interior cells have the same number of neighbours -> Regular pyramid

Summary Image quantization formulae Image sampling size tradeoff Data structure Integral Images Graph based representation Image Pyramids Quadtree

Thank you Next Lecture: Neighbourhood Relationship