=Paper=
{{Paper
|id=Vol-2300/Paper53
|storemode=property
|title=Fast Contour Tracing Algorithm Based on a Backward Contour Tracing Method
|pdfUrl=https://ceur-ws.org/Vol-2300/Paper53.pdf
|volume=Vol-2300
|authors=Yuriy Batko,Vitalii Dyminskyi
|dblpUrl=https://dblp.org/rec/conf/acit4/BatkoD18
}}
==Fast Contour Tracing Algorithm Based on a Backward Contour Tracing Method==
https://ceur-ws.org/Vol-2300/Paper53.pdf
219
Fast Contour Tracing Algorithm Based on a Backward
Contour Tracing Method
Yuriy Batko, Vitalii Dyminskyi
Department of Computer Science, Ternopil National Economic University, UKRAINE, Ternopil, 8 Chehova str., email: bum@tneu.edu.ua
Abstract: The article contains algorithm for detecting a object), then right turn). The algorithm stops its work if it
connected objects contour. The algorithm was teste on returns to the starting point.
digital biomedical images. The contours are use to 2) Moore-Neighbor Tracing [4] - The algorithm is based on
separate objects from their backgrounds, to calculate the step-by-step verification of all adjacent points in order to find
sizes of objects, to classify shapes and to find the feature the next contour point. Stopping the algorithm occurs when it
points of objects). returns to the starting point.
Keywords: contour tracing, image analysis, contour 3) "Radial Sweep" [5] - this algorithm is a modification of
chain, boundary following, pixel following. the previous one. Its main difference lies in the point of
beginning of the bypass of the active pixel. In this algorithm,
I. INTRODUCTION this is a point that was recognize as contour in the previous
Analysis form of objects plays a significant role in the step of the algorithm, and not the point from which the
course of many researches. In particular, changing the shape transition to the active pixel occurred.
of the object can signal its transition from one state to another 4) Theo Pavlidi's Algorithm [6] - The main idea of the
(for example, in the medical process of the course of the algorithm is to use a group of three pixels to determine the
disease) [1]. In nature, the shape of an object is determine by next contour pixel. Verification is carry out by successive
its contours (cell walls, outside layer etc.). verification of adjacent points with a strictly defined
Contour tracing is the stage of receiving a discrete signal sequence.
describing the boundaries of the digital object. 5) Snakes algorithm (active contour) [7] and Amoeba
The requirements for contour tracing algorithms are: algorithm [8] are a group of algorithms base on finding
reduction of storage space; reducing the time and complexity contours by sequencing the image pixels to find the set of
of further processing; obtaining informative features of the extreme (boundary) pixels. The algorithms stop their work if
object. all possible pixels are searches or if there are no pixels that
The separate contour can take place in two ways: satisfy a certain condition.
underlining the boundaries of an object by filtering the input 6) Topological-hierarchical algorithms [9, 10] - a group of
image or by passing the inner contour of a homogeneous algorithms associated with tracking contours based on
region. hierarchical relations between points. Algorithms of this
The main algorithms for selecting the boundaries of the group instead of markers use morphometric operations of
object are snake algorithm, Canny algorithm, filtration based finding points of overlap of several circuits for the purpose of
on Sobel, Laplace, Prewitt and others. They are base on their further separation.
underscoring sharp drops of brightness, which are These algorithms are used for analysis and describing the
characteristic of the boundaries of objects. The result of their contour. Almost every programming language has libraries
work is a set of unconnected areas. To obtain connected with implemented algorithms, for example, for Mathlab,
contour, it is necessary to carry out additional processing. OpenCV etc.
Algorithms for selection of areas: threshold segmentation, Their main disadvantage is dependence on the complexity
clustering, region-growing, watershed algorithm, block of the circuit and the stopping criterion. The algorithms are
segmentation, etc. They are base on a union pixels in sensitive to microscopic objects, the contour of which
homogeneous regions based on a certain homogeneity contains a branch in one pixel thickness. This can lead both
criterion [2]. The result of their work is a set of homogeneous to the false end of the algorithms, and to the incorrect
areas. To get the description of the contour of object, it is selection of the contour. A similar problem may occur if the
necessary to use contour tracing algorithms. micro-object consists of two or more parts that are connect
The following algorithms for passing the contour are only by single pixels. Another drawback of the algorithms is
know: the imperfect criteria for stopping (returning to the starting
1) Square Tracing Algorithm [3] algorithm, the main point, passing a certain point several times), leading to
advantage of which is simplicity. Contour tracing is base on incorrect work results.
two simple rules: if the value of the active pixel is equal to
one (the active pixel is at the point belonging the object), then
II. FAST СONTOUR TRACING ALGORITHM
the left turn, otherwise, when the active pixel value is zero A binary image with the selected objects is forming as
(the active pixel is at a point, which does not belong the result of the selection of objects in the images and the
subsequent binarization procedure. These objects are
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
220
represent in the form of homogeneous areas. The geometric The next neighboring contour pixel is
characteristics of these areas are important features for the searching Imkn ( x , y ) . The sequence of checks of adjacent
analysis and perception of the image as a whole. Biological
systems of visual perception, as shown by the research, use contour points is base on a marking grid. Pixels are clockwise
mainly the boundary of the border, rather than the separation checked. The starting checking position d is determined by
of objects in brightness. In many cases, the most informative ( d '+2) mod 8 , where d ' is the position from which the
are the characteristics of the boundaries of the regions. To
obtain the coordinates of the contour points, you must active pixel was found Ima ( x , y ) . Contour tracing illustrate
perform the path detection procedure by passing the on the Fig. 1. The search ends when you find the next contour
boundary of the region. pixel or to check all neighboring contour pixels.
We introduce the following definitions [11]:
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. Fig.1. Contour tracing for steps
Contour Pixel Imk ( x , y ) is a pixel belonging to the object's If the neighboring pixel is a contour and does not match
the end pixel, then it is enter into an array of contour pixels
contour. Background pixel Im f ( x , y ) is a pixel that belongs
Imkn ( x , y ) = Ima ( x , y ) and assigned an active pixel tag.
to the background image. The neighboring contour If an adjacent pixel is found in the previous search steps,
Imkn ( x , y ) pixel is a pixel that belongs to the contour of the but does not match the end pixel Imkn ( x , y ) ≠ Ime ( x , y ) ,
object and borders on the active pixel. then the active pixel is considered to be non-informative,
After analyzing the advantages and disadvantages of removed from the array of outline points, indexed as the pixel
existing methods, the following algorithm for contour tracing of the background. The active pixel status is assign to the
has been, develop with the ability to cut off the informational previous contour pixel.
branches of the object's path, which is represent by a If the resulting contour pixel coincides with the end pixel
sequence of steps:
Imkn ( x , y ) = Ime ( x , y ) and the number of points in the
Start pixel is searching Ims ( x , y ) .
contour is greater than one, then complete.
Finding a neighboring contour pixel Imkn ( x , y ) The time of algorithm work can be reduce by the parallel
tracing both clockwise and opposite. In step 3, a parallelism
clockwise and a neighboring contour pixel Imkn ( x ′, y ′) of verification was perform. The starting point for validation
counterclockwise. is calculated as, ( d ' '−2) mod 8 , where d ' ' is the position
If the adjacent contour pixels match from which the counterclockwise active pixel was found
Imkn ( x , y ) = Imkn ( x ′, y ′) , then the active pixel is Imac ( x , y ) .
recognize as background Im f ( x , y ) and exclude from When Ima ( x , y ) or Imac ( x , y ) is found already markup
further processing and the transition to p. 8 is carried out. contour pixel, then a label type check is performed. If the
If the resulting contour pixels do not match contour label was, install by them in the previous step, and
Imkn ( x , y ) ≠ Imkn ( x ′, y ′) , then the start pixel is also then such a pixel is considered to be non-informative. If the
contour mark was, install by the other side, then the contour
recognize as the endpoint Ims ( x , y ) = Ime ( x , y ) . The is consider to be found.
neighboring contour pixel obtained in step 2 is entered into To obtain a connected path, the points obtained by moving
an array of contour pixels and assigned to it an active pixel against the clock are successively add to the set of contour
points obtained by direct motion.
label Imkn ( x , y ) = Ima ( x , y ) .
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
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
221
(approximated) using 3 to 10 straight lines. Normal contours - The process of the algorithm's operation can be simply
are contours that are approximated by more than 10 straight parsed into several streams, which reduces the processing
lines. Complex contours are described by a array of more time of the image. The accuracy of the algorithm results does
than 10 straight lines, between which there are both sharp and not decrease in parallel processing;
dull angles. The approximating maximum error value is 2 - the possibility of a rollback of work. It should be noted
pixels. that the principle of returning the operation of the passage
TABLE I. OBJECT CONTOUR CLASSIFICATION algorithm has not been used previously. Using the rollback of
work prevents the looping of the algorithm, the rejection of
Simple Normal Complex contours
informational pixels and the possibility of correct work with
contours contours
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.
more than more than 10 straight
3 to 10 straight
10 straight lines and different
lines
lines angles between them
The results of contour tracing algorithms for normal
contour are showing in Table II.
TABLE II. COMPARISON CONTOUR TRACING ALGORITHMS FOR
DIFFERENT PARAMETERS
Algorithms 4- 8- Number of
Connectivity Connectivity inspections
contour contour
Square Tracing
+ - 1-4
Algorithm
Moore-
Neighbor + + 1-7
Tracing
Redial Sweep + + 1-8
Theo Pavlidi’s
+ + (1-3)x3
Algorithm
Fast Backward
Contour
+ + 1-6
Tracing
Algorithm
The advantages of this algorithm are:
- work with 8-connected contour; Fig.2. Contour tracing with Fast Backward Contour Tracing
- Independence from the choice of the start pixel; Algorithm
- high speed by reducing points for analysis, for example, It is possible to form a connected contour of object,
in comparison with the "Redial Sweep" algorithm can make without rejecting the informative pixels. In this case,
up to 25% (Table II);
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
222
informational pixels do not belong to the background of the The Square Tracing Algorithm was chose as standard
image, but remain in the matrix of the outline points with the because it is easy to implement and the result of its work is
appropriate label assignment to them. always productive.
Results of simulation of contour tracing algorithms on the
images chest figures, which including object with normal III. CONCLUSION
contour are showing in Tables III and IV. The contour tracing algorithm is allows to discard the less
informative branches for further analysis, since it provides for
TABLE III. CONTOUR TRACING WITH FAST BACKWARD
a rollback process. However, if it is necessary to obtain a
CONTOUR TRACING ALGORITHM
complete connected contour of object, the possibility of
Image object Contour object 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.
REFERENCES
[1] A. Kazlouski; R. K. Sadykhov, "Plain objects detection
in image based on a contour tracing algorithm in a
binary image", Innovations in Intelligent Systems and
Applications (INISTA) Proceedings, 2014 IEEE
International Symposium, 23-25 June 2014, DOI:
10.1109/INISTA.2014.6873624.
[2] O. Berezsky, G. Melnyk, Yu. Batko, O. Pitsun, "Regions
Matching Algorithms Analysis to Quantify the Image
Segmentation Results", Proceedings of the 11th
International Scientific and Technical Conference CSIT,
2016 , pp. 200-203.
[3] William K. Pratt, Digital Image Processing: PIKS
Inside, Third Edition, John Wiley and Sons, Inc., New
York. – 2001–736p.
[4] V. Hlavac, M. Sonka, R. Boyle, Image Processing,
Analysis, and Machine Vision, International Student
Edition. Thomson Learning, part of the Thomson
Corporation – 2008 – 829p.
[5] P.Rajashekar, "Evaluation of Stopping Criterion in
Contour Tracing Algorithms" (IJCSIT) International
Journal of Computer Science and Information
Technologies. – Vol. 3 (3). – 2012. – P. 3888-3894.
TABLE IV. COMPARISON CONTOUR TRACING ALGORITHMS [6] T. Pavlidis, Algorithms for Graphics and Image
Algorithms Perimeter, Perimeter, Number Number Processing, US, Rockville, Maryland: Computer Science
pixel % of of Press, 1982. – 438 p.
inspec- inspec- [7] M. Kass, A. Witkin, D. Terzopoulos, Snakes: active
tions tions, % contour models, Int J Comput Vis – 1988- pp. 321–331.
Square [8] G. Iannizzotto, L. Vita, Fast and accurate edge-based
Tracing 683 100% 976 100% segmentation with no contour smoothing in 2-D real
Algorithm images, IEEE Trans Image Process 9- 2000-1232–1237.
Moore- [9] P. Kuagoolkijgarn, P. Koomsap, N. Chansri, A new
algorithm for tracing nests of interconnected contours,
Neighbor 523 77% 1356 139%
The International Journal of Advanced Manufacturing
Tracing
Technology September 2010, Volume 50, Issue 5–8, pp
Redial 717–727.
523 77% 1473 151%
Sweep [10] P. Koomsap, N. Chansri, Topological hierarchy-contour
Theo tracing algorithm for nests of interconnected contours,
Pavlidi’s 523 77% 1289 132% Int J Adv Manuf Technol (2014) 70:1247–1266.
Algorithm [11] Yu. Batko, O. Berezsky "Algorithm of determination of
Fast image contours of biological nature", Proceedings of
Backward international conference "Modern problems of radio
Contour 447 65% 1089 112% engineering, telecommunications and computer science"
Tracing TCSET 2006, 28 February – 4 March 2006, Lviv,
Algorithm Ukraine. – 2006. – pp. 642–644.
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic