Код документа: RU2331085C2
Область техники, к которой относится изобретение
Изобретение относится к области цифровой стеганографии или встраивания в цифровое изображение произвольных водяных знаков. Более конкретно, изобретение относится к области прямого, без спектральных преобразований, обратимого встраивания произвольных водяных знаков посредством квантования и модификации амплитудных значений сигнала в условиях, когда оригинальное изображение (контейнер) не доступно, а передаваемое сообщение не известно на приемном конце - технология слепого встраивания.
Терминология, используемая в данном документе
Установленный и неустановленный бит - альтернативные значения бита, описываемые вне зависимости от конкретной интерпретации; обычно 0 и 1, в изобретении - ±1 или 0 и 2 и пр.
Пиксель ("точка") - элемент изображения.
Отсчет яркости (отсчет, яркость) - значение яркости пикселя.
Преобразование изображения - получение нового изображения посредством изменения значений яркости его пикселей.
Представление изображения - результат преобразования изображения.
Контейнер - исходный цифровой сигнал, изображение, предназначенное для встраивания.
Контекст контейнера - наблюдаемая информация контейнера, формально представляемая некоторым множеством визуально воспринимаемых пикселей. Контекст контейнера (предметная область рассматриваемых изображений) не ограничивается.
Сообщение, водяной знак - встраиваемые данные, упорядоченная в виде бинарной матрицы последовательность произвольных кодов, предназначенная для передачи вместе с контекстом контейнера. Представляют собой бинарные коды (биты), содержащие встраиваемую информацию, которая кодируется в пикселях с варьируемой яркостью и дополняет наблюдаемую информацию (контекст контейнера).
Встраивание - внедрение, запоминание сообщения в контейнере. Модификация содержащихся в изображении кодов природной, встроенной шумовой и пр. неявной информации.
Стего-изображение - цифровое изображение, содержащее встроенное сообщение. Изображение с модифицированными кодами природной, встроенной шумовой и пр. неявной информации.
Амплитуда, амплитудное значение - синоним термина "яркость", которым удобно обозначать яркость формально вычисленного представления сигнала при употреблении вместе с термином "яркость", относящемуся к исходному изображению.
Шкала яркости - перечисленные по порядку последовательные неповторяющиеся значения яркости, которые могут встретиться в произвольном изображении или представлении изображения. Для обработки изображения шкала представляется в виде последовательности отождествляемых со значениями яркости (амплитуды) адресов массива ячеек памяти ЭВМ, в которые записываются сопоставляемые различным значениям яркостям величины, например, количество встречающихся пикселей данной яркости при вычислении гистограммы, или значения амплитуды при вычислении представления изображения в виде "гистограммного образа".
Диапазон яркости - некоторый диапазон значений яркости шкалы, ограниченный встречающимися в изображении (представлении изображения) значениями яркости (амплитуды).
Рабочий диапазон - рассматриваемый диапазон яркости изображения, ограниченный встречающимися в изображении минимальным и максимальным значениями яркости.
Вычисляемый (о диапазоне) - вычисляемый по гистограмме изображения посредством итеративного разделения рабочего диапазона на последовательности диапазонов, вложенных один в другой. В предусмотренном числе итераций диапазоны вычисляются одинаковыми для контейнера и стего-изображения независимо от сообщения.
Приближение изображения снизу (сверху) - представление изображения, в котором значения яркости пикселей заменены на минимальные (максимальные) значения яркости вычисляемых диапазонов, которым принадлежат значения яркости этих пикселей. Приближения снизу и сверху непосредственно для каждого пикселя изображения устанавливают граничные яркости диапазонов и сами диапазоны допустимого варьирования значений яркости пикселей или для краткости просто диапазоны допустимого варьирования яркости. При этом независимое друг от друга варьирование значений яркости пикселей изображения внутри установленных диапазонов допустимого варьирования яркости не влияет на результат вычисления приближений снизу и сверху по модифицируемому изображению.
Канал - "коридор" между приближениями изображения снизу и сверху (объединение по координатам диапазонов допустимого варьирования значений яркости пикселей). Более точно - множество изображений, по каждому из которых вычисляется рассматриваемая пара приближений изображения снизу и сверху. В ином, эквивалентном в рамках изобретения определении, канал - множество изображений, порождаемых независимым варьированием значений яркости пикселей внутри диапазонов допустимого варьирования яркости. Канал рассматривается как член иерархической последовательности (иерархии) вложенных друг в друга каналов. При выбранной паре приближений изображения снизу и сверху канал содержит всевозможные стего-изображения, порождаемые встраиванием в данный контейнер различных сообщений (но не исчерпывается этими стего-изображениями). Максимальный канал содержит все остальные каналы и порождается независимым варьированием значений пикселей изображения неграничной яркости внутри рабочего диапазона яркости.
Упаковка по яркости - преобразование изображения, заключающееся в замещении значений яркости пикселей последовательными номерами встречающихся в изображении значений шкалы яркости, например, значения яркости 1, 100, 110 по порядку замещаются своими номерами, например на 0, 1, 2.
Эквидистантная нормировка - линейное преобразование значений яркости пикселей изображения, например, для его визуализации (вывода на дисплей), которое сводится к умножению значений яркости упакованного изображения на коэффициент так, чтобы максимальное встречающееся значение яркости совпало с верхней границей максимального диапазона, который определяется числом бит, предусмотренных в ЭВМ для ввода/вывода изображения. Если при "упаковке" яркости по порядку замещаются своими номерами, например яркости 1, 100, 110 замещаются на 0, 1, 2, то при "эквидистантной нормировке" упакованные яркости умножаются на коэффициент, например, на 127.5 так, чтобы максимальная яркость совпала с максимально возможным яркостным значением 255.
Стандартные преобразования - упаковка, линейное растяжение (посредством умножения значений яркости на коэффициент, превышающий 1), эквидистантная нормировка и др. линейные и нелинейные преобразования яркостных значений пикселей изображения без нарушения их порядка следования.
Инвариантный (по умолчанию) - сохраняющийся при стандартных преобразованиях.
Арифметическое преобразование (амплитудного значения) - деление нечетного значения нацело на два и удвоение четного значения, предварительно поделенного на четыре. Применение именно этого преобразования для инвариантного представления изображения обосновано, например, в М.В. Харинов, В.Л. Горохов Псевдотроичная система счисления и анализ изображений // Известия ВУЗов России. Радиоэлектроника. / Вып. 2, - СПб., 2003. - С. 49-53.
Изоморфное представление изображения, образа - такое представление изображения, при котором между значениями яркости пикселей сохраняются имевшиеся в исходном изображении соотношения "меньше", "равно", "больше". Например, стандартные преобразования порождают изоморфные образы.
Гомоморфное представление изображения, образ - представление изображения, при получении которого допускается переход неравных яркостей в равные. Например, арифметическое преобразование порождает гомоморфные образы.
Уровень техники
Решения, связанные со встраиванием в контейнер некоторого сообщения при передаче по общедоступному каналу связи, условно подразделяются на задачи стеганографии и задачи встраивания в контейнер водяного знака. Под стеганографией понимается скрытное встраивание в контейнер сообщения относительно большого объема, которое может являться частью контейнера, зависимым или независимым образом дополнять контекст контейнера для ограничения несанкционированного доступа к сообщению, дублировать контекст на случай помех, снабжать его сопроводительной информацией и пр. Под встраиванием водяного знака обычно понимается скрытное встраивание заранее известного распределенного или повторяющегося сообщения относительно малого объема для идентификации подлинности контекста контейнера или источника стего-изображения, защиты авторских прав и пр., а также для целей стеганографии, достигаемых в рамках ограниченного объема сообщения.
При ограниченном требуемом объеме сообщения к встраиванию водяных знаков предъявляют наиболее жесткие требования, среди которых выделяют (см. B. Chen and G. W. Wornell, "Digital Watermarking and Information Embedding using Dither Modulation", IEEE Signal Processing Society 1998 Workshop on Multimedia Signal Processing December 7-9, 1998, Los Angeles, California, USA Electronic Proceedings May 1998 [Chen98], и B. Chen and G. W. Wornell, "Quantization index modulation: A class of provably good methods of digital watermarking and information embedding", IEEE Transactions on Information Theory Vol. 47, pp. 1423-1443, May 2001, [Chen01]) следующие три основных:
- максимальная скорость встраивания (и извлечения) сообщения;
- метрическая близость стего-изображения и исходного контейнера, например, по среднеквадратичному отклонению;
- максимальная робастность встраивания сообщения.
Перечисленные постановочные требования справедливо считаются противоречивыми. Для преодоления сопутствующих недостатков необходим анализ целевых установок, который состоит в следующем.
При современном резком возрастании вычислительных ресурсов ЭВМ проблема недостаточной скорости встраивания сообщений возникает из-за недостаточно эффективной организации запоминания данных и многократного повторения вычислений с различными параметрами, из-за прямого перебора вариантов заведомо известных сообщений в процессе корреляционного анализа или перебора способов встраивания ([Chen98,Chen01]), а также прочих причин, которые для настоящего изобретения не являются актуальными.
Требование метрической близости стего-изображения и исходного контейнера является основным источником противоречий, поскольку:
- логически не согласуется с предположением о контейнере, который не доступен на приемном конце;
- ограничивает возможный объем сообщения;
- препятствует встраиванию сообщения одновременно с упрощением стего-изображения за счет сокращения числа градаций яркости (сопутствующее изменение гистограммы влечет большое поточечное среднеквадратичное отклонение);
- ограничивает возможности инвариантного встраивания сообщения независимо от предусмотренных преобразований;
- препятствует робастному встраиванию сообщения с периодическими повторениями по координатам;
где, в отличие от инвариантности (сохранения в точном смысле), под робастностью (устойчивостью к возможным случайным или преднамеренным помехам при передаче) понимается неполное, неточное сохранение сообщения, которое исследуется на примерах заранее известных искажений в виде линейных преобразований, JPEG-компрессии, добавления шумов и пр.
Кажется очевидным, что для эффективного сокрытия сообщений необходимо уметь формально разделять сигнал, в зависимости от контекста, на видимую и незаметную компоненты и затем сохранять видимую компоненту в процессе встраивания сообщения. Тем не менее, в известных решениях необходимость подобного разделения сигнала с последующим сохранением видимой компоненты осознается недостаточно, формализуется недостаточно просто и достигается неполной эвристической реализацией либо того, либо другого.
Для повышения эффективности сокрытия сообщений за счет учета контекста контейнера развивают способы распределения встроенных кодов по текстурным участкам изображения с повышенной концентрацией яркостных перепадов, на которых внедрение информации сообщения оказывается незаметным (трава, волосы, шумовые искажения и пр.).
Тенденция развития способов прямого встраивания сообщения с учетом контекста контейнера иллюстрируется на Фиг.1.
На Фиг.1 крайним слева изображен контейнер в виде стандартного изображения "Лена" (крайнее слева) и схемы a), b), c) встраивания информации, на которых белые поля обозначают варьируемые пиксели, в которых допускается модификация, т.е. в которые встраиваются коды сообщения. Таким образом, решения основаны на покоординатном распределении встроенных кодов сообщения по результатам анализа контейнера: крайний слева - контейнер; рядом - схемы координат встроенных кодов при простейшем LSB-методе (a), поблочном встраивании кодов (b) и при поточечном встраивании кодов по текстурным участкам (c).
В простейшем LSB методе встраивание кодов сообщения выполняют в фиксированное число младших бит независимо от контекста контейнера, причем встраивание прекращают, когда сообщение оказывается исчерпанным (см. В.Г. Грибунин, И.Н. Оков и И.В. Туринцев. Цифровая стеганография. Москва, СОЛОН-Пресс, 2002, 258 с. (аналитический обзор) [Гри02]). В методах (см. Гика С.Н. Анализ эффективности методов сокрытия информации в графических файлах // 32-ая Санкт-Петербургская научно-техническая конференция студентов, аспирантов и молодых ученых. Тезисы докладов. - СПб.: 2000. - 75с. [Ги00], Hioki Hirohisa A data embedding method using BPCS principle with new complexity measures // Proc. Of Pacific Rim Workshop on Digital Steganography 2002, Jan. 2002. P. 30-47 [HiHi02]) встраивание кодов сообщения выполняют по предварительно вычисленным участкам текстур, которые аппроксимируются блоками координат встраивания простой формы.
Перечисленные работы отражают тенденцию современных решений к адаптивному сокрытию сообщений с учетом контекста контейнера. Однако возможности обработки при этом ограничиваются преимущественно геометрически адаптивным встраиванием данных, которое выполняется по текстурным яркостным и цветовым сегментам с повышенной концентрацией перепадов яркостей цветовых компонент.
Если скрытое сообщение при приеме предполагается не известным, то оно обычно сопровождается сопутствующей управляющей информацией о размещении встроенных данных. Управляющая информация не адаптивно размещается по фиксированным координатам предусмотренного фрагмента сигнала независимо от контекста контейнера, как в простейшем "LSB"-методе. Сообщение встраивается в некоторые блоки контейнера для снижения объема управляющей информации, которая задается, например, списком координат блоков. При этом поблочная запись сообщения ограничивает точность учета геометрии рисунка контейнера и снижает эффект сокрытия кодов сообщения по участкам текстур. Если сообщение заведомо известно и обнаруживается при приеме посредством стандартных методов корреляционного анализа, то можно обойтись без управляющей информации, применить поточечное встраивание, и при внедрении сообщения ограничиться выделением текстур (схема (c) на Фиг.1). Однако сама по себе задача эффективного выделения текстур на произвольных изображениях является проблематичной.
Таким образом, для известных способов слепого встраивания водяных знаков адаптивно к контейнеру характерно, что контекст контейнера учитывают только геометрическим размещением кодов сообщения по координатам при фиксированных диапазонах модификации яркости, величина которых устанавливается кратной степени 2. Поскольку результаты вычисления по контейнеру координат встроенных кодов сообщения не воспроизводятся при аналогичной обработке стего-изображения (встроенное сообщение влияет на расчет текстурных сегментов), для успешного извлечения сообщения в контейнер независимо от контекста встраиваются сопутствующие сведения, которые могут также независимо от контейнера задаваться алгоритмически и в общей схеме встраивания и извлечения сообщений, в частности водяных знаков, фигурируют в качестве атрибутивного ключа ([Гри02], V.I. Gorodetsky, V.I. Samoilov "Simulation-Based Exploration of SVD-Based Technique for Hidden Communication by Image Steganography Channel", Proc. of the Second Int. Workshop on Mathematical Methods, Models, and Architectures for ComputerNetwork Security MMM-ACNS, ISSN: 0302-9743, ISBN: 3-540-40797-9, St. Petersburg: Springer-Verlag-Berlin-Heidelberg, pp. 349-359, Sep. 2003 [Гор03]), как иллюстрируется Фиг.2. Пунктиром на данном чертеже показаны данные, которые могут использоваться на входе подсхемы извлечения сообщения, но не всегда обязательны.
Если исключить из схемы все необязательные элементы, она остается перегруженной запрашиваемыми данными на входе и недостаточно конкретной на выходе. Помимо входного ключа, который "навязывает" модификацию контейнера независимо от маскирующего контекста изображения, на выходе общей схемы при извлечении сообщения не формализуют или недостаточно формализуют извлечение информации исходного сигнала (контейнера), которая сохраняется после встраивания кодов сообщения. При этом смешивают понятия неизвестного и недоступного контейнера.
В отсутствие независящего от контейнера ключа недоступность самого контейнера при извлечении сообщения является главным препятствием для точного вычисления координат размещения встроенных кодов, которое преодолевается в RDH-методе (Reversible Data Hiding) обратимого встраивания данных в изображение или аудиосигнал (см. Mehmet U. Celik, Gaurav Sharma, A. Murat Tekalp, Eli Saber. Reversible Data Hiding. IEEE Proceedings of the International Conference on Image Processing (ICIP), New York, 23 September 2002. P. 157-160 [Meh02], Fridrich J., Goljan M., Du R. Lossless data embedding - new paradigm in digital watermarking. EURASIP Journ. Appl. Sig. Proc., vol. 02, Feb 2002. P. 185-196 [Fri02]). В указанном методе встраивание сообщения обеспечивается за счет частичного сжатия видеоданных, содержащихся в младших битах исходного представления сигнала, что поясняется схемой на Фиг.3. При этом в оригинальном RDH-методе сначала извлекается сообщение, а затем восстанавливается контейнер. Однако, если в качестве сообщения встраивать списки координат встраивания кодов, то для извлечения сообщения окажется необходимым предварительное восстановление контейнера.
В схеме RDH-метода под преобразованным контейнером понимается представление исходного сигнала с некоторым количеством младших бит, освобождаемых благодаря упаковке информации младших разрядов. Освободившийся объем используется для встраивания сообщения, что позволяет в процессе передачи без искажений сохранить как контейнер, так и встроенное сообщение.
Однако в силу ограниченного коэффициента сжатия и относительно малого объема встраиваемых кодов (менее 10%) от объема контейнера, а также из-за неустойчивости к искажениям в процессе передачи стего-изображения RDH-метод оказывается недостаточно эффективным при встраивании сообщений относительно большого объема и имеет в задачах стеганографии ограниченное практическое значение.
Сущность изобретения
Настоящее изобретение относится к способу обратимого слепого идемпотентного (за одну итерацию) встраивания стеганографических сообщений или произвольных водяных знаков без использования ключа в пиксели с вычисляемыми диапазонами яркости переменной величины, в том числе - двухкомпонентное встраивание сообщения в инвариантный сегментированный контейнер и добавленный шумовой сигнал.
Согласно настоящему изобретению при двухкомпонентном встраивании сообщение внедряется в пиксели контейнера с нефиксированными значениями яркости, а второе сообщение накладывается на контекст стего-изображения со встроенным первым сообщением.
Решение предназначено для записи и извлечения произвольных кодов информации (видеоданных) и, в зависимости условий применения, трактуется как встраивание стеганографического сообщения или произвольного водяного знака относительно большого объема в контейнер. Вопреки сложившимся стереотипам полагается, что незаметность встраивания, сама по себе, не определяет сущность и особенности алгоритмов, а, скорее, является ограничением на выбор настроечных параметров встраивания в процессе применения в режиме реального времени (on-line). Вне зависимости от условия визуальной незаметности встраивания сообщения базовая задача стеганографии или задача встраивания произвольного сообщения не меняется по существу и включает, прежде всего, обратимое встраивание кодов сообщения адаптивно к контейнеру.
В настоящем изобретении разделяются понятия неизвестного и недоступного контейнера, полагая контейнер при приеме известным, но в огрубленном, упрощенном виде. Для формализации понятия "незаметного встраивания" вместо метрической близости используется предположение, что наблюдаемый после встраивания сообщения контекст контейнера может быть просто вычислен независимо от сообщения и представлен в виде огрубленного нового изображения (образа), получаемого по заранее определенному алгоритму сегментации контейнера или стего-изображения. Поскольку указанный алгоритм сегментации относится к алгоритмам улучшения изображения со снижением числа градаций яркости (см. Прэтт У. Цифровая обработка изображений: В 2х кн. М.: Мир, 1982. 714 с. [Прэтт]), то реальное улучшение визуального восприятия рассматривается вместо принятой в стеганографии формальной оценки ухудшения качества стего-изображения по среднеквадратичному отклонению от контейнера.
Поскольку на передающем конце перед встраиванием сообщения вычисляется тот же самый упрощенный контейнер, что и на принимающем конце, передающая сторона имеет возможность независимо от сообщения заранее оценить степень сохранения контекста контейнера для целей автоматизации обработки. Для управления сокрытием кодов сообщения в режиме реального времени предусматривается, помимо стандартного уменьшения объема сообщения, максимальное распределение встраиваемых кодов по полю изображения.
При исключении требования метрической близости контейнера и стего-изображения из числа существенных требований к встраиванию сообщения с сохранением контекста контейнера имеется возможность разделить нестрогое понятие робастности на точное понятие инвариантности (строгое сохранение) встроенного сообщения при линейных и нелинейных стандартных преобразованиях стего-изображения (упаковки, линейного преобразования, эквидистантной нормировки по яркости и пр.) и обычную устойчивость сообщения относительно случайных или технологических искажений стего-изображения (зашумления, JPEG-преобразования), а также преднамеренных внешних атак. В задачах с ограниченным объемом сообщения достигается устойчивость относительно искажений контейнера при передаче за счет периодического повторения кодов встраиваемого сообщения заранее известного на приемном конце размера в границах изображения при встраивании, а затем суммирования извлеченных соответствующих кодов различных копий при приеме сообщения.
Биты сообщения вставляются, аналогично LSB-методу, по заранее определенному закону (с начала изображения, с конца изображения, с использованием генератора случайных чисел и пр.), однако, с пропусками, зависящими от контекста контейнера.
При встраивании сообщения в стего-изображение с одновременным снижением его числа яркостных градаций по сравнению с исходным контейнером, увеличиваются перепады между яркостями, которыми кодируется сообщение. Благодаря такому кодированию сообщения большими перепадами яркости и, в результате, увеличения амплитуды сигнала сообщения повышается робастность встраивания сообщения.
Инвариантность встраивания сообщения относительно стандартных преобразований стего-изображения обеспечивается тем, что перед внедрением сообщения контейнер независимо от стандартных преобразований преобразуется на передающем конце по определенному алгоритму в некоторое инвариантное представление, а перед извлечением сообщения на приемном конце по тому же алгоритму стего-изображение преобразуется для восстановления сообщения, в случае предусмотренных преобразований при передаче.
Используя инвариантное встраивание сообщения одновременно со снижением числа яркостных градаций, возможно создание дополнительной шумовой компоненты встраивания сообщения за счет обратимого добавления шума к стего-изображению с первоначальным сообщением, закодированным в ограниченном числе градаций яркости, где под обратимым добавлением шума понимается внесение шума с возможностью подавления. Основной целью создания такой дополнительной компоненты встраивания сообщений является повышение суммарного объема встраиваемых кодов. Попутно с увеличением общего объема встраивания кодов пары сообщений достигается эффект маскировки одного сообщения другим.
Таким образом, при прямом встраивании кодов сообщения решается проблема стеганографии (скрытного встраивания сообщения относительно большого объема), которая объединяется с проблемой робастного сокрытия в изображении произвольного водяного знака.
Для управления встраиванием предусматривается автоматизированная настройка параметров в режиме реального времени. В целом оптимальное встраивание достигается в условиях конкретной задачи как разумный компромисс между объемом встроенного сообщения, с одной стороны, и условиями незаметности и робастности встраивания, с другой стороны.
Кодирование пары сообщений в пикселях с одними и теми же координатами или, иными словами, одновременное кодирование независимых сообщений в яркостных значениях одних и тех же обеспечивает повышение объема встроенных кодов сообщения. Для повышения общего объема встраиваемых кодов предлагается способ двухкомпонентного встраивания произвольных водяных знаков по независимым каналу и шумовой компоненте. При этом, помимо робастности встраивания сообщения за счет инвариантности встраивания в сочетании со снижением числа градаций, обеспечивается двухкомпонентное сокрытие независимых сообщений посредством обратимого добавления в сигнал шума, который вносится в изображение с возможностью подавления при приеме.
Общий объем кодов геометрически повторяющегося сообщения (т.е. повторяющегося одного и того же встроенного сообщения в местоположениях изображения с отличающимися координатами) определяется контекстом контейнера, но само сообщение произвольно. Стего-изображение помимо кодов самого сообщения не содержит сведений ни о сообщении, ни об исходном контейнере, как в LSB-методе. Хотя контейнер не требуется для извлечения сообщения на приемном конце, однако, исходный сигнал (или, при инвариантном встраивании, его образ) в сегментированном виде известен при передаче и приеме, поскольку сохраняется в процессе встраивания сообщения. Сообщение на приемном конце считается не известным. При приеме сообщения диапазоны модификации яркостей не фиксируются одинаковыми для различных координат, и не требуется специального указания координат встраивания сообщения, поскольку координаты пикселей с варьируемой яркостью и диапазоны встраивания сообщения вычисляются по полученному стего-сигналу точно так же, как и по исходному контейнеру. Корреляционный анализ не предполагается.
Краткое описание чертежей
Фиг.1 иллюстрирует известные решения при покоординатном распределении встроенных кодов сообщения по результатам анализа контейнера;
Фиг.2 иллюстрирует общую схему встраивания и извлечения сообщений для стеганографии и встраивания водяных знаков;
Фиг.3 иллюстрирует схему обратимого встраивания данных в RDH-методе;
Фиг.4 иллюстрирует схему обратимого встраивания данных согласно изобретению;
Фиг.5 иллюстрирует адаптивное встраивание кодов сообщения по координатам и диапазонам яркости, вычисленным согласно изобретению в результате анализа контейнера;
Фиг.6 иллюстрирует обратимое встраивание сообщения на примере одномерного фрагмента изображения;
Фиг.7 иллюстрирует пример инвариантного изоморфного представления изображения, полученный согласно изобретению;
Фиг.8 иллюстрирует запоминание иерархии разбиений дискретных отрезков;
Фиг.9 иллюстрирует контейнер и его изоморфный гистограммный образ, а также оригинальное и преобразованное сообщение;
Фиг.10 иллюстрирует результат встраивания сообщения в контейнер;
Фиг.11 иллюстрирует инвариантное встраивание сообщения;
Фиг.12 иллюстрирует гистограмму стего-изображения с картой, встроенной в гистограммный образ, и добавленным шумом;
Фиг.13 иллюстрирует встраивание сообщений по двум независимым каналам;
Фиг.14 демонстрирует эффект использования геометрического повторения кодов сообщения для подавления искажений при передаче стего-изображения;
Подробное описание изобретения
Предполагается, что человек, как более совершенная вычислительная система, способен извлечь сохранившуюся информацию контейнера не хуже, чем это может быть смоделировано на ЭВМ. Визуально наблюдаемую компоненту контейнера вычисляют как сигнал контекста, который сохраняется после встраивания сообщения. Маскировка достигается за счет перемежения пикселей, содержащих сообщение, с пикселями наблюдаемой компоненты сигнала и зависит от амплитуды сигнала сообщения, а также от частоты сигнала сообщения, которая может повышаться за счет внесения в сообщение высокочастотной составляющей, например, за счет добавления в сигнал сообщения высокочастотной компоненты или за счет формального введения периодического колебания "нулевого" уровня отсчета сигнала сообщения.
На Фиг.4 в упрощенном виде представлена схема предлагаемого решения.
Вместо применяемой в RDH-методе процедуры сжатия информации используется сегментация изображения. Благодаря сегментации и ослаблению условия полного восстановления информации контейнера удается увеличить объем встраиваемых кодов сообщения.
В результате сегментации контейнер необратимым образом, но без существенного ущерба для зрительного восприятия, преобразуется в упрощенное представление изображения - сегментированный сигнал (контейнер или стего-изображение) с ограниченным числом градаций яркости, который задается вычисляемым множеством значений яркостей пикселей с неизменяемым значением яркости, и такой сигнал сохраняется при встраивании сообщения. Пиксели с не меняющейся при встраивании сообщения яркостью являются экстремальными в определенным образом вычисленных диапазонах яркости и позволяют определить уровень отсчета значений яркости, а также пределы изменения яркости остальных (модифицируемых) пикселей с промежуточными значениями яркости, изменением яркости которых кодируется сообщение. Таким образом, значения яркости пикселей сегментированного контейнера, равно как и сегментированного стего-изображения, позволяют определить уровень отсчета для модификации яркостных значений, используемых для кодирования сообщения. В отличие от RDH-метода, коды сообщения размещаются адаптивно к контейнеру, поскольку записываются в стего-изображении в пикселях с переменной (варьируемой, модифицируемой) яркостью, которые перемежаются с пикселями контейнера, имеющими неизменяемую яркость. Робастность, устойчивость сообщения к возможным искажениям стего-изображения обеспечивается за счет геометрического повторения кодов сообщения в границах контейнера.
Фиг.5 приведена для сравнения предлагаемого решения с известными и иллюстрирует встраивание кодов сообщения в изобретении. Крайним слева на Фиг.5 изображен контейнер, рядом с контейнером - приближение контейнера снизу, следующее - его приближение сверху и крайнее справа - представление емкости контейнера, которое определяется разностью приближений сверху и снизу. На основе сравнения градаций яркости представления емкости друг с другом можно наглядно оценить ширину диапазона допустимого варьирования яркости в сигнале для каждого пикселя. "Допустимое варьирование" означает, что модификация изображения за счет независимого изменения яркостей пикселей строго внутри диапазонов допустимого варьирования яркости на вычисление этих диапазонов не влияет. В отличие от известных решений обеспечивается адаптивное встраивание кодов сообщения не только по координатам, но и по диапазонам яркости без использования неадаптивной управляющей информации или перебора вариантов в процессе корреляционного анализа. Благодаря снятию условия LSB-метода о встраивании кодов сообщения в заранее заданное число битов изображения (т.е., в терминах изобретения, в фиксированные диапазоны яркости по величине кратные степени 2) снижается доступность сообщения для стегоанализа. Маскировка сообщения достигается не за счет ограничения изменений яркости пикселей контейнера, а, главным образом, за счет перемежения на изображении пикселей с встроенными данными сообщения с пикселями с неизмененными данными контейнера и за счет добавления в сообщение высокочастотного несущего сигнала.
Наряду со встраиванием битов сообщения в меняющиеся по координатам диапазоны допустимого варьирования яркости контейнера, предложенное решение не требует неадаптивного (не зависящего от контейнера) указания координат встраиваемых блоков данных и позволяет избежать поблочной записи согласно известному методу, что усиливает преимущества по сравнению с известными решениями.
Управление встраиванием сообщения выполняется в режиме реального времени посредством задания величин вычисляемых диапазонов гистограммы (и, как следствие, диапазонов допустимого варьирования значений яркости пикселей изображения) с помощью чисел Мерсенна в виде уменьшенных на единицу степеней двойки (т.е. 2n-1, например, 1, 3, 7, 15, 31, 63 и т.п.), с одновременным изменением соотношения числа пикселей с сохраняемыми и варьируемыми значениями яркости. С увеличением указанного числа Мерсенна (т.е. увеличением числа диапазонов яркости) уменьшается величина каждого диапазона допустимого варьирования яркости. При этом, чем больше число диапазонов, тем больше будет фиксировано пикселей с граничными значениями яркости. Так как эти пиксели включены в наблюдаемую картину и перемежаются с варьируемыми пикселями, то визуально степень сокрытия сообщения возрастает.
Таким образом, для различных значений чисел Мерсенна вычисляются вариант набора допустимых диапазонов варьирования яркости, и в каждом варианте диапазоны допустимого варьирования яркости при записи сообщения меняются от пикселя к пикселю, так как на изображении рядом встречаются пиксели из различных диапазонов яркости.
Величины диапазонов варьирования яркостей, в общем случае, не совпадают со степенями 2. Например, яркостный диапазон 0-4 содержит 5 целочисленных значений яркости. Два из них являются граничными и, если пиксель имеет яркость, равную одному из этих значений, он является неизменяемым. Три других, а именно значения 1-3, могут использоваться для кодирования сообщения. Однако для кодирования двух битов встраиваемого сообщения необходимо не менее 4 внутренних значений указанного диапазона помимо граничных значений, поэтому при наличии только трех упомянутых неграничных значений в диапазоне 0-4 можно закодировать только один бит встраиваемого сообщения. Следовательно, для кодирования двух битов встраиваемого сообщения число значений яркости вместе с граничными должно быть не менее 6 в пределах одного диапазона варьирования яркости.
Хотя в диапазонах допустимого варьирования яркости с количеством значений яркости, включая граничные, превышающем 5, можно кодировать несколько (т.е. более одного) битов сообщения на пиксель изображения, настоящее изобретение ограничивается встраиванием единственного бита на каждый модифицируемый пиксель во избежание снижения робастности и скремблирования сообщения, которые особенно критичны при переменных диапазонах модификации яркости по полю изображения.
Фиг.6 иллюстрирует исходную идею изобретения. На Фиг.6 сплошной темной линией для изображения (контейнера)
Суть идеи выполнения обратимого встраивания без использования ключа для нахождения координат встраивания кодов сообщения сводится к построению "коридора" допустимой модификации (на чертеже ограничен пунктирными линиями) исходного изображения, который, с одной стороны, вычисляется по изображению, а, с другой стороны, от варьирования яркостей пикселей изображения в заданных пределах не зависит. Для наглядности изображение обозначено непрерывной кривой, а коридор показан с перекрывающимися диапазонами варьирования яркостей, которые, на самом деле, вычисляются неперекрывающимися и разнесены по вертикальной оси.
В результате построения приближений снизу и сверху границы диапазонов допустимого варьирования яркости "натягиваются" на яркости пикселей сигнала (контейнера или стего-изображения) с сохраняемой яркостью и для каждого пикселя с изменяемой яркостью задают внутренний допустимый диапазон варьирования яркости, а также для допустимых диапазонов варьирования яркости определяют обозначенные белым цветом центральные значения яркости нулевого (т.е. "сегментированного") сигнала. В принципе, в изображении может не встретится ни одного пикселя, значение яркости которого совпадает с центральным значением в допустимом диапазоне варьирования значения яркости. Тем не менее, центральные значения яркости диапазонов, которые вычисляются одними и теми же как для контейнера на передающем конце, так и для стего-изображения на приемном конце, служат начальным уровнем для кодов сообщения не хуже реальных значений яркости и могут рассматриваться как яркости передаваемого формального нулевого сигнала.
Изобретение применяется к исходному цифровому сигналу, яркости (амплитуды, яркостные отсчеты и пр.) которого задаются в целых числах. При этом рассматривается не переход от непрерывных величин к дискретным, а замещение нескольких (целых) величин общим значением. Для точного и однозначного выполнения встраивания (записи) бита сообщения в изображение в настоящем изобретении без использования округления целых чисел бит сообщения записывают посредством зеркального отражения яркостного значения пикселя изображения относительно оси допустимого диапазона варьирования яркости. Например, если u{x} - яркость пикселя с координатой x, а a{x} и b{x} - граничные значения диапазона, то "отраженное" относительно центрального значения диапазона значение v{x} яркости вычисляется по формуле v{x} =a{x}+b{x}-u{x}, и значение v{x} получается целым. При другом способе модификации результат может оказаться нецелым, и тогда потребуется округление.
Установленные и неустановленные биты сообщения кодируются в пикселях с варьируемыми значениями яркости, соответственно, положительными и отрицательными (или наоборот - отрицательными и положительными) единичными значениями знака отклонения яркости пиксела от центральной яркости диапазона допустимого варьирования. Следует обратить внимание, что зеркальное отражение яркости пиксела относительно центральной яркости диапазона допустимого варьирования аналогично изменению на противоположное значения бита младшего разряда в LSB методе и при записи бита сообщения согласно изобретению выполняется только тогда, когда указанное значение знака не совпадает с требуемым кодом сообщения. Поэтому при повторной записи сообщения в стего-изображение последнее не меняется.
Обратимое встраивание битов сообщения в яркости пикселей с координатами x описывается соотношением:
P(
где
Под идемпотентным преобразованием понимается преобразование, повторное применение которого совпадает с однократным:
P=P2
Результат преобразования изображения под действием идемпотентного преобразования в данном изобретении называется идемпотентным представлением.
Существенным для упрощения описания и реализации настоящего изобретения является понятие иерархии гомоморфных представлений изображения, а также алгоритмы ее построения и запоминания.
Иерархия гомоморфных представлений. Под представлением, изоморфным изображению по яркостному порядку, т.е. по отношению яркостей между любыми двумя яркостями независимо от диапазонов, понимается преобразованное в тех же координатах изображение, между значениями яркости которого сохраняются отношения меньше, равно, больше. Если в преобразованном изображении в отношениях между значениями яркости допускается переход от неравенств к равенствам, но эти отношения не замещаются альтернативными, то оно считается гомоморфным представлением исходного изображения. Преобразование изображения в изоморфное (гомоморфное) представление называется изоморфным (гомоморфным) преобразованием. Под иерархией представлений изображения в рамках изобретения имеются в виду представления изображения, которые порождаются последовательностью разбиений яркостной шкалы на вложенные друг в друга диапазоны яркости и которые вычисляются для каждого разбиения посредством изоморфного преобразования. Вложенные друг в друга диапазоны находятся итеративным разбиением шкалы яркости, например, на две части, потом каждого из получившихся диапазонов еще раз на две части и т.д. В результате оказывается, что каждое значение яркости содержится в некоторой иерархической последовательности вложенных друг в друга диапазонов, верхняя и нижняя границы которых "стягиваются" к этому значению яркости.
При заданном разбиении шкалы яркости на диапазоны гомоморфные представления изображения получаются посредством замещения встречающихся в изображении значений яркости пикселей последовательными порядковыми номерами вычисляемых диапазонов, порядковыми номерами диапазонов с пропусками номеров, или иными последовательными индексами тех диапазонов, которые содержат яркости этих пикселей, а изоморфное представление получается, когда каждый диапазон из заданного разбиения шкалы яркости содержит единственное значение яркости.
Числовая иерархия инвариантных идемпотентных гомоморфных представлений. Под числовой иерархией представлений изображения понимается иерархия гомоморфных представлений, которая получается посредством итеративного применения к значениям яркости пикселей некоторого изоморфного представления изображения деления нацело и умножения на целое число, в частности, посредством применения вышеупомянутого арифметического преобразования, результат которого зависит только от значения яркости преобразуемого пикселя. Иными словами, числовая иерархия - это последовательность представлений изображения, которая задается значениями яркости пикселей изоморфного представления изображения и арифметическими действиями с ними, например, в простейшем случае, итеративным делением значений яркостей изображения нацело пополам. Пример получения числовой иерархии для неповторяющихся значений яркости приведен ниже в описании со ссылками на Фиг.8.
Числовая иерархия считается инвариантной, если изоморфное представление, которое ее порождает, не зависит от стандартных преобразований изображения (упаковки, линейного преобразования, эквидистантной нормировки по яркости, а также других линейных и нелинейных изоморфных преобразований).
На Фиг.7 приведен пример инвариантного изоморфного представления изображения, полученный согласно изобретению. На Фиг.7 изображение приведено слева и его инвариантное изоморфное идемпотентное представление, эквидистантно нормализованное на рабочий диапазон значений яркости (от 0 до 255), - справа.
Фиг.7 демонстрирует, что правое изображение ничем, кроме некоторого увеличения резкости, не отличается от левого, что позволяет говорить о том, что инвариантное изоморфное представление существенно не меняет изображение по визуальному восприятию.
Показанное на чертеже инвариантное изоморфное представление Hu изображение u, взятое в качестве исходного изображения, при повторном преобразовании под действием алгоритма H не меняется. Поэтому алгоритм H является идемпотентным:
H = H2,
а полученное по алгоритму H изображение Hu является идемпотентным представлением исходного изображения u.
Инвариантные идемпотентные гомоморфные представления
где Mrsn - число градаций формальной амплитудной шкалы представления Hu, выражаемое некоторым числом Мерсенна; μ - число градаций шкалы представления
Для краткости инвариантные идемпотентные гомоморфные представления
Построение гистограммного образа для обратимого встраивания сообщения согласно изобретению обеспечивает разделение пикселей изображения на пиксели видимого (вычисляемого) контекста изображения, значения яркости которых не подлежат модифицированию при встраивании сообщения, и пиксели с варьируемой яркостью.
Гистограммный образ представляет собой инвариантное представление, которое вычисляется в 1, 3, 7, 15... Mrsn градациях формальной амплитудной шкалы и не меняется при стандартных преобразованиях исходного изображения. При инвариантном встраивании сообщения гистограммный образ используется в качестве контейнера вместо исходного изображения.
Гистограммный образ вычисляется посредством итеративного применения рекуррентного арифметического преобразования амплитудных значений пикселей изоморфного гистограммного образа, который по числу встречающихся градаций совпадает с исходным изображением и визуально отличается от него повышенной резкостью. Итеративное применение арифметического преобразования порождает иерархическую последовательность гистограммных образов, которые в ограниченном числе 1, 3, 7, 15,... Mrsn градаций амплитудной шкалы представляют изоморфный гистограммный образ в упрощенном виде. Встраивание сообщения не влияет на последовательность гистограммных образов в 1, 3, 7, 15,..., μ градациях амплитудной шкалы.
Изоморфный гистограммный образ строится по гистограмме изображения в описанном ниже алгоритме итеративного разбиения гистограммы на 2 части с максимально равными суммарными количествами пикселей (за счет выделения центральной 3 части в случае равноправных альтернатив).
Необходимость построения изоморфного гистограммного образа для встраивания и извлечения сообщения обусловлена тем, что в его амплитудных значениях запоминается последовательность разбиений шкалы яркости изображения на диапазоны. При этом по сигналу (на передающем или приемном конце) и его гистограммному образу оказывается проще, чем по гистограмме, вычислить последовательность диапазонов допустимого варьирования яркости и встроить или извлечь сообщение.
Во всех пикселях с неграничными и нецентральными значениями яркости кодируются биты сообщения посредством зеркального отражения яркостных значений относительно центрального значения согласно вышеприведенной формуле v{x} =a{x}+b{x}-u{x} (для отражения относительно центрального значенияне требуется вычисления самого центрального значения). Внешние границы a{x}, b{x} допустимого варьирования значений яркости для каждого пикселя непосредственно задаются амплитудными значениями приближений изображения снизу и сверху, а приближения изображения снизу и сверху вычисляются по гистограммному образу и изображению без использования гистограммы. При этом построение приближения изображения снизу (сверху) сводится к нахождению минимального (максимального) значения яркости пикселей изображения, помеченных одинаковыми амплитудными значениями гистограммного образа (т.е. пикселей имеющих одинаковые амплитудные значения в представлении гистограммного образа), и замещению значений яркости пикселей изображения найденными минимальными (максимальными) значениями яркости.
Таким образом, встраивание сообщения в данный канал выполняется по изображению и гистограммному образу посредством построения приближений изображения снизу и сверху без дополнительной обработки гистограммы.
Итеративное формирование амплитудных значений изоморфных гистограммных образов. Иерархическая последовательность вложенных разбиений яркостной шкалы на диапазоны допустимого варьирования значений яркости запоминается (задается) непосредственно в амплитудных значениях изоморфного гистограммного образа, который формируется независимо от линейных и нелинейных изоморфных преобразований, в частности, упаковки изображения по яркости. При этом каждое амплитудное значение гистограммного образа на той или иной итерации помечает последовательные значения шкалы яркости изображения, отнесенные к соответствующему вычисляемому диапазону, и находится по амплитудному значению изоморфного гистограммного образа посредством рекуррентного арифметического преобразования A, которое определено выше.
Пользуясь тем, что гистограммные образы не зависят от упаковки изображения, поясним построение изоморфного гистограммного образа (и вместе с ним - всей иерархии гистограммных образов) на примерах упакованного по яркости изображения с 7-10 встречающимися значениями яркости. Для простоты полагаем, что пиксели с различной яркостью встречаются на изображении одинаковое число раз. В этом случае построение изоморфного гистограммного образа сводится к итеративному разбиению шкалы яркости (в виде отрезка целочисленной длины) на равные части, которое запоминается в амплитудных значениях гистограммного образа.
Запоминание иерархии разбиений дискретных отрезков. Фиг.8 иллюстрирует запоминание иерархии разбиений дискретных отрезков (рядов одинаковых ячеек) целочисленной длины. Вверху - рассматриваемые отрезки. Внизу под ними - последовательные результаты итеративного кодирования иерархии разбиений шкалы яркости изображения на диапазоны, которые задаются построчно выписанными в ячейках амплитудными значениями гистограммных образов.
На начальной итерации амплитудные значения гистограммного образа полагаются равными 0 (заполненные нулями строки таблиц Фиг.8). На каждой последующей итерации (следующие строки таблиц) рассматриваемое амплитудное значение удваивается и к нему добавляется 0, 1 или 2, в зависимости от того, где находится это значение - в левой части, в центре, либо в правой части текущего диапазона из одинаковых амплитудных значений. Формирование амплитудных значений изоморфного гистограммного образа завершается, когда каждое из них оказывается отличным от соседних. При этом построение самого изоморфного гистограммного образа достигается замещением яркостей пикселей изображения сформированными амплитудными значениями. Преобразование рассматриваемого матричного представления изображения в изоморфный гистограммный образ сводится к замещению величин яркости амплитудными значениями в виде номеров, которые присваиваются яркостям с сохранением порядка, но не обязательно последовательно (Фиг.8). При этом результирующий гистограммный образ является изоморфным рассматриваемому представлению изображения по яркостному порядку. Гистограммный образ, который получается замещением яркостей рассматриваемого изображения амплитудными значениями, вычисленными на промежуточной итерации, оказывается гомоморфным изображению по яркостному порядку. Гомоморфные гистограммные образы (или просто гистограммные образы) получаются из изоморфного гистограммного образа посредством рекуррентного применения деления нечетных амплитудных значений нацело на два, а четных - удвоения результата деления нацело на четыре. При этом изоморфный гистограммный образ определяет иерархию (иерархическую последовательность) промежуточных гистограммных образов, каждый из которых можно получить, применяя к значениям изоморфного гистограммного образа арифметическое преобразование необходимое число раз.
Более подробно иллюстрируемый на Фиг.8 справа пример построения гистограммного образа для десяти значений яркости, встречающихся в упакованном изображении одинаковое число раз поясняется следующим.
Рассматривается последовательность упорядоченных по возрастанию значений яркости ячеек яркостной шкалы, количество которых в данном случае равно количеству встречающихся в изображении значений яркости.
На начальной итерации (вторая строка на Фиг.8 справа) во все ячейки записывают нули - начальные значения амплитуд формируемого гистограммного образа, которые сопоставляются значениям яркости преобразуемого изображения. На начальном этапе имеется только один диапазон значений яркости от 0 до 10, заданный единственной последовательностью нулевых амплитудных значений гистограммного образа.
На каждой следующей итерации все амплитудные значения удваиваются. После этого к каждому амплитудному значению добавляется, соответственно, 0, 1 или 2 в зависимости от того, где находится это значение - в левой части (ближе к левому краю), в центре, либо в правой части (т.е. ближе к правому краю) предыдущего диапазона из одинаковых амплитудных значений.
Таким образом, на первой итерации (третья строка на Фиг.8 справа) последовательность ячеек разделяется на два диапазона равной длины и к удвоенному значению ячейки их предыдущей строки добавляют 0 или 2 для значений яркости слева и справа от центра диапазона.
На второй итерации (четвертая строка на Фиг.8 справа) амплитудные значения во всей последовательности удваиваются (с получением значений 0 и 4 для ячеек слева и справа от середины предыдущего диапазона), после чего каждый из двух диапазонов (помеченных 0 и 4) разделяется на три части: два диапазона равной длины и центральное значение, равноудаленное от левого и правого края. Далее в каждом из диапазонов из 5 ячеек добавляют значения 0 и 2 для значений яркости в ячейках слева и справа от центральной ячейки и 1 для значения самой центральной ячейки.
На третьей итерации (пятая строка на Фиг.8) значения яркости всей последовательности снова удваивают, и каждый диапазон, полученный на предыдущем этапе, делят аналогично предыдущим итерациям на две/три части и формирование амплитудных значений заканчивают, поскольку каждый результирующий диапазон оказывается помеченным неповторяющимся амплитудным значением гистограммного образа, т.е. содержит единственное значение яркости.
При этом формирование амплитудных значений гистограммного образа завершается, когда каждое из них оказывается отличным от соседних. Для построения гистограммного образа остается заменить значения яркости пикселей изображения сформированными амплитудными значениями. Очевидно, что окончательно сформированный гистограммный образ является изоморфным исходному изображению, а каждый из промежуточных - гомоморфным исходному изображению.
Фиг.8 следует трактовать как абстрактную схему вычисления изоморфного гистограммного образа, который строится по гистограмме яркости. При этом адресами ячеек, в которых формируются амплитудные значения изоморфного гистограммного образа служат яркостные значения пикселей, отсчитываемые по горизонтальной оси гистограммы, в которой количество пикселей откладывается по вертикальной оси. Количество пикселей слева и справа от рассматриваемого яркостного значения в общем случае изоморфного гистограммного образа используется вместо метрической длины строки ячеек.
Формирование амплитудных значений гистограммного образа по гистограмме. Более точно, формирование амплитудных значений изоморфного гистограммного образа выполняется в соответствии с описанным ниже алгоритмом, который обеспечивает итеративное вычисление амплитудного значения изоморфного гистограммного образа для каждого встречающегося на изображении значения яркости.
При этом рассматриваются встречающиеся в изображении значения яркости (без учета "пустых" значений с нулевыми пиками гистограммы (поскольку при упаковке изображения изоморфный гистограммный образ не меняется, можно, не уменьшая общности, все яркостные значения из рабочего диапазона считать встречающимися на изображении)), которые на горизонтальной оси гистограммы сначала помечаются нулевыми амплитудными значениями гистограммного образа (т.е. каждому встречающемуся значению яркости сопоставляется начальное амплитудное значение гистограммного образа, равное нулю).
Затем выделяются диапазоны значений яркости, помеченных одинаковыми амплитудными значениями гистограммного образа, и каждый из диапазонов обрабатывается как рабочий диапазон яркости самостоятельного изображения. Обработка состоит в удвоении амплитудных значений гистограммного образа и увеличения их на 0, 1 или 2 в зависимости от суммы пиков рассматриваемого участка гистограммы слева и справа от данного значения яркости. В результате каждая последовательность одинаковых амплитудных значений гистограммного образа разделяется на 2-3 новых последовательности либо остается последовательностью из одного элемента, если содержит единственное значение яркости. Процесс разделения диапазонов на 1-3 части итеративно продолжается до тех пор, пока не окажется, что все диапазоны содержат по одному значению яркости.
Обработка диапазона значений яркости на очередной итерации состоит в следующем.
Соответствующее (текущее) значение гистограммного образа удваивается.
1. Подсчитывается сумма пиков гистограммы, расположенных левее текущего пика гистограммы, а также сумма пиков гистограммы, расположенных правее текущего пика (текущий пик не участвует в суммировании).
2. Если левая и правая сумма совпадают, то к удвоенному значению текущего гистограммного образа прибавляется единица. В противном случае, если левая сумма пиков меньше правой, то удвоенное значение текущего гистограммного образа оставляют неизменным, либо увеличивают на двойку, если левая сумма превосходит правую.
Базовое идемпотентное встраивание битового сообщения
Обратимое встраивание сообщения в базовом варианте состоит в следующем.
При встраивании сообщения в контейнер вычисляют изоморфный гистограммный образ контейнера, который задает полную иерархию гистограммных образов. Задают числом Мерсенна желаемое число μ градаций амплитудной шкалы, редуцируют изоморфный гистограммный образ посредством арифметического преобразования A до желаемого числа градаций. Параметр μ определяет величину допустимого варьирования яркости и играет роль, аналогичную той, которую играет количество модифицируемых младших бит в LSB-методе.
Посредством гистограммного образа, построенного в шкале из μ амплитудных градаций, разделяют пиксели изображения на пиксели контекста и пиксели модифицируемой (варьируемой) яркости, вычисляют допустимые диапазоны модификации яркостей контейнера, а затем записывают биты сообщения в яркости модифицируемых пикселей контейнера, пропуская пиксели контекста. Запись сообщения осуществляется во все пиксели изображения, значение яркости которых не является центральным или граничным. При этом пикселями не модифицируемого контекста считают пиксели граничных яркостей, а также пиксели со среднеарифметическим значением граничных яркостей. Остальные пиксели относят к пикселям с варьируемой яркостью, которые используют при кодировании битов сообщения посредством отражения значений яркости варьируемых пикселей относительно центральных значений диапазонов.
Процесс записи одного экземпляра встраиваемого сообщения согласно настоящему изобретению прекращается после завершения поступления данных этого сообщения. Для повышения робастности встраивают множество копий одного сообщения последовательно в один контейнер. Для считывания сообщения достаточно, чтобы его биты записались в той или иной копии хотя бы однажды.
При извлечении сообщения из стего-изображения на приемном конце вычисляют изоморфный гистограммный образ стего-изображения и посредством арифметического преобразования A редуцируют его до числа μ градаций яркостной шкалы. При этом в точности воспроизводится гистограммный образ контейнера, использованный до встраивания битов сообщения в изображение. В отсутствие искажений при передаче также сохраняется разделение пикселей изображения на пиксели контекста и пиксели с модифицируемой яркостью, и по гистограммному образу восстанавливаются диапазоны допустимого варьирования значений яркости. По положениям значений яркости пикселей стего-изображения относительно центров диапазонов допустимого варьирования в координатах варьируемых пикселей декодируют биты сообщения.
Для подавления возможных искажений арифметически суммируют декодированные в виде ±1 биты сообщения с учетом повторений в поле изображения копий сообщения заранее определенных размеров, получают положительные, отрицательные или нулевые суммарные арифметические значения пикселей сообщения, которые интерпретируют, соответственно как установленные, неустановленные и неопределенные биты сообщения в виде бинарной матрицы сообщения.
Благодаря параметру μ (аналога числа модифицируемых бит LSB-метода) достигается регулировка амплитуды и управление геометрическим распределением кодов сообщения в режиме реального времени. Указанный параметр определяет выбор канала для встраивания сообщения, заданный одним из вложенных разбиений рабочего диапазона шкалы яркости, которое задает диапазоны допустимого варьирования значений яркости пикселей изображения. Встраивание кодов сообщения в пиксели с одинаковыми допустимыми диапазонами варьирования яркости выполняется точно так же, как в максимальный канал составленного из этих пикселей самостоятельного изображения (посредством зеркального отражения значений яркости в рассматриваемом диапазоне допустимого варьирования этих пикселей). Поскольку c возрастанием параметра μ диапазоны допустимого варьирования яркости нефиксированных пикселей уменьшаются, уменьшается и амплитуда встраиваемого сигнала сообщения.
Для лучшего сокрытия сообщения, проявляющегося на изображении из-за недостаточной частоты, к нему добавляют высокочастотную составляющую, которую учитывают при извлечении сообщения.
Полноцветные 24-битовые изображения рассматривают как три 8-битовых полутоновых изображения и при встраивании и извлечении сообщения обрабатывают по цветовым компонентам независимо друг от друга.
Инвариантное встраивание сообщения
Инвариантное обратимое встраивание сообщения независимо от изоморфных преобразований стего-изображения выполняется по алгоритмам базового встраивания и отличается тем, что перед встраиванием сообщения исходный контейнер предварительно преобразуется в гистограммный образ, а перед извлечением сообщения в свой гистограммный образ преобразуется стего-изображение, на случай искажений при передаче.
К параметру μ, который задает число градаций гистограммного образа, используемого при разделении пикселей изображения на пиксели с немодифицируемой яркостью и с варьируемой яркостью, добавляется параметр μ1, который задает инвариантный гистограммный образ, используемый при генерации инвариантного стего-изображения вместо изображения. Таким образом, при инвариантном встраивании имеем два управляющих параметра в виде чисел Мерсенна. μ1- параметр, который по сравнению с LSB-методом задает новую возможность - снижение числа градаций, но при приеме он считается известным точно так же, как и параметр μ.
Встраивание в гистограммный образ изображения выполняется со снижением числа фактически встречающихся градаций яркости. Однако, поскольку изоморфные гистограммные образы строятся в формальной шкале, число градаций которой обычно превышает число градаций в диапазоне яркости [0, 255], предусмотренном для хранения изображений в ЭВМ, в дополнение к преобразованию контейнера в гистограммный образ удобно использовать упаковку изображения по яркости, что не меняет сущности расчетов.
Таким образом, в базовом алгоритме встраивания сообщения все экземпляры экстремальных яркостей фиксируются, а экземпляры промежуточных яркостей модифицируются при записи сообщения. В алгоритме инвариантного встраивания (относительно определенных преобразований яркости) граничные яркости также фиксируются, но изображение предварительно преобразуется в "гистограммный образ".
Встраивание двух независимых компонент
Дополнительное, вторичное, сообщение встраивают в шумовую компоненту сигнала до или после обратимого добавления шума к первоначальному стего-изображению с ограниченным числом градаций и инвариантно встроенным сообщением. Как самостоятельный сигнал, шум, обратимо добавленный в стего-изображение с возможностью подавления в смысле восстановления порядка яркостей контейнера (но не обязательно самих яркостей), порождает дополнительную компоненту. Например, если вместо яркостей 1, 2, 3, 4 получают 1, 23, 34, 400, то восстанавливается порядок яркостей, но не сами яркости, или яркости восстанавливают с точностью до изоморфного преобразования, так как точно восстановить значения яркости после зашумления и перераспределения в рабочем диапазоне оказывается затруднительно.
Две независимых компоненты одного сообщения или, другими словами, два сообщения встраивают в контейнер последовательно. На первом этапе сначала выполняют встраивание в контейнер первого сообщения с одновременным снижением числа градаций стего-изображения по сравнению с числом градаций контейнера. Снижение числа градаций нужно, чтобы можно было добавить шум для встраивания второго сообщения. Если в контейнере градаций изначально мало, то снижение числа градаций не является необходимым. Затем выполняют эквидистантную нормировку яркостей стего-изображения и в него с возможностью подавления добавляют шум. При этом за счет эквидистантной нормировки повышается резкость изображения.
На следующем этапе встраивают вторую компоненту сообщения. Для этого зашумленное стего-изображение раскладывают в сумму стего-изображения и шумового представления, в шумовое представление встраивают второе сообщение, и затем шумовое представление со встроенным вторым изображением добавляют к первоначальному стего-изображению. В результате суммирования получается требуемое стего-изображение со встроенной парой сообщений.
Таким образом, двухкомпонентное встраивание сообщения сводится к инвариантному встраиванию сообщения в контейнер с одновременным снижением числа градаций яркости и обратимому добавлению шума со встроенной дополнительной компонентой сообщения. Благодаря тому, что дополнительная компонента сообщения встраивается в шум посредством отражения значений яркости относительно центральных значений допустимых диапазонов варьирования яркости и без снижения числа яркостных градаций шума, характер гистограммы первоначального стего-изображения с добавленным шумом при этом не меняется, и возможность выделения шума сохраняется.
Общий объем данных, встраиваемых по двум каналам, составляет 15-20% от объема контейнера.
Примеры
Описание программной реализации 2-компонентного встраивания
Изобретение выработано в процессе программных экспериментов по неявному встраиванию сообщения в 8-битовые полутоновые и 24-битовые полноцветные изображения, обрабатываемые по цветовым компонентам как три независимых полутоновых изображения.
Основной целью первых экспериментов являлось тестирование вычисления объема (количества кодов) встраиваемого битового сообщения независимо от содержания сообщения, а также проверка возможности практического встраивания битового сообщения независимо от стандартных преобразований стего-изображения. В последующих экспериментах исследовалось принципиальная возможность встраивания битов сообщения с наложением по координатам за счет разделения стего-изображения на две компоненты.
При решении задачи встраивания в изображение произвольного сообщения в качестве последнего рассматривались варианты двухградационного представления сообщения в границах изображения, порождаемого некоторой бинарной матрицей с размерами, меньшими соответствующих размеров изображения. За счет периодического повторения кодов бинарной матрицы сообщения исключался случай достижения конца записываемого сообщения, однако, допускалось, что в зависимости от контейнера, некоторые биты фактического "привязанного" к координатам представления сообщения не помещаются в контейнер и при чтении (а также при записи) считаются неопределенными.
Встраивание битов сообщения с повторениями выполнялось за счет периодического повторения в поле изображения исходной бинарной матрицы сообщения в целом. При этом размеры бинарной матрицы сообщения являются параметрами, которые необходимо указать при приеме. Другими возможными параметрами являются преимущественно высокие частоты искусственно вносимого несущего сигнала, на который накладывается сообщение с целью визуального сокрытия сообщения.
Правильность вычислений контролировалась при встраивании посредством извлечения битов сообщения из стего-изображения и проверкой на совпадение с битами сообщения.
Программная реализация изобретения является достаточно сложной логической задачей, если представлять обработку в терминах преобразования исходных пикселей изображения. Постановка и программная реализация алгоритмов существенно упрощается благодаря использованию отлаженного модуля генерации иерархии гистограммных образов, посредством которой вычисляются промежуточные и выходные матричные представления изображения. При этом основными матричными представлениями изображения, вычисляемыми по изображению, являются (в порядке приоритета вычислений):
- представление изображения в виде изоморфного гистограммного образа, который задает иерархию (гомоморфных) гистограммных образов;
- приближения изображения снизу и сверху, ограничивающие допустимые диапазоны варьирования яркости изображения;
- бинарное представление сообщения в границах изображения.
Для экспериментального осуществления изобретения создана программа сокрытия пары битовых сообщений в каждой из RGB-компонент изображения, в которой сокрытие двух сообщений обеспечивается разделением цветовой компоненты на два аддитивных представления и встраиванием в каждое из указанных представлений, фактически, по одному битовому сообщению.
Встраивание сообщения выполняется программой по 4 алгоритмам при последовательном выборе для каждого из них начального разбиения изображения на независимые зоны пикселей посредством гистограммного образа в
Экспериментальные результаты
Изобретение выработано в процессе программных экспериментов, результаты которых иллюстрируются на примере изображения "Лена" размером 1084×2318 пикселей, взятого в качестве контейнера и сообщения в виде фрагмента размером 296×525 пикселей карты Берлинской операции, преобразованной к 8 цветам по определенному алгоритму с использованием иерархии гистограммных образов.
На Фиг.9 показан контейнер и его изоморфный гистограммный образ, а также оригинальное и преобразованное сообщение. Для обоих преобразований характерно улучшение резкости изображения. На Фиг.9 в верхнем ряду изображены исходное изображение (слева) и изоморфный гистограммный образ, линейно нормированный на рабочий диапазон яркости (справа). В нижнем ряду представлен фрагмент карты в первоначальном виде (слева) и в виде сообщения, представленного в 8 цветах (справа, показано в эквидистантной нормировке на рабочий диапазон яркости).
Базовое встраивание сообщения
Результат встраивания сообщения (фрагмента карты в 8 цветах) в контейнер иллюстрируется Фиг.10. На Фиг.10 в верхнем ряду изображены: контейнер (слева) и стего-изображение (справа). Под представлениями в нижнем ряду - соответствующие гистограммы яркости.
Для вычисления диапазонов допустимого варьирования яркости взят гистограммный образ, построенный в 63 градациях амплитудной шкалы.
Инвариантное встраивание сообщения
Фиг.11 иллюстрирует результат инвариантного встраивания сообщения в гистограммный образ изображения "Лена", выполненный в 7 градациях шкалы яркости.
Встраивание сообщения в контейнер выполнено с одновременным снижением числа фактических градаций до 4. Оба представления стего-изображения содержат одно и то же сообщение в виде фрагмента карты в 8 цветах, которое не зависит от нелинейных изоморфных преобразований, в данном случае, стандартных преобразований упаковки и эквидистантной нормировки стего-изображения. На Фиг.11 имеется единственный диапазон значений яркости, содержащий 4 значения яркости - пару граничных и пару модифицируемых. В упакованном виде достигается визуальное сокрытие контейнера вместе с сообщением, так как перепады между значениями яркости малы (вертикальные линии на гистограмме на Фиг.11 сливаются друг с другом в затемненную полосу). Для зрительного сокрытия факта встраивания в сигнал сообщения добавлена высокочастотная составляющая. Характерно, что незаметное встраивание достигается при кодировании сообщения достаточно большими перепадами яркости, поскольку при четырех градациях все встречающиеся перепады яркости сравнимы между собой.
Фиг.11 представляет инвариантное встраивание сообщения. В верхнем ряду приведено стего-изображение, упакованное по яркости (слева), и эквидистантно нормированное на рабочий диапазон яркости (справа), при этом перепады между значениями яркости увеличиваются, что видно на гистограмме под рисунком, и изображение становится видимым. В нижнем ряду - соответствующие яркостные гистограммы по R-компоненте.
Встраивание двух компонентов
На Фиг.12 изображение включает большее количество градаций, а именно 16 встречающихся из 31 градаций амплитудной шкалы (число градаций яркости зависит от второго параметра Мерсенна μ1). На чертеже показана гистограмма стего-изображения с первоначальным сообщением и обратимо добавленным шумом. Затемненные 16 полос на гистограмме указывают диапазоны, в центральные значения яркости которых добавлена шумовая составляющая, т.е. одно значение яркости "размыто" шумом. Сообщение в виде фрагмента карты встроено в гистограммный образ изображения "Лена", полученный в шкале из 31 амплитудной градации. Шум (2,7%), добавлен посредством системного редактора PhotoShop.
На Фиг.12 приведена яркостная гистограмма по одной из RGB-компонент (остальные гистограммы имеют аналогичный вид). Шум добавлен с возможностью подавления, при этом при подавлении шума яркости стего-изображения с точностью до изоморфизма восстанавливаются благодаря использованию промежутков между ненулевыми значениями гистограммы. При этом промежутки задают последовательные диапазоны яркости, и яркости пикселей каждого диапазона с сохранением порядка замещаются одним значением, например, номером диапазона. Соотношение параметров μ, μ1 инвариантного встраивания первого сообщения при встраивании первого сообщения в гистограммный образ контейнера взято таким, что биты первого сообщения встраиваются примерно в половину пикселей гистограммного образа контейнера.
Окончательный результат двухкомпонентного встраивания сообщений по двум независимым каналам на заднем плане демонстрируется на Фиг.13. На Фиг.13 представлены цветовое стего-изображение с сообщениями в виде изображения карты в 8 цветах (внизу), встроенного в контейнер со снижением числа градаций яркости, и фотографии в 2 тонах (справа вверху), встроенной в добавленную шумовую компоненту.
В качестве встраиваемой в шум дополнительной компоненты сообщения взята фотография, которая составлена из одинаковых цветовых компонент и содержит две градации яркости, что обеспечивает дополнительную возможность подавления помех за счет учета повторений битов сообщения по цветам. В остальных отношениях совпадение RGB-компонент не принципиально - фотография, как и карта, может содержать 8 цветов. Встраивание первоначального сообщения (карты) для визуального сокрытия выполнено с добавлением в сигнал сообщения высокочастотной составляющей. Встраивание дополнительного сообщения в шумовую компоненту выполнено для разбиения диапазона яркости шумового представления на 16 начальных диапазонов Фиг.12. При этом биты дополнительного сообщения сопоставляются положению яркости пикселя стего-изображения в той или иной половине соответствующего диапазона. Т.е. когда каждая яркость дополнительного сообщения попадает в тот или иной диапазон, то ее кодируют установленным битом сообщения, если она превышает центральное значение яркости диапазона, в противном случае - неустановленным.
Суммарный объем кодов двух встроенных сообщений составляет приблизительно
Робастное встраивание сообщений
Фиг.14 демонстрирует эффект использования геометрического повторения кодов сообщения для подавления искажений при передаче стего-изображения. В качестве непредусмотренного воздействия на стего-изображение рассматривается JPEG-преобразование, и более конкретно - влияние JPEG- преобразования на сообщение (левое верхнее), встроенное в контейнер посредством гистограммных образов в 3, 7 и 15 амплитудных градациях (правое верхнее, левое и правое нижние, соответственно).
Сохранение сообщения обеспечивается его кодированием с повторениями и относительно большими перепадами яркости благодаря заданию диапазонов допустимого варьирования яркостей контейнера посредством гистограммных образов с ограниченным числом градаций амплитудной шкалы. При этом предусмотрена количественная оценка степени искажения сообщения, которая выражается отличием числа повторений по координатам битов сообщения от максимальной величины. В отсутствие искажений указанная оценка обращается в 0.
Среда для реализации настоящего изобретения
Описание примерной рабочей среды для реализации настоящего изобретения является только одним примером подходящей вычислительной среды и не предназначено для наложения каких-либо ограничений на использование или функциональные возможности изобретения.
Изобретение может быть описано посредством выполняемых компьютером программных модулей. Обычно программные модули включают в себя подпрограммы, программы, структуры данных и т.д., которые выполняют конкретные задачи. Кроме того, специалистам в данной области техники понятно, что изобретение может быть применено во множестве конфигураций компьютерных систем, включающих в себя портативные устройства, многопроцессорные системы, миникомпьютеры, универсальные компьютеры и т.п. Изобретение также может быть применено в распределенных вычислительных средах, с помощью выполнения операций удаленными обрабатывающими устройствами, которые соединены посредством сетей связи. В распределенной вычислительной среде программные модули могут быть расположены как на локальном, так и на удаленном запоминающем устройстве.
Пример системы для реализации изобретения включает в себя вычислительное устройство общего назначения в виде компьютера, включающего в себя процессор (средство обработки), системную память и системную шину, которая соединяет различные компоненты системы, включая системную память и процессор.
Компьютер обычно включает в себя множество считываемых компьютером носителей. В качестве примера, а не ограничения, считываемые компьютером носители могут включать в себя носители компьютерной памяти и коммуникационные носители. Примеры носителей компьютерной памяти включают в себя оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), электрически стираемое программируемое постоянное запоминающее устройство (ЭСППЗУ), флэш-память или другие технологии памяти, ПЗУ CD-ROM, DVD или запоминающие устройства другого типа.
Компьютер может также включать в себя другие носители компьютерной памяти, например, накопитель на жестком диске, накопитель на магнитном диске, накопитель на оптическом диске и другие. Запоминающие устройства обычно соединены с системной шиной с помощью соответствующих интерфейсов, очевидных для специалистов.
Пользователь может вводить команды и информацию в компьютер посредством устройств (средств) ввода, например, клавиатуры, устройства указания, такого как мышь или сенсорная панель, средства приема входного радиосигнала и т.п. Другие устройства ввода могут включать в себя микрофон, джойстик, антенну, сканер и т.д. Эти и другие устройства ввода соединены с процессором посредством соответствующего интерфейса устройств ввода.
Устройство (средство) отображения также соединено с системной шиной через интерфейс, например видеоинтерфейс. Средство отображения может быть любым средством, отображающим выходные данные: монитором, жидкокристаллическим экраном, обычным телевизором или экранным проектором. Кроме средства (устройства) отображения компьютер может также включать в себя другие периферийные устройства вывода, такие как принтер, которые могут быть соединены посредством интерфейса устройств вывода.
Компьютер в настоящем изобретении может работать в сетевой среде с использованием соединений с одним или более удаленными компьютерами. Соединения включают в себя локальную вычислительную сеть и глобальную вычислительную сеть, но могут также включать в себя другие сети, такие Internet. Специалистам понятно, что такие компоненты и взаимные соединения являются хорошо известными.
Как упомянуто ранее, настоящее изобретение может быть описано посредством используемых компьютером программ выполнения операций. Используемые компьютером инструкции включают в себя функции, процедуры, подпрограммы, сегменты программ и модули, используемые одним или более компьютерами или другими устройствами. Используемые компьютером инструкции образуют интерфейс для того, чтобы дать возможность компьютеру реагировать в соответствии с входными данными. Инструкции взаимодействуют с другими сегментами программ, чтобы инициировать множество задач в ответ на данные, принятые вместе с источником принятых данных.
Однако настоящее изобретение также может быть реализовано посредством только компьютерного аппаратного обеспечения, например, реализуя блоки (средства) обработки в виде специализированных интегральных схем, на основе программируемых логических матриц и т.п., как очевидно специалистам в данной области техники.
Все возможные варианты осуществления изобретения в виде программных, аппаратных и программно-аппаратных средств охватываются формулой изобретения и не ограничиваются каким-либо одним примером реализации.
Изобретение относится к области цифровой стеганографии или встраивания в цифровое изображение произвольных водяных знаков, и, конкретнее, к области прямого, без спектральных преобразований, обратимого встраивания произвольных водяных знаков посредством квантования и модификации амплитудных значений сигнала в условиях, когда оригинальное изображение (контейнер) не доступно, а передаваемое сообщение не известно на приемном конце - технология слепого встраивания. Технический результат заключается в повышении эффективности сокрытия сообщений. Предложен способ встраивания произвольного бинарного сообщения в цифровое изображение посредством изменения яркости пикселей изображения, содержащий этапы итеративного разделения шкалы яркости всего изображения на последовательные диапазоны, причем для каждого из диапазонов, полученных на одной из промежуточных итераций, определяют не изменяющуюся и варьируемую при встраивании сообщения компоненты изображения, и встраивания битов сообщения в пиксели варьируемой компоненты изображения посредством либо принятия значения яркости пикселя изображения в качестве пикселя, содержащего встраиваемое сообщение, либо зеркального отражения значения его яркости относительно центрального значения яркости для упомянутого диапазона. 3 н. и 7 з.п. ф-лы, 14 ил.
Способ и устройство обнаружения водяного знака для определенных масштабов и произвольных сдвигов