Участник:Artem.sevastopolsky/Преобразование Хаффа: различия между версиями

Версия 20:59, 19 ноября 2016

Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении
Последовательный алгоритм
Последовательная сложность	[math]O(NMK)[/math]
Объём входных данных	[math]O(NM)[/math]
Объём выходных данных	[math]O(K\sqrt{N^2 + M^2})[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(NMK)[/math]
Ширина ярусно-параллельной формы	[math]O(1)[/math]

Автор статьи: Севастопольский Артем

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Преобразование Хаффа — это преобразование бинарного изображения, которое позволяет эффективно найти его наиболее выраженные прямые линии. Метод переводит бинарное изображение в изображение в специальном пространстве (пространстве Хаффа), в котором каждая ячейка отвечает за определённую линию. Преобразование было предложено П. Хаффом (P. Hough) в 1962 г. с целью создания метода для регистрации следов быстрых заряженных ионизирующих частиц в пузырьковой камере, и, потенциально, для поиска произвольных сложных шаблонов на фотографии.^[1] В своём патенте П. Хафф предлагает электронную схему, реализация которой способна регистрировать следы пролетающих частиц, в то время как сам алгоритм в его современном описании был описан А. Розенфельдом (A. Rozenfeld) и другими математиками.^[2] Метод является одним из популярных и цитируемых методов в компьютерной графике.^[3]

Преобразование Хаффа используется в компьютерном зрении и цифровой обработке изображений для извлечения признаков из изображения. Алгоритм позволяет найти прямые линии, даже если разрывны, пересекаются другими прямыми, являются частями более сложных линий, или если прямой принадлежат точки из разных частей изображения. В силу низкой вычислительной сложности ([math]O(NMK)[/math], где [math]N, M[/math] — размеры изображения, [math]K[/math] — число уровней квантования наклона прямой), алгоритм является одним из эффективных методов поиска прямых линий, и более эффективен, чем перебор по всевозможным линиям.

За количество линий, которые считаются наиболее выраженными, отвечает значение специального порога, которое необходимо задать пользователю. Необходимость ручного подбора количества наиболее выраженных линий может считаться недостатком метода.

Метод имеет много модификаций, предназначенных для его ускорения или изменения его свойств. Одними из самых популярных модификаций алгоритма являются его варианты для поиска окружностей и эллипсов. Эти модификации обладают аналогичными свойствами и позволяют находить окружности и эллипсы, даже если на изображении они разрывны. Кроме того, возможен поиск более сложных аналитических кривых и кривых без параметризации (Generalized Hough Transform^[4]).

Вычислительное ядро алгоритма поиска прямых линий представляет собой один тройной вложенный цикл, из тела которого производятся обращения записи в общую память, поэтому метод успешно подвергается распараллеливанию. При поиске кривой, параметризуемой [math]m[/math] параметрами ([math]m=2[/math] для прямой линии, [math]m=3[/math] — для окружности, и т.д.), временная сложность повышается до [math]O(NMK^{m-1})[/math] (при условии, что число уровней квантования всех параметров, кроме одного, равно [math]K[/math]). Это представляет основную проблему применения метода на практике для сложных линий. Однако, т. к. вид алгоритма не меняется относительно алгоритма поиска прямых линий, модифицированный метод также допускает распараллеливание.

1.2 Математическое описание алгоритма

Пусть имеется бинарное изображение [math]I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}[/math] (интенсивность каждого пикселя равна либо нулю, либо единице). Преобразование Хаффа заключается в построении специального изображения — аккумулятора — по исходному изображению. Пространство, которому принадлежит аккумулятор, называют пространством Хаффа. Обозначим аккумулятор через [math]A(\rho, \theta), \rho \in \overline{0, K_{\rho} - 1}, j \in \overline{0, K_{\theta} - 1}[/math]. [math]K_{\rho}[/math] выбирают равным [math]2\sqrt{N^2 + M^2}[/math] для простоты реализации и наибольшей точности (тем не менее, можно переписать алгоритм так, чтобы [math]K_{\rho}[/math] было произвольным, возможно, не зависящим от [math]N, M[/math]). [math]K_{\theta}[/math] выбирают произвольной константой, но наиболее естественным является выбор math>K_{\theta}</math> (по одному уровню квантованию на каждый градус угла).

Каждый элемент аккумулятора отвечает определённой прямой линии: элемент [math]A(\rho + \sqrt{N^2 + M^2}, \theta)[/math] соответствует прямой, имеющей уравнение [math]x\cos\theta + y\sin\theta = \rho.[/math] В таком уравнении прямой [math]\rho[/math] имеет смысл длины перпендикуляра (со знаком) к прямой от начала координат, [math]\theta[/math] — угла между перпендикуляром и горизонтальной осью. Любая линия, проходящая через точки изображения, имеет единственную такую параметризацию.

Алгоритм преобразования изображения в пространство Хаффа имеет следующий вид:^[5]

   А[i][j] := 0 для всех i, j;
   для каждого t от 0 до [math]K_{\theta}[/math] - 1
       для каждого i от 0 до [math]N[/math] - 1
           [math]\theta_t = -\frac{\pi}{2} + \frac{\pi \cdot i}{K_\rho}[/math]
           для каждого j от 0 до [math]M[/math] - 1
               если I[i][j] равно 0,
                   [math]\rho_t = round(j \cdot \cos\theta_t + i \cdot \sin\theta_t + \sqrt{N^2 + M^2})[/math], где [math]round(x)[/math] — функция округления числа [math]x[/math]
                   A[[math]\rho_t[/math]][t] += 1

После проведения указанных действий в массиве А содержится аккумулятор для изображения I. Для того чтобы получить наиболее выраженные прямые по данным из аккумулятора, необходимо взять [math]T[/math] максимальных значений элементов аккумулятора и сопоставить им их прямые линии. Параметр метода [math]T[/math] необходимо либо подобрать вручную, либо выбрать на основе значений аккумулятора.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

↑ P. V. C. Hough, "Method and Means for Recognizing Complex Patterns", US Patent 3,069,654, Ser. No. 17,7156 Claims, 1962.
↑ Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).
↑ Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).
↑ Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015
↑ Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015

[1] P. V. C. Hough, "Method and Means for Recognizing Complex Patterns", US Patent 3,069,654, Ser. No. 17,7156 Claims, 1962.

[2] Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).

[3] Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).

[4] Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015

[5] Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015

[1]

[2]

[3]

[4]

[5]

@@ Строка 16: / Строка 16: @@
 Преобразование Хаффа используется в компьютерном зрении и цифровой обработке изображений для извлечения признаков из изображения. Алгоритм позволяет найти прямые линии, даже если разрывны, пересекаются другими прямыми, являются частями более сложных линий, или если прямой принадлежат точки из разных частей изображения. В силу низкой вычислительной сложности (<math>O(NMK)</math>, где <math>N, M</math> &mdash; размеры изображения, <math>K</math> &mdash; число уровней квантования наклона прямой), алгоритм является одним из эффективных методов поиска прямых линий, и более эффективен, чем перебор по всевозможным линиям.
-Также известно, что метод не является устойчивым к шуму на изображении. Кроме того, за количество линий, которые считаются наиболее выраженными, отвечает значение специального порога, которое необходимо задать пользователю. Необходимость ручного подбора количества наиболее выраженных линий может считаться недостатком метода.
+За количество линий, которые считаются наиболее выраженными, отвечает значение специального порога, которое необходимо задать пользователю. Необходимость ручного подбора количества наиболее выраженных линий может считаться недостатком метода.
 Метод имеет много модификаций, предназначенных для его ускорения или изменения его свойств. Одними из самых популярных модификаций алгоритма являются его варианты для поиска окружностей и эллипсов. Эти модификации обладают аналогичными свойствами и позволяют находить окружности и эллипсы, даже если на изображении они разрывны. Кроме того, возможен поиск более сложных аналитических кривых и кривых без параметризации (''Generalized Hough Transform''<ref>Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015</ref>).
-Вычислительное ядро алгоритма представляет собой один тройной вложенный цикл, из тела которого производятся обращения записи в общую память, поэтому метод успешно подвергается распараллеливанию. При поиске кривой, параметризуемой <math>m</math> параметрами (<math>m=2</math> для прямой линии, <math>m=3</math> &mdash; для окружности, и т.д.), временная сложность повышается до <math>O(NMK^{m-1})</math> (при условии, что число уровней квантования всех параметров, кроме одного, равно <math>K</math>). Это представляет основную проблему применения метода на практике для сложных линий. Однако, т. к. вид алгоритма не меняется относительно алгоритма поиска прямых линий, модифицированный метод также допускает распараллеливание.
+Вычислительное ядро алгоритма поиска прямых линий представляет собой один тройной вложенный цикл, из тела которого производятся обращения записи в общую память, поэтому метод успешно подвергается распараллеливанию. При поиске кривой, параметризуемой <math>m</math> параметрами (<math>m=2</math> для прямой линии, <math>m=3</math> &mdash; для окружности, и т.д.), временная сложность повышается до <math>O(NMK^{m-1})</math> (при условии, что число уровней квантования всех параметров, кроме одного, равно <math>K</math>). Это представляет основную проблему применения метода на практике для сложных линий. Однако, т. к. вид алгоритма не меняется относительно алгоритма поиска прямых линий, модифицированный метод также допускает распараллеливание.
 === Математическое описание алгоритма ===
-Алгоритм имеет следующий вид:<ref>Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015</ref>
+Пусть имеется бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math> (интенсивность каждого пикселя равна либо нулю, либо единице). Преобразование Хаффа заключается в построении специального изображения &mdash; ''аккумулятора'' &mdash; по исходному изображению. Пространство, которому принадлежит аккумулятор, называют ''пространством Хаффа''. Обозначим аккумулятор через <math>A(\rho, \theta), \rho \in \overline{0, K_{\rho} - 1}, j \in \overline{0, K_{\theta} - 1}</math>. <math>K_{\rho}</math> выбирают равным <math>2\sqrt{N^2 + M^2}</math> для простоты реализации и наибольшей точности (тем не менее, можно переписать алгоритм так, чтобы <math>K_{\rho}</math> было произвольным, возможно, не зависящим от <math>N, M</math>). <math>K_{\theta}</math> выбирают произвольной константой, но наиболее естественным является выбор math>K_{\theta}</math> (по одному уровню квантованию на каждый градус угла).
+Каждый элемент аккумулятора отвечает определённой прямой линии: элемент <math>A(\rho + \sqrt{N^2 + M^2}, \theta)</math> соответствует прямой, имеющей уравнение <math>x\cos\theta + y\sin\theta = \rho.</math> В таком уравнении прямой <math>\rho</math> имеет смысл длины перпендикуляра (со знаком) к прямой от начала координат, <math>\theta</math> &mdash; угла между перпендикуляром и горизонтальной осью. Любая линия, проходящая через точки изображения, имеет единственную такую параметризацию.
+Алгоритм преобразования изображения в пространство Хаффа имеет следующий вид:<ref>Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015</ref>
+    А[i][j] := 0 для всех i, j;
+    для каждого t от 0 до <math>K_{\theta}</math> - 1
+        для каждого i от 0 до <math>N</math> - 1
+            <math>\theta_t = -\frac{\pi}{2} + \frac{\pi \cdot i}{K_\rho}</math>
+            для каждого j от 0 до <math>M</math> - 1
+                если I[i][j] равно 0,
+                    <math>\rho_t = round(j \cdot \cos\theta_t + i \cdot \sin\theta_t + \sqrt{N^2 + M^2})</math>, где <math>round(x)</math> &mdash; функция округления числа <math>x</math>
+                    A[<math>\rho_t</math>][t] += 1
+После проведения указанных действий в массиве А содержится аккумулятор для изображения I. Для того чтобы получить наиболее выраженные прямые по данным из аккумулятора, необходимо взять <math>T</math> максимальных значений элементов аккумулятора и сопоставить им их прямые линии. Параметр метода <math>T</math> необходимо либо подобрать вручную, либо выбрать на основе значений аккумулятора.
 === Вычислительное ядро алгоритма ===