Digital Signal Processing Reference
In-Depth Information
A
System for Image
/
Vadeo Object Query By Shape
VOS-DOT EXTRACTION
In this section, we list the steps in the extraction process that produce
the shape descriptor from a given shape. The extraction process is di-
vided into two parts: the first transforms VOS into an ordered tree and
the second transforms the ordered tree into a robust shape descriptor
via DOT representation.
EXTRACTION PROCESS: CONTOUR TO ORDERED
TREE
The first section shows the calculation of the VOS, and uses the mul-
tiresolution property of the VOS to derive the initial ordered tree repre-
sentation of the shape. After normalizing the size of the shape contour,
we apply these steps, as shown in Figure 6.10:
1.
Order the contour
We arbitrary pick a linear order for all the points on our contour,
giving an index value to every point on the contour.
2.
Calculate the Voronoi Order
For every point on the interior of the contour, we find the index of
the closest point of the contour. The Voronoi Ordered Space can be
calculated in
O
(
n
log(
n
)), where
n
is the number of pixels of shape
image. By mapping the grid of the image space to a graph, the
Voronoi Ordered Space calculation is a modified Dijkstra's algorithm
[Cormen et al., 1990] that initially places each point on the contour
into the set of points of minimal distance. After the minimum dis-
tance calculations, the index of minimal distant contour point can be
propagated to all pixels in
O
(
n
) (where
n
is the number of pixels in
the space).
3.
Calculate the Voronoi Order Skeleton
For a given point, the VOS is calculated by Eq. 3.1, i.e., maximum
absolute difference of the Voronoi Order from one pixel and any of
its adjacent pixels. Since the number of adjacent pixels is a constant,
this step runs in
O
(
n
) (where
n
is the number of pixels in the space).
4.
Threshold the Voronoi Order Skeleton
The value of the Voronoi Skeleton image is related to the support
structure strength. Therefore, a simple thresholding can remove noise
and small protrusions on the contour.
The thresholding value of 5-
10% is a good value.
5.
Find pixel-based ordered tree representation
After thresholding, the remaining non-zero pixels form the pixel-
Search WWH ::
Custom Search