© The Institution of Engineering and Technology
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)
-
R. Urquhart
.
Graph theoretical clustering based on limited neighborhood sets.
Pattern Recognit.
,
3 ,
173 -
187
-
2)
-
M.J. Fadili ,
M. Melkemi ,
A. ElMoataz
.
Non-convex onion peeling using a shape hull algorithm.
Pattern Recognit. Lett.
,
1577 -
1585
-
3)
-
H. Edelsbruner ,
E.P. Mucke
.
Three-dimensional alpha shapes.
ACM Trans. Graphics
,
1 ,
43 -
72
-
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)
-
R.C. Veltkamp
.
The γ- neighborhood graph.
Comput. Geom. Theory Appl.
,
4 ,
227 -
246
-
6)
-
M. de Berg ,
M. van Kreveld ,
M. Overmars ,
O. Schwarzkopf
.
(1997)
Computational geometry: algorithms and applications.
-
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)
-
J. Edmonds
.
(1960)
A combinatorial representation for polyhedral surfaces.
-
9)
-
N. Amenta ,
M. Bern ,
D. Eppstein
.
The crust and the β-skeleton: combinatorial curve reconstruction.
Graph. Models Image Process.
,
2 ,
125 -
135
-
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)
-
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)
-
G. Garai ,
B.B. Chaudhuri
.
A split and merge procedure for polygonal border detection of dot pattern.
Image Vis. Comput.
,
75 -
82
-
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)
-
R.O. Duda ,
P.E. Hart
.
(1973)
Pattern classification and scene analysis.
-
15)
-
D.G. Kirkpatrick ,
J.D. Radke ,
G. Toussaint
.
(1998)
A framework for computational morphology computational geometry.
-
16)
-
J. O'Rourke
.
(1994)
Computational geometry in C.
-
17)
-
J. O'Rourke ,
H. Booth ,
R. Washington
.
Connect-the-dots: a new heuristic.
Comput. Vis. Graph. Image Process.
,
258 -
266
-
18)
-
H. Ogawa
.
Labeled pattern matching by Delaunay triangulation and maximal cliques.
Pattern Recognit.
,
35 -
40
-
19)
-
J.Q. Jaromczyk ,
G.T. Toussaint
.
Relative neighborhood graphs and their relatives.
Proc. IEEE
,
9 ,
1502 -
1517
-
20)
-
M. Melkemi ,
M. Djebali
.
Computing the shape of a planar points set.
Pattern Recognit.
,
1423 -
1436
-
21)
-
O. Faugeras
.
(1999)
Three-dimensional computer vision: a geometric viewpoint.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cvi.2009.0079
Related content
content/journals/10.1049/iet-cvi.2009.0079
pub_keyword,iet_inspecKeyword,pub_concept
6
6