 Computer Science and Application 计算机科学与应用, 2013, 3, 407-410 http://dx.doi.org/10.12677/csa.2013.39070 Published Online December 2013 (http://www.hanspub.org/journal/csa.html) Computing the Hausdorff Distance between Two Algebraic Surfaces* Huahao Shou1, Yongming Huang1, Kaili Gu1, Yongwei Miao2, Liping Wang3 1College of Science, Zhejiang University of Technology, Hangzhou 2College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 3College of Business and Administration, Zhejiang University of Technology, Hangzhou Email: shh@zjut.edu.cn Received: Sep. 27th, 2013; revised: Oct. 29th, 2013; accepted: Nov. 10th, 2013 Copyright © 2013 Huahao Shou et al. This is an open access article distributed under the Creative Commons Attribution License, which permits un- restricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accordance of the Creative Commons Attribution License all Copyrights © 2013 are reserved for Hans and the owner of the intellectual property Huahao Shou et al. All Copyright © 2013 are guarded by law and by Hans as a guardian. Abstract: An algorithm for computing the approximate Hausdorff distance as well as its error value between two alge- braic surfaces is proposed based on dividing and conquering subdivision technique and interval arithmetic. Theoreti- cally, as long as the size of the voxels is small enough, the computed approximate Hausdorff distance can reach any precision, however, the CPU time used may be overwhelming. Keywords: Hausdorff Distance; Algebraic Surface; Interval Arithm etic; Subdivision Algorithm 两张代数曲面之间 Hausdorff 距离的计算* 寿华好 1，黄永明 1，顾凯丽 1，缪永伟 2，王丽萍 3 1浙江工业大学理学院，杭州 2浙江工业大学计算机科学与技术学院，杭州 3浙江工业大学经贸管理学院，杭州 Email: shh@zjut.edu.cn 收稿日期：2013 年9月27 日；修回日期：2013 年10 月29 日；录用日期：2013 年11 月10 日 摘 要：基于细分算法和区间算术，本文提出一种计算代数曲面间的 Hausdorff 距离的新算法。该算法在计算出 Hausdorff 距离近似值的同时能给出误差值。在理论上讲，只要设置的体素大小足够小 ，就可以使得计算出 的 Hausdorff 距离近似值与精确值之间的误差达到任意小。但具体计算的时候,如果精度要求较高则时间成本会变 得很高。 关键词：Hausdorff 距离；代数曲面；区间算术；细分算法 1. 引言 Hausdorff 距离是两组点集之间相似程度的一种 度量，它度量了两个点集间的最大不匹配程度。 Hausdorff 距离在计算机图形学、计算辅助几何设计、 计算机视觉、图像处理等领域有十分重要的应用[1]。 已有的有关 Hausdorff 距离的工作一般都是针对 点集(图像)、多边形网格、或者参数曲线曲面提出来 的。早期 Rucklidge[2]针对 2维图像提出了一种高效的 Hausdorff 距离计算方法，但该方法很难推广到 3维。 Atallah[3]针对非相交平面凸多边形提出了一种计算时 间为线性函数的 Hausdorff距离计算方法。Barton 等[4] *项目基金：国家自然科学基金(No. 61272309, 61070135)。 Open Access 407  两张代数曲面之间 Hausdorff 距离的计算 针对多边形网格提出了一种计算精确 Hausdorff 距离 的方法，但是速度很慢，达不到实时计算的目的。Tang 等[5]借助于 BVH 技术提出了一种多边形网格之间 Hausdorff 距离近似计算的方法，速度很快，可以达到 实时计算的要求。Kim 等[6]借助于双圆弧和深度缓存 技术提出了一种计算参数曲线之间 Hausdorff 距离的 方法。Bai 等[7]用折线逼近的办法提出了一种计算参数 曲线之间 Hausdorff 距离的方法。Chen 等[8]提出了一 种计算 B样条曲线之间Hausdorff 距离的方法。近期， Hanniel 等[9]使用 GPU加速技术提出了一种针对 NURBS 曲面的 Hausdorff距离计算方法。以上这些算 法都没有涉及到代数曲面之间的 Hausdorff 距离计算 问题。Jüttler[10]对隐式曲线之间或者参数曲线之间的 Hausdorff 距离的上界进行了理论上的估计，但是关于 隐式曲线之间 Hausdorff 距离没有给出具体的计算算 法。 近年来随着计算机计算能力的大幅提升，代数曲 线曲面在计算机图形学和几何造型中的运用越来越 多[11]，从而代数曲线曲面间的Hausdorff 距离的计算 也就显得十分重要。然而由于代数曲面的难操作性， 一般情况下很难进行参数化，所以到目前为止代数曲 面之间的 Hausdorff距离计算还没有任何算法问世。 本文在区间分析和细分算法的基础上针对代数曲面 之间的 Hausdorff 距离计算问题首次提出了一种计算 方法。该算法的基本思想是用修正仿射算术[12]先对代 数曲面进行离散化，然后通过计算离散化后的一个个 小立方体(体素)间的Hausdorff 距离来近似代替代数 曲面间的 Hausdorff距离，在求解过程中借助了八叉 树和区间算术进行加速。数值试验表明本文给出的算 法能有效且稳定地计算出两张代数曲面之间的 Hausdorff 距离的近似值，并且能在计算出近似值的同 时给出误差范围。但是当精度要求较高的时候，时间 开销会变得很大。 2. 算法 两张代数曲面和间的 Hausdorff 距离定义为 1 S2 S 1212 21 ,max,,, H SShSS hSS， 其中 2 1 12 ,maxmin qS pS hS Spq 从到的单向 Hausdorff 距离， 2 S1 Spq是某种距离 范式(通常取 Euclidean 距离)，取到 Hausdorff 距离的 点对称为 Hausdorff 点对。 假设 1,, 0fxyz ， 是给定的两张 空间代数曲面，其中 2,, 0fxyz ,, 1 f xyz 2 ， ,, f xyz是三元多 项式，所考虑的计算区域是 ,,, x xyyzz ，终 止条件给定为 。算法的第一个关键步骤是代数曲面 离散化，也就是利用八叉树和区间算术分别找出包含 这两条代数曲面的像素点的两个集合 1 11 ,,, n iiii ii i A aa bb cc 和 2 21 ,,, n jj jjjj j A ddeef f 。 具体过程是：先通过修正仿射算术计算 1,, 0fxyz 在计算区域 ,,, x xyyzz 上的取值范围 11 , f f ， 然后判断 11 , f f 是否包含 0，如果 11 , f f 不包含 0， 说明 ,,, x xyyzz 内不包含代数曲面 1,, 0fxyz ，则抛弃该区域，否则如果 11 , f f 包含 0，说明 ,,, x xyyzz 有可能包含代数曲面 1,, 0fxyz ，则将该空间区域在中点处一分为八， 通过八叉树算法的递归过程使得细分后的区域逐渐 减小，一直细分到区域的大小即区域的长、宽和高都 小于等于给定的终止条件 为止，如果还是排除不掉， 则将该区域存入 1 A ，同理可得 2 A 。这里特别值得一 提的是：如果不用八叉树数据结构，那么需要对每个 小长方体进行判断，比较费时间。而使用八叉树数据 结构，那么当11 , f f 不包含 0时，整个区域 x ,,,xyy zz 可以抛掉，不需要对这个区域内 的小的长方体作进一步的判断，而能不能把一个不包 含代数曲面的区域成功的抛掉又取决于所使用的区 间算术的精确度，这也是为什么我们选用相对精确的 修正仿射算术的原因。总之八叉树数据结构和相对比 较精确的区间算术可以起到计算加速的作用。 算法的第二个关键步骤就是通过计算两个小立 方体列表集合 1 A 和2 A 的距离来近似两张代数曲面间 的Hausdorff 距离。即将计算点与点之间的距离替换 为计算两个立方体之间的区间距离。即单向 Hausdorff 称为是从 到的单 向Hausdorff 距离， 1 S2 S 区间距离 22 11 121 2 ,maxmin RA RA A AR hR。其中 1 A 和2 A 1 2 21 ,maxm qS pS hS Sq inp 称为是 Open Access 408  两张代数曲面之间 Hausdorff 距离的计算 分别表示两张代数曲面离散化后的立方体列表， 和 分别表示 1 R 2 R1 A 和2 A 中的立方体，12 RR表示两个 立方体之间的区间距离。假设空间立方体区域 11111 11 ,,,Rxxyyzz 和 22222 2,,,Rxx yy zz 2 那么根据区间算术它们 之间的区间距离定义为 2 1211 2 2 12 22 112 21122 ,,, ,, ,, RRggxxxx yyyyzzzz 。 当给定某一立方体 ，i在1与 之间，因为 1i RA1 n2 A 中有 个立方体，那么遍历 2 n2 A 中所有 个立方体后 将得到 个区间距离记为 2 n 2 n, ij ij g g ， 。 2 1, 2,,jn 令 22 nn 11 ,min,min iiij ij jj ggg g 1 ，因为 A 中有 个立 1 n 方体，若遍历 1 A 中所有的立方体将得到 个 1 n, ii g g ， 再对这 个区间分别取左端点的最大值和右端点的 最大值即可得到单向Hausdorff 区间距离 1 n 12 , A Ah， 即 11 22 11 121 21 ,max minmax,max nn ii RA RAi x A ARRg hg ， 同理可求出 21 , A Ah。 若 12 , A Ah和 21 , A Ah二者没有交集，那么 1 , 2 A A 12 , H就取端点值较大的区间；若二者有交集，那 么 A AH就取 12 , A Ah和 21 , A Ah二者中左端点 的较大值以及 12 , A Ah和 21 , A Ah二者中右端点的 较大值所组成的区间。具体算法如下： 1) 输入两张代数曲面的多项式函数表达式 1,, f xyz ， 2,, f xyz，以及所要计算的区域范围 ,,, x xy yzz 和终止条件 。 2) 利用修正仿射算术计算 1,, f xyz在区域 ,,, x xyyzz 上的取值范围 11 , f f ，如果 11 , f f 不包含 0，则将该区域剔除，否则将该区域在 其中点处一分为八个小区域，对每个小区域重复步骤 (2)，一直细分到区域的大小为小于等于给定的终止条 件 为止，如果还是排除不掉，则将其存入 1 A ，最后 得 1 11 ,,, n iiii ii i A aa bb cc 。 3) 同理可得 2 21 ,,, n jj jjjj j A ddeef f 。 4) 计算两个立方体之间的区间距离这里有两种 方法可供选择，其中一种方法是直接采用区间运算 即： 22 12 2 ,,,,, ,, ijijiijji ijj iij j ggaaddbbee ccf f ， 1 1, 2,,in ，2 1, 2,,jn ；另一种方法是通过分别 计算出立方体间的八个顶点间的距离，在计算出的 64 个距离值中以其中的最小值作为区间距离 , ij ij g g 的 左端点，以其中的最大值作为区间距离 , ij ij g g 的右 端点。令 22 1 11 ,min,min,1,2, , nn i iijij jj g gggi n， 则 11 12 11 ,max ,max nn i ii i A Ag g h。同理可得 21 , A Ah。 5) 如果 12 , A Ah和 21 , A Ah不相交，取端点值 较大的作为 21 , A AH；如果二者有交集，那么 12 , A AH就取 1 ,2 A Ah和 2 , 1 A Ah二者中左端点的 较大值以及 12 , A Ah和 21 , A Ah二者中右端点的较 大值所组成的区间，算法结束。 由于区间运算的保守性，两张代数曲面之间的精 确Hausdorff 距离 12 , H AA 一定落在已经通过区间算 术和细分算法计算得到的 Hausdorff 区间距离 12 , A AH之中。所以我们可以取 12 , A AH的中点作 为 21 , H AA 的近似值，而且误差一定不会超过区间 12 , A AH长度的一半。也就是说我们在计算出 Hausdorff距离的近似值的同时给出了误差值，这是很 多其它有关 Hausdorff 距离计算的算法所不具备的优 点。此外，从理论上讲只要 足够地小，可以使得计 算出的 Hausdorff 距离的误差达到任意小， 但具体计 算的时候如果要求误差很小那么计算时间的开销会 变得非常大。 3. 实例 我们用 Mathematica 8.0编程实现上面的算法，并 Open Access 409  两张代数曲面之间 Hausdorff 距离的计算 Open Access 410 且在配置为 Intel Core Duo CPU E7500 @2 .93 GHz处 理器内存为 2 GB 的计算机里运行该程序进行了相应 的实例计算。 例：计算以下代数曲面在 2,2 2,2 2,2 区域范围内的 Hausdorff距离： 22 1 22 2 111 ,, , 449 111 ,, 16 4 9 2 2 f xyzxy z f xyzxyz 在计算过程中我们取 10.015625 64 ，计算的 结果得到 Hausdorff 区间距离为 17 103 22 , 0.7288689868,0.8970437559 48 ， 我们取该区间的中点值 0.81295637135 作为这两个代 数曲面间 Hausdorff距离的近似值，那么误差不超过 该区间长度的一半即0.08 408738455 。计算花费总 的 CPU 时间为789694 秒。如果需要进一步提高精度， 那么 应该取更小的数值，但计算时间会变得无法忍 受。如何对算法进行优化，或者利用计算机硬件设备 比如 GPU 等进行加速是我们下一步需要做的工作。 4. 结论 从以上算法描述和实例可以看出，本文提出的算 法可以有效地计算出两张代数曲面之间 Hausdorff 距 离的近似值，并且在计算出 Hausdorff 距离近似值的 同时给出了误差范围。本文的意义在于首次针对代数 曲面之间的 Hausdorff 距离给出了一种计算方法，由 于到目前为止还没有其它针对代数曲面之间的 Hausdorff距离的算法出现，我们无法进行比较研究。 本文算法的缺点是当精度要求较高的时候耗时过多， 这个问题有待将来通过算法优化或者利用 GPU 加速 进行改进。 参考文献 (References) [1] Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., et al. (2013) Efficient Haus- dorff distance computation for freeform geometric models in close proximity. Computer Aided Design, 45, 270-276. [2] Rucklidge, W. (1996) Efficient visual recognition using the Hausdorff distance. Lecture Notes in Computer Science, 1173, 1- 161. [3] Atallah, M. (1983) A linear time algorithm for the Hausdorff distance between convex polygons. Information Processing Let- ters, 17, 207-209. [4] Barton, M., Hanniel, I., Elber, G., et al. (2010) Precise Hausdorff distance computation between polygonal meshes. Computer Aided Geometric Design, 27, 580-591. [5] Tang, M., Lee, M. and Kim, Y.-J. (2009) Interactive Hausdorff distance computation for general polygonal models. ACM Tran- sactions on Graphics, 28, 1-9. [6] Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., et al. (2010) Precise Haus- dorff distance computation for planar freeform curves using biarcs and depth buffer. The Visual Compute r, 26, 1007-1016. [7] Bai, Y.-B., Yong, J.-H., Liu, C.-Y., et al. (2011) Polyline ap- proach for approximating the Hausdorff distance between two planar free-form curves. Computer A id ed Desi gn , 43, 687-698. [8] Chen, X.-D., Ma, W., Xu, G., et al. (2010) Computing the Haus- dorff distance between two B-spline curves. Computer Aided Design, 42, 1197-1206. [9] Hanniel, I., Krishnamurthy, A. and McMains, S. (2012) Com- puting the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU. Graphical Models, 74, 255-264. [10] Jüttler, B. (2000) Bounding the Hausdorff distance of implicitly defined and/or parametric curves. Mathematical Methods in CAGD, 1-10. [11] Li, Q.-D. and Tian, J. (2009) 2D piecewise algebraic splines for implicit modeling. ACM Transactions on Graphics, 28, 1-13. [12] Shou, H.-H., Lin, H.-W., Ralph, M., et al. (2003) Modified af- fine arithmetic is more accurate than centered interval arithmetic or affine arithmetic. Lecture Notes in Computer Science, 2768, 355-365. |