Information Technology Reference
In-Depth Information
3 Feature Extraction
We have developed computationally efficient algorithms [4] to extract general shape
features of a curve, and the convex hull and the minimum bounding rectangle of a
closed curve. These geometric features are obtained directly from the graph/tree hier-
archical data structure that contains the boundary information produced by the seg-
mentation system. As the hierarchical representation permits fast computation of
several features of open and closed curves, the approach is referred to as the
trans-
form-and-conquer approach
.
Section 3.1 illustrates the terminology used in the feature extraction algorithms.
Section 3.2 discusses the general shape features of a curve such as concave-up, con-
cave-down, local minimum, local maximum, inflection points, and concavities. Sec-
tion 3.3 and Section 3.4 briefly introduce the methods for finding the convex hull and
the minimum bounding rectangle, respectively. The details can be found in [4].
3.1 Terminology
The
network sequence
of a curve is defined as the ordered sequence of the curve ex-
traction network numbers which extract the curve segments of the curve. The magni-
tude of the i
th
element of the
network difference sequence
is obtained as the absolute
difference of the (i+1)
th
and i
th
elements of the
network sequence.
The sign of the i
th
element of
network difference sequence
is determined based on the orientation of the
(i+1)
th
curve segment relative to the i
th
curve segment. If the (i+1)
th
curve segment
lies to the right of the i
th
curve segment, then the sign is negative. Otherwise, it is
positive. The
slope differential sequence
is obtained by adding contiguous blocks of
elements of the same sign in the
network difference sequence.
3.2 General Shape Features
The general shape attributes of a curve such as concave-up, concave-down, local
minimum, local maximum, inflection points, and concavities can be identified by
simply using the
network sequence
, the
network difference sequence
, and the
slope
differential sequence
of the curve.
Concave-Up and Concave-Down.
An open curve is concave-up over an interval if
the first derivative is increasing over the interval. Therefore, a
network sequence
of
increasing numbers identifies concave-up portion of the curve. Similarly, a
network
sequence
of decreasing numbers identifies concave-down portion of the curve. Also,
the positive and negative numbers in the
slope differential sequence
identify concave-
up and concave-down segments of the curve, respectively. The
network sequence
and
the
slope differential sequence
for the curve in Fig. 3 are [4 3 2 1 2 3 4 3 2 1] and
[-3 +3 -3], respectively. Note that the arrow indicates the starting point of the curve
and the curve is traversed from left to right. From these sequences, one can easily
determine the general shape of the curve which consists of two concave-down
segments and one concave-up segment.
Local Minimum and Local Maximum.
The location of each local minimum of a
curve is identified by a transition from the curve extraction network N
1
or N
2
to the
Search WWH ::
Custom Search