JEI Letters

Iterative generalization of morphological skeleton

[+] Author Affiliations
Radu Mihnea Udrea, Nicolae Vizireanu

Politechnica University Bucharest, Faculty of Electronics, Telecommunications and Informations Technology, Bucharest, Romania

J. Electron. Imaging. 16(1), 010501 (March 12, 2007). doi:10.1117/1.2713739
History: Received November 09, 2006; Accepted December 18, 2006; Published March 12, 2007
Text Size: A A A

Open Access Open Access

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.

Figures in this Article

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.1116 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.28

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,1720

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—Lh, vertical lines—Lv, 45° lines—L45, and 135° lines—L135, for the next four steps). Its compression rate is very high, and the binary images can be perfectly reconstructed.

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.110

The binary digital skeleton is one of the main operators in mathematical morphology, and it can be calculated entirely using the basic morphological operators.1020 It has been proved120 that the skeleton subsets S(X,nB), of order n, of a binary digital image X in Z2 can be calculated by means of binary morphological operations, in the following way:Display Formula

1S(X,nB)=XnB(XnB)B,
where B is a structuring element, with nB=(n1)BB and 0B=0.

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

2X=n=0NS(X,nB)nB,
where S(X,NB) and S(X,nB)= for nN+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).

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,89,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 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(X,nBB), with nB=0,1,2,,NB, S(X,NBB), S(X,(NB+1)B)=, nBNB+1. We may then define XBnB=S(X,nBB), for nB=0,1,2,,NB.

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).

  • 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).

Graphic Jump LocationF1 :

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

Graphic Jump LocationF2 :

The skeleton completed with structuring element information.

Graphic Jump LocationF3 :

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 nB=0,1,2,,NB, 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 nhnB=0,1,2,,NhnB, we obtain the skeleton subsets P(nhnBLh)=S(XBnB,nhnBLh), with S(XBnB,NhnBLh) and S(XBnB,(NhnB+1)Lh)=,nNhnB+1, of the first-order skeleton subsets XBnB.

We may then defineDisplay Formula

3Xh(nB)=XBnBnB=0NhnBP(nhnBLh)nhnBLh,
where the − sign is the set difference. The binary image Xh(nB) contains just vertical lines and 45° and 135° lines.

In the next step, the skeleton decomposition algorithm is applied for Xh(nB), using as structuring elements the vertical lines. We obtain skeleton subsets of Xh(nB) defined by P(nvnBLv)=S(XBnB,nvnBLv) for nvnB=0,1,2,,NvnB.

As with Eq. 3, we may now defineDisplay Formula

4Xv(nB)=XBnBnB=0NvnBP(nvnBLv)nvnBLv.
The binary image Xv(nB) contains just 45° and 135° lines.

Finally, in the last two steps, we apply a similar algorithm, obtaining P(n45nBLv) and P(n135nBLv). Many lines (horizontal, vertical, 45° and 135°) of different lengths are replaced by points.

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.

Baja  G. S., and Nystrom  I., “ 2D grey-level skeleton computation: A discrete 3D approach. ,”  Proc. 17th Intl. Conf. Patt. Recog.. 2, , 455–458  ((2004)).
Wang  H., , Schuster  G. M., , Katsaggelos  A. K., , and Pappas  T. N., “ An optimal shape encoding scheme using skeleton decomposition. ,”  IEEE Workshop Multimedia Signal Process.. , pp. 85–88  ((2002)).
Wang  H., , Schuster  G. M., , Katsaggelos  A. K., , and Pappas  T. N., “ An efficient rate-distortion optimal shape coding approach utilizing a skeleton-based decomposition. ,” IEEE Trans. Image Process..  1057-7149 12, (10 ), 1181–1193  ((2003)).
Ito  M., “ 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)).
Park  J.-S., and Oh  I.-S., “ Shape decomposition and skeleton extraction of character patterns. ,”  Proc. 16th Intl. Conf. Patt. Recog.. 3, , 411–414  ((2002)).
Kegl  B., and Krzyzak  A., “ Piecewise linear skeletonization using principal curves. ,” IEEE Trans. Pattern Anal. Mach. Intell..  0162-8828 24, (1 ), 59–74  ((2002)).
Kuo  L.-C., and Wang  S.-J., “ A flexible architecture for feature-based image editing. ,”  Proc. IEEE Intl. Conf. Acoustics, Speech, Signal Process.. 2, , 1177–1180  ((2005)).
Morooka  K., , Takagi  H., , and Nagahashi  H., “ 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)).
Namati  E., and Li.  J. S. J., “ A novel shape descriptor based on empty morphological skeleton subsets. ,”  Proc. 2004 Intl. Symp. Intelligent Multimedia, Video, and Speech Process.. , pp. 446–449  ((2004)).
Liu  P.-C., , Wu  F.-C., , Ma  W.-C., , Liang  R.-H., , and Ouhyoung  M., “ Automatic animation skeleton using repulsive force field. ,”  Proc. 11th Pacific Conf. Computer Graphics Appl.. , pp. 409–413  ((2003)).
Sadri  J., , Suen  C. Y., , and Bui  T. D., “ Automatic segmentation of unconstrained handwritten numeral strings. ,”  Ninth Intl. Workshop Frontiers in Handwriting Recog.. , pp. 317–322  ((2004)).
Loke  S. W., “ 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)).
Strand  R., “ Surface skeletons in grids with non-cubic voxels. ,”  Proc. 17th Intl. Conf. on Pattern Recog.. 1, , 548–551  ((2004)).
Torsello  A., and Hancock  E. R., “ Correcting curvature-density effects in the Hamilton-Jacobi skeleton. ,” IEEE Trans. Image Process..  1057-7149 15, (4 ), 877–891  ((2006)).
Vizireanu  D. N., , Halunga  S., , and Fratu  O., “ A grayscale image interpolation method using new morphological skeleton. ,”  Telecomm. Modern Satellite, Cable and Broadcasting Service, Proc. 6th Intl. Conf.. 2, , 519–521  ((2003)).
Choi  W.-P., , Lam  K.-M., , and Siu  W.-C., “ An efficient algorithm for the extraction of a Euclidean skeleton. ,”  Proc. IEEE Intl. Conf. Acoustics, Speech, and Signal Process.. 4, , IV3241–IV3244  ((2002)).
Ma  W.-C., , Wu  F.-C., , and Ouhyoung  M., “ Skeleton extraction of 3D objects with radial basis functions. ,” Int. J. Shape Model..  0218-6543 , 207–215  ((2003)).
Xu  J., “ A generalized discrete morphological skeleton transform with multiple structuring elements for the extraction of structural shape components. ,” IEEE Trans. Image Process..  1057-7149 12, (12 ), 1677–1686  ((2003)).
Xu  J., “ A generalized morphological skeleton transform and extraction of structural shape components. ,”  Proc. Intl. Conf. Image Process.. 1, , 325–328  ((2003)).
Xu  J., “ Efficient morphological shape representation with overlapping disk components. ,” IEEE Trans. Image Process..  1057-7149 10, (9 ), 1346–1356  ((2001)).
© 2007 SPIE and IS&T

Citation

Radu Mihnea Udrea and Nicolae Vizireanu
"Iterative generalization of morphological skeleton", J. Electron. Imaging. 16(1), 010501 (March 12, 2007). ; http://dx.doi.org/10.1117/1.2713739


Figures

Graphic Jump LocationF1 :

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

Graphic Jump LocationF3 :

Details of the second-category lines for skeleton subsets.

Graphic Jump LocationF2 :

The skeleton completed with structuring element information.

Tables

References

Baja  G. S., and Nystrom  I., “ 2D grey-level skeleton computation: A discrete 3D approach. ,”  Proc. 17th Intl. Conf. Patt. Recog.. 2, , 455–458  ((2004)).
Wang  H., , Schuster  G. M., , Katsaggelos  A. K., , and Pappas  T. N., “ An optimal shape encoding scheme using skeleton decomposition. ,”  IEEE Workshop Multimedia Signal Process.. , pp. 85–88  ((2002)).
Wang  H., , Schuster  G. M., , Katsaggelos  A. K., , and Pappas  T. N., “ An efficient rate-distortion optimal shape coding approach utilizing a skeleton-based decomposition. ,” IEEE Trans. Image Process..  1057-7149 12, (10 ), 1181–1193  ((2003)).
Ito  M., “ 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)).
Park  J.-S., and Oh  I.-S., “ Shape decomposition and skeleton extraction of character patterns. ,”  Proc. 16th Intl. Conf. Patt. Recog.. 3, , 411–414  ((2002)).
Kegl  B., and Krzyzak  A., “ Piecewise linear skeletonization using principal curves. ,” IEEE Trans. Pattern Anal. Mach. Intell..  0162-8828 24, (1 ), 59–74  ((2002)).
Kuo  L.-C., and Wang  S.-J., “ A flexible architecture for feature-based image editing. ,”  Proc. IEEE Intl. Conf. Acoustics, Speech, Signal Process.. 2, , 1177–1180  ((2005)).
Morooka  K., , Takagi  H., , and Nagahashi  H., “ 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)).
Namati  E., and Li.  J. S. J., “ A novel shape descriptor based on empty morphological skeleton subsets. ,”  Proc. 2004 Intl. Symp. Intelligent Multimedia, Video, and Speech Process.. , pp. 446–449  ((2004)).
Liu  P.-C., , Wu  F.-C., , Ma  W.-C., , Liang  R.-H., , and Ouhyoung  M., “ Automatic animation skeleton using repulsive force field. ,”  Proc. 11th Pacific Conf. Computer Graphics Appl.. , pp. 409–413  ((2003)).
Sadri  J., , Suen  C. Y., , and Bui  T. D., “ Automatic segmentation of unconstrained handwritten numeral strings. ,”  Ninth Intl. Workshop Frontiers in Handwriting Recog.. , pp. 317–322  ((2004)).
Loke  S. W., “ 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)).
Strand  R., “ Surface skeletons in grids with non-cubic voxels. ,”  Proc. 17th Intl. Conf. on Pattern Recog.. 1, , 548–551  ((2004)).
Torsello  A., and Hancock  E. R., “ Correcting curvature-density effects in the Hamilton-Jacobi skeleton. ,” IEEE Trans. Image Process..  1057-7149 15, (4 ), 877–891  ((2006)).
Vizireanu  D. N., , Halunga  S., , and Fratu  O., “ A grayscale image interpolation method using new morphological skeleton. ,”  Telecomm. Modern Satellite, Cable and Broadcasting Service, Proc. 6th Intl. Conf.. 2, , 519–521  ((2003)).
Choi  W.-P., , Lam  K.-M., , and Siu  W.-C., “ An efficient algorithm for the extraction of a Euclidean skeleton. ,”  Proc. IEEE Intl. Conf. Acoustics, Speech, and Signal Process.. 4, , IV3241–IV3244  ((2002)).
Ma  W.-C., , Wu  F.-C., , and Ouhyoung  M., “ Skeleton extraction of 3D objects with radial basis functions. ,” Int. J. Shape Model..  0218-6543 , 207–215  ((2003)).
Xu  J., “ A generalized discrete morphological skeleton transform with multiple structuring elements for the extraction of structural shape components. ,” IEEE Trans. Image Process..  1057-7149 12, (12 ), 1677–1686  ((2003)).
Xu  J., “ A generalized morphological skeleton transform and extraction of structural shape components. ,”  Proc. Intl. Conf. Image Process.. 1, , 325–328  ((2003)).
Xu  J., “ Efficient morphological shape representation with overlapping disk components. ,” IEEE Trans. Image Process..  1057-7149 10, (9 ), 1346–1356  ((2001)).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.