5.1.2. Принципы сжатия изображений

5.1.2. Принципы сжатия изображений

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

— пространственная, или корреляция между соседними пикселами;

— спектральная, или корреляция между соседними частотными полосами;

— временная, или корреляция между соседними кадрами (для видео).

Велика ли статистическая избыточность в неподвижном изображении? Для ответа на этот вопрос попробуйте сжать картинку каким-либо архиватором — результаты вас разочаруют. Высокие коэффициенты сжатия достижимы лишь с использованием психовизуальной избыточности изображения, то есть пренебрежения его визуально незначимыми частями. И тут уж не обойтись без знания системы человеческого зрения. «Выброшенные» части изображения заменяют нулями (константами), и если их много — применяют кодер длин серий. В реальных алгоритмах сжатия осуществляют обнуление не пикселов изображения, а спектральных коэффициентов. Преимущество такого подхода заключается в том, что близкие к нулю спектральные коэффициенты имеют тенденцию располагаться в заранее предсказуемых областях, что приводит к появлению длинных серий нулей и повышению эффективности кодирования. Большие по величине коэффициенты («значимые») подвергают более или менее точному квантованию и также сжимают кодером длин серий. Последним этапом алгоритма сжатия является применение энтропийного кодера (Хаффмана или арифметического).

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

, (5.1)

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

, (5.2)

где 255 — максимальное значение яркости полутонового изображения (т. е. 8 бит/пиксел). Восстановленное изображение считается приемлемым, если ПОСШ >= 28–30 дБ (в среднем). Перечисленные объективные меры искажения не всегда коррелируют с субъективным восприятием изображений, однако ничего лучшего до сих пор не придумано.

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

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

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

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

Стандарт сжатия JPEG является в настоящее время наиболее распространенным и своеобразным «benchmark`ом» для алгоритмов ЦВЗ (то есть устойчивость системы ЦВЗ к сжатию JPEG проверяется обычно в первую очередь). В соответствии с этим стандартом изображение разбивается первоначально на блоки 8х8 элементов, к каждому из которых применяется дискретное косинусное преобразование (ДКП). Назначением ДКП является осуществление перераспределения энергии: значимые коэффициенты группируются в левом верхнем углу квадрата спектральных коэффициентов, так как соседние пикселы изображения коррелированы. Далее следуют равномерное табличное квантование коэффициентов, кодирование длин серий и кодирование Хаффмана.

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

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

Одним из наиболее естественных способов является учет взаимосвязей между коэффициентами из различных субполос. В высокочастотных субполосах имеются обычно большие области с нулевой или малой энергией. Области с высокой энергией повторяют от субполосы к субполосе свои очертания и местоположение. И это неудивительно — ведь они появляются вокруг контуров в исходном изображении — там, где вейвлет-преобразование не может адекватно представить сигнал, что приводит к «утечке» части энергии в ВЧ субполосы. Медленно изменяющиеся, гладкие области исходного изображения хорошо описывают НЧ вейвлет-базисы, что приводит к «упаковке» энергии в малом числе коэффициентов НЧ области. Этот процесс примерно повторяется на всех уровнях декомпозиции, что и приводит к визуальной «похожести» различных субполос.

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

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

Впервые идея нульдерева была предложена в работе [3]. В их алгоритме применялась древовидная структура данных для описания вейвлет-коэффициентов (см. рис. 5.2).

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

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

Квантование нульдеревом основано на наблюдении, что если коэффициент мал, его отпрыски на дереве зачастую тоже малы. Это объясняется тем, что значимые коэффициенты возникают вблизи контуров и текстур, которые локальны. Нетрудно увидеть, что это является разновидностью предсказания. Можно предположить, что если какой-либо коэффициент незначимый, то все его потомки также будут незначимыми. Дерево или субдерево, которое содержит (по крайней мере, так предполагается) только незначимые коэффициенты, называется нульдеревом.

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

Данный алгоритм является эффективным в силу двух причин. Во-первых, в силу хорошей «упаковки» энергии вейвлет-преобразованием и, во-вторых, за счет совместного кодирования нулей. Для кодирования нулей обычно применяется кодер длин серий. Для повышения эффективности на вход этого кодера коэффициенты должны подаваться в определенном порядке. Например, в JPEG применено зигзагообразное сканирование. Наверное, наиболее важным вкладом этой работы была демонстрация того, что область вейвлет-коэффициентов прекрасно приспособлена для работы кодера длин серий. В самом деле, генерируются большие серии нулей и не надо передавать их длину, так как высота дерева известна. Аналогично JPEG, данный алгоритм является разновидностью скалярного/векторного квантования. Каждый (значимый) коэффициент квантуется отдельно, а символы, соответствующие малым коэффициентам, образуют вектор. Этот вектор состоит из символа нульдерева и последовательности нулей длиной до конца дерева.

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

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

Для передачи информации о позициях значимых коэффициентов известен исключительно эффективный алгоритм «вложенного нульдерева» (EZW) [4], а также его разновидности — SPIHT [5] и другие.

Стандарт JPEG хорошо пригоден для сжатия изображений в 30–40 раз. При более сильном сжатии качество резко падает. Эта и множество других причин послужило причиной разработки нового стандарта на сжатие изображений — JPEG-2000. В новом стандарте реализованы такие опции, как последовательная передача, кодирование конкретного интересующего блока изображения, его масштабируемость, защищенность от ошибок передачи, произвольный доступ к сжатому изображению. В стандарте JPEG-2000 в качестве первичного преобразования применяется вейвлет-преобразование. Вейвлет-коэффициенты подвергаются квантованию по алгоритму, известному как «иерархическое кодирование блоков с оптимизированным усечением» (EBCOT), предложенному в работе [6]. Основное отличие этого алгоритма от EZW и SPIHT заключается в том, что EBCOT работает с независимыми неперекрывающимися блоками, которые кодируются итеративно. Таким образом вместо структуры данных нульдерева здесь используется структура квадродерева. В результате получается многоуровневый легко масштабируемый поток бит. Каждый уровень соответствует какой-то степени искажения. Распределение бит между уровнями осуществляется решением оптимизационной задачи с применением метода множителей Лагранжа [7].

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

Данный текст является ознакомительным фрагментом.