Сравнительный анализ методов формирования контурных представлений для поиска линий на основе метода Хафа

Системы компьютерного зрения и распознавания образов широко входят в обыденную жизнь современного человека. Компьютерное зрение позволяет эффективно решать различные задачи, связанные с анализом изображений или видеопоследовательностей. При автоматизированном анализе цифровых изображений очень часто возникает задача определения простых фигур, таких как прямые, круги или эллипсы. Преобразование Хафа может применяться в этих областях для распознавания контуров зданий на изображениях [1], нормализации ориентации текста на странице сканированного документа, определения линии горизонта [2], нахождения линий дорожной разметки и в прочих сферах [3].

Преобразование Хафа – метод, используемый в обработке изображений и компьютерном зрении, который предназначен для поиска параметрических и непараметрических объектов с использованием процедуры голосования. Данный метод основывается на представлении объекта интереса в виде параметрического уравнения [4; 5]. Параметры этого уравнения представляют собой фазовое пространство (аккумуляторный массив/пространство, пространство Хафа). Идея преобразования Хафа состоит в том, что для каждой точки пространства параметров подсчитывается число точек пространства, порождающих в про- странстве параметров отклики. При этом на основе данных фазового пространства возможно восстановить параметры исследуемого объекта.

Классический алгоритм преобразования Хафа является наиболее простым в реализации и быстрым в работе. Он предназначен для нахождения прямых на изображении. В этом случае фазовое пространство получается двумерным, так как любую линию можно задать двумя параметрами её уравнения [6; 7]. При формировании фазового пространства целесообразно использование нормального уравнения прямой:

R = x ■ cos 0 + y ■ sin 0 , (1)

где R – длина перпендикуляра, опущенного из начала координат на прямую; θ – угол между положительным направлением оси OX и направлением этого перпендикуляра R.

Использование в качестве параметров фазового пространства угла θ и длины перпендикуляра (радиуса) R обусловлено тем, что в случае применения параметров уравнения прямой с угловым коэффициентом y = k · x + b будет невозможно представить в фазовом пространстве прямую, параллельную оси OY .

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

Алгоритм выполнения преобразования Хафа (рис. 1) можно представить в виде последовательности шагов.

Шаг 1. Задание параметров для фазового пространства. На этом шаге выполняется задание диапазона углов θ и расчет максимальной длины перпендикуляра (радиуса) R _max, рассчитываемой по формуле

R max

22 width ⁺ I height ,

где I width – ширина изображения; I height – высота изображения.

Шаг 2. Задание размерности фазового пространства Хафа для угла (θ) и для радиуса ( R ).

Шаг 3. Создание матрицы, в которую заносятся данные о количестве точек, лежащих на прямой с заданными параметрами, PhaseSpace ( R , θ).

Шаг 4. Анализ каждой точки изображения. Если точка принадлежит контуру (в бинарном виде контурного представления она представлена белым цветом), то переход к шагу 5. В противном случае анализируется следующая точка изображения. Когда рассмотрены все точки изображения, переход к шагу 6.

Шаг 5. Проверка каждой прямой на возможность прохождения через точку ( x , y ). Для выполнения проверки перебираются все возможные углы наклона и все возможные расстояния от начала координат. Для каждого значения угла θ и расстояния R проверка выполняется согласно выражению

|x ■ cos 0 + y ■ sin 0- R.\ <  TS , (3)

где x , y – координаты точки в пространстве изображения; θ, R – значения параметров фазового пространства; TS – порог задания точности аппроксимации.

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

Шаг 6. Визуализация фазового пространства (рис. 1, б ) и формирование массива параметров фазового пространства PhasePar, который содержит в себе следующие элементы: угол θ, длину перпендикуляра R, значение аккумулятора для этих параметров Counter. В массив включаются элементы, содержащие ненулевое значение элемента Counter.

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

Шаг 8. Отрисовка на основании массива PhasePar найденных линий (рис. 1, в ) по точкам для θ, R , которые получены в результате преобразования.

При обработке цветных цифровых изображений точность определения линий во многом зависит от контурного представления изображения и параметров аппроксимации в фазовом пространстве. Методы формирования контурных представлений широко применяются в различных задачах, например для поиска наложенного текста [3], в задачах улучшения качества изображений [8], а также при сегментации [9] и анализе параметров объектов в различных сферах [10; 11]. Наиболее известными являются методы Робертса, Превита, Собела и Лапласа [9; 10].

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

Метод Робертса, как показывает практика, является самым простым и самым быстродействующим. В данном методе используется маска 2×2 вида

GD

DD ^,

где G – пиксел, с которым ведется работа; D – соседние пикселы.

а

б

в

Рис. 1. Примеры изображений формируемых при выполнении преобразования Хафа: а – исходное изображение; б – фазовое пространство; в – найденные линии

Операторы Робертса

– коэффициент Лапласа с отрицательным ядром:

Gx =

- 1

Gy =

- 1 0

используются для расчета значения нового пиксела по формулам

G = 7Gx2 + Gy2 G = |Gx| +1Gy|,      (4)

	0	1	0		1	1	1
a =	1	- 4	1	, a =	1	- 8	1
	0	1	0		1	1	1

Методы Превита и Собела аналогичны методу Робертса – они также основаны на вычислении градиента и работают с масками 3×3 следующего вида:

D	D	D
D	G	D
D	D	D

где G – пиксел, с которым ведется работа; D – соседние пикселы;

Для расчета нового значения методы Превита и Собела также используют выражение (4). Основное их отличие заключается в самих операторах:

– операторы Превита:

	1 0 - 1		111
Gx 1 =	1 0 - 1	, Gy 1 =	000
	1 0 - 1		- 1 - 1 - 1

	1	1	0		0	1	1
Gx 2 =	1	0	- 1	, Gy 2 =	- 1	0	1
	0	- 1	- 1		- 1	- 1 0

– операторы Собела:				1	21
	1	0 - 1
Gx 1 =	2	0 - 2	, Gy 1 =	0	00
	1	0 - 1		- 1	- 2 - 1

Gx 2 =

0 - 1

- 1

- 2

Gy 2 =

- 1 0

- 2

- 1

На рис. 2 отображены примеры контурных представлений некоторых методов.

Как можно заметить из рис. 2, метод Собела дает более плотное описание линий контуров, метод Робертса учитывает меньше градиентных переходов, метод Лапласа с отрицательным ядром подчеркивает внешние границы, а с положительным ядром – внутренние.

Прежде чем выполнять обработку контурного представления методом Хафа, необходимо выполнить бинаризацию. Бинаризацию можно выполнить с использованием фиксированного порога, адаптивного порога на основе значений максимума и минимума или порога, вычисленного методом Отсу [12].

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

(σ кл )² = ω 1 ∙ω 2 ∙(a 1 – a 2 )²,               (6)

где ω 1 и ω 2 – значения вероятности первого и второго классов; a 1 и a 2 – средние арифметические значения для каждого из классов.

Для расчета значений вероятностей классов с учетом порога используются выражения:

® 1 ( t ) = ^Pi, ® 2 ( t ) = X P i = 1 -® 1 ,    (7)

i = 0                          i = t + 1

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

mn

I new ⁽ x , у ) = EZ ^a k , 1 ' I old ⁽ x - m^{/2 + k} , у - n^{/2 + 1} ), ⁽⁵⁾ k = 0 1 = 0

где I _new, I _old – новые и старые значения пикселов изображения; α_{k , l} – коэффициент, определяющий эффект фильтра; m , n – константы, задающие размер фильтра. При наложении фильтра Лапласа коэффициент α может иметь различный вид (рис. 2):

– коэффициент Лапласа с положительным ядром:

- 1

- 1

- 1

- 1

где p i – вероятность распределения i -го элемента гистограммы; t – значение порога.

Обобщенная форма алгоритма вычисления порога методом Отсу:

Шаг 1. Формирование гистограммы и вероятностей p_i распределения интенсивностей.

Шаг 2. Анализ гистограммы. Начиная с порога t = 1 происходит проход через всю гистограмму, на каждом шаге выполняются следующие действия:

Шаг 2.1. Пересчитывается дисперсия σ кл ( t ).

Шаг 2.2. Если на каком-то шаге дисперсия оказалась больше максимума, то дисперсия обновляется и T = t .

Еще один метод бинаризации – максиминный. В нем выполняется расчет глобального порога бинаризации Т на основе минимума (min) и максимума (max) интенсивности для всего изображения согласно формуле

a =

- 1

- 1

a= - 1 8 - 1

- 1

- 1

- 1

- 1

T = max + min =     2

.

а

б

г

Рис. 2. Примеры работы методов по выделению контурных линий:

а - метод Собела с вычислением градиента по всем направлениям; б - метод Робертса; в - метод Лапласа с отрицательным ядром; г - метод Лапласа с положительным ядром

Проанализировав представленные методы бинаризации на тестовых изображениях, авторы сделали вывод о том, что наиболее эффективным из перечисленных методов глобальной бинаризации по качеству обработки (величина ошибок до 30 % и меньше) является метод Отсу. К его недостаткам относится размытие линий, потеря тонких линий [12; 13]. Примеры бинаризации контурных представлений показаны на рис. 3.

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

Для анализа описанных методов формирования контурных представлений был проведен ряд экспериментов, который заключался в следующем: на тестовых фотографиях отмечались важные линии (каркас-ные линии, имеющие значение при построении модели помещения), после этого с помощью реализованных методов программа находила линии и сохранялись параметры и результаты их работы. Для проведения экспериментов были отобраны 100 различных фотографий, сделанных в разных условиях: 40 фотографий были сделаны внутри помещений, имеющих длинный центральный коридор; 30 фотографий были сделаны внутри помещений, имеющих четкие разгра- ничительные линии (между стенами и потолком, стенами и полом); остальные фотографии были выполнены в условиях плохой различимости линий (сливающиеся, тонкие, искаженные). Выполнение оценки методов формирования контурных представлений осуществлялось для бинаризации методом Отсу и с использованием адаптивного порога на основе максимальных и минимальных значений гистограммы. Бинаризация со статическим порогом была исключена, поскольку она очень сильно зависит от величины отклика, полученного при формировании контурного представления, и условий освещения во время съемки. В качестве оценки использовались следующие критерии: процент точного определения искомых линий, процент дублирующих линий, процент ложно обнаруженных линий. В таблице представлены сводные данные для оценки методов.

На основе проведенных экспериментов можно сделать следующие выводы. Одним из самых эффективных методов формирования контурного представления для поиска линий является метод Собела. По точности определения искомых линий он превышает остальные методы на 8^30 %. Его существенным недостатком является то, что на месте одной линии он находит несколько (с равным углом и сходным расстоянием). Количество этих линий лишь немногим меньше, чем в методе Превита. Характерной особен- ностью этих линий является достаточно большой разброс (2…6 пикселов), в отличие от метода Лапласа (0…3 пиксела). Метод Собела также находит большое количество посторонних (не основных) линий, причем по их количеству он уступает лишь методу Робертса на 7…8 %.

а

б

в

г

Рис. 3. Пример бинаризации контурных представлений методом Отсу (слева) и на основе Максиминого порога (справа):

а – метод Собела с градиентом по всем направлениям; б – метод Робертса; в – метода Лапласа с отрицательным ядром; г – метод Лапласа с положительным ядром

Интерфейс

Ядро

Модуль работы с файлами

Модуль формирования контурного представления

Модуль сбора статистики

Модуль преобразования Хафа

Преобразование цветов моделей

Формирование контуров

Бинаризация изображения

YUV

Метод Робертса

Метод Отсу

HLS

Метод Собела

Максимин

Метод Лапласа

Метод Превита

Рис. 4. Схема организации модулей экспериментального программного обеспечения

Оценка методов формирования контурных представлений

Методы формирования контурных представлений	Точность определения искомых линий, %		Ложное определение, %		Дублирующиеся линии, %
	Отсу	максимин	Отсу	максимин	Отсу	максимин
Метод Собела (все направления)	80,2	52,1	17,3	2,7	28,1	16,8
Метод Собела (декартовые направления)	77,1	50,7	15,3	2,7	27,05	18,1
Метод Собела (диагональные направления)	73,4	50,3	14,6	5,6	28,35	16,7
Метод Превита (все направления)	79,2	48,3	16,1	2,8	31,05	16,8
Метод Превита (декартовые направления)	73,2	47,1	14,3	2,7	29,05	18,1
Метод Превита (диагональные направления)	72,8	47,4	16,2	4,9	28,35	16,7
Метод Робертса	71,6	12,3	18,3	2,9	25,15	8,6
Метод Лапласа (положительное ядро 4)	43,5	9,2	10,2	3,5	21,75	5,1
Метод Лапласа (положительное ядро 8)	49,2	43,1	12,8	2,7	23,1	20,5
Метод Лапласа (отрицательное ядро 4)	50,3	8,7	5,2	1,7	20,5	6,15
Метод Лапласа (отрицательное ядро 8)	48,4	48,1	5,4	2,5	19,2	23,05

Подводя итоги, можно сказать, что выбор метода формирования контурного представления в большей степени зависит от решаемых задач: если требуется найти как можно больше верных линий, то метод Собела будет наилучшим выбором; если же требуется, чтобы среди найденных линий присутствовало как можно меньше ложно определенных линий и допускается небольшая потеря основных линий, то целесообразно использование метода Лапласа. Для компенсации дублирующихся линий предлагается ввести следующую модификацию: при нахождении линий с одинаковым углом и сходной длиной перпендикуляра (различия на 2…4 пиксела) следует объединять их в одну линию, при этом итоговая длина перпендикуляра будет вычисляться как среднее арифметическое значение. Данная модификация позволит улучшить показатели методов Лапласа и Робертса за счет малого разброса их дублирующихся линий. По предвари- тельным оценкам в методах Собела и Превита количество дублирующихся линий с применением модификации сократится в среднем на 60…70 %.