2.2.1 Boundary peeling

This

method is based on boundary erosion process; in this process each pixel removes

the pixels while sequence of pixels remains one pixel wide. This is a repetitive,

time intensive process of testing and deletion each layer. The difficulty of

this method is that the set of rules defined for removing pixels is dependent

highly on the type of image and that different set of rules will be applied for

different type of images. However, this method is good for connectivity preservation.

The pixel level iterative thinning is like iterative erosion of the line object

boundary as introduced by 35, the kernel procedure is moving a 3 x 3 window

over the image and applying a set of rules to mark the centre of the window,

after completion of each scan, all marked points are deleted until no more

points can be deleted. The set of functions, B(P1) represents the number of

black pixels, A(P1) :- no of white –black patterns and C(P1):- no of distinct 8

connected components and rules 36 are as follows. P is marked for deletion if

all the following rules are satisfied

·

P must have at least 1 white 4 connected

37 neighbors, means p is an edge point

·

P must have at least 2 black 8 connected

37 neighbors, means p should not be an end.

·

At least 1 of black 8 connected of p

must be unmarked.

·

P must not be a break point; deletion of

break point disconnects line in two components.

·

If P2 is marked setting P2

white must not make P a break point.

·

If P4 is marked, setting P4

white must not make P a break point.

A

fast parallel thinning 38 is proposed to perform deletion of corner points by

using two iterations. End points and pixel connectivity are preserved. Each

pattern is thinned down to a “skeleton” of unitary thickness but it

will not produce desired result in the presence of noise near corners. These

problems are resolved 39 by slight modification in conditions but it doesn’t

produce one pixel wide skeleton in sloping lines. Enhanced parallel thinning

algorithm 40 produces one pixel wide skeleton as well as it maintains 8

connectivity and removes the problems of 38,39. The main issue with pixel

level iterative thinning algorithm is the time complexity, which is O(wN),w is

line width and N is total number of

pixels in the image and in presence of noise these algorithm may not produce

desired results.

2.2.1 Distance transformation

These methods are based on the distance transform

and medial axis transforms (MAT), are sequential and non-iterative, the

distance coding is based on Euclidean distance or the approximation to

Euclidean distance. The skeleton produced in fixed number of passes

irrespective of image size 44. These algorithms are based on distance

transform of binary image as replacing each pixel by a number indicating the

minimum the minimum distance from that pixel to a white point after that local

maxima operation is used to find the skeleton of the object 43. The important

choice in distance transform methods is metric used in distance transform for

eg “Chamber 2-3” 41, “quasi Euclidean Metric 42″as it will directly affects

the centering of skeleton and rotation sensitivity.

Distance

transform – Voronoi Diagram:- The Voronoi skeleton can be calculated from boundary

of an object. Henceforth, the Voronoi diagram of a (discrete) set of boundary

points will be equivalently termed the discrete Voronoi medial axis (DVMA).

The DVMA is accurate approximation of the continuous MAT46,47,48.

The Delaunay triangulation and the

Voronoi diagram are utilized to extract the skeletons that are guaranteed to be

topologically correct to extract object centrelines 49, but this

method also sensitive to noise and jagged boundaries.