Content

1. Introduction
2. 1. Automatic image segmentation
1. 1.1 Statement of the problem
2. 1.2 Quality assessment methods for automatic segmentation
3. 2. Interactive image segmentation
1. 2.1 Statement of the problem
2. 2.2 Assessment of the quality of interactive segmentation algorithms
4. Conclusions
5. References

Introduction

Image segmentation is a partition image to dissimilar to some attributes field [1],[5]. It is assumed that the regions correspond to real objects, or parts thereof, and the boundaries of the regions correspond to the boundaries of objects. Segmentation is important in image processing tasks of computer vision.

Segmentation methods can be divided into two classes: automatic - do not require user interaction and interactive - use user input directly in the process [2],[3].

The main purpose of research is to development of methods and algorithms of contour segmentation in search problems of similar objects in an image. To achieve this goal it is necessary:

1. to stage tasks automatic and interactive image segmentation;
2. to consider the main criteria for assessing the quality of methods and algorithms for automatic and interactive segmentation;
3. to analyse of existing methods and algorithms for automatic and interactive image segmentation;
4. to develop of methods and algorithms of contour segmentation;
5. to develop software for search similar objects in an image.

1 Automatic image segmentation

1.1 Statement of the problem

Automatic segmentation tasks are divided into two classes

1. allocation areas of images with known properties;
2. partitioning the image into homogeneous areas.

Between the two performances of the problem is a fundamental difference. In the first case, the problem of segmentation is to find a certain areas about which there is a priori information (for example, we know the color, shape areas, or areas of ​​interest to us are famous image of the object). Methods main focus for this group of highly specialized for each task. Segmentation setting is mainly used in the problems of computer vision (scene analysis, the search for objects in the picture) [4],[6],[7].

In the second case, there is no a priori information about areas parameters not used, but on a partition of the image itself under some (eg, all areas must be uniform in color and texture). Since at formulation of the problem of segmentation is not used a priori information about the image of the object, the main focus for this group of methods are universal and apply to any of the images. Basically segmentation main focus for this formulation is applied at the initial stage of solving the problem, in order to get an image in a more convenient form for next work [8],[9].

At first we consider the formulation of the problem of segmentation as splitting the image into homogeneous areas. This statement came before the problem of extracting areas of images with known properties and methods main focus for this group at the moment is well developed.

It is clear that the task of splitting the image into homogeneous areas set correctly, since not always for the image is the only "correct" segmentation, which is not always the problem of segmentation has a unique solution. According same reason there is no objective criterion for assessing the quality of the partition image.

Figure 1 - The original image

Figure 2 - Options for the segmentation of the image

1.2 Quality assessment methods for automatic segmentation

Since the segmentation is usually not used alone, but as part of a system (for example, machine vision systems), from a practical point of view, the quality of the method is evaluated on the basis of the system as a whole. Therefore, the same segmentation method may be good for one task and bad for another. A rough estimate of the quality of the method in a specific problem usually fix a number of properties that should have a good segmentation. The performance is evaluated according to the method of how the segmentation obtained possesses these properties. Most often the following properties:

1. homogeneity regions (uniformity of color or texture);
2. dissimilarity of neighboring regions;
3. smoothness of the boundary of the region;
4. a small number of small "holes" in the region.

A more general approach to evaluating the quality of the method, which does not include a specific application, is to test the method on a common image database, which is known for the "correct" segmentation. For example, Berkeley Segmentation Dataset includes more than 1,000 images, manually otsegmentirovannyh 30 different people [2].

2. Interactive image segmentation

It has recently become clear that modern automatic algorithms are not able to solve arbitrary segmentation problem with a guaranteed result [3]. Moreover, most likely, in the near future there will be no such algorithms. Therefore, more and more attention is paid to the interactive image segmentation.

The real breakthrough in this area occurred in 2000 - with the invention Yuri Boikov and Marie-Pierre Jolly algorithm GraphCut. This algorithm is the de facto reference. Most of the new algorithms for interactive image segmentation algorithm development are GraphCut. Other algorithms are compared first with it. The cuts of graphs, which is based GraphCut, have been actively used in other areas of computer vision: video segmentation, stitchinge, stereo reconstruction [1],[3],[5].

Interactive image segmentation is widely used for image editing, analyzing medical data, and is an integral part of many computer vision algorithms [10],[11],[12].

2.1 Statement of the problem

In an interactive image segmentation is usually considered only the problem of the partition into two areas - the object and the background (the partition into more areas of multiple turns division into two areas) [3].

The input to the algorithm is:

1. the original image;
2. some additional information from the user:
   1. limitation of the fact that some specific pixels must belong to the object (background);
   2. bounding box around the object;
   3. the approximate boundary of the object.

In the process of the algorithm the user can refine or add input.

At the output of the algorithm should give a partition of the original image that satisfies the users cash constraints. This partition must satisfy certain a priori conceptions member of a partition of the objects depicted.

Figure 3 - Example of an interactive image segmentation. (animatied gif - 4 frames)

2.2 Assessment of the quality of interactive segmentation algorithms

In the automatic segmentation quality measures for constructing partitions, used the assumption that the pixel color similarity, texture within a single object must be maximized, and between objects - minimum [2]. But in an interactive segmentation of the user can do any number of clues algorithm - add new restrictions to specify the input information as long as it receives the expected result. It is clear that in the limit when the user explicitly tells about each pixel to which region it should belong, he will always get a perfect segmentation. It would be possible to assess the quality of segmentation in the same tips, but a variety of different algorithms receive input from the user [3],[8],[9].

Also interactive segmentation assumed that the user using the tips algorithm - an additional input should be able to otsegmentirovat even when part, and the color and texture of the background is closer than the remainder of the object. It is also difficult to create objective metrics [3].

So naturally, to compare the interactive segmentation algorithms often use subjective comparison by taking a few pictures, and several users to put one of two things:

1. apply the segmentation algorithm not all the images worse predetermined level (compared to the "worse" subjectively performed by the user, to compare a given sample of the segmentation), then measured for which the algorithm for this task took the least time;
2. for a specified, limited time, as much as possible apply segmentation to the image data, after the expiry of the due date, the user subjectively assess which algorithm gave a better segmentation.

Conclusions

In this research paper, an analysis of methods and algorithms for image segmentation contour. The paper discusses existing approaches to automatic and interactive image segmentation, the advantages and disadvantages of each approach, identifying criteria for evaluating the quality of methods and algorithms for segmentation, as well as a range of different methods of segmentation.

The investigations of methods and algorithms for contour segmentation is further will be used to solve the problems of searching for similar images.

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.

References

1. Конушин А.С. Материалы курса лекций лаборатории компьютерной графики при ВМК МГУ.
   // http://courses.graphicon.ru/files/courses/vision2/2012/lectures/cv2012_14_segmentation.pdf
2. Вежневец А. Баринова О. Методы сегментации изображений: автоматическая сегментация.
   // http://cgm.computergraphics.ru/content/view/147
3. Конушин В. Вежневец В. Методы сегментации изображений: интерактивная сегментация.
   // http://cgm.computergraphics.ru/content/view/172
4. Вежневец А. Выделение связных областей в цветных и полутоновых изображениях.
   // http://cgm.computergraphics.ru/content/view/53
5. Фурман Я.А. Введение в контурный анализ. // ФИЗМАТЛИТ 2003, 592 стр.
6. Шлезингер М. И. Математические средства обработки изображений. // Наукова думка, 1989, 196 стр.
7. Шлезингер М. И. Теоретические и прикладные вопросы распознавания изображений. // Издательство института кибернетики АН УССР, 1991, 86 стр.
8. Rafael Ceferino Gonzalez, Richard Eugene Woods. Digital Image Processing. // Prentice Hall, 2008, 954 p.
9. Bernd Jähne. Digital Image Processing. // Springer, 2005, 607 p.
10. David Salomon. Data Compression. // Springer, 2007, 1092 p.
11. Paragios N., Chen Y., Faugeras O. Handbook of Mathematical Models in Computer Vision. // Springer, 2010, 605 p.
12. Francus P. Image Analysis, Sediments and Paleoenvironments. // Springer, 2004, 330 p.