 
Chapter 3: Data Structures in Image Analysis
 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


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 

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

Mpyramid  Matrix pyramid ... is a sequence {ML, ML1, ..., M0} of images
ML has the same dimensions and elements as the original image
Mi1 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. 

Mpyramids 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 Mpyramid are Gaussian and Laplacian pyramids which
are used for image compression. 
 The number of image pixels used by an Mpyramid for storing all matrices is


Often it is advantageous to use several resolutions simultaneously rather than to choose just one image from the
Mpyramid. Such images can be represented using tree pyramids ... Tpyramids. 

Tpyramid is a tree, every node of the Tpyramid has 4 child nodes.


 Quadtrees

Quadtrees are modifications of Tpyramids. 

Every node of the tree except the leaves has four children (NW: northwestern, NE: northeastern, SW:
southwestern, SE: southeastern). 

Similarly to Tpyramids, 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
