Computer Graphics & Geometry
Mohamed Ali Said
Eng. Math. & Phys. Dept.,
Faculty of Eng., Zagazig Univ., Zagazig, Egypt.
email:
Contents
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 singlevalued digital curves. The suggested method has the ability to deal with closed curves if they decomposed to two singlevalued 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, singlevalued digital curves, polyline approximation, hierarchical approximation, upper hull, lower hull.
1. INTRODUCTION 1.1 MotivationDigital 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 straightline segment leads to data compression since only two points describe a straightline segment.
Replacing curve segment by a straightline 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 straightline 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 readymade 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.
1.2. Statement Of The ProblemGiven a singlevalued 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} + (xx_{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 curvesegment 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 curvesegment 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.
1.3. Literature ReviewThrough 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 curveemploying 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 abovementioned 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 readymade 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.
2. THE CONVEX HULLSOne 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.
Fig.1 Upper hull and Lower hull 
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 singlevalued 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 singlevalued 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 (N1) 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.
Fig.2 Demonstration of the Theorem
The proof that the vertices of the upper hull partition the set of points of the singlevalued digital curve follows directly from
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 ≤ w1 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 singlevalued 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:
3.3 Comparison With Hershberger and Snoeyink Work[12] and [13]
In Hershberger and Snoeyink [12], [13], to approximate the chain from V_{n} to V_{m} , start with the line segment V_{n} V_{m} . If the farthest vertex from this segment has distance at most e , then accept this approximation. Otherwise, split the chain at this vertex and recursively approximate the two pieces. The convex hull is used to find the farthest point as they prove that the farthest point is a vertex of the convex hull of the chain under consideration.
Regarding the proposed method in this paper explained in section 3.1, the difference between it and [12], [13] become clear.
4.EXPERIMENTAL RESULTS
4.1 The First Case : (Single Peak Symmetric Curve)
The singlevalued curve y = 100 exp[(x50)/25]^{2}^{} is digitized at 101 points , from x = 0 pixel to x = 100 pixel, and is shown in Fig.3a. The polyline approximation of the curve at different levels of error tolerance ε is shown in Fig.3b 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
Error tolerance (ε) in pixels 
ε >98 
9≤ε≤98 
1≤ε≤8 
ε =0 
Number of vertices Of the polyline 
2 
17 
69 
101 
Compression ratio 
50.5 : 1 
6 : 1 
1.5 : 1 
1 : 1 
(a) Original 
(b) ε > 98 

(c) 9 ≤ ε ≤ 98 
(d) 1 ≤ ε ≤ 8 
(e) ε = 0 

Fig.3 Progress of the approximation process 
The above figure shows that the method preserves symmetry.
4.2 Second Case: (MultiPeak Curve)
The singlevalued curve y = 50(1 + sin t)e^{t/10} , t=�(x12.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.4b to i while the original curve is shown in Fig.4a. 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
Error tolerance (ε) in pixels 
ε>86 
52≤ε≤86 
6≤ε≤51 
4≤ε≤5 
ε =3 
ε =2 
ε =1 
ε =0 
Number of vertices Of the polyline 
2 
15 
29 
40 
51 
59 
67 
101 
Compression Ratio 
50.5:1 
6.7 : 1 
3.5 : 1 
2.5 : 1 
2 : 1 
1.7 : 1 
1.5 :1 
1 : 1 
Original digital curve 
(b) ε > 86 
(c) 52 ≤ ε ≤ 86 
(d) 6 ≤ ε ≤ 51 
(e) 4 ≤ ε ≤ 5 
(f) ε =3 
(g) ε =2 
(h) ε = 1 
(i) ε = 0 
Fig. 4 Progression of the approximation process 
The above figure shows that the method do well with multipeak 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.5a. The approximation process is proceeded as shown in Fig.5b 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
Error tolerance (ε) in pixels 
ε >99 
56≤ε≤99 
0≤ε≤55 
Number of vertices Of the polyline 
2 
4 
5 
Compression Ratio 
50.5 : 1 
25.3 : 1 
20.2 : 1 
(a) Original digital curve 
(b) ε > 99 
(c) 56 ≤ ε ≤ 99 
(d) 0 ≤ ε ≤ 55 
Fig.5 Progression of the approximation process 
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 singlevalued 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 curvepoints and the approximating polygon, as an error measure.
In this work we confine ourselves with singlevalued curves. The next step is to deal with general digital curves especially closed ones through the decomposition of such curves into singlevalued components.
REFERENCES
[1] Umbaugh, S.E., Computer Vision and Image Processing � a practical approach using CVIPtools,pp.237239, Prentice Hall, 1998.
[2] Davis, T.J., �Fast Decomposition of Digital Curves Into Polygons Using the Haar Transform�, IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. 21, No. 8, pp. 786790, August 1999.
[3] Miyaoku, K. and Harada, K., �Effective Data Reduction by the CurvatureBased Polygonal Approximation�, IEICE Trans. Inf. & Syst., Vol. E80 D, No. 2, February 1997.
[4] G�nther, O. and Dominguez, S., �Hierarchical Schemes for Curve Representation�, IEEE Computer Graphics & Applications, pp.5563,May 1993.
[5] Sheu, H. and Hu, W., � Multiprimitive Segmentation of Planar Curves � A Two � Level Breakpoint Classification and Tuning Approach�, IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. 21, No. 8, pp.791797, August 1999.
[6] Meek, D. S., and Walton, D. J., �Approximation of Discrete Data by G^{1} Arc Splines�, ComputerAided Design, Vol. 24, No. 6, pp. 301305, June 1992.
[7] Zhu, P. and Chirlian, P.M., �On Critical Point Detection of Digital Shapes�, IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. 17, No. 8, pp.737748, August 1995.
[8] Li, L. and Chen, W., �Corner Detection and Interpretation on Planar Curves Using Fuzzy Reasoning�, IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. 21, No. 11, pp.12041210, November 1999.
[9] De Berg, M. et al, Computational Geometry � Algorithms and Applications, pp. 210, SpringerVerlag, 1997.
[10] Akl, S.G., �Optimal Parallel Algorithms for Selection, Sorting and Computing Convex Hulls�, In Computational Geometry, Toussiant, G.T., Eds., pp. 122, Elsevier Science Pub., 1985.
[11] Barber, C.B., et al, � The quickhull Algorithm for Convex Hulls�, ACM Transactions on Mathematical Software, Vol. 22, Issue 4, pp. 469483, 1996.
[12] Hershberger, J and Snoeyink, J, �Speeding Up The DouglasPeucker Line Simplification Algorithm�, Proceeding Of The 5^{th} International Symposium On Spatial Data Handling , Volume 1, Pages 134143, 1992.
[13] Hershberger, J and Snoeyink, J, �Cartographic Line Simplification and Polygon CSG Formulae in O(n log^{*}n) Time�, Workshop on Algorithms and Data Structures, Pages 93103, 1998.
Computer Graphics & Geometry