2.3.2. Кодирование изображений посредством преобразований

Кодирование изображений посредством преобразований достаточно подробно обсуждалось в литературе; хорошие обзоры по этому вопросу были представлены Уинтцем [5] и Хуангом и др. [10]. Главная цель такого кодирования состоит в переводе изображения в некоторую обратимую форму, более удобную для применения определенных методов кодирования. Обычно при этом получают данные с меньшей корреляцией, чем у элементов исходного изображения, и процесс сокращения полосы частот становится реализуемым с помощью кодеров без памяти, действующих в преобразованной области. При анализе изображений часто исходят из статистических характеристик второго порядка и предположения о стационарности, а для описания соответствующих процессов пользуются ковариационными матрицами.

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

(см. скан)

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

Рассмотрим отдельные строки табл. 2.1. Метод разложения по сингулярным значениям пригоден для применения только при условии, что на передающей стороне (у источника изображения) имеется возможность выполнить весьма большой объем вычислений, поскольку необходимо вычислить сингулярные векторы, которые однозначно определяются обрабатываемым изображением, и эти вычисления требуют в целом выполнения операций. Полученные сингулярные (или собственные) векторы, в которые в качестве постоянных входят собственные значения, пригодны теперь для кодирования и передачи. Вследствие обширных вычислений, необходимых для выполнения РСЗ, подобные методы практически пригодны только для запоминания изображений в мощных вычислительных системах. Усеченная форма выражаемая (2.19), является оптимальной с точки зрения среднеквадратичного приближения и обеспечивается только усеченным разложением по сингулярным значениям. Следовательно, если исходить из записи слов в машинную память с плавающей запятой (сохраняющей точность в противоположность записи в обычной кодовой форме), РСЗ оказывается единственным преобразованием, оптимальным в смысле среднеквадратичного критерия верности. При заданном К минимизируется следующее выражение:

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

где - двумерный разделимый оператор математического ожидания, который усредняет рассматриваемые разделимые статистические характеристики, описывающие данный тип изображения. Из предположения о разделимости вытекает требование, чтобы статистические характеристики по горизонтали и вертикали были разделимыми (которое отнюдь не обязательно удовлетворяется). Ковариационные матрицы, описывающие столбцовые (вертикальные) и строчные (горизонтальные) статистические характеристики, выражаются соответственно как Если для рассматриваемого класса изображений справедлива стационарная разделимая модель, то имеет смысл вычислять собственные векторы ковариационной матрицы (что выполняется однократно) с помощью большой вычислительной системы, удаленной от источника изображения и передатчика. Таким образом,

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

у источника изображения или передатчика. Для этой процедуры требуется выполнение арифметических операций, что составляет экономию в два раза по сравнению с методом РСЗ в расчете на одно изображение. Важно отметить, что двумерное преобразование Карунена — Лоэва, определяемое (2.32), дает в результате полную матрицу элементы которой таковы, что в среднем наибольшая часть энергии изображения сосредоточена в наименьшем количестве коэффициентов Разумеется, действительные характеристики алгоритма такого типа будут хорошими с точки зрения психофизики явлений зрительного восприятия лишь в той степени, в какой статистическая модель будет соответствовать передаваемому детерминированному изображению.

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

Поскольку такие матрицы преобразуются в диагональные с помощью синусов или косинусов соответствующей частоты и фазы [16], для дискретной аппроксимации разложения этого типа больше всего подходит косинусное преобразование, занимающее третью строку табл. 2.1. Дополнительное преимущество этого преобразования состоит в наличии быстрого алгоритма реализации операций вместо а также в том, что здесь не требуется разложение по собственным значениям. Таким образом, это преобразование является детерминированным и может служить основой для эффективной аппаратурной реализации (возможно, аналоговым методом). Косинусное преобразование не производит точной диагонализации дискретного марковского процесса, однако экспериментальная проверка показала, что результат довольно близок к статистическому оптимуму Карунена — Лоэва [11].

Если марковская модель не дает удовлетворительного описания статистических характеристик процесса генерирования изображений, но предположение о стационарности остается в силе, то сохраняют форму тёплицевых матриц. При больших матрицах отсчетов (больших и относительно быстром уменьшении корреляции между не слишком удаленными отсчетами изображения тёплицевы ковариационные матрицы могут быть хорошо аппроксимированы матрицами-циркулянта-ми, причем различия проявляются в конечных точках матриц:

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

где

диагональные матрицы, ненулевые элементы которых (собственные значения) определяются разложением в ряд Фурье первой строки циркулянта [2.7]. Таким образом, область двумерного преобразования Фурье может представлять интерес для кодирования изображений, поскольку в этой области стационарные тёплицевы процессы оказываются почти некоррелированными. В какой степени преобразование Фурье пригодно для декорреляции данных, определяется тем, как велико число

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

В строках 5—8 табл. 2.1 представлены наклонное преобразование, преобразование в дискретном линейном базисе, преобразования Уолша и Хаара. Каждое из этих преобразований имеет соответствующие статистические характеристики, описываемые разделимыми ковариационными матрицами вида

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

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

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

В последней строке табл. 2.1 помещен чисто пространственный метод двумерной ДИКМ, рассмотренный в предыдущем разделе. Для системы двумерной ДИКМ требуется лишь ячеек памяти и вычислительных операций. Очевидно, что при число требуемых операций для ДИКМ становится таким же, как для обычных методов быстрого преобразования. При получаем случай предсказания по полной матрице и число операций становится таким же, как при выполнении полномасштабного преобразования Карунена — Лоэва. Таким образом, преимущество метода ДИКМ состоит в наличии предсказателей низкого порядка (с малым которые производят эффективную декорреляцию данных и в то же время обеспечивают экономию в количестве вычислений и емкости памяти.

Выше были рассмотрены возможности использования различных преобразованных областей для получения менее коррелированных источников кодируемой информации, обеспечивающих сокращение полосы частот при передаче изображений. Практические алгоритмы кодирования не обсуждались, поскольку это выходит за рамки данной главы; заинтересованные читатели могут обратиться к работам [5, 8—17]. Пришлось также исключить различные дополнительные вопросы, связанные с кодированием изображения. Могло бы представить интерес наблюдение кодера при различных условиях работы канала, чтобы исследовать его характеристики при наличии шума. С другой стороны, на характеристики системы могут оказывать влияние дополнительные критерии, учитывающие аппаратурные ограничения и неидеальность синхронизации. Наконец, при проектировании системы кодирования изображения должен учитываться конечный получатель, т. е. наблюдатель с присущими ему параметрами.