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

Авторы патента:

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

G06T9 - Кодирование изображения, например из побитового к непобитовому изображению (сжатие вообще H03M; сжатие для связи изображения H04N)

Владельцы патента RU 2327301:

Государственное образовательное учреждение высшего профессионального образования Академия Федеральной службы охраны Российской Федерации (Академия ФСО России) (RU)

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

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

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

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

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

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

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

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

1 класс	А₁≥A₂≥А₃≥A₄
2 класс	А₁≥А₂≥А₄≥A₃
3 класс	А₁≥А₄≥А₂≥A₃

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

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

Далее к исходному изображению применяется алгоритм фрактального кодирования изображений [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 с.

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

Изобретение относится к способу передачи сигналов в сети цифрового телевидения. .

Управление импортом контента // 2324301

Изобретение относится к системам управления импортом контента в домен, содержащий несколько устройств. .

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

Изобретение относится к области электросвязи, а именно к области, связанной с сокращением избыточности передаваемой информации. .

Система и способ идентификации и вставки рекламы в вещательные программы // 2299523

Изобретение относится к системам трансляции программ вещания, и, в частности, к системам идентификации и вставки рекламы в вещательные программы. .

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

Изобретение относится к области электросвязи, а именно к области связи с сокращением избыточности передаваемой информации. .

Способ и устройство для передачи команды // 2285352

Изобретение относится к способу и системам передачи команды в управляемое устройство. .

Система связи, передатчик, приемник и способ применения дескриптора сохраняемых данных // 2280960

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

Интерактивное видеооборудование и способ наложения титров на изображение с помощью этого оборудования // 2278479

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

Способ и устройство для передачи данных // 2241315

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

Способ и устройство передачи дополнительных данных с множеством уровней // 2225682

Изобретение относится к способу и устройству для передачи дополнительных данных, связанных с аудио/видеосигналом с множеством уровней. .

Способ маскирования ошибок в видеопоследовательностях // 2321967

Изобретение относится к кодированию видеоданных и, в частности, к маскированию искажений, вводимых ошибками. .

Способ повышения скорости кодирования при совместном использовании векторного квантования и фрактального кодирования изображений // 2321184

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

Система и способ последовательного преобразования и кодирования цифровых данных // 2321063

Изобретение относится к обработке цифровых изображений, а именно к кодированию и декодированию изображений. .

Обработка изображений // 2317587

Изобретение относится к системам обработки изображений, в частности к способам и системам кодирования и декодирования изображений. .

Способ кодирования и декодирования цифровых данных, переданных методом приоризированной передачи пикселей или хранящихся в памяти // 2316137

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

Адаптивный способ и система для отображения значений параметров в индексы кодовых слов // 2313174

Изобретение относится к системе кодирования и декодирования видеосигналов. .

Способ кодирования и декодирования данных трехмерных объектов и устройство для его осуществления // 2267161

Изобретение относится к кодированию и декодированию данных трехмерных объектов, которые состоят из данных точечной текстуры, данных вокселей или данных дерева октетов.

Способ генерирования структуры узлов, предназначенных для представления трехмерных объектов с использованием изображений с глубиной // 2237284

Изобретение относится к представлению трехмерных объектов на основе изображений с глубиной. .

Устройство и способ представления трехмерного объекта на основе изображений с глубиной // 2237283

Изобретение относится к представлению трехмерных объектов на основе изображений с глубиной. .

Способ представления информации визуализации на основании изображения в 3d сцене // 2227323

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

Определение применимости кодированного файла для приложения // 2332717

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