Computing the Hausdorff distance between curved objets
Full text
Computing the Hausdor Distane Between Curved Ob jets 1 Helmut Alt Ludmila Sharf Institute for Computer Siene, Freie Universitat Berlin, Takustr.9, D-14195 Berlin Key words: shap e omparison, Hausdor distane, parametri urves 1. Intro dution Analysis and omparison of geometri shap es are of imp ortane in various appliation areas within omputer siene, suh as pattern reognition and omputer vision, but also in other disiplines on- erned with the form of ob jets suh as artography, moleular biology, mediine, or biometri signal pro essing. The general situation is that we are given two ob jets A , B mo delled as subsets of 2- or 3- dimensional spae and we want to know how muh they resemble eah other [1℄. For this purp ose we need a similarity measure dened on pairs of shapes indiating the degree of resemblane of these shapes. A frequently used similarity measure is the Hausdor distane, whih is dened for arbitrary non-empty ompat sets A and B . It assigns to eah p oint of one set the distane to its losest p oint in the other and takes the maximum of all these values. Formally, we dene the one-sided Hausdor distane from A to B as ~ Æ H ( A; B ) = max a 2 A min b 2 B d ( a; b ) ; (1) where d ( x; y ) denotes a distane measure b etween p oints x and y . Here we will assume the planar ase, i.e., that A; B R 2 and that d is the Eulidean distane. The (bidiretional) Hausdor distane b etween A and B is dened as Æ H ( A; B ) = max( ~ Æ H ( A; B ) ; ~ Æ H ( B ; A )) (2) We will only desribe the omputation of the one-sided Hausdor distane from A to B , the omputation of the bidiretional Hausdor distane is then straightforward. 1 This researh was supp orted by the Europ ean Union under ontrat No. IST-2000-26473, Pro jet ECG. The aim of this pap er is to nd an algorithm for general shap es whih are mo delled by two sets of n algebrai urves . When we speak ab out the Hausdor distane between these two sets we atually mean the Hausdor distane b etween the two sets of points lying on these urves. We will restrit to urves that are given by rational parameterizations , i.e., eah urve is represented by a parameterization : I ! R 2 ; ( t ) = ( x ( t ) ; y ( t )) (3) where I R is a losed interval and x ( t ) ; y ( t ) are rational funtions with no poles in I . Observe that this denition inludes some imp ortant families of free-form parametri urves, for example B-splines. For simpliity, we assume a ertain general p osition of the input urves. In partiular, we assume that any two urves interset in at most nitely many p oints. 2. Basi ases In this setion we will investigate how the direted Hausdor distane b etween two single objets (urves or p oints) an b e omputed. 2.1. Point-urve and urve-point The Hausdor distane from a p oint p = ( u; v ) to a urve ( t )=( x ( t ) ; y ( t )) ; t 2 I is min t 2 I d ( p; ( t )). The Hausdor distane from a urve ( t ) to a p oint p is the maximum Eulidean distane from any p oint on to p . In order to nd those parameters t where the minimum or maximum is attained, we onsider the 20th EWCG Seville, Spain (2004)
20th Europ ean Workshop on Computational Geometry zero es of the derivative of the squared distane d d t [ d 2 ( p; ( t ))℄, i.e., the equation 2 ( u x ( t )) x 0 ( t ) + 2 ( v y ( t )) y 0 ( t ) = 0 (4) This equation has onstantly many solutions if the degree of is b ounded. We all a p oint satisfying this equation a footpoint of p on . In addition to the p oints given by the solutions of equation 4 the minimum or maximum distane an be attained at the endp oints of (Fig. 1). p c(t) Q Fig. 1. Hausdor distane from a urve ( t ) to a p oint p is the distane from p to the farthest p oint on . 2.2. Curve-urve We redue the problem of determining the Hausdor distane from a urve a , a ( t ) = ( x a ( t ) ; y a ( t )), t 2 I a to a urve b , b ( s )=( x b ( s ) ; y b ( s )), s 2 I b to determining the distanes of onstantly many andidate p oints on a to the urve b . There are four dierent typ es of andidate p oints. Firstly, the Hausdor distane an be assumed at one of the endpoints of urve a ( type EA ). Seondly, it an happ en that the Hausdor distane is attained b etween an endpoint Q of b and a p oint on a . Therefore, we determine on a all fo otp oints of the endp oints of b by equation (4) ( type EB ). For the third typ e of andidate p oints we onsider the self-bisetor (or medial axis ) of a urve, whih is the set of all p oints whose minimal distane to the urve is attained at more than one p oint on the urve, f. Fig. 2. The Hausdor distane from a to b an b e attained at an intersetion p oint of a with the selfbisetor of b . We will only give a system of equations desribing suh a p oint here for the part of the self-bisetor where the two losest points are interior p oints of b , see Fig. 3. point−point bisector point−curve bisector curve−curve bisector Fig. 2. Self-bisetor of a parabola segment. a(t) Q b(s) R P Fig. 3. The Hausdor distane from the urve a ( t ) to the urve b ( s ) is assumed at the intersetion p oint Q of the urve a with the self-bisetor of the urve b . The p oint Q has two dierent internal foot-p oints P and R on b . Supp ose Q = a ( t ) and that P = b ( s ) and R = b ( r ) with r 6 = s are the p oints on b losest to Q . Then we obtain the following system of equations for t; s; and r : ( x a ( t ) x b ( s )) 2 + ( y a ( t ) y b ( s )) 2 ( x a ( t ) x b ( r )) 2 + ( y a ( t ) y b ( r )) 2 = 0 (5) ( x a ( t ) x b ( s )) x 0 b ( s ) + ( y a ( t ) y b ( s )) y 0 b ( s ) = 0 (6) ( x a ( t ) x b ( r )) x 0 b ( r )+( y a ( t ) y b ( r )) y 0 b ( r ) = 0 (7) In order to enfore the ondition r 6 = s we introdue a new variable u and add one more equation to the system: 1 u ( s r ) = 0 (8) We add all points determined by the nitely many solutions of this system to the andidate list ( type SB ). For the fourth typ e of possible andidate p oints we observe that the Hausdor distane an o ur b etween two interior p oints p 2 a and q 2 b with-
Marh 25-26, 2004 Seville (Spain) out one of them lying on the self-bisetor of the other urve, see Fig. 4. a(t) b(s) p q Fig. 4. Hausdor distane at interior points. Sine q is a fo otp oint on b for p oint p , the line segment pq must b e p erp endiular to the tangent line to urve b at p oint q . In addition it an b e shown that the tangent line to the urve a at p oint p must b e parallel to the tangent line to the urve b at p oint q and, thus, also p erp endiular to the line segment pq . The remaining andidate p oints ( type I ) for the Hausdor distane are, therefore, among the solutions of the following system: ( x a ( t ) x b ( s )) x 0 b ( s )+( y a ( t ) y b ( s )) y 0 b ( s ) = 0 (9) ( x a ( t ) x b ( s )) x 0 a ( t ) + ( y a ( t ) y b ( s )) y 0 a ( t ) = 0 (10) A detailed geometri proof for this fat is omitted due to spae limitations and an b e found in [7℄. 3. The general ase As was said b efore, the general problem we onsider is to nd the Hausdor distane b etween two p oint sets given by two sets A; B of rationally parameterized algebrai urves. In order to nd ~ Æ ( A; B ) we split the urves of A at their intersetion p oints with the Voronoi diagram of B . The resulting set A 0 of urves has the prop erty that eah urve lies in one Voronoi ell of B , so its distane to B is the distane to one urve and an b e determined using the tehniques of setion 2. Computing the omplete Voronoi diagram of algebrai urves is a very diÆult task in pratie and there are some op en questions about the bisetor of algebrai urves [3{5℄. In [5℄ an approximation algorithm for Voronoi diagrams of urves is given. Instead, we just ompute the intersetion p oints desrib ed. The splitting of eah urve a of A is done inrementally. Supp ose that we have list of intersetion p oints of the Voronoi diagram of a subset of B with a and we want to add a new urve b 2 B . We do this by sanning the urrent segments of a . Eah segment s b elongs to some urve 2 B whih has already b een pro essed. First we determine all intersetion p oints of the bisetor b etween b and with a and nd out whih ones lie inside s . s is split further with these p oints and some p ortions are labelled with b as nearest neighbor, others with . After this has b een done it might be ne- essary to merge neighb oring segments whih are b oth marked with b but are separated by a splitp oint from previous steps. Similar to the ase of self-bisetors, the interse- tion points of with the bisetor b etween b and an b e found as solutions of systems of equations. We only give this system here for the \interior" bisetor of two urves b and , not the ones for the bisetor between an endp oint of one urve and another urve or b etween two endpoints. These systems, however have to b e onsidered, as well. The system for the \interior" bisetor uses the prop erty that if a p oint a ( t ) lies on the bisetor b etween b and and the orresp onding fo otp oints are b ( s ) and ( r ) then the line segment a ( t ) b ( s ) is p erp endiular to the tangent vetor b 0 ( s ), and a ( t ) ( r ) is p erp endiular to 0 ( r ). d ( a ( t ) ; b ( s )) d ( a ( t ) ; ( r )) = 0 (11) h ( a ( t ) b ( s )) ; b 0 ( s ) i = 0 (12) h ( a ( t ) ( r )) ; 0 ( r ) i = 0 (13) The worst ase running time of our algorithm as stated is O ( nm 2 ) if A onsists of n and B of m urves, assuming that the degrees of the urves are b ounded. It an be easily improved to O ( nm log m ) by using a divide-and-onquer approah for the splitting of the urves of A . It should b e worthwhile to further improve the ombinatorial omplexity of the algorithm (see also [2℄), but our ma jor intent was to nd a simple algorithm that an be put into pratie with a reasonable amount of eort. 4. Implementation We implemented the algorithm desrib ed in C++ using the omputer algebra software library SYNAPS (SYmboli Numeri APpliationS), see [8,6℄, for solving the systems of p olynomial equations.
20th Europ ean Workshop on Computational Geometry For visualization purp oses a graphial user interfae was develop ed using the GTK library. It inludes visualization of the urves, the input and editing of the parameterization and the intervals if the parameter values, the omputation of the Hausdor distane and the graphial indiation of the andidate p oints onsidered for the omputation. Figure 5 shows the interfae with an example. Fig. 5. Result of a Hausdor distane omputation with two B-splines of degree 2. Both one-way distanes and all andidate p oints are shown. Referenes [1℄ Helmut Alt and Leonidas J. Guibas. Disrete geometri shap es: Mathing, interpolation, and approximation. In Handbook of omputational geometry . Elsiever Siene B.V., 1999. [2℄ Helmut Alt and Otfried Shwarzkopf. The Voronoi diagram of urved ob jets. In Pro. 11th ACM Comput. Geom. Symp. , pages 89{97, Vanouver, BC, 1995. [3℄ Gershon Elb er and Myung-So o Kim. Bisetor urves of planar rational urves. Computer-Aided Design , 30(14):1089{1096, 1998. [4℄ Rida T. Farouki and Ra jesh Ramamurthy. Degenerate p oint/urve and urve/urve bisetors arising in medial axis omputations for planar domains with urved b oundaries. Internat. J. Comput. Geom. Appl. , 8:599{ 617, 1998. [5℄ Rida T. Farouki and Ra jesh Ramamurthy. Voronoi diagram and medial axis algorithm for planar domains with urved b oundaries, I. Theoretial foundations. Journal of Computational and Applied Mathematis , 102(1):119{141, February 1999. [6℄ G. Dos Reis, B. Mourrain, R. Rouillier, and Ph. Trebuhet. An environment for symb oli and numeri omputation. In Pro. of the International Conferene on Mathematial Software , pages 239{249, 2003. [7℄ Ludmila Sharf. Computing the Hausdor distane b etween sets of urves. Master's thesis, Freie Universitat Berlin, Germany, 2003. [8℄ http://www-sop.inria.fr/galaad/logiiels/synaps/.