1 January 2007 Iterative generalization of morphological skeleton
Abstract
This paper addresses the representation of binary images using mathematical morphology, a nonlinear theory for image processing, based on set theory. The new image representation, called "five-step" skeleton representation, is an extension of the morphological binary skeleton. It consists of calculating the morphological digital binary skeleton using squares or crosses and then reiterating the above procedure for skeleton subsets using lines (horizontal, vertical, 45° and 135°). The theoretical background of the new morphological iterative image representation is presented. Applications and results are illustrated by computer simulations.

Introduction

Image representation is a key component in many tasks in computer vision and image processing. It consists generally of presenting an image in a form that differs from the original one, in which desired characteristics of the image are emphasized and can be easily accessed.1, 10

Mathematical morphology is part of set theory, and it has a strong geometric orientation. For binary images, mathematical morphology provides a well-founded theory for analysis and processing. Therefore, binary morphological representations can be developed and analyzed.11, 12, 13, 14, 15, 16 Mathematical morphology involves the study of the different ways in which a structuring element interacts with a given set, modifies its shape, and extracts the resultant set.2, 3, 4, 5, 6, 7, 8

The basic operations are erosion and dilation. Based on these operations, opening and closing operations are defined. The morphological operations have been successfully used in many applications including object recognition, image enhancement, texture analysis, and industrial inspection.2, 9, 17, 18, 19, 20

The new morphological binary image representation presented in this article is the “five-step” skeleton (denoted as 5SK), which is a natural extension of the morphological skeleton. It consists of first calculating the morphological digital binary skeleton using squares or crosses and then reiterating the above procedure for skeleton subsets using lines (horizontal, vertical, 45° and 135°) of growing length. In five steps, we have the skeleton of the skeleton subsets of the skeleton subsets, etc. using different structuring elements (squares or crosses—first step, and then horizontal lines— ${L}^{h}$ , vertical lines— ${L}^{v}$ , 45° lines— ${L}^{45}$ , and 135° lines— ${L}^{135}$ , for the next four steps). Its compression rate is very high, and the binary images can be perfectly reconstructed.

Original Morphological Digital Skeleton

As mention, dilation and erosion are the fundamental operators of mathematical morphology. The key process in the dilation and erosion operators is the local comparison of a shape, called the structuring element, with the object to be transformed. The structuring element is a predefined shape, used for morphological processing of the images. The most common shapes used as structuring elements (SE) are squares, crosses, horizontal lines, vertical lines, etc.1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The binary digital skeleton is one of the main operators in mathematical morphology, and it can be calculated entirely using the basic morphological operators.10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 It has been proved1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 that the skeleton subsets $S\left(X,nB\right)$ , of order $n$ , of a binary digital image $X$ in ${Z}^{2}$ can be calculated by means of binary morphological operations, in the following way:

1

$S\left(X,nB\right)=X\ominus nB-\left(X\ominus nB\right)\circ B,$
where $B$ is a structuring element, with $nB=\left(n-1\right)B\oplus B$ and $0B=\mathbf{0}$ .

From the collection of subsets $S\left(X,nB\right)$ and known order $n$ , the original digital binary image shape $X$ can be perfectly reconstructed by morphological formulas:

2

$X=\underset{n=0}{\overset{N}{\cup }}S\left(X,nB\right)\oplus nB,$
where $S\left(X,NB\right)\ne \varnothing$ and $S\left(X,nB\right)=\varnothing$ for $n⩾N+1$ .

Figure 1 shows a binary image and its morphological skeleton. The skeleton is obtained using a rhomb as the structuring element. The compression rate for this example is 27. This means that, for the skeleton, we need 27 times less information in order to reconstruct the original image. The reconstruction process needs additional information about the size of the structuring element for each point of the skeleton. By adding the information about the structuring element to the skeleton, the resulting image can be considered as a grayscale image (Fig. 2 ).

Fig. 1

The original image (a) and its skeleton (b).

Fig. 2

The skeleton completed with structuring element information.

The morphological skeleton is thin, composed of lines and/or points. The most difficult problem with the skeleton representation is that it contains many redundant points. These points are not needed for reconstruction but appear in the skeleton. Several methods were proposed for reducing the skeleton’s redundancy, and the use of these methods reduces the number of redundant points in various degrees.2, 6, 8, 9, 14, 17 The image representations obtained from these methods are called reduced skeletons. The computational complexity is very high, and the compression rate grows, although generally not significantly.

The “Five-Step” Skeleton

The method proposed in this paper is entirely based on the digital skeleton representation and represents an iterative generalization. The main idea is to compute the skeleton five times. The new morphological binary image representation presented in this article is the “five-step” skeleton (denoted as 5SK), which is a natural extension of the morphological skeleton. In the first step, the skeleton subsets of the binary image are computed. The structuring element used for this operation must be a square or an elementary cross. The skeleton has a large number of redundant points that reduce the compression rate.

We obtain $S\left(X,{n}_{B}B\right)$ , with ${n}_{B}=0,1,2,\dots ,{N}_{B}$ , $S\left(X,{N}_{B}B\right)\ne \varnothing$ , $S\left(X,\left({N}_{B}+1\right)B\right)=\varnothing$ , ${n}_{B}⩾{N}_{B}+1$ . We may then define ${X}_{B}^{{n}_{B}}=S\left(X,{n}_{B}B\right)$ , for ${n}_{B}=0,1,2,\dots ,{N}_{B}$ .

Because of these redundant points, the elements of the skeleton subsets are highly connected. These lines are divided into two categories:

• The first category contains horizontal lines, vertical lines, lines at 45°, and lines at 135°.

• The second category contains all the other lines. If we take a closer look at these lines, we notice that they are actually made of small horizontal and vertical lines as well as 45° and 135° lines (Fig. 3 ).

Fig. 3

Details of the second-category lines for skeleton subsets.

Since the skeleton is mainly composed of lines, the structuring elements used for the next four-step new skeleton computation will be a horizontal line, a vertical line, a 45° line, and a 135° line. For ${n}_{B}=0,1,2,\dots ,{N}_{B}$ , we apply the next four steps.

In the second step, for each skeleton subset obtained using squares or crosses, each horizontal line (a small one or a big one) will be replaced by a pixel. That pixel’s intensity will be the length of the line. We just have to apply the skeleton algorithm using the horizontal line as a structuring element.

For ${n}_{h}^{{n}_{B}}=0,1,2,\dots ,{N}_{h}^{{n}_{B}}$ , we obtain the skeleton subsets $P\left({n}_{h}^{{n}_{B}}{L}^{h}\right)=S\left({X}_{B}^{{n}_{B}},{n}_{h}^{{n}_{B}}{L}^{h}\right)$ , with $S\left({X}_{B}^{{n}_{B}},{N}_{h}^{{n}_{B}}{L}^{h}\right)\ne \varnothing$ and $S\left({X}_{B}^{{n}_{B}},\left({N}_{h}^{{n}_{B}}+1\right){L}^{h}\right)=\varnothing ,n⩾{N}_{h}^{{n}_{B}}+1$ , of the first-order skeleton subsets ${X}_{B}^{{n}_{B}}$ .

We may then define

3

${X}^{h}\left({n}_{B}\right)={X}_{B}^{{n}_{B}}-\underset{{n}_{B}=0}{\overset{{N}_{h}^{{n}_{B}}}{\cup }}P\left({n}_{h}^{{n}_{B}}{L}^{h}\right)\oplus {n}_{h}^{{n}_{B}}{L}^{h},$
where the − sign is the set difference. The binary image ${X}^{h}\left({n}_{B}\right)$ contains just vertical lines and 45° and 135° lines.

In the next step, the skeleton decomposition algorithm is applied for ${X}^{h}\left({n}_{B}\right)$ , using as structuring elements the vertical lines. We obtain skeleton subsets of ${X}^{h}\left({n}_{B}\right)$ defined by $P\left({n}_{v}^{{n}_{B}}{L}^{v}\right)=S\left({X}_{B}^{{n}_{B}},{n}_{v}^{{n}_{B}}{L}^{v}\right)$ for ${n}_{v}^{{n}_{B}}=0,1,2,\dots ,{N}_{v}^{{n}_{B}}$ .

As with Eq. 3, we may now define

4

${X}^{v}\left({n}_{B}\right)={X}_{B}^{{n}_{B}}-\underset{{n}_{B}=0}{\overset{{N}_{v}^{{n}_{B}}}{\cup }}P\left({n}_{v}^{{n}_{B}}{L}^{v}\right)\oplus {n}_{v}^{{n}_{B}}{L}^{v}.$
The binary image ${X}^{v}\left({n}_{B}\right)$ contains just 45° and 135° lines.

Finally, in the last two steps, we apply a similar algorithm, obtaining $P\left({n}_{45}^{{n}_{B}}{L}^{v}\right)$ and $P\left({n}_{135}^{{n}_{B}}{L}^{v}\right)$ . Many lines (horizontal, vertical, 45° and 135°) of different lengths are replaced by points.

Conclusions

Usually, the number of points in 5SK is much smaller than the number of points in the classical skeleton. For Fig. 1, using the five-step skeleton, the compression rate is 61. Finally, we have to attach the information about the structuring elements to the points of the 5SK. This information can be added in a similar way to the morphological skeleton method. The method could be applied for grayscale images. We just have to divide the grayscale images in binary images. The results are good, with perfect reconstructions.

The “five-step” skeleton is a new and improved method for removing the redundant points from the morphological skeleton of a binary image. Because of these properties, the five-step skeleton is recommended for image compression in areas where image quality is essential, including those where a degradation of the image due to the compression process is not accepted. The complexity of the method is not high because the standard skeleton algorithm is fast and could be applied to specialized processors.

references

1.  G. S. Baja and I. Nystrom, “2D grey-level skeleton computation: A discrete 3D approach,” Proc. 17th Intl. Conf. Patt. Recog. 2, 455–458 (2004). Google Scholar

2.  H. Wang, G. M. Schuster, A. K. Katsaggelos, and T. N. Pappas, “An optimal shape encoding scheme using skeleton decomposition,” IEEE Workshop Multimedia Signal Process., pp. 85–88 (2002). Google Scholar

3.  H. Wang, G. M. Schuster, A. K. Katsaggelos, and T. N. Pappas, “An efficient rate-distortion optimal shape coding approach utilizing a skeleton-based decomposition,” IEEE Trans. Image Process. 12(10), 1181–1193 (2003). Google Scholar

4.  M. Ito, “On the properties of morphological skeletons of discrete binary image using double structuring elements,” IEEE Southwest Symp. Image Analysis and Interpretation, pp. 26–30 (2006). Google Scholar

5.  J.-S. Park and I.-S. Oh, “Shape decomposition and skeleton extraction of character patterns,” Proc. 16th Intl. Conf. Patt. Recog. 3, 411–414 (2002). Google Scholar

6.  B. Kegl and A. Krzyzak, “Piecewise linear skeletonization using principal curves,” IEEE Trans. Pattern Anal. Mach. Intell.  10.1109/34.982884 24(1), 59–74 (2002). Google Scholar

7.  L.-C. Kuo and S.-J. Wang, “A flexible architecture for feature-based image editing,” Proc. IEEE Intl. Conf. Acoustics, Speech, Signal Process. 2, 1177–1180 (2005). Google Scholar

8.  K. Morooka, H. Takagi, and H. Nagahashi, “Active balloon model based on 3D skeleton extraction by competitive learning,” Proc. 4th Intl. Conf. 3-D Digital Imaging and Modeling, pp. 87–94 (2003). Google Scholar

9.  E. Namati and J. S. J. Li., “A novel shape descriptor based on empty morphological skeleton subsets,” Proc. 2004 Intl. Symp. Intelligent Multimedia, Video, and Speech Process., pp. 446–449 (2004). Google Scholar

10.  P.-C. Liu, F.-C. Wu, W.-C. Ma, R.-H. Liang, and M. Ouhyoung, “Automatic animation skeleton using repulsive force field,” Proc. 11th Pacific Conf. Computer Graphics Appl., pp. 409–413 (2003). Google Scholar

11.  J. Sadri, C. Y. Suen, and T. D. Bui, “Automatic segmentation of unconstrained handwritten numeral strings,” Ninth Intl. Workshop Frontiers in Handwriting Recog., pp. 317–322 (2004). Google Scholar

12.  S. W. Loke, “Towards data-parallel skeletons for grid computing: An itinerant mobile agent approach,” Cluster Computing and the Grid, Proc. 3rd IEEE/ACM Intern. Symp., pp. 651–652 (2003). Google Scholar

13.  R. Strand, “Surface skeletons in grids with non-cubic voxels,” Proc. 17th Intl. Conf. on Pattern Recog. 1, 548–551 (2004). Google Scholar

14.  A. Torsello and E. R. Hancock, “Correcting curvature-density effects in the Hamilton-Jacobi skeleton,” IEEE Trans. Image Process. 15(4), 877–891 (2006). Google Scholar

15.  D. N. Vizireanu, S. Halunga, and O. Fratu, “A grayscale image interpolation method using new morphological skeleton,” Telecomm. Modern Satellite, Cable and Broadcasting Service, Proc. 6th Intl. Conf. 2, 519–521 (2003). Google Scholar

16.  W.-P. Choi, K.-M. Lam, and W.-C. Siu, “An efficient algorithm for the extraction of a Euclidean skeleton,” Proc. IEEE Intl. Conf. Acoustics, Speech, and Signal Process. 4, IV3241–IV3241 (2002). Google Scholar

17.  W.-C. Ma, F.-C. Wu, and M. Ouhyoung, “Skeleton extraction of 3D objects with radial basis functions,” Int. J. Shape Model., 207–215 (2003). Google Scholar

18.  J. Xu, “A generalized discrete morphological skeleton transform with multiple structuring elements for the extraction of structural shape components,” IEEE Trans. Image Process. 12(12), 1677–1686 (2003). Google Scholar

19.  J. Xu, “A generalized morphological skeleton transform and extraction of structural shape components,” Proc. Intl. Conf. Image Process. 1, 325–328 (2003). Google Scholar

20.  J. Xu, “Efficient morphological shape representation with overlapping disk components,” IEEE Trans. Image Process.  10.1109/83.941858 10(9), 1346–1356 (2001). Google Scholar

© (2007) Society of Photo-Optical Instrumentation Engineers (SPIE)
Mihnea R. Udrea, Mihnea R. Udrea, Nicolae Dragos Vizireanu, Nicolae Dragos Vizireanu, } "Iterative generalization of morphological skeleton," Journal of Electronic Imaging 16(1), 010501 (1 January 2007). https://doi.org/10.1117/1.2713739 . Submission:
JOURNAL ARTICLE
3 PAGES

SHARE
KEYWORDS