Техника "водяных знаков"
Изначально техника маркирования изображений цифровыми «водяными знаками» (а позднее и цифровых аудиосигналов и видеоданных) была разработана для защиты авторских прав). В предлагаемой вашему вниманию статье описывается нетрадиционный способ использования «водяных знаков».
В данной статье мы предлагаем рассмотреть технику «водяных знаков» для обнаружения искажений в цифровых изображениях. Эта техника дает нам возможность выделить побочные (искажающие) изменения свойств, появившиеся в результате обработки изображения, путем сравнения коррелированных величин из различных его частей. Для реализации этой техники требуется незначительный объем памяти и небольшие вычислительные мощности, что делает возможным ее применение для аппаратной реализации в цифровых фотоаппаратах.
Техника представляет собой деление изображения на блоки и маркирование этих блоков «водяными знаками», зависящими от секретного ключа (идентификационного номера камеры) и протяженности изображения. Данный метод «водяных знаков» базируется на использовании широкополосных сигналов. Для достижения непрерывной зависимости от изображения мы предлагаем специальный процесс извлечения отдельных битов из каждого блока с учетом порогового значения, сгенерированного на основе зависимых от ключа случайных гладких шаблонов. Далее эти биты используются для инициализации PRNG и синтеза широкополосного сигнала.
1. Введение
Мощные общедоступные графические пакеты, такие как, например, Adobe Photoshop или Paintshop Pro, имеют в своем арсенале различные инструменты, способные серьезно изменить реальные изображения. Это может быть и совмещение различных частей одного или нескольких изображений, причем настолько качественное, что границ просто незаметно. Подобную модификацию (монтаж) изображения в ряде случаев можно обнаружить при исследовании зашумления различных частей изображения путем сравнения гистограммы непересекающихся блоков изображения или путем поиска нарушения непрерывности областей. Однако опытные фальсификаторы делают монтаж так, что обнаружить подлог практически невозможно.
Возможность обработки изображения является одной из причин того, что они никогда не принимаются в качестве вещественного доказательства. С другой стороны, в некоторых сферах деятельности (особенно для военных) очень важно знать, была совершена подделка полученного цифрового изображения или нет.
Для эффективного обнаружения подделки изображения может быть использована техника маркирования «водяными знаками», с помощью которой помечаются небольшие блоки изображения, «Водяные знаки» будут зависеть от секретного ключа, используемого в дальнейшем при обнаружении модификации изображения.
Одной из первых техник, применяемых для обнаружения искажений (модификации) изображения, была техника, основанная на внедрении контрольных сумм в наименьший значащий бит (LSB). Уэлтон [1] предложил технику, в которой используется зависимая от ключа псевдослучайная последовательность, «гуляющая» по изображению. Контрольная сумма строится из семи старших битов и вставляется в LSB выбранных пикселей. Контрольную сумму делают «гуляющей» для того, чтобы предотвратить модификацию обменивающихся групп пикселей с той же контрольной суммой. Однако, хотя контрольные суммы и могут обеспечить очень высокую вероятность обнаружения изменений, они не могут различить регулировку яркости и модификацию, изменяющую лицо на изображении. Увеличение градаций серого для всех пикселей дает более значительные изменения, даже если изображение остается неизменным и пригодным для использования.
Ван Шиндел и др. [2] модифицировали LSB пикселей, добавив длинную т-последовательность к рядам пикселей, фаза которой несет информацию о «водяном знаке». В качестве теста для определения наличия «водяного знака» используется простая кросс-корреляция. Этот способ при любой LSB технике обеспечит низкий уровень безопасности и не будет устойчив к операциям обработки изображения с низкочастотными характеристиками.
Вольфганг и Делн [3] расширили работу Ван Шиндела и улучшили свойства локализации и ошибкоустойчивости. Они использовали m-последовательность в пределах (-1,1), размещенную в блоках размером 8х8 пикселей, и добавили их к соответствующим блокам изображения. Их техника является умеренно стойкой по отношению к прямолинейной и нелинейной фильтрации и небольшому добавочному (дополнительному) шуму. Однако, поскольку «водяной знак» вставлен в LSB плоскости, он может быть легко удален.
Цю и др. [4] предложили техники, основанные на использовании маскирования в пространственной и частотной области. Такие «водяные знаки» являются гарантированно невидимыми, но тем не менее позволяют выявлять ошибки более половины максимально допустимых изменений в каждом пикселе или частоте в зависимости от используемой техники маскирования. Изображение делится на блоки, в каждом из которых фиксируется секретная случайная подпись, промодулированная маскирующим значением этого блока. При этом оценка погрешности для маленьких искажений получается достаточно точной.
Однако неясно, может ли эта техника обеспечить необходимую информацию для изображений, искажения в которых видны на глаз.
В этом случае лучше использовать более стойкую схему маркирования «водяными знаками», применяемую к большим блокам. «Водяные знаки» в описанном методе [4] в слабой степени зависят от изображения.
Секретная подпись не должна зависеть от изображения — она модулирована маскирующими значениями каждого блока. Но эти маскирующие значения доступны и могут быть легко вычислены. Маркирование большого количества изображений с одним секретным ключом не будет безопасным, поэтому эту технику нельзя использовать в цифровых камерах (фотоаппаратах).
В данной статье мы описываем технику, в которой используются стойкие «водяные знаки» для больших блоков (64х64 пикселей). Для предотвращения несанкционированного устранения или искажения «водяной знак» должен зависеть от секретного ключа S (ID), количества блоков В и от содержания блока. Содержание каждого блока представляется с М битами, извлеченными из блока при использовании случайного гладкого шаблона и определенного порогового значения. В результате получается М-кортеж (упорядоченный набор) для подобных блоков, позволяющий успешно синтезировать широкополосный сигнал маркированного искаженного изображения. Широкополосный сигнал для каждого блока генерируется сложением псевдослучайной М-последовательности однородно распределенной в (-1, 1). Причем каждая последовательность зависит от секретного ключа, номера блока и бита, извлеченного из блока. Если k из М битов извлечены неправильно из-за искажения изображения, то широкополосный сигнал будет иметь большую корреляцию с изображением до тех пор, пока k << М.
Широкополосный сигнал масштабируется, делается независимым от DC компонентов и добавляется к среднему значению третьих DCT-коэффициентов для каждого блока. Процедура обнаружения производится поблочно, восстанавливаются М-биты для каждого блока, генерирующего широкополосный сигнал и коррелирующего со средним значением третьих DCT-коэффициентов.
Если «водяные знаки» присутствуют во всех блоках, можно быть уверенным, что изображение не модифицировалось (не было добавления или удаления свойств). С другой стороны, если корреляция «водяного знака» ниже однородности всех блоков изображения, можно сделать вывод, что некоторая обработка изображения носила прикладной характер. Далее на основе однородности изображения и наличия «водяного знака» в каждом блоке можно попытаться определить, какая операция (например, низкочастотный или высокочастотный фильтры, гамма-коррекция, зашумление и т. д.) была применена к данному изображению. Если один или более блоков демонстрируют очень низкие показатели наличия «водяного знака», в то время как в других блоках они высоки, то с высокой вероятностью можно сказать было модифицировано изображение или нет.
Во второй части мы детально рассмотрим технику маркирования «водяными знаками» для обнаружения модификации изображения и представим некоторые результаты экспериментов. Будущие направления исследований, возможные улучшения и практическая реализация будут обсуждены в третьей части.
2. Описание техники
Техника «водяных знаков», которая используется для обнаружения модификации изображений и может быть применена в цифровых фотоаппаратах, имеет свои особенности. Например, если специальные «водяные знаки» будет генерировать отдельный встроенный чип, то изображения будут промаркированы еще до сохранения их на носителе информации (например на жестком диске, флэш-карте и т.п.). В этом случае не будет немаркированных изображений. При таком подходе важным условием является сохранение качества изображения при невидимости «водяного знака». Другими условиями являются низкая вычислительная сложность и малый объем памяти. «Водяной знак» должен зависеть от изображения и секретного идентификационного номера камеры и выжить при использовании общих операций обработки изображений, таких как регулировка контраста и яркости, зашумления и сжатия с потерей данных. Однако в этом случае мы сталкиваемся с конфликтом между ошибкоустойчивостью и размером блока (при желании защитить маленькие части изображения уменьшается ошибкоустойчивость). Компромисс в этом конфликте был достигнут путем отказа от использования блоков размером 64х64 пикселя. При этом мы руководствовались тем, что при низком разрешении человеческое лицо, масштабированное к блоку размером 32х32 пикселя, становится нераспознаваемым.
При использовании техники, предложенной в начале этой статьи, изображение делится на блоки 64х64 пикселя. При маркировке каждого блока используется частота, основанная на технике применения широкополосного сигнала [5]. Обозначив i-й блок Вi, мы выполняем три следующих стадии для каждого блока.
Стадия 1. Извлечение М-последовательности бит изображения
В соответствии с определением безопасности образ «водяного знака» должен зависеть от блока. Для извлечения М (~30) бит из каждого блока необходимо разработать стойкий процесс для данной операции. С одной стороны, это важно для получения некоррелируемых М-кортежей для различных блоков и изображений, с другой стороны, М-кортежи должны быть отождествлены для всех подобных видимых блоков. Используя PRNG совместно с идентификационным номером, мы генерируем М случайные черные и белые образы Рi для блоков одного размера, сглаживая их низкочастотным фильтром и делая их независимыми от DC. Затем мы рассчитываем проекции этих стереотипов на блок изображения. Экспериментируя с блоками различных изображений, мы обнаружили распределение этих проекций, имевшее вид распределения Гаусса (см. рис. 1).
Рис.1.Распределение проекций на случайные гладкие образы
Если проекция на отдельном образе велика, маловероятно, что незначительное искажение изображения изменит это значение, и наоборот. Поэтому имеет смысл извлечь бит Bi из каждой проекции и сравнить его абсолютную величину с порогом Тp:
Bi = 1 если |Pi • Bi | > Тp,
Bi = 0 в противном случае.
Порог Тp был выбран так, чтобы приблизительно половина извлеченных битов имела значение, равное 1, а другая половина — 0. При этом условии извлеченные М-кортежи содержат наибольшее количество информации. Для проведения экспериментов мы взяли Тp = 2500.
Для тестирования процесса извлечения отдельных битов в блоках размером 64х64 пикселя в качестве экспериментального мы выбрали изображение Lenna. После применения к изображению операции blur (такой как в Paintshop Pro) из 50 бит мы смогли правильно восстановить по крайней мере 47. Регулирование яркости ±25% привело к неприемлемому осветлению или затемнению изображения, и мы получили 45 и 44 правильных бит соответственно. Добавление белого шума с распределением по Гауссу со средним квадратическим отклонением в пределах 36 градаций серого привело к получению 46 правильных бит. Другие общие операции обработки изображения, такие как, например, эквалайзер, увеличение и уменьшение глубины цвета и JPEG-преобразование с коэффициентом качества ниже 10%, дали примерно аналогичные результаты. При использовании коррекции ошибок реально можно извлечь 30 бит из каждого блока. Причем соотношение единиц и нулей в извлеченных 50 кортежах было равно 1/2.
Имеются две причины, по которым мы использовали сглаженные случайные шаблоны вместо белого шума. Во-первых, они менее восприимчивы к синхронизации, которая может быть важной, если изображение обрезалось или изменялся его размер. Во-вторых, наши эксперименты указывают, что извлечение отдельных бит, основанное на гладких шаблонах, более устойчиво по отношению к искажениям.
Стадия 2. Генерация широкополосного сигнала
Поскольку на стадии 3 производится модуляция средним значением третьих DCT-коэффициентов (D-коэффициенты) и используется широкополосный сигнал, мы сгенерировали псевдослучайную М-последовательность длиной D, однородно распространенную в (0, 1), сложили их и добавили к заранее заданному среднему квадратическому отклонению и среднему нулевому значению. Чтобы сгенерировать j-ю последовательность в блоке Вi, 1<=j<=M,c j-м извлеченным битом Bi, мы рассмотрели PRNG совместно с идентификационным номером фотоаппарата S, i, j и Bj. При этом важно, чтобы последовательности из различных блоков изображения и для различных извлеченных битов Bj были некоррелированы, поскольку встроенный чип содержит номер блока i и порядковый номер j явно.
В нашей реализации фактически использовано приближение [5] и скрывается последовательность из М символов для каждого символа, состоящего из r бит, в широкополосном сигнале. Для того чтобы спрятать М r-бит символов, мы генерируем псевдослучайную М-последовательность длиной D. Каждая последовательность выбирается случайным образом в качестве сегмента D чисел из D + r случайно сгенерированного числа. При этом широкополосный спектр представляет собой сумму этих сигналов. Чтобы выявить спрятанный символ, производится простое вычисление кросс-корреляции восстановленного коэффициента D DCT со сдвигом на сгенерированную D + r последовательность [5]. В наших экспериментах мы использовали фиксированный символ М, жертвуя, таким образом, ошибкоустойчивостью «водяного знака».
Стадия 3. Внедрение «водяного знака»
Мы вычисляем DCT для каждого блока и модулируем в среднем 30% DCT-коэффициентов, добавляя широкополосный сигнал. Для достижения равновесия между видимостью «водяного знака» и его ошибкоустойчивостью амплитуда добавленного сигнала изменится. Во время проведения экспериментов мы установили амплитуду равную 13 (при использовании симметричной формы DCT). Причем при использовании линеаризованной пространственной маскирующей модели Гирода [6] без временного аспекта «водяной знак» был виден для 0,17% всех пикселей.
Обнаружение «водяного знака» производится поблочно. Для каждого блока извлекаются М биты, а к блоку применяют DCT-преобразование.
Тогда широкополосный сигнал синтезируется с учетом идентификационного номера фотоаппарата и PRNG. В итоге М символы извлекаются из каждого блока путем выбора символов с большей корреляцией. Для каждого блока мы добавляем число правильно восстановленных символов и рассчитываем вероятность получения большинства правильных символов. При М г-бит символов вероятность Р (k, М) получения k правильных символов из М будет равна:
Порог, определяющий наличие «водяного знака» или свидетельствующий о том, что блок не модифицировался, должен рассчитываться на основе полученного значения вероятности, Например, Р (5,10) = = 2,3х10 ^ (-7), что определяет вероятность получения по крайней мере пяти из десяти правильных символов меньше, чем 1:4 000 000. Переставленный блок или выявленный «водяной знак» с неправильным ключом приводит к получению значительно больших значений Р.
Рис. 2. Результаты тестирования при использовании 1000 случайных ключей
Рисунок 2 показывает максимум Р (k, М), преобладающий на всех 16 блоках в изображении размером 256х256 пикселей для 1000 случайно сгенерированных секретных ключей.
По своей природе схемы маркирования с использованием «водяных знаков» и сами «водяные знаки» достаточно устойчивы к операциям регулирования контраста/яркости, эквалайзеру, зашумлению. Они даже выжили при применении двух последовательных операций blur (в Paintshop Pro).
Однако результаты проверки на ошибкоустойчивость по отношению к JPEG-преобразованию были менее удовлетворительны. При 50-процентном JPEG-сжатии некоторые блоки показали едва различимые «водяные знаки», хотя в других блоках знаки выжили. Детальный анализ ошибкоустойчивости этой техники по отношению к искажению изображения описан в другой статье [7]. В настоящее время мы изучаем другой вариант схемы [8] и возможность ее использования для обнаружения модификаций.
| Рис.3.Изображение «Лена», разделенное на блоки 64х64 пикселя. Прямоугольная область перемещена из соответствующей области немаркированного изображения |
|
Далее при испытании нашей схемы мы разрезали немаркированное изображение на прямоугольные части (см. рис. 3) и вставляли их в соответствующее маркированное изображение. При этом не было никаких видимых изменений, однако мы смогли обнаружить модификацию изображения, применив функцию обнаружения с правильным идентификационным номером (рис. 4). График отражает тот факт, что большая часть блоков 10 и11 заменена — вероятность Р очень велика. Неиспорченные блоки имеют вероятность, равную 10-18. Блоки 6 и 7 были заменены только частично, и поэтому вероятности в данном случае не так велики. Этот эксперимент показал, что «водяной знак» также достаточно устойчив к операции обрезки. Два испорченных блока 14 и 15 дали совсем незначительное увеличение вероятности.
Рис. 4. График обнаружения злонамеренных искажений
Очевидно, что ошибкоустойчивость «водяных знаков» прямо влияет на чувствительность процесса обнаружения искажений. С одной стороны, «водяные знаки» слишком восприимчивы к маленьким искажениям, их можно легко удалить простыми операциями обработки изображений. Это уменьшит наши возможности различать умышленные и неумышленные искажения. С другой стороны, стойкие «водяные знаки» не смогут выявить незначительные модификации изображения в отдельных его частях (из-за устойчивости к обрезке рисунка). Поэтому имеет смысл фактически совмещать техники внедрения контрольной суммы в LSB [3] с нашей техникой. Это даст возможность выявлять более широкий спектр модификаций изображения. Контрольные суммы будут применяться для обнаружения и локализации маленьких изменений, в то время как стойкие «водяные знаки» будут определять значительные модификации.
3. Улучшения и будущие направления исследований
Для практической реализации (если случайные гладкие стереотипы не хранятся, а генерируются для каждого изображения) объем необходимой памяти определяется количеством пикселей в двух блоках плюс длина широкополосного сигнала. Это приблизительно 9,3 Кбайт. Вычисление шаблона для каждого изображения не является необходимым процессом, и он может быть встроен в память камеры. При использовании М = 30 образов это потребует всего 30х64^2 байт, то есть 123 Кб.
Улучшить эффективность процесса обнаружения изменений при повороте и масштабировании позволит встраивание дополнительного калибровочного сигнала [9]. Чтобы улучшить ошибкоустойчивость по отношению к низкочастотной фильтрации и низкому качеству при JPEG-преобразовании, «водяные знаки» необходимо совместить с низкочастотными метками [10].
Проводя эксперименты, мы заметили, что обнаружение «водяного знака» в блоке сильно зависит от его содержания. Некоторые деформации изображения оставляют знаки практически неизменными в ряде блоков, в то время как в других блоках «водяные знаки» теряются. Обычно текстурированные блоки более надежно сохраняют знаки, чем блоки с относительно однородными областями. Мы можем попытаться дать классификацию различных блоков изображения, основанную на их содержании и оценке чувствительности «водяных знаков» к специфическим искажениям изображения. Это поможет определить различия между низкой корреляцией из-за обрезки и подстановки и применением некоторых функций обработки изображений.
«Водяные знаки» могут быть усилены при адаптировании их к конкретному содержанию блока. Модели человеческой зрительной системы, частота и пространственное маскирование делают возможным создание более надежных «водяных знаков». Однако для небольших относительно однородных блоков эта схема не применима, так как ошибкоустойчивость знаков в таких областях будет всегда ниже, чем у используемой техники.
Литература
1. S. Walton, «Information Authentication for a Slippery New Age», Ur. Dobbs Journal, vol. 20, no. 4, pp. 18-26, Apr 1995.
2. R. G. van Schyndel, A. Z. Tirkel, and C. F. Osbome, «A Digital Watermark», Proc. of the IEEE Int. Conf. on Image Processing, vol. 2, pp. 86-90, Austin, Texas, Nov 1994.
3. R. В. Wolfgang and E. J. Delp, «A Watermark for Digital Images», Proc. IEEE Int. Conf. on Image Processing, vol. 3, pp. 219-222,1996.
4. В. Zhu, М. D. Swanson, and A. Tewfik, «Transparent Robust Authentication and Distortion Measurement Technique for Images», preprint, 1997.
5. ]. ]. К. 0 Ruanaidh and Т. Pun, «Rotation, Scale and Translation Invariant Digital Image Watermarking», Proc. of the ICIP, vol. I, pp. 536-539, Santa Barbara, California, Oct 1997.
6. В. Girod, «The Information Theoretical Significance of Spatial and Temporal Masking in Video Signals», Proc. of the SPIE Human Vision, Visual Processing, and Digital Display, vol. 1077, pp. 178-187,1989.
7. J. Fridrich, «Methods for Detecting Changes in Digital Images», Proc. of The 6th IEEE International Workshop on Intelligent Signal Processing and Communication Systems (IPACS'98), Melbourne, Australia, 4-6 November 1998.
8. М. Swanson, В. Zhu, and A. H. Tewfik, «Data Hiding for Video-in-video», Proc. ICIP '97, vol. II, pp. 676-679, 1997.
9. A. Herrigel, ). 0 Ruanaidh, H. Petersen, S. Pereira, T. Pun, «Secure Copyright Protection Techniques for Digital Images», Proc. 2nd Int. Information Hiding Workshop, Portland, Oregon, Apr 1998.
10. J. Fridrich, «Combining Eow-frequency and Spread Spectrum Watermarking», Proc. SPIE Int. Symposium on Optical Science, Engineering, and Instrumentation, San Diego, July 19-24, 1998.
Статья опубликована на сайте: 27.07.2000