Computer Graphics & Geometry

Polyline Approximation Of Single-Valued Digital Curves Using Alternating Convex Hulls

Mohamed Ali Said
Eng. Math. & Phys. Dept.,
Faculty of Eng., Zagazig Univ., Zagazig, Egypt.
e-mail:

Contents

• Abstract
• 1. INTRODUCTION
• 1.1 Motivation
• 1.2. Statement Of The Problem
• 1.3. Literature Review
• 2. THE CONVEX HULLS
• 3. THE PROPOSED METHOD: ALTERNATING CONVEX HULLS
• 3.1 Items Of The Method
• 3.2 Algorithm Of The Method
• 3.3 Comparison With Hershberger and Snoeyink Work[12] and [13]
• 4.EXPERIMENTAL RESULTS
• 4.1 The First Case : (Single Peak Symmetric Curve)
• 4.2 Second Case: (Multi-Peak Curve)
• 4.3 Third Case: ( Polyline )
• 5. CONCLUSIONS AND FUTURE WORK
• REFERENCES

ABSTRACT

Curve approximation by connected series of line segments leads to data compression, which is required for higher level processing of that curve. The approximation process should comply with two contradicting goals: smoothing out the curve and, in the same time, preserving sharp changes in the curve. In this work the concept of the alternating convex hull is introduced and is then used to develop a new method that generate polyline approximation for single-valued digital curves. The suggested method has the ability to deal with closed curves if they decomposed to two single-valued curves. The method is hierarchical in nature, that is, the approximation varies from coarser to finer, using nested alternating upper/lower hulls, to comply with error tolerance specified. Experimental results show the success of the method in achieving the required approximation.

KEYWORDS: Alternating convex hulls, single-valued digital curves, polyline approximation, hierarchical approximation, upper hull, lower hull.

Digital curves are the contours of many objects dealt in computer graphics, computer vision, image processing, or cartography. Approximation of such curves to a connected series of line segments leads to data compression. Data compression economize, facilitate, and speed shape description, recognition, and matching. The ratio of the original (uncompressed) data size to the compressed data size is referred to as the compression ratio [1]:

Compression Ratio =(Uncompressed data size)/(Compressed data size)

Replacing a curve segment by a straight-line segment leads to data compression since only two points describe a straight-line segment.

Replacing curve segment by a straight-line segment is intended to reduce less important curve fluctuations, thus has the effect of smoothing locally. Globally, we need to preserve sharp changes in the given curve as they characterize the curve.

Thinking of the convex hull of a set of points we see that its sides are straight-line segments and its vertices are the extreme points of that set in some sense.

In this work, regarding the reasoning in the last two paragraphs, a trial is made to find a link between the approximation problem at hand and convex hulls since convex hull is a ready-made building block in computational geometry.

It is to be noted that only single valued curves are considered here as they are the building blocks for general parametric curves. A general parametric curve consists of three single valued curves; x = x(t), y = y(t), and z = z(t). Another note is that the vertices of the output polyline belong to the points of the input curve to allow for using convex hull in determining them. The vertices of the convex hull of a set of points belong to that set of points.

Given a single-valued digital curve as a sequence of n points P={(x_j , y_j ), j=1,�,n} and an allowable error tolerance ε . It is required to replace this sequence of points by a connected series of line segments, each segment with x_k ≤ x ≤ x_k+m has the form: y(x)=y_k + (x-x_k)� (y_k+m �y_k)/(x_k+m �x_k), for some specified values of k and m, such that the maximum perpendicular distance between the curve-segment points and the approximation line of that segment does not exceed the allowable error bound ε, that is:

= ε, k ≤ j ≤ k+m. Where j varies on the curve-segment points. The problem now is to determine k and m for each segment and thus the set of vertices V of the approximation polyline such that V is a subset of P. The approximation polyline should realize the error criteria, each side perform local smoothing, and globally sharp changes is preserved. This is done using the proposed method.

Through a search on the internet I noticed that there is a lot amount of work on the polygonal approximation of curves since 1960s till now. However the material I have got on the subject is limited and I will try to summarize it in the rest of this section. Davis [2] has used the Haar transform to solve the problem. In this method the slope of the curve is approximated to piece �wise constant function. Miyaoku and Harada [3] proposed a curvature based polygonal approximation. In this method the curvature information of each point is considered as the weight of this point. Gunther and Dominguez [4] compared the performances of three curve representation scheme: the strip tree, Bezier curve-employing methods, and the arc tree scheme. They concluded that arc tree outperform the other two. In arc tree representation a curve is divided into several arcs of equal length. The end points of these arcs are connected with line segments to form a polygonal path, which serves as an approximation of the curve. Sheu and Hu [5], Meek and Walton [6] proposed methods that approximate a curve using circular arcs and line segments. As a related problem, Zhu and Chirlian [7] presented algorithm for critical point detection of 2D digital shapes, and Liyuan Li and Weinan Chen [8] studied corner detection as a fuzzy classification problem that contains three stages: evaluation, classification, and location.

An alternative to the above-mentioned approaches is the suggested alternating convex hull approach. In this approach we introduce the concept of alternating convex hull and then we use it to solve the problem. An important advantage is that this approach makes use to convex hull, which is a ready-made building block in computational geometry.

It is to be noted that convex hull is utilized by other authors in solving line simplification problems. The difference between them and the proposed method is made clear in section 3.3.

1.4. Organization Of The Paper

Section 2 is devoted to outline some necessary topics of convex hull, which is the corner stone of the proposed method. The proposed method, the alternating convex hull method, is explained in section 3. Section 4 is devoted to the experimental results of the proposed method. In section 5 we set the conclusions and the future work intended.

One of the first problems studied in computational geometry is the computation of planar convex hulls. Given a set P of n points in the plane, the convex hull CH(P) is the smallest convex set that contains P. To be more precise, it is the intersection of all convex sets that contain P. Practically CH(P) is a unique convex polygon whose vertices are points of P and that contains all points of P.

Many algorithms are available for computing convex hull, see for example [7], [8], and [9]. The complexity of computing convex hull is stated in [7] in the form of a theorem: The convex hull of a set of n points in the plane can be computed in O(n log n ) time. In incremental algorithms, convex hull is computed in two stages, the first is to compute the upper hull which contains the convex hull edges bounding the convex hull from above, the second stage is to compute the lower hull which contains the convex hull edges bounding the hull from below, see Fig.1. A natural way to represent convex hull is to list its vertices in clockwise order , starting with an arbitrary one, say the left most one.

3. THE PROPOSED METHOD: ALTERNATING CONVEX HULLS

3.1 Items Of The Method

The method is portrayed through the following items:

1^st, convex hull is governed by the extreme points of a point set. This makes convex hull candidate for preserving sharp changes in a curve point set.

2^nd, the edges of the convex hull are straight line segments . This makes convex hull candidate for smoothing less important changes in a curve point set since a curve segment is replaced by a straight line segment.

3^rd, the above two items can be used to realize the philosophy of smoothing while maintaining sharp changes in an approximation process.

4^th, since convex hull consists of two parts, the upper hull and the lower hull, one of them only can be used to approximate a single-valued digital curve. In the proposed method the upper hull is used as a first approximation to the input curve.

5^th, convex hull of a point set is unique and it does not depend on the error tolerance allowed in the approximation process. This is a drawback from the point of view of using convex hull in an approximation process that varies from coarse approximation to a fine approximation as required by the allowable error. This drawback is made more precise in the following theorem:

Theorem:

Let P={p_i=(x_j , y_j ), i=1,�,n such that x_j+1 � x_j =1 pixel and for each x_j there is only one y_j associated with it} be the set of points of a single-valued digital curve and let V= {v_j = (x_j , y_j ), i=1,�,N } be the set of vertices of the upper hull of the convex hull of the sequence P. Then V partition P into (N-1) subsets S_j ={ set of points starts at v_j and ends at v_j+1 } with the property that the union of the upper hulls of S_j is the upper hull of the set P.

The proof that the vertices of the upper hull partition the set of points of the single-valued digital curve follows directly from

1. The set of points of the single-valued digital curve form a sequence starts at the left most point and ends at the right most point.
2. The upper hull and hence its vertices is unique for a given set of points.

To prove that the union of the upper hulls of the subsets S_j forms the upper hull of the set P we proceed as follows

Suppose that there is a vertex T between v_j and v_j+1 then T either lies above the edge v_j v_j+1 and this contradicts the fact that all the points must lie below the upper hull, or T lies below the edge v_j v_j+1 and thus the route v_j T v_j+1 of the upper hull becomes nonconvex which contradicts the fact that the upper hull must be convex. So the upper hull of S_j consists only of the edge v_j v_j+1, thus the union of these segments forms the upper hull of the set P. A similar proof can be made if we consider the lower hull �

Now, we continue in portraying the proposed method and overcoming the drawback mentioned above:

6^th, the vertices of the upper hull, generally, are not the vertices of the lower hull except for the start and end vertices. So, if we take a curve segment S_j which starts at the vertex v_j and ends at the vertex v_j+1, its upper hull is v_j v_j+1. To get more vertices and hence better approximation on this segment, we find the vertices of its lower hull. The vertices of the lower hull partition S_j into smaller subsets say R_k, 1≤ k ≤ w-1 if the number of vertices of its lower hull is w. If we need much better approximation we can find the vertices of the upper hull of each subset R_k.

Thus, as we go from coarse approximation to finer ones we alternate between upper hulls and lower hulls nested in each other and hence the name of the method, alternating convex hulls.

3.2 Algorithm Of The Method

Given a single-valued digital curve as {(x_j,y_j), i=1,�,n such that x_j+1 � x_j =1 pixel} and an allowable error bound ε, the algorithm approximate the curve by a polyline whose vertices lies on the curve such that the maximum vertical deviation between the polyline and the curve is less than the allowable error bound ε. The approximation process is based on the philosophy of smoothing while maintaining sharp changes.

INPUT: Curve points {(x_j,y_j), i=1,�,n} and error bound ε in pixels.

OUTPUT: Set of vertices of the approximation polyline {(x_j,y_j), i=1,�,k}

METHOD:

1. Input the sorted set of points P of a single-valued digital curve and the error tolerance ε.
2. Find the vertices of the upper hull of the set P and store these vertices in the list of vertices of the sought for approximation polyline. These vertices divide P into subsets.
3. For each subset check the satisfaction of the error tolerance ε, if not satisfied subdivide it into smaller subsets using the vertices of the alternate hull (upper/ lower) of this subset and append these vertices to the list of vertices of the approximation polyline.
4. Sort the list of vertices of the approximation polyline . Each two successive vertices confine between them a subset of the curve points.
5. Repeat step (3) and (4) until the error tolerance ε is satisfied everywhere.
6. Output the list of vertices of the approximation polyline.

4.EXPERIMENTAL RESULTS

4.1 The First Case : (Single Peak Symmetric Curve)

The single-valued curve y = 100 exp[-(x-50)/25]² is digitized at 101 points , from x = 0 pixel to x = 100 pixel, and is shown in Fig.3-a. The polyline approximation of the curve at different levels of error tolerance ε is shown in Fig.3-b to f.

In Table 1, the number of vertices of the approximation polyline at different levels of ε and the compression ratio of the data are shown.

Table 1

The above figure shows that the method preserves symmetry.

4.2 Second Case: (Multi-Peak Curve)

The single-valued curve y = 50(1 + sin t)e^-t/10 , t=�(x-12.5)/25

is more complicated than the first one. This curve possesses more features than the first one. The curve is digitized into 101 points from x = 0 to x = 100 pixels. The approximation process at different levels of error tolerance ε is shown in Fig.4-b to i while the original curve is shown in Fig.4-a. The variation of the number of vertices of the approximation polyline and the compression ratio of the data is shown in Table 2.

Table 2

The above figure shows that the method do well with multi-peak curves.

4.3 Third Case: ( Polyline )

Here we show that the method can recover a polyline into the same polyline. The function

is digitized into 101 points from x = 0 to x = 100 pixels and is shown in Fig.5-a. The approximation process is proceeded as shown in Fig.5-b to k according to the input error tolerance ε. The variation of the number of vertices of the approximation polyline with ε and the compression ratio of the data are all tabulated in Table 3.

Table 3

The above figure shows that the method can recover polylines.

5. CONCLUSIONS AND FUTURE WORK

The alternating convex hulls method is introduced and is used to approximate single-valued digital curves into a polylines. The approximation is hierarchical from coarser to finer, through nested alternating upper/lower hulls, to comply with the allowable error bound. The alternating convex hulls method realize the philosophy of averaging (smoothing) while maintaining sharp changes. The alternating convex hulls method uses the concepts of convex hulls which is well established working block in computational geometry. This gives the method the advantage of compatibility with the other works in computational geometry. The performance of the method on curves with various complexities shows that the method is reliable, robust and rapidly converges to the original curve when the error tolerance is zero. A special bonus to the method is that it recovers polygonal curves with the minimal number of vertices, the number of vertices of the original curve (refer to the three cases in sections 4.1, 4.2, and 4.3 when e = 0 ). Also, the method preserves symmetry (refer to case 1 in section 4.1). The method has the nice property that the vertices of the approximation polyline is concentrated at the portions of the curve where critical points takes place, specially at the points of high curvature. The method allows the use of the perpendicular distance between curve-points and the approximating polygon, as an error measure.

In this work we confine ourselves with single-valued curves. The next step is to deal with general digital curves especially closed ones through the decomposition of such curves into single-valued components.

REFERENCES

Computer Graphics & Geometry