Методы сегментации изображений на основе спектров Фурье

Последующее вычисление значений F (u) дает нам возможность определить частотный состав любого сигнала, используемого на практике, и открывает широкий спектр возможностей для анализа и обработки сигналов в физике и технике. Указанные преобразования можно легко распространить на функции двухпеременных, (26), (27)Для получения спектра изображения применяется ДПФ. На вход ДПФ подается дискретная функция, которая обычно создается путём дискретизации (выборки значений из непрерывных функций). Фактически, ДПФ позволяет представить дискретную функцию в виде конечного числа частот с определёнными значениями амплитуды и фазы (раскладывает функцию в её спектр). ДПФ (прямое) дискретной функции одной переменной f (x) задается следующим равенством, (28)По заданному Фурье-преобразованию F (u) можно восстановить исходную функцию при помощи обратного дискретного преобразования Фурье, (29)При рассмотрении дискретных последовательностей обычно оперируют номерами отсчетов и спектральных гармоник без привязки к действительному масштабу времени и частоты, т. е. считают частоту дискретизации равной единице. Поэтому u=0,1,2,…, M-1 — индекс в частотной области; x=0,1,2,…, M-1 — временной индекс входных отсчетов; F (u) — «u».

— й компонент дискретного преобразования Фурье, т. е. F (0), F (1), F (2) и т. д.; f (x) — последовательность входных отсчетов f (0), f (1), f (2) и т. д.; M — количество отсчетов входной последовательности и количество частотных отсчетов результата дискретного преобразования Фурье. Также возможна и тригонометрическая форма записи ДПФ, (30), (31)u=0,1,2,…, M-1; x=0,1,2,…, M-1. Таким образом, каждый элемент Фурье-преобразования (т.е. значение F (u) для каждого значения «u») состоит из суммы по всем значениям функции f (x). Из равенств (28, 30) видно, что элементы Фурье-образа в общем случае являются комплексными величинами. Как и в случае комплексных чисел, значения F (u) удобно иногда выражать в полярных координатах, (32)где — спектр Фурье-преобразования (33) — действительная часть (34) — мнимая часть (35) — фазовый спектр преобразования (36)По указанным формулам производится разложение сигнала в спектр. Энергетический спектр (спектр мощности), определяется как квадрат Фурье-спектра, (37)Спектр Фурье обладает следующими свойствами: 1) при увеличении вдвое площади под кривой в пространственной области высота спектра удваивается; 2) при увеличении вдвое размера носителя функции количество нулей спектра в заданном интервале удваивается. Наглядно указанные свойства приведены на рис. 6Рис.

6. (a) Дискретная M — точечная функция и (б) её фурье-спектр. (в) Дискретная функция с удвоенным числом ненулевых значений и (г) её Фурье-спектр.Дискретное прямое и обратное преобразования Фурье допускают непосредственное обобщение на двумерный случай. Прямое дискретное фурье-преобразование функции f (x, y) (изображения) размерами MxN задается равенством, (38)Как и в одномерном случае, это выражение должно быть вычислено для всех u=0,1,2,…, M-1 и также для всех v=0,1,2,…, N-1. Аналогично, по заданному фурье-преобразованию F (u, v), мы можем получить f (x, y) при помощи обратного преобразования Фурье, задаваемого выражением, (39)где х=0,1,2,…, M-1 и y=0,1,2,…, N-1. Равенства (38) и (39) составляют пару двумерных ДПФ (прямое и обратное).

Переменные «u» и «v» — частотные переменные, «х» и «у» — пространственными переменными или переменными изображения. Как и в одномерном случае, положение множителя MN 1 не имеет значения. Он может быть отнесен в обратное преобразование или разделен на два равных сомножителя 1/√(MN) в прямом и обратном преобразованиях. Фурье-спектр, фаза и энергетический спектр определяются аналогично, (40), (41), (42)где величины Re (F (u, v))иIm (F (u, v)) обозначают действительную и мнимую части величины F (u, v) соответственно. Обычной практикой является умножение исходной функции (изображения) на (-1)x+y перед вычислением Фурье-преобразования для центровки спектра, т. е., (43)где — обозначает преобразование Фурье своего аргумента. Это равенство означает, что начало координат для Фурье-преобразования функцииf (x, y)(-1)x+y (т.е. та точка, где значение этого преобразования равно F (0,0)) находится в точке с координатами u=M/2, v=N/2. Другими словами, умножение функции f (x, y) на величину (-1)x+y приводит к сдвигу начала координат для её образа F (u, v) в точку с частотными координатами (M/2, N/2), которая является центром прямоугольной области размером (MxN), занимаемой двумерным дискретным фурье-преобразованием. Будем говорить об этой области в частотном пространстве как о частотном прямоугольнике. Он простирается от u=0 до u=M-1 и от v=0 до v=N-1 («u» и «v» целые).

Как следует из формулы (38), значение преобразования в точке (u, v)=(0,0) равно, (44)т.е. среднему значению функции f (x, y). Другими словами, если f (x, y) — изображение, то значение фурье-преобразования в начале координат равно среднему значению яркости на изображении. Для упрощения вычисления двумерного преобразования Фурье, применяется метод вычисления посредством одномерных преобразований. Для этого необходимо разделить переменные в ДПФ (38) следующим образом, (45)где, (46)При каждом значении «x» (и при v = 0,1, 2,…, N-1) последнее выражение является полным одномерным фурье-преобразованием. Другими словами, F (x, y) есть фурье-преобразование одной строки функции f (x, y).

При изменении «х» от 0 до «М-1», получаем фурье-преобразования по всем строкам функции f (x, y). Для получения полного двумерное преобразования, необходимо изменять значения переменной «u» в равенстве (45) диапазоне от 0 до «М-1», что повлечет вычисление одномерного преобразования по каждому столбцу функции F (x, v). Таким образом, для вычисления двумерного преобразования можно сначала вычислить одномерные преобразования по каждой строке исходного изображения, а затем вычислить одномерные преобразования по каждому столбцу полученного промежуточного результата. Изменение порядка вычислений (сначала по столбцам, потом по строкам) не изменит результат. Указанный метод применим и для вычисления двумерного обратного преобразования Фурье: сначала производится вычисление обратного преобразование по каждой строке функции F (u, v), после — вычисление обратного преобразование по каждому столбцу полученного промежуточного результата. Библиотека OpenCV как база для написания практических приложений систем компьютерного зрения.

Дляобъединенияусилийвобластиинтеллектуальнойобработкиграфическойинформациибыласозданасвободнораспространяемая библиотека элементов компьютерного зрения «OpenCV» (OpenSourceComputerVisionLibrary), которая реализована на языке программирования «C++» и имеет APIдля работы с ней в средах программирования на языках «Java"и «Piton» под управлением различных операционных систем. Библиотека «OpenCV» содержит алгоритмы для: интерпретации изображений, калибровки камеры по эталону, устранение оптических искажений, определение сходства, анализ перемещения объекта, определение формы объекта и слежение за объектом, 3D-реконструкция, сегментация объекта, распознавание жестов и т. д.Популярность данной библиотеки обусловлена открытостью кода, что позволяет бесплатно ее использовать как в учебных, так и коммерческих целях. Основными модулями библиотеки являются:

1) «cxcore» — ядро, содержащее базовые структуры данных и алгоритмы: — базовые операции над многомерными числовыми массивами— матричная алгебра, математические ф-ции, генераторы случайных чисел— Запись/восстановление структур данных в/из XML— базовые функции 2D графики2) «CV» — модуль обработки изображений и компьютерного зрения, который содержит: — базовые операции над изображениями (фильтрация, геометрические преобразования, преобразование цветовых пространств и т. д.) — анализ изображений (выбор отличительных признаков, морфология, поиск контуров, гистограммы) — анализ движения, слежение за объектами— обнаружение объектов, в частности лиц— калибровка камер, элементы восстановления пространственной структуры3) «Highgui» — модуль для ввода/вывода изображений и видео, создания пользовательского интерфейса, позволяющий: — захват видео с камер и из видео файлов, чтение/запись статических изображений.— функции для организации простого UI (все демоприложения используют HighGUI)4) «Cvaux» — экспериментальные и устаревшие функции— пространств. зрение: стерео калибрация, само калибрация— поиск стерео-соответствия, клики в графах— нахождение и описание черт лица5) «CvCam» — захват видео— позволяет осуществлять захват видео с цифровых видео-камер (поддержка прекращена и в последних версиях этот модуль отсутствует) Таким образом, библиотека «OpenCV» предлагает реализованные наиболее популярные алгоритмы для работы с изображениями, в том числе, алгоритмы сегментации, что позволяет исследователю быстро изменять программный код под конкретную задачу, не тратя много времени на «изобретение велосипеда» — программную реализацию и отладку давно известного алгоритма. Разработка алгоритма сегментации на основе преобразования Фурье.

Как было сказано ранее, для получения спектра изображения надо взять одномерное преобразование Фурье от каждой строки изображения, а после проделать то же самое с каждым столбцом из полученных данных. В качестве изображения возьмем черно-белое изображение, где в качестве параметра «частота» будет приниматься значение яркости пикселя в диапазоне [0.255]. Предлагаемый алгоритм основывается на резком изменении частоты на границе объекта. Под резким изменением частоты будем понимать значения частоты в половину предыдущего значения. Для получения центрированного ДПФ необходимо исходное изображение умножить на (-1)x+y, после чего вычислить прямое ДПФ изображения. Прямое ДПФ изображения (функции f (x, y)) размерами MxN задается равенством:

Для упрощения вычислений, воспользуемся ранее описанным способом разделения двумерного ДПФ посредством одномерных ДПФ по равенствам (45) и (46).Для создания функцииh (x, y), представляющей собой функцию фильтра по частотным перепадам, необходимо получить дискретную функцию значений частоты для каждого пикселя в строке, затем выполнить аналогичные действия для каждого столбца, при этом сравнивая разность частоты предыдущего значения пикселя с текущим. При условии, если разность частот меньше половины значения предыдущего пикселя, значениеh (x, y) в данном случае равняется 0, в противном случае присваиваем h (x, y) равным 1. Далее, берем ДПФ функции h (x, y), по аналогичному способу, приведенному в равенстве (45), (46).После проведенных вычислений, функция F (u, v) умножается на полученную функцию H (u, v).Умножение функций двух переменных H и F осуществляется поэлементно, т. е. первый элемент функции H умножается на первый элемент функции F, второй элемент функции H — на второй элемент функции F, и т. д. В этом случае и действительная, и мнимая части функции F умножаются на одну и ту же действительную функцию фильтра H, так как функция Hне меняет фазы функции Фурье-преобразования. В общем случае, формула данного этапа выглядит так: G (u, v)= H (u, v) F (u, v) Конечное изображение получается вычислением обратного преобразования Фурье от фурье-образа G (u, v), а также умножения полученного результата на (-1)x+y, для компенсирования первоначального эффекта от умножения изначального изображения на ту же величину. Блок-схема предлагаемого алгоритма приведена на рис. 7.Рис. 7 Блок схема алгоритма. Сравнение алгоритма с алгоритмом пороговой сегментации. Отличие предлагаемого алгоритма сегментации от алгоритма пороговой сегментации заключается в том, что в алгоритме пороговой сегментации выбирается некоторое пороговое значение, которое может быть слишком высоким, что автоматически отсечет границы объектов с более низким показателем яркости. Наглядный пример вышесказанного приведен на рис.

8.Рис. 8. Пример работы алгоритма пороговой сегментации с автоматическим подбором оптимального значения порога.

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

Заключение

.

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

Грузман И.С., Киричук В. С., Косых В. П., Перетягин Г. И., Спектор А. А. Цифровая обработка изображений в информационных системах: Учебное пособие.

Новосибисрк: Изд-во НГТУ, 2002. — 352 c. Известия ВУЗов. Приборостроение. 2013. Т.

56, № 5. С. 63−70. Фисенко.

В. Т., Фисенко. Фрактальные методы сегментации текстурных изображений. Лукин А. В. «Введение в цифровую обработку сигналов (математические основы)» / А. В. Лукин. — М.: МГУ, 2007. — 54 с.Спиридонов.

К. Н. Методы цифровой обработки изображений. Учебное пособие /К. Н. Спиридонов- Петрозаводск:

Петр

ГУ, 2012. — 30 с. Статья «Эффективная сегментация изображений на графах» ;

http://habrahabr.ru/post/81 279/ - Режим доступа:

http://habrahabr.ru. — Заглавие с экрана. — (Дата обращения: 10.

12.2015). Статья «Выделение и описание областей» ;

http://wiki.technicalvision.ru/index.php/Выделение_и_описание_областей — Режим доступа:

http://wiki.technicalvision.ru/. — Заглавие с экрана. — (Дата обращения: 8.

12.2015). Статья «Фрактал» ;

https://ru.wikipedia.org/фракталРежим доступа: :

http:// u.wikipedia.org. — Заглавие с экрана. — (Дата обращения: 8.

12.2015). Статья «Опыт использования преобразования Фурье для обнаружения объектов на изображении» ;

http://www.science-education.ru/106−8081- Режим доступа:

http://www.science-education.ru. — Заглавие с экрана. — (Дата обращения: 11.

12.2015).