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

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

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

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

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

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

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

Для достижения этого технического результата вставка дополнительной информации при фрактальном методе сжатия осуществляется в индексы ориентации доменных блоков, поскольку в кн. С. Уэлстида "Фракталы и вейвлеты для сжатия изображений в действии". Учебное пособие. - М.: Издательство Триумф, 2003, с.99-100 [3] указано, что незначительная чувствительность к искажениям в индексах преобразований (индексах ориентации доменов) является подтверждением того, что эти преобразования могут быть вообще исключены из процесса кодирования. Данный факт был также подтвержден авторами заявки на изобретение.

Рассмотрим базовый алгоритм фрактального кодирования изображений, который выполняется следующим образом [3]:

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

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

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

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

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

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

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

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

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

где: {dij} и {rij} - это соответственно значения пикселов доменной и ранговой областей.

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

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

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

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

фиг.1 - аффинное преобразование доменов в ранговые блоки;

фиг.2 - зависимость ошибки декодирования от ошибок в индексах доменов и индексах преобразований;

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

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

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

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

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

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

Источники информации

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

2. Патент №2292662, МПК8 Н04N 7/08 от 27.01.2007 г.

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

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

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

Иллюстрации к изобретению RU 2 339 181 C1

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

Изобретение относится к способу сокращения избыточности передаваемой информации. Технический результат, на достижение которого направлено изобретение, заключается в собственно создании способа передачи дополнительной информации при фрактальном кодировании изображений. Передача дополнительной информации осуществляется следующим образом: при сжатии исходного изображения с помощью фрактального способа сжатия в индексы ориентации доменных блоков записывают бинарную последовательность из трех цифр, представляющую дополнительную информацию, далее с учетом данной дополнительной информации осуществляют поворот обрабатываемого домена и поиск коэффициентов яркости - о и контрастности - s методом наименьших квадратов, соответствующие оптимальным значениям, при которых минимизируют выражение: где: {dij} и {rij} соответственно значения пикселов доменной и ранговой областей, в результате чего находят оптимальный домен с учетом встроенной дополнительной информации для кодирования рангового блока, после чего индексы доменов, коэффициенты яркости и контрастности, дополнительную информацию передают по каналу связи. На приемной стороне происходит выделение дополнительной информации и восстановление исходного изображения. 4 ил.

Формула изобретения RU 2 339 181 C1

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

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

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

СПОСОБ ПЕРЕДАЧИ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИИ ПРИ ФРАКТАЛЬНОМ КОДИРОВАНИИ ИЗОБРАЖЕНИЯ 2005
  • Тезин Александр Васильевич
  • Шмойлов Александр Витальевич
  • Стремоухов Михаил Владимирович
RU2292662C2
US 6272258 В1, 07.08.2001
US 6643383 В1, 04.11.2003
Способ детоксикации организма 1979
  • Панченков Роман Тихонович
  • Выренков Юрий Евгеньевич
  • Ярема Иван Васильевна
  • Уртаев Бексолтан Махарбекович
  • Яценко Александр Александрович
  • Кулаженков Сергей Афанасьевич
SU833262A1
J
Puate, F
Jordan, Using fractal compression scheme to embed a digital signature into an image, Proc
Порт-карта для авиационных целей 1924
  • Виткевич В.И.
SU2915A1
С.Уэлстид, Фракталы и вейвлеты для сжатия изображений в действии, Москва, Триумф, 2003, с.с.99-100.

RU 2 339 181 C1

Авторы

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

Ширко Александр Иванович

Кириллов Александр Алексеевич

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

Даты

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

2007-06-25Подача