Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 004.932.2

R-D ПРОБЛЕМА И ЭФФЕКТИВНОСТЬ СИСТЕМ СЖАТИЯ ИЗОБРАЖЕНИЙ

Мороз В.В.

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

В зависимости от вида извлекаемой избыточности возможны два класса алгоритмов сжатия данных: с частичной потерей информации и без потери информации. Сжатие без потери информации, основанное на извлечении статистической избыточности, позволяет полностью восстановить исходные данные, т.е. реконструированные после сжатия данные будут идентичны данным до сжатия. Но, сжатие без потери информации позволяет достичь небольших степеней сжатия – в 3-5 раз. Для извлечения дополнительных типов избыточности используется психофизическое строение системы зрения человека. Установлено, что в системе зрения человека содержаться  элементы гомоморфной обработки информации. А такие характеристики системы зрения, как способность восприятия яркости света и ее пространственно частотный отклик, позволяют извлекать из изображения цветовую и пространственную избыточность.

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

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

В задачах кодирования реалистических изображений с использованием дискретного вейвлетного преобразования (Discrete Wavelet TransformDWT) [1] эффективность кодирования понимается как минимизации среднеквадратичной ошибки восстановленного после сжатия изображения для заданного битрейта. Битрейт есть количество бит, приходящееся на один пиксель. Эффективность кодирования изображений неразрывно связана с контролем уровня потерь информации и управлением степенью сжатия. Потери информации в процессе сжатия происходят на этапе квантования вейвлетных коэффициентов Q. Поэтому определение оптимальных, с точки зрения визуального качества, параметров квантования Q и энтропийного кодирования EC для заданного битрейта является актуальной задачей. Кодер С используется для подготовки контекстного моделирования квантованных вейвлетных коэффициентов и в дальнейшем рассматривается как часть энтопийного кодера.

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

Наиболее известными алгоритмами решения задачи эффективного кодирования с использованием DWT являются EZW (Embedded Zerotree Wavelet) [2], SPIHT (Set Partitioning In Hierarchical Trees) [3] и EBCOT (Embedded Block Coding with Optimized Truncation) [4], в которых использована упрощенная математическая модель исходного изображения. Предполагается, что изображение является дискретным случайным процессом с независимыми и одинаково распределенными случайными величинами (как правило, с гауссовским распределением вероятностей). Кодирование рассматривается как последовательная обработка нескольких информационных потоков , где  – количество частотных диапазонов, полученных в результате дискретного вейвлетного преобразования. Вейвлетные коэффициенты в каждом частотном диапазоне равномерно квантуются с заданным для каждого диапазона коэффициентом квантования. Энтропийное кодирование, как показано на рис. 2, выполняется за два шага: сначала выполняется контекстное моделирование (исследование окрестности уже квантованных коэффициентов) для выбора вероятностной модели с последующим адаптивным арифметическим кодированием, а затем ―  оптимальное распределение бит.

Для определения оптимального распределения бит между потоками используются кривые эффективности, которые характеризуют функциональную зависимость битрейта  от уровня искажения восстановленного изображения . Минимальный уровень искажения  при ограничении битрейта ищется путем минимизации функции , где  ― уровень искажения -го потока,  ― битрейт  -го потока, λ ― множитель Лагранжа. Наибольшую сложность такого метода решения задачи представляет определение кривых эффективности каждого потока, которые зависят от вероятностной модели изображения и используемой техники кодирования. В некоторых работах функциональная зависимость  строится для нескольких точек, а общая  кривая получается в результате аппроксимации этих точек [5].

Задача минимизации уровня искажения при заданном ограничении на битрейт также может быть решена с использованием  алгоритма Ллойда-Макса [6], но он основан на обучении, в связи с чем возникает необходимость наличия информации об источнике. Построение квантователя на основе этой информации тоже требует больших вычислительных затрат. Следовательно решение задачи эффективного кодирования с оптимальным распределением бит должно быть направлено на поиск другой техники энтропийного кодирования. Так как кодированию подвергаются квантованные вейвлетные коэффициенты (индексы квантования), то было бы целесообразно совместить  квантование, энтропийное кодирования и оптимальное распределение бит. При совместном рассмотрении процессов квантования и энтропийного кодирования, необходимо знать какой вклад привносит квантование и энтропийное кодирование в общую характеристику производительности кодека. Это позволило бы отслеживать  квантователи, требующие больших вычислительных ресурсов, но без определения вычмслительной сложности квантователя это сделать тяжело.

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

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

Пусть дискретная случайная величина  имеет плотность распределения вероятностей . Рассматривается равномерное квантование с размером шага квантования  и предполагается, что  настолько мал, что в пределах интервала квантования  функция плотности вероятности  будет практически постоянной. С каждым интервалом квантования  связывается число  ― уровень квантования, причем  , где  ― количество уровней квантования. Входное значение  отображается в , если, и только если . Мера уровня искажения, в общем случае, может быть введена как  норма [1]:

.                                                  (1)

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

Ошибка квантования для этого случая будет:

.

 

Тогда уровень искажения может быть определен как

.                                                    (2)

 

Как видно из (2) уровень искажения является функцией шага квантования. Если используется равномерное квантование для всего изображения, то изменяя шаг квантования, можно изменять качество изображения. При достаточно малых значениях  с учетом выражения (2) среднеквадратичная ошибка в частотном домене будет . Если преобразование является ортонормированным, то  не будет изменяться в области изображения. Отношение сигнал/шум по мощности можно вычислить как:

     ,                                   

где:       – количество бит, приходящееся на один пиксель в исходном изображении.

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

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

 λ.                                                     (3)

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

Для поиска λ возьмем математическое ожидание от функционала (3):

.                                        (4)

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

С учетом (2) и данного предположения, выражение (4) примет вид:

   .                                                   (5)

Тогда

,

а ограничение  может быть переписано как

.

Дифференцируя правую часть в выражении (5) и приравнивая ее к нулю, получим

,

 или

,                                                                       (6)

где: .

 

После подстановки (6) в (3) получим

или, после нормализации,

.                          (7)

 

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

В качестве тестовых изображений использовались Lena (размером 512х512 пикселей), Barbara и Goldhill (размером 720х256 пикселей) с глубиной цвета 24 бита. Изображения сначала переводились  из цветового пространства RGB в YUV. Затем к ним применялось DWT с использованием фильтра 9/7.  Последующее кодирование производилось с использованием предложенного алгоритма.

Как показывают экспериментальные исследования, данный подход позволяет значительно ускорить поиск оптимального индекса квантования и снизить вычислительные затраты не менее чем в два раза. При этом качество восстанавливаемых после сжатия тестовых изображений не уступает, а для битрейтов ниже 0,6 бит/пиксель и превосходит на 0,1 – 0,3 децибела качество изображений, полученным с помощью верификационной модели кодека JPEG2000.

Исключение составляют классы изображений, содержащих высокочастотные области. В качестве таких тестовых изображений были выбраны Cha1520 (размером 1520x1008 пикселей) и House (размером 512x512 пикселей). Несмотря на высокую производительность кодирования, для таких изображений наблюдался эффект «размывания» высокочастотных областей. Для устранения данного артефакта необходимо производить дополнительный анализ контекста текущего пикселя, но это может привести к повышению вычислительной сложности алгоритма.

Таким образом, предложенный алгоритм эффективного кодирования может быть использован в системах сжатия с целью уменьшения вычислительных затрат. Время кодирования/декодирования кодека, разработанного на базе данного алгоритма, меньше по сравнению с верификационной моделью JPEG2000 Jasper 7.1. Но судить о скорости работы практических реализаций стандарта пока рано, количество таких реализаций на сегодняшний день очень невелико. Имеющиеся plug-in JPEG2000, например в графическом браузере ACDSee 8.0, не позволяют провести детальный анализ их эффективности. Тем не менее, можно сказать, что доступные реализации на некоторых  битрейтах не только уступают по качеству, предложенному алгоритму, но и медленнее его. Так для тестового изображения  CHA1520 у кодека, реализующего предложенный алгоритм, время кодирования для степени сжатия 80:1 (0,3 бит/пиксель) ниже на 18%, чем у кодека Jasper 7.1.

Достоинством кодека, реализующего данный алгоритм, является также его совместимость со стандартом сжатия JPEG2000.

 

The rate-distortion relation is a key problem in systems of images compression. For increase of efficiency of compression systems search of an optimum rate-distortion parity offered. The embedded encoding with change of scanning wavelet coefficients is using for truncation of the least significant bits.

 

1.                  Добеши И. Десять лекций по вейвлетам. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 464 с.

2.                  Shapiro J. Embedded image coding using zerotree of wavelet coefficients // IEEE Trans. Signal Processing. — 1993 — Vol. 41. — Pp. 3445 — 3462.

3.                  Said A., Pearlman W. A new, fast and efficient image codec based on set partitioning in hierarchical trees // IEEE Trans. Circuits Syst. Video Technol. — 1996 — Vol. 6. — Pp. 243 — 250.

4.                  Taubman D. High performance scalable image compression with EBCOT // IEEE Trans. Image Proc.  — 2000 — Vol. 9. — Pp. 1158 1170.

5.                  Jin Li, Shawmin Lei. An embedded  still image coder with rate-distortion optimization //  IEEE Trans. on image processing. 1999 Vol. 8, . 7.  P. 913 924.

6.                  Gersho A., Gray R. M., Vector Quantization and Signal Compression. Norwell: Kluwer Academic Publishers, 1992. — 732 p.

7.                  Adams M. D. The JPEG-2000 Still Image Compression Standard // ISO/IEC JTC 1/SC 29/WG1 N 2412.  —  2001.

 

 





Ответы на вопросы [_Задать вопроос_]

Информационно-измерительные системы

Ковальов О.І. Вимірювання у процесно-орієнтованих стандартах

Полякова М.В., Ищенко А.В., Худайбердин Э.И. Порогово-пространственная сегментация цветных текстурированных изображений на основе метода JSEG

Дзюбаненко А. В. Организация компьютерных систем для анализа изображений

Гордеев Б.Н., Зивенко А.В., Наконечный А.Г. Формирование зондирующих импульсов для полиметрических измерительных систем

Богданов А.В., Бень А.П., Хойна С.И. Релаксация обратного тока диодов Шоттки после их магнитно-импульсной обработки (МИО)

Тверезовский В.С., Бараненко Р.В. Проектирование измерителя добротности варикапов

Тверезовский В.С., Бараненко Р.В. Оптимизированная модель измерителя доб-ротности варикапов

Руднєва М.С., Кочеткова О.В., Задорожній Р.О. Принципи побудови оптимальної структури інформаційно-вимірювальної системи геометричних розмірів об’єктів в діапазоні від 1 нм до 1000 нм

Биленко М.С., Рожков С.А., Единович М.Б. Идентификация деформаций пе-риодических структур с использованием систем технического зрения

Рашкевич Ю.М., Ковальчук А.М., Пелешко Д.Д. Афінні перетворення в модифікаціях алгоритму RSA шифрування зображень

Дидык А.А., Фефелов А.А, Литвиненко В.И., Шкурдода С.В., Синяков Ф. В. Классификация масс-спектров с помощью кооперативного иммунного алгоритма

Клименко А.K. Обратная модель для решения задач в системах с многосвязными динамическими объектами

Завгородній А.Б. Порівняльне дослідження твердотільних і рідиннофазних об'єктів методом газорозрядної візуалізації

Голощапов С.С., Петровский А.В., Рожко Ж.А., Боярчук А.И. Измерение доб-ротности колебательного контура на основе метода биения частот

Кириллов О.Л., Якимчук Г.С. Диагностирование критерия безопасности при заполнении замкнутых объемов СПЖ косвенным методом

Долина В.Г. Проблеми підвищення точності рефрактометра на основі прозорих порожнистих циліндрів.

Самков О.В., Захарченко Ю.А. Застосування алгоритму клонального відбору для побудови планів модернізації авіаційної техніки

Попов Д.В. Метод формування регламентів технічного обслуговування повітряних суден

Казак В.М., Чорний Г.П., Чорний Т.Г. Оцінювання готовності технічних об’єктів з урахуванням достовірності їх контролю

Тверезовский В.С., Бараненко Р.В. Технические аспекты проектирования цифрового измерителя добротности варикапов

Тверезовский В.С., Бараненко Р.В. Технические аспекты проектирования устройства для разбраковки варикапов по емкостным параметрaм и добротности

Сосюк А.В. Інтелектуальний автоматизований контроль знань в системах дистанційного навчання

Соколов А.Є. Деякі аспекти систезу комп’ютеризованої адаптивної системи навчання

Полякова М.В., Волкова Н.П., Іванова О.В. Сегментація зображень стохастичних текстур амплітудно-детекторним методом у просторі вейвлет-перетворення

Луцкий М.Г., Пономаренко А.В., Филоненко С.Ф. Обработка сигналов акустической эмиссии при определении положения сквозных дефектов

Литвиненко В.И., Дидык А.А., Захарченко Ю.А. Компьютерная система для решения задач классификации на основе модифицированных иммунных алгоритмов

Лубяный В.З., Голощапов С.С. Прямоотсчетные измерители расхождений емкостей

Беляев А.В. Построение навигации для иерархических структур в WEB-системах и системах управления WEB-сайтом

Терновая Т.И., Сумская О.П., Слободянюк И.И., Булка Т.И. Контроль качества тканей специального назначения с помощью автоматических систем.

Шеховцов А.В. Інформаційний аспект: розпізнавання образів індивідуума.

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

Литвиненко В.И. Прогнозирования нестационарных временных рядов с помощью синтезируемых нечетких нейронных сетей

Ковриго Ю.М., Мисак В.Ф., Мовчан А.П., Любицький С.В. Автоматизована система діагностики генераторів електростанцій

Браїловський В.В., Іванчук М.М., Ватаманюк П.П., Танасюк В.С. Керований детектор імпульсного ЯКР спектрометра

Забытовская О.И. Построение функции полезности по экспериментальным данным.

Шиманські З. Апаратні засоби сегментації мовного сигналу

Хобин В.А., Титлова О.А. К вопросу измерения парожидкостного фронта в дефлегматоре абсорбционно-диффузионной холодильной машины (АДХМ)

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

Слань Ю. М., Трегуб В. Г. Оперативна нейромережна ідентифікація складних об’єктів керування

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

Кириллов О.Л., Якимчук Г.С., Якимчук С.Г. Изучение электрического поля с помощью датчика измерителя электростатического потенциала на модели замкнутого металлического объема

Грицик В.В. Застосування штучних нейронних мереж при проектуванні комп’ютерного зору.

Гасанов А.С. Информационные технологии построения систем прогнозирования отказов

Шеховцов А.В., Везумский А.К., Середа Е.С. Алгоритм сжатия информации без потерь: модифицированный алгоритм LZ77

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Методы и алгоритмы визуализации пространственных данных на примере моделирования распространения лесных пожаров.

Полякова М.В., Крылов В.Н. Обобщённые масштабные функции с компактным носителем в задаче сегментации изображений упорядоченных текстур. – C. 75 – 84.

Полторак В.П., Дорогой Я.Ю. Система распознавания образов на базе нечеткого нейронного классификатора.

Литвиненко В.И. Синтез радиально-базисных сетей для решения задачи дистанционного определения концентрации хлорофилла.

Бражник Д.А. Управление совмещением изображения объекта в сцене и эталонного изображения.

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

Крылов В.Н., Полякова М.В., Волкова Н.П. Контурная сегментация в пространстве гиперболического вейвлет-преобразования с использованием математической морфологии.

Квасников В.П., Баранов А.Г. Анализ влияния дестабилизирующих факторов на работу биканальной координатно-измерительной машины.

Казак В.М., Гальченко С.М., Завгородній С.О. Аналіз можливості застосування імовірнісних методів розпізнавання для виявлення пошкоджень зовнішнього обводу літака.

Тищенко И.А., Лубяный В.З. Управление коммутационными процессами в интегрированных сетях связи.

Корниенко-Мифтахова И.К.,Филоненко С.Ф. Информационно-измерительная система для анализа характеристик динамического поведения конструкций.

Тверезовский В.С., Бараненко Р.В. Модель измерителя емкости с линейной шкалой измерений.

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

Рожков С.О., Федотова О.М. Алгоритм розпізнавання дефектів тканин для автоматичної системи контролю якості.

Бражник Д.А. Использование проективного преобразования для автоматизации обнаружения объектов.

Ходаков В.Є., Шеховцов А.В., Бараненко Р.В. Математичні аспекти створення автоматизованої системи „Реєстр виборців України”