1.

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.

2.

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 proved^{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} that the skeleton subsets $S(X,nB)$ , 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:

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:

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.

3.

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(X,n_{B}B)$ , with $n_B=0,1,2,\mathrm{\dots },N_B$ , $S(X,N_{B}B)\ne \varnothing$ , $S(X,(N_B+1)B)=\varnothing$ , $n_B⩾N_B+1$ . We may then define $X_B^{n_B}=S(X,n_{B}B)$ , for $n_B=0,1,2,\mathrm{\dots },N_B$ .

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

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,\mathrm{\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,\mathrm{\dots },N_h^{n_B}$ , we obtain the skeleton subsets $P\left(n_h^{n_B}{L}^h\right)=S(X_B^{n_B},n_h^{n_B}{L}^h)$ , with $S(X_B^{n_B},N_h^{n_B}{L}^h)\ne \varnothing$ and $S(X_B^{n_B},(N_h^{n_B}+1)L^h)=\varnothing ,n⩾N_h^{n_B}+1$ , of the first-order skeleton subsets $X_B^{n_B}$ .

We may then define

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(X_B^{n_B},n_v^{n_B}{L}^v)$ for $n_v^{n_B}=0,1,2,\mathrm{\dots },N_v^{n_B}$ .

As with Eq. ³, we may now define

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.

4.

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.