Óêðà¿íñüêà   Ðóññêèé
DonNTU   Masters' portal

Abstract on the topic Research and development of a method for determining an object on an image with using the algorithm of ant colony

        

Contents

                 

Introduction

        

In recent years, a scientific direction with the name Natural Computing (Natural Computing), which combines mathematical methods, which lay down the principles of natural mechanisms of adoption solutions. These mechanisms ensure the effective adaptation of flora and fauna to the environment throughout the several million years.

        

Among the so-called Soft computing techniques developed over the past ten years for difficult to solve problems of discrete optimization, are listed:

        

Simulation of self-organization of ants colony forms the basis of ant optimization algorithms. The colony Ants can be considered as a multi-agent system in which each agent (ant) functions autonomously by very simple rules. In contrast to the almost primitive behavior of agents, the behavior of all systems it turns out to be surprisingly reasonable.

        

Ant algorithms are seriously investigated by European scientists since the mid-1990s. To date, Good results have been obtained for optimizing such complex combinatorial problems as the traveling salesman problem, a task optimization of truck routes, graph coloring problem, quadratic assignment problem, task optimize network schedules, the task of scheduling and many others. The ant algorithms are particularly effective at dynamic optimization of processes in distributed non-stationary systems, for example, traffic in telecommunication networks.

                 

1. STATEMENT OF THE TASK

The purpose of the master's thesis is to study and develop a method for determining the object on the image using the algorithm of ant colony.

        

To achieve this goal, you must perform the task data:

        
                
  1. Analyze the current state of the problem of determining the objects in the image.
    2.             
  2. Analyze modern methods of swarm optimization of object detection in the image.
    3.             
  3. Develop a swarm method for determining objects in an image using the algorithm of ant colony
    4.             
  4. Propose a modification of the roving algorithm, to optimize the algorithm of ant colonies to determine the object on the image.
    5.             
  5. Development of software, a swarm algorithm, for optimization of the algorithm of ant colony and conducting its testing
    6.             
  6. Conducting a comparison of the efficiency of the developed swarm algorithm with the existing algorithm
    7.         
                 

2. REVIEW OF THE CONTEMPORARY CONDITION OF THE PROBLEM

Let's consider the basic scientific works connected with research of possibility of use of algorithm of ant colony for image processing:

In the work of "Ant Colony Optimization towards Image Processing" K. Kavita, A. Madan, we consider various image processing tasks that can be achieved by optimizing the algorithm of ants colony - an important area of ??soft computing. The algorithm of ant colonies is an approach based on the computational intelligence that is used to solve the combinatorial optimization problem. The simplicity and optimal approach of the ant colony algorithm led to its applicability to routing, scheduling, subset problems, assignment and classification. Edge detection, snap to edge, function extraction, segmentation and image compression are various image processing tasks in which the algorithm is successfully applied.

T. Piatrik, E. Izquerto considers the possibility of image clustering by optimizing the algorithm of ant colony in the work "An application of ant colony optimization to image clustering". The authors have come to the conclusion that the original image search can be significantly improved by providing a good initial clustering of visual data. The problem of image clustering is that most modern algorithms can not identify individual clusters existing in different feature subspaces. In this paper, we propose a new approach for the clustering of subspaces based on the optimization of the ant colonies and the learning mechanism. The proposed algorithm changes the assumption that all clusters in a data set are in one set of measurements, assigning weights to functions in accordance with local data correlations along each dimension. The results of experiments with data sets of real images show the need to select functions in clustering and the advantages of selecting functions locally.

In the work "A Novel Image Segmentation Algorithm Based on Artificial Ant Colonies" Huizhi Cao, Peng Huang, and Shuqian Luo presented a new segmentation algorithm, which uses a biologically inspired paradigm known as artificial ants colonies. Taking into account the peculiarities of the colonies of artificial ants, an extended model is used, which is used for image segmentation. Each ant in the model has the ability to memorize a reference object, which will be updated when a new target is detected. A measure of fuzzy connectivity is taken to assess the similarity between the target and the reference object. The behavior of one ant depends on neighboring ants, and cooperation between ants is carried out by exchanging information through the updating of pheromones. The simulated results show the effectiveness of the new algorithm, which is able to preserve the details of the object and is insensitive to noise.

 ðàáîòå “Image Feature Selection Based on Ant Colony Optimization” Ling Chen, Bolun Chen, Yixin Chen ïðåäñòàâëÿåòñÿ àëãîðèòì âûáîðà ïðèçíàêîâ, îñíîâàííûé íà îïòèìèçàöèè êîëîíèè ìóðàâüåâ (ACO). Äëÿ n ôóíêöèé áîëüøèíñòâî ìåòîäîâ âûáîðà îáúåêòîâ íà îñíîâå ACO èñïîëüçóþò ïîëíûé ãðàô ñ ðåáðàìè O (n2). Îäíàêî èñêóññòâåííûå ìóðàâüè â ïðåäëàãàåìîì àëãîðèòìå ïåðåñåêàþòñÿ íà îðãðàôå ñ òîëüêî 2n äóãàìè. Àëãîðèòì èñïîëüçóåò ïðîèçâîäèòåëüíîñòü êëàññèôèêàòîðà è êîëè÷åñòâî âûáðàííûõ ôóíêöèé êàê ýâðèñòè÷åñêóþ èíôîðìàöèþ è âûáèðàåò îïòèìàëüíîå ïîäìíîæåñòâî ôóíêöèé ñ òî÷êè çðåíèÿ ðàçìåðà íàáîðà ôóíêöèé è ýôôåêòèâíîñòè êëàññèôèêàöèè. Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû íà ðàçíûõ èçîáðàæåíèÿõ ïîêàçûâàþò, ÷òî àëãîðèòì ìîæåò ïîëó÷èòü ëó÷øóþ òî÷íîñòü êëàññèôèêàöèè ñ ìåíüøèì íàáîðîì ôóíêöèé ïî ñðàâíåíèþ ñ äðóãèìè àëãîðèòìàìè.

                 

3. MODERN METHODS OF ROUTING OPTIMIZATION OF DETECTING OBJECTS ON IMAGES

3.1 Ant alghorythms

        

Ants refer to social insects that form collectives. A collective system is capable of solving complex dynamic collaboration tasks that could not be performed by each element systems in Separate in a variety of environments without external management, control or coordination. In such cases say about swarm intelligence, as about intricate ways of cooperative behavior, that is, strategy survival.

        

One of the confirmations of the optimality of the behavior of ant colonies is the fact that the network of nests supercolonies

is close to the minimal spanning tree of the graph of their anthills.

        

The basis of the behavior of the ant colony is self-organization, which ensures achievement of the general goals of the colony on basis of low-level interaction. The colony does not have centralized management, and its features are the exchange of local information only between individuals (direct exchange - food, visual and chemical contacts) and the presence of indirect exchange, which is used in ant algorithms. Thus, way, in general, blind ants are considered that are not able to feel the closeness of food.

        

Indirect exchange - stigmers (stigmergy), is represented by a distance e in time interaction, in which one individual changes a certain area of ??the environment, while others use this information later when it gets into it. Biologists have established that this deferred interaction occurs through a special chemical substance - pheromone, the secret of special glands deposited by the movement of the ant. Concentration of the pheromone in the path determines the preferability of movement along it.

Ant algorithms are probabilistic greedy heuristics, where probabilities are established based on information about the quality of the solution obtained from previous solutions. They can be used for both static and dynamic combinatorial optimization tasks. Convergence is guaranteed, that is, in any case we will get the optimal solution, but the rate of convergence is unknown.

3.2 The history of creating ant algorithms

everything from studying the behavior of real ants. Experiments with Argentine ants, conducted by Goss in 1989 and Deneborg in 1990, served as a starting point for further exploration of the swarm intelligence. Research applications of the knowledge obtained for discrete mathematics began in the early 90s of the XX century, the author of the idea is Marco Dorigo of the University of Brussels, Belgium. It was for the first time that he was able to formalize the behavior of ants and apply the strategy of their behavior to solve the problem of shortest paths. Later, with the participation of Gambardell, Tillard and Di Caro, many other approaches to solving complex optimization problems with the help of ant algorithms were developed. To date, these methods are very competitive in comparison with other heuristics and for some problems give the best results to date.

3.3 The concept of ant algorithms

The idea of ??the ant algorithm is to simulate the behavior of ants associated with their ability to quickly find the shortest path from an anthill to a food source and adapt to changing conditions, finding a new shortest path. With its movement, the ant marks the path with a pheromone, and this information is used by other ants to select the path. This is an elementary rule of behavior and determines the ability of ants to find a new path, if the old one is not available.

Consider the case shown in the figure when an obstacle appears on the optimal hitherto path. In this case, it is necessary to define a new optimal path. Having reached the barrier, ants with equal probability will bypass it to the right and left. The same will happen on the reverse side of the barrier. However, those ants that randomly choose the shortest path will pass it faster, and for several movements it will be more enriched with pheromone. Since the movement of ants is determined by the concentration of pheromone, the following will prefer this way, continuing to enrich it with a pheromone until this path for some reason becomes unavailable.

anim.gif

Ants movement route

The obvious positive feedback will quickly lead to the shortest path becoming the only route of the movement of most ants. Modeling the evaporation of pheromone - negative feedback - guarantees us that the locally found optimal solution will not be unique - the ants will look for other ways. If we simulate the process of such behavior on some graph, the edges of which represent possible ways of moving the ants, for a certain time, then the most enriched pheromone path along the edges of this graph will be the solution of the problem obtained with the help of the ant algorithm.

3.4 Generalized algorithm

Any ant algorithm, irrespective of modifications, is represented in the following form:

Tepe s look at each step in the cycle in more detail:.
  1. Create ants
    • The starting point, which is placed ant depends on the constraints imposed by the conditions of the problem. Because for each task the method of placing ants is decisive. Either they all fit into one point, or into different ones with repetitions, or without repetitions.
    • At the same stage, the initial level of pheromone is set. It is initialized with a small positive number so that at the initial step the probabilities of the transition to the next vertex are not zero.
  2. We are looking for solutions.
  3. We are updating the pheromone.
    • The pheromone level is updated according to the following formula:

      • 1245

      Where is the evaporation rate, L (t) is the price of the current solution for the k-th ant, and Q is the parameter having the order of the optimal solution price, - pheromone deposited by the k-th ant,(i, j).

  4. Additional actions.
    • Usually, a local search algorithm is used here, but it can also appear after searching for all solutions.

3.5 Stages of solving problems using ant algorithms

In order to build a suitable ant algorithm for solving a problem, you need to:

Also determining are:

4 ROUTINE METHOD OF DETERMINING OBJECTS ON IMAGE WITH THE HELP OF ALGORITHM OF ANSTITUTIONAL COLONIES

The problem is formulated as the problem of finding the minimum cost A closed path through all the vertices without repetitions at full weighted graph with n vertices. The vertex graphs are the cities that the salesman must visit, and the weights of the edges reflect the distances (lengths) or fare. This problem is NP-difficult, and the exact over-all algorithm of its solution has a factorial complexity. Simulation of the behavior of ants is related to the distribution of pheromone on the trail-edge of the graph in the traveling salesman's problem. In this case, the probability of including an edge in the route of a separate ant is proportional to the amount of pheromone on this edge, and the amount of pheromone deposited is proportional to the length of the route. The shorter the route, the more pheromone will be delayed on its edges, hence the larger number of ants will include it in the synthesis of their own routes. Modeling this approach using only positive feedback leads to premature convergence - most ants move along a locally optimal route. This can be avoided by simulating a negative feedback in the form of evaporation of pheromone. At the same time, if the pheromone evaporates quickly, it leads to a loss of memory of the colony and to the forgetting of good decisions; on the other hand, a large evaporation time can lead to a stable local optimal solution.

Now, taking into account the characteristics of the traveling salesman problem, we we can describe the local rules of ants' behavior when choosing a path.

  1. Ants have their own memory. Since each city can be visited only once, then each ant has a list of cities already visited - a list of prohibitions. Denote by the list of cities that need to visit the ant k, located in the city i.
  2. Ants have sight - visibility is a heuristic desire to visit city j, if the ant is in city i. We will assume that visibility is inversely proportional to the distance between cities.
  3. Ants have smell - they can catch a trail of pheromone, confirming the desire to visit city j from city i based on the experience of other ants. The amount of pheromone at the edge (i, j) at time t will be denoted by.
  4. 4. On this basis, we can formulate a probability-proportional rule that determines the probability of the transition of the k-th ant from city i to city j:

    Where, - parameters specifying of the weight of the pheromone trace. When = 0, the algorithm degenerates to a greedy algorithm (the closest city will be selected). Note that the choice of a city is probabilistic, rule (1) only determines the width of a city zone j; A random number is cast into the general zone of all cities, which determines the choice of the ant. The rule (1) does not change in the course of the algorithm, but for two different ants the value of the transition probability will differ, since they have a different list of permitted cities.

  5. 5. Passing the edge (i, j), the ant lays on it a certain amount of pheromone, which should be related to the optimality of the choice made. Let there be a route traversed by the ant k by the time t, is the length of this route, and Q is a parameter having a value of the order of the length of the optimal path. Then the amount of pheromone that can be deposited can be given in the form:

    The rules of the environment determine, first of all, the evaporation of pheromone. Let there be an evaporation coefficient, then the evaporation rule has the form: where m is the number of ants in the colony.

At the beginning of the algorithm, the amount of pheromone on the ribs is assumed to be a small positive number. The total number of ants remains constant and equal to the number of cities, each ant starts a route from its city.

A further modification of the algorithm can be the management of so-called "elite" ants that strengthen the edges of the nail the learned route found from the beginning of the algorithm. Let T * be the best current route, and L * its length. Then if there are e elite ants in the colony, then the edges of the route will receive an additional amount of pheromone.

4.1 The ant algorithm for the traveling salesman problem in pseudocode

Algorithm:

The complexity of this algorithm, as it is easy to see, depends on the life time of the colony () cities (n) and the number of ants in the colony (m).

6 AREA OF APPLICATION AND POSSIBLE MODIFICATIONS

Since the ants algorithm is based on the modeling of the movement of ants along certain paths, this approach can be an effective way of finding rational solutions for optimization problems that allow graph interpretation. A number of experiments show that the effectiveness of ant algorithms grows with the increase in the dimension of the solved optimization problems. Good results are obtained for non-stationary systems with time-varying parameters, for example, for calculations of telecommunication and computer networks. On the Internet, you can find a description of the application of the ant algorithm to develop the optimal structure of the GPS surveying networks in the context of creating high-precision geodetic and survey technologies. At present, based on the application of ant algorithms, good results have been obtained for such complex optimization tasks as the traveling salesman problem, the transport problem, the scheduling task, the graph coloring problem, the quadratic assignment problem, the optimization problem of network traffic, and a number of others.

< p> The quality of the solutions obtained largely depends on the tuning parameters in the probability-proportional path selection rule based on the current amount of pheromone and on the parameters of the deposition and evaporation rules romon. It is possible that dynamic adaptive adjustment of these parameters can help to obtain better solutions. An important role is played by the initial distribution of pheromone, as well as by the choice of a conditionally optimal solution at the initialization step. Perspective ways to improve the ant algorithms are various parameter adaptations using the base of fuzzy rules and their hybridization, for example, with genetic algorithms. Alternatively, such hybridization can consist of exchanging, at certain intervals, the current best solutions.

5 MODIFICATION OF THE ALGORITHM OF ANGAL COLONIES FOR DETERMINING THE OBJECT ON THE IMAGE

5.1 Advantages

5.2 Disadvantages

CONCLUSIONS

Ant algorithms are based on the simulation of the self-organization of social insects through the use of dynamic mechanisms by which the system is provided Gaeta global goal result of local low-level interaction elements. The effectiveness of ant algorithms increases with the increase in the dimension of the optimization problem. Ant algorithms provide solutions and Other combinatorial problems are not worse than general meta-heuristic optimization technologies and some problem-oriented methods. Especially good results of ant optimization are obtained for non-stationary systems whose parameters vary with time, for example, telecommunications and computer networks. An important property of ant algorithms is nonconvergence: even after a large number of iterations, many solutions are simultaneously investigated, as a result of which there are no long time delays in local extremes. All this allows us to recommend the use of ant algorithms for solving complex combinatorial optimization problems. Prospective ways to improve ant algorithms are online adaptation of parameters using the base of fuzzy rules, as well as their hybridization with other methods of natural calculations, for example, by genetic algorithms.

Source list

  1. Vadim Konushin, Vladimir Vezhnevets, Image segmentation methods: interactive segmentation, // Bulletin of the Moscow State University named after Lomonosov - ¹4, 2008. - P. 107-118
  2. L. Lucchese and S.K. Mitra Color Image Segmentation: A State-of-the-Art Survey, 2001
  3. N. R. Pal and S. K. Pal, A Review on Image Segmentation Techniques, Pattern Recognition, Vol. 26, No. 9, 2000
  4. R. Laptik, D. Navakauskas, Application of Ant Colony Optimization for Image Segmentation [Electronic resource]. - Access mode: http: //www.ktu .lt / lt / mokslas / ....
  5. Ruobing Zou, Weiyu Yu, Image Segmentation Based on Local Ant Colony Optimization. - Access mode: http://www.computer.org/portal/web/csdl/ ....
  6. Akhmetshin AM, Akhmetshina LG, Segmentation of low-contrast medical radiological images by the method of space-resonance imaging [Electronic resource]. - Access mode: http: //www.uacm.kharkov.ua/download / ....
  7. Tomas Piatrik, Ebroul Izquierdo, An application of ant colony optimization to image clustering [Electronic resource]. - Access mode: http: // citeseerx.ist.psu.edu / ....
  8. Dzung L.Pham, Chenyang Xu, Jerry L.Prince, A survey of the current methods in the medical image segmentation [Electronic resource]. - Access mode: http: //www.mcs.csueastbay.edu / ... .
  9. Huizhi Cao, Peng Huang, Shuqian Luo, A novel image segmentation based on artificial ant colonies [Electronic resource]. - Access mode: http://books.google.com/ .. ..
  10. Myung-Eun Lee, Soo-Hyung Kim, Wan-Hyun Cho, Soon-Young Park, Jun-Sik Lim, Segmentation of Brain MR Images Using an Ant Colony Optimization Algorithm [ Electronic resource]. - Access mode: http://www.computer.org/....