DonNTU   Masters' portal

Abstract

Table of contents

Intro

In computer vision, segmentation — the process of partitioning digital images into multiple segments (sets of pixels, also known as superpixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to identify objects and boundaries (lines, curves, etc.) on images. More precisely, the segmentation of images — a process of assigning these labels to each pixel in the image that the pixels with the same label have common visual characteristics.

The result of image segmentation is a set of segments, which together cover the entire image, or a set of contours extracted from the image. All pixels in the segment are similar in some characteristic or computed property, such as color, brightness, or texture. Adjacent segments are significantly different in this characteristic.

Urgency

One of the main problems in the field of computer vision is the task of extracting information and knowledge from images. Segmentation — the process of partitioning the image into segments (clusters, superpixels), which represent a set of pixels, united on this or other status. Segmentation allows you to reduce the amount of information in the image and to facilitate its analysis. In addition, the solution to the problem of image segmentation is the key to many other problems and techniques of computer vision, such as:

and to ease the problem of a logical grouping of image pixels.

In some subject areas there are difficulties with the definition of rules by which the segmentation is performed, also after choosing the optimal segmentation rule raises a lot of computational problems associated with finding the required segmentation.

Here are some examples of practical applications of segmentation:

Goals

The aim is to study the possibility of efficient implementation of segmentation algorithms to simplify the task of object recognition in two-dimensional images

Objectives

The work will need to examine existing approaches to image segmentation, to analyze the possibility of parallelization of existing algorithms and optimization algorithms for software implementation using technology NVidia CUDA.

The expected results

As a result, work is planned to obtain:

  1. results of experiments to perform a comparative analysis of serial and parallel implementation of algorithms;
  2. software system for image segmentation using the selected algorithm.

Novelty

Existing segmentation algorithms can not provide high-speed image processing because of the need to process each pixel individually. Actively developing technology NVidia CUDA allows you to use the full power of parallel graphics accelerators for various applications.

Review of similar studies

In DonNTU previously conducted studies on undergraduates image segmentation. Deputat, Skobtsov [14] investigated the possibility of image segmentation using ant colony algorithm. Savchenko [15] also investigated methods for image segmentation. Chudovsky [16] conducted studies on the implementation of the algorithm for edge detection technology with Kenni NVidia CUDA.

Image segmentation is often the first step before applying the algorithms for image processing at higher levels. If you need to perform processing in real time is a problem with the performance of a software system that performs segmentation. This is due to the fact that the algorithms work with individual pixels and the number of operations is large enough. To overcome this problem it is necessary to perform the segmentation in parallel using multiple compute nodes. Currently, active research is conducted on the parallelization of algorithms for segmentation.

Some of the earliest studies conducted Alireza Khotanzad and Abdel Majud Bouarfa. Their work [8] is devoted to image segmentation using a threshold clustering algorithm. As a result of their work was received eight times the acceleration of the algorithm using 11 processors.

In studies conducted by Shahram Rahimi, M. Zargham and A. Thakre [12], the possibility of parallelization of the algorithm C-Mean, using a fuzzy partition of pixels into clusters. There was a ninefold acceleration efficiency close to unity. In the course of studies was found proportionately between the number of processors and the growth rate of image segmentation.

Studies Nawal Copty, Sanjay Ranka, Geo rey Fox, Ravi V. Shankar [10] also show good results when parallelizing algorithms growth regions. The studies were conducted using a computer system, built with the architecture of MIMD. As a result also seen a significant increase in processing speed when using a large number of computing nodes.

In Jan Wassenberg, Wolfgang Middelmann and Peter Sanders [2] described a segmentation algorithm on graphs with a computer system with the architecture of SMP. Operating time of the algorithm depends linearly on the dimension of the input data.

The classification of existing algorithms

For the image segmentation was developed several generic algorithms. Since the general solution for the problem of image segmentation does not exist, these methods often have to combine with knowledge of the subject area, to better address the problem in a particular subject area.

One classification algorithm divides the existing methods for the following subset of (fig. 1) [5]:

Algorithm classification scheme

Figure 1 — Algorithm classification scheme. Animation — 8 frames, the delay is 500 ms and 3000 ms for the last frame.

Thresholding algorithms are simple to implement. Threshold — a sign of (property), which helps to separate the desired signal to the classes. The operation of the threshold is to compare the separation of functions (such a function can return the brightness of a pixel) for each pixel with a given threshold.

The algorithms in this group may give inaccurate results, especially at a high level of noise in the image, which requires an additional pre- or post-processing of images [7].

The simplest transformation — binarization. It is an operation of the threshold of separation, which results in a binary image. The purpose of binarization operation is a radical decrease in the amount of information contained in the image. During the initial binarization halftone image having a certain number of brightness levels, converted to black and white image, the pixels which have only two values ​​— 0 and 1.

There are several types of thresholding:

Allocation algorithms allow edges define the boundaries of the elements in the image. The best known such algorithm is the edge detector Kenni (Canny edge detector) [6]

The main steps of the algorithm:

As a consequence of the fact that a group of these algorithms work with individual pixels, there is a lack of — may be found gaps in the borders, which requires some post-processing to correct inaccuracies.

Extraction algorithms operate on areas such as the notion of "region" or "area" and "seed" — was originally given pixel, from which subsequently grow area. Initially given a few centers ("seeds") regions of the image and further growth occurs in these regions due to the absorption of neighboring pixels. Such algorithms as input data centers require the regions to better segmentation. [13]

The method of expansion of areas from seed requires additional input. The result of the segmentation depends on the choice of seeds. Noise can cause the image that the seeds of ill-placed. The method of expansion of areas without the use of seeds — a modified algorithm which does not require explicit seeds. As a measure of proximity to the pixel intensity of pixels is used and the average intensity in the region δ.

The algorithm starts with one of A1 — pixel is selected here have little effect on the final segmentation. At each iteration the algorithm considers the neighboring pixels as well as a method of expansion of areas with the use of seeds. But the method of expansion of areas characterized by the fact that if the minimum δ is not less than the predetermined threshold T, then the pixel is added to the appropriate area Aj. Otherwise, the pixel is considered to be very different from all current areas Ai and created a new area of ​​An +1, containing this pixel.

Algorithm for the growth of regions [13] is also a typical representative of the algorithms using regions. After choosing the initial positions of the algorithm begins to search for neighboring pixels, the intensity of which lie in the intervals defined thresholds, and then combine them in order to expand the region.

In order to get rid of dependence on the initial values ​​and to automate the algorithm can be included in a certain statistical information and a priori values. For example, the criterion of homogeneity, which was proposed by Pohle Toennies [7], makes the algorithm adaptable to different values ​​of initial points.

The algorithm uses a square tree takes root as a whole image, and if it is not homogeneous, it is a process of partitioning the image into 4 areas — the child nodes of the root. For the sons of the same process is repeated. In turn, if the four sons are homogeneous, then they are merged (merge process) into a single node. The process is repeated recursively until as long as possible to perform splitting and merging. This master's work is not completed yet. Final completion: January 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. Blasiak Anna. A Comparison of Image Segmentation Methods. Электронный ресурс. Режим доступа http://dspace.nitle.org/bitstream/handle/10090/781/s10csci2007blasiak.pdf?sequence=1 свободный. – Загл. с экрана. – Яз. англ.
  2. Wassenberg Jan. Middelmann Wolfgang, Sanders Peter. An Efficient Parallel Algorithm for Graph-Based Image Segmentation. Электронный ресурс. Режим доступа http://algo2.iti.kit.edu/wassenberg/wassenberg09parallelSegmentation.pdf свободный. - Загл. с экрана. – Яз. англ.
  3. Pantofaru Caroline, Hebert Martial. A Comparison of Image Segmentation Algorithms. Режим доступа http://www.ri.cmu.edu/pub_files/pub4/pantofaru_caroline_2005_1/pantofaru_caroline_2005_1.pdf свободный. - Загл. с экрана. – Яз. англ.
  4. Zhen Ma, João Manuel R. S. Tavares, R. M. Natal Jorge. A review on the current segmentation algorighms for medical images. Режим доступа http://repositorio-aberto.up.pt/bitstream/10216/7125/2/17022.pdfhttp://repositorio-aberto.up.pt/bitstream/10216/7125/2/17022.pdf свободный. – Загл. с экрана. – Яз. англ.
  5. Поршнев С.В., Левашкина А. О. Универсальная классификация алгоритмов сегментации изображений. Электронный ресурс. Режим доступа http://jurnal.org/articles/2008/inf23.html свободный.
  6. Canny, J. A Computational Approach to Edge Detection. Ээлектронный ресурс. Режим доступа http://www.limsi.fr/Individu/vezien/PAPIERS_ACS/canny1986.pdf свободный. - Загл. с экрана. – Яз. англ.
  7. Pohle, R., Toennies, K. D. Segmentation of Medical Images Using Adaptive Region Growing. Электронный ресурс. Режим доступа http://wwwisg.cs.uni-magdeburg.de/bv/pub/pdf/mi_4322_153.pdf свободный. - Загл. с экрана. – Яз. англ.
  8. Alireza Khotanzad, Abdelmajid Bouarfa. Image segmentation by a perallel, non- parametric histogram based clustering algorithm. Электронный ресурс. Режим доступа http://www.cs.gsu.edu/~wkim/index_files/papers/imagesegmentation.pdf свободный. - Загл. с экрана. – Яз. англ.
  9. Brian Fulkerson, Stefano Soatto. Really quick shift: Image segmentation on a GPU. Электронный ресурс. Режим доступа http://www.vision.ucla.edu/papers/fulkersonS10really.pdf свободный. – Загл. с экрана. – Яз. англ.
  10. Nawal Copty , Sanjay Ranka , Geo rey Fox , Ravi V. Shankar. A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection Machine. Режим доступа http://www.new-npac.org/users/fox/pdftotal/sccs-0596.pdf свободный. – Загл. с экрана. – Яз. англ.
  11. Lucas Lattari, Anselmo Montenegro, Aura Conci, Esteban Cluaa, Virginia Mota, Marcelo Bernardes Vieirab, Gabriel Lizarragac. Using graph cuts in GPUs for color based human skin segmentation. Режим доступа http://pire.fiu.edu/publications/Graph_Cuts_2011.pdf свободный. – Загл. с экрана. – Яз. англ.
  12. Shahram Rahimi, M. Zargham, A. Thakre. A Parallel Fuzzy C-Mean algorithm for Image Segmentation. Режим доступа http://opensiuc.lib.siu.edu/cs_pubs/26/ свободный. – Загл. с экрана. – Яз. англ.
  13. Frank Y. Shih, Shouxian Cheng, Automatic seeded region growing for color image segmentation. Электронный ресурс. Режим доступа http://www.csd.uoc.gr/~hy471/papers/AutomaticSRGColor.pdf свободный. – Загл.с экрана. – Яз. англ.
  14. Депутат Е. В., Скобцов Ю. А, Сегментация медицинских изображений с помощью алгоритма муравьиных колоний., Информационные управляющие системы и компьютерный мониторинг 2010/ Сборник материалов к I Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых.- Донецк, ДонНТУ-2010, с.12-16.
  15. Савченко Д. А., Исследование методов сегментации изображений, Режим доступа http://masters.donntu.ru/2010/fknt/savchenko/diss/index.htm свободный. – Загл.с экрана.
  16. Чудовская А.К., Исследование возможностей распараллеливания алгоритмов выделения контуров объектов по технологии CUDA, Режим доступа http://masters.donntu.ru/2010/fknt/chudovskaja/diss/index.htm свободный. – Загл.с экрана.