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