СПОСОБ ВСТРАИВАНИЯ ИНФОРМАЦИИ В ГРАФИЧЕСКИЙ ФАЙЛ, СЖАТЫЙ ФРАКТАЛЬНЫМ МЕТОДОМ
METHOD OF EMBEDDING INFORMATION IN GRAPHIC FILE COMPRESSED BY FRACTAL CODING

Изобретение относится к области стеганографии, а именно к способам встраивания информации в графический файл, и может быть использовано для организации скрытого хранения и передачи данных по открытым каналам связи.
Известен «Способ встраивания сообщения в цифровое изображение» (патент RU 2407216 С1, опубликован: 20.12.2010 г.), в котором встраивание осуществляют за счет замены наименее значащего бита в байтах исходного цифрового изображения, при этом наименее значащему биту в байтах исходного цифрового изображения присваивают флаговое значение «единица» при совпадении части битов байта сигнала цифрового изображения и битов сигнала сообщения, либо флаговое значение «ноль» при несовпадении.
Недостатком данного способа является невозможность его применения для графического файла, сжатого фрактальным методом.
Известен «Способ передачи дополнительной информации при фрактальном кодировании изображения» (патент RU2292662C2, МПК H04N 7/08, опубликовано: 27.01.2011), в котором встраивание производят в младшие разряды индексов доменов.
Недостатком данного способа является искажение исходного изображения в результате переориентации доменов, связанной с необратимыми преобразованиями координат доменов.
Известен «Способ передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображений с учетом классификации доменов и блоков из кодовой книги» (патент RU 2327301 C2, МПК H04N 7/08, G06T 9/00, опубликовано: 27.12.2007), в котором в вектор индекса доменов или блока из кодовой книги, состоящий из n разрядов, вводят m разрядов дополнительной информации, вместо младших разрядов данного вектора.
Недостатком данного способа является искажение исходного изображения из-за переориентации доменов и их смещения относительно начального положения, вызванных преобразованием младших разрядов координат домена.
Наиболее близким по технической сущности и выполняемым функциям является «Способ встраивания информации в изображение, сжатое фрактальным методом, на основе сформированной библиотеки доменов» (патент RU 2530339 С1, МПК H04N 19/46, H04N 19/90, H04L 9/00, опубликовано: 10.10.2014), в котором библиотеку доменов делят на несколько равных частей для кодирования встраиваемой информации.
Недостатком данного способа является низкая эффективность встраивания информации, выраженная в малом соотношении объема встраиваемой информации к размеру исходного файла.
Задачей изобретения является создание способа встраивания информации в графический файл, сжатый фрактальным методом, обеспечивающего возможность скрытой передачи большего по сравнению с прототипом объема данных, используя контейнер, представленный в виде фрактально сжатого изображения.
Эта задача решается тем, что в способе встраивания информации в графический файл, сжатый фрактальным методом, включающем этапы формирования вектора параметров сжатия изображения, ввода скрываемой информации, выделения доменов и ранговых областей, соотнесения ранговых областей и доменов, формирования конечного архива, в процессе сжатия изображения биты скрываемой информации встраивают в исходный графический файл путем преобразования реальных координат домена в мнимые, реализуемого за счет введения корректирующих коэффициентов, значения которых вычисляют в зависимости от положения блока вводимой дополнительной информации в кодовой конструкции, созданной на основе мнимых изображений.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявляемый способ соответствует условию патентоспособности «изобретательский уровень».
«Промышленная применимость» изобретения обусловлена тем, что устройство, реализующее предложенный способ, может быть осуществлено с помощью современной элементной базы, с достижением указанного в изобретении назначения.
Заявленный способ встраивания информации в графический файл, сжатый фрактальным методом, поясняется чертежами, на которых показаны:
фиг. 1 - метод формирования мнимых доменов, отвечающих за значение встраиваемой информации, где i, j - индексы блоков в кодовой конструкции;
фиг. 2 - алгоритм, обобщенно отображающий предлагаемый способ встраивания информации;
фиг. 3 - функциональная схема предлагаемого способа встраивания информации.
В соответствии с функциональной схемой (фиг. 3), процесс формирования фрактально сжатого графического файла с параллельным встраиванием информации основан на пяти блоках. Первый блок реализует ввод параметров сжатия вместе со встраиваемой информацией. Второй и третий блоки предназначены для поиска в структуре исходного графического файла доменов и ранговых областей соответственно. Действия, выполняемые с первого по третий блок, описаны в (Y. Fisher, Fractal Image Compression - Theory and Application: New York: Springer, 1994). Этап соотнесения доменов и ранговых областей с параллельным встраиванием информации выполняет четвертый блок, что представлено в источнике (А.Е. Jacquin, “Fractal image coding based on a theory of iterated contractive image transformations” in Proceedings of SPIE Visual Communications and Image Processing ′90, vol. 1360, 1990). Конечный этап формирования файла-архива осуществляет пятый блок. Особенности функционирования описанных блоков указаны в (Y. Fisher, Fractal Image Compression - Theory and Application: New York: Springer, 1994).
Реализация предлагаемого способа состоит в преобразовании процесса сжатия графического файла, выраженном в параллельном включении процедуры встраивания информации в этап соотнесения доменов и ранговых областей изображения.
Первый блок в соответствии с общим алгоритмом фрактального сжатия предназначен для ввода параметров сжатия, среди которых минимальный размер домена, минимальный шаг домена, значение порога среднеквадратического отклонения (СКО), глубина квадродерева и встраиваемая информация, что рассмотрено в (Т. Laurencot, А.Е. Jacquin, Hybrid image block coders incorporating fractal coding and vector quantization, with a robust classification scheme, AT&T Tech. Memo., February 1992).
Введенные данные поступают на вход второго блока, на второй вход которого загружают исходное изображение, предназначенное для сжатия. На базе второго блока реализуют разбиение изображения на домены, минимальный размер которых указан в параметрах сжатия. Также выделяют группы домены большего размера, и для более эффективного расчета, каждые следующие группы доменов больше предыдущих в два раза. Максимально возможный размер домена выбирают в соответствии с размерами исходного изображения. После выделения доменов, осуществляют их классификацию на основе значений математических ожиданий интенсивности пикселей «колец» сегментов, что представлено в (патент RU 2541203 С2, МПК H04N 19/90, G06T 9/00, опубликовано: 10.02.2015).
Далее, загруженное изображение поступает на третий блок, который выделяет ранговые области в графическом файле. Ранговые области полностью заполняют все изображение, в отличии от доменов не пересекаются друг с другом и меньше доменов по ширине в два раза, что указано в (А.Е. Jacquin, “Fractal image coding based on a theory of iterated contractive image transformations” in Proceedings of SPIE Visual Communications and Image Processing ′90, vol. 1360, 1990).
После формирования библиотеки доменов и определения ранговых областей, данные с третьего блока поступают на вход четвертого блока, который осуществляет основной этап соотнесения ранговых областей и доменов с параллельным встраиванием информации. Данную процедуру реализуют путем подбора соответствующих рассматриваемой ранговой области доменов. Классификация позволяет уменьшить сложность выполняемой задачи в несколько раз, так как соотнесение проводят для сегментов, принадлежащих одному классу.
Схожесть доменов и рангов определяют по методу наименьших квадратов (МНК). Исследуемый домен подвергают аффинным преобразованиям для обеспечения максимального сходства с рангом, после чего по значению, полученному по МНК, принимают решение о продолжении поиска соответствия. Аффинные преобразования подразумевают под собой такие операции над сегментами изображения, как зеркальное отображение, поворот на углы в 90, 180, 270 градусов и масштабирование (Кроновер P.M. Фракталы и хаос в динамических системах. Основы теории. М., 2000. - 352 с.). В параметрах сжатия заранее указывают минимальный порог СКО, получаемый при расчете значения по МНК. В случае определения значения порога необходимо искать компромисс между длительностью компрессии графического файла и качеством его сжатия, так как данные параметры имеют взаимообратную зависимость. В случае если для ранговой области не будет найден подходящий домен, используют метод квадродерева, при котором ранговую область разбивают на четыре равные части и с ними проводят аналогичные действия по поиску соответствующих доменов, что показано в (Y. Fisher, Fractal Image Compression - Theory and Application: New York: Springer, 1994).
После выполнения этапа соотнесения ранговых областей и доменов, данные с четвертого блока поступают на пятый блок. Данный блок формирует архив, состоящий из заголовка, в котором указаны параметры сформированного сжатого файла, и поля данных, содержащего координаты соответствующих доменов, коэффициенты аффинных преобразований и значения яркости и контрастности.
В разработанном способе предлагается использование мнимых доменов, которые формируют на основе исходного изображения. В процессе соотнесения доменов и ранговых областей, соответствующему ранговой области домену присваивают координаты из мнимой области, в зависимости от положения в кодовой конструкции того блока информации, который необходимо встроить в графический файл. Кодовую конструкцию формируют на базе исходного изображения путем его дублирования по осям x и y, где каждое мнимое изображение (выделены пунктирной линией), а соответственно и домен мнимого изображения (заштрихованные области), отвечает за различные значения встраиваемой информации, представленные в двоичном виде (фиг. 1). Размер кодовой конструкции зависит от задаваемой при вводе параметров сжатия размерности блоков n, на которые делят встраиваемую информацию. В случае если длина блока четное число, то размерность кодовой конструкции s рассчитывают по формуле , иначе по формуле , где n≥2. Разбитую по блокам встраиваемую информацию на каждой итерации при поиске соответствия ранг - домен соотносят с составленной кодовой конструкцией, после чего рассчитывают значения мнимых координат домена, с учетом расположения этого блока в кодовой конструкции. Расчет значений мнимых координат происходит по формулам  и , где fx, fy - корректирующие коэффициенты, соответствующие порядковому номеру расположения мнимого изображения в кодовой конструкции по осям x и y соответственно; h, v - ширина и высота изображения, x, y - координаты реального домена, соответствующего конкретной ранговой области (фиг. 2).
Максимальный размер кодовой конструкции зависит от битовой размерности поля, выделенного под параметр координаты домена в сжатом файле. В используемом алгоритме сжатия графических файлов размер области координат, плавающий с крайним значением в 12 бит (от 0 до 4095 пикселей). В зависимости от исходного изображения существует возможность создания кодовой конструкции с размерностью около 10 на 10, то есть около 6 бит встраиваемой информации на одну ранговую область. Для повышения эффективности стеганографического алгоритма возможно расширение области координат, в зависимости от целей разработчика.
Обратная операция извлечения встроенной информации основана на получении частного от деления заданных координат на ширину и высоту графического файла соответственно. Полученные целые значения указывают на блок встроенной информации в кодовой конструкции и на соответствующие встроенные данные. Сам процесс декомпрессии основан на перерасчете мнимых координат доменов реальным путем взятия модулей от мнимых координат по ширине и высоте соответственно. Дальнейшая декомпрессия реализуется по стандартному алгоритму.
Эффективность функционирования предлагаемого способа по сравнению с прототипом состоит в увеличении объема встраивания дополнительной информации при отсутствии структурных изменений в формируемом файле.
Реализация предложенного способа встраивания информации подтвердила эффективность его применения. Наиболее популярные программные продукты, предназначенные для стеганографического анализа, не позволяют выявить факт встраивания информации при использовании данного способа, так как статистика распределения битов не изменяется. Потенциальный объем передаваемой информации в процентном соотношении составляет в зависимости от исходного файла 6% и более от общего объема файла-контейнера в отличии от прототипа, где аналогичное значение достигало 1%. Полученный процент высчитывается на основе отношения произведения количества ранговых областей в изображении с количеством бит, описываемых одним мнимым доменом к общему размеру файла. В ходе эксперимента использовалось изображение, размером 617 кБ, в котором было сформировано около 50000 ранговых областей, при 6 битах на домен. Соответственно, объем встроенной информации составляет 300000 бит (37500 байт), что составляет 37500/617000=0,06 (6%) от общего размера исходного файла.