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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В данной процедуре предложено использовать известный метод Гаусса-Зейделя [4, с.171-176]. Процесс поиска оптимальных индексов доменов, определенных на множестве "1" и "0", может занимать достаточно большое время. Поэтому для сокращения времени поиска оптимальных элементов индексов предлагается реализовать приближенный метод поиска. Данный метод предполагает осуществление оптимизации одного подмножества при фиксации других. Далее, для найденного оптимального подмножества, выполняют оптимизацию других подмножеств. Данный процесс повторяется, пока изменение одного из подмножеств не будет приводить к минимизации (максимизации) выбранного критерия.

Процесс поиска оптимальных элементов вектора в заявленном способе предлагается осуществить в виде следующей последовательности действий:

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

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

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

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

5. Выполнить инверсию i-го элемента вектора : , где x_i {0,1},

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

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

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

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

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

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

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

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

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

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

Фиг.4 - алгоритм поиска оптимальных элементов индексов домена при вводе дополнительной информации для передачи по каналу связи;

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

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

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

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

На фиг.5 отображены результаты проведенного исследования, которые показали, что при встраивании дополнительной информации в индекс домена качество восстановленного изображения остается в пределах нормы. При кодировании изображения размером 256×256 пикселов в градациях серого дополнительно передавалась дополнительная информация. В качестве дополнительной информации выступало изображение размером 64×64 пикселов в градациях серого. При декодировании в качестве начальных изображений был использован шум. Соотношение сигнал/шум после пятой итерации для основного изображения составило 22,8 дБ (восстановление основного изображения путем итераций представлено на фиг.5 на первых двух строках). При кодировании тестового изображения "Лена" без вставки дополнительной информации соотношение сигнал/шум составляло 25,7 дБ. Соотношение сигнал/шум после пятой итерации для дополнительного изображения составило 27 дБ (декодирование этого изображения представлено на последних двух строках фиг.5).

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

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

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

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

4. Ракитин В. И., Первушин В.Е. Практическое руководство по методам вычислений с приложением программ для персональных компьютеров: Учеб. пособие. - М.: Высш. шк., 1998. - 383 с.