Преобразование Хафа

Одним из наиболее эффективных методов поиска аналитически заданных примитивов является на сегодня группа методов, основанных на идее преобразования Хафа.

Основная идея преобразования Хафа сходна с идеей хорошо знакомого нам по курсу школьной геометрии метода "общих геометрических мест". Вспомним, например, задачу построения треугольника по трем его заданным сторонам. При этом вначале произвольным образом строится одна сторона треугольника, а затем проводятся две окружности с радиусами, равными длине соответственно второй и третьей сторон треугольника и центрами, совпадающими с концами первой построенной стороны. Эти окружности являются "геометрическим местом точек", в которых могли бы заканчиваться искомые стороны треугольника. Для всех точек левой окружности выполняется условие "расстояние от центра равно длине второй стороны". Для всех точек правой окружности выполняется условие "расстояние от центра равно длине третьей стороны". Там, где окружности пересекаются, выполняются оба условия - таким образом, это и есть искомая третья вершина треугольника - "общее геометрическое место" (рис. 1).

Обобщая эту методику геометрического построения, можно сказать, что было осуществлено "голосование" в пользу возможного положения вершины, при этом в голосовании участвовали две точки (концы первого отрезка), и в результате проведения процедуры голосования победила та точка, которая набрала максимум голосов (в данном случае, как мы видим, - два, в отличие от остальных точек плоскости, получивших ноль или один голос). При этом форма "голосующей кривой" для каждой точки определялась нашими априорными знаниями о геометрических характеристиках искомого объекта (в данном случае - заданными длинами сторон треугольника).

Решение задачи о построении окружности по трем заданным точкам методом общих геометрических мест (методом голосования)

Аналогичным образом решается еще одна известная школьная задача - о построении окружности по трем заданным точкам (рис. 2). В этом случае в качестве общих геометрических мест выступают серединные перпендикуляры к отрезкам, попарно соединяющим заданные точки. Заметим, что для решения задачи достаточно найти точку пересечения двух серединных перпендикуляров - третий строить уже не обязательно - он непременно пройдет через ту же точку, которая и является центром искомой окружности. Это происходит потому, что в школьных задачах на построение всегда дано ровно столько данных, сколько нужно для решения задачи, и эти данные всегда $\textit{совместимы,}$ то есть их голоса не могут противоречить друг другу.

Рассмотрим теперь, как эта идея может быть модифицирована для работы с реальными данными на изображениях, когда требуется найти тот или иной геометрический примитив, заданный аналитическим уравнением, и при этом на изображении имеется не две и не три, а значительное количество голосующих контурных или особых точек. На рис. 3 показано решение задачи обнаружения окружности известного радиуса в бинарном точечном множестве, в котором могут присутствовать и "ложные" точки (рис. 3 $\textit{а}$). Очевидно, что набор центров всех возможных окружностей радиуса $R$, проходящих через каждую конкретную точку, образует окружность радиуса $R$ вокруг этой точки. Таким образом, геометрическое место точек, которые могли бы быть центрами окружности данного размера, проходящей через эту точку, представляет собой окружность такого же размера с центром в голосующей точке. Наилучшее решение относительно положения центра "наиболее вероятной" присутствующей в данном точечном множестве окружности соответствует точке пересечения максимального числа голосующих окружностей (на рис. 3 $\textit{б}$ точка-"победитель голосования" помечена большим кружком, а соответствующая ей окружность - сплошным контуром). Заметим, что были в нашем примере и такие точки, чьи голоса (на рис. 3 $\textit{б}$ они помечены красным (см. цветную вклейку)) противоречили найденному в итоге решению. Но поскольку нас интересовал поиск одной наиболее вероятной окружности, голоса, поданные за менее популярные гипотезы, в итоге были проигнорированы. Чем больше отношение числа точек, лежащих на "главной" окружности, к общему числу точек, тем более достоверным и устойчивым будет полученное решение (здесь также можно говорить об отношении "сигнал/шум").

Таким образом, метод голосования действительно позволяет решать и "некорректные" с точки зрения школьной геометрии задачи анализа избыточных и противоречивых пространственных данных.

А что случится, если на изображении присутствует несколько фигур заданной формы (в рассматриваемом примере - несколько окружностей заданного радиуса)? Тогда у нас возникнет несколько кандидатов с достаточно большим количеством поданных голосов. Если в нашу задачу входит поиск и обнаружение всех таких объектов, то решение задачи будет представлять собой список из нескольких "победителей голосования", в чью пользу было подано достаточное количество голосов, чтобы они преодолели установленный барьер минимального "избирательного ценза" (порог на количество поданных голосов).

Итак, для того чтобы начать непосредственно использовать метод голосования в задачах компьютерного анализа изображений, нам осталось решить единственную серьезную проблему - как вычислительно (алгоритмически) организовать процесс порождения гипотез и сбора голосов в их пользу в случае, когда число точек на изображении может составлять десятки и сотни тысяч. И здесь мы, наконец, переходим собственно к преобразованию Хафа.

Подробнее

Литература для самостоятельного изучения

Лучшим русскоязычным описанием группы процедур сегментации изображений на основе моделей, к которым относится преобразование Хафа, следует признать описание, данное в книге ($\textit{Форсайт, Понс}$). В главе $15$ "Сегментация через подбор модели" описано преобразование Хафа (в данном переводе названное преобразованием Хоха), его различные модификации, а также дано описание процедур голосования как процедур вероятностного вывода (в нашей терминологии - $\textit{анализ свидетельств на изображениях}$, см. ниже).

Книга Дэвиса, к сожалению, не переведена на русский язык, однако в ней наиболее полно в англоязычной книжной литературе описано все богатство и разнообразие как методов, восходящих к преобразованию Хафа, так и их приложений в области машинного зрения.

Список источников к разделу

1. $\textit{Hough P. V. C.}$ Methods, Means for Recognizing Complex Patterns / U.S., Patent 3069654, 1962. [188]
2. $\textit{Svalbe I. D.}$ Natural representation for straight fines, the Hough transform on discrete

arrays\Dslash IEEE Trans. on Pattern Analysis\Dslash Machine Intelligence. V. II. No.~9. September, 1989. [286]

1. $\textit{Davies E. R.}$ A new parametrisation of the straight line, its application for the optimal detection

of objects with straight edges\Dslash Pattern Recogn. 1987. №~6. P.~9--14. [141]

1. $\textit{Ellis T. J., Abbood A., Brillault B.}$ Ellipse detection, matching with uncertainty\Dslash Image Vision

Comput. 1992. №~10(5). P.~271--276. [155]

1. $\textit{Yuen H. K., Illingworth J., Kittler J.}$ Ellipse detection using the Hough transform\Dslash Proc. 4th

Alvey Vision Conf. Manchester (31August-2 September). 1988. P.~167--174. [258]

1. $\textit{Ballard D. H.}$ Generalizing the Hough transform to detect arbitrary shapes\Dslash Pattern Recognition. 1981. 13(2). P.~111--122. [123]
2. $\textit{Davies E. R.}$ The performance of the generalised Hough transform: concavities, ambiguities, positional

accuracy\Dslash Proceedings of the 3$^{rd}$ Alvey Vision Conference. Cambridge, 15-17 September 1987. P.~327--333. [142]

1. $\textit{Zheltov S. Yu., Vizilter Yu. V.}$ Robust Computer Image Analysis fof Flight Vehicles Navigation\Dslash Guidance,

16th IFAC Symposium on Automatic Control in Aerospace. V.~2. St. Petersburg, 2004. P.~164--167. [287]

1. $\textit{Хуанг Т. С.}$ Обработка изображения и цифровая фильтрация. - М.: Мир, 1979. [47]
2. $\textit{Davies E. R.}$ A modified Hough scheme for general circle location\Dslash Pattern Recogn. 1988b. №~7. P.~34--37. [145]
3. $\textit{Davies E. R.}$ Application of the generalised Hough transform to corner detection\Dslash IEEE Proc. 1988a. E~135. P.~49--54. [144]
4. $\textit{Davies E. R.}$ Computationally efficient Hough transform for 2-D object location\Dslash Proc. 4th British Machine Vision

Assoc. Conf. Univ. of Surrey, 21--23 September, 1993. V.~1. P.~259--268. [148]

1. $\textit{Davies E. R. }$Corner detection using the generalised Hough transform\Dslash Proc. 2$^{nd}$ Int. Conf. on Image Processing,

Its Applications. IEEE Conf. Publ., 24-26 June, 1986. №~265. P.~175--179. [140]

1. $\textit{Davies E. R.}$ Improved localisation in a generalised Hough scheme for the detection of straight edges\Dslash Image Vision

Comput. 1987. №~5. P.~279--286. [143]

1. $\textit{Davies E. R.}$ Locating objects from their point features using an optimised Hough-like accumulation technique\Dslash Pattern Recogn.

1992. №~13(2). P.~113--121. [147]

1. $\textit{Davies E. R.}$ Machine Vision: Theory, Algorithms, Practicalities. - Academic Press., 2-nd Edition, San Diego, 1997. [146]
2. $\textit{Deans S. R.}$ Hough transform from the Radom transform\Dslash IEEE Trans. Pattern Anal. Mach. Intel. 1981. №~3. P.~185--188. [150]
3. $\textit{Duda R. O., Hart P. E.}$ Use of the Hough transformation to detect lines, curves in pictures\Dslash Comm. ACM 15. 11-15. 1972. P.~11--15 [154].
4. $\textit{Grimson W. E. L., Huttenlocher D. P.}$ On the sensitivity of the Hough transform for object recognition\Dslash IEEE Trans. Pattern

Anal. Mach. Intell. 1990. №~12(3). P.~255--274. [173]

1. $\textit{Illingworth J., Kittler J.}$ A survey of the Hough transform. Comput. Vision Graph. Image Process. 1988. V.~44. P.~87--116. [198]
2. $\textit{Illingworth J., Kittler J.}$ The adaptive Hough transform\Dslash IEEE Trans. Pattern Anal. Mach. Intell. 1987. V.~9. P.~690--698. [197]
3. $\textit{Kiryati N., Bruckstein A. M.}$ Antialiasing the Hough transform\Dslash Comput. Vision Graph. Image Process.: Graph. Models Image

Process. 1991. №~53. P.~213--222. [203]

1. $\textit{Li H., Lavin M. A.}$ Fast Hough transform based on bintree data structure\Dslash Proc. Conf. Comput. Vision, Pattern Recogn.,

Miami Beach, Florida, 1986. P.~640--642. [210]

1. $\textit{Lutton, Ma\^{\i}tre H., Lopez-Krahe J.}$ Contribution to the determination of vanishing points using Hough transform\Dslash IEEE

Trans. Pattern Anal. Mach. Intell. 1994. №~16(4). P.~430--438. [213]

1. $\textit{Silberberg T. M., Davis L., Harwood D.}$ An iterative Hough procedure for three-dimensional object recognition\Dslash Pattern

Recogn. Lett. 1984. №~17. P.~621--629. [244]

1. $\textit{Sklansky J.}$ On the Hough technique for curve detection\Dslash IEEE Trans. Comput. 1978. №~27. P.~923--926. [245]
2. $\textit{Stephens R. S. }$Probabilistic approach to the Hough transform\Dslash Image Vision Comput. 1991. №~9(1). P.~66--71. [248]
3. $\textit{Thomas Risse.}$ Hough Transform for line Recognition: Complexity of Evidence Accumulation, Cluster Detection. Computer Vision,

Graphics, Image Processing. 1989. №~46. P.~327--345. [250]

1. $\textit{V. F. Leavers, Boyce J. F.}$ The Radon transform, its application to shape parametrization in machine vision\Dslash Image Vision Comput.,

1987. №~5. [208]

1. $\textit{Xu, Oja E.}$ Randomized Hough transform (RHT): basic mechanisms, algorithms, computationnal complexities\Dslash Computer Vision Graph.

Image Process: Image Understanding. 1993. №~57. P.~131--154. [255]

1. $\textit{Yuen H. K., Illingworth J., Kittler J.}$ Ellipse detection using the Hough transform\Dslash Proc. 4th Alvey Vision Conf.,

Manchester, 31~August--2~September, 1988. P.~167--174. [258]