ГЛАВА 1. ВВЕДЕНИЕ

(Т. С. Хуанг)

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

Существуют три основные области обработки изображений [1.1]: эффективное кодирование, реставрация и улучшение визуального качества изображений, распознавание образов. Многие методы реставрации и улучшения визуального качества изображений основаны на использовании линейных пространственно-инвариантных (ЛПИ) фильтров. Такие фильтры подробно рассмотрены в [1.1, 1.2]. Преобразования и связанные с ними методы позволяют построить эффективную с вычислительной точки зрения реализацию ЛПИ-фильтров. Многие преобразования полезны также при эффективном кодировании и выделении признаков в распознавании образов.

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

В следующих разделах более подробно обсуждается содержание глав этой книги.

1.1. Преобразования

Различные двумерные преобразования рассматривались с единых позиций (на основе понятия внешнего произведения) в [1.2, гл. 2]. Более детальное обсуждение некоторых из них можно найти в [1.3]. Среди этих преобразований наиболее широко применяется, несомненно, преобразование Фурье. Другие полезны главным образом в кодировании изображений и отчасти — в задачах распознавания. Опыт последних лет показал, что среди независимых от изображений преобразований (в эту категорию не входит преобразование Карунена — Лоэва) наилучшие результаты в

кодировании изображений дают дискретное косинусное преобразование (ДКП) и слэнт-преобразование. Как показано в [1.4], с теоретической точки зрения ДКП асимптотически оптимально для всех марковских сигналов конечного порядка. Джейн недавно ввел новое семейстзо унитарных преобразований, которое включает многие известные преобразования, такие, как ДКП [1.5].

Разложение по сингулярным значениям (РСЗ) и его приложения достаточно глубоко рассмотрены в [1.2, гл. 1, 2]. Недавно было проведено сопоставление поведения сингулярных значений с автокорреляционной функцией изображения [1.6]. Разработан новый метод подавления шума при реставрации изображений посредством РСЗ [1.7].

Обычный метод вычисления ДКП состоит в использовании быстрого преобразования Фурье [1.8, 1.9]. Однако новейшие быстрые алгоритмы обещают увеличение скорости в шесть раз [1.10].

Для выполнения двумерных преобразований, таких, как преобразование Фурье или Адамара, на ЭВМ, чья память на магнитных сердечниках не позволяет хранить изображение целиком, необходима дополнительная память. При этом обычно используется транспонирование матриц. Эффективный алгоритм транспонирования матриц был предложен в 1972 г. Эклундом [1.11]. Несколько позже он разработал два новых алгоритма и получил некоторые результаты по оптимальной стратегии [1.12] (см. также [1.13]). С другой стороны, двумерное дискретное преобразование Фурье (ДПФ) и аналогичные ему преобразования можно выполнять и без транспонирования матриц [1.14-1.18].

Интересной новой областью исследований является использование теоретико-числовых методов в обработке сигналов. Первым, кто предложил применить теоретико-числовые преобразования (ТЧП) (например, преобразования по числам Ферма) для вычисления быстрой двумерной свертки, был Рейдер. Блестящим введением в эту идею является раздел, написанный им в [1.24]. Детальное изложение можно найти в [1.25, 1.26].

Используя ТЧП, заметную экономию вычислений можно получить в тех случаях, когда: 1) одномерные последовательности, подлежащие обработке, относительно коротки; 2) необходима значительная точность и 3) операции умножения дороже операций сложения.

Виноград применил теоретико-числовые методы к вычислению ДПФ [1.27-1.30]. При этом число умножений значительно снижается по сравнению с БПФ, а число сложений почти не меняется. Например, для 1024-точечной последовательности БПФ требует 12 288 умножений и 26 624 сложений, тогда как алгоритм Винограда преобразования Фурье (АВПФ) для 1008 точек требует 4212 умножений и 25 224 сложений. Дополнительные сведения и соображения по программной реализации можно найти в [1.31-1.34].

АВПФ реализован в быстродействующем процессоре обработки сигналов [1.35]. Ошибки квантования (обусловленные округлением и квантованием коэффициентов) при ВПФ для случая вычислений с фиксированной запятой изучались в [1.36]. Было обнаружено, что в общем случае при той же ошибке вычислений АВПФ требует для представления данных на 1—2 бита больше, чем алгоритм БПФ.

Материал по преобразованиям в книге разделен на две части: алгоритмы транспонирования матриц и теоретико-числовые методы. В гл. 2 обсуждаются некоторые эффективные алгоритмы транспонирования матриц, а также прямой метод преобразования Андерсона [1.14]. В гл. 3 описываются быстрые алгоритмы цифровой свертки и преобразования Фурье, основанные на полиномиальных преобразованиях. В некоторых алгоритмах используется комбинация полиномиальных преобразований и алгоритма Винограда. Подробный вывод АВПФ приведен в гл. 4.