Chapter 3

 

Chapter 3: Data Structures in Image Analysis


Chapter 3 Overview: 

3.1 Levels of image data representation
3.2 Traditional image data structures
3.3 Hierarchical data structures

3.1    Levels of image data representation 

Iconic images - consists of images containing original data; integer matrices with data about pixel brightness. e.g., outputs of pre-processing operations (e.g., filtration or edge sharpening) used for highlighting some aspects of the image important for further treatment. 
Segmented images - 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 representations - hold knowledge about 2D and 3D shapes. The quantification of a shape is very difficult but very important. 
Relational models - give 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.  Example - counting planes standing at an airport using satellite images A priori knowledge such as position of the airport (e.g., from a map), relations to other objects in the image ( e.g., to roads, lakes, urban areas), geometric models of planes for which we are searching etc. 

3.2 Traditional image data structures 

Used not only for the direct representation of image information, also a basis of more complex hierarchical methods of image representation. Some examples are matrices, chains, graphs,  lists of object properties, relational databases, etc. 
Matrices 
Most common data structure for low level image representation Elements of the matrix are integer numbers 
Image data of this kind are usually the direct output of the image capturing device, e.g., a scanner. 
Chains 
Chains are used for description of object borders 
Symbols in a chain usually correspond to the neighborhood of primitives in the image. 
Chain codes describe object borders or other lines. A border is defined by a reference pixel and symbol sequences that correspond to a line of unit length in different directions
If local information is needed from the chain code, it is necessary to search through the whole chain systematically.  e.g. Does the border turn somewhere to the left by 90 degrees? A sample pair of symbols in the chain must be found. 

If global information is needed, situation is much more difficult. Questions about the shape of the border represented by chain codes are not trivial. 

Chains can be represented using static data structures (e.g., 1D arrays); their size is the longest length of the chain expected. 
Dynamic data structures are more advantageous in terms of memory. 
Run length coding often used to represent strings of symbols in an image matrix (e.g., FAX machines use it). 
In binary images, run length coding records only areas that belong to the object in the image; the area is then represented as a list of lists. Each row of the image is described by a sublist, the first element of which is the row number. Subsequent terms are co-ordinate pairs; the first element of a pair is the beginning of a run and the second is the end. There can be several such sequences in the row. 

Run length coding can be used for an image with multiple brightness levels as well - in the sublist, sequence brightness must also be recorded. 

Topological data structures 
Image description as a set of elements and their relations. 
Graphs An algebraic structure which consists of a set of nodes and arcs (or edges). Each edge connects a pair of nodes.
Evaluated graphs a graph with weights on the nodes and edges.
Region adjacency graphs: a graph in which nodes correspond to regions and neighboring regions are connected by edges. It shows how regions are related.


Relational structures 
information is concentrated in relations between semantically important parts of the image - objects - that are the result of segmentation. Appropriate for higher level image understanding

3.3    Hierarchical data structures 

Computer vision is by its nature very computationally expensive
One of the solutions is using parallel computers = brute force 
Many computer vision problems are difficult to divide among processors, or decompose in any way. 
Hierarchical data structures make it possible to use algorithms which decide a strategy for processing on the basis of relatively small quantities of data. 
They work at the finest resolution only with those parts of the image for which it is necessary, using knowledge instead of brute force to ease and speed up the processing. 
Pyramids 
M-pyramid - Matrix pyramid ... is a sequence {ML, ML-1, ..., M0} of images 
ML has the same dimensions and elements as the original image 
Mi-1 is derived from the Mi by reducing the resolution by one half. 
Square matrices with dimensions equal to powers of two required - M0 corresponds to one pixel only. 
M-pyramids are used when it is necessary to work with an image at different resolutions simultaneously. 
An image having one degree smaller resolution in a pyramid contains four times less data, so that it is processed approximately four times as quickly. 
One common form of M-pyramid are Gaussian and Laplacian pyramids which are used for image compression.
The number of image pixels used by an M-pyramid for storing all matrices is 

Often it is advantageous to use several resolutions simultaneously rather than to choose just one image from the M-pyramid. Such images can be represented using tree pyramids ... T-pyramids. 
T-pyramid is a tree, every node of the T-pyramid has 4 child nodes. 

Quadtrees 
Quadtrees are modifications of T-pyramids. 
Every node of the tree except the leaves has four children (NW: north-western, NE: north-eastern, SW: south-western, SE: south-eastern). 
Similarly to T-pyramids, the image is divided into four quadrants at each hierarchical level, however it is not necessary to keep nodes at all levels. 

If a parent node has four children of the same value (e.g., brightness), it is not necessary to record them. 
Problems associated with hierarchical image representation: 
Dependence on the position, orientation and relative size of objects. Two similar images with just very small differences can have very different pyramid or quadtree representations. Even two images depicting the same, slightly shifted scene, can have entirely different representations.


01/10/01