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

Глава 4. Статистическая избыточность дискретизированных данных

Однако парная статистическая корреляция может быть устранена использованием ортогонального линейного преобразования Кархунена–Лоэва (ПКЛ) или Хотеллинга [2.72–2.76]. Это преобразование позволяет оценить предельные степени сжатия информации, достижимые за счет снижения корреляции компонент.

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

Вычисление матрицы преобразования ПКЛ осуществляется следующим образом.

Предположим, в изображении имеется M блоков по N пикселов, значения которых равны bnm (1 n N ; 1 m M ).

Первоначально рассчитывается ковариационная матрица R = R ij , элементы которой равны

Вычисление собственных значений обычно осуществляется итерационными методами.

для 1 k N равен нулю, вычисление коэффициентов преобразования осуществляется следующим образом.

Первоначально один из коэффициентов, например t1k, фиксируется, скажем, t1k = 1, количество уравнений при каждом значении k сокращается на одно, и они

4.4. Кодирование с преобразованием

вычисляются путем решения системы N − 1 линейных уравнений величины t2k,

t3k, . . . , tN k.

Затем вычисляются координаты коэффициентов преобразования путем нор-

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

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

Например, предположим, что коэффициенты ПКЛ (c1, . . . , cN ) упорядочены по убыванию собственных значений λ1 · · · λN . Также предположим, что из соображений сокращения объема передаваемой информации передаче подлежат только первые pN коэффициентов (0 p 1).

В этом случае в приемнике используется усеченное количество коэффициентов (c1, . . . , cpN , 0, . . . , 0) и в результате преобразования вычисляются значения пикселов (b1, . . . , bN ).

Можно показать, что при этом среднеквадратичная ошибка преобразования

Таким образом, ПКЛ минимизирует среднеквадратичную ошибку преобразования [2.4].

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

На базе применения ДКП построен алгоритм JPEG, являющийся стандартом кодирования полноцветных изображений [2.77–2.80].

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — Международной организации по стандартизации.

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

Существует специальная реализация JPEG без потерь — Lossless JPEG. Стандарт Lossless JPEG ориентирован на полноцветные 24-битные или 8-бит-

ные в градациях серого изображения без палитры. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений.

Глава 4. Статистическая избыточность дискретизированных данных

4.4.1.Статистика монохромных изображений без преобразования

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

Статистика этих реализаций нестационарна и сильно изменяется в различных изображениях [2.4, 2.56, 2.81]. Так, для конкретного изображения статистика распределения уровней яркости может быть существенно неравномерной, и ее использование для кодирования, например, кодами переменной длины может обеспечить существенное сжатие изображений.

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

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

Более эффективно использование блочных и условных статистик отдельных изображений. Исследования различных изображений показывают:

–при увеличении размера блока энтропия на один пиксел уменьшается;

–условные энтропии с увеличением количества условий уменьшаются;

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

Следует заметить, что при 8-битовой информации о значении уровней пикселов для конкретного изображения трудно построить достоверную статистику высокого порядка, поскольку ограничено число пикселов. Так, например, при оценке вероятности блока, состоящего только из трех пикселов, число возможных уровней составляет (28)3 = 224, а количество пикселов в изображении с числом пикселов в строке, равным 720, и с числом строк, равным 540, определяется неравенством 720 × 540 < 219.

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

где τx = x2 − x1 — сдвиг вправо, τy = y2 − y1 — сдвиг вниз, τt = t2 − t1 — сдвиг во времени от пиксела (x1, y1, t1) к пикселу (x2, y2, t2) динамического изображения.

Автоковариационная функция изображения определяется как

K(x1, y1, t1; x2, y2, t2) =

= E{[b(x1, y1, t1) − E(b(x1, y1, t1))] · [b(x2, y2, t2) − E(b(x2, y2, t2))]}, (4.36) где E(b(x, y, t)) — средние значения яркостей пикселов изображения.

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

4.4. Статистика монохромных и цветных изображений

от того, в каких блоках изображения она вычисляется:

R(x1, y1, t1; x2, y2, t2) = R(τx, τy , τt);

(4.37)

K(x1, y1, t1; x2, y2, t2) = K(τx, τy , τt).

Величина K(0, 0, 0) определяет дисперсию процесса. Нормализованная автоковариационная функция

ρ(τx, τy , τt) = K(τx, τy , τt)/K(0, 0, 0)

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

зультат преобразования Фурье его автокорреляционной функции [2.83–2.88]:

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

Для упрощения вычислений пространственную автокорреляционную функцию представляют в виде произведения автокорреляционных функций для каждой пространственной переменной:

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

Весьма часто нормализованную автоковариационную функцию аппроксими-

где коэффициенты αx, αy , αt характеризуют корреляционные свойства изображения соответственно между пикселами в одной строке, между строками и между кадрами (полями).

Если расстояние между пикселами в строке обозначить τx = nT0, между строками τy = mTстр, а между кадрами (полями) τt = pTк(п), то это соотношение

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

Относительный энергетический спектр рассматриваемого процесса можно пред-

Глава 4. Статистическая избыточность дискретизированных данных

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

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

Это приводит к тому, что быстро движущиеся объекты в каждом отдельном кадре оказываются сильно размытыми, как показано на рис. 4.8.

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

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

4.4. Статистика монохромных и цветных изображений

Рис. 4.9. Смещение изображений в смежных полях при чересстрочной развертке

4.4.2.Статистика монохромных изображений

спреобразованием

Статистики (особенно второго или более высоких порядков) сигналов в кодерах с предсказанием имеют существенно меньшие зависимости от изменения изображения [2.4, 2.56].

Они почти всегда могут быть охарактеризованы Лапласовым распределением

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

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

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

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

Глава 4. Статистическая избыточность дискретизированных данных

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

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

–сокращается количество передаваемых коэффициентов;

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

Исследования показали, что при широко используемых унитарных преобразованиях (Фурье, косинусного, Уолша–Адамара и др.) все коэффициенты преобразований, кроме первого, имеют Лапласово распределение плотностей вероятностей, что может быть использовано для выбора алгоритма квантования.

4.4.3. Статистика цветных изображений

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

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

По мере уменьшения окраски корреляции между сигналами R, G и B возрастают.

Эти корреляции практически могут быть оценены с использованием, например, преобразования Кархунена–Лоэва. При этом большая часть энергии будет сосредоточена в одной из компонент.

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

Результаты применения преобразования Кархунена–Лоэва к ряду тестовых изображений подтверждают, что используемые на практике комбинации сигналов основных цветов — YIQ (NTSC) и YUV (PAL, SECAM) имеют близкое к оптимальному распределение мощности, при том что большая часть этой мощности приходится на сигнал яркости [2.4, 2.81]. Этот факт иллюстрируется табл. 4.16.

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

Так, в системе NTSC ширина полос сигналов I и Q составляет соответственно 36% и 12% от ширины полосы сигнала яркости, и цифровой поток может

4.5. Кодирование с сокращением объема передаваемой информации

Таблица 4.16. Распределение мощности по компонентам

быть уменьшен по сравнению с потоком данных сигнала яркости Y до [(0,36)2 + (0,12)2] ×100 = 14% просто за счет прореживания и передискретизации массивов величин I и Q в 0,36 и 0,12 раз соответственно сначала по горизонтали, а затем по вертикали.

Есть и дополнительные резервы сокращения относительного объема информации о цветности [2.69, 2.89]:

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

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

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

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

Измерения показывают [2.4, 2.89], что корреляция между компонентами Y, U, V в кодере с преобразованием практически отсутствует (за исключением специфической пространственной корреляции при резких переходах цвета).

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

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

В этом случае ˆ максимальна, если все возможные символы равноверо-

I(Ψ, Ψ) Ψ

ятны. Следовательно, если множество символов Ψ имеет J возможных членов, то

или J = 2N ·C . Таким образом, множество символов Ψ может быть использовано для передачи двоичных слов длины N · C битов, и передача происходит со скоростью C бит/пиксел. Если канал шумит, передача информации со скоростью, близкой к C, еще возможна, но в кодер канала необходимо включать коды исправления ошибок.

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

Для неискаженной передачи информации энтропия источника H(b) должна быть меньше энтропии потока на выходе кодера H(Φ), которая, в свою очередь, должна быть меньше емкости канала:

Однако во многих ситуациях требование ˆ не является ни необходимым, b = b

ни экономичным. В этом случае кодер источника должен производить оценку информации b и создавать символ Φ с энтропией, меньшей, чем H(b).

При H(Φ) < H(b) кодирование источника необратимо и получаемая инфор-

мация ˆ не всегда равна информации источника b. Таким образом, можно прийти b

к ошибке передачи ˆ , параметры которой (например, среднее значение, d(b, b)

среднеквадратичное отклонение и др.) могут быть мерой общей работы системы связи.

Естественным представляется требование ограничения усредненного парамет-

границы емкости канала R(D) очевидно выполнение неравенства C R(D), где C — потенциальная емкость канала без помех.

Шеннон показал [2.2], что при соответствующем кодировании источника и канала величину C можно сделать сколь угодно близкой к R(D).