Кафедра математической физики чекан ростислав владимирович методы параллелизации Гауссова фильтра при обработке растровых изображений

Минск 2010

АННОТАЦИЯ

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

АНАТАЦЫЯ

У дадзенай дыпломнай працы вывучаюцца розныя рэалізацыі фільтра Гаўса і робіцца іх параўнальны аналіз з параллелизацией аптымальнага метада.

ANNOTATION

Different implementations of the Gaussian filter are researched and comparative analysis was made in this thesis including parallelization of the optimal method.

РЕФЕРАТ

Отчёт по дипломной работе, 56 страниц, 7 источников, 2 приложения.

^ ФИЛЬТРА ГАУССА, РАЗМЫТИЕ ПО ГАУССУ, РЕКУРСИВНЫЙ АЛГОРИТМ, ПАРАЛЛЕЛИЗАЦИЯ, OPENCL

Объект исследования – реализации фильтра Гаусса.

Цель работы – исследовать существующие реализации алгоритмов фильтрации по Гауссу, выделить оптимальные, улучшить с помощью параллелизации.

Метод исследования – аналитический метод, практическая реализация.

Результатом работы является программа, которая позволяет посмотреть различные реализации фильтра Гаусса.

Содержание


Введение

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

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

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

Разработка и анализ алгоритмов для решения проблемы фильтрации цифровых сигналов будет являться предметом данной работы оптимальных по скорости на больших объёмах данных.

1. Фильтры

Цифровой фильтр — любой фильтр, обрабатывающий цифровой сигнал с целью выделения и/или подавления определённых частот этого сигнала. В отличие от цифрового, аналоговый фильтр имеет дело с аналоговым сигналом, его свойства не дискретны, соответственно передаточная функция зависит от внутренних свойств составляющих его элементов. Особую роль среди цифровых фильтров играют фильтры нижних частот (ФНЧ). ФНЧ – фильтр, эффективно пропускающий частотный спектр сигнала ниже некоторой частоты (частоты среза), и уменьшающий (или подавляющий) частоты сигнала выше этой частоты. Степень подавления каждой частоты зависит от вида фильтра. Широко применяется как аппаратная (на основе специализированных микросхем или FPGA), так и программная (на базе процессоров общего назначения или сигнальных процессоров) реализация фильтров нижних частот. Мы же будем рассматривать различные варианты программной реализации одного из ФНЧ - фильтра Гаусса.

^ 1.1 Фильтр Гаусса

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



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

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

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



^ 1.2 Базовый случай фильтра Гаусса

Импульсная характеристика одномерного фильтра Гаусса может быть представлена в виде:

.

А со среднеквадратичным отклонением:

.

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

.

где x -  расстояние от центра по горизонтальной оси, y - расстояние от центра по вертикальной оси, σ- среднеквадратичное отклонение распределения гаусса.

 Рассмотрим более общий случай. Результирующая формула будет иметь следующий вид для n-мерного случая:



Однако для реализации данное определение может быть нецелесообразным в виду непрерывности. Поэтому в дальнейшем можем сделать некоторые упрощения.

Так как гауссовское ядро обладает свойствами отделимости 

,

то n-мерная операция свёртки может быть разбита на множество одномерных применений гауссова ядра для каждого измерения:

, где

.

и где t является корнем дисперсии и равно σ².  Свойство отделимости на практике имеет большое значение, так как позволяет упростить вычисления и привести их к одномерному случаю. Далее будем рассматривать именно его.

Для реализации одномерного шага сглаживания наиболее простым способом является операция свёртки  дискретного сигнала и гауссового ядра:

,

где

.

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

,

для M выбрано достаточно большим, что:

.

Общий выбор выбора M заключается в создании зависимости её от дисперсии, к примеру:



где С зачастую выбирается где-то между 3 и 6.

Использование заданного гауссова ядра может привести к проблемам точности в случаях, когда важны точность и надёжность. При незначительной роли погрешности при вычислениях (10 ^{- 6} до 10 ^{- 8}) , ошибки вносимые ограничением ядра незначительны. Однако если точность важна, то есть более лучшие альтернативы гауссову ядру как оконной функции, к примеру, оконные функции Хэмминга, Блэкмана, Кайзера (см. [5]) будут меньше изменять спектр, чем это сделает ядро гаусса. А так как функция Гаусса быстро убывает на концах, то рассматривание значений на больше 10 ^{- 8} не является целесообразным.

^ 1.3 Применение фильтра Гаусса с помощью преобразования Фурье

1.3.1 Дискретное преобразование Фурье

Итак, вспомним, что же такое преобразование Фурье – это интегральное преобразование, которое ставит функцию вещественной переменой другую функцию вещественной переменной и может быть записано в виде:

.

Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами.

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

1. 
   Формула обращения позволяет получить искомую функцию
   

.

2. 
   Теорема о свёртке. Свёртка функций — операция, показывающая «схожесть» одной функции с отражённой и сдвинутой копией другой. Пусть   — две функции вещественной переменной, интегрируемые относительно меры Лебега. Тогда их свёрткой называется функция:
   

.

Тогда фильтр Гаусса есть не что иное как свёртка:



Тогда теорема о свёртке гласит: если , тогда

.

Так как мы работаем с изображениями, то представим перечисленные выше высказывания в дискретном виде. Прямое преобразование примет вид:

.

Обратное преобразование:

.

Теорема о свёртке:

.

Таким образом, мы можем выполнить частотную фильтрацию изображения в частотной области. Это означает, что при частотной фильтрации выполняются прямое и обратное пространственно-частотное преобразование, в нашем случае двумерное дискретное преобразование Фурье (ДПФ) преобразует изображение, заданное в пространственной координатной системе (x, y) , в двумерное дискретное преобразование изображения, заданное в частотной координатной системе (u, v). В соответствии с теоремой о свертке, свертка двух функций в пространственной области может быть получена ОДПФ произведения их ДПФ.

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

• 
  выполнить двумерное ДПФ входного изображения f(x,y) (подвергаемого фильтрации) размером (N *M), получить F(u,v);
  
• 
  вычислить передаточную характеристику фильтра Гаусса в частотной области
  

,

размер матрицы (N*M); выполнить децентрирование характеристики

H(u,v);

• 
  выполнить поточечное умножение
  

,

• 
  выполнить ОДФП
  

На практике ДПФ крайне не эффективно, так как имеет сложность O(N²), поэтому обычно применяют быстрое преобразование Фурье (БПФ).