Advanced
Polar-Natural Distance and Curve Reconstruction
Polar-Natural Distance and Curve Reconstruction
International Journal of Contents. 2015. Jun, 11(2): 9-14
Copyright © 2015, The Korea Contents Association
  • Received : January 29, 2015
  • Accepted : April 20, 2015
  • Published : June 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hyoung-Seok Kim
hskim@deu.ac.kr
Ho-Sook Kim

Abstract
We propose a new distance measure between 2-dimensional points to provide a total order for an entire point set and to reflect the correct geometric meaning of the naturalness of the point ordering. In general, there is no total order for 2-dimensional point sets, so curve reconstruction algorithms do not solve the self-intersection problem because the distance used in the previous methods is the Euclidean distance. A natural distance based on Brownian motion was previously proposed to solve the self-intersection problem. However, the distance reflects the wrong geometric meaning of the naturalness. In this paper, we correct the disadvantage of the natural distance by introducing a polar-natural distance, and we also propose a new curve reconstruction algorithm that is based on the polar-natural distance. Our experiments show that the new distance adequately reflects the correct geometric meaning, so non-simple curve reconstruction can be solved.
Keywords
1. INTRODUCTION
The problems of reconstructing a shape from sample points appear in many scientific and engineering applications. Because of its practical importance, many algorithms have been proposed over the last two decades in the fields such as the reverse engineering of geometric models and image processing of medical images. Especially, curve reconstruction plays an important role in the shape reconstruction problems because most of boundaries of shapes are represented by the set of curves.
Curve reconstruction is the problem of computing a piecewise linear approximation to a curve from a set of sample points. So curve reconstruction consists of two steps: the first step is how to order the given points and the second step is how to interpolate the ordered points [1] - [4] . The first step is called the point ordering problem . Many approaches have been suggested for the point ordering problem. Edelsbrunner et al. [5] defined the α-shapes of point sets as the underlying space of a simplicial complex. Attali proposed the r -regular shape method, where the r -regular shapes are characterized by requiring that any circle passing the points on the boundary has radius greater than r [6] . These methods deal with only uniform sample points. For the non-uniform sample points, Amenta et al. [7] proposed the first algorithm to reconstruct a curve from non-uniform sample points with guarantee. This algorithm uses the Voronoi diagram and the Delaunay triangulation of the sample points. Dey et al. [8] proposed the nearest neighbor approach based on the properties of Voronoi diagrams. These algorithms work only under the assumption that the sample points are dense and do not work for non-simple curve reconstruction because they reconstruct curves without the consideration of curve's orientation [9] - [12] . Kim et al. [3] proposed a point ordering approach with a natural distance to reflect the orientation. The natural distance is based on properties of Brownian motion so that the approach enables us to give 1-dimentional order to points on 2-dimentional space. However, the approach missed important geometric property: the right direction of Brownian motion.
In this paper, we introduce a new natural distance based on polar coordinates so that the distance enables our algorithm to reflect the direction properly and resolve the non-simple curve reconstruction.
2. POLAR-NATURAL DISTANCE
In this section, we review the properties of Brownian motion and the natural distance [3] . First of all, we will discuss naturalness for a direction-based distance. In order to do this, we define the naturalness for a distance between points which is suitable to order the points on a 2D plane. For chosen consecutive points p i-1 and pi which are already ordered, we define the ordering direction vector as vector
PPT Slide
Lager Image
. For the ordering direction, what will be the next point p i+1 ?
Let P be the sample point sets. We define the candidate set C i+1 ( ri ) for the next point p i+1 as
PPT Slide
Lager Image
as shown in Fig. 1 , where d ( p , q ) is the Euclidean distance between p and q , and ri is the radius of the ordering neighborhood. The radius ri is computed by the average length of the consecutive points:
PPT Slide
Lager Image
PPT Slide
Lager Image
The candidate set Ci+1 for the next point pi+1.
If a measure μ prefers to pick up the next point q C i+1 satisfying the following conditions, then we say that the measure has a naturalness and call it as a natural distance :
(C-1) Suppose pi and q 1 , q 2 ,⋯ , qm C i+1 are on the same line. Then the measure prefers to choose the closest one qk to the previous point pi among qj ’s :
PPT Slide
Lager Image
(C-2) Suppose q 1 , q 2 ,⋯ qm C i+1 are on the same circle with center pi , and the angle between
PPT Slide
Lager Image
is strictly smaller than the angle between
PPT Slide
Lager Image
. Then qk is more preferable to pj :
PPT Slide
Lager Image
The condition (C-2) implies that, among the points with the same Euclidian distance from pi , we want to choose the point which makes the arc, made by connecting the chosen points, most smooth as shown in Fig. 2 . To show the naturalness of distance, we adopt a simple property of one dimensional Brownian motion.
PPT Slide
Lager Image
Geometric conditions for naturalness of ordering: (a) (C-1) condition and (b) (C-2) condition
An easier way to understand Brownian motion is to think of it as a continuous version of the random walk process. As documented in an enormous amount of literature on stochastic processes such as [17], [18], Brownian motion has several properties which explain the irregular motion observed in nature; for example, in two-dimensional space the motion of pollen grains suspended in liquid which does not flow. Among those, we use only the following property throughout this paper:
(P.B) For given time T, Brownian motion starting at 0 is a random variable normally distributed with mean 0 and variance T.
Roughly speaking, (P.B) means that the set of original points on the real line at time 0, which move randomly, become the set which is normally distributed with mean 0 and variance T after T time. Now, we will introduce the polar-natural distance function by understanding the right geometric meaning of the Brownian property.
We assume that p i-1 and pi are already chosen and q is an arbitrary point in C i+1 . In order to determine the next point p i+1 , Kim et al. [3] defined the natural distance in the following manner. They applied a 2-dimension transformation so that p i-1 is on the negative x -axis and pi is the origin of R 2 . In order to help the geometric understanding, let R ( p i-1 , pi ) be the ray with the initial point pi and the directional vector
PPT Slide
Lager Image
and L ( q , p i-1 , pi ) be the perpendicular line to R ( p i-1 , pi ) passing through the point q satisfying (C-1) as shown in Fig. 3 . Therefore, the arbitrary point q can be represented by the new coordinates q = ( qt , qs ) as follows:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
PPT Slide
Lager Image
New coordinates for point q [3]
The coordinate qt is the Euclidian distance between pi and the intersection of R ( p i-1 , pi ) and L (q, p i-1 , pi ), and the coordinate qs is the signed Euclidian distance between q and the intersection of R ( p i-1 , pi ) and L ( q , p i-1 , pi ). Then we can think the pair ( qt , qs ) as the new coordinates of q . With the property (P.B) of Brownian motion, we further think of the qt -axis as the time axis with the original point pi , and qs -axis as the axis representing the value of Brownian motion.
Therefore, if qt > 0, qs is considered as a sample point of the random variable which has the normal distribution with mean 0 and variance q t as shown in Fig. 4 , then we consider the point q as one of the normally distributed points after q t time, which is randomly diffused from the original point.
PPT Slide
Lager Image
The distribution of Brownian motion [3]
The value of distribution cannot directly be applied to the natural distance because the distribution changes according to the position of q . So we transform the distribution into the standard normal distribution so that the random variable qs is transformed to the standard random variable
PPT Slide
Lager Image
. It is well known that the larger the value of the standard random variable is, the smaller the probability is. Therefore, the problem of determining the next point p i+1 is transformed into that of computing the minimum of the standard random variables. Kim et al. [3] defined a natural distance by the following manner:
PPT Slide
Lager Image
where K is a constant and plays a role of a subjective weight.
It is well known that the natural distance of Kim et al. [3] marked a turning point in the research on point ordering problem. Most of the distances used in the previous point ordering research cannot give a total order to the set of points on R 2 , whereas the natural distance can do that. So we could solve the problem of reconstructing curves having self-intersections. However, there are obvious shortcomings in the natural distance. The first is that the random variable
PPT Slide
Lager Image
used in the natural distance cannot reflect the right geometric meaning of the conditions (C-1) and (C-2. The second is that the result of point ordering is very sensitive to the value of subjective weight. The condition (C-1) shows that all points on the same line with pi have the same value qs , the condition (C-2) shows that all points on the same circle with center pi have the same value qt . So the random variable
PPT Slide
Lager Image
cannot resemble the right geometric meaning of conditions. In this paper, we introduce a new natural distance which may give a total order to two-dimensional points and reflect the right geometric meaning of conditions (C-1) and (C-2). First of all, we define the polar-natural coordinates as ( ri ( q ), θi ( q )), where
PPT Slide
Lager Image
. By using this coordinates and understanding the geometric meaning as shown in Fig. 5 , we define the polar-natural distance as
PPT Slide
Lager Image
PPT Slide
Lager Image
The new distribution of Brownian motion based on the polar-natural coordinates
3. POLAR-NATURAL DISTANCE BASED POINT ORDERING ALGORITHM
In this section, we will describe a practical algorithm for ordering points in an unorganized point cloud. Assume that there are arbitrarily scattered n points, called sample points, in R 2 . Denote the set of all sample points by P. The point ordering problem aims to choose a subset SP of P , where SP is a well-ordered set satisfying the natural conditions (C-1) and (C-2) mentioned in Section 2. In the above theoretical section, we have assumed that the first point p 1 and the second point p 2 are known. This easily enabled us to initialize the algorithm at the first point with an initial direction
PPT Slide
Lager Image
. In general, the result of the point ordering problem is dependent on the initial direction. But, in practice, p 1 and p 2 are not known. Moreover, the well-ordered subset SP may have several connected components, and may be open or closed according to the distribution of the data points. So we need to analyze the distribution of the sample points in order to find out the property of the subset SP . In general, the sample points of the unorganized point cloud for curve reconstruction may cluster in several groups and the points of each group are densely located near meaningful trajectories. So, the shape of each cluster looks like the union of bands. The objective of our algorithm is to remove outliers in each cluster and find out a well-ordered subset that plays a role of skeletons of clusters. Our algorithm consists of three major steps: data clustering, determination of the initial direction, and local point ordering.
- 3.1 Data Clustering
Most partitioning methods cluster objects based on the Euclidean distance between objects. Such methods can find only spherical-shaped clusters and encounter difficulty at discovering clusters of arbitrary shapes. We cannot apply such clustering methods directly to our problem because the shape of the input point set P is unknown. In this paper, we adopt the DBSCAN clustering algorithm based on the density, which is useful to filter out outliers and discover clusters of an arbitrary shape. The general idea is to continue growing the given cluster as long as the density in the neighborhood exceeds some threshold; that is, for each data point within a given cluster, the neighborhood of a given radius cr , called clustering radius has to contain at least a minimum number of points. By exploiting DBSCAN algorithm, we may obtain nc clusters CL 1 CL 2 ,…, CLnc , in P of a band-like shape. For each cluster CLj , we choose a point which may well represent the character of the shape of the cluster as the initial point, denoted by cpj .
- 3.2 Determination of Initial Direction
Now, we will try to determine the initial direction of the natural distance at the initial point cpj for each cluster CLj . For the sake of convenience, we set the initial point as p 1 . In order to analyze the distribution of points near p 1 , we compute the neighborhood N ( p 1 , r ) of p 1 with a given radius r, called ordering radius ; N ( p 1 , r ) = { p CLj | pd ( p 1 , p ) ≤ r }, where pd ( p , q ) is the Polar-Natural distance between two points pand q, which is defined in Section 2. And then we apply the PCA (Principal Components Analysis) to the neighborhood because the principal component analysis of a set of points gives us the mean, an orthogonal frame, and the standard deviation of the neighbors. Let q 1 , q 2 ,⋯, qm be the points in the neighborhood N ( p 1 , r ). We compute the mean m of the neighbors such that
PPT Slide
Lager Image
and then we construct the covariance matrix We compute the eigenvector of the covariance matrix which corresponds to the maximal eigenvalue so that it plays a role of the major principal axis in the neighborhood. Let
PPT Slide
Lager Image
be the unit vector on the principal axis. Then the neighborhood N ( p 1 , r ) may be subdivided into two half discs:
PPT Slide
Lager Image
Where
PPT Slide
Lager Image
If HD = ø or HD + = ø, then the point p 1 is one of the two end points of SP. Otherwise the point is a middle point of SP so that we should apply the following one-way ordering algorithm to both HD + and HD with the direction vectors
PPT Slide
Lager Image
, respectively. Let SP + and SP be the solutions of the one-way ordering problem with the initial directions
PPT Slide
Lager Image
, respectively. Then the solution SP of the original point ordering problem may be obtained by merging the subsets SP + and SP , i.e., SP = SP + SP .
- 3.3 Local Point Ordering
Now, we are ready to explain the one-way point ordering algorithm with the first point p 1 and the initial direction
PPT Slide
Lager Image
. First of all, we have to select the candidates of the next point p 2 in the neighborhood N ( p 1 , r ). It is well known that the candidate C 2 set is the same as the half disc HD + ( p 1 , r ). So, without loss of generality, we may put C i+1 = HD ( p 1 , r ). Next, we select the second point p 2 in N ( p 1 , r ) satisfying the following condition: f 1 ( p 1 ) = min pHD+(p1) f 1 ( p ), where the function f 1 ( p ) is derived from the initial direction vector
PPT Slide
Lager Image
. We have known that the above condition satisfies the properties of conditions (C. 1) and (C. 2). Then the point p 2 is added to the well-ordered set so that SP + = { p 1 , p 2 }.
In order to find out the third point p 3 we compute the candidate set C 3 that is the half disc HD + ( p 2 , r ) with the direction vector
PPT Slide
Lager Image
. The third point p 3 should satisfy the following condition: f 2 ( p 2 ) = min pHD+(p2) f 2 ( p ), where the function f 2 ( p ) is derived from the direction vector
PPT Slide
Lager Image
. Then SP + = { p 1 , p 2 , p 3 }. We apply the above process until the candidate set C i+1 is empty or the intersection of C i+1 and HD ( p 1 ) is not empty. When the algorithm meets the former condition, it generates one of the two end points for an open curve, so it has to be applied to the other region of the cluster with the direction
PPT Slide
Lager Image
. If the latter is satisfied, then the new obtained point p n1 is near the first point p 1 .We can consider the well-ordered set is a closed piecewise curve so that there is no need to continue this one-way point ordering algorithm in the cluster. The solution of the one-way point ordering problem is SP + = { p 1 , p 2 , ⋯ , p n1 }. By similar process, we may get SP = { p -n2 , p -n2+1 , ⋯ , p -1 } as the solution of the backward one-way ordering algorithm. Now, we may obtain the first connected well-ordered subset SP = SP + SP . Therefore, the global point ordering problem can be solved by applying the above process to all of clusters in P. The outline of our natural point ordering algorithm is as follows.
PPT Slide
Lager Image
- 3.4 Time Complexity
The three major steps of this algorithm are to partition the point set P into several clusters, to find out the neighbor points in N ( p , r ), and to select one point who has the minimum natural distance among them. The computational complexity of DBSCAN algorithm is O ( n log n ), where n is the number of the input cloud points. It is well-known that the algorithm is sensitive to the user-defined parameters. The second process of this algorithm runs in O ( n ) time. The process is to find out a neighborhood N ( p , r ) of a given point p and to apply the principal component analysis to the neighborhood in order to derive the initial direction. The third process is repeatedly to find out a candidate set C i+1 , and to select one point who has the minimum natural distance among the candidates. It takes O ( kM ), where k is the number of the output points in SP and
PPT Slide
Lager Image
. Our algorithm is output-sensitive. However, in the worst case, the total time complexity of this algorithm may be O( n 2 ), where the most of candidate sets have only one point as neighbors.
4. EXPERIMENTS
Our experimental results demonstrate the superiority of our point ordering algorithm based on the polar-natural distance. First of all, we compare the results of curve reconstruction for a sampled point set which are obtained by the natural distance and by the polar-natural distance.
The point set is obtained by sampling from points on two circles with different radius. Figure 6 presents two piecewise linear curves obtained by the natural point ordering method (a) and the polar-natural ordering method (b). These figures show quite different curves. The curve generated by our distance is more natural than that by the natural distance in [3] . Moreover, the polar-natural poing ordering method can be used to reconstruct a curve for the sample points set containing the noise points not on the curve as well as those on it.
PPT Slide
Lager Image
The results of curve reconstruction for a sampled point set: the natural distance and the polar-natural distance
Fig. 7 shows the results of curve reconstruction for a point cloud set. The cloud poing set was obtained by mouse dragging-and-dropping so that the global figure of the set has several self-intersections. Fig. 7 (a) does not overcome the self-intersection problem, whereas Fig. 7 (b) well reflects the global configuration of the data set.
PPT Slide
Lager Image
The results of curve reconstruction for a point cloud set: (a) the natural distance and (b) the polar-natural distance
Fig. 8 shows the process of our polar-natrual point ordering algorithm. Fig. 8 (a) is the initial point set. The set was obtained by mouse dragging-and-dropping so that the global figure of the set is the union of two ‘C’-type point sets. Fig. 8 (b) shows the middle state which has two curves. Each curve has two components SP + and SP . The final result (c) has two curves. Since our algorithm has a special key that is polar-natural distance it can solve the self-intersection problem. Therefore our algorithm can be applied to non-simple curve reconstruction.
PPT Slide
Lager Image
The process of our point ordering algorithm: (a) point set (initial state), (b) each curve has two components (middle state), and (c) two curves (final state)
5. CONCLUSION
In this paper, we proposed an improved curve reconstruction algorithm by exploiting a new distance. We already introduced a natural distance in [3] which is based on a useful property of Brownian motion. The distance enables us to provide a totally order for the set of arbitrarily scattered points. However, the work of [3] missed the geometric meaning of the naturalness conditions (C-1) and (C-2). In this paper we proposed the polar-natural distance that is based on the polar coordinates. The totally ordered set generated by the polar-natural distance is more natural than that by the natural distance. By connecting these ordered points, we can obtain desired or meaningful curves. Also the polar-natural point ordering method can be used in the reconstruction of smooth curves, even though the data set contains noise points. The several experimental results show the superiority of our point ordering algorithm based on the polar-natural distance.
BIO
Hyoung-Seok Kim
He received the M.S. and Ph.D. degrees in department of Mathematics from KAIST (Korea Advanced Institute of Science and Technology) in 1992 and 1998, respectively. During 1998-1999, he worked at ETRI as a post-Doctorial researcher. He is a professor in dept. of Multimedia Engineering at Dong-Eui University from 1999. His interesting research fields are computer graphics, computer game engine, and applied mathematics.
Ho-Sook Kim
She received the M.S. and Ph.D. degrees in department of Computer Engineering from Ewha Womans University in 1999 and 2005, respectively. She was an associate professor in division of Advance Computer Information at Dong-Eui Institute of Technology from 2001 to 2009. She is a teacher in dept. of mathematics and computer science at Korea Science Academy of KAIST from 2010. Her interesting research fields are database, data mining, GIS, and mobile technology.
References
Hoppe H. , DeRose T. , Duchamp T. , McDonald J. , Stuetzle W. “Surface Reconstruction from unorganized points,“ Proc. SIGGRAPH’ 92 1992 71 - 78
Boissonnat J. D. , Geiger B. “Three cimentional reconstruction of complex shapes based on the Delaunay triangulation,“ Proc. of Biomedical Image Process, Biomed. Visualizaiton 1993 964 - 975
Kim Philsu , Kim Hyoung-Seok 2010 “Point ordering with the natural distance based on Brownian motion,” Mathematical problems in engineering article ID 450460 2010 17 -
Boissonnat D. , Cazals F. 2002 “Smooth surface reconstruction via natural neighbor interpolation of distance functions,” Comp. Geom. Theo. Appl. 22 185 - 203    DOI : 10.1016/S0925-7721(01)00048-7
Edelsbrunner H. , Kirkpatrick D. G. , Seidel R. 1983 “On the shape of a set of points in the plane,” IEEE Trans. Information Theory 551 - 559    DOI : 10.1109/TIT.1983.1056714
Attali D. “r-regular shape reconstruction from unorganized points,” Proc. of 13th Ann. Sympos. Comput. Geom. 1997 248 - 253
Amenta N. , Bern M. , Eppstein D. 1998 “The crust and the beta-skeleton: combinatorial curve reconstruction,” Graphical Models 60 125 - 135    DOI : 10.1006/gmip.1998.0465
Dey T. K. , Kumar T. K. “A simple provable algorithm for curve reconstruction,” Proc. 10th. ACM-SIAM Symp. Discr. Algorithms 1999 893 - 894
Fang L. , Gossard D. C. “Fitting 3D curves to unorganized data points using deformable curves,” Proc. of CG International'92 1992 535 - 543
Dedieu J. P. , Favardin C. H. 1994 “Algorithms for ordering unorganized points along parametrized curves,” Numerical Algorithms 6 160 - 200    DOI : 10.1007/BF02149768
Taubin G. , Ronfard R. 1996 “Implicit simplical models for adaptive curve reconstruction,” IEEE Trans. on Pattern Analysis and Machine Intelligence 18 321 - 325    DOI : 10.1109/34.485559
Nguyen Thanh An , Zeng Yong 2008 “VICUR: A human-vision-based algorithm for curve reconstruction,” Robotics and Computer Integrated manufacturing 24 824 - 834    DOI : 10.1016/j.rcim.2008.03.007