Цифровая стеганография

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

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

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

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

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

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

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

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

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

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

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

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