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

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

Способ совместного использования векторного квантования и фрактального кодирования изображений, заключающийся в том, что в процессе векторного квантования исходное изображение разбивают на блоки по к отсчетов в каждом (к - целое положительное), формируют идентичные кодовые книги в кодере и декодере, к каждому ранговому блоку исходного изображения применяется фрактальный метод кодирования, сравнивают варианты фрактального преобразования всех доменов с выбранным ранговым блоком, используя в качестве доменных областей либо фрагменты кодируемого изображения, либо векторы кодовой книги, при этом, если ранговый блок точнее отображается доменным блоком E₁(R,D)_min <E₂(R,D)_min, то декодеру передают индекс соответствующего домена, в противном случае для блоков с большим динамическим диапазоном при E ₁(R,D)_min>E₂ (R,D)_min декодеру передается индекс вектора, по которому из кодовой книги на приеме выбирается соответствующий индексу фрагмент, которым после фрактального декодирования заполняется восстановленное изображение,

где - метрика между ранговым блоком R и приведенным к нему по размеру доменным блоком D, n - число строк в обрабатываемом ранговом блоке, m- число столбцов в обрабатываемом ранговом блоке,

E₁(R,D) - метрика, где доменами являются блоки исходного изображения,

Е₂(Р,В) - метрика, где доменами являются блоки из кодовой книги.

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

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

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

где E(R,D) - метрика между ранговым блоком R и приведенным к нему по размеру доменным блоком D;

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

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

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

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

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

Наиболее близким по своей технической сущности к заявленному способу совместного использования векторного квантования и фрактального кодирования изображений является устройство кодирования и декодирования с использованием векторного квантования по патенту США №5010401, H 04 N 7/13, 1991 г. [3].

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

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

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

Суть предлагаемого способа заключается в комбинировании фрактального способа сжатия с векторным квантованием. Сначала к исходному изображению применяется описанный в [1] фрактальный алгоритм сжатия. После этого поиск наиболее подходящего домена осуществляется из кодовой книги. Это связано с тем, что для ранговых областей с большим динамическим диапазоном бывает сложно подобрать домен с еще большим динамическим диапазоном, поэтому для кодирования таких областей используется кодовая книга. Формирование кодовой книги осуществляется итерационным кластерным алгоритмом, известным также как алгоритмом k-средних, описанным в [2]. В соответствии с данным алгоритмом выбирают некоторую последовательность изображений, принадлежащих различным классам. Далее эту последовательность преобразуют в последовательность входных векторов или обучающую последовательность, по которым формируется кодовая книга. При этом входные векторы должны обладать большим динамическим диапазоном, так как кодовая книга должна содержать блоки, отображающие резкие грани между фрагментами изображения, поскольку именно в таких случаях могут возникнуть проблемы с поиском подходящего домена. Такая ситуация обычно возникает из-за ограничений на динамический диапазон искомого домена, который, как правило, должен быть больше динамического диапазона ранговой области. На участках с резкими границами динамический диапазон очень велик и часто оказывается, что он достигает своего максимального значения. В этом случае не существует домена со строго большим динамическим диапазоном и ранговая область замещается наиболее похожим блоком из кодовой книги. Блоки выбраны так, что их структура не зависит от разрешения, и это дает ему дополнительное преимущество в сочетании с фрактальным методом.

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

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

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

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

- Фиг.3 зависимость пикового соотношения сигнал/шум (PSNR) от числа итераций при восстановлении исходного изображения с помощью базового алгоритма фрактального сжатия и алгоритма совместного использования векторного квантования и фрактального кодирования изображений.

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

На фиг.2 показана схема совместного использования векторного квантования и фрактального кодирования изображений. Предварительно в кодере и декодере с помощью векторного квантования формируют идентичные кодовые книги. Далее к каждому ранговому блоку исходного изображения применяется фрактальный метод сжатия. В результате работы которого алгоритм сравнивает варианты преобразования всех доменов к выбранному ранговому блоку. В качестве доменных областей используются либо фрагменты кодируемого изображения, либо векторы кодовой книги. Если ранговый блок лучше отображается доменным блоком (E₁(R,D) _min<E₂(R,D)_min ), то декодеру передается индекс соответствующего домена, в противном случае (E₁(R,D)_min >E₂(R,D)_min) декодеру передается индекс вектора, по которому из кодовой книги на приеме выбирается необходимый фрагмент, которым после фрактального декодирования заполняется восстановленное изображение.

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

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

Литература

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

2. Спутниковое телевидение. Новые методы передачи. / Н.Г.Харатишвили, Э.И.Кумыш, В.Ю.Епанечников, О.Г.Зумбурипзе; Под ред. Н.Г.Харагишвили. - М: Радио и связь, 1993.

3. Патент США №5010401, МПК H 04 N 7/13, 1991 г.