Вадим Грибунин - Цифровая стеганография
Для каждого из коэффициентов самой НЧ области существует три таких дерева, соответствующих трем порядкам фильтрации.
Квантование нульдеревом основано на наблюдении, что если коэффициент мал, его отпрыски на дереве зачастую тоже малы. Это объясняется тем, что значимые коэффициенты возникают вблизи контуров и текстур, которые локальны. Нетрудно увидеть, что это является разновидностью предсказания. Можно предположить, что если какой-либо коэффициент незначимый, то все его потомки также будут незначимыми. Дерево или субдерево, которое содержит (по крайней мере, так предполагается) только незначимые коэффициенты, называется нульдеревом.
В работе [3] был предложен следующий алгоритм квантования вейвлет-коэффициентов. Вначале каждый узел квантуется квантователем, оптимальным для плотности распределения Лапласа. Если значение узла меньше некоторого порога, его потомки игнорируются. Эти потомки будут восстановлены декодером как нули. Иначе осуществляется переход к четырем отпрыскам узла, и процедура повторяется. Если узел не имеет отпрысков (является листом), начинает обрабатываться следующий корневой узел и т. д.
Данный алгоритм является эффективным в силу двух причин. Во-первых, в силу хорошей «упаковки» энергии вейвлет-преобразованием и, во-вторых, за счет совместного кодирования нулей. Для кодирования нулей обычно применяется кодер длин серий. Для повышения эффективности на вход этого кодера коэффициенты должны подаваться в определенном порядке. Например, в JPEG применено зигзагообразное сканирование. Наверное, наиболее важным вкладом этой работы была демонстрация того, что область вейвлет-коэффициентов прекрасно приспособлена для работы кодера длин серий. В самом деле, генерируются большие серии нулей и не надо передавать их длину, так как высота дерева известна. Аналогично JPEG, данный алгоритм является разновидностью скалярного/векторного квантования. Каждый (значимый) коэффициент квантуется отдельно, а символы, соответствующие малым коэффициентам, образуют вектор. Этот вектор состоит из символа нульдерева и последовательности нулей длиной до конца дерева.
В большинстве алгоритмов сжатия изображений на основе вейвлет-преобразования имеется возможность выделить две составляющие скорости и две составляющие искажения. В алгоритмах выполняется оптимизация распределения бит между этими составляющими с учетом ограничения на общую скорость кодирования изображения.
Одна из составляющих связана с «обнулением» коэффициентов, не превосходящих некоторый порог, другая — с квантованием больших коэффициентов («значимых») и передачей их местоположения. Эффективность алгоритма сжатия зависит от правильного определения порога принятия решения о значимости коэффициентов, а также от выбранного способа квантования значимых коэффициентов и от метода передачи информации об их местоположении.
Для передачи информации о позициях значимых коэффициентов известен исключительно эффективный алгоритм «вложенного нульдерева» (EZW) [4], а также его разновидности — SPIHT [5] и другие.
Стандарт JPEG хорошо пригоден для сжатия изображений в 30–40 раз. При более сильном сжатии качество резко падает. Эта и множество других причин послужило причиной разработки нового стандарта на сжатие изображений — JPEG-2000. В новом стандарте реализованы такие опции, как последовательная передача, кодирование конкретного интересующего блока изображения, его масштабируемость, защищенность от ошибок передачи, произвольный доступ к сжатому изображению. В стандарте JPEG-2000 в качестве первичного преобразования применяется вейвлет-преобразование. Вейвлет-коэффициенты подвергаются квантованию по алгоритму, известному как «иерархическое кодирование блоков с оптимизированным усечением» (EBCOT), предложенному в работе [6]. Основное отличие этого алгоритма от EZW и SPIHT заключается в том, что EBCOT работает с независимыми неперекрывающимися блоками, которые кодируются итеративно. Таким образом вместо структуры данных нульдерева здесь используется структура квадродерева. В результате получается многоуровневый легко масштабируемый поток бит. Каждый уровень соответствует какой-то степени искажения. Распределение бит между уровнями осуществляется решением оптимизационной задачи с применением метода множителей Лагранжа [7].
В стеганографии используется много идей из области компрессии изображений. Кроме того, знание алгоритмов сжатия видео помогает конструировать робастные к этим алгоритмам ЦВЗ.
5.2. Скрытие данных в пространственной области
Алгоритмы, описываемые в данном пункте, внедряют ЦВЗ в области исходного изображения. Их преимуществом является то, что для внедрения ЦВЗ нет необходимости выполнять вычислительно громоздкие линейные преобразования изображений. ЦВЗ внедряется за счет манипуляций яркостью или цветовыми составляющими .
А1. (Kutter[8]). Пусть изображение имеет RGB-кодировку. Встраивание выполняется в канал синего цвета, так как к синему цвету система человеческого зрения наименее чувствительна. Рассмотрим алгоритм передачи одного бита секретной информации.
Пусть si - встраиваемый бит, I = {R,G,B} — контейнер, p = (x,y) — псевдослучайная позиция, в которой выполняется вложение. Секретный бит встраивается в канал синего цвета путем модификации яркости :
, (5.3)
где q — константа, определяющая энергию встраиваемого сигнала. Ее величина зависит от предназначения схемы. Чем больше q, тем выше робастность вложения, но тем сильнее его заметность.
Извлечение бита получателем осуществляется без наличия у него исходного изображения, то есть вслепую. Для этого выполняется предсказание значения исходного, немодифицированного пиксела на основании значений его соседей. В работе [8] предлагается для получения оценки пиксела использовать значения нескольких пикселов, расположенных в том же столбце и той же строке. Авторы использовали «крест» пикселов размером 7х7. Оценка получается в виде
, (5.4)
где c — число пикселов сверху (снизу, слева, справа) от оцениваемого пиксела (c = 3). Так как в процессе встраивания ЦВЗ каждый бит был повторен cr раз, то мы получим cr оценок одного бита ЦВЗ. Секретный бит находится после усреднения разности оценки пиксела и его реального значения
. (5.5)
Знак этой разности определяет значение встроенного бита.
Можно ли гарантировать всегда верное определение значения секретного бита? Нет, так как функция извлечения бита не является обратной функции встраивания. Для повышения надежности необходимо применение дополнительных мер.
В работе [8] рассмотрена также и модификация данного алгоритма для встраивания нескольких бит. Показано, что алгоритм является робастным ко многим из известных атак: низкочастотной фильтрации изображения, его сжатию в соответствии с алгоритмом JPEG, обрезанию краев.
А2. (Bruyndonckx[9]). ЦВЗ представляет собой строку бит. Для повышения помехоустойчивости применяется код БЧХ. Внедрение осуществляется за счет модификации яркости блока 8х8 пикселов.
Процесс встраивания осуществляется в три этапа.
1) Классификация, или разделение пикселов внутри блока на две группы с примерно однородными яркостями.
2) Разбиение каждой группы на категории, определяемые данной сеткой.
3) Модификация средних значений яркости каждой категории в каждой группе.
Рассмотрим подробнее каждый из этих этапов.
1) При классификации авторы выделяют два типа блоков: блоки с «шумовым контрастом» (рис. 5.3(а)) и блоки с резко выраженными перепадами яркости (рис. 5.3(б)).
Рис. 5.3. Два типа блока: а) с нечетким контрастом и б) с резко выраженным контрастом
В блоках второго типа зоны с отличающейся яркостью не обязательно должны располагаться вплотную друг к другу, не обязательно должны содержать равное количество пикселов. Более того, некоторые пикселы вообще могут не принадлежать ни одной зоне. В блоках первого типа классификация особенно затруднена.
Для выполнения классификации значения яркости сортируются по возрастанию (рис. 5.4(а) и (б)). Далее находится точка, в которой наклон касательной к получившейся кривой максимален (α). Эта точка является границей, разделяющей две зоны в том случае, если наклон больше некоторого порога. В противном случае пикселы делятся между зонами поровну.
2) Для сортировки пикселов по категориям на блоки накладываются маски, разные для каждой зоны и каждого блока. Назначение масок состоит в обеспечении секретности внедрения. Пример масок для двух зон приведен на рис. 5.5(а) и (б).
