A TOPOLOGICAL CHARACTERIZATION OF THINNING

被引:59
作者
RONSE, C
机构
[1] Philips Research Lab, Brussels, Belg, Philips Research Lab, Brussels, Belg
关键词
COMPUTER PROGRAMMING - Algorithms;
D O I
10.1016/0304-3975(86)90164-7
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A large number of skeletonization algorithms for binary images use the method of thinning: successive layers of pixels are deleted from the figure until it becomes one pixel thick. In this paper we analyze the topological properties of the set D of pixels to be deleted from a figure F in order to get a skeleton. We characterize them by the concept of strong k-deletability (k equals 4 or 8). For individual pixels, strong k-deletability is equivalent to a more general property that we call k-deletability. We show that a strongly k-deletable subset D of a figure F can be deleted by a succession of deletions of individual pixels p//1,. . . ,p//t. This justifies our definition of strong deletability and shows that any topologically valid skeleton can be obtained by some thinning process.
引用
收藏
页码:31 / 41
页数:11
相关论文
共 13 条
[1]   THINNING ALGORITHMS - A CRITIQUE AND A NEW METHODOLOGY [J].
DAVIES, ER ;
PLUMMER, APN .
PATTERN RECOGNITION, 1981, 14 (1-6) :53-63
[2]  
Hilditch C.J., 1969, MACH INTELL, P403
[3]   AN ISOMORPHISM FOR DIGITAL IMAGES [J].
RONSE, C .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1985, 39 (02) :132-159
[4]  
RONSE C, 1981, R456 PHIL RES LAB RE
[5]  
RONSE C, 1981, R454 PHIL RES LAB RE
[6]  
RONSE C, 1983, R470 PHIL RES LAB RE
[7]   CHARACTERIZATION OF PARALLEL THINNING ALGORITHMS [J].
ROSENFELD, A .
INFORMATION AND CONTROL, 1975, 29 (03) :286-291
[8]   ADJACENCY IN DIGITAL PICTURES [J].
ROSENFELD, A .
INFORMATION AND CONTROL, 1974, 26 (01) :24-33
[9]   CONNECTIVITY IN DIGITAL PICTURES [J].
ROSENFELD, A .
JOURNAL OF THE ACM, 1970, 17 (01) :146-+
[10]  
Serra J., 1982, IMAGE ANAL MATH MORP, V1