УДК 004.932.4

Сборник материалов пятой всеукраинской научнотехнической конференции студентов, аспирантов и молодых ученых "Комп'ютерний моніторінг та інформаційні технології (КМІТ - 2009)". Донецк, ДонНТУ - 2009. - с. 126-127

Исследование эффективности параллельной реализации быстрого преобразования Фурье для цифровых изображений

 

Смоляная Д.В., Костюкова Н.С.

Донецкий национальный технический университет

 

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

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

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

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

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

 

Процедура фильтрации изображения, основанная на преобразовании Фурье, содержит следующие шаги[2]:

1)     прямое преобразование Фурье;

2)     анализ спектра сигнала по Фурье образу и выбор типа фильтра и его параметров;

3)     генерация фильтра и его применение к Фурье образу;

4)     обратное преобразование Фурье для получения отфильтрованного изображения.

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

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

Существуют алгоритмы, позволяющие решать эту задачу, не прибегая к ее увеличению[3].

1)     Алгоритм Кули - Тьюки быстрого преобразования Фурье

2)     Алгоритм Кули - Тьюки по основанию два

3)     Алгоритм Гуда - Томаса быстрого преобразования Фурье

4)     Алгоритм Герцеля

5)     Вычисление преобразования Фурье с помощью свертки

6)     Алгоритм Винограда для быстрого преобразования Фурье малой длины

 

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

 

Литература

[1] Прэтт У. Цифровая обработка изображений: Пер. с англ.—М.: Мир, 1982.— Кн.1—312 с, ил.

[2] Р. Гонсалес, Р. Вудс Цифровая обработка изображений Москва: Техносфера, 2005. – 10727с.

[3] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов Москва «Мир» 1989