A comparison between two fully parallel thinning algorithms designed for images sampled on the square and hexagonal grids is reported. Using techniques from mathematical morphology, a hexagonal algorithm has been designed to closely match the operation of a well known square grid algorithm. Proofs of the connectivity and single pixel limb width of the resulting converged hexagonal skeleton have been presented. Implementations of both algorithms were found to produce accurate skeletons, but the hexagonal could be implemented with only 50% of the logical operations required by the square.
References
-
-
1)
-
R.C. STAUNTON
.
Hexagonal sampling in image processing.
Adv. Imag. Electron Phys.
,
231 -
307
-
2)
-
L. LAM ,
S.W. LEE ,
C.Y. SUEN
.
Thinning methodologies, a comprehensive survey.
IEEE Trans. Pattern Anal. Mach. Intelli.
,
9 ,
869 -
885
-
3)
-
S.S.O CHOY ,
C.S.T CHOY ,
WC SIU
.
New single-pass algorithm for parallel thinning.
Computer Vis. Image Underst.
,
1 ,
69 -
77
-
4)
-
Y.S. CHEN
.
Hidden deletable pixel detection using vector analysis in parallel thinning to obtain bias-reduced skeletons.
Comput. Vis. Image Underst.
,
3 ,
294 -
311
-
5)
-
C. RONSE
.
Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images.
Discrete Appl. Math.
,
67 -
79
-
6)
-
JANG, B.K.: `Shape analysis using mathematical morphology', 1990, PhD Dissertation., Univ. Wisconsin Madison, Dept. Elect. Comput. Eng..
-
7)
-
R.C. STAUNTON
.
An analysis of hexagonal thinning algorithms and skeletal shape representation.
Pattern Recognit.
,
7 ,
1131 -
1146
-
8)
-
N. BOURBAKIS ,
N. STEFFENSEN ,
B. SAHA
.
Design of an array processor for parallel skeletonization of images.
IEEE Trans. Circuits. Syst. II, Analog Digit Signal Process.
,
4 ,
284 -
298
-
9)
-
E.S. DEUTSCH
.
Thinning algorithms on rectangular hexagonal and triangular arrays.
Commun. ACM
,
9 ,
827 -
837
-
10)
-
C. RONSE
.
A topological characterization of thinning.
Theor. Comput. Sci.
,
31 -
41
-
11)
-
B.K. JANG ,
R.T. CHIN
.
One pass parallel thinning analysis, properties and quantitative evaluation.
IEEE Trans. Pattern Anal. Mach. Intell.
,
11 ,
1129 -
1140
-
12)
-
A. PETROSIN ,
G. SALVI
.
A two-subcycle thinning algorithm and its parallel implementation on SIMD machines.
IEEE Trans. Image Process.
,
2 ,
277 -
283
-
13)
-
F.Y. SHIH ,
W.T. WONG
.
Fully parallel thinning with tolerance to boundary noise.
Pattern Recognit.
,
12 ,
1677 -
1695
-
14)
-
S. YOKOI ,
J. TORIWAKI ,
T. FUKUMURA
.
An analysis of topological properties of digitized binary pictures using local features.
Comput. Graph. Image Process.
,
63 -
7
-
15)
-
R.W. SMITH
.
Computer processing of line images: a survey.
Pattern Recognit.
,
1 ,
7 -
15
-
16)
-
A. Rosenfeld ,
A.C. Kak
.
(1982)
Digital picture processing.
-
17)
-
J. Serra
.
(1992)
Image analysis and mathematical morphology.
-
18)
-
S. YOKOI ,
J. TORIWAKI ,
T. FUKUMURA
.
Topological properties in digitized binary pictures.
Syst. - Comput. - Controls
,
6 ,
32 -
39
-
19)
-
B.K. JANG ,
R.T CHIN
.
Analysis of thinning algorithms using mathematical morphology.
IEEE Trans. Pattern Anal. and Mach. Intell.
,
6 ,
541 -
551
-
20)
-
V. RANWEZ ,
P. SOILLE ,
G. BERTRAND ,
M. EOUPRIE ,
L. PERROTON
.
Order independent homotopic thinning, Discrete geometry for computer imagery', .
-
21)
-
A. ROSENFELD
.
A characterization of parallel thinning algorithms.
Inf. Control
,
286 -
291
-
22)
-
J.P. MYLOPOULOS ,
T. PAVLIDIS
.
On the topological properties of quantised spaces.
J. Assoc. Comput. Mach.
,
2 ,
239 -
246
-
23)
-
F. MEYER ,
J. SERRA
.
(1988)
Skeletons in digital spaces, Image analysis and mathematical morphology, Vol 2: Theoretical Advances.
-
24)
-
Z. KALMAR ,
Z. MARCZELL ,
C. SZEPESVARI ,
A. LORINCZ
.
Parallel and robust skeletonization built on self-organizing elements.
Neural Netw.
,
1 ,
163 -
173
-
25)
-
R.M. Mersereau
.
The processing of hexagonally sampled two dimensional signals.
Proc. IEEE
,
6 ,
930 -
949
-
26)
-
J. SERRA ,
B. LAY
.
Square to hexagonal lattice conversion.
Signal Process.
,
1 -
13
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-vis_20010076
Related content
content/journals/10.1049/ip-vis_20010076
pub_keyword,iet_inspecKeyword,pub_concept
6
6