Преобразование хафа для поиска окружностей matlab

Институт информатики и искусственного интеллекта

Кафедра программного обеспечения интеллектуальных систем

Специальность «Программное обеспечение систем»

Видео:Лабораторная работа "Обобщенное преобразование Хафа" Часть 2Скачать

Исследование и разработка метода распознавания кривых на плоскости

Научный руководитель: к.ф.-м.н., доц. Ручкин Константин Анатольевич

Видео:Лекция 9 Канни, Хаф, Харрис,SIFTСкачать

Реферат по теме выпускной работы

Видео:Лабораторная работа "Обобщенное преобразование Хафа" Часть 1Скачать

Содержание

Видео:ТАУ. Matlab/Simulink - моделирование передаточной функции, снятие характеристикСкачать

Введение

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

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

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

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

1.1 Актуальность темы

Задача автоматизированной обработки данных стояла перед человечеством ещё со времён появления самых данных. Но только с появлением цифровых форматов хранения этот процесс значительно продвинулся вперёд. Еще в 60-х годах XX века [7] Хаф предложил преобразование, позволяющее переводить координаты точек двухмерного пространства в данные аккумуляторного массива с дальнейшим применением процедуры голосования. И хотя в то время цифровой формат хранения был не особо распространен, тем не менее, данное преобразование очень заинтересовало научное сообщество. В последующем различными учёными были предложены варианты данного преобразования для нахождения не только линии, но и окружностей, эллипсов и даже объектов произвольной формы [12].

С течением времени распространение цифровых форматов изображений дало ещё больший толчок к освоению области автоматической обработки изображений. И к преобразованию Хафа стали обращаться всё чаще. Возникло множество его модификаций, которые ускоряли алгоритм и делали его достаточно быстрым. Это позволяло применять его в реальных системах обнаружения объектов [14] и даже в системах реального времени. Так же положительным моментов в развитии этого направления стал играть тот факт, что с каждым годом вычислительная мощность современных ЭВМ возрастает, что так же помогает ускорить процесс поиска объектов на изображении.

Уже на текущий момент преобразование Хафа может применяться в таких областях как распознавание контуров зданий на изображениях [11], определение линии горизонта [9], нахождение линий дорожной разметки, определение количества осей у движущегося транспорта и прочих сферах.

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

1.2 Цель и задачи исследования

Объектом исследования является задача автоматизированного поиска различных объектов на изображении.

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

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

В процессе работы необходимо решить следующие задачи:

1) исследование существующих методов поиска объектов на изображении и выделение из них наиболее производительных и популярных;

2) детальное рассмотрение частных случаев этих методов для обнаружения различных типов объектов;

3) разработка оптимизированных методов, позволяющих ускорить базовый алгоритм поиска объекта;

4) программная реализация базовых и оптимизированных методов с целью сравнения их скорости выполнения и эффективности распознавания.

1.3 Научная новизна

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

1.4 Практическая значимость

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

Видео:Image Processing toolboxСкачать

2 Современное состояние проблемы

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

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

В источнике [2] обсуждается рандомизированное преобразование Хафа для поиска эллипсов на изображении. Объясняются уравнения для нахождения эллипсов и их реализация. Алгоритм показал хорошие результаты при нахождении эллипсов с углом наклона 0 и 90 градусов к оси координат на изображении. Так же приведены примеры поиска и нахождения эллипсов на реальных изображениях после предобработки данных изображения.

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

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

В источнике [8] описывается преобразование Хафа для поиска линий и окружностей на изображении с использованием библиотеки OpenCV. Детально описано преобразование Хафа для линий и приведён исходный код алгоритма на языке С++, так же описаны функции библиотеки OpenCV, реализующие это преобразование. Описан алгоритм для поиска окружностей и соответствующие функции на языке OpenCV, представлен пример соответствующей программы. Приведены результаты работы написанных программ с описанием полученного результата.

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

В источнике [10] описывается преобразование Хафа для поиска окружностей и линий. Описаны разновидности этого преобразования для поиска линий и детали реализации в библиотеке OpenCV. В частности описаны функции этой библиотеки, передаваемые ей параметры и возвращаемые значения. Приведены иллюстрации работы функций с разными передаваемыми ей параметрами.

В источнике [11] описываются метод восстановления 3D моделей зданий из снимков двухмерных изображений. Метод основанный на определении уровней детализации. Рассматриваются каждый из трёх уровней детализации. Так же в работе описывается как может быть применено преобразование Хафа для обнаружения границ зданий.

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

В источнике [13] рассмотрено преобразование Радона, его свойства и основные типы. Рассмотрена задача распознавания простейших геометрических объектов на монохромном изображении на основании интегрального преобразования пространства изображения в пространство параметров объекта. Приведены алгоритмы поиска простейших геометрических объектов на изображении.

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

Источник [15] описывает способы поиска параметрических кривых на бинарном изображении с использованием преобразования Хафа. В частности детально и пошагово описан алгоритм преобразования Хафа как для поиска прямой, так и окружности на изображении. Приведён пример программы на языке JAVA и описано её применения в распознавании радиуса монеты для определения её номинала.

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

Видео:Лабораторная работа "Обобщенное преобразование Хафа" Часть 3Скачать

3 Анализ преобразования Хафа для задачи поиска двухмерных геометрических примитивов на изображении

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

Классический алгоритм преобразования Хафа был предназначен для нахождения прямой на изображении, но позже алгоритм был расширен и теперь его можно применять для обнаружения как остальных параметризируемых объектов (например, эллипсов [2], окружностей [14], парабол), так и не параметризируемых объектов произвольной формы [12].

Как было сказано ранее классическое преобразование Хафа является линейным и применяется для обнаружения прямых. Прямая задается уравнением y=mx+b и может вычисляться для любой пары активных точек на изображении (x,y). Главная идея преобразования Хафа – учитывать характеристики прямой в терминах её параметров, то есть параметров m и b. Таким образом, пространство параметров для линий будет двухмерным и состоит из двух параметров – угла наклона m и точки пересечения прямой с осью OY, b. Но для данного типа уравнения существует проблема задания вертикальных прямых, потому что в этом случае получаем бесконечные значения параметров m и b. Если же представить прямую через параметры вектора, перпендикулярного этой прямой и проходящего через начало координат, то эта проблема исчезнет. Зададим прямую через два параметра R и θ. R представляет собой длину указанного вектора, а θ – угол вектора к оси координат.

В этом случае уравнение прямой будет представлено в таком виде:

Или же оно может быть преобразовано к следующему виду: r = x*cos θ + y*sin θ.

Таким образом, каждая прямая на изображении может быть представлена двумя параметрами своего вектора нормали – r и θ. Эти параметры будут уникальными при условии θЄ[0,PI] и rЄR или если θЄ[0,2PI] и r>=0. Создавши аккумуляторный массив с определённым шагом, сможем заносить в него значения заданных параметров. Этот массив так же называется пространством Хафа для прямых на плоскости или просто накопительным пространством.

Через одну точку может проходить бесконечное число прямых линий. Если эта точка имеет координаты (x0,y0), то все прямые линии, проходящие через неё, будут иметь следующее уравнение:

Где r и θ могут иметь произвольные значения из вышеуказанного диапазона.

Это соответствует синусоидальной кривой в накопительном пространстве (r,θ), которая уникальна для каждой отдельной точки. Синусоиды нескольких точек накладываются друг на друга. Точки их пересечения в пространстве параметров определяют параметры прямых (r,θ), которые проходят через точки задающие синусоиды. Таким образом точки, которые формируют прямую линию, определяют синусоиды, которые пересекаются в одной точке накопительного пространства, которая задает параметры искомой линии. Задача поиска прямой линии, в конечном счете, сводится к задаче поиска максимума в накопительном пространстве параметров.

3.1 Преобразование Хафа для поиска линий

Пускай заданно N активных точек на изображении (точек по которым нужно найти прямую линию).

Пусть имеется множество плоских линий L(R,θ), которые задаются в параметрическом виде параметрами R, θ. Первый параметр это длина перпендикуляра от прямой до точки начала координат, второй – угол между перпендикуляром и осью координат (пусть это будет ось OX). Таким образом, подставив эти параметры в параметрическое уравнение, мы сможем восстановить исходное уравнение прямой.

Параметры прямых образуют двухмерное пространство Хафа, по одной оси которого будет менятся параметр R, по другой оси параметр θ. Это пространство нам необходимо сделать дискретным, для этого нам нужно знать минимальное и максимальное возможное значение радиуса (R) и угла (θ). Минимальный радиус будет равен нулю (прямая проходит через начало координат), максимальный – расстоянию от самой дальней активной точки изображения до начала координат. Минимальный угол равен 0 градусов, максимальный – 2*PI (или 360 градусов). Так же определим размерность нашей таблицы – пусть по оси R она равна k, а по оси θ равна m. Тогда массив прямых можно изобразить как L[k][m]. Значение радиуса в ячейке L[i][j] равно:

R(L[i][j]) = Rmin + dR*i,

где Rmin – минимальный радиус (равен нулю);
dR = (Rmax-Rmin)/k.

Значение угла в ячейке L[i][j] равно:

Таким образом, если на прямой линии с заданными параметрами R и θ лежит активная точка, то значение её ячейки увеличивается на единицу. Ячейка, значение которой наибольшее, как рак раз и будет указывать на параметры найденной прямой.

В общем виде алгоритм Хафа для поиска прямой линии на изображении будет выглядеть так:

1. Вычислить максимальное значение удалённости активных точек от начала координат – Rmax.
2. Задать размерность пространства Хафа для угла (θ) и для радиуса (R).
3. Вычислить параметры dR и dθ.
4. Создать матрицу, в которую заносятся данные о количестве активных точек, лежащих на прямой с заданными параметрами – L(R, θ), размерность равна – L[k][m].
5. Обнулить все значения матрицы L(R, θ).
6. Цикл по всем активным точкам изображения – Ti(Xi,Yi):
   Цикл по j от 0 до 2*PI с шагом dθ:
   θ = j * dθ;
   R = Xi*cos(θ) + Yi*sin(θ);
   Rтек = Rmin;
   k = 0;
   Пока |Rтек-R|>dR/2:
   Rтек = Rтек + dR;
   k = k + 1;
   конец Пока;
   L[k][j] = L[k][j] + 1;
   Конец цикла по j;
   Конец цикла по всем точкам.
7. Найти ячейку L[i][j] c максимальным значением счётчика.
8. Восстановить параметры прямой по ячейке L[i][j] согласно формулам:
   R(L[i][j]) = dR*i;
   θ(L[i][j] = j*dθ;
9. Вывести найденные параметры R и θ.

Блок-схема алгоритма представлена на рисунке 3.1.

Рисунок 3.1 – Блок-схема алгоритма преобразования Хафа для поиска линии
(анимация: 8 кадров, 5 циклов повторения, 39.5 килобайт)

3.2 Преобразование Хафа для поиска окружностей

Преобразование Хафа успешно применяется для поиска окружностей на растровом изображении.

Геометрически окружность представляет собой множество точек, равноудалённых от одной точки – центра окружности. Уравнение окружности имеет вид: (x-a)^2+(y-b)^2=R^2, где (x,y) – координаты любой точки окружности, (a,b) – координаты центра окружности, R – радиус окружности.

Таким образом, любую окружность можно задать тремя параметрами: радиус (R) и координаты центра окружности (a,b). Значит накопительное пространство Хафа будет трехмерным (R,a,b). Если при поиске окружности известен её радиус, тогда накопительное пространство будет двухмерным (неизвестные параметры искомой окружности – координаты её центра (a,b)).

Ниже описан в общем виде алгоритм Хафа для поиска окружностей.

1. Задать максимальный радиус круга – Rmax.
2. Задать границы размещения центра круга – Xmin, Xmax, Ymin, Ymax.
3. Создать массив, в котором хранятся данные об окружностях и количестве точек, через которые они проходят:
   C[Xmax-Xmin][Ymax-Ymin][Rmax].
4. Обнулить массив C[a][b][R].
5. Цикл по всем активным точкам (Xi, Yi) изображения:
   Цикл по а от Xmin до Xmax c шагом dX=1:
   Цикл по b от Ymin до Ymax c шагом dY=1:
   R := SQRT((Xi – a)^2 + (Yi – b)^2);
   C[a][b][R] := C[a][b][R] + 1;
   Конец цикла по b;
   Конец цикла по а;
   Конец цикла по всем активным точкам.
6. В массиве C[a][b][R] найти ячейку с максимальным значением.
7. Найти параметры уравнения окружности по найденной ячейке C[i][j][k]:
   a := i;
   b := j;
   R := k.
8. Вывести найденные параметры.

Блок-схема алгоритма Хафа для поиска окружностей в общем виде представлена на рисунке 3.2.

Рисунок 3.2 – Блок-схема алгоритма преобразования Хафа для поиска окружности на изображении

3.3 Применимость преобразования Хафа

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

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

Чтобы ускорить работу алгоритма для нахождения эллипсов и окружностей, необходимо оптимизировать алгоритм для каждого частного случая и поставленной задачи. Например, если известен радиус окружности, то пространство Хафа можно свести к двухмерному, если известен её центр – к одномерному. Если известен центр эллипса, то пространство Хафа уже будет трехмерным, а если ещё дополнительно известно соотношение большой и малой полуоси эллипса, или угол наклона к оси координат – пространство Хафа будет двухмерным.

Видео:Преобразования #11: введение в вейвлеты, вейвлет-преобразование ХаараСкачать

Выводы

В работе были проанализированы методы поиска двухмерных геометрических примитивов на изображении. В результате выполнения были изучены литературные и Интернет источники, в которых описывались подобные методы. Наиболее простым, но достаточно эффективным методом оказался метод преобразования Хафа. Этот метод может успешно применяться для распознавания таких геометрических объектов на изображении – линии, окружности, эллипсы, а так же непараметрические объекты. В проанализированных источниках были изучены случаи этого преобразования для всех указанных типов геометрических объектов.

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

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

Видео:Отслеживание ПРЯМЫХ линий Метод ХАФА Processing OPENCV lineDetection веб камера web cameraСкачать

Список источников

1. The Hough Transform [Электронный ресурс]. – Режим доступа : http://homepages.inf.ed.ac.uk/rbf/CVonline. .
2. Samuel A. Inverso. Computer Vision: Ellipse Detection Using Randomized Hough Transform [Электронный ресурс]. – Режим доступа : http://www.saminverso.com/res/vision/.
3. James Matthews. Hough Transforms [Электронный ресурс]. – Режим доступа : http://www.generation5.org/content/2008. .
4. Алгоритм Хафа для обнаружения произвольных кривых на изображениях [Электронный ресурс]. – Режим доступа : http://habrahabr.ru/blogs/algorithm/102948/.
5. Использование преобразований Хафа (Hough transform) для выделения прямых на изображении [Электронный ресурс]. – Режим доступа : http://eddy-em.livejournal.com/932.html.
6. Дегтярева A. Преобразование Хафа [Электронный ресурс]. – Режим доступа : http://www.cgm.computergraphics.ru/content/view/36.
7. Преобразование Хафа [Электронный ресурс]. – Режим доступа : http://ru.wikipedia.org/wiki. .
8. OpenCV шаг за шагом. Преобразование Хафа [Электронный ресурс]. – Режим доступа : http://robocraft.ru/blog/computervision. .
9. Коррекция наклона (skew correction) [Электронный ресурс]. – Режим доступа : http://bik-top.livejournal.com/37060.html.
10. Преобразования Хафа [Электронный ресурс]. – Режим доступа : 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с.
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с.
13. Запрягаев С. А. Программная оболочка для поиска примитивов на изображении / С. А. Запрягаев, А. И. Сорокин // Вестник ВГУ, серия: системный анализ и информационные технологии. – Воронеж, 2008. – № 2. – С. 37-47.
14. Сай И. С. Эффективность алгоритмов поиска оттиска печати в изображении документа / Сай И. С. // Вестник ТОГУ. – 2009. – № 4. – C. 53-60.
15. Семенов А.Б. Обработка и анализ изображений с использованием языка JAVA, курс лекций / Семенов А.Б. – Тверь : Тверской государственный университет, 2007. – 10 c.

Видео:Алгоритм бинарного поиска: пример реализации в MATLABСкачать

Важное замечание

При написании данного автореферата магистерская работа еще не завершена. Предположительная дата завершения – 1 декабря 2012 г. Полный текст работы, а также материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Видео:Сегментация изображения сетью - SegNet. 1 – алгоритм в MATLABСкачать

Алгоритм Хафа для обнаружения произвольных кривых на изображениях

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

В алгоритме преобразования Хафа используется аккумуляторный массив, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых. Например, при обнаружении прямых, описываемых уравнением y=m*x+b, для каждой прямой необходимо вычислить значения двух параметров m и b. При этом в массиве в элементах A[M,B] накапливаются значения, указывающие на вероятность наличия на изображении прямой y=m*x+b, где M и B соответствуют дискретным значениям m и b.

Массив A используется в алгоритме Хаффа для проверки каждого пиксела изображения и его окрестности. Определяется присутствует ли в данном пикселе выраженный край. Если присутствует, то вычисляются параметры искомой кривой, проходящей через данный пиксел. После оценки параметров прямой в данном пикселе они дискретизируются для получения соответствующих значений M и B, и значение массива A[M,B] увеличивается. В некоторых реализациях увеличение выполняется на единицу, в других на величину мощности края в обработанном пикселе. После обработки всех пикселов выполняется поиск локальных максимумов в аккумуляторном массиве. Точки локальных максимумов соответствуют параметрам наиболее вероятных прямых на изображении.

Аккумуляторный массив позволяет определить параметры бесконечно протяжённых прямых или кривых, но с его помощью невозможно определить, где именно начинаются и заканчиваются отрезки этих линий. Для получения этой информации можно завести ещё одну структуру данных PTLIST. Элемент PTLIST[M,B] содержит список координат всех пикселов, которые внесли вклад в значение аккумуляторного массива A[M,B]. По содержанию этих списков можно найти присутствующие на изображении отрезки или сегменты кривых.

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

Уравнение прямой y=m*x+b не подходит для представления вертикальных прямых. Удобнее представлять прямые в виде d=x*cos(f)+y*sin(f), где d — это длина перпендикуляра к прямой, а f — угол между перпендикуляром и горизонтальной осью. В системе координат изображения оси направлены вдоль строк и столбцов изображения. Так координата c соответствует x, а координата r — координате (-y), то уравнение прямой принимает вид: d=c*cos(f)-r*sin(f).

Индексы аккумуляторного массива A соответствуют дискретным значениям d и f. В серии экспериментов 1976 О’Горман и Кловс дискретизировали значения d с шагом 3 и значения f с шагом 10. Ниже в виде процедуры accumulate_lines приведён алгоритм О’Гормана и Кловса для заполнения аккумуляторного массива A и массива списков PTLIST.

Алгоритм работает в двумерном координатном пространстве. Функция row_gradient и column_gradiet обрабатывают окрестности пикселов для оценки компонент градиента в направлении строк и столбцов. Функция gradient комбинирует комбинирует две эти компоненты для получения величины градиента. Функция atan2 возвращает по заданным компонентам градиента угол в соответствующем квадранте. Процедура accumulate_lines представляет собой версию преобразования Хафа. Оригинальный метод Хафа не предусматривает стандартного метода выделения отрезков прямых. Поэтому была разработана процедура find_lines. Функция pick_greatest_bin возвращает максимальное значение из аккумуляторного массива, присваивая параметрам DQ и THETAQ соответствующие дискретные значения d и f. Функция reader упорядочивает список точек в элементе массива по координате столбца при f 135 и по координате строки при 45

Видео:Разметка данных для сегментации в MATLABСкачать

Преобразование хафа для поиска окружностей matlab

Copy raw contents

Copy raw contents

[П]|[РС]|(РП) Преобразования Хафа

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

Преобразование Хафа для линий

Теоретической подоплекой преобразования Хафа для линий является то, что любая точка на бинарном изображении, возможно, является частью некоторого множества линий. Если описать каждую линию по её наклону a и сдвигу b <Roman — наклон и пересечение (или наклон-сдвиг) — параметры уравнения прямой y = k•x + b, где k — угловой коэффициент прямой, вычисляемый через тангенс, а пересечение b — коэффициент сдвига прямой по оси y так, чтобы прямая пересекала ось y на высоте b>,то точка на исходном изображении преобразуется во множество точек на плоскости (a, b), соответствующие всем линиям, проходящих через эту точку (рисунок 6-9). Если преобразовать каждый ненулевой пиксель во входном изображении в такой набор точек в выходном изображении и просуммировать все подобные внесения, тогда линия, появившаяся на входном изображении (то есть на плоскости (x,y)) будет соответствовать локальному максимуму в выходном изображении (то есть на плоскости (a,b)). Поскольку суммируется вклад от каждой точки, плоскость (a,b) принято называть накопительной плоскостью (в дальнейшем просто накопитель).

Может оказаться, что плоскость вида наклон-сдвиг не лучший способ представления всех линий, проходящих через точку (из-за значительно различной плотности линий в зависимости от наклона и от того, что интервал возможных наклонов лежит в диапазоне от –∞ до +∞) . По этой причине, в численных расчетах используется другая параметризация преобразования изображения. Предпочтительная параметризация представляет каждую линию как точку в полярных координатах (ρ, θ), при чем эта линия проходит через указанную точку, но линия должна быть перпендикулярной к радиус-вектору от начала координат до этой точки на линии (рисунок 6-10). Уравнение для такой прямой:

Рисунок 6-9. Преобразование Хафа для линий находит множество линий на каждом изображении. Некоторые из них ожидаемые, но другие могут не быть таковыми

Рисунок 6-10. Точка (, ) на плоскости изображения (график a) соответствует множеству линий, каждая из которых параметризирована разными ρ и θ (график b); каждая из этих линий соответствует точкам на плоскости (ρ, θ), которые, будучи собранными вместе, образуют кривую характеристической формы (график c)

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

OpenCV поддерживает два вида преобразований Хафа для линий: обычное преобразование Хафа (SHT) и прогрессивное (улучшенное) вероятностное преобразование Хафа (PPHT). Ранее уже был рассмотрен алгоритм SHT. PPHT является его разновидностью и также вычисляет протяжённость каждой линии в дополнение к их наклону (рисунок 6-11). Алгоритм назван «вероятностным», т.к. вместо добавления каждой возможной точки на накопительную плоскость, он добавляет только часть из них. Идея состоит в том, что если существует максимум на плоскости, то, в любом случае, хотя бы частичное попадание в этот максимум будет достаточным условием, чтобы обнаружить линию; как результат — существенное снижение времени выполнения вычислений. Для обоих случаев в OpenCV существует одна функция, которая, в зависимости от входных параметров, принимает решение о выполнение того или иного метода.

Первый аргумент — это исходное изображение. Оно должно быть 8-битным, но при этом будет трактоваться как бинарное (т.е. все ненулевые значения будут восприниматься как равные единицы). Второй аргумент — указатель на место, где будет храниться результат, который может быть либо хранилищем в памяти (CvMemoryStorage из главы 8), либо матрицей размера Nx1 (при этом количество строк N будет также еще ограничивать максимальное число возвращаемых линий). Следующий аргумент method может быть CV_HOUGH_STANDARD, CV_HOUGH_PROBABLISTIC, CV_HOUGH_MULTI_SCALE для SHT, PPHT и многопараметрического варианта SHT (MSHT) соответственно.

Следующие два аргумента, rha и theta, устанавливают желательное разрешение для линий (т.е. разрешение накопительной плоскости). Параметр rho вычисляется в пикселях, а параметр theta в радианах, поэтому накопительную плоскость можно рассматривать как двухмерную гистограмму с ячейками размерностью rho пикселей на theta радиан. Значение параметра threshold определяет величину, при достижении которой сообщается о нахождении линии. Этот последний параметр на практике несколько мудрёный, при чем он не нормализуется, поэтому ожидается, что сам разработчик будет его масштабировать с учетом роста размерности входного изображения для алгоритма SHT. Помните, этот параметр, в действительности, определяет количество точек, которое должна содержать линия, чтобы быть добавленной в возвращаемый список линий.

Рисунок 6-11. Сначала выполнен проход при помощи детектора границ Canny (param1 = 50, param2 = 150), результат показан в оттенках серого. Затем произведено прогрессивное вероятностное преобразование Хафа (param1 = 50, param2 = 10), результат показан белым. Заметьте, что преобразование Хафа в основном правильно обнаруживает чёткие линии

Аргументы param1 и param2 алгоритм SHT не использует. Для алгоритма PPHT param1 задает минимальную длину для возвращаемого сегмента линии, а аргумент param2 задает расстояние между коллинеарными сегментами, необходимое для того, чтобы алгоритм не склеил их вместе в один сегмент большей длины. Для многопараметрического варианта SHT эти два параметра применяются для указания наивысшего разрешения до которого параметры возвращаемых линий должны быть вычислены. Многопараметрический SHT сначала вычисляет положение линий с учетом разрешений rho и theta, а затем начинает уточнение результатов до степени параметров param1 и param2 соответственно (т.е. конечное разрешение rho – это rho делённое на param1, а конечное разрешение для theta равно theta делённому на param2).

Возвращаемое значение функции зависит от входных параметров. Если параметр line_storage матрица, тогда возвращаемое значение будет NULL. В этом случае, матрица должна быть типа CV_32FC2 для SHT или многопараметрического SHT и CV_32SC4 для PPHT. В первых двух случаях величины ρ и θ для каждой линии будут помещены в двух каналах массива. В случае PPHT, четыре канала будут содержать значения x и y для начальной и конечной точек возвращаемого сегмента. И для всех этих случаев, количество строк в массиве будет обновлено функцией cvHoughLines2() до количества возвращаемых линий.

Если параметр line_storage содержит указатель на хранилище в памяти (более подробно об этом будет рассказано в главе 8), тогда возвращаемым значением будет указатель на структуру последовательности CvSeq. В этом случае, можно получить каждую линию или сегмент линии из последовательности при помощи подобной команды:

где lines это возвращаемое значение функции cvHoughLines2(), а i — индекс запрашиваемой линии. В этом случае, line будет указателем на данные запрашиваемой линии, при чем line[0] и line[1] будут действительными числами, соответствующие значениям ρ и θ (для SHT и MSHT), либо указателем на структуру из парных значений CvPoint для начальной и конечной точек сегмента (для алгоритма PPHT).

Преобразование Хафа для окружностей

Преобразование Хафа для окружностей (рисунок 6-12) работает почти аналогично только что описанному преобразованию Хафа для линий. «Почти» только лишь потому, что — если выполнить точно аналогичные действия — накопительная плоскость будет замещена плоскостью объема с тремя измерениями: одно для x, одно для y и последнее для радиуса круга r. Это приводит к значительно большим затратам памяти и значительно меньшей скорости выполнения. Реализация преобразования Хафа для окружности в OpenCV уходит от этой проблемы, применяя несколько хитрый метод, называемый градиентным методом Хафа.

Градиентный метод Хафа работает следующим образом. Вначале изображение проходит фазу поиска краев (использование функции cvCanny()). Затем для каждой ненулевой точки краев изображения ищется локальный градиент (вычисляется путем расчета производных Собеля первого и второго порядка для x и y при помощи функции cvSobel()). Используя этот градиент, каждая точка линии обозначается как наклон — от установленного минимума до указанного максимального расстояния — итерационно изменяя накопитель. В тоже время, запоминается расположение каждой ненулевой точки на изображении краев. Центры-кандидаты затем выбираются из тех точек (двухмерного) накопителя, величины которых выше заданного порога и, одновременно, больше всех их непосредственных соседей. Эти центры-кандидаты сортируются в порядке убывания их величины в накопителе, так, что центры с наибольшим количеством пикселей выбираются первыми. Далее, для каждого центра, анализируются все ненулевые пиксели. Эти пиксели сортируются в соответствии с их расстоянием от центра. Обрабатывая от наименьших расстояний до наибольших радиусов, выбирается единственный радиус, который лучше всего подходит ненулевым пикселям. Центр сохраняется, если он имеет достаточное количество ненулевых пикселей на краях на изображении и если расстояние от любого ранее выбранного центра удовлетворяет заданному значению.

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

Рисунок 6-12. Преобразование Хафа для круга находит несколько кругов на тестовом шаблоне и (правильно) не находит ничего на фотографии

Во-первых, применение производных Собеля для вычисления локального градиента — и предположение, что он может быть рассмотрен как локальный тангенс — численно не стабильное решение. Он может давать верный результат «большую часть времени», при этом на выходе не исключено присутствие некоторого количества шума.

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

И наконец, поскольку центры рассматриваются в возрастающем порядке значений из накопителя и к тому же новые центры не добавляются, если они слишком близки к уже добавленным центрам, в случае концентрических кругов (либо около концентрических), предпочтение может отдаваться тем, у которых наибольший размер. (Указано «может» потому что существует некоторый шум, исходящий от производных Собеля; на гладком изображении с бесконечным расширением алгоритм будет определенным)

Принимая во внимание все выше сказанное, рассмотрим функцию OpenCV, которая реализует алгоритм Хафа для окружностей:

Функция преобразования Хафа для окружностей cvHoughCircles() имеет параметры, похожие на параметры в функции для линий. Исходное изображение должно быть 8-битным. Значительное отличие между cvHoughCircles() и cvHoughLines2() в том, что последняя функция запрашивает бинарное изображение. Функция cvHoughCircles() внутренне (автоматически) сама вызывает функцию cvSobel() (Внутренне вызывается функция cvSobel(), вместо cvCanny(). Это связано с тем, что cvHoughCircles() необходимо определить направление градиента для каждого пикселя, а это сложно выполнить для бинарной карты краев), поэтому вполне хватает и изображения в оттенках серого.

Аргумент circle_storage может быть либо массивом, либо хранилищем в памяти — зависит от предпочтений разработчика. Если массив, то он должен иметь одну колонку типа CV_32FC3; три канала используются для хранения значений положения и радиуса круга. Если хранилище в памяти, то окружности будут преобразованы в последовательности OpenCV, а функция cvHoughCircles() возвратит указатель на эту последовательность. (При указании в circle_storage указателя на массив, возвращаемым значением функции будет NULL). Аргумент method всегда должен быть равен CV_HOUGH_GRADIENT.

Аргумент dp является разрешением накопителя. Этот аргумент позволяет создавать накопитель более низких разрешений, чем исходное изображение. ((!)Есть смысл делать это, поскольку нет никаких оснований для существования окружностей, которые ровно подходят под количество категорий, таких как высота или ширина изображения сами по себе (!)). Если аргумент dp равен 1, тогда разрешение будет таким же, как и у исходного изображения; если аргумент dp больше 1, тогда разрешение будет в dp раз меньше (в случае dp = 2, будет половинным). Значение dp не может быть меньше 1.

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

Для применяемого (и требуемого на данный момент) метода CV_HOUGH_GRADIENT, следующие два параметра, param1 и param2, являются порогами для краев (Canny) и накопителя соответственно. В данном случае может смутить, что Canny сам по себе запрашивает два разных параметра для порогов. На самом деле внутренний вызов функции *cvCanny()*устанавливает в качестве верхнего порога значение равное param1, а нижний порог устанавливает равным половине величине param1. Параметр param2 применяется к накопителю в точно таком же смысле, как и параметр threshold для cvHoughLines().

Последние два параметра — это минимально и максимально возможные значения радиуса для окружностей, которые ищутся. Это означает, что они являются радиусами окружностей, для которых накопитель имеет представление. Пример 6-1 отражает пример использования функции cvHoughCircles().

Пример 6-1. Использование cvHoughCircles() для получения последовательности найденных окружностей на изображение в оттенках серого

Стоит заострить внимание на том, что независимо от все возможных применяемых приемов, описать окружности можно только при помощи трех степеней свободы (x, y и r), в то время как для линий достаточно только двух (ρ и θ). Как результат, алгоритм поиска окружностей, по сравнению с алгоритмом поиска линий, затрачивает на выполнение больше времени и памяти. Принимая во внимание данный факт, неплохо было бы ограничивать радиус окружности насколько это возможно в той или иной ситуации (Хотя cvHoughCircles() улавливает центры достаточно точно, он иногда не способен найти правильный радиус. Поэтому в приложениях, где требуется только нахождение центра (либо там, где для нахождения радиуса можно применить другие механизмы), величину радиуса, возвращаемую cvHoughCircles можно игнорировать). Преобразование Хафа было расширено произвольными формами Балларда в 1981, в основном рассматривая формы, как наборы градиентных граней.

🎬 Видео

Лекция 2. Обработка изображенийСкачать

Урок #3 Python / Распознавание контуров OpenCVСкачать

MATLAB 03 Написание программСкачать

Работа с файлами изображений и их типы в MatLabСкачать

Детектирование линий разметки. Часть 1 – алгоритм в MATLABСкачать