본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

평면곡선에 대한 Hausdorff 거리 계산의 가속화 기법에 대한 연구
Efficient Hausdorff Distance Computation for Planar Curves

김용준    (서울대학교 전기컴퓨터공학부   ); 오영택    (서울대학교 전기컴퓨터공학부   ); 김명수    (서울대학교 컴퓨터공학부  );
  • 초록

    We present an efficient algorithm for computing the Hausdorff distance between two planar curves. The algorithm is based on an efficient trimming technique that eliminates the curve domains that make no contribution to the final Hausdorff distance. The input curves are first approximated with biarcs within a given error bound in a pre-processing step. Using the biarc approximation, the distance map of an input curve is then approximated and stored into the graphics hardware depth-buffer by rendering the distance maps (represented as circular cones) of the biarcs. We repeat the same procedure for the other input curve. By sampling points on each input curve and reading the distance from the other curve (stored in the hardware depth-buffer), we can easily estimate a lower bound of the Hausdorff distance. Based on the lower bound, the algorithm eliminates redundant curve segments where the exact Hausdorff distance can never be obtained. Finally, we employ a multivariate equation solver to compute the Hausdorff distance efficiently using the remaining curve segments only.


  • 주제어

    Hausdorff distance .   biarc approximation .   distance map .   depth buffer .   trimming .   solution of multivariate equation.  

  • 참고문헌 (21)

    1. Elber, G. and Kim, M. S., "Geometric Constraint Solver using Multivariate Rational Spline Functions", Proc of the Sixth ACM Symposium on Solid Modeling and Applications, pp. 1-10, 2001. 
    2. Lennerz, C. and Schomer, E., "Efficient Distance Computation for Quadric Curves and Surfaces", Proc. of Geometric Modeling and Processing, pp. 60-69, 2002. 
    3. Sohn, K. A., Juttler, B., Kim, M. S. and Wang, W., "Computing Distances between Surfaces using Line Geometry", Pacific Conference on Computer Graphics and Applications, pp. 236-245, 2002. 
    4. Kim, K. J., "Minimum Distance between a Canal Surface and a Simple Surface", Computer-Aided DeSign, Vol. 35, No. 10, pp. 871-879, 2003. 
    5. Chen, X. D., Yong, J. H., Zheng, G. Q., Paul, J. C. and Sun, J. G., "Computing Minimum Distance between Two Implicit Algebraic Surfaces", Computer- Aided Design, Vol. 38, No. 10, pp. 1053-1061, 2006. 
    6. Chen, X. D., Chen, L., Wang, Y., Xu, G. and Yong, J. H., "Computing the Minimum Distance between Bezier Curves", Journal of Computational and Applied Mathematics, Vol. 230, No.1, pp. 294-310, 2009. 
    7. Rabl, M. and Juttler, B., "Fast Distance Computation Using Quadratically Supported Surfaces", Proc of Computational Kinematics (CK 2009)", pp. 141-148, 2009. 
    8. Juttler, B., "Bounding the Hausdorff Distance of Implicitly Defined and/or Parametric Curves", Mathematical Methods in CAGD: Oslo 2000, pp. 223- 232, 2001. 
    9. Cignoni, P., Rocchini, C. and Scopigno, "Metro: Measuring Error on Simplified Surfaces", Computer Graphics Forum, Vol. 17, No.2, pp. 167-174,1998. 
    10. Aspert, N., Santana, D. and Ebranhimi, T., "MESH: Measuring Errors between Surfaces using the Hausdorff Distance", Proc. of the IEEE International Conference on Multimedia and Expo 2002 (ICME), Vol. 1, pp. 705-708. 
    11. Alt, H. and Scharf, L., "Computing the Hausdorff Diatance between Sets of Curves", Proc. of the 20th European Workshop on Computational Geometry, pp. 233-236, 2004. 
    12. Alt, H. and Scharf, L., "Computing the Hausdorff Distance between Curved Objects", International Journal of Computational Geometry and Applications, Vol. 18, No.5, pp. 307-320, 2008. 
    13. Tang, M., Lee, M. and Kim, Y. J., "Interactive Hausdorff Distnace Computation for General Polygonal Models", Proc. of SIGGRAPH 09, Computer graphics Annual Conference Series, Article No. 74,2009. 
    14. Elber, G. and Grandine, T., "Hausdorff and Minimal Distances between Parametric Freeforms in $R^2$ and $R^3$", Lecture Notes in Computer Science: Advaces in Geometric Modeling. and Processing, Proc. of 5th Int. Conf. GMP 2008, Vol. 4975, pp. 191-204,2008. 
    15. Aichholzer, O., Aigner, W., Aurenhammer, F., Hackl, T., Obemeder, M. and luttler, B., "Medial Axis. Computation for Planar Free-Form Shapes", Computer- Aided Design, Vol. 41, No.5, pp. 339-349, 2009. 
    16. Hoff, K., Culver, T., Keyser, J., Lin, M. and.: Manocha, D., "Fast Computation of Generalized Voronoi Diagrams Using Graphic Hardware", Proc. of SIGGRAPH 99, Computer Graphics Annual Conference Series, pp. 277-286, 1999. 
    17. Sir, Z., Feichtinger, R. and luttler, B., "Approximating Curves and Their Offsets Using Biarcs and Pythagorean Hodograph Quintics", Computer-Aided Design, Vol. 38, No.6, pp. 608-618, 2006. 
    18. Nutbourne, A. and Martin,R., "Differential Geometry Applied to Curve and Surface Design", Vol. 1, Chichester, UK, Ellis Horwood, 1988. 
    19. Parkinson, D. and Moreton, D., "Optimal Biarccurve Fitting", Computer-Aided Design, Vol. 23, No. 6, pp. 411-419, 1991. 
    20. Rossignac, J. and Requicha, A, "Piecewise Circular Curves for Geometric Modeling", IBM Journal of Research and Development, Vol. 31, No.3, pp. 296- 313, 1987. 
    21. IRlT 9.5 User's Manual, Technion. http:// www.cs.technion.ac.il/-irit. 

 저자의 다른 논문

  • 김용준 (1)

    1. 2009 "k-DOP을 이용하여 2차원 볼록 다각형간의 Hausdorff 거리를 계산하는 효율적인 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 36 (2): 111~123    
  • 김명수 (11)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기