Importance Of Thinning And Image Analysis Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Thinning plays a vital role in image processing and computer vision. It is an important preprocessing step in many applications such as document analysis, image compression, data compression, fingerprint classification, and pattern recognition. The main objective of thinning is to minimize the amount of information to be processed by preserving the important information such as shape, size and topological properties thereby enhancing the later processing steps (extracting features from patterns). Thinning process transforms an input binary image into skeletons with nearly thin lines, curves and arcs.

Skeleton, initially termed as medial axis, was first introduced by Blum [Blum, 1964]. During these years, several thinning algorithms are developed to address wide variety of problems. These algorithms are classified into iterative and non-iterative as shown in figure 1.1 based on the approach used for thinning [Lam, Lee & Suen, 1992]. Non-iterative algorithms obtain the skeleton in a single pass using the methodologies like distance transforms and run-length coding without considering all the pixels. Iterative algorithms either delete or retain the boundary pixels layer by layer successively until the desired skeleton is obtained. These iterative algorithms are categorized as sequential (boundary pixels are processed one by one, layer by layer) and parallel (all the boundary pixels are processed simultaneously layer by layer). Sequential algorithms consume less amounts of memory and produce better skeletons. In contrast, parallel algorithms are much faster and require more memory compared to sequential algorithms. Parallel algorithms process all the border pixels at once and hence are order independent.

A good thinning algorithm should possess many properties. First, the result of thinning should be connected and one pixel width. Second, the skeleton should have minimal deviation from the medial (central) axis. Third, skeleton should preserve the topological and geometrical properties of the image to be thinned. Fourth, the skeleton produced should not affected by the noise near the boundaries (i.e. insensitive to noise). Fifth, the algorithm should be efficient in terms of memory requirements and time constraints. Sixth, the skeleton produced should be invariant to the geometrical transformations like rotation and scaling. Finally, the skeleton obtained should be in such a way that one can able to reconstruct the original image.

All algorithms may not satisfy all the above characteristics, but a good algorithm aims at most of them. A number of thinning algorithms have been proposed during the last four decades. In recent past, newly devised algorithms concentrated on improving the quality of the skeleton obtained or reducing the execution time of the popular existing algorithms. The time required for thinning depends on the size and the complex shape of the given image.


Thinning plays crucial role in image analysis and pattern recognition applications. These applications require extracting features of interest like number of endpoints, junction points etc., to distinguish one object from another. Extracting such features from a thin line-like representation (skeleton) is easier and efficient (reduces time for analysis) than extracting from the original input image. In addition, from an artificial intelligence perspective, thin line representation is believed to be close to the way humans recognize objects. And finally, by reducing an object to only a skeleton, irrelevant features and image noise can be filtered out.


In spatial domain, digital image is defined as a two-dimensional object with a finite set of intensity values whose elements are referred to as picture elements (pixels). Images whose possible intensity values are only black (foreground) represented as 1 and white (background) represented as 0 are referred to as a binary images. Representation of English alphabet 'T' as a binary image is illustrated in figure 1.2.

Mask is an array of values specifying the relative importance of sub pixels. Most of the thinning algorithms based on spatial domain processing techniques use masks of size 3x3 as shown in figure 1.3.

Pixels P1, P2, P3, P4, P5, P6, P7 and P8 are 8-neighbors of the candidate pixel Pi denoted as N8(Pi). Whereas P2, P4, P6 and P8 are 4-neighbors of Pi denoted as N4(Pi). Thus

N8(Pi) = {P1, P2, P3, P4, P5, P6, P7, P8}

N4(Pi) = {P2, P4, P6, P8}

Pixel connectivity is a way in which pixels relate to their neighbors. If the pixels are connected horizontally and vertically in terms of pixel coordinates is termed as 4-connectivity. In 8-connectivity, pixels are connected diagonally also besides horizontal and vertical. Two pixels P and Q are said to be 4-connected, if Q is a 4-neighbor of P or 8-connected, if Q is an 8-neighbor of P. Pixel is said to be 4-simple or 8-simple; if we change the pixel from foreground to background does not change the 4-connectivity or 8-connectivity of 1's in its neighbors respectively. Connected Component is an ordered set of foreground pixels in such a way that any two successive pixels should be neighbors of each other. Based on the connectivity of the successive pixels the corresponding connected component is referred to as either 4-connected component or 8-connected component.

A break point is a foreground pixel which breaks the connectedness of the original object if it is changed to background. An edge or border point is a pixel with at least one background 4-neighbor. Redundant points are pixels belong to the skeleton whose removal doesn't affect the pixel connectivity.

Iteration refers to processing of all the border pixels belongs to a single layer. Scan (pass or cycle) refers to processing of all the border pixels layer by layer until no more pixels are deleted.

By placing a 3x3 mask on a foreground (black) pixel of an image, one can define three spatial domain operators on the 8-Neighborhood of Pi. These are foreground pixel count denoted by BP, The number of 4-connected components (one-to-zero or zero-to-one transitions) denoted by AP and the number of 8-connected components denoted by CP. For example, in figure 1.4, there is one one-to-zero transition (AP = 1) with six non-zero neighbors (BP = 6) comprises only one 8-connected component (CP = 1).

Based on the definitions of BP, AP and CP, an end point can be defined as a pixel whose BP = 1 or (BP == 2 && AP == 1) or (BP == 2 && AP == 1 && CP == 1) as illustrated in the following figure 1.5 (a), (b) and (c) respectively.


Binary image thinning algorithms based on the assumption that images to be thinned have only two possible intensity values 0 and 1. Hence all the input images have more than two intensity levels (gray or color) need to be converted to binary images. Normally thresholding technique is used as a preprocessing step to convert images into binary. If a pixel in the image has intensity less than the threshold value, the corresponding pixel in the resultant image is set to black (1). If the pixel is greater than or equal to the threshold intensity, the resulting pixel is set to white (0). Processing and analyzing such binary images is difficult and time consuming. Hence, the input images need to be transformed into skeletons containing essential information.

The process of obtaining skeletons is referred to as skeletonization which is spatial domain processing technique. These techniques operate directly on the aggregate of the pixels that compose the image. Skeletons are usually obtained through an iterative reduction operator called thinning. In this process, pixels whose removal will not affect the shape and size of the image (simple pixels) are iteratively removed until no more pixels can be deleted. Pixels can be removed either one-by-one (sequential) or layer-by-layer (parallel).

The endpoint criteria and different spatial processing operators (BP, AP and CP) discussed in section 1.2 are used to make decision about pixel deletions. These combinations can be converted into a set of masks termed as templates which can be matched against the candidate pixel neighborhood. These templates can be rewritten into rules in the form of "if the neighborhood matches with the input template, change it into resultant template". The latter approaches are termed as rule-based against to the former template based approaches.


The hardest task of thinning algorithms is to obtain the skeleton near the central axis. To tackle this problem, existing algorithms used the technique of dividing the entire process into sub cycles (passes). The Second major problem of thinning is excessive erosion. To overcome this problem, there are several approaches like smoothing templates, flagmap techniques are used. The third severe problem is connectivity preservation. Parallel algorithms are more vulnerable to discontinuities compared to sequential algorithms. Thus to preserve connectivity in parallel algorithms, one should adopt a method to retain the pixel that cause discontinuity. Fourth, redundant points do not make contribution to the connectivity and thus should be removed to improve the thinning ratio. Unfortunately, not every thinning algorithm can delete all the redundant points. The number of redundant points in a skeleton is inversely proportional to the quality of the skeleton.

The quality of the obtained skeleton can be judged based on how well it enhances the later processing steps. Thus defining the skeleton of an object uniquely is difficult. This vagueness causes difficulties in evaluating and comparing different thinning algorithms, but there are some properties of skeletons such as thinness, connectivity and sensitivity are measured using mathematical equations.


There are some limitations in thinning depending on the approach used. Parallel algorithms use non-isotropic way to find end points that result in producing nearly similar skeletons for specific orientations like multiples of right angles (900). Whereas for other angles they produce different skeletons may be with unnecessary information such as spurs or ridges. These are the bottlenecks for the recognition processes. Some thinning algorithms are developed to suit the specific needs (script dependent) of the application where they can be applied but failed for other application areas. Within the same application domain, Algorithm that works best for most of the patterns but failed for other types of patterns which are similar in appearance. Sometimes the resultant skeleton may contain more than one pixel and cause discontinuities if it thins further. These limitations motivated towards the investigation and finding the possibilities to overcome the difficulties.


Novel approaches to thinning are focused on implementing existing methods in an efficient manner. Some algorithms results in good skeletons for specialized patterns they are concentrating on but produce poor skeletons for other types of patterns. For example, thinning algorithms for patterns containing only straight lines may not be suitable for thinning patterns composed of only curves (Telugu Handwritten Characters). Whereas finger print patterns require sophisticated algorithms because of small ridges and furrows can influence the recognition process.

Devising a generalized thinning algorithm which can produce satisfactory results for all varieties of pattern shapes is very difficult [Fu, Ya-Ching & Pavlidis, 1999]. But the thinning algorithms developed recently aimed at more than one application area but are not completely generalized.


This research work focuses on the development of parallel binary image thinning algorithms which are rotation invariant and order independent. Besides this they are size and shape preserving as well as produce one pixel wide connected skeletons on a wide variety of image patterns ranging from linear to non-linear. We want to make the thinning algorithm independent of application areas ranging from thinning characters of different languages to finger prints. The performance and results obtained are compared with existing thinning algorithms in terms of excessive erosion, connectivity, thickness and symmetry of the skeletons, endpoint preservation, and visual quality after skeletonization.


For the tasks like character recognition, thinning operation is used as a pre-processing step. An effective thinning helps in latter recognition performance. In the recent past, most of the researchers have concentrated on reducing the thinning time of the algorithm than the resulting skeleton shape. A few of them focused on the quality of the skeleton produced. It is difficult to produce an algorithm which can simultaneously focuses on both thinning time and skeleton quality. Hence, the main objective of the proposed work is to develop a robust thinning algorithm that focuses simultaneously on both the factors. Besides these it also considers the order-independent and rotation-invariant properties as well as retaining topological and geometrical properties of the obtained skeletons.


The carried research work not only limited to thinning particular types of binary image patterns. The proposed algorithm considers varieties of image patterns varying from characters of different languages to objects of linear and non-linear as well as finger print images. Finally the proposed algorithm compared against the existing algorithms in terms of performance, thinning ratio, sensitivity to noise and the property of resulting connected skeletons around the medial axis with one pixel wide.


The remainder of this thesis is organized as follows. Chapters 2 deals with literature survey which reviews some of the existing thinning algorithms that have been used in this thesis work (iterative and non-iterative thinning algorithms). Chapter 3 gives a detailed description of the implementation of an efficient two-pass parallel binary image thinning algorithm and rule based order independent rotation invariant algorithm for binary images. Topology preserving and making the implementation time efficient are also discussed in this chapter. A detailed analysis and comparison of these algorithms explained in chapter 4. The analysis and comparison are based on the results of both simple input patterns and real images. Finally, the conclusions are summarized in chapter 5.