Content-Based Retrieval of Aurora Images Based on the Hierarchical Representation - Advanced Concepts for Intelligent Vision Systems - page 252

curve extraction network N 3 or N 4 . This is because the curve segment extracted by N 1
or N 2 has a negative slope and the curve segment extracted by N 3 or N 4 has a positive
slope. A transition from a curve with a negative slope to a curve with a positive slope
defines a local minimum. Similarly, a local maximum is identified by a transition
from the curve extraction network N 3 or N 4 to the curve extraction network N 1 or N 2 .
This is because the curve segment extracted by N 3 or N 4 has a positive slope and the
curve segment extracted by N 1 or N 2 has a negative slope. A transition from a curve
with a positive slope to a curve with a negative slope defines a local maximum.
Therefore, it is obvious that the curve in Fig. 3 has two local maxima and one local
minimum, and their locations are also known.

Inflection Point and Concavity. An inflection point is defined as a point where the
curve changes from concave-up to concave-down or vice versa. Each sign change in
the slope differential sequence identifies an inflection point. In general, the number
of inflection points is equal to the length of the slope differential sequence for a
closed curve and (length of the slope differential sequence - 1) for an open curve.
Therefore, the curve in Fig. 3 has two inflection points as identified by two sign
changes in its slope differential sequence [-3 +3 -3]. The first inflection point is on
the curve segment extracted by N 1 (fourth curve segment) and the second inflection
point is on the curve segment extracted by N 4 (seventh curve segment). For a closed
curve, the number of inflection points is even. The inflection points are useful in
identifying the number and location of concavities. The convex hull algorithm pre-
sented in the next section makes use of inflection points to identify concavities.

Fig. 3. An open curve that consists of ten curve segments

3.3 Method for Finding the Convex Hull

The new convex hull algorithm utilizes the hierarchical representation of the concave
object and produces the modified hierarchical representation for the resulting convex
polygon. The algorithm uses a two-step approach. While Step 1 identifies the
concavities at the curve segment level, Step 2 identifies the concavities missed in Step
1 using line segments. Step 1 is based on the observation that a positive number in the
network difference sequence indicates the presence of a concavity and also provides
rough information of its location. The algorithm uses a simple decision function [5] to
determine if a given point lies to the left or right side of a given line. Let P 0 (x 0 , y 0 ),
P 1 (x 1 , y 1 ), and P 2 (x 2 , y 2 ) be the three points. Using two vectors P 1

P 0 ,
the value of the decision function D is obtained by the following
equation:

− P 0 and P 2 −

(1)

D = [(x 1 − x 0 )(y 2 − y 0 ) − (x 2 − x 0 )(y 1 − y 0 )].

It has been shown that D is positive if P 2 is to the left of P 0 P 1 , and D is negative if P 2
is to the right of P 0 P 1 . If all three points are collinear, then D is zero.