RU2301447C2

RU2301447C2 - Method for finding images in jpeg format which contain a digital watermark

Info

Publication number: RU2301447C2
Application number: RU2005116628/09A
Authority: RU
Inventors: Владимир Алексеевич Баранов (RU); Владимир Алексеевич Баранов; Олег В чеславович Гатилов (RU); Олег Вячеславович Гатилов; Алексей Валентинович Скурнович (RU); Алексей Валентинович Скурнович; Сергей Васильевич Харченко (RU); Сергей Васильевич Харченко; Иван Владимирович Иванов (RU); Иван Владимирович Иванов; Дмитрий Александрович Кирюхин (RU); Дмитрий Александрович Кирюхин
Priority date: 2005-05-31
Filing date: 2005-05-31
Publication date: 2007-06-20
Also published as: RU2005116628A

Abstract

FIELD: steganography, in particular, methods for detecting additional information in graphic images in JPEG format, having various degrees of significance in form of a digital watermark.

SUBSTANCE: invention allows detection of digital watermark size and coordinates of modified discontinuous cosine transformation coefficients of JPEG format file with required error probability. Along perimeter of each image block, correlation coefficient relative to adjacent blocks are determined for all image blocks, analyzed block after forced modification - incrementing by one in accordance to complete enumeration method of one or several absolute values of discontinuous cosine transformation coefficients (not equal to 0 and 1) - and reverse discontinuous cosine transformation is restored in spatial area. Along perimeter of restored block, values of coefficients of correlation with adjacent blocks are calculated. Minimum of distance is determined - minimum of average square deviation between values of correlation coefficients of restored image block, restored fragment from a corresponding set of discontinuous cosine transformation coefficients is the most correlated with adjacent fragments, and its restored discontinuous cosine transformation coefficients characterize the digital watermark.

EFFECT: increased efficiency.

3 dwg

Description

Изобретение относится к области стеганографии, а именно к способам обнаружения элементов дополнительной информации в частотной области графических изображений формата JPEG, представленной в виде цифрового водяного знака (ЦВЗ).The invention relates to the field of steganography, and in particular to methods of detecting additional information elements in the frequency domain of graphic images in JPEG format, presented as a digital watermark (CEH).

Целью изобретения является анализ изображений формата JPEG для определения числа и координат модифицированных процедурой встраивания ЦВЗ, встроенного в коэффициенты дискретного косинусного преобразования (ДКП) двух или более блоков пикселей изображения с требуемой вероятностью ошибки.The aim of the invention is the analysis of JPEG images to determine the number and coordinates modified by the embedment of the CEH built into the discrete cosine transform (DCT) coefficients of two or more blocks of image pixels with the required error probability.

Поставленная цель достигается за счет определения степени коррелированности анализируемого блока пикселей изображения с соседними четырьмя блоками по его периметру, как поясняется на фиг.1. Для этого введены этап формирования массива анализируемых блоков 8×8 пикселей, этап формирования массива значений коэффициентов корреляции между блоками пикселей, этап выбора анализируемого блока пикселей, этап выбора коэффициентов ДКП анализируемого блока пикселей для принудительной модификации, этап принудительной модификации коэффициента ДКП анализируемого блока пикселей, этап вычисления обратного ДКП, этап расчета значений коэффициентов корреляции между анализируемым и соседними блоками пикселей и сравнения с исходными значениями, этап определения среднеквадратического отклонения (СКО) для значений коэффициентов корреляции, полученных после принудительной модификации коэффициентов ДКП анализируемого блока пикселей, этап сравнения величины расстояния - СКО с предыдущим значением и сохранением минимального значения, этап проверки числа принудительных модификаций коэффициентов ДКП в анализируемом блоке пикселей, этап проверки числа анализируемых блоков пикселей, этап формирования массива выявленных модификаций коэффициентов ДКП изображения по критерию минимума расстояния между коэффициентами корреляции с соседними блоками.This goal is achieved by determining the degree of correlation of the analyzed block of image pixels with the neighboring four blocks along its perimeter, as explained in figure 1. For this, the stage of forming an array of analyzed blocks of 8 × 8 pixels, the stage of forming an array of values of correlation coefficients between blocks of pixels, the stage of selecting an analyzed block of pixels, the stage of selecting DCT coefficients of the analyzed pixel block for forced modification, the stage of forcing modifying the DCT coefficient of the analyzed pixel block, the stage calculating the inverse DCT, the stage of calculating the values of the correlation coefficients between the analyzed and neighboring blocks of pixels and comparing with the original values ii, the step of determining the standard deviation (RMS) for the values of the correlation coefficients obtained after the forced modification of the DCT coefficients of the analyzed block of pixels, the step of comparing the distance - the standard deviation with the previous value and maintaining the minimum value, the step of checking the number of forced modifications of the DCT coefficients in the analyzed block of pixels, the stage of checking the number of analyzed blocks of pixels, the stage of forming an array of identified modifications of the DCT coefficients of the image according to the criterion minimum distance between correlation coefficients with neighboring blocks.

Введение перечисленных этапов и связей между ними позволяет анализировать характер модификаций изображения JPEG в частотной области, а именно число и координаты модифицированных коэффициентов ДКП при встраивании ЦВЗ. Решение о модификациях, осуществленных процедурой встраивания ЦВЗ, принимается на основе определения минимального расстояния - минимума СКО от максимально возможного значения степени коррелированности между векторами пикселей анализируемого блока после принудительной модификации методом полного перебора одного или нескольких его коэффициентов ДКП.The introduction of the above steps and the relationships between them allows us to analyze the nature of the JPEG image modifications in the frequency domain, namely the number and coordinates of the modified DCT coefficients when embedding the CEH. The decision on the modifications made by the CEH embedding procedure is made on the basis of determining the minimum distance - the minimum standard deviation from the maximum possible value of the degree of correlation between the pixel vectors of the analyzed block after forced modification by the method of exhaustive search of one or several of its DCT coefficients.

Заявленный способ поясняется чертежами, на которых на фиг.2 представлена общая схема реализации способа; на фиг.3 - график зависимости вероятности ошибки определения числа и координат модифицированных коэффициентов ДКП от размера встроенного ЦВЗ.The claimed method is illustrated by drawings, in which figure 2 presents a General diagram of the implementation of the method; figure 3 is a graph of the probability of error in determining the number and coordinates of the modified DCT coefficients on the size of the integrated CEH.

Заявленный способ, схема которого представлена на фиг.2, состоит из этапа формирования массива анализируемых блоков 8×8 пикселей и этапа формирования массива значений коэффициентов корреляции между блоками пикселей, соединенных с этапом выбора анализируемого блока пикселей, который соединен с этапом выбора коэффициентов ДКП анализируемого блока пикселей для принудительной модификации, соединенного с этапом принудительной модификации коэффициента ДКП анализируемого блока пикселей, соединенного с этапом вычисления обратного ДКП, который соединен с этапом расчета значений коэффициентов корреляции между анализируемым и соседними блоками пикселей и сравнения с исходными значениями, соединенного с этапом определения СКО для значений коэффициентов корреляции, полученных после принудительной модификации коэффициентов ДКП анализируемого блока пикселей, который соединен с этапом сравнения величины расстояния - СКО с предыдущим значением и сохранением минимального значения, соединенного с этапом проверки числа принудительных модификаций коэффициентов ДКП в анализируемом блоке пикселей и соединенного обратной связью с этапом принудительной модификации коэффициента ДКП анализируемого блока пикселей, который соединен с этапом проверки числа анализируемых блоков пикселей и соединенного обратной связью с этапом выбора анализируемого блока пикселей, соединенного с этапом формирования массива выявленных модификаций коэффициентов ДКП изображения по критерию минимума расстояния между коэффициентами корреляции с соседними блоками.The claimed method, the scheme of which is shown in figure 2, consists of a stage of forming an array of analyzed blocks of 8 × 8 pixels and a stage of forming an array of values of correlation coefficients between blocks of pixels connected to a step of selecting an analyzed block of pixels, which is connected to a step of selecting coefficients of DCT of the analyzed block pixels for forced modification connected to the step of forced modification of the DCT coefficient of the analyzed block of pixels connected to the step of calculating the inverse DCT, cat The first one is connected with the step of calculating the values of the correlation coefficients between the analyzed and neighboring blocks of pixels and comparing with the initial values, connected with the step of determining the standard deviation for the values of the correlation coefficients obtained after the forced modification of the DCT coefficients of the analyzed block of pixels, which is connected with the step of comparing the distance - the standard deviation with previous value and maintaining the minimum value connected with the step of checking the number of forced modifications of DCT coefficients in the analyzer a block of pixels and connected by feedback to the stage of forced modification of the DCT coefficient of the analyzed block of pixels, which is connected to the stage of checking the number of analyzed blocks of pixels and connected by feedback to the step of selecting the analyzed block of pixels connected to the stage of forming an array of identified modifications of the coefficients of the DCT of the image according to the criterion of minimum the distance between the correlation coefficients with neighboring blocks.

Способ осуществляют следующим образом. Сначала формируют массив анализируемых блоков изображения, в который заносятся только те блоки пикселей, которые содержат в своем спектре 2 и более коэффициента ДКП, не равных 0 и 1, и массив значений коэффициентов корреляции между блоками изображения, вычисляемых согласно [1]The method is as follows. First, an array of analyzed image blocks is formed, in which only those blocks of pixels that contain 2 or more DCT coefficients not equal to 0 and 1, and an array of correlation coefficients between image blocks calculated according to [1] are entered

где V1 и V2 - граничные вектора пикселей (Фиг.1). Для каждого блока по его периметру определяют по четыре значения коэффициента корреляции.where V1 and V2 are the boundary pixel vectors (Figure 1). For each block, four values of the correlation coefficient are determined by its perimeter.

Далее анализируемый блок, после принудительной модификации, заключающейся в увеличении на единицу абсолютной величины одного из коэффициентов ДКП переменного тока (не равного 0 и 1), количество которых определяют согласноNext, the analyzed block, after forced modification, which consists in increasing by one the absolute value of one of the AC DCT coefficients (not equal to 0 and 1), the amount of which is determined according to

где m_AC=0,1 - число коэффициентов ДКП переменного тока в блоке, равных 0 и 1, восстанавливают путем обратного ДКП в пространственной области. Для восстановленного блока изображения по его периметру считают величины коэффициентов корреляции с соседними блоками. Количество итераций принудительных модификаций коэффициентов ДКП и восстановления блока зависит от числа коэффициентов в нем и определяется согласноwhere m _{AC = 0.1} is the number of AC DCT coefficients in the block, equal to 0 and 1, is restored by reverse DCT in the spatial domain. For the restored image block along its perimeter, the values of the correlation coefficients with neighboring blocks are considered. The number of iterations of forced modifications of DCT coefficients and block recovery depends on the number of coefficients in it and is determined according to

где М - число одновременных принудительных модификаций коэффициентов.where M is the number of simultaneous forced modifications of the coefficients.

Затем находят минимальное значение расстояния - минимум СКО между величинами коэффициентов корреляции восстановленного блока изображения и максимальным значением коэффициента корреляции с соседними блоками, непригодными для встраивания ЦВЗ и не включенных в массив анализируемых блоков. Минимум СКО определяется по формуле [2]:Then find the minimum value of the distance — the minimum of the standard deviation between the correlation coefficients of the reconstructed image block and the maximum value of the correlation coefficient with neighboring blocks unsuitable for embedding the CEH and not included in the array of analyzed blocks. The minimum standard deviation is determined by the formula [2]:

где j - номер итерации для восстанавливаемого блока (k,l) с набором исходных и принудительно модифицированных коэффициентов ДКП, приводящих к большей коррелированности с соседними блоками.where j is the iteration number for the reconstructed block (k, l) with a set of initial and forcibly modified DCT coefficients, leading to greater correlation with neighboring blocks.

Полученный набор принудительно модифицированных коэффициентов характеризует число бит ЦВЗ, приведших к искажениям коэффициентов ДКП исходного изображения, а их местоположение в каждом анализируемом блоке совпадает с соответствующими коэффициентами ДКП, младшие биты которых представляют собой ЦВЗ.The obtained set of forcibly modified coefficients characterizes the number of CEH bits that led to distortions of the DCT coefficients of the original image, and their location in each analyzed block coincides with the corresponding DCT coefficients, the least significant bits of which are the CEH.

Выходные данные заносятся в массив выявленных модификаций коэффициентов ДКП изображения, соответствующий модификациям при встраивании ЦВЗ.The output is entered into the array of identified modifications of the DCT coefficients of the image, corresponding to the modifications when embedding the CEH.

Таким образом, применение перебора определенных комбинаций коэффициентов ДКП позволяет с определенной вероятностью выявить такую их последовательность, на основе которой восстановленный фрагмент изображения будет наиболее коррелированным по отношению к соседним, что позволяет судить о наличии ЦВЗ в конкретном наборе коэффициентов принятого файла.Thus, the use of enumeration of certain combinations of DCT coefficients makes it possible to identify their sequence based on which the reconstructed fragment of the image will be most correlated with respect to the neighboring ones, which makes it possible to judge the presence of the CEH in a specific set of coefficients of the received file.

Благодаря этому получен технический результат, а именно возникла возможность определения размера ЦВЗ и местоположения модифицированных коэффициентов ДКП с вероятностями ошибки, приведенными на графике фиг.3. Из графика видно, что при относительном размере ЦВЗ (отношении числа бит ЦВЗ, приведших к модификациям коэффициентов ДКП, к числу всех коэффициентов ДКП) от 15 до 70% вероятность ошибки не превышает 10^-1.Thanks to this, a technical result was obtained, namely, it became possible to determine the size of the CEH and the location of the modified DCT coefficients with the error probabilities shown in the graph of Fig. 3. The graph shows that with a relative size of the CEH (the ratio of the number of bits of the CEH that led to modifications of the DCT coefficients to the number of all DCT coefficients) from 15 to 70%, the error probability does not exceed 10 ^-1 .

Источники информацииInformation sources

1. Гмурман В.Е. Теория вероятностей и математическая статистика. Изд. 4-е, доп. Учеб. Пособие для вузов. М.: Высшая школа, 1972.1. Gmurman V.E. Theory of Probability and Mathematical Statistics. Ed. 4th, add. Textbook Manual for universities. M .: Higher School, 1972.

2. Левин Б.Р. Теоретические основы статистической радиотехники. В трех книгах. Книга третья. - М.: «Советское радио», 1975.2. Levin B.R. Theoretical foundations of statistical radio engineering. In three books. The third book. - M .: "Soviet Radio", 1975.

Claims

A method for searching JPEG images containing a digital watermark (CEH) embedded in the discrete cosine transform (DCT) coefficients of two or more blocks of image pixels to determine the number and coordinates modified by the embedding of the CEH DCT coefficients with the required error probability, which consists in the fact that they form an array of the analyzed blocks of pixels, form an array of values of the correlation coefficients between the blocks of pixels, for each analyzed block of pixels choose the coefficients D P of the analyzed block of pixels for forced modification, carry out a forced modification of the DCT coefficient, for each modification of the DCT coefficients calculate the inverse DCT, calculate the values of the correlation coefficients between the analyzed and neighboring blocks of pixels and compare them with the original values, determine the distance - standard deviation (RMS) between the values the correlation coefficients obtained after the forced modification of the DCT coefficients form an array of identified coefficient modifications of DCT images by the criterion of the minimum distance between the correlation coefficients with neighboring blocks.