The article contains algorithm for detecting a connected objects contour. The algorithm was teste on digital biomedical images. The contours are use to separate objects from their backgrounds, to calculate the sizes of objects, to classify shapes and to find the feature points of objects).
Analysis form of objects plays a significant role in the
course of many researches. In particular, changing the shape
of the object can signal its transition from one state to another
(for example, in the medical process of the course of the
disease) [
Contour tracing is the stage of receiving a discrete signal describing the boundaries of the digital object.
The requirements for contour tracing algorithms are: reduction of storage space; reducing the time and complexity of further processing; obtaining informative features of the object.
The separate contour can take place in two ways: underlining the boundaries of an object by filtering the input image or by passing the inner contour of a homogeneous region.
The main algorithms for selecting the boundaries of the object are snake algorithm, Canny algorithm, filtration based on Sobel, Laplace, Prewitt and others. They are base on underscoring sharp drops of brightness, which are characteristic of the boundaries of objects. The result of their work is a set of unconnected areas. To obtain connected contour, it is necessary to carry out additional processing.
Algorithms for selection of areas: threshold segmentation,
clustering, region-growing, watershed algorithm, block
segmentation, etc. They are base on a union pixels in
homogeneous regions based on a certain homogeneity
criterion [
The following algorithms for passing the contour are know:
1) Square Tracing Algorithm [
2) Moore-Neighbor Tracing [
3) "Radial Sweep" [
4) Theo Pavlidi's Algorithm [
5) Snakes algorithm (active contour) [
6) Topological-hierarchical algorithms [
These algorithms are used for analysis and describing the contour. Almost every programming language has libraries with implemented algorithms, for example, for Mathlab, OpenCV etc.
Their main disadvantage is dependence on the complexity of the circuit and the stopping criterion. The algorithms are sensitive to microscopic objects, the contour of which contains a branch in one pixel thickness. This can lead both to the false end of the algorithms, and to the incorrect selection of the contour. A similar problem may occur if the micro-object consists of two or more parts that are connect only by single pixels. Another drawback of the algorithms is the imperfect criteria for stopping (returning to the starting point, passing a certain point several times), leading to incorrect work results.
II. FAST СONTOUR TRACING ALGORITHM
A binary image with the selected objects is forming as result of the selection of objects in the images and the subsequent binarization procedure. These objects are represent in the form of homogeneous areas. The geometric characteristics of these areas are important features for the analysis and perception of the image as a whole. Biological systems of visual perception, as shown by the research, use mainly the boundary of the border, rather than the separation of objects in brightness. In many cases, the most informative are the characteristics of the boundaries of the regions. To obtain the coordinates of the contour points, you must perform the path detection procedure by passing the boundary of the region.
We introduce the following definitions [
Let Im be a binary digital image with NxM pixels, where the coordinate of the top-leftmost pixel is (0,0) and that of the bottom-rightmost pixel is (N - 1, M - 1) . If Im( x, y) = 1 , then this point belongs to the object, otherwise - the background.
Start pixel Ims ( x, y) is the pixel from which the object boundary begins to go. The choice of the starting point is arbitrary, for example, the extreme left-top pixel belonging to the object. The final pixel Ime ( x, y) is the pixel, upon which the algorithm ends its operation. Active pixel Ima ( x, y) pixel located in the middle of the marking grid. Neighboring pixel Imn ( x, y) is a pixel that borders on the active pixel. Contour Pixel Imk ( x, y) is a pixel belonging to the object's contour. Background pixel Im f ( x, y) is a pixel that belongs to the background image. The neighboring contour Imkn ( x, y) pixel is a pixel that belongs to the contour of the object and borders on the active pixel.
After analyzing the advantages and disadvantages of existing methods, the following algorithm for contour tracing has been, develop with the ability to cut off the informational branches of the object's path, which is represent by a sequence of steps:
Start pixel is searching Ims ( x, y) .
Finding a neighboring contour pixel clockwise and a neighboring contour pixel Imkn ( x′, y′) counterclockwise.
If the adjacent contour Imkn ( x, y) = Imkn ( x′, y′) , then the recognize as background Im f ( x, y) and exclude from further processing and the transition to p. 8 is carried out.
If the resulting contour pixels do not match Imkn ( x, y) ≠ Imkn ( x′, y′) , then the start pixel is also recognize as the endpoint Ims ( x, y) = Ime ( x, y) . The neighboring contour pixel obtained in step 2 is entered into an array of contour pixels and assigned to it an active pixel label Imkn ( x, y) = Ima ( x, y) .
Imkn ( x, y) pixels active
match pixel is
The next neighboring contour pixel is searching Imkn ( x, y) . The sequence of checks of adjacent contour points is base on a marking grid. Pixels are clockwise checked. The starting checking position d is determined by (d '+2) mod 8 , where d ' is the position from which the active pixel was found Ima ( x, y) . Contour tracing illustrate on the Fig. 1. The search ends when you find the next contour pixel or to check all neighboring contour pixels.
If the neighboring pixel is a contour and does not match the end pixel, then it is enter into an array of contour pixels Imkn ( x, y) = Ima ( x, y) and assigned an active pixel tag.
If an adjacent pixel is found in the previous search steps, but does not match the end pixel Imkn ( x, y) ≠ Ime ( x, y) , then the active pixel is considered to be non-informative, removed from the array of outline points, indexed as the pixel of the background. The active pixel status is assign to the previous contour pixel.
If the resulting contour pixel coincides with the end pixel Imkn ( x, y) = Ime ( x, y) and the number of points in the contour is greater than one, then complete.
The time of algorithm work can be reduce by the parallel tracing both clockwise and opposite. In step 3, a parallelism of verification was perform. The starting point for validation is calculated as, (d ' '−2) mod 8 , where d ' ' is the position from which the counterclockwise active pixel was found Imac ( x, y) .
When Ima ( x, y) or Imac ( x, y) is found already markup contour pixel, then a label type check is performed. If the contour label was, install by them in the previous step, and then such a pixel is considered to be non-informative. If the contour mark was, install by the other side, then the contour is consider to be found.
To obtain a connected path, the points obtained by moving against the clock are successively add to the set of contour points obtained by direct motion.
In order to evaluate the operation of the contour tracing algorithm, classify the complexity of the contours of objects Table I. Simple contours are contours that can be describe (approximated) using 3 to 10 straight lines. Normal contours are contours that are approximated by more than 10 straight lines. Complex contours are described by a array of more than 10 straight lines, between which there are both sharp and dull angles. The approximating maximum error value is 2 pixels.
- The process of the algorithm's operation can be simply parsed into several streams, which reduces the processing time of the image. The accuracy of the algorithm results does not decrease in parallel processing;
- the possibility of a rollback of work. It should be noted that the principle of returning the operation of the passage algorithm has not been used previously. Using the rollback of work prevents the looping of the algorithm, the rejection of informational pixels and the possibility of correct work with complex contours.
Testing algorithm for correct work will be performed on digital images with the cytological objects. Cytological objects have different complexity of contour line, therefore they are optimally suited for testing. An example of testing is shown on Fig.2. 3 to 10 straight lines more than 10 straight lines more than 10 straight
lines and different angles between them
The results of contour tracing algorithms for normal contour are showing in Table II. The advantages of this algorithm are: - work with 8-connected contour; - Independence from the choice of the start pixel; - high speed by reducing points for analysis, for example, in comparison with the "Redial Sweep" algorithm can make up to 25% (Table II); informational pixels do not belong to the background of the image, but remain in the matrix of the outline points with the appropriate label assignment to them.
Results of simulation of contour tracing algorithms on the images chest figures, which including object with normal contour are showing in Tables III and IV. Number of inspections 976 1356 1473 1289 100% 139% 151% 132% 1089 112%
The Square Tracing Algorithm was chose as standard because it is easy to implement and the result of its work is always productive.
The contour tracing algorithm is allows to discard the less informative branches for further analysis, since it provides for a rollback process. However, if it is necessary to obtain a complete connected contour of object, the possibility of processing small informative branches is foreseen.
Obtained connected object contour in the form of a sequence of points coordinates can be further analyzed. For example, to reduce the amount of memory for storing the contour can perform an approximation procedure. 523 523 523 447 100% 77% 77% 77% 65%