Transcript No Slide Title

Quadtrees,
Octrees and their
Applications in
Digital Image
Processing
Hierarchical Data Structures for
Computer Vision and Image
Processing
Definition of pyramids
Explanation of Quadtrees and
Octrees
Techniques used for generation
Applications
What is a pyramid?
A(0)
1
2 *2
1
A(1)
A(2)
22*22
Example of a four layer
pyramid
20*20
21*21
22*22
Example of a four layer
pyramid
Layer 3
23*23
How partitioning is done?
1 partitioned to 2 2 = 4
How pyramid is build?
•From top to bottom
•From bottom to top
•Always recursively
•Good exercise in recursion and arrays
•Treat image as a Boolean or discrete function, what is the
counterpart of these type of recursions?
Another Way of Partitioning
For simplicity, dimension = 2
Partitioning at any level i from i-1 can be
done by defining a two-dimensional
array A(i) for the i-th level
The partitioning
Algorithm
Cell (j,k) at
level i-1
The partitioning
Algorithm
Pyramids versus trees
Pyramids are interlinked (for instance by
indices) sequences of arrays with hierarchy.
Similarly we can create trees to
define this hierarchy
Trees can be more convenient for
processing
Types of pyramids:
quadtree and octree
Recursive Tree Decomposition
Think how to write this
software in Lisp
Construction of the quadtree
Advantages of the
quadtree
Trees can be well manipulated in software, for
instance in Lisp
Disadvantages of the
quadtree
Structure of an
Octree
Structure of an
Octree
Advantages of the
Octrees
Applications of these data structures
•The quadtree, octree and binary tree decomposition methods are
widely used in two and three dimension image processing and
computer graphics
•Some of the application areas involve:
• the image data structure,
• region representation,
• picture segmentation,
• component labeling,
• image smoothing,
• image enhancement,
• data compression
Applications of these data structures
• Pattern recognition
• Shape analysis
• Image segmentation
• Region matching
• Images can be represented with pyramids and
thus, both local and global feature extraction is
possible
Application to pattern
recognition
Tree Decomposition in Pattern
Classification
Tree decomposition can be used not only in image
space but in transform space or feature space
Tree Decomposition in Pattern
Classification
Tree Decomposition in
Pattern Classification
Application to Edge Detection
•The edge detection task can be accomplished by applying a
point-neighborhood operator or the edge detector to every
point of a large matrix
•The algorithm for this works as follows:
•An edge detector is applied at each point in the starting
level
•At each point, if the value exceeds a threshold, the
operation is applied to the descendants of the point in the
next finer level.
Application to Feature Detection
Pyramides limit scope of the
search
Pyramides are used for
feature detection
Pyramides are used for
feature extraction
Application to Feature Detection
The disadvantage of this method is that
the reduction of resolution will affect
the visual appearance of edges and
small objects
•In particular, at a coarser level of resolution:
• edges tend to get smeared and
•region separation may disappear
Extracting compact objects
• Many image analysis tasks require the extraction of compact
objects from a background, where
• the shapes of the desired objects are not known,
• except for the fact that they are compact
• Image segmentation using pyramids can be applied to extract such
objects.
• “Spot detectors” are applied to image at each level of the pyramid:
• this is equivalent to applying spot detectors of many sizes to fullresolution image
Extracting compact
objects
Extracting compact objects
•Three sets of information are represented in the
pyramid structure
•1. Gray level
•2. Edge magnitude and direction
•3. Surroundedness
•The interaction between the different types of
information at each level of the pyramid leads
to the final segmentation
Using Quadtrees to Smooth Images
• Digital images usually contain
noise of various kinds.
• Most image processing tasks are
simplified if noise removed
•A general approach to noise
removal is to smooth the image
• Smoothing done by replacing
each pixel value by a new value
which is a function of the values
in some neighborhood of the
pixel.
Using Quadtrees to Smooth
Images
Using Quadtrees to Smooth
Images
Using Quadtrees to Smooth Images
Using
Quadtrees
to Smooth
Using Quadtrees
to Smooth
Images Images
Using
Quadtrees
Smooth
Using
Quadtrees
to Smoothto
Images
Images
Method 2
1. Constructs a quadtree from an image
2. Replaces each pixel by the gray level of the leaf to
which each corresponds
Hierarchical Coding of Binary Images
Hierarchical Coding = to segment a picture into
the largest possible uniform areas and to transmit a
hierarchical representation of these areas.
Quadtrees can be used for coding
Pictures with large uniform areas can be highly
compressed
Hierarchical Coding of Binary Images
The transmission result can be
recreated by the receiver as soon as
sufficient information about
transmitted picture has been
gathered
Quadtree Compression
G = goto ground
W=white
B=black
w
Second level
w
Hierarchical Coding of
Binary Images
Hierarchical Coding of
Binary Images
•A bit assignment can be selected
for the symbols
•The coding can also be extended to
three dimensions with the use of
octrees
Problems to solve:
•Use pyramide for edge detection
•Treat a large (12 variables) Karnaugh Map as an
image. What is the counterpart of Shannon
Decomposition in terms of binary trees?
•Generalize to 4-valued logic and show link to
quadtrees
•Generalize to 8-valued logic and show link to octrees
•Disscuss general links between discrete functions,
images and compression methods.
Problems to solve:
•Use octree to represent the space for robot
manipulator
•Use this space description to plan precise assembling
operations.
References
References
References
References