DonNTU   Masters' portal

Abstract

Сontent

Introduction

Every day, the progress and development of modern science and technology brings a new contribution to the life and development of society. On the land there are few people who do not use modern electronic computing devices in their lives. Almost impossible to imagine the lives of most people and sectors of the economy without such things familiar to us as a personal computer, mobile phone and other things.

In connection with this situation the amount of information on the ground increases very rapidly and this process can not be stopped in this regard. Modern man is not able to learn and process all the information stored in the modern world. And almost all of this information is stored in digital form on various storage devices in different parts of the world. This makes it easy to access it using any electronic device capable of operating this type of file and facilitate copying and dissemination of information, an example using the global Internet.

In connection with the growth of information and inability to process it all manually will appear the idea of automatic processing with electronic computing devices. One of the most popular data formats are the digital images. One of the most complex operations in image processing – search and selection on it desired object. These methods are particularly relevant nowadays, when they are actively used not only in mapping and photographs, but also in many automating real-time systems, where critical accuracy and reliability.

In this paper we consider the Hough transform method which can find various geometric shapes, and also objects of arbitrary shape in the image and even in 3D space. This method is capable of great accuracy finding parameters that are represent the desired objects in the binary image. After finding these parameters, we can easily recover the desired object. Considered in detail special cases of this transformation and the implementation of algorithms to search for lines, circles and ellipses in the image.

1 Theme urgency

The automated data processing task arose for humanity since the appearance of most data. But only with the advent of digital storage formats, this process has moved forward significantly. Still in the 60s of the XX century [7] Hough proposed transform, which allows to translate the coordinates of points the two-dimensional space in the data accumulator array with the further using the voting procedure. And although at the time digital storage format was not very common, however, this transformation is very interested in the scientific community. Subsequently, various scientists have proposed variants of this transformation, not only for finding the line, but also circles, ellipses and even arbitrary shape objects [12].

Over time, the spread of digital image formats give even greater impetus to the development of automated image processing. And the Hough transform began to use more often. There are a lot of modifications to accelerate the algorithm and made it fast enough. This allowed apply it in real systems of object recognition [14] and even in real-time systems. Also, the positive moments in the development of this trend began playing the fact that every year the computing power of modern computers increases, which also helps to speed up the process of finding objects in the image.

Already Hough transform can be applied in such areas as detection of buildings border in images [11], the definition of the horizon line in the image [9], finding the lines of road markings, determining the number of axles in a moving vehicle, and other areas.

Thus, research in this area in order to study this transformation, its application and search methods of its optimization are very relevant.

2 Goal and tasks of the research

Research object is the task of automated search of various objects in the image.

Research subject – methods for finding the parametric and nonparametric objects in the image that allow in the subsequent restore of these objects in the original image.

The purpose of the final Master's research is to study of the existing methods of parametric and nonparametric find objects in the image.

In the process will need to solve the following tasks.

  1. The research of existing methods for finding objects in the image and the selection from these the most productive and popular.
  2. Detailed consideration of particular cases of these methods to detect various types of objects.
  3. Creation of optimized methods to speed up the basic algorithm for finding the object.
  4. The program realization the basic methods and optimized to compare their speed of execution and performance recognition.

3 Analysis of the Hough transform for a task finding two-dimensional geometric primitives in the image

Hough transform – a method for extracting elements from the images used in image processing and computer vision. The method is designed for search parametric and nonparametric objects using a voting procedure [7]. Apply the voting procedure and fill accumulator array we find there maximum, and by coordinates of this maximum will be able to recover the parameters of the object and, therefore, the object.

The classical Hough transform is linear and used to detect а straight lines. The straight line defined by the equation y=mx+b, and can be calculated for any pair of active pixels in the image (x,y). The main idea of Hough transform – consider the characteristics of the line in terms of its parameters, m and b. Thus, the parameter space for lines will be two-dimensional and consists of two parameters – the angle of slope m and the point of intersection with the axis OY, b. But for this type of equation has a problem set of vertical lines, because in this case we get infinite values of the parameters m and b. If we present a straight line through the parameters of the vector perpendicular to the line and passing through the origin, then this problem will disappear. We define a straight line through the two parameters R and θ. R is the length of this vector, and θ – the angle of the vector to the coordinate axis.

In this case, the equation of the line will be represented in this form:

Or it can be transformed into the following form: r = x*cosθ+y*sinθ.

Thus, each line of the image can be represented by two parameters of the normal vector – r and θ. These settings will be unique under the condition θЄ[0,PI] and rЄR or θЄ[0,2PI] and r>=0. Create accumulator array with a certain step and put them a given parameter values. This array is also called Hough space for lines in the plane or simply an accumulation space.

Through one point may pass an infinite number of straight lines. If this point has the coordinates (x0,y0), then all the straight lines passing through it will have the following equation:

Where r and θ can be arbitrary values in the aforementioned range.

This corresponds to a sinusoidal curve in the storage space (r,θ), which is unique to each individual point. Sinusoids several points overlap each other. The point of their intersection in the parameter space of lines define the line parameters (r,θ). This line passes through points that define the sine waves. The problem of finding a straight line, ultimately, reduced to the problem of finding the maximum in the storage parameter space.

Conclusion

In this paper we have analyzed search methods of two-dimensional geometric primitives in the image. A result of work was studied literature and Internet sources, which described these methods. The most simple, but effective method was the method of Hough transform. This method can be applied successfully to detect geometrical objects in the image – lines, circles, ellipses, as well as non-parametric objects. In the analyzed sources were studied cases of this transformation for all of these types of geometric objects.

Most simple in realization and fast in work was a special case of this method for finding lines in the image. In this case, the accumulative Hough space is two dimensional, because any line can be specified by two parameters of the equation. A more difficult and slow in the work was Hough transform to find the circles. It is because accumulative space has become a three-dimensional and the search time increased significantly. The most difficult and slow was the Hough transform for search ellipses. In the general case parameter space will be a five-dimensional and in this case the algorithm is inefficient. Therefore, for its effective use must optimize the input data and the algorithm for each particular case of its application.

Thus, the Hough transform with a certain optimization algorithm can be successfully applied not only for search lines in the image, but also circles, ellipses, and even objects of arbitrary shape defined by a cloud of points.

References

  1. The Hough Transform [Electronic resource]. – Access mode : http://homepages.inf.ed.ac.uk/rbf/CVonline....
  2. Samuel A. Inverso. Computer Vision: Ellipse Detection Using Randomized Hough Transform [Electronic resource]. – Access mode : http://www.saminverso.com/res/vision/.
  3. James Matthews. Hough Transforms [Electronic resource]. – Access mode : http://www.generation5.org/content/2008....
  4. Алгоритм Хафа для обнаружения произвольных кривых на изображениях [Electronic resource]. – Access mode : http://habrahabr.ru/blogs/algorithm/102948/.
  5. Использование преобразований Хафа (Hough transform) для выделения прямых на изображении [Electronic resource]. – Access mode : http://eddy-em.livejournal.com/932.html.
  6. Дегтярева A. Преобразование Хафа [Electronic resource]. – Access mode : http://www.cgm.computergraphics.ru/content/view/36.
  7. Преобразование Хафа [Electronic resource]. – Access mode : http://ru.wikipedia.org/wiki....
  8. OpenCV шаг за шагом. Преобразование Хафа [Electronic resource]. – Access mode : http://robocraft.ru/blog/computervision....
  9. Коррекция наклона (skew correction) [Electronic resource]. – Access mode : http://bik-top.livejournal.com/37060.html.
  10. Преобразования Хафа [Electronic resource]. – Access mode : http://locv.ru/wiki....
  11. Arefi H. Levels of detail in 3D building reconstruction from lidar data / [H. Arefi, J. Engels, M. Hahn, H. Mayer.]. – Stuttgart : Stuttgart University of Applied Sciences; Munich : Bundeswehr University Munich, 2008. – 490 p.
  12. Ballard D. H. Generalizing the Hough transform to detect arbitrary shapes / Ballard D. H. – New York : Computer Science Department, University of Rochester, 1980 – 122 p.
  13. Запрягаев С. А. Программная оболочка для поиска примитивов на изображении / С. А. Запрягаев, А. И. Сорокин // Вестник ВГУ, серия: системный анализ и информационные технологии. – Воронеж, 2008. – № 2. – С. 37-47.
  14. Сай И. С. Эффективность алгоритмов поиска оттиска печати в изображении документа / Сай И. С. // Вестник ТОГУ. – 2009. – № 4. – C. 53-60.
  15. Семенов А.Б. Обработка и анализ изображений с использованием языка JAVA, курс лекций / Семенов А.Б. – Тверь : Тверской государственный университет, 2007. – 10 c.

Important note

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