Вадим Грибунин - Цифровая стеганография

Рис. 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].

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

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

А1. (Kutter[8]). Пусть изображение имеет RGB-кодировку. Встраивание выполняется в канал синего цвета, так как к синему цвету система человеческого зрения наименее чувствительна. Рассмотрим алгоритм передачи одного бита секретной информации.

Пусть s i - встраиваемый бит, I = {R,G,B} — контейнер, p = (x,y) — псевдослучайная позиция, в которой выполняется вложение. Секретный бит встраивается в канал синего цвета путем модификации яркости :