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

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

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

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

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

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

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

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

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

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

Предварительно исходное изображение разбивают на неперекрывающиеся ранговые блоки и их классифицируют. В данном изобретении используется классификация, предложенная Фишером в [3], согласно которой каждый ранговый блок относится к одному из трех классов (фиг.2):

1 класс	А 1 A2 А3 A4
2 класс	А1 А2 А4 A3
3 класс	А1 А4 А2 A3

где А ₁, А₂, А₃, А₄ - сумма значений пикселов классифицируемого доменного блока в верхнем левом, верхнем правом, нижнем левом и нижнем правом квадрантах соответственно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.2 - Схема разбиения на классы доменов и блоков из кодовой книги.

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

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

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

На Фиг.2 представлена схема разбиения на классы доменов и блоков из кодовой книги. Каждый домен или блок из кодовой книги разбивается на четыре квадранта и в каждом квадранте вычисляется сумма значений пикселов.

где k - число строк (столбцов) в квадранте;

r_j - значение j-го пиксела квадранта.

Уровнями яркости каждого квадранта показаны соответствующие классы разбиения.

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

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

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

Таблица 1
	Число бит, встраиваемых в индексы доменов и блоков из кодовой книги
	1 бит	2 бита	3 бита	4 бита	5 бит	6 бит	7 бит
PSNR на изображении "Лена", [дБ]	28.0	27.1	26.2	25.6	25.1	24.5	23.5
Максимально допустимый объем доп. информации, [бит]	1024	2048	3072	4096	5120	6144	7168

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

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

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

3. Y. Fisher, Fractal image compression with quadtrees. Fractal Image Compression - Theory and Application, Springer-Verlag, New York, 1994.

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