ДонНТУ   Портал магистров

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

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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] равно:

θ(L[i][j]) = j*dθ,

где dθ = 2*PI/m.

Таким образом, если на прямой линии с заданными параметрами 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 Применимость преобразования Хафа

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

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

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

Выводы

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

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

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

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

  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.

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

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