Transcript CS654: Digital Image Analysis

CS654: Digital Image Analysis
Lecture 3: Data Structure for Image
Analysis
Recap of Lecture 2
• Image digitization
• Image acquisition
• Sampling
• Quantization
Today’s 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
𝐴
𝐿3
𝐿2
𝐿4
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
1
2
3
2
1
4
5
3
4
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 𝑃𝑘−1 and 𝑃𝑘
𝐹 𝑘, 𝑖, 𝑗 = (𝑘 − 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
Disadvantages
• To store recursive definition
• 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