способ передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображений

Формула изобретения

Способ передачи дополнительной информации при кодировании изображений, содержащий стадии а) перевода в цифровую форму исходного изображения, b) его сжатия с помощью необратимого способа сжатия, с) вставки цифровой полезной информации, d) декомпрессии сжатого изображения, е) выделения цифровой полезной информации, отличающийся тем, что после сжатия исходного изображения с помощью совместного использования векторного квантования и фрактального кодирования, вставляют m разрядов дополнительной информации вместо младших разрядов в каждый вектор индекса домена или блока из кодовой книги, состоящий из n разрядов, к оставшимся k=n-m исходным разрядам применяют процедуру пробной инверсии, в которой используют метод Гаусса-Зейделя, после чего их вместе с дополнительной информацией передают по каналу связи.

Описание изобретения к патенту

Изобретение относится к области электросвязи, а именно к области, связанной с сокращением избыточности передаваемой информации. Основанием для этого по существу является то, что с помощью современных технологий кодирования и уплотнения данных можно значительно сократить частотный диапазон, необходимый для передачи изображений. Техническим результатом изобретения является разработка способа передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображений, обеспечивающего передачу дополнительной информации без увеличения объема передаваемых данных.

В цифровой видеотехнике для повышения передаваемого количества информации уже предлагалось заменять в цифровом сигнале данные развертки, содержащиеся в интервале бланкирования дополнительной информации, например цифровыми звуковыми сигналами, и за счет этого обеспечивать передачу дополнительной информации (Ulrich Schmidt, Цифровая видеотехника, Издательство Franzis Verlag, Фельдкирхен, 1996) [1].

Наиболее близким по своей технической сущности к заявленному способу передачи дополнительной информации при кодировании изображений является способ, описанный в патенте №2212769, МПК⁷ Н04N 7/08 [2]. Способ-прототип исключает не требующуюся часть информации изображения, т.е. физиологически едва или вовсе не воспринимаемую тонкую структуру изображения, за счет необратимого уплотнения и последующей декомпрессии сигнала изображения, т.е. осуществляет сокращение данных и в полученное таким образом свободное пространство вставляет полезную и управляющую информацию.

Однако общая полоса частот, занимаемая при передаче основного изображения и дополнительной информации, остается прежней, как и до необратимого уплотнения исходного изображения.

Целью данного изобретения является разработка способа, который позволяет при кодировании любого типа изображений передавать дополнительную полезную информацию при сохранении скорости передачи и длине формата кадра. Поставленная цель достигается тем, что при сжатии исходного изображения с помощью совместного использования векторного квантования и фрактального кодирования в младшие разряды индексов домена или блоков из кодовой книги вводят дополнительную информацию, благодаря чему сокращается список используемых доменов и блоков из кодовой книги, что приводит к существенному уменьшению общего времени кодирования при незначительном ухудшении качества восстановленного изображения. К оставшимся разрядам применяют процедуру пробной инверсии.

Рассмотрим алгоритм передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображений (фиг.1).

Предварительно исходное изображение разбивают на неперекрывающиеся ранговые блоки, а затем покрывают последовательностью доменных блоков, возможно перекрывающихся. Домены могут быть разных размеров. Также в кодере и декодере предварительно формируют идентичные кодовые книги. После этого в младшие разряды индексов домена или блоков из кодовой книги встраивают дополнительную информацию.

Далее к исходному изображению применяется базовый алгоритм фрактального кодирования изображений [3]. Главный вычислительный шаг во фрактальном кодировании - это сравнение доменной и ранговой областей. Для каждого рангового блока находят домен и соответствующее преобразование, которое наилучшим образом покрывает ранговый блок. Обычно это аффинное преобразование

где _i - константа, которая расширяет или сужает диапазон значений функции f (управляет контрастностью изображения);

_i - константа, которая увеличивает или уменьшает значения градаций серого (управляет яркостью изображения);

w_i - аффинное преобразование;

- пространственная составляющая преобразования w _i;

f(x,y) - значение пиксела изображения с координатами (х,у).

Аффинное преобразование состоит из трех этапов. Во-первых, к выбранному домену применяется один из восьми базовых поворотов/отражений (четыре поворота на 90 градусов и зеркальное отражение в каждой ориентации). Во-вторых, вращаемая доменная область сжимается, чтобы соответствовать размеру ранговой области. И, наконец, методом наименьших квадратов вычисляются параметры контрастности и яркости соответствующие оптимальным значениям, при которых минимизируется выражение

где n и m - число строк и столбцов в обрабатываемом ранговом блоке;

R_ij и D _ij - значения пикселов ранговой и доменной областей.

Продолжают этот процесс до тех пор, пока не добьются приемлемого соответствия или размер ранговых блоков не достигнет некоторого заранее определенного предела.

Кроме того, поиск необходимого домена осуществляется из сформированной ранее кодовой книги с учетом встроенной дополнительной информации в младшие разряды фрагментов кодовой книги. Формирование кодовой книги осуществляется итерационным кластерным алгоритмом, известным также как алгоритмом k-средних, описанным в [4]. В соответствии с данным алгоритмом выбирают некоторую последовательность изображений, принадлежащих различным классам. Далее эту последовательность преобразуют в последовательность входных векторов или обучающую последовательность, по которым формируется кодовая книга. При этом входные вектора должны обладать большим динамическим диапазоном, так как кодовая книга должна содержать блоки, отображающие резкие грани между фрагментами изображения, поскольку именно в таких случаях могут возникнуть проблемы с поиском подходящего домена. Такая ситуация обычно возникает из-за ограничений на динамический диапазон искомого домена, который, как правило, должен быть больше динамического диапазона ранговой области. На участках с резкими границами динамический диапазон очень велик, и часто оказывается, что он достигает своего максимального значения. В этом случае не существует домена со строго большим динамическим диапазоном, и ранговая область замещается наиболее похожим блоком из кодовой книги.

Если ранговый блок лучше отображается доменным блоком, то декодеру передается индекс соответствующего домена, при приеме которого в декодере осуществляется фрактальное декодирование исходного блока. При выборе для рангового блока фрагмента из кодовой книги декодеру передается индекс, по которому из кодовой книги в декодере выбирается необходимый фрагмент, которым после фрактального декодирования заполняется восстановленное изображение.

В предлагаемом способе в каждый вектор индекса доменов или блока из кодовой книги, состоящие из n разрядов, вводятся m разрядов дополнительной информации вместо младших разрядов данного вектора (фиг.2). В результате такого введения список доменов и блоков из кодовой книги для обработки конкретного рангового блока заметно уменьшается, что приводит к уменьшению как времени поиска подходящих доменов и фрагментов кодовой книги, так и общего времени кодирования в целом. К оставшимся k=n-m разрядам применяется процедура пробной инверсии. В данной процедуре с целью снижения вычислительной сложности по сравнению со способом полного перебора предложено использовать известный метод Гаусса-Зейделя. Процедура пробной инверсии осуществляет оптимизацию элементов индексов домена путем пробной инверсии ее каждого элемента. Процесс поиска оптимальных элементов вектора в заявленном способе предлагается осуществить в виде следующей последовательности действий:

1. Положить t=1;

2. Сформировать вектор индекса домена или блока из кодовой книги с учетом ввода дополнительной информации

3. Положить r=1;

4. Выбрать соответствующую ориентацию домена или блока из кодовой книги, рассчитать параметры преобразования, такие как контрастность и яркость и определить выражение (2) для вектора ;

5. Выполнить инверсию r-го элемента вектора

где x_r {0,1},

6. Сформировать вектор:

1. Выбрать соответствующую ориентацию домена или блока из кодовой книги, настроить параметры преобразования, такие как контрастность и яркость, для минимизации выражения (2) при инверсии r-го элемента вектора

8. Вычислить ;

9. Выполнить: если u>0, то значению е ² присвоить значение и значению x_r, присвоить ; если u<0, то значения e² и х _r оставить без изменения;

10. Выполнить: если r<k, то увеличить r на единицу и перейти к пункту 4; если r=k, то положить t=t+1 и перейти к пункту 2 для оптимизации следующих индексов домена или блоков из кодовой книги.

После встраивания дополнительной информации и оптимизации индексов доменов и блоков из кодовой книги, эти данные вместе с информацией об индексах их ориентации, коэффициентах яркости и контрастности передаются по каналу связи. В декодере происходит выделение дополнительной информации и восстановление исходного изображения. Декодирование изображения осуществляется путем итеративного применения аффинного преобразования к произвольному начальному изображению. В соответствии с теоремой о сжимающих отображениях итерации будут сходиться независимо от выбора начального изображения. Сжимающее отображение определяется как отдельное преобразование для каждого рангового блока. Каждый ранговый блок имеет связанные с ним преобразование и домен. Содержимое этого рангового блока вычисляется применением преобразования к доменному блоку. Одна итерация завершается, когда обработаются все ранговые блоки.

В случае кодирования ранга блоком из кодовой книги данный фрагмент кодовой книги с учетом индекса его ориентации, коэффициентов яркости и контрастности заполняет соответствующую область восстановленного изображения.

Заявленный способ поясняется чертежами:

- Фиг.1 представляет алгоритм кодирования изображения при совместном использовании векторного квантования и фрактального метода сжатия с учетом встроенной дополнительной информации;

- Фиг.2 - процедура записи дополнительной информации;

- Фиг.3 - схема передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображения.

На фиг.1 представлен алгоритм кодирования изображения при совместном использовании векторного квантования и фрактального метода сжатия с учетом встроенной дополнительной информации. Исходное изображение разбивается на неперекрывающиеся ранговые и доменные блоки. После чего в доменные блоки встраивается дополнительная информация. Как видно, после вставки дополнительной информации к оставшимся исходным разрядам применяют процедуру пробной инверсии, в которой используют известный метод Гаусса-Зейделя для решения оптимизационных задач. После этого для каждого рангового блока находят домен и соответствующее преобразование, которое наилучшим образом покрывает ранговый блок. Обычно это - аффинное преобразование. В качестве доменов могут выступать доменные области исходного изображения или блоки кодовой книги. Кодирование завершается при покрытии каждого рангового блока доменной областью с заданной погрешностью.

На фиг.2 показана процедура записи дополнительной информации. В предлагаемом способе в каждый вектор индекса доменов или блоков из кодовой книги, состоящий из n разрядов, вместо младших разрядов вводятся m разрядов дополнительной информации. Поскольку эти данные не добавляются дополнительно к первоначальному сигналу, а заменяют часть первоначального сигнала, то ширина полосы сигнала не увеличивается за счет добавления этой информации.

На фиг.3 представлена схема передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображения. Предварительно в кодере и декодере формируют идентичные кодовые книги. После этого в младшие разряды индексов домена или блоков из кодовой книги встраивают дополнительную информацию. Далее осуществляется фрактальное кодирование ранговых блоков с учетом встроенной дополнительной информации, а также поиск наиболее подходящего блока из сформированной ранее кодовой книги. Если ранговый блок лучше отображается доменным блоком, то декодеру передается индекс соответствующего домена, при приеме которого в декодере осуществляется фрактальное декодирование исходного блока. При выборе для рангового блока фрагмента из кодовой книги декодеру передается индекс, по которому из кодовой книги в декодере выбирается необходимый фрагмент, которым после фрактального декодирования заполняется восстановленное изображение.

В таблице 1 приведены результаты имитационного моделирования вставки дополнительной информации в тестовое изображение "Лена" размером 256×256 пикселов. Размер рангового блока составлял 8×8 пикселов, при этом их общее количество в изображении будет 1024. Пиковое соотношение сигнал/шум (PSNR) до вставки дополнительной информации составляло 29 дБ.

Таблица 1
	Число бит, встраиваемых в индексы доменов и блоков из кодовой книги
	1 бит	2 бита	3 бита	4 бита	5 бит	6 бит	7 бит	8 бит	9 бит
PSNR на изображении "Лена", [ДБ]	28.9	28.4	27.8	27.3	26.5	25.6	24.5	23.4	23
Максимально допустимый объем доп. информации, [бит]	1024	2048	3072	4096	5120	6144	7168	8192	9216

Данный способ передачи дополнительной информации при совместном использовании векторного квантования и фрактального кодирования изображений может быть реализован на современных процессорах обработки сигналов. Указанный способ может найти свое применение при передаче дополнительной информации по низкоскоростным каналам связи. В качестве дополнительной информации может выступать скрытая информация, другое изображение или иное полезное сообщение.

Литература

1. Ulrich Schmidt, Цифровая видеотехника. Издательство Franzis Verlag, Фельдкирхен, 1996.

2. Патент №2212769, МПК⁷ Н 04 N 7/08, бюл. №26 от 20.09.2003 г.

3. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособие. - М.: Издательство Триумф, 2003 - 320 с.

4. Спутниковое телевидение. Новые методы передачи. / Н.Г.Харатишвили, Э.И.Кумыш, В.Ю.Епанечников, О.Г.Зумбуридзе. /Под ред. Н.Г.Харатишвили. - М.: Радио и связь, 1993.