Investigation of edge detection algorithms parallelizing by CUDA technology

Abstract

Introduction

Actuality of the subject

Scientific novelty

Expected results

Solution of the problem and the results of studies

Conclusions

Introduction

Contour analysis is a set of methods for counturs isolation, description and transformation in the image. It is an important stage of image processing and recognition of visual images. The contour determines the whole shape of the image and contains all the necessary information for image recognition by their shape. This approach allow to don’t consider the internal points of the image and thus reduce the amount of processed information. It can provide the work of the recognition system in real time. Also, this approach will reduce the amount of memory in the recognition system.^[1]

Problems arise in the analysis of technical vision systems for image processing and recognition of visual images. One of the objectives of contour analysis is the allocation of the contours of the image. Dedicated boundary objects are then used to automatically find and recognize objects presented in the image. The main consumers of edge detection algorithms are real-time systems. The most popular representatives of these systems are automatic control of product quality, as well as tracking system for compliance with traffic regulations. Such systems must accurately and, most importantly, quickly highlight the contours of objects in the image, and then categorize them and analyze or compare with the pattern. To achieve the required speed is proposed to use hardware and software CUDA platform.

Actuality of the subject

The actuality of edge detection is caused by the fact that this is the initial stage of pattern recognition. In turn, the task of pattern recognition is solved in such areas as machine vision systems, applicable for text recognition, identifying defects in manufactured products, recognition of faces, detect accidents, driving, etc. All these areas are now in widespread use, but in the serial realization do not give adequate performance. Therefore, parallelization, which must give acceleration, is no less important piece of work.

It should be noted that on the issue of contours allocation are also working scientists from different countries. For example, a professor at the University of South Florida Sudep Sarkar, professor and chairman of the Department of Science and Computer Engineering Kevin Bauer (University of Notre Dame), Ph.D., head of laboratory automation systems of Dreksel Pauli.

Scientific novelty

Alleged scientific novelty comes from the basic shortcoming of all existing algorithms — namely, a relatively low speed for use in real-time systems. Achieving the acceleration is possible due to modifications of existing algorithms and its parallelization on CUDA technology. Since this is a fairly new, only developing technology, yet there is no edge detection algorithms implemented on it. Modification of the algorithm will also provide a scientific novelty. The rationale for modifications is that not every algorithm can efficiently parallelize.

Expected results

The planned result will be a software implementation of a modified algorithm that can efficiently and quickly determine the contours of the images. The basic condition for the proposed program will be the availability of CUDA technology by nVidia company (chips GeForce 6 series and above)^[6] on your PC, that will be used to run the program.

Solution of the problem and the results of studies

The most logical choice of edge detection algorithm is a neural network algorithm, since the neurons in a single layer neural networks operate independently of each other and are ideal candidates for presentation to the independent scalar processors.

To implement procedures of edge detection using neural network was adopted by the following model. To the input of the neural network is fed the image observation window size m Х n. This image meets the following requirements:

1. The image always contains an element of the contour, ie, in any view the image contains the boundary brightness differential between the object and background.
2. The image has only one contour, that is not provided, that the algorithm can process multiple contours.
3. The picture may has additive Gaussian noise, which prevents the proper working of the algorithm.

The output is necessary to obtain the basic parameters of a straight line approximates the brightness border: u  — background intensity, u + h — object intensity, d — distance from the center of the window to line, φ  — angle of line. These options are shown in fig. 1.

Figure 1 — The border object / background in elementary window

 

To implement this model was chosen neural network-type multi-layered perceptron, since the problem is clearly statistical in nature. The network contains two layers. The first layer consists of 10 neurons, the second of 4.^[3] All artificial neurons used logistic activation function. The network architecture is shown in fid. 2.

Figure 2 — Neural network

 

We should pay particular attention to the first requirement for the window image. Since the window, served on a neural network must necessarily contain a portion of the border, and in fact only one (requirement 2), it must be some way to find these windows. One solution to this problem is to find a pre-contour by more faster and rough method. Then, the obtained approximation of the contour is divided into sections, which are specified in the neural network. In addition, a separate task is to gather scattered land contours in a continuous contour. To solve this problem can be, for example, finding the middle point between two extreme points of approximating straight line in two adjacent windows.^[4] The process of finding boundaries is schematically shown in figure 3.

Figure 3 — The process of finding the image boundaries
Animations created in the Adobe PhotoShop CS2; consists of 6 frames, 1s delay between frames, the number of cycles is limited to playing 10; the size of animation - 27 kb, 250x250 pixels

 

As an algorithm for determining the contours of pre-selected a combination of several stages of the algorithm Canny:

Step 1. The first step is to filter out any noise in the original image before trying to locate and detect any edges. And because the Gaussian filter can be computed using a simple mask, it is used exclusively in the Canny algorithm. Once a suitable mask has been calculated, the Gaussian smoothing can be performed using standard convolution methods. A convolution mask is usually much smaller than the actual image. As a result, the mask is slid over the image, manipulating a square of pixels at a time. The larger the width of the Gaussian mask, the lower is the detector's sensitivity to noise. The localization error in the detected edges also increases slightly as the Gaussian width is increased.^[5]

Step 2. After smoothing the image and eliminating the noise, the next step is to find the edge strength by taking the gradient of the image. The Sobel operator performs a 2-D spatial gradient measurement on an image. Then, the approximate absolute gradient magnitude (edge strength) at each point can be found. The Sobel operator uses a pair of 3x3 convolution masks, one estimating the gradient in the x-direction (columns) and the other estimating the gradient in the y-direction (rows).

The magnitude, or edge strength, of the gradient is then approximated using the formula: |G| = |Gx| + |Gy|

Step 3. Hysteresis is used as a means of eliminating streaking. Streaking is the breaking up of an edge contour caused by the operator output fluctuating above and below the threshold. If a single threshold, T1 is applied to an image, and an edge has an average strength equal to T1, then due to noise, there will be instances where the edge dips below the threshold. Equally it will also extend above the threshold making an edge look like a dashed line. To avoid this, hysteresis uses 2 thresholds, a high and a low. Any pixel in the image that has a value greater than T1 is presumed to be an edge pixel, and is marked as such immediately. Then, any pixels that are connected to this edge pixel and that have a value greater than T2 are also selected as edge pixels. If you think of following an edge, you need a gradient of T2 to start but you don't stop till you hit a gradient below T1.^[2]

This algorithm can also be parallelized for the calculation on software and hardware complex CUDA by dividing the image into sections and the calculation of these sites on different processors.

As a result, the entire image is divided into the window size m X n, suitable for processing by neural network, but processed shall be only those that contain exactly one part of the contour.

Conclusions

Existing sequential algorithms for edge detection in images is not fast enough for use in real-time systems. This was considered a possible way of improving the algorithm and optimization for parallelizing its technology CUDA. In the future is planned implementing of algorithms and a comparison with the already existing to determine the effectiveness of the proposed improvements.

References

1. Фурман Я.А., Юрьев А.Н., Яншин В.В. Цифровые методы обработки и распознавания бинарных изображений. — Красноярск, 1992. — 248с. http://www.4tivo.com/education/2329-cifrovye-metody-obrabotki-i.html^[↑]
2. Green B. Canny Edge Detection Tutoria // Drexel Autonomous Systems Lab., 2002. — http://www.pages.drexel.edu/~weg22/can_tut.html ^[↑]
3. Сирота А.А., Соломатин А.И. Статистические алгоритмы обнаружения границ объектов на изображениях. — Воронеж: Вестник ВГУ, № 1, 2008. — www.vestnik.vsu.ru/.../sirota_2.pdf^[↑]
4. Чудовская А.К. Возможности распараллеливания алгоритмов выделения контура по технологии CUDA // Искусственный интеллект.— Донецк: ІПШІ МОН і НАН України “Наука і освіта”, 2010.
5. Прэтт У. Цифровая обработка изображений, том 2 — Москва: Мир, 1982 — 478с.
6. Лосев С. Перспективы параллельных вычислений на GPU от Nvidia — Hard’n’Soft, №6 — 2009. — www.nvidia.eu/cuda/files/HardnSoft_026_027_trends_Cuda.pdf

The abstract of the Master's work is not complete yet . The final completion in 1st December 2010. Full text of the work and materials on the topic can be obtained from the author or his head after that date.

Biography

Abstract