Polygonal shape reconstruction in the plane

A. Gheibi; M. Davoodi; A. Javad; F. Panahi; M.M. Aghdam; M. Asgaripour; A. Mohades

Polygonal shape reconstruction in the plane

Access Full Text

Polygonal shape reconstruction in the plane

Author(s): A. Gheibi ; M. Davoodi ; A. Javad ; F. Panahi ; M.M. Aghdam ; M. Asgaripour ; A. Mohades
DOI: 10.1049/iet-cvi.2009.0079

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Computer Vision — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): A. Gheibi ¹ ; M. Davoodi ¹ ; A. Javad ¹ ; F. Panahi ¹ ; M.M. Aghdam ¹ ; M. Asgaripour ¹ ; A. Mohades ¹
- Affiliations: 1: Laboratory of Algorithms and Computational Geometry, Mathematics and Computer Science Department, Amirkabir University of Technology, Tehran, Iran
Source: Volume 5, Issue 2, March 2011, p. 97 – 106
DOI: 10.1049/iet-cvi.2009.0079 , Print ISSN 1751-9632, Online ISSN 1751-9640

Published

In this study a robust shape reconstruction algorithm is proposed which guarantees a simple polygon as output and works well on both types of input, dot patterns and boundary samples, in the plane. Guaranteed polygonal output makes it favourable for many applications because of its ease of manipulation and use. The proposed algorithm, called simple-shape, starts reconstruction from the convex hull and makes it concave step by step based on a new hybrid selection criterion which is built on human beings visual perception. Also at the end, a simple-shape algorithm is tested in several cases and the results are compared with the latest shape reconstruction algorithm in the literature.

References

1. 1)
  - R. Urquhart . Graph theoretical clustering based on limited neighborhood sets. Pattern Recognit. , 3 , 173 - 187
2. 2)
  - M.J. Fadili , M. Melkemi , A. ElMoataz . Non-convex onion peeling using a shape hull algorithm. Pattern Recognit. Lett. , 1577 - 1585
3. 3)
  - H. Edelsbruner , E.P. Mucke . Three-dimensional alpha shapes. ACM Trans. Graphics , 1 , 43 - 72
4. 4)
  - H. Edelsbrunner , D.G. Kirkpatrick , R. Seidel . On the shape of a set of points in the plane. IEEE Trans. Inf. Theory IT , 551 - 559
5. 5)
  - R.C. Veltkamp . The γ- neighborhood graph. Comput. Geom. Theory Appl. , 4 , 227 - 246
6. 6)
  - M. de Berg , M. van Kreveld , M. Overmars , O. Schwarzkopf . (1997) Computational geometry: algorithms and applications.
7. 7)
  - M. Duckham , L. Kulik , M. Worboys , A. Galton . Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognit. , 10 , 3224 - 3236
8. 8)
  - J. Edmonds . (1960) A combinatorial representation for polyhedral surfaces.
9. 9)
  - N. Amenta , M. Bern , D. Eppstein . The crust and the β-skeleton: combinatorial curve reconstruction. Graph. Models Image Process. , 2 , 125 - 135
10. 10)
  - N. Amenta , S. Choi , R. Kolluri . The power crust, unions of balls, and the medial axis transform. Int. J. Comput. Geom. Appl. Spec. Issue Surf. Reconstr. , 127 - 153
11. 11)
  - Chassery, J.M., Montanvert, A.: `Geometric representation of shapes and objects for visual perception', Geometric reasoning for perception and action, selected papers presented in a Workshop held at Grenoble, 16–17 September 1991, France, p. 163–182.
12. 12)
  - G. Garai , B.B. Chaudhuri . A split and merge procedure for polygonal border detection of dot pattern. Image Vis. Comput. , 75 - 82
13. 13)
  - H. Alani , C.B. Jones , D. Tudhope . Voronoi-based region approximation for geographical information retrieval with gazetteers. Int. J. Geogr. Inf. Sci. , 4 , 287 - 306
14. 14)
  - R.O. Duda , P.E. Hart . (1973) Pattern classification and scene analysis.
15. 15)
  - D.G. Kirkpatrick , J.D. Radke , G. Toussaint . (1998) A framework for computational morphology computational geometry.
16. 16)
  - J. O'Rourke . (1994) Computational geometry in C.
17. 17)
  - J. O'Rourke , H. Booth , R. Washington . Connect-the-dots: a new heuristic. Comput. Vis. Graph. Image Process. , 258 - 266
18. 18)
  - H. Ogawa . Labeled pattern matching by Delaunay triangulation and maximal cliques. Pattern Recognit. , 35 - 40
19. 19)
  - J.Q. Jaromczyk , G.T. Toussaint . Relative neighborhood graphs and their relatives. Proc. IEEE , 9 , 1502 - 1517
20. 20)
  - M. Melkemi , M. Djebali . Computing the shape of a planar points set. Pattern Recognit. , 1423 - 1436
21. 21)
  - O. Faugeras . (1999) Three-dimensional computer vision: a geometric viewpoint.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Polygonal shape reconstruction in the plane

Polygonal shape reconstruction in the plane

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content