首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Two linear-time algorithms for computing the minimum length polygon of a digital contour
Authors:J-O Lachaud
Institution:
  • a LAMA, UMR CNRS 5127, Université de Savoie, F-73376 Le Bourget du Lac, France
  • b LIRMM, UMR CNRS 5506, Université Montpellier II, 161 rue Ada, F-34000 Montpellier, France
  • Abstract:The Minimum Length Polygon (MLP) is an interesting first order approximation of a digital contour. For instance, the convexity of the MLP is characteristic of the digital convexity of the shape, its perimeter is a good estimate of the perimeter of the digitized shape. We present here two novel equivalent definitions of MLP, one arithmetic, one combinatorial, and both definitions lead to two different linear time algorithms to compute them. This paper extends the work presented in Provençal and Lachaud (2009) 26], by detailing the algorithms and providing full proofs. It includes also a comparative experimental evaluation of both algorithms showing that the combinatorial algorithm is about 5 times faster than the other. We also checked the multigrid convergence of the length estimator based on the MLP.
    Keywords:Discrete geometry  Shape analysis  Minimum length polygon  Multigrid convergent length estimator  Combinatorics on words
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号