DonNTU-> Masters DonNTU
Abstract
Topicality.
The world tends to automate processes in all spheres of human life. Medicine - not the exception. Every year more and more medical equipment are appeare in hospitals and clinics. This new technical capabilities expand the range of research and discovering new ways for solving problems. In consequence, there is a lot of information contained in the images.
Problem.
Medical images provide contain a lot of information about the patient, but first we should extract it using required analysis. One of the main parts of the automated measurement of optical and geometrical parameters is the selection of objects. This problem is solved using the methods and means of digital image analysis. Segmentation of medical images is a difficult task, methods for the solution of which are chosen in accordance with the characteristics and properties of the analyzed image. [2]
Scientific novelty
The algorithm of ant colonies is applicable for a lot of optimization problems, specially on graphs. For the most part it has a positive effect. Applying it to the segmentation algorithms we obtain greater efficiency. There are currently developing such a plane are produced, but its practical application in large-scale projects only in the future.
Ant Colony Optimization
The idea of ant algorithm - modeling of the behavior of ants associated with their ability to quickly find the shortest path from nest to a food source and to adapt to changing conditions, finding new shortest path. In its motion the ant leaves pheromone in its path, and this information is used other ants to choose path. This is an elementary rule of conduct and determine the ability of ants to find new path, if the old is unavailable.
Consider the case shown in Figure 1.

Path of the ants 'home' to food.
Figure 1 -Path of the ants 'home' to food.

When the optimal path (Figure 1.A), there is a barrier (Figure 1.B) ant must define a new optimal path. When he reached the barrier, the ants with equal probability will bypass it on the right and left. Same will occur on the reverse side of the blockage. However, those ants that happen to choose the shortest path will be faster to pass, and a few movements it will be more enriched in pheromone. Since motion ants by the concentration of pheromone, then the following will prefer this route (Figure 1.D), continuing to enrich its pheromone to as long as this path for any reason becomes unavailable.
The apparent positive feedback will quickly lead to the fact that the shortest path will be the only route traffic Most ants. Modeling evaporation of pheromone - a negative feedback - we guarantee that the obtained locally optimal solution will not only - the ants will find other ways. If we model the process of such behavior some graph whose edges represent possible ways to move the ants for some time, then most enriched in pheromone path along the edges of this graph and will be a solution obtained by formic algorithm.[1]
Basic ant algorithm, regardless of modifications, can be represented by a scheme (Figure 2)
Generalized ant algorithm.

Figure 2 - Generalized ant algorithm.
(Animation: volume - 7.4 KB; size - 400x400; number of frames - 25; delay between frames - 5 ms; delay between the last and first frames - 5 ms; number of cycles repeat - indefinitely.)

Initialize the ants - a starting point, where the ant is placed depends on the constraints imposed by the terms problem. Because for each task, the way ants placement is crucial. Either they are placed in one point, either in different repetitions with or without repetition. At this juncture, given the initial level of pheromone. It is initialized with a small positive number to the initial step of the transition probability in the next peak were not zero.
Finding solutions.
The transition probability from vertex i to vertex j is determined according to equation 1:

Probability transition from vertex i to vertex j (1)

where formula 2 is the set of possible vertices associated with vertex i, for ant k, τ (ij) - the level of pheromone d (ij) - heuristic distance,α and β - constant parameters. Update pheromone occurs in accordance with the equation 2.

Update pheromone (2)

where n (k) - number of ants ρ– evaporation, Lk(t) – path length, constructed k-th ant at time t, and the Q - parameter value, ie - pheromone laid by k-th ant uses edge (i, j).
Application of ant colony algorithm for the problem of image segmentation.
This is a distributed algorithm that uses positive feedback to achieve the clustering of pixels. It is mainly based on the versions described in [4] and [1]. A number of slight modifications have been introduced that improve the quality of the clustering and to speed up of the convergence. In both LF and Agent algorithms, the ants evolve on the discrete 2D board. The size of this grid should be selected in dependence of the data collection, as it otherwise impairs convergence speed. If the size is too small, the ants carrying data items will make everlasting move since they will never find an empty case to drop down them. This will consume large amount of computational time. Otherwise, if the size of the grid is too large, ants will make idle movement when no carrying data items before encountering an item data. As far as we know these is not theoretical guideline to determine automatically the size of the board. For this reason, we replace the rectangular grid by a discrete array of N cells when N is the total number of pixels to be clustered. All cells of the array are connected to the nest of the ants’ colony in order to let the ants travel from one cell to another easily. During the algorithm ants are able to create, build or destroy existing clusters of pixels. A cluster is defined as a collection of two or more pixels.
As in [2], a cluster is spatially located in a single cell, which makes the identification of clusters easily unlike in the LF algorithm where spatial patterns of objects car touch each other. Initially the N pixels {P1,…Pn} to be clustered are placed on the array such that each array cell can only occupied by one pixel. Each ant ai from a colony of K ants { a(1),....,a(k)} picks up a randomly chosen pixel from its cell and returns to his nest. After this initialization phase, the clustering phase starts. During an iterative process, one ant is selected randomly; it performs a number of movements between its nest and the array and decides with a probabilistic rule whether or not to drop its pixel. If the ant becomes free, it searches for a new pixel to pick up. The ant has knowledge of a list of the locations of all pixels not being carried by other ants. The ant randomly selects a pixel from this list of “free” pixels and probabilistically decides whether or not to pick up that pixel. This process is repeated for all ants. The stopping criterion of the algorithm is the number of iteration fixed by the user at the beginning. The algorithm works as follows: On the array, each ant a(i) may possibly picks up a pixel p(i) from a cell c(k) or drop it in the cell c(k) according to the similarity function f, which represents the average distance between the pixel p(i) and others pixels p(j) in the cell c(k). It is used to determine when pixel p(i)should leave from others pixels. [8]
Conclusion.
Although the image processing algorithms can provide accurate quantitative indicators (eg, measurement of left ventricular ejection fraction heart of a dynamic sequence of images) or can solve certain problems, which is not feasible for manual processing (eg, accurate registration of multimodal images), problems of reliability and accountability remain major obstacles to widespread use of these algorithms. Checking the correctness of the algorithm is often difficult due to lack of theory, allows one to compare the results of processing. [7]
References.
1. Информационные управляющие системы и компьютерный мониторинг 2010/ Сборник материалов к I Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых.- Донецк,ДонНТУ-2010, с.12-16.
2.Винсент Бретон. Медицинские изображения и их обработка
3. Методы сегментации изображений: интерактивная сегментация. Вадим Конушин, Владимир Вежневец
4. Image Segmentation Using ACO. Manda M. Ukey, Dr. V. M. Thakare
5. Swarm Intelligence: Focus on Ant and Particle Swarm Optimization, Book edited by: Felix T. S. Chan and Manoj Kumar Tiwari, ISBN 978-3-902613-09-7, pp. 532, December 2007, Itech Education and Publishing, Vienna, Austria
6. N. R. Pal and S. K. Pal, “A Review on Image Segmentation Techniques,” Pattern Recognition, Vol. 26, No 9, 2000
7. R. Jain, R. Kasturi, and B. G. Schunck, Machine Vision, 2005
8. S.-T. Bow, Pattern Recognition and Image Preprocessing, Marcel Dekker, Inc., New York, NY, 2006.