6.3. Стегоалгоритмы, использующие фрактальное преобразование
6.3. Стегоалгоритмы, использующие фрактальное преобразование
В алгоритмах данного пункта используются идеи, заимствованные из области кодирования изображений. Тема фрактального сжатия изображения, наверное, самого оригинального алгоритма сжатия, стала популярной в середине 90-х годов. Этому методу выдавались громадные авансы, сообщалось о фантастических достигнутых коэффициентах сжатия (порядка нескольких тысяч). Как выяснилось позднее, значительная часть этих публикаций имела чисто рекламный характер, а эксперименты были поставлены некорректно. Насколько нам известно, лучшие фрактальные кодеры незначительно превосходят по эффективности сжатия алгоритм JPEG и значительно уступают алгоритму JPEG2000. Важным преимуществом фрактального метода сжатия для многих приложений является его резкая асимметричность. Декодер реализуетсяя исключительно просто. Так, сжатый этим методом видеофильм может быть воспроизведен даже на 386DX-40.
Основная идея метода сжатия заключается в поиске последовательности афинных преобразований (поворот, сдвиг, масштабирование), позволяющих аппроксимировать блоки изображения малого размера (ранговые) блоками большего размера (доменами). То есть считается, что изображение самоподобно. Эта последовательность преобразований и передается декодеру. Будучи примененными к любому изображению, эти преобразования дают в результате искомое изображение. Фрактальное кодирование может рассматриваться, как разновидность векторного квантования, причем в качестве кодовой книги выступают различные преобразования.
Мы рассмотрим три стегоалгоритма, использующих фрактальное преобразование. Как нам кажется, только первый из них является более или менее перспективным. Второй и третий алгоритмы не являются устойчивыми к сжатию изображения — заполненного контейнера.
А34 (Bas[48]). Интересно, что «внешний» ЦВЗ в данном алгоритме вообще отсутствует. Информация встраивается за счет такого изменения изображения, чтобы оно стало содержать самоподобия. Таким образом может быть внедрено 15 различных ЦВЗ.
Алгоритм работает следующим образом. Вначале выбираются несколько «особых» точек с использованием известного из фрактального кодирования метода Стефана-Харриса. Каждая особая точка определяет блок размером 4х4 вокруг нее и 16 блоков размером 4х4, образующих доменный пул (рис. 4.7). Для каждой особой точки выполняют изменение доменного блока в той же позиции так, чтобы он был более похож на ранговый блок, чем любой другой доменный блок. (Так как всего можно выбрать 15 блоков, это дает возможность внедрить 15 ЦВЗ). Получившийся доменный блок определяется выражением
, (6.39)
где
- среднее значение пикселов в D. Он добавляется к Rj в соответствии с выражением
, (6.39)
где s — коэффициент, учитывающий квантование.
При извлечении ЦВЗ вначале восстанавливаются значения особых точек, Dj и Wj. Для каждого блока Rj вычисляется
. (6.40)
Далее находят наиболее похожий блок, который должен быть тем же, что и в процессе встраивания. Число совпавших блоков есть мера вероятности того, что ЦВЗ присутствует в изображении.
А35 (Puate [47]). В качестве ЦВЗ выступает строка бит. Секретным ключом, от которого зависит эффективность всего алгоритма, является в данном случае выбор рангового блока. Число ранговых блоков есть верхняя граница для числа встраиваемых бит. Доменный пул делится на две части: одной будет соответствовать внедрение единиц, другой — внедрение нулей.
ЦВЗ добавляется следующим образом. Для выбранного в соответствии с ключом рангового блока в доменном пуле ищется соответствующий блок. Если надо встроить 1, поиск выполняется в одной части пула, если 0 — в другой части. Для ранговых блоков, в которые не встраивается биты ЦВЗ, поиск осуществляется во всем доменном пуле. После фрактального кодирования изображения осуществляется его декодирование для получения исходного изображения.
Декодер знает секретный ключ и выполняет обратные преобразования, восстанавливая ЦВЗ. В работе [47] показано, что этот алгоритм устойчив к сжатию JPEG.
А36 (Davern [49]). Алгоритм заключается в следующем. Пользователь вручную выбирает две неперекрывающиеся квадратные области на изображения, называемые ранговой и доменной областью. Местоположение этих областей составляет часть секретного ключа, необходимого для извлечения ЦВЗ.Блоки ы ранговой области модифицируются для внедрения битов ЦВЗ. Эти блоки могут иметь размеры 4х4, 8х8 или 16х16. Число блоков есть верхняя граница длины ЦВЗ. Блоки выбираются в псевдослучайном порядке, что составляет вторую часть секретного ключа. Также, как и в предыдущем алгоритме, доменная область делится на две части: соответствующую внедрению нулей и единиц. Далее вычисляются значения масштабирующего коэффициента и коэффициента сдвига
, удовлетворяющих равенству
, (6.41)
где
Rk — ранговый блок, Dmk — соответствующий ему (и ЦВЗ) доменный блок. Получив коэффициенты, выполняем обратное преобразование: вычисляем значение рангового блока
. (6.41)
Теперь находим отличный от первого коэффициента
коэффициент в
, либо равный нулю, либо равный 255, путем зигзагообразного сканирования
, начиная со второго коэффициента. Пусть найденный коэффициент
. Далее вычисляем новые значения коэффициентов
:
, (6.42)
. (6.43)
Как видно из этого выражения, в вычислении новых значений коэффициентов участвуют не все пикселы ранговой и доменной областей. И, наконец, мы вычисляем значения всех пикселов от
до
с использованием
:
, где
. (6.44)
Получившимся блоком
заменяют исходный блок
. При извлечении ЦВЗ ранговые блоки обходятся в том же порядке, что и при встраивании. Для каждого рангового блока ищется соответствующий ему доменный. Если находится полностью соответствующий блок, то по его принадлежности к той или иной части доменной области судят о встроенном бите ЦВЗ.
Недостатком этого алгоритма является, на наш взгляд, способ вычисления коэффициентов масштабирования и сдвига — всего лишь по двум пикселам. Это может существенно ухудшить качество изображения при внедрении ЦВЗ.
Данный текст является ознакомительным фрагментом.