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

Fig. 4 (a) shows a concave object. For this object, Step 1 takes 27 iterations and
Fig. 4 (b) through Fig. 4 (e) show the intermediate results after four selected iterations
(iteration 3, 9, 15, and 21). Fig. 4 (f) is the result of Step 1 after 27 iterations and
Fig. 4 (g) is the result of Step 2 after 3 iterations. The resulting convex hull of the
object is shown in Fig. 4 (h).
(a) (b) (c) (d)
(e) (f) (g) (h)
Fig. 4. Illustration of Step 1 and Step 2 of the convex hull algorithm
3.4 Method for Finding the Minimum Bounding Rectangle
The new algorithm for finding the minimum bounding rectangle is based on two theo-
rems proven by Freeman and Shapira [6]. The four steps of our algorithm are given
below.
Theorem 1. The rectangle of minimum area enclosing a convex polygon has a side
collinear with one of the edges of the polygon.
Theorem 2. The minimum-area rectangle encasing the convex hull of a simple,
closed, chain-coded curve is one and the same as the minimum-area rec-
tangle encasing the curve.
Step 1. For a convex object, this step is skipped. For a concave object, the convex
hull of the given object and its hierarchical representation are obtained using the algo-
rithm described in Section 3.3. The straight line segments of the convex hull speci-
fied by the Level-2 nodes represent the object as a convex polygon. A concave object
and its convex polygon are shown in Fig. 5 (a) and Fig. 5 (b).
Step 2. From Theorem 1 and Theorem 2 described above, the minimum bounding
rectangle must have an edge collinear with one of the edges of the polygon. The con-
struction of the bounding rectangle that is collinear with a hull edge is illustrated by
constructing the bounding rectangle that is collinear with hull edge AB in Fig. 5 (c).
Let m be the slope of the line AB . Let p be the starting point of a curve segment that is
farthest from the line AB . Let p1 be the point that is farthest from AB which is ob-
tained by trial-and-error starting from p .