СПОСОБ ПЕРЕДАЧИ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ПРИ СОВМЕСТНОМ ИСПОЛЬЗОВАНИИ ВЕКТОРНОГО КВАНТОВАНИЯ И ФРАКТАЛЬНОГО КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ С УЧЕТОМ КЛАССИФИКАЦИИ ДОМЕНОВ И БЛОКОВ ИЗ КОДОВОЙ КНИГИ Российский патент 2008 года по МПК H04N7/08 G06T9/00 

Описание патента на изобретение RU2327301C2

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

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

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

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

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

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

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

1 классА1≥A2≥А3≥A42 классА1≥А2≥А4≥A33 классА1≥А4≥А2≥A3

где А1, А2, А3, А4 - сумма значений пикселов классифицируемого доменного блока в верхнем левом, верхнем правом, нижнем левом и нижнем правом квадрантах соответственно.

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

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

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

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

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

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

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

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

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

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

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

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

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

В предлагаемом способе в каждый вектор индекса доменов или блока из кодовой книги, состоящий из 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, то значению е2 присвоить значение и значению хr присвоить ; если u<0, то значения е2 и хr оставить без изменения;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1Число бит, встраиваемых в индексы доменов и блоков из кодовой книги1 бит2 бита3 бита4 бита5 бит6 бит7 битPSNR
на изображении "Лена", [дБ]
28.027.126.225.625.124.523.5
Максимально допустимый объем доп. информации, [бит]1024204830724096512061447168

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

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

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

2. Патент №2212769, МПК7 Н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 с.

Похожие патенты RU2327301C2

название год авторы номер документа
СПОСОБ ПЕРЕДАЧИ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ПРИ СОВМЕСТНОМ ИСПОЛЬЗОВАНИИ ВЕКТОРНОГО КВАНТОВАНИЯ И ФРАКТАЛЬНОГО КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ 2005
  • Тезин Александр Васильевич
  • Шмойлов Александр Витальевич
  • Шульгин Роман Николаевич
RU2313917C2
СПОСОБ СОВМЕСТНОГО ИСПОЛЬЗОВАНИЯ ВЕКТОРНОГО КВАНТОВАНИЯ И ФРАКТАЛЬНОГО КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ 2005
  • Тезин Александр Васильевич
  • Шмойлов Александр Витальевич
  • Чистяков Сергей Владимирович
  • Стремоухов Михаил Владимирович
RU2316908C2
СПОСОБ ПОВЫШЕНИЯ СКОРОСТИ КОДИРОВАНИЯ ПРИ СОВМЕСТНОМ ИСПОЛЬЗОВАНИИ ВЕКТОРНОГО КВАНТОВАНИЯ И ФРАКТАЛЬНОГО КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ 2006
  • Тезин Александр Васильевич
  • Шмойлов Александр Витальевич
  • Трегубов Роман Борисович
RU2321184C2
СПОСОБ ВСТРАИВАНИЯ ИНФОРМАЦИИ В ИЗОБРАЖЕНИЕ, СЖАТОЕ ФРАКТАЛЬНЫМ МЕТОДОМ, НА ОСНОВЕ СФОРМИРОВАННОЙ БИБЛИОТЕКИ ДОМЕНОВ 2013
  • Двилянский Алексей Аркадьевич
  • Кирюхин Дмитрий Александрович
  • Снаров Михаил Михайлович
  • Еменка Константин Геннадьевич
  • Чириков Владимир Евгеньевич
  • Трапашко Владимир Сергеевич
  • Швытов Константин Владимирович
  • Чурбанов Андрей Николаевич
  • Иванов Иван Владимирович
RU2530339C1
СПОСОБ ПЕРЕДАЧИ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ПРИ ФРАКТАЛЬНОМ КОДИРОВАНИИ ИЗОБРАЖЕНИЯ 2005
  • Тезин Александр Васильевич
  • Шмойлов Александр Витальевич
  • Стремоухов Михаил Владимирович
RU2292662C2
СПОСОБ ВСТРАИВАНИЯ ИНФОРМАЦИИ В ИЗОБРАЖЕНИЕ, СЖАТОЕ ФРАКТАЛЬНЫМ МЕТОДОМ, С УЧЕТОМ МОЩНОСТИ ПИКСЕЛЕЙ ДОМЕНА 2013
  • Иванов Владимир Алексеевич
  • Двилянский Алексей Аркадьевич
  • Кирюхин Дмитрий Александрович
  • Снаров Михаил Михайлович
  • Еменка Константин Геннадьевич
  • Чириков Владимир Евгеньевич
  • Иванов Иван Владимирович
RU2546558C2
СПОСОБ ВСТРАИВАНИЯ ИНФОРМАЦИИ В ГРАФИЧЕСКИЙ ФАЙЛ, СЖАТЫЙ ФРАКТАЛЬНЫМ МЕТОДОМ 2015
  • Иванов Владимир Алексеевич
  • Снаров Михаил Михайлович
  • Двилянский Алексей Аркадьевич
  • Иванов Иван Владимирович
  • Кирюхин Дмитрий Александрович
  • Крюков Марк Сергеевич
  • Ксенофонтов Алексей Андреевич
  • Щуров Константин Сергеевич
RU2602670C1
СПОСОБ СЖАТИЯ ГРАФИЧЕСКОГО ФАЙЛА ФРАКТАЛЬНЫМ МЕТОДОМ С ИСПОЛЬЗОВАНИЕМ КОЛЬЦЕВОЙ КЛАССИФИКАЦИИ СЕГМЕНТОВ 2013
  • Иванов Владимир Алексеевич
  • Двилянский Алексей Аркадьевич
  • Кирюхин Дмитрий Александрович
  • Снаров Михаил Михайлович
  • Еменка Константин Геннадьевич
  • Чириков Владимир Евгеньевич
  • Иванов Иван Владимирович
RU2541203C2
СПОСОБ ПЕРЕДАЧИ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ПРИ ФРАКТАЛЬНОМ КОДИРОВАНИИ ИЗОБРАЖЕНИЙ 2007
  • Тезин Александр Васильевич
  • Ширко Александр Иванович
  • Кириллов Александр Алексеевич
  • Шмойлов Александр Витальевич
RU2339181C1
СПОСОБ СЖАТИЯ ИЗОБРАЖЕНИЯ 2009
  • Трофимов Александр Сергеевич
  • Шоробура Сергей Миронович
RU2408076C1

Иллюстрации к изобретению RU 2 327 301 C2

Реферат патента 2008 года СПОСОБ ПЕРЕДАЧИ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ПРИ СОВМЕСТНОМ ИСПОЛЬЗОВАНИИ ВЕКТОРНОГО КВАНТОВАНИЯ И ФРАКТАЛЬНОГО КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ С УЧЕТОМ КЛАССИФИКАЦИИ ДОМЕНОВ И БЛОКОВ ИЗ КОДОВОЙ КНИГИ

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

Формула изобретения RU 2 327 301 C2

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

Документы, цитированные в отчете о поиске Патент 2008 года RU2327301C2

СПОСОБ И УСТРОЙСТВО ДЛЯ СОЗДАНИЯ ТЕЛЕВИЗИОННОГО СИГНАЛА С ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИЕЙ, А ТАКЖЕ УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ИЗ ТЕЛЕВИЗИОННОГО СИГНАЛА 1998
  • Тёлле Ханс-Рольф
  • Гюнтхер Херман
RU2212769C2
Устройство для преобразования изображений объектов 1989
  • Лысенко Юрий Андреевич
  • Елманов Сергей Александрович
SU1672490A1
US 6643383 B1, 04.11.2003
US 5862263 A1, 19.01.1999
JP 2000308056 A, 02.11.2000
US 6775415 A1, 10.08.2004
US 5065447 A1, 12.11.1991
УЭЛСТИД С
Фракталы и вейвлеты для сжатия изображений в действии
- М.: Триумф, 2003, с.107, 120-127
PUATE J., JORDAN F
Using fractal compression scheme to

RU 2 327 301 C2

Авторы

Тезин Александр Васильевич

Шмойлов Александр Витальевич

Даты

2008-06-20Публикация

2006-04-07Подача