(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 7. Групповое кодирование изображений

Следует заметить, однако, что это преобразование уступает по эффективности четному косинусному преобразованию, которое имеет весьма широкое применение.

Выполнение двумерного преобразования Фурье при построении четных функциональных соотношений пристраиванием к блоку изображения его зеркальных отражений приводит к четному косинусному преобразованию [3.18, 3.38, 3.57]:

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

На рис. 7.8–7.12 приведены псевдотрехмерные изображения структур, образуемых базисными функциями двумерного косинусного преобразования и определяемыми соотношениями:

могут быть построены путем замены коэффициентов u на коэффициенты v и наоборот.

яркости пикселов преобразуемого блока изображения. Компоненты F [0, 1], F [1, 0]

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

˜ ˜ ˜ ˜ ˜ ˜

ными спектральными компонентами F [1, 1], F [2, 2], F [3, 3], F [4, 4], F [5, 5], F [6, 6]

˜

и F [7, 7].

На рис. 7.13 показаны псевдотрехмерные матрицы блока изображения, аналогичного рис. 7.6, спектра его косинусного преобразования и ошибок восстановления пикселов исходного блока.

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

Как следует из этой таблицы, косинусное преобразование имеет несомненные преимущества перед преобразованиями Хаара, Уолша–Адамара и синусным.

Таблица 7.2. Результаты статистических исследований ортогональных преобразований

Глава 7. Групповое кодирование изображений

мое преобразование Кархунена–Лоэва или Хотеллинга [3.17, 3.18, 3.36, 3.38, 3.39, 3.59, 3.60].

образования

7.1. Дискретные линейные ортогональные преобразования

косинусного преобразования

Рис. 7.13. Блок изображения 8 × 8 пикселов и его косинусное преобразование

Пусть имеется некоторый класс векторов {X}, компоненты которых коррелируют между собой. Необходимо построить некоторое ортогональное преобразование T , переводящее данный класс векторов в класс векторов {f }, компоненты которых имеют диагональную ковариационную матрицу, т. е. некоррелированы.

Пусть ковариационная матрица K{X} класса векторов {X} в терминах ее элементов определяется соотношением

Глава 7. Групповое кодирование изображений

k(i, j) = E{(xi − E{xi}) · (xj − E{xj })},

где E — оператор математического ожидания.

Тогда базисом преобразования Кархунена–Лоэва является система собственных векторов {tm}, таких, что

tm K{X} tTm = λm, tmtTn = δmn,

где λm — собственные значения диагональной ковариационной матрицы K{X} класса некоррелированных векторов {f }, δmn — символ Кронекера, K{f } =

= δimδjmλm .

Собственные значения λm имеют смысл квадратов величин соответствующих коэффициентов разложения векторов x по базису t, усредненному по всему классу {X}.

Несколько более подробно преобразование Кархунена–Лоэва было рассмотрено в материале части II.

Непосредственное применение преобразования Кархунена–Лоэва (ПКЛ) в прикладных программах сжатия изображений не осуществляется по причине невозможности разработки быстрого алгоритма его вычисления и связанных с этим проблем.

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

Именно по этой причине широкое распространение получило применение дискретного косинусного преобразования, поскольку оно дает результаты, близкие к результатам преобразования Кархунена–Лоэва. Это имеет теоретическое обоснование: косинусные функции хорошо аппроксимируют собственные векторы матрицы Теплица [3.46]:

Всвою очередь, эта матрица близка к ковариационным матрицам характерных телевизионных изображений.

Вкачестве подтверждения этого факта на рис. 7.14 приведены базисные функции Кархунена–Лоэва для изображения «Залив» (см. рис. 6.4) при N = 8 и базисные функции дискретного косинусного преобразования.

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

7.1.7. Другие виды преобразований

Возможно построение других видов унитарных преобразований. Так, например, известно ортогональное наклонное или слэнт-преобразование, которое обладает базисными функциями, имеющими вид кусочно-линейных функций [3.18, 3.61– 3.63]. При N = 2 наклонное преобразование совпадает с преобразованием Ада-

7.1. Дискретные линейные ортогональные преобразования

Рис. 7.14. Сравнение базисных функций преобразования Кархунена–Лоэва для конкрет-

где IK —единичная матрица K-го порядка; aN , bN определяются рекуррентно:

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

Унитарное преобразование может быть построено также на основе использования полиномовЛежандра

Например, для N = 8 матрица преобразования имеет вид, представленный в табл. 7.3.

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

Глава 7. Групповое кодирование изображений

Таблица 7.3. Матрица преобразования Лежандра для N = 8

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

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

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

В ряде исследований использовался метод гибридного преобразования, при котором сначала производилось одномерное косинусное преобразование отрезков строк, а затем над полученными коэффициентами осуществлялась вертикальная ДИКМ. Любопытно, что при достаточно глубоком квантовании (объем передаваемой информации менее 0,5 бита/пиксел) результат получился лучше, чем при применении двумерного косинусного преобразования (ДКП).

Однако с учетом того, что в большинстве случаев алгоритмы вычислений для N × N двумерных преобразований работают быстрее, чем для линейных порядка N 2, практическое применение находят именно двумерные преобразования.

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

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

Всамом общем случае процесс квантования — это осуществление нелинейного преобразования, характеристика которого имеет вид монотонной ступенчатой функции. Распределение величин шагов квантования можно оптимизировать, например, по среднеквадратичной ошибке для заданного распределения плотности вероятностей исходной функции и количества дискретных уровней (процедура Ллойда–Макса) [3.17, 3.18, 3.64, 3.65].

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

7.2. Квантование коэффициентов преобразования

Для этих случаев при большом числе уровней преобразования близким к оптимальному является квантование с равномерной шкалой в соответствии с формулой:

Fq = round(F/k),

где F и Fq — соответственно квантуемая и квантованная величины, k – коэффициент преобразования. При восстановлении изображения компоненты унитарных преобразований умножаются на коэффициент k. Этот алгоритм имеет наибольшее распространение в цифровой обработке сигналов.

Следует отметить, что при этом минимизируется среднеквадратичное отклонение восстановленного после обратного ортогонального преобразования T -изоб- ражения от исходного, поскольку [3.17]

=[k · Fq (u, v) − F (u, v)]2 = {k · round[F (u, v)/k] − F (u, v)}2.

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

max{abs[Xвых(i, j) − Xвх(i, j)]} min .

i,j

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

Как следует из этого рисунка, с ростом k увеличивается коэффициент сжатия и существенно возрастает заметность искажений.

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

При этом результаты унитарного преобразования подвергаются квантованию [3.17, 3.66–3.68] в соответствии с формулой:

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

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

Так, известна функция VHS (video home system) [3.69]: