Компьютерная Графика и Мультимедиа Сетевой журнал

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

Содержание 

1. Введение.
2. Основная идея.
3. Базовый алгоритм.
4. Проблемы метода.
5. Модификации метода.
1. Комбинаторное преобразование Хафа (Combinatorial Hough Transform)
2. Иерархическое преобразование Хафа (Hierarchical Hough Transform)
3. Адаптивное преобразование Хафа (Adaptive Hough Transform)
4. Вероятностное преобразование Хафа (Probabilistic Hough Transform)
5. Постепенное вероятностное преобразование Хафа (Progressive Probabilistic Hough Transform)
6. Случайное преобразование Хафа (Randomized Hough Transform)
6. Методы поиска пиков в аккумуляторе.
1. "Размытие" аккумулятора.
2. Алгоритм сходящихся квадратов (The Converging Squares Algorithm)
3. Сдвиг центра масс (Mean Shift)
7. Литература.

Введение

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

Основная идея

Пусть дано облако точек в пространстве R^m:

X = {x₁, : , x_n}

и семейство параметрически заданных кривых:

F(φ, x) = 0

где F - некоторая функция, φ - вектор параметров семейства кривых, x - координаты точек из R^m. Каждое значение φ определяет одну кривую, а все множество значений φ образует фазовое пространство Φ кривых данного семейства.

В силу конечного объема памяти и дискретного машинного представления мы не можем рассматривать каждое значение φ в отдельности, поэтому фазовое пространство Φ разбивается на ячейки, для чего вводится регулярная сетка с заданным шагом дискретизации. Каждой ячейке ставится в соответствие счетчик. Набор всех счетчиков называется аккумулятором. Любая ячейка задаёт множество кривых, а значение счетчика ячейки определяется количеством точек из облака X, лежащих хотя бы на одной из этих кривых. Тогда если все точки из X лежали на одной кривой с параметром φ₀, то в соответствующей ячейке значение счетчика будет максимально.[1]

Базовый алгоритм

Базовый алгоритм выделения кривых состоит из следующих шагов:

1. Выбор сетки дискретизации

На этом этапе предстоит выбрать шаг дискретизации для каждого параметра кривой. От этого выбора будет зависеть сложность (~ скорость) и эффективность алгоритма.

2. Заполнение аккумулятора (матрицы счетчиков)

Зачастую это самый долгий шаг алгоритма, поскольку заполнение производится путем полного перебора. Сложность алгоритма напрямую зависит от первого шага и составляет O(N*M), где N - кол-во точек, M - кол-во ячеек аккумулятора.

3. Анализ аккумулятора (поиск пиков)

В матрице аккумулятора ищется счетчик с максимальным значением.

4. Выделение кривой

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

5. Вычитание из аккумулятора

Для точек выделенной кривой считается временный аккумулятор и поточечно вычитается из основного.

6. Переход на шаг 3

Проблемы метода

• Дискретизация

На шаге 1 мы выбираем сетку дискретизации. В связи с этим выбором возможны следующие проблемы:

-       Сетка выбрана слишком мелкой. Тогда, если в исходном облаке точек присутствовал шум, то даже точки одной кривой будут попадать в разные ячейки сетки, а значит, потенциальный максимум аккумулятора (соответствующий этой кривой) будет <размыт> и его будет сложнее или вообще невозможно найти.

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

-       При любой сетке дискретизации, если точки облака X образуют кривую с параметром φ₀, лежащим на границе ячейки, то из-за шума точки этой кривой будут попадать в соседние ячейки и будет наблюдаться размытие пика в аккумуляторе. Это вообще фундаментальная проблема дискретизации.

• Сложность алгоритма

Заполнение аккумулятора на шаге 2 является самой трудоёмкой частью алгоритма, сложность которой зависит от: размерности фазового пространства и сетки дискретизации. Чем больше размерность Φ и меньше сетка, тем больше ячеек в аккумуляторе. Значит, тем больше требуется памяти и времени для его хранения и заполнения. Именно поэтому на практике чаще всего фазовое пространство представляет собой плоскость, а преобразование Хафа применяется в основном для поиска прямых на плоскости (изображениях).

Модификации метода

В связи с вышеперечисленными проблемами были разработаны некоторые модификации стандартного алгоритма (Standard Hough Transform, SHT).

Комбинаторное преобразование Хафа (Combinatorial Hough Transform)

Эта модификация разрабатывалась для быстрого поиска прямых линий на изображении [4]. В таком случае у нас имеется плоское бинарное изображение (на нём точки интереса одного цвета, а точки фона другого). Поскольку производится поиск прямых линий, то размерность фазового пространства равна 2.

Идея метода состоит в изменении шага 2(заполнение аккумулятора):

1. Исходное бинарное изображение разбивается на небольшие участки
2. В каждом участке для каждой пары точек определяются параметры (ρ,θ) прямой, проходящей через них
3. (ρ,θ) попадают в некоторую ячейку, и её счетчик соответственно увеличивается.

Первый шаг модификации необходим для сокращения числа переборов.

Если точек в участке мало и сетка дискретизации фазового пространства тоже мала, количество записей в аккумуляторе получается меньше.

Иерархическое преобразование Хафа (Hierarchical Hough Transform)

Это еще одна модификации для поиска линий на бинарном изображении [1, 4, 7].

Идея метода:

1. Исходное изображение разбивается регулярной сеткой
2. В каждом фрагменте изображения выделяются прямые преобразованием Хафа
3. Производится иерархическое слияние

На каждом уровне рассматриваются 4 соседних фрагмента. Линии, выделенные на каждом из фрагментов, объединяются на основании преобразования Хафа для объединения фрагментов. Если линии не удалось слиться ни с одной линией из соседних фрагментов, она удаляется из рассмотрения.

4. Слияние производится до получения одного исходного изображения

В результате сложность алгоритма снижается за счет подразбиения изображения (можно использовать более грубую сетку в фазовом пространстве и количество точек существенно меньше).

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

Адаптивное преобразование Хафа (Adaptive Hough Transform)

Эта модификация позволяет использовать меньше места для хранения аккумулятора и быстрее выделять кривые. На протяжении всего процесса поиска используется аккумулятор заранее выбранного маленького размера (например, 9х9 или 3х3х3х3 в многомерном случае) [2, 3, 4, 7].

Алгоритм выглядит следующим образом:

1. Выбор размера аккумулятора (маленький!)
2. До достижения заданной точности:

На каждой итерации размер ячейки уменьшается. Цикл идет до достижения заранее заданного размера ячейки.

3. Заполнение аккумулятора

Как и в стандартном варианте, но значительно меньше сложность за счет маленького размера аккумулятора.

4. Поиск ячейки с максимальным значением счетчика
5. Ячейка принимается за новое фазовое пространство, переход на шаг 2

Таким образом, мы уменьшаем шаг дискретизации, но только в области интереса (ячейке с максимальным счетчиком).

6. Выделяем кривую

Главными достоинствами являются:

-      меньшая сложность по времени и по памяти

-      практическое решение проблемы дискретизации, поскольку сетка дискретизации не регулярная и на каждой итерации уточняется.

Главный недостаток:

Если исходное облако точек X образует несколько кривых из заданного семейства, то для выделения каждой необходимо повторить весь алгоритм сначала (предварительно выкинув из рассмотрения точки уже выделенных кривых)

Вероятностное преобразование Хафа (Probabilistic Hough Transform)

В этой [1, 4, 5, 6, 7] модификации алгоритма рассматривается только доля α точек из X, при этом результат с некоторой вероятностью получается такой же, как и у стандартного алгоритма. Доля точек выбирается случайно с равномерной вероятностью.

Показано, что существует α_threshold такое, что при α > α_threshold ошибок (относительно стандартного алгоритма) происходит очень мало, а при α < α_threshold их количество резко возрастает. По этому рекомендуется выбирать α примерно равное α_threshold, которое находится в диапазоне 5% - 15% от всего количества точек.

Очевидное достоинство модификации заключается в сокращении перебора на шаге 2.

И так же очевиден недостаток - недетерменированность результата относительно входных данных.

Прогрессивное вероятностное преобразование Хафа (Progressive Probabilistic Hough Transform)

Пусть имеется облако точек X и большое количество точек образуют искомую кривую. Тогда в соответствующей ячейке фазового пространства значение счетчика будет иметь большое значение. Идея этой модификации заключается в том, что бы выделять кривые (шаг 4) при достижении счетчиком порогового значения, не заполняя аккумулятор полностью (шаг 2) [5]. Для вышеописанной кривой значение соответствующего счетчика довольно быстро наберет пороговое значение.

Алгоритм формулируется следующим образом:

1. Если в облаке нет точек, окончание
2. Аккумулятор пополняется случайно выбранной точкой из X, а точка удаляется из рассмотрения.
3. Если максимальное значение аккумулятора не превосходит порога, переход на шаг 1
4. Находится кривая максимальной длинны

Внутри некоторого коридора (определяемого ячейкой с максимальным значением счетчика) производится поиск кривой с максимальной длинной.

5. Все точки найденной кривой удаляются с исходного изображения и аккумулятора
6. переход на шаг 1

Достоинством этого метода так же является то, что он постоянно пополняет результат, т.е. его выполнение можно оборвать при достижении остаточного количества результатов или по истечении некоторого времени.

Случайное преобразование Хафа (Randomized Hough Transform)

Эта модификация своей идеей схожа с идеей Комбинаторного преобразования Хафа [1, 4, 6, 7]. Если параметры φ кривой F(φ, x) = 0 можно однозначно восстановить по К точкам, то алгоритм заполнения аккумулятора формулируется следующим образом (шаг 2):

1. из облака точек X случайным образом выбирается К точек
2. по выбранным точкам определяются параметры кривой φ
3. значение счетчика соответствующей ячейки увеличивается

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

Методы поиска пиков в аккумуляторе

Анализ аккумулятора бывает часто затруднен следующими проблемами:

-      размытие пиков

-      3-х мерная поверхность значений аккумулятора очень редко бывает гладкой

Причинами являются дискретизация и шум.

Для их решения можно применяются следующие методы

<Размытие> аккумулятора

Это очень простое и элегантное решение призвано бороться с проблемами дискретизации, а именно граничной проблемой (когда точки одно кривой могут попасть в разные ячейки аккумулятора). Для этого при заполнении аккумулятора (шаг 2), увеличивают счетчик не только той ячейки, в которую попала точка, но так же увеличивают счетчики соседних ячеек [1].

Алгоритм сходящихся квадратов (The Converging Squares Algorithm)

Это тоже довольно простой метод поиска максимумов, но при этом он более устойчивый, нежели простой анализ локальных максимумов или градиентный подъем (спуск) [8].

Суть алгоритма в том, что он оперирует не понятием значения в точке, а понятием плотности региона. Здесь плотность региона - это среднее арифметическое точек региона, т.е. отношение суммы значений в каждой точке региона к количеству точек.

1. Пусть имеется квадратная матрица значений, размером KxK
2. Рассматривается 4 квадратных <подматрицы> размерами (K-1)x(K-1) прижатых к каждому углу соответственно.
3. Выбирается матрица с максимальной плотностью.
4. Для выбранной матрицы проводятся шаги a.-d. если K не равно 1.

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

Сдвиг центра масс (Mean Shift)

Здесь будет рассмотрен частный случай применения этого метода - наиболее простой (более общая формулировка метода описана в [9, 10]).

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

1. Cчитается центр масс точек внутри окна, по формуле:

,,

2. Центр окна переносится в центр масс
3. Шаги a.-b. повторяются до тех пор, пока сдвиг не станет меньше порога.

Существует дополнение к алгоритму, для проверки найденного максимума. После окончания основного алгоритма, окно сдвигается во всевозможных направлениях, на небольшое расстояние. Если из каждого такого положения алгоритм, опять сойдется к уже найденному максимуму, значит это стабильный максимум.

Литература

2. Анна Дегтярева, Владимир Вежневец, "Преобразование Хафа (Hough transform)", CGM 06.02.2003 http://cgm.graphicon.ru/metodyi/hough_transform.html
3. Olivier Ecabert, Jean-Philippe Thiran, "Adaptive Hough transform for the detection of natural shapes under weak affine transformations" Pattern Recognition Letters (25), No. 12, September 2004, pp. 1411-1419.
4. Tina Yu Tian, Mubarak Shah, "Recovering 3D Motion of Multiple Objects Using Adaptive Hough Transform" IEEE Trans. Pattern Anal. Mach. Intell. 19(10): 1178-1183 (1997)
5. Heikki Kalviainen "Randomized Hough Transform: New Extensions" (Kalviainen_doc_thesis-94.pdf)
6. J. Matas, C. Galambos, J. Kittler, "Progressive Probabilistic Hough Transform" (p176.pdf)
7. Nahum Kiryati, "Randomized or Probabilistic Hough Transform: Unified Performance Evaluation" Pattern Recognition Letters, Vol. 21, pp. 1157-1164, 2000
8. Robert A. McLaughlin and Michael D. Alder "Technical Report - The Hough Transform versus the UpWrite" Tech. Rep. TR97-02, 1997, Univ. of Western Australia, CIIPS, Dept. of Electrical and Electronic Eng.
9. Lawrence O'Gorman and Arthur C. Sanderson "THE CONVERGING SQUARES ALGORITHM: AN EFFICIENT MULTIDIMENSIONAL PEAK PICKING METHOD" IEEE Int. Conference on Acoustics, Speech, and Signal Processing, Boston, April, 1983, pp. 112-115
10. Hanzi Wang, David Suter, "False-Peaks-Avoiding Mean Shift Method for Unsupervised Peak-Valley Sliding Image Segmentation" DICTA 2003: 581-590
11. Dorin Comaniciu, Peter Meer, "Mean Shift: A Robust Approach Toward Feature Space Analysis" IEEE. Trans. Pattern Analysis and Machine Intelligence, 24(5):603-619, May 2002.

Дополнительная информация

Ссылка: 

Кирилл Мариничев, Владимир Вежневец. Алгоритмы выделения параметрических кривых на основе преобразование Хафа. Компьютерная графика и мультимедиа. Выпуск №4(1)/2006. http://cgm.computergraphics.ru/content/view/107

Выпуск: 

Выпуск №4(1)/2006