Sergey Mishustin

Introduction

In recent years the developing scientific field called "Natural computing", combines mathematical methods, which lays down the principles of the natural mechanisms of decision-making. These mechanisms provide effective adaptation of the flora and fauna of the environment for several million years.

Of our contemporaries are engaged in the field of natural computing S. Young, G. Beni, J. Wang, M. Dorigo, and domestic researchers S.A. Subbotin, A.A. Oleinik, V.K. Yatsenko and many others.

Examples of algorithms based on natural computations are algorithm ant colony optimization, bacterial foraging optimization algorithm, particle swarm optimization algorithm and genetic algorithm.

One of the applications of such algorithms is in the area of pattern recognition, which is nowadays widely used for the recognition of gestures, including on devices with multitouh interfaces.

At the heart of the creation of modern interfaces is multitouh alphabet gestures on the plane. A mathematical model of these gestures is a two-dimensional shape of the objects. For example, the arc may be a gesture of rotation, straight – zoom or move.

For best results, use pattern recognition multi-agent systems. Multi-agent system in this case can actas the algorithm using a set of agents, such as formic algorithm colony of bees algorithm or bacterial foraging optimization algorithm, as well as a system consisting of several algorithms, where algorithms somehow interact.

In the ant algorithm, ant colony can also be considered as a multi-agent system in which each agent (ant) operates autonomously for a very simple rules. In contrast, almost primitive behavior of agents, the behavior of the whole system turns surprisingly reasonable.

Ant algorithms seriously investigated by European scientists since the mid 90s. To date has received good results for the complex combinatorial optimization problems such as the problem traveling salesman problem of optimizing truck routes, the task of graph coloring, quadratic assignment problem, the problem of optimization of network scheduling, tasks cheduling, and many others.

Especially effective ant algorithms for dynamic optimization of unsteady processes in distributed systems, for example, traffics in telecommunication networks.

Genetic algorithm (GA) itself are not multi-agent system, but to solve a number of problems is quite effective. At the heart of the GA on the principles of natural evolution, formulated by Darwin – natural selection, variability, heredity. With their help, GA simulate the genetic processes occurring in biological communities.

Typically, genetic algorithms are used to solve optimization problems. Specialization GA include problems in combinatorics, bioinformatics, and other GA also used for processing and pattern recognition, particularly images.

Another algorithm – bacterial foraging optimization (BFO) has been accepted by the scientific community as a global optimization algorithm for distributed optimization andmanagement. BFO is based on modeling the behavior of Escherichia coli. BFO has already attracted the attention of researchers because of its effectiveness in solvingreal optimization problems arising in several areas of application. The biological basis for the strategy – moving bacteria E.coli, emulated wonderfully and is used as a simple algorithm optimization.

The purpose of performing this research is to analyze existing heuristic algorithms used in pattern recognition problems. The analysis is performed in the context of two-dimensional recognition of shapes of objects which can be obtained from devices using the technology multitouch.

1. The purpose and objectives of the research, the expected results

The object of the study is a binary image.

The subject of the study is to find a method of simple geometric shapes on a given image.

The main task is the development, program implementation and analysis of the search method of simple geometric shapes in a binary image.

The input data for the method is a binary image.

2. Relevance of the topic

Recognition of simple geometric shapes the images are very common in a number of problems, because such figures are often present in the environment created by man. For this problem, in recent time opened another area – mobile touch devices. In some applications and games need to recognize the primitive shapes, with few screen as a result of a manipulator on it.

3. Prospective scientific novelty

It is assumed that the search speed when using the method developed or developed by modification of the existing method is higher than the common techniques presently, only by performing one iteration of the search.

Findings

A review of techniques that can be applied to the problem of recognizing simple shapes. Chosen method of recognition for this task. Substantiated reasons for the choice. We consider the algorithm BFOA for an example of recognition of the circle. We consider the modification of an existing algorithm BFOA to find more shapes in the image. Proposed modification of this method. Comparative description of the existing and the proposed modifications. In future research work existing and proposed modifications to the different images for determine the numerical characteristics of speed, and planned analysis various objective functions.

This master's work is not completed yet. Final completion: December 2013. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

List of sources

1.  Преобразование Хафа (Hough transform) [Електронний ресурс]. – Режим доступа : http://www.cgm.computergraphics.ru/content/view/36.

2.  Kim D.H., Abraham A., Cho J.H. A Hybrid Genetic Algorithm and Bacterial Foraging Approach for Global Optimization // Information Sciences. – 2007. – № 18 (177). – P. 3918-3937.

3.  S. Dasgupta, S. Das, A. Biswas, A. Abraham Automatic circle detection on digital images with an adaptive bacterial foraging algorithm // Soft Comput. – 2010. – P. 1151–1164.

4.  Генетический алгоритм [Електронний ресурс]. – Режим доступа : ru.wikipedia.org/wiki/Генетический_алгоритм.

5.  Neidhardt F.C., Ingraham J.L., Schaechter M. Physiology of the Bacterial Cell: A Molecular Approach. – Sunderland: Sinauer Associates, 1990. – 520 p.

6.  Alberts B., Bray D., Lewis J., Raff M., Roberts K., Watson J.D. Molecular Biology of the Cell. – New York: Garland Publishing, 1994. – 1408 p.

7.  Segall J.E., Block S.M., Berg H.C. Temporal Comparisons in Bacterial Chemotaxis // Proceedings of the National Academy of Sciences. – 1986. – № 83 (23). – P. 8987-8991.

8.  Berg H.C. Random Walks in Biology. – Princeton: Princeton University Press, 1993. – 164 p.

9.  Woodward D.E., Tyson R., Myerscough M.R., Murray J.D., Budrene E.O., Berg H.C. Spatio-Temporal Patterns Generated by Salmonella Typhimurium // Biophysical Journal. – 1995. – № 68. – P. 2181-2189.

10.  Analysis And Design of Intelligent Systems Using Soft Computing Techniques / Eds.: P. Melin, O.R. Castillo, E.G. Ramirez, J. Kacprzyk. – Heidelberg: Springer, 2007. – 855 p.

11.  Passino K.M. Biomimicry of Bacterial Foraging for Distributed Optimization and Control // IEEE Control System Magazine. – 2002. – № 3 (22). – P. 52-67.