Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований тема диссертации и автореферата по ВАК РФ 05.13.11, доктор физико-математических наук Умняшкин, Сергей Владимирович

• Умняшкин, Сергей Владимирович
• доктор физико-математических наук
• 2001

Оглавление диссертации доктор физико-математических наук Умняшкин, Сергей Владимирович

8

ГЛАВА 1. КОМПРЕССИЯ ИЗОБРАЖЕНИЙ: ОСНОВНЫЕ

ПОНЯТИЯ И ПРОБЛЕМЫ

1.1. Основные подходы к проблеме компрессии изображений

1.1.1. Математическая модель дискретного изображения

1.1.2. Мера ошибки восстановления изображений

1.1.3. Исходные идеи методов компрессии статических изображений

1.1.4. Вариант JPEG, основанный на применении ДКП

1.1.5. Проблема выбора базисов разложения

1.2. Использование вейвлет-преобразований для компрессии статических изображений

1.2.1. Основные понятия, определения, специфика вейвлет-преобразований

1.2.2. Двумерные вейвлет-преобразования

1.2.3. Основные идеи современных алгоритмов вейвлет-компрессии изображений

1.3. Особенности обработки видеопоследовательностей

1.4. Общая постановка задачи оптимизации кодирования с потерями

Введение диссертации (часть автореферата) на тему «Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований»

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

Дискретное черно-белое полутоновое изображение можно задать некоторой матрицей, элементы которой (точки изображения, называемые также пикселями) представляют собой полученные в результате некоторой пространственной дискретизации отсчеты функции, описывающей распределение яркости на непрерывном изображении. Цифровым изображением будем называть матрицу, полученную в результате поэлементного квантования (с конечным числом уровней) значений отсчетов дискретного изображения. Для описания цветного изображения (дискретного или цифрового) требуется уже три матрицы, соответствующие трем яркостным компонентам в выбранном цветовом пространстве, например RGB (red, green, blue). Описание изображения в виде матриц(ы) яркости будем называть непосредственным представлением.

Обработка, хранение, передача цифровых изображений при непосредственном представлении требуют колоссальных объемов данных. Так, например, для записи одного только кадра высококачественного цветного изображения размером 1024x1024 точки, при кодировании каждого отсчета 24 битами (8 бит на цветовую компоненту), потребуется 3 мегабайта данных. Конечно, при просмотре видеороликов допустимо меньшее разрешение экрана, тем не менее, для демонстрации цифрового видеофильма в реальном масштабе времени необходима передача данных со скоростью около 160 мегабит/с [39]. Сказанное объясняет тот громадный интерес, который проявляется во всем мире к поискам путей эффективного кодирования изображений.

Уже на заре развития цифровых методов обработки изображений (конец пятидесятых - начало шестидесятых годов) избыточность непосредственного представления изображений была очевидной, однако простейшие способы, применявшиеся для сжатия данных, такие как дифференциальная импульсно-кодовая модуляция с последующим статистическим кодированием, давали более чем скромные результаты. Постановка вопроса о применении частотных методов для сжатия изображений стала возможной благодаря появлению в 1965 году работы Кули и Тьюки [108], содержавшей описание алгоритма быстрого вычисления дискретного преобразования Фурье (ДПФ). Идея замены изображения как непосредственного объекта кодирования отсчетами его двумерного спектра ДПФ была выдвинута в 1968 году [89,91]. Кодирование посредством использования ДПФ основано на том, что для большинства изображений естественного происхождения значения многих коэффициентов ДПФ сравнительно малы. Такие коэффициенты можно часто вообще отбросить, или отвести на их кодирование малое число бит, без риска внести сколь либо значимые искажения. В 1969 году Прэтт, Эндрюс и Кэйн предложили использовать для кодирования изображений вместо преобразования Фурье преобразование Адамара [46,154,174], что во многих практических случаях позволяет значительно уменьшить объем необходимых вычислений. После этого были предприняты исследования по применению для кодирования изображений дискретных преобразований Карунена-Лоэва [126] и Хаара [83,158]. Преобразование Карунена-Лоэва является оптимальным в том смысле, что обеспечивает минимальную среднеквадратическую ошибку кодирования при отбрасывании части коэффициентов-трансформант, однако требует, к сожалению, знания статистических характеристик обрабатываемых изображений и не имеет быстрого алгоритма вычисления [45]; преобразование

Хаара, напротив, характеризуется в высшей степени эффективным алгоритмом вычисления, но дает, как правило, сравнительно большую погрешность кодирования [45]. В 1971 году Шибата и Эномото [119] предложили специально для использования в кодировании изображений так называемое наклонное преобразование векторов из 4-х или 8-ми компонент. Вскоре после этого Прэтт, Чен и Уилч разработали обобщенный алгоритм наклонного преобразования векторов большой длины и двумерных массивов [155].

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

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

Как показано Ахмедом и др. [87], в применении к кодированию изображений, для которых подходит марковская статистическая модель, дискретное косинусное преобразование (ДКП), имеющее быстрый алгоритм вычислений, приближается по эффективности спектрального представления данных к преобразованию Карунена-Лоэва (см. также [4,118,159]). Данный факт явился причиной того, что именно ДКП послужило основой при разработке стандарта сжатия неподвижных изображений JPEG [131,132,171]. Указанный стандарт явился плодом многолетних усилий . коллектива специалистов, образованного в 1987 году из представителей двух авторитетных международных организаций: ISO и ITU. Появление объединенной группы JPEG было вызвано ростом числа разработчиков и пользователей различных систем ЦОИ и вытекавшей из этого необходимостью унификации формата сжатого представления цифровых изображений. Выработанная в итоге спецификация [131,132] явилась документом, которого сегодня придерживаются практически все разработчики программных систем ЦОИ общего назначения. С 1994 года производятся специализированные микросхемы, реализующие сжатие и восстановление по JPEG аппаратно и обеспечивающие обработку цветных изображений в реальном масштабе времени (480x640 точек, 30 кадров/с [143]). С точки зрения достижимого уровня сжатия, вариант JPEG, основанный на использовании ДКП, не является лучшим среди существующих ныне методов эффективного кодирования изображений. Так, методы, базирующиеся на использовании вейвлет-преобразований2 [113], могут обеспечить значительно более высокие уровни сжатия - по этой причине в расширенном стандарте JPEG2000 [149],

2 w

В отечественной литературе вместо прямого перевода слова wavelet часто используется также термин всплеск. существующем в виде предварительной (draft) спецификации с 2000 года3 [139], уже предусмотрена возможность применения вейвлет-преобразований. Однако говорить о том, что сжатие изображений с использованием ДКП себя полностью изживает, на сегодняшний день преждевременно, поскольку по сравнению с вейвлет-преобразованиями вычислительные затраты, необходимые для реализации ДКП, намного меньше [177]. Более подробный обзор современных методов компрессии изображений и различий в используемых подходах будет дан в главе 1 настоящей работы.

Важность проблемы компрессии данных при обработке изображений трудно переоценить - достаточно проанализировать наблюдаемый в последнее десятилетие рост числа соответствующих публикаций. Так, значительную часть содержания ежемесячного журнала IEEE Transactions on Image Processing, издаваемого с 1992 года, составляют статьи, посвященные именно этой теме. Нельзя не заметить также и тот факт, что алгоритмы сжатия изображений и лежащая в их основе теория разрабатываются в основном за рубежом, прежде всего, в США. Конечно, говорить об отсутствии отечественных работ в данной области нельзя [5,8,11,24,29,41,81,98,117], однако необходимость значительного расширения российского фронта исследований не вызывает никаких сомнений.

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

3 2 января 2001 года часть 1 «JPEG 2000 Image Compression System: Part I Core Coding System» окончательно утверждена для принятия в качестве официального международного стандарта ISO/IEC 15444-1.

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

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

СКО = X у)2 > где ~ матрица исходного изображения, Л

Х = (х/ у) - матрица изображения, полученного после обработки (сжатия и восстановления данных). Для логарифмической величины СКО используется общепринятая мера PSNR (peak signal to noise ratio - отношение пикового

255 значения сигнала к шуму), PSNR = 201g-[дБ].

СКО

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

N-1M-1 квантование есть выделение из входных данных некоторой основной части информации, когда ее менее значимая часть опускается. Применяется как скалярное, так и векторное [124,125,151] квантование. В скалярном случае элементы обрабатываемого набора данных квантуются независимо друг от друга.

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

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

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

В первой главе отмечается, что для оптимизации алгоритмов сжатия данных с потерями часто используется подход, основанный на минимизации RD-функции Лагранжа [95]. Пусть X - некоторый входной набор данных, которому в результате выполнения процедуры сжатия-восстановления ставится в соответствие < выходной набор данных той же природы, Y=F(X,и), где u=(u\,.,un) - набор управляющих параметров алгоритма сжатия F. СчитаемX, Y элементами некоторого пространства Q с метрикой D(X, Y), множество всех возможных значений управляющего вектора и обозначим U. Задача оптимизации кодирования состоит в том, чтобы для заданного набора входных данных X и максимально допустимых битовых затрат Rb найти такие параметры и* = (щ,.,и*п) алгоритма F, чтобы ошибка кодирования данных D(X,Y)=D(X,F(X,\i)) принимала бы минимальное значение. То есть

D(X,F(X, u )) = D(X, u ) = minZ)(X,u), asU (0.1)

R(X,v)<Rb, где 7?(X,u) - число бит, необходимое для кодирования набора данных X с параметрами и.

Поиск решения задачи (0.1) в большинстве случаев сводится к громоздким численным процедурам итерационного характера. Если не задаваться ограничением R(X,u)<Rb, то для определения оптимальных параметров кодирования и*, соответствующих решению задачи (0.1) для некоторого заранее неизвестного значения Rb, используется упрощенный вариант минимизации RD-функции Лагранжа: и) = тт[7(и) = 1)(и) + АК(и)], (0.2) и где Я - неотрицательный параметр, задаваемый внешне. Параметр Я в функции /(и) устанавливает баланс между качеством и уровнем сжатия данных. Значение Я=0 соответствует наименьшей ошибке кодирования, увеличивая значение Я, получаем при оптимизации параметров алгоритма Р по (0.2) меньшую длину кода, но большую ошибку. Тем самым можно настраивать алгоритм кодирования -Р на необходимые характеристики. Для поиска решения задачи (0.1) минимизация (0.2) повторяется итерационно, с различными значениями Я - данная процедура носит название КО-оптимизации [95].

В первой главе также кратко отмечаются особенности, связанные с обработкой (сжатием-восстановлением) динамических изображений. Основным используемым преобразованием для видеокомпрессии пока остается ДКП, как более простое в плане объема вычислений по сравнению с вейвлет-преобразованиями [177]. Так же как и для статической компрессии, алгоритмы кодирования видео чаще всего являются более сложными по сравнению с алгоритмами декодирования. Реализация программной компрессии видео в реальном масштабе времени, таким образом, накладывает существенные ограничения на допустимую сложность вычислений.

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

Х = (х0,л;1,.,д:Дг1)г, вектор-спектр У получен в результате некоторого ортогонального преобразования с матрицей У=ЛУХ. Опуская выкладки, среднюю безусловную энтропию для коэффициентов вектор-спектра можем записать:

Нср = — X | /к (щ , х)\о%/к (тк ,ок,х)4х =

-/V Ъ-п к=0

0.3) Л к=0 к=0 функция плотности распределения вероятностей для

1 Аг-1 1 1\—11 1

Л°(х)1оё/Лх>/х; 1 лг где /к(ткоьх) спектральной характеристики ук (Аг-ой компоненты вектора У), /и^ -математическое ожидание, ок - среднеквадратичное отклонение, /к(х) = Чем меньше средняя энтропия (0.3), тем эффективнее будет последующее независимое кодирование компонент спектра.

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

1 Г 1 м~1(

1\ ^ ае1^х к=0 у-=0 ^

0.4)

Величина (0.4) неотрицательна, причем чем больше ее значение, тем ниже эффективность декоррелирующего преобразования с матрицей Численные расчеты величины (0.4) для различных преобразований и видов ковариационных матриц показали результаты, полностью согласующиеся с известными данными [4,43,45,118,153].

Большой интерес для анализа представляет модель дискретного сигнала (вектора X), имеющего статистику дискретного марковского процесса первого порядка, когда ковариационная матрица имеет следующий вид:

К х(р) =

1 Р

Р 1 лг-1 Л

N-2 рК-1 рМ-2

0.5)

Данная модель часто используется и для описания межстрочной и межстолбцовой корреляции в дискретных изображениях [45,90]. При р=1, когда все компоненты в исходном векторе X одинаковы (для любых двух отсчетов вектора коэффициент корреляции равен единице), расчет введенного критерия (0.4) для матрицы (0.5) невозможен, т.к. в этом случае имеем <ЫКХ = 0. Вместе с тем, на фоновых областях изображения р—>1. В главе 2 доказывается следующая теорема [78].

Теорема 2.1. Для любой ортогональной матрицы (Л/х/У) такой, что

V/ = ОД,. ,ЛГ -1: >у0 .• = —(базисная функция с нулевым индексом есть лА/У нормированная постоянная составляющая) и ковариационной матрицы (0.5) лм/ 2 N-1 N-1

1ипДЯ(\У,Кх)= — \о%

Различные исследования [4,43,45,118], в том числе проведенные в главе 2, показывают, что среди дискретных преобразований, имеющих быстрые алгоритмы вычислений (для размерности N реализуемых за -Шо^Ы арифметических операций) наиболее близкие к оптимальному преобразованию Карунена-Лоэва характеристики декорреляции для марковского процесса (0.5) дает использование ДКП. Несмотря на наличие хорошо проработанных быстрых алгоритмов вычисления, ДКП принципиально требует для своей реализации выполнения операций умножения и по объему вычислений заметно уступает, например, преобразованиям Хаара, Уолша, Крестенсона-Леви. Отдельным вопросом, рассмотрению которого уделено значительное внимание в главе 2, является построение (синтез) нового преобразования, имеющего как высокие характеристики декорреляции для модели (0.5), так и значительно более быстрые, чем для ДКП, алгоритмы вычисления. Полученное в результате дискретное псевдокосинусное преобразование (ДПКП) [65,66,74] определено для векторов такой размерности А^, для которой возможно разложение N=N1 ■. -Ып, причем У к {2,3,4}. Тогда матрица ДПКП (в данном случае нижний индекс указывает на размерность преобразования) строится как прямое (тензорное) произведение элементарных матриц ДПКП {\¥2,\¥з,\У4}: = \¥Лг1 ®. ® \Ул,п, причем элементарные матрицы ортогональны и представляют собой полученные в результате определенных модификаций матрицы ДКП соответствующей размерности4. Элементарные матрицы представимы в виде произведения некоторой диагональной матрицы Б на матрицу С, а структура С позволяет реализовать умножение на произвольный вектор и, СИ, только при помощи операций сложения и вычитания чисел.

Из свойств тензорного произведения следует представление = ОдгСд,, где диагональная матрица ®, а матрица

См =Сщ ®.®СЫп. Структуры матриц С2, С3, С4, В2, Б3, Б4 приводятся в главе 2. Таким образом, реализация ДПКП У = \Уд,Х = Б^С^Х заключается в реализации умножения матрицы См на вектор, У = С^Х, и последующей нормировке полученного вектора У: У = Б^У. Для вычисления ДПКП удобно использовать быстрые алгоритмы, основанные на факторизованном представлении для матрицы Оу в виде произведения слабозаполненных мат-риц5: Сдг = ТдГ] • ТдГ~1) ■.■ ТдР, где Т#> =1^ ^ ®1„м «.»1^ ,

1дг. - единичная матрица размерности ТУ . хА/" -. Поскольку матрицы Тд/}

J J J состоят из определенным образом разреженных матриц-блоков , умножение матрицы Тд/} на вектор также сводится только к операциям сложения и вычитания чисел. Быстрые алгоритмы обратного ДПКП строятся

4 Под тензорным (прямым) произведением матриц (/=0,.,7]-1; т= 0,.,А-1) и О^^} (к—0,., у-1; 7=0, .,/¿-1) понимаем матрицу

А0,0^ •••

8=В®С=К/}}= . ,а=0Х.,щ-\,р=0Х.,1йг\.

5 Для обоснования справедливости данного представления см. с.84-85 из монографии [1]. аналогично, т.к. в силу ортогональности ДПКП:

Отметим, что необходимая при вычислении ДГШП и обратного ДПКП нормировка (умножение на матрицу Ду) для схемы сжатия со скалярным квантованием коэффициентов преобразования не влечет усложнения вычислений [74]. Нормировка может быть объединена при сжатии данных с этапом скалярного квантования у^ - гоипс1(у7 / с() путем выбора для каждого элемента у. преобразованного индивидуального шага квантования qj=qldjj (где

- элемент диагональной нормировочной матрицы Б^). При А восстановлении вектора У~ У, у ту ■, множители для элементов у ^ следует выбирать также индивидуально, в виде

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

Третья глава посвящена изучению вопросов применения для сжатия изображений дискретного преобразования Крестенсона-Леви (ДПКЛ) и является развитием исследований кандидатской работы автора [72].

Система функций Крестенсона-Леви {хт на полуинтервале хе [0;1) в нумерации Пэли определяется следующим образом:

1(т)

271 ^ к=1

Жт(^)=11ехр I—хк -тк =ехр г—^хк-т.

V Р /

С ,2л1— V гк , (0.6)

Р *=1 где р>2 (целое число), хк = [х-^^тоёр), тк = \т!рк~х\т.о6-р), число / находится из условия: т<р1-1. Скобки [.] означают операцию взятия целой части, а хь т к представляют собой коэффициенты р-ичного разложения чисел х, т. Система функций Крестенсона-Леви является обобщением на комплексную плоскость хорошо известной системы функций Уолша [6,100,144], которая получается по определению (0.6) при р=2. Дискретное преобразование Уолша прочно занимает свое место в ряду других преобразований, применяемых для обработки изображений [47,51,80,81,85,86]; о приложениях ДПКЛ можно найти более скудную информацию [10,42,51,52].

Предварительно в главе 3 изучаются вопросы построения быстрых алгоритмов ДПКЛ. В матричном виде ДПКЛ можем записать:

У = (0.7) где Х = (х0,х1,.,^„1)г- исходный вектор, У = рП - векторспектр ДПКЛ. Нижний индекс п матрицы \У(„) указывает на размерность преобразования, Лт-рп. Элементами симметрической матрицы \У(„) являются отсчеты функций системы (0.6): мк1 = Хк (//Рп )• Быстрые алгоритмы ДПКЛ основаны на факторизованном представлении матрицы \У(И) в виде произведения слабозаполненных матриц. Один из возможных способов факторизации матрицы ДПКЛ предложен автором и может быть сформулирован в виде следующей теоремы [17].

Теорема 3.1. Матрица ДПКЛ представима в виде \У(й) = W((И1))W{(^)). .\¥((")), где Щ] = и(Л О на диагонали матрицы размерности рпхрп находятся р матриц размера рпЛхрпЛь остальные элементы матрицы - нулевые). Матрица п) ={Щк) (,Д=0,1,.,/-1) имеет следующий вид: м>м = ч • ди'к~1, где кх=к{то&р), ]п =[¡1 рп~1\то&р), ^=ехр(-2т/р), 8™ = \ ПрИ т { . 0, при т. Ф 7

Дискретные (цифровые) полутоновые изображения описываются в виде вещественной матрицы X. При обработке вещественных векторов (матриц) спектр ДПКЛ распадается на пары комплексно сопряженных элементов, поэтому часть элементов спектра можно не вычислять. Учет этих особенностей позволил предложить для обработки вещественных массивов алгоритмы ДПКЛ и обратного ДПКЛ с неполным вычислением. При обработке вещественных наборов данных возможно также применение «совмещённых» преобразований, аналогично тому, как это делается при вычислениях дискретного преобразования Фурье. При этом из двух вещественных векторов X и X2 формируют комплексный вектор Х=Х1+/Х2 и выполняют преобразование.

Если использовать для комплексных чисел г=хНу представление в базисе (1 г=а+Рд е~2л'/3), то вычисление ДПКЛ (при р= 3) может быть выполнено без использования операций умножения (нормирующий множитель

1/4р" , см. (0.7) - не учитывается), при помощи операций сложения и вычитания (данный факт установлен А.В.Ефимовым). Использование в алгоритмах с неполным вычислением базиса (1 ,д) влечет за собой ряд особенностей, которые рассматриваются в главе 3. При размерности матрицы изображения ЗпхЗг вычисление ДПКЛ или обратного ДПКЛ по алгоритмам с неполным вычислением требует выполнения 7(п+г)-3"+г'1 операций сложения (вычитания), операции умножения и деления не используются. Использование базиса (1,<7) в вычислительном плане является более эффективным и для алгоритмов совмещенных вычислений. Специфика, которую налагает использование ДПКЛ и базиса (1,#), а также необходимые для реализации совмещённых ДПКЛ и обратного ДПКЛ формулы [14], получены в главе 3.

Для обработки неподвижных изображений в кандидатской работе автора [72] был предложен алгоритм компрессии, в котором исходное изображение разбивается для обработки на элементарные фрагменты X, 9x9 точек, и каждая матрица-фрагмент обрабатывается при помощи ДПКЛ (по алгоритму с неполным вычислением). В главе 3 приводится краткое описание алгоритма компрессии [20], который подтвердил обоснованность использования дискретного преобразования Крестенсона-Леви для сжатия изображений. Характер вносимых в процессе сжатия-восстановления ошибок различен для основанного на ДКП метода JPEG и для предложенной схемы: при использовании JPEG имеет место "размывание", в то время как новая схема сжатия приводит к "зубчатости" изображения. Тем не менее, субъективное качество восприятия при использовании обоих рассмотренных способов сжатия примерно одинаково. Оценки величины искажений по величине PSNR, выполненные для ряда тестовых изображений размерности 720x504=362880 точек, также дали близкие результаты: для одних изображений может наблюдаться незначительное преимущество основанного на ДКП стандарта JPEG, для других изображений лучшее качество восстановления возможно при использовании нового метода. Различия невелики, особенно при невысоких уровнях сжатия. Оценки вычислительных затрат показывают, что алгоритм на основе ДПКЛ не уступает JPEG и в части, касающейся вычислительной сложности реализации. Алгоритм компрессии изображений [20,72], использующий ДПКЛ и имеющий сравнимые с JPEG характеристики, представляет собой результат, впервые полученный автором.

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

Для коэффициентов одномерного ДКП, определяемого формулой получено следующее соотношение (Ь*Ю): кк (0.8) вт— #

2Ы где А/=ху—Ху 1 - первые разности отсчетов исходного вектора данных Х = (л;0,д:1,.,л:лг1)Т. Формула (0.8) показывает, что разности А,- имеют различный характер влияния на спектр ДКП. Так, разность Аш-хш-х^/2-\ (при четном IV) входит во все коэффициенты у2ш с максимальными по модулю (единичными) весами. Разность между отсчётами х0 и вообще не входит в (0.8), что принципиально отличает ДКП от его «прародителя» - дискретного преобразования Фурье, амплитудный спектр которого инвариантен к циклическим сдвигам (х0—>х}—>.—>Хл>-1—>*о) компонент вектора данных X.

В предположении некоррелированности разностей6 А; и равенства нулю их математических ожиданий Е(А/)=0 исследовались также вероятностные оценки, в частности, величина суммарной дисперсии переменных составляющих спектра ДКП: Е - ¿,0{ук). Данная сумма пред ставима через к= 1 дисперсии первых разностей вектора данных следующим образом: Е=-^|S(j)D{Aj), где ¿'(у) - некоторый весовой коэффициент. Доказана

Теорема 4.1: для коэффициентов $(/) верно соотношение: Данная теорема вновь подтверждает, что и для использовавшейся вероятностной модели вектора X разность Ат (в данном случае, ее дисперсия) вносит наибольший вклад. Чем ближе номер разности к N/2, тем больше значение веса £(/') и тем больший вклад вносит разность А, в энергию переменных составляющих. Исследование спектров ДКП для некоторых характерных

6 Для марковской модели (0.5) данное допущение не верно. сигналов также подтвердило, что при использовании приемов кодирования спектров из JPEG (в частности, кодирование серий нулей - run-length encoding) эффективность кодирования будет ухудшаться в случае, когда информационная насыщенность дискретного сигнала будет приходиться на центральные отсчеты вектора.

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

Для сжатия статических изображений с использованием ДКП 8x8 в четвертой главе разработан новый алгоритм [59], отличающийся от JPEG этапом энтропийного кодирования, для которого используется несколько статистических моделей и алгоритм многопотокового арифметического кодирования [22]. Выбор модели производится определенным образом по контексту уже обработанных данных. Предложенный алгоритм арифметического контекстного кодирования коэффициентов ДКП повышает сжатие данных на 10% по сравнению со стандартной схемой JPEG (эталоном служила программа JPEG Optimizer™ v.4.0, см. http://xat.com).

Значительное внимание в четвертой главе уделено изучению общих теоретических и практических аспектов применения векторного квантования (ВК) для компрессии изображений в области преобразований, не обязательно с использованием ДКП. Для этого спектры фрагментов изображения необходимо разбить на определенные зоны, каждая из которых соответствует отдельному потоку данных, подвергаемому ВК. Сформулируем зад^ту разбиения коррелированного набора данных, который представим в виде вектора Y, на кластеры (классы) [53,63]. Исходными параметрами являются ковариационная матрица Ку вектора У и ограничение на максимальную неопределённость (энтропию) НтаХ для каждого кластера в разбиении. Требуется найти такое разбиение множества случайных компонент У={70,.,ГЛг1} на подмножества

У(А) = ^„.„У^], к=1,.,М, чтобы:

Ъ*"^ . (О,) я(у^)<ятах5 к=\,.,М. Минимум ищется по всем возможным разбиениям. Решение задачи определяет правило разбиения спектра фрагмента на зоны (кластеры) которые соответствуют М потокам данных, каждый из которых обрабатывается отдельным векторным квантователем. По полученной в результате статистической обработки фрагментов изображения ковариационной матрице коэффициентов преобразования Ку для построения разбиения спектра на зоны ВК могут быть использованы два квазиоптимальных способа [53,63]: алгоритм «Выращивания кластеров» и алгоритм «Выделения сильных связей». Оба предложенных способа численного поиска решения (0.9) основаны на минимизации энтропии межкластерных связей

М-1 .

Нсв(\а\.,\(м))=^Н{\{к))-Н(У). Более близкие к оптимальному к=1 удовлетворяющему (0.9)) разбиению показал второй из названных алгоритмов.

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

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

W = обозначает матрицу дискретного вейвлет-спектра, полученную в результате двумерного л-шагов о го вейвлет-преобразования матрицы дискретного изображения. Количество шагов вейвлет-преобразования определяет число частотных уровней в спектре, для п шагов имеем л+1 уровень. При этом коэффициенты вейвлет-разложения можно упорядочить в виде совокупности древовидных структур {7}, корнями которых являются элементы, лежащие в самом низкочастотном диапазоне спектра (саббэнде), см. рисунок. Подобное упорядочивание определяет для вейвлет-коэффициентов (узлов дерева) связи вида «родитель-потомки». Идейные основы разработанного алгоритма сжатия уходят корнями в работы Lewis-Knowles [145] и Xiong-Ramchandran-Orchard [175]; при этом основная задача, стоящая перед алгоритмом компрессии, состоит в поиске RD-оптимальной топологии (т.е. структуры S, которая получается после подрезания ветвей исходного дерева Т), минимизирующей функцию Лагранжа для фиксированного значения Я: J(S*) = тт[Д£) + ЯR(S)].

SqT

Идея, которая восходит к работе [145] и в том же виде используется в [175], заключается в следующем: чем больше абсолютная величина вейвлеткоэффициента I wj (или энергия, wf) узла-родителя /, тем менее вероятно появление у данного узла нулевой (т.е. подрезанной) ветви, что следует использовать для кодирования топологии дерева S. Более точное предсказание появления нулевой ветви можно составить, если использовать в качестве прогнозной величины Р, сумму, включающую в себя, помимо wf, также квадраты значений вейвлет-коэффициентов, соседних в саббэнде к узлу i. Проведенные в главе 5 экспериментальные исследования статистических зависимостей показали целесообразность использования для прогнозной к ев-------- ЕВ величины Р{ взвешенной суммы из абсолютных значений коэффициентов-соседей. Необходимые значения весовых множителей были установлены в результате статистической обработки вейвлет-спектров реальных фотографических изображений. Для кодирования топологии «подрезанного» дерева £ каждому узлу г дерева приписывается признак наличия (гц= 0) или отсутствия (пг— 1) в данном узле подрезанной ветви. Установлено, что для повышения эффективности статистического кодирования топологии 5 признаки {я,} следует определенным образом группировать в новые элементы данных {Ту,}. Последние подвергаются адаптивному арифметическому кодированию, причем используется несколько статистических моделей, контекстное (т.е. по уже закодированным данным) правило выбора модели задается определенным образом по прогнозным величинам {Т5,-}.

Для кодирования скалярно проквантованных вейвлет-коэффициентов, не попавших в нулевые (подрезанные) ветви, также используется несколько статистических моделей. Предложенное правило контекстного выбора моделей учитывает как значение прогнозной величины Р{ узла-родителя, так и значения вейвлет-коэффициентов соседних узлов, которые находятся в том же саббэнде, рядом с обрабатываемым, но уже закодированы. Выбор статистической модели для кодирования скалярно проквантованного вейвлет-коэффициента Wj=XQш\l^{Wjlд), соответствующего узлу у дерева Б, осуществляется по величине л , =0.36Р н-1.0б{ 1 У

Ух 0.4

М?; ]<1 где ]у - узел-сосед по вертикали, х — узел-сосед по горизонтали,/^ - узел-сосед по диагонали. Значения весовых множителей, фигурирующие в прогнозной величине зу, были получены в результате экспериментов по обработке реальных изображений.

Сравнение результатов, полученных в экспериментах по обработке реальных изображений, с результатами применения других известных алгоритмов вейвлет-компрессии изображений показывает, что предложенный алгоритм [61,165] имеет весьма высокие показатели. Так, для известного тестового изображения Lena при уровне сжатия 0.5 бит на пиксель (16 раз) ошибка PSNR=37.66 дБ.

Завершающие исследования главы 5 относятся к построению гибридной схемы кодирования вейвлет-спектра, когда в дополнение к описанному выше способу подрезания ветвей вейвлет-коэффициентов допускается также возможность векторного «самоквантования» ветвей, которое может трактоваться как фрактальное кодирование в области вейвлет-преобразований (см., например, [112]). Полученный в результате гибридный алгоритм [56] требует существенно большего объема вычислений, однако фрактальная составляющая кодирования при этом оказалась практически полностью подавленной базовой схемой вейвлет-компрессии, основанной на подрезании ветвей. Необходимо отметить, однако, что «смычка» подходов в гибридном алгоритме была произведена несложным способом и возможности дальнейшего развития оставляют здесь обширное поле для исследований.

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

Кадром видеопоследовательности называем матрицу пикселей из Mi строк и М2 столбцов: B=(bkj), А:=0,1,.,МГ1, /=0,1,.,М2-1, а под термином видеопоследовательность понимаем упорядоченный набор кадров В0,!*1,. ,,Вг,. Назовем (у, х)-блоком кадра В (у, х- целочисленные координаты) некоторую подматрицу BytX=(bkii), где k=y,y+\,.y+Ni-\, 1=х>х+\,.у+ЫгА. В разработанном алгоритме каждый кадр видеопоследовательности разбивается при обработке на смежные матрицы-блоки {BWj„} размером 8x8, т,п=0,8,16. Если какой-либо блок видеопоследовательности оказался в определенном смысле «похож» на оригинальный блок В'тп, считаем, что блок В1т>п - это перемещенный фрагмент B^J предыдущего кадра, и для кодирования (т,п)блока изображения достаточно задать координаты блока в предыдущем кадре, у их, либо изменения координат у-т и х-п. Частным случаем перемещенного блока является неподвижный блок, когда т=у, л=х Если блоку В'тп нельзя найти похожий в предыдущем кадре, блок должен кодироваться как новый. Такой идеологии следуют современные международные стандарты видеокомпрессии MPEG [105], Н.261-Н263 [169,130,170], причем все они опираются также на использование ДКП для кодирования новых блоков.

Разработка нового алгоритма видеокомпрессии проводилась в рамках общего подхода к RD-оптимизации сжатия с потерями. В разработанном алгоритме для выбора способа кодирования очередного обрабатываемого блока В1т п руководствуемся критерием минимума функции Лагранжа для блока: J(b)-D(b)+?iR(b). Положим, что аргумент Ъ=0 соответствует кодированию перемещенного (неподвижного) блока, а ¿=1 - нового. Тогда если J(l)>/(0), то блок кодируется как перемещенный, и как новый - в противном случае.

При использовании RD-оптимизации задача поиска перемещенных блоков формулируется следующим образом [166]. Для заданного (т, я)-блока В1т п ¿-ого кадра найти в предыдущем восстановленном кадре такой (у,х)-блок л ., чтобы минимальное значение принимала RD-функция Лагранжа

Щу-т,х-п)= mintein-B^ +AK(w-m,v-n)l (0.10) tt,v)e£2 и ' '

J =

А • 1

В —В т,п у,х

Здесь учтено, что координаты найденного блока будут кодироваться как относительные, т.е. вектором перемещений г={у-т,х-п).) Гарантированно найти минимум (0.10) возможно лишь при полном переборе элементов (и,у)е£1, а для того, чтобы алгоритм поиска можно было реализовать в реальном масштабе времени, в качестве области О необходимо рассматривать лишь точки (у, и), достаточно близко расположенные к точке (т,п). Повышение эффективности поиска за счет расширения области С2 достигается применением различных алгоритмов направленного поиска [96,99,136,141,156], ориентированных на минимизацию ошибки представления перемещенного блока ||в'га>п , что соответствует частному случаю (0.11) при Я=0. Алгоритмы направленного поиска находят минимум (0.11) приближенно, однако за счет существенного расширения области поиска обычно позволяют найти большее количество перемещенных блоков, при аналогичной полному перебору сложности.

В шестой главе предложен новый алгоритм направленного поиска перемещенного блока [25,166], ориентированный на приближенное решение задачи (0.10) уже для произвольного значения X. Отличительной особенностью предложенного алгоритма является также то, что малые перемещения блоков изображения ищутся более точно [55], т.к. должны строго отслеживаться в силу специфики визуального восприятия. Для повышения эффективности полученного в главе 6 алгоритма поиска для вектора перемещения (А ,АХ) обрабатываемого блока следует строить прогноз по векторам перемещения (д^Л^) и (д*Д) двух уже обработанных «соседей» (соответственно соседа по вертикали и соседа по горизонтали). Собственно прогноз — это относительные координаты (у0,*0), которые определяют перенос центра области поиска: из точки (т,п) в точку (ш,п)={т + у0,п + х°). Экспериментально подтверждено, что число новых блоков изображения сокращается на 5.25%, если принять следующее правило составления прогноза [25,55,60]:

0,0), оба соседних блока - новые

Д^Д^), по горизонтали- новый, по вертикали- перемещенный (Ану,Акх), по горизонтали - перемещенный, по вертикали - новый ((д; ,ДУХ)+(ДА,, ДАХ ),)/2, оба соседа - перемещенные блоки

Следуя идеологии стандарта MPEG, в разработанной схеме компрессии обработка новых блоков также осуществляется при помощи квантования с последующим статистическим кодированием коэффициентов двумерного ДКП. Результат ДКП блока Вот>и обозначим S, S=F(BW>„). Также обозначим: Se=fe;/=round(5M/^i;)}^=0, Q = кД/=0 - одна из матриц квантования JPEG. Для статистического кодирования матрицы S применен алгоритм контекстного кодирования, предложенный в главе 4, в который введен дополнительный этап RD-оптимизации. Пусть ZQ =(z0,.,z63)

- вектор, полученный в результате зигзагообразного считывания данных из матрицы SQ по правилу, определяемому стандартом JPEG (S0 <->ZQ). RDоптимизация статистического кодирования возможна за счет удлинения нулевых серий компонент в векторе ZQ путем их дополнительного обнуления [111]. Для того, чтобы в результате не произошло заметного усложнения алгоритма кодирования, в оптимизированном варианте алгоритма контекстного кодирования ДКП-коэффициентов анализируется лишь возможность увеличения финальной нулевой серии, что дает наибольший вклад в дополнительную минимизацию функции J(Zq)=D(Zq)+ÀR(Zq). При этом считается, что матрица Q, определяющая квантование коэффициентов ДКП, задана. Универсальный алгоритм кодирования должен оперировать некоторым набором матриц квантования {Q/}, с возможностью выбора необходимой матрицы для конкретных требований к качеству и уровню сжатия. Если набор матриц достаточно большой, то подбор матрицы квантования Q по принципу минимума функции J(Zq) превращается в громоздкую процедуру, нереализуемую в реальном масштабе времени стандартными средствами. Кроме того, при большом диапазоне возможных значений индекса j его кодирование для каждого нового блока по отдельности влечет недопустимо высокие дополнительные битовые затраты. Поэтому в качестве исходного набора были выбраны лишь несколько матриц из множества, рекомендуемого JPEG, которые соответствуют наилучшему, наихудшему и некоторым промежуточным уровням качества. В экспериментах использовалось число матриц |{Q/}|=4. Для ускорения выполнения операций деления, которые необходимы при квантовании, элементы матриц {Q,} были округлены до ближайшего значения 2к, k=G,\,. Такой подход позволяет заменить операции целочисленного деления и умножения сдвигами разрядов двоичного представления чисел, которые обычно выполняются реальной аппаратурой намного быстрее.

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

При исследовании характеристик итогового алгоритма видеокомпрессии для оценки величины ошибки кодирования в восстановленной последовательности В0,В1,.,ВЛ:~1 использовалась отношение пикового значения сигнала к шуму, которое определялось следующим образом:

PSNR = 101g ¿III

X W -B* 2

ДБ], где Mi и M2 задают размер кадра в пикселях. Для экспериментов были выбраны широко известные тестовые последовательности News, Container ship, Hall monitor, Akiyo, Claire. Результаты численных экспериментов, полученные аспирантом Ф.В.Стрелковым [166], показали, что во всех тестах предложенная схема компрессии дает высокие результаты, превосходя характеристики кодера MPEG-2, разработанного группой MSSG (mpeg2encode, версия 1.1, см. http://www.mpeg.org/MSSG). Программное сжатие видеопоследовательностей при этом осуществляется в реальном масштабе времени.

Итог исследованиям, проведенным в диссертационной работе, подводится в заключительном разделе - «Основные выводы и заключение».

На защиту диссертации выносятся следующие основные результаты:

• Метод оценки декоррелирующей эффективности ортогональных преобразований и основанные на нем алгоритмы кластеризации коррелированных данных;

• ДПКП и быстрый алгоритм его вычисления;

• Новый быстрый алгоритм ДПКЛ и его модификация - алгоритм с неполным вычислением; алгоритм совмещенных вычислений ДПКЛ для обработки вещественных массивов в базисе (1,ехр(-2то/3));

• Метод компрессии изображений, основанный на специальном способе арифметического кодирования спектров ДПКЛ блоков изображения;

• Детерминированные и вероятностные оценки коэффициентов ДКП;

• Алгоритм контекстного кодирования спектров ДКП изображений;

• Общая схема компрессии изображений на основе адаптивного векторного квантования в области ортогональных преобразований;

• Алгоритмы вейвлет-компрессии статических изображений;

• Алгоритм поиска перемещенных блоков изображения;

• Экспериментальная методика построения разбиения спектров на области независимого кодирования;

• Алгоритм видеокомпрессии.

Основные результаты, изложенные в диссертации, опубликованы в 30 работах [13-17,19,20,53-56,59-61,63,65,66,69-71,73,74,76-79,25,48,165,166]. Все приводимые в диссертации теоретические результаты из 11 написанных в соавторстве работ [13-17,77-79,25,48,166] получены лично автором. В тех случаях, когда приводимые экспериментальные численные данные (таблицы, графики) из совместных работ были получены соавторами [25,31,48,77-79,166], на это явно указано по ходу изложения при цитировании результатов.

Предложенный в шестой главе алгоритм видеокомпрессии был реализован программно в рамках работ, проводившихся в ГУ НПК «Технологический Центр» Московского государственного института электронной техники и в НПП «Технология» [25,48]. Внедрение разработанных библиотек видеокомпрессии осуществлено в ряде программных систем, производящих обработку видеоизображений (в том числе, кодирование) в реальном масштабе времени, среди которых наибольший практический интерес представляет система видео контроля и регистрации Visual Security (см. http://www.tcen.ru/vs). Копии документов об использовании и внедрении результатов диссертационной работы имеются в приложении 6.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Умняшкин, Сергей Владимирович

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

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

По результатам проведенных в диссертационной работе исследований можно сделать следующие выводы.

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

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

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

4. При использовании статистического кодирования коэффициентов ДКП по методу JPEG наличие «скачков» дискретного сигнала наименее желательно в центральной области фрагментов обработки.

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

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

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

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

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

Выработанные подходы и рекомендации привели к построению конкретных схем и алгоритмов компрессии, многие из которых были реализованы программно и экспериментально подтвердили эффективность своего применения. Результаты исследований по видеокомпрессии, которые проводились в рамках возглавлявшихся автором НИР [25,48] и финансировались Министерством науки и промышленности РФ, внедрены в виде алгоритмов в программно-аппаратной системе Visual Security (см. приложение №6).

Список литературы диссертационного исследования доктор физико-математических наук Умняшкин, Сергей Владимирович, 2001 год

1. Абстрактные алгебраические системы и цифровая обработка сигналов / Вариченко Л.В., Лабунец В.Г., Раков М.А. Киев: Наукова думка, 1986. -248 с.

2. Алексеев А.Г. Кластеризация коррелированного набора данных // «Микроэлектроника и информатика 99». VI всерос. межвуз. н.-т. конф. ст. и асп.: Тез. док. - М.: МИЭТ, 1999. - С.133.

3. Ахмед Н., Pao К. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. М.: Связь, 1980. - 248 с.

4. Ватолин Д. С. Гибридная схема фрактальной компрессии и квантования векторов для малых блоков // Труды международной конференции Graphicon-98. Москва, 1998, стр. 205-212.

5. Виленкин Н.Я. Об одном классе полных ортогональных систем // Изв. АН СССР. Сер. мат. 1947. - Т.П. - С. 363-400.

6. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. -С.-Пб.: Изд-во воен. ун-та связи, 1999. 204 с.

7. Гашников М. В., Глумов Н. К, Сергеев В. В. Информационная технология компрессии изображений в системах оперативного дистанционного зондирования // Изв Самарского центра РАН. 1999. — № 1. — С. 99-107.

8. Голд Б., Рейдер Ч. Цифровая обработка сигналов: Пер. с англ. М.: Сов. радио, 1973. - 368 с.

9. Голубое Б.И., Ефимов A.B., Скворцов В. А. Ряды и преобразования Уолша: Теория и применения. М.: Наука, 1987. - 344 с.

10. Горлов С.К., Корыстин A.B., Родин В.А. Об одной реализации метода сжатия отображений с помощью нелинейной аппроксимации сумм Фурье-Хаара// Теор. функций и прибл.: Тр. 7-й Саратов, зим. шк. (1994 г.). Ч. 2.-Саратов: Изд.-во СГУ, 1995.

11. Дмитриев В.И. Прикладная теория информации: Учеб. для студ. вузов. -М.: Высш. шк., 1989. 320 с.

12. Ефимов A.B., Поспелов A.C., Умняшкин C.B. Некоторые свойства мультипликативных ортонормированных систем, используемые в цифровой обработке сигналов // Труды математического института им. В.А.Стеклова РАН. Т.219. - 1997. - С 137-182.

13. Ефимов A.B., Умняшкин C.B. Быстрые алгоритмы вычисления дискретного преобразования Крестенсона-Леви и оценки его спектральных. характеристик// Теор. функций и прибл.: Тр. 7-й Саратов, зим. шк. (1994 г.). Ч. 2.- Саратов: Изд.-во СГУ, 1995. С. 9-20.

14. Жуков В.Г. Исследование методов сравнения перемещенных блоков изображений в алгоритмах сжатия видеопоследовательностей. //Микроэлектроника и информатика-99. Всерос. межвуз. н.-т. конф. студентов и аспирантов: Тезисы докладов. М.:МЙЭТ,1999. - С. 137.

15. Жуков ДМ. Эквивалентность одномерного и двумерного преобразования Крестенсона-Леви // Методы цифровой обработки изображений: Сб. науч. тр. МИЭТ. М.: МИЭТ, 1982 - С. 65-70.

16. Задирака В.К., Евтушенко В.Н. Оптимальный способ зонного кодирования с использованием Слэнт-преобразования // Кибернетика и системный анализ. 1994. - №4. - с. 56-60.

17. Исследование и разработка алгоритмов программного сжатия данных с потерями для цифровой обработки видеоизображений: Отчет о НИР (закл.) / HI 111 «Технология»; рук. -Умняшкин C.B. «Дозор»; № гос. per. 01200004624; Инв. №100704. - Москва, 2000. - 48 с.

18. Кендэл М. Ранговые корреляции. М.: Статистика, 1975. - 216 с.

19. Коваленко КН., Филиппова А.А. Теория вероятностей и математическая статистика. М.: Высш. школа, 1982. - 256 с.

20. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров: Пер. с англ. М.: Наука, 1970. - 720 с.

21. Кочетков М.Е. Компрессия цифровых изображений с использованием векторного квантования в области дискретных ортогональных преобразований: Дисс. канд. техн. наук. М., 1999. -191 с.

22. Кочетков М.Е., Умняшкин C.B. Многопотоковая реализация алгоритма арифметического кодирования / М.: МГИЭТ (ТУ), 1998. 21 с. Депонировано в ВИНИТИ 25.12.98 № 3884-В98.

23. Кочетков М.Е., Умняшкин C.B. О сравнении критериев для оценки эффективности декоррелирующих преобразований / М.: МГИЭТ (ТУ), 1998. 34 с. - Деп. в ВИНИТИ 13.04.98, № 1069-В98.

24. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации: Учеб. пособие. — М.: Изд-во МАИ, 1998. 344 с.

25. Лисовец Ю.П., Поспелов А. С. Мультипликативные голографические преобразования для обработки изображений // Методы цифровой обработки изображений: Сб. науч. тр. М.: МИЭТ, 1982 - С. 100-109.

26. Литош И.П. Объединение алгоритмов фрактальной и вейвлет-компрессии цифровых изображений// «Микроэлектроника и информатика -2001». У1П всерос. межвуз. н.-т. конф. ст. и асп.: Тез. док. -М.:МИЭТ, 2001. -С.147.

27. Марков А.А. Сжатие цифровых изображений с использованием \vavelet-преобразований // «Микроэлектроника и информатика 2000». VII всерос. межвуз. н.-т. конф. ст. и асп.: Тез. док. -М.:МИЭТ, 2000. -С. 114.

28. Мудрое А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. — Томск: МП «РАСКО», 1991. -272с.

29. Новиков И.Я., Стечкин С.Б., Основные конструкции всплесков // Фундаментальная и прикладная математика. 1997. - Том 3. - №4. -С.999-1028.

30. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. М.: Радио и связь, 1985. - 248 с.

31. Пеев Е., Боянов К, Белчева О. Методи и средства за компрессия на изображения // Автоматика и информатика.-1994.-28, №3.-стр.3-14.

32. Петухов А.П. Введение в теорию базисов всплесков. СПб.: Изд-во СПбГТУ, 1999. 132 с.

33. Поспелов А. С. Методы обработки цифровой видеоинформации с использованием преобразований голографического типа// Сб. тр. междунар. совещ. по програмир. и мат. методам решения физ. задач (Дубна, 14-19 июня 1993). Сообщение ОИЯИР11-94-100. - С, 71-73.

34. Поспелов А. С. Некоторые математические задачи и алгоритмы цифровой обработки информации с использованием дискретных преобразований: Дисс. на соиск. уч. степ, д-ра физ.-мат. наук. М., 1992. -398 с.

35. Применения цифровой обработки сигналов: Пер. с англ. / Под ред. Э.Оппенгейма. М: Мир, 1980. - 552 с.

36. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир, 1982. -Кн.1 и 2.-312 и 480 с.

37. Прэтт У, Кэш Д., Эндрюс X. Кодирование изображений посредством преобразования Адамара // ТИИЭР. 1969. - Т.57. - №1. - С. 66-77.

38. Птачек М. Цифровое телевидение. Теория и техника / Пер. с чешек, под ред. Л.С.Виленчика. М.: Радио и связь, 1990. -528 с.

39. Розанов Ю.А. Случайные процессы. М.: Наука, 1971. - 288 с.

40. Свешников A.A. Прикладные методы теории случайных функций. М. : Наука, 1968.-463 с.

41. Трахтман В.А. Спектральный анализ в базисе функций Виленкина-Крестенсона//Радиотехника и электроника. -1975. -Т. 20. -№1. -С.130-138.

42. Трахтман A.M., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. М.: Сов. Радио, 1975.

43. Умняшкин C.B. Алгоритм кластеризации коррелированных данных // VII Международная конференция. Математика. Экономика. Экология.

44. Образование. Международный симпозиум. Ряды Фурье и их приложения: Тезисы докладов. Ростов: Рост. гос. эконом, акад., 1999. - С. 211-212.

45. Умняшкин C.B. Алгоритм поиска перемещенных блоков для кодирования цифровых видеоизображений // Межотраслевой научно-технический журнал «Оборонный комплекс научно-техническому прогрессу России», №3,2001.-С. 38-41.

46. Умняшкин С. В. Алгоритм фрактального кодирования изображений в области вейвлет-преобразований // Компьютерна математика. Оптажзащя обчислень: Зб1рник наукових праць. Том 1. — Кшв: 1нститут шбсрнетики ím. В.М.Глушкова, 2001. - С. 385-391.

47. Умняшкин C.B. Быстрые алгоритмы вычисления дискретного мультипликативного преобразования / М.: МГИЭТ (ТУ), 1995. 15 с. - Деп. в ВИНИТИ 16.02.95, № 442-В95.

48. Умняшкин C.B. Быстрый алгоритм вычисления дискретного преобразования Крестенсона-Леви для обработки вещественных массивов / М.: МГИЭТ (ТУ), 1995. 19 с. - Деп. в ВИНИТИ 05.12.95, № 3212-В95.

49. Умняшкин С. В. Использование контекстного арифметического кодирования для повышения сжатия данных по схеме JPECj // Известия вузов. Электроника. №3. - 2001. - С. 96-98.

50. Умняшкин C.B. Компенсация перемещения объектов при сжатии видеоданных // «Электроника и информатика XXI век» Третья международная научно-техническая конференция: Тез. док. - М.: МИЭТ, 2000.-С. 365-366.

51. Умняшкин С. В. Вейвлет-компрессия цифровых изображений с прогнозированием статистических моделей //Известия вузов. Электроника. №5. - 2001. - С.86-94.

52. Умняшкин C.B. Метод кодирования дискретных изображений на основе преобразования Крестенсона-Леви // Микроэлектроника и информатика -96: Тез. докл. межвуз. науч.-тех. конф. М.: МГИЭТ (ТУ), 1996. - С.167.

53. Умняшкин C.B. О кластеризации коррелированных данных. // Информационные технологии в инновационных проектах. Международная конференция (г.Ижевск, 20-22 апреля 1999г.): Материалы докладов. -Ижевск, ИжГТУ, 1999. С. 59-65.

54. Умняшкин C.B. О квантовании элементов спектра дискретного преобразования Крестенсона-Леви/ М.: МГИЭТ (ТУ), 1995. 12 с. - Деп. в ВИНИТИ 16.02.95, № 441-В95.

55. Умняшкин C.B. О модификации дискретного косинусного преобразования // Теория приближений и гармонический анализ: Тез. докл. междунар. конф. (Тула, 26-29 мая 1998 г.). Тула: ТулГУ, 1998. - С.264-265.

56. Умняшкин C.B. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998. Т. 4. Вып. 1. С. 143-147.

57. Умняшкин C.B. Об оценке декоррелирующих свойств дискретных преобразований // Микроэлектроника и информатика 97: Тезисы докл. межвузовской научно-технической конференции. Часть 2. - М. МГИЭТ (ТУ), 1997.-С. 110:

58. Умняшкин C.B. Особенности использования дискретного преобразования Крестенсона-Леви при обработке вещественных массивов // Микроэлектроника и информатика: Тез. докл. межвуз. науч.-тех. конф. 1214 апр. 1995 г. М.: МГИЭТ (ТУ), 1995. - С. 188-189.

59. Умняшкин C.B. Оценка эффективности использования унитарных преобразований для кодирования дискретных сигналов //Информатика и связь: Сб. научн. тр. под ред. В.А.Бархоткина. М.: МИЭТ.- 1997. С.73-78.

60. Умняшкин C.B. Применение дискретного преобразования Крестенсона-Леви в цифровой обработке изображений. Дис. канд. техн. наук. -Москва, 1997. - 198 с.

61. Умняшкин C.B. Псевдокосинусное преобразование для сжатия дискретных сигналов // Информационные технологии и проблемы микроэлектроники. Сб. науч. тр. -М.: МИЭТ. -1999. С.158-170.

62. Умняшкин С. В. Схема RD-оптимизированной компрессии для обработки видеоданных в реальном масштабе времени// Принято к публикации в журнал «Известия вузов. Электроника». №6. - 2001.

63. Умняшкин C.B. Цифровая компрессия изображений с использованием дискретного преобразования Крестенсона-Леви // Межотраслевой научнотехнический журнал «Оборонный комплекс — научно-техническому прогрессу России», №2,2000. С.28-39.

64. Умняшкин C.B., Космач М.В. Оптимизация кодирования цифровых изображений по методу JPEG //Известия вузов. Электроника. №4-5. -2000. - С. 139-141.

65. Умняшкин C.B., Кочетков М.Е. Анализ эффективности использования дискретных ортогональных преобразований для цифрового кодирования коррелированных данных // Известия вузов. Электроника. №6. - 1998. - С. 79-84.

66. Умняшкин C.B., Стрелков Ф.В., Жуков В.Г. Трехшаговые алгоритмы поиска перемещенных блоков изображения // Информационные технологии и системы управления. Сб. научн. тр. под ред. В.А.Бархоткина.- М: МИЭТ, 2000. С. 47-55.

67. Хармут X. Теория секвентного анализа. Основы и применения: Пер. с англ.- М.: Мир, 1980. 574 с.

68. Цифровая обработка телевизионных и компьютерных изображений / Под ред. Ю.Б.Зубарева и В.ПДворковича. М.: Международный Центр научной и технической информации, 1997. - 212 с.

69. Чен Ш.-К. Принципы проектирования систем визуальной информации. -М.: Мир, 1994. 408 с.

70. Эндрюс Г. Применение вычислительных машин для обработки изображений / Пер. с англ. под ред. Б.Ф.Курьянова. М.: Энергия. - 1977. -161 с.

71. Яворский Б.М., Детлаф А.А. Справочник по физике для инженеров и студентов вузов.-Издание 7-е, исправленное.-М.:Наука, 1977.-944 с.

72. Ярославский JI.II. Введение в цифровую обработку изображений. М.: Сов. радио, 1979.-312 с.

73. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику. М.: Радио и связь. - 1987. -296 с.

74. Ahmed N., Natarajan Т., Rao K.R. On image processing and a discrete cosine transform // IEEE Trans. Computers. -1974. V. C-23 - №1. - P.90-93.

75. Allen J.B. andRabiner L. R. A unified approach to short-time Fourier analysis, synthesis//Proc. IEEE 1977.-Vol. 65. -№ Ию-Р. 1558-1564.

76. Anderson J.В., Huang T.S. Piecewise Fourier transformation for picture bandwidth compression // IEEE Trans. Commun. -1972.- V. COM-20 №3. -P.488-491.

77. Andrews H. C., Hunt B.R. Digital Image Restoration.- Englewood Cliffs (NJ): Prentice Hall, 1977. XVIII, 238 p.

78. Andrews H. C., Pratt W.K. Fourier transform coding of images // Hawaii International Conference on System Science, January 1968. P. 677-679.

79. Andrews H.C., Pratt W.K. Transform image coding // Proc. Computer processing in communications. New York: Polytechnic Press, 1969. -P. 63-84.

80. Antonini M., BarlaudM., Mathieu P., andDaubechies I., Image coding using wavelet transform// IEEE Trans. Image Proc. Vol. 1. - №2, 1992. -P. 205-220.

81. Barnsley F., Jacquin A. Application of recurrent iterated function systems to images//Proc. SPIE.- 1988.-Vol. 1001.-P. 122-131.

82. Berger T. Rate Distortion Theory. Endlewood Cliffs, NJ: Prentice Hall, 1971.

83. Bierling M. Displacement estimation by hierarchical block-matching // Proc. SPIE Conf. On Vis. Commun. And Image Proc. Cambrige, 1988. - P. 942-951.

84. Bilgin A., Sementilli.P. and Marcellin M. Progressive image coding using trellis quantization // IEEE Trans. Image Proc. 1999.-V.8.-№11.-P. 1638-1643.

85. Chernov V.M., Dmitriyev A. G. Image Compression Using Discrete Orthogonal Transforms with the «noise-like» Basis Functions // Компьютерная оптика. 1999. - Вып. 19. - С. 184-187.

86. Cheung С.К., Ро L.M. A hybrid adaptive search algorithm for fast block motion estimation // Proc. IEEE International Symp. on Signal Proc. and its App. (Aug.1996). Vol.1. 1996 - P.365-368.

87. Chrestenson H.E. A class of generalized Walsh functions // Pacific. J. Math. -1955.-V.5.-№l.-P. 17-32.

88. Chrysafis C. Wavelet image compression rate distortion optimizations and complexity reductions: PhD (Electrical Engineering) Thesis. University of Southern California, Los Angeles, 2000. - 144 pages.

89. Chrysafis C., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet Image Compression // Proc. Data Compression Conference. -Snowbird (Utah), 1997. P. 241-250.

90. С ho N., Lee S. Fast algorithm and implementation of 2-D discrete cosine transform // IEEE Trans. Circuits and Systems. 1991. -V.38. - P.297-305.

91. ChouP.A., Lookabaugh Т., GrayR.M. Entropy-constrained vector-quantization 11 IEEE Trans. ASSP. 1989. - Vol. 37. -№1. -P.31-42.

92. Coding of moving pictures and audio (MPEG-4). Standard ISO/IEC 14496: 1999.

93. Cohen A., Daubechies I., FeauveauJ.-C., Biorthogonal bases of compactly supported wavelets // Comm. Pure Appl. Math. 1992. - V. 45. - №5. - P. 485560.

94. Coifman R., and Wickerhauser M. V., Entropy-based Algorithms for Best Basis Selection // IEEE Trans. Information Theory. 1992. - Vol. 38. - №2 - P. 713718.

95. Cooley J. W., Tukey J.W. An algorithm for machine computation of complex Fourier series // Mach. Comput. 1965. - V. 19. - P. 297-301.

96. Cosman P.C., GrayRM., and VetterliM. Vector Quantization of Image Subbands: A survey // IEEE Trans. Image Proc. 1996. - V. 5. - №5. - P. 202225.

97. Costantini R. et al. A Low-Complexity Video Coder Based on the Discrete Walsh Hadamard Transform //Proc. European Signal Processing Conference 2000 (Tampere, Finland, September 5-8). -2000. -P.1217-1221.

98. Crouse M. and Ramchandran K. Joint thresholding and quantizer selection for transform image-coding: entropy-constrained analysis and applications to baseline JPEG // IEEE Trans, on Image Processing. 1997. - Vol. 6. -№2 - P. 285-297.

99. Davis G.M., A wavelet-based analysis of fractal image compression // IEEE Trans. Image Proc. 1998. - V.7-№2. -P.141-154.

100. Davis G., Nosratinia A. Wavelet-based Image Coding: An Overview // Applied and Computational Control, Signals and Circuits. -1998. -V.l. -№1. -P. 205269.

101. Deever A. and Hemami S. What's your sign?: Efficient sign coding for embedded wavelet image coding 11 Proc. of Data Compression Conference, 2000.-P. 273-282.

102. Duhamel P., Guillemont C. Polynomial transform computation of 2-D DCT // Proc. ASSP'90. 1990. - P.1515-1518.

103. EfimovA. V. Multiplicative function systems and their applications in discrete information processing // Approximation and function spaces/ Banach center publications (Warsaw). 1989. - V.22. - P. 111-117.

104. Eflmov V.M., Kolesnikov A.N. Image compression with preliminary interpolation of the signal // Pattern Recognition and Image Analysis. 1996. — Vol. 6. - №1.

105. EliottD.F., Rao K.R. Fast transforms: algorithms, analyses, applications. -London: Academic Press inc., 1982. 488 p.

106. Enomoto II, Shibata K. Orthogonal transform coding system for television signals // IEEE Trans. Electromagnetic Compatibility. 1971. - Special issue on Walsh functions. -V. EMC-13. - №3. - P. 11-17.

107. Feig E. A fast scaled DCT algorithm // Proc. SPIE Int. Soc. Opt. Eng. 1990. -Vol. 1244.-P. 2-13.

108. Fischer T.R., and WangM. Entropy-constrained trellis coded quantization// IEEE Trans. Inf. Theory. 1992. - Vol. 38 - №2 - P. 415-426.

109. Fisher Y. Fractal Compression: Theory and Application to Digital Images. -New York: Spinger Verlag, 1994. 341 p.

110. Good J. The interaction algorithm and practical Fourier analysis // J. Royal Stat. Soc. (London). 1958. - V. B-20. - P. 361-372.

111. Gray R.M. Vector Quantization //IEEE ASSP Magazine. -Apr. 1984. -P.4-29

112. Gray R„ Neuhoff D. Quantization //IEEE Trans. Inf. Theory. Oct. 1998. - Vol. 44.-No. 6.-P. 2325-2383.

113. HabibiA., WintzP.A. Image coding by linear transformation and block quantization//IEEE Trans. Comm. Tech. -1971. -V. COM-19. №1. -P.50-63.

114. Hamidi M., Pearl J. Comparison of the cosine and Fourier transforms of Markov-I signals 11 IEEE Trans. ASSP. V.24. - 1976. - P.428-429.

115. Hauque M.A. A two-dimensional fast cosine transform // IEEE Trans. ASSP. -1985. V. 33. - №6. - P.1532-1538.

116. Huang J. Y., Schultheiss. Block quantization of correlated Gaussian random variables// IEEE Trans. Commumications. -1963. -V. CS-11 (Sept.) -P. 289296.

117. Information technology Generic coding of moving pictures and associated audio information: Video. //Recommendation ITU-T H.262. - Standard ISO/IEC 13818-2-2000.

118. ISO/IEC JTC1 Committee Draft 10918-1. Digital compression and coding of continuous-tone still images. Part 1. Requirements and guidelines. -1991.

119. ISO/IEC JTC1 Committee Draft 10918-2. Digital compression and coding of continuous-tone still images. Part 2. Compliance Testing. 1991.

120. Jacquin A. Fractal image coding based on a theory of iterated contractive image transformations // Proc. SPIE Visual Comm. And Image Proc. 1990. - P.227-239.

121. Jacquin A. Image coding based on a fractal theory of iterated contractive image transformations // IEEE Trans. Image Proc. 1992. - Vol.1. - №1. -P. 18-30.

122. Jafarkhani H., Farvardin N., and Lee C.-C., Adaptive image coding based on the discrete wavelet transform 11 Proc. IEEE Int. Conf. Image Proc. Vol. 3 -Austin (TX), 1994. - P. 343-347.

123. Jain J.R. and Jain A.K. Displacement measurement and its application in interframe image coding // IEEE Trans. Comm. 1981. - Vol. 29. - №12. -P.1799-1806.

124. JoshiR.L., Fischer T.R., and Bamberger R.H. Optimum classification in subband coding of images // Proc. IEEE Int. Conf. Image Proc. Vol. 2 - Austin (TX), 1994.-P. 883-887.

125. Joshi R.L. et al., Comparison of different methods of classification in subband coding of images// IEEE Trans. Image Processing. 1997. - Vol. 6. - Nov. - P. 1473-1486,1997.

126. JPEG2000. Part 1. Final Committee Draft Version 1.0. ISO/IEC JTC1/SC29 WG1.-205 pages.

127. Kasner J.H., Marcellin M. W. Adaptive wavelet coding of images // Proc. IEEE Int. Conf. Image Proc. Vol. 3 - Austin (TX), 1994. - P. 358-362.

128. Koga T. et al, Motion compensated interframe coding for video conferencing // Proceedings of the National Telecommunications Conference, New Orleans, Louisiana, Nov. 29 Dec. 3. - 1981. - Vol. 4. - P. G5.3.1-G5.3.5.

129. Kossentini F., Chung W.C., and Smith M. J. T. Rate-Distortion-Constrained Subband Video Coding. // IEEE Transactions on Image Processing. -1999. -Vol. 8.-№2.-P. 145-154.

130. Kurosaki M., WakiH. A JPEG-compliant colorimage compression/decompression LSI // Mitshubisi Elec. Adv. -1994. -V.68, Sept. -P.17-18.

131. Levy P. Sur une generalization des fonctions orthogonales de M.Rademacher II Comment, math. helv. 1944. - V.16. - P. 146-152.

132. Lewis A.S., Knowles G. Image Compression Using the 2-D Wavelet Transform . II IEEE Trans. Image Proc. 1992. - Vol. 1. - №2. - P.244-250.

133. Linde Y., Buzo A., Gray R.M. An algorithm for vector quantizer design // IEEE Trans. On Comm. — 1980. — V.28. №1. - P.8^95.

134. LoPresto S.M., Ramchandran K., OrchardM.T. Image Coding based on Mixture Modeling of Wavelet Coefficients and Fast Estimation-Quantization Framework // Proc. Data Compression Conference. Snowbird (Utah), 1997. - P. 221-230.

135. MallatS., Multiresolution approximation and wavelet orthonormal bases of L2(R) // Trans. AMS. 1989. - V.315. -P.69-87.

136. Marcellin M. et ail. An Overview of JPEG-2000 // Proc. Data Compression Conference, J. A. Storer andM. Cohn, eds. Snowbird, Utah, Mar. 28-Mar. 30, 2000. Snowbird, 2000. - P. 523-541.

137. MarchallX. Motion estimation and compensation for very low bitrate video coding: Docteur of Sciences Appliquées. Université Catholique de Louvalin. -Louvalin-la-Neuve, 1998. - 228 pages.

138. Nasrabadi N.M., King R.A. Image coding using vector quantization: A review // IEEE Trans, on Communication. 1988. - V. 36. -No.8. - P. 957-971.

139. Nelson M., Gailly J A. The Data Compression Book (Second Edition). New York: M&T Books, 1995. - 541 p.

140. Pearl J. On coding and filtering stationary signals by discrete Fourier transforms // IEEE Trans. Inf. Theory. 1973. - Vol. IT-19. - P. 229-232.

141. Pratt W.K, Andrews H.C. Application of Fourier-Hadamard transformation to bandwidth compression // Picture bandwidth compression / Ed.: Huang T.S., Tretiak O.J. New York: Gordong and Breach, 1972. - P. 515-554.

142. Pratt W.K, Chen W.H., Welch L.R. Slant transform image coding // IEEE Trans. Commun. -1974. -V. COM-22. P.1075-1093.

143. Queluz M.P., Motion estimation for video coding: a review // HF Magazine -December 1995. Special Issue on Video Coding. - No. 4. - pp. 5-28.

144. Ramachandran K, Vetteri M. Best wavelet packet bases in a rate-distortion sense // IEEE Trans. Image Proc. 1993. -V.2. -№2. - P. 160-175.

145. Rao K.R., Narasimhan M.A., Reviduri K. Image data processing by Hadamard-Haar transform// IEEE Trans. Computers. 1975. - V. C-23. - №9. - P. 888-896.

146. Rao K.R., Yip P. Discrete cosine transform algorithms, advantages, applications. - London: Academic Press inc., 1990.

147. Roska T., Boros T., Radvânyi A., Thiran P. and ChuaL.O. Detecting Moving and Standing Objects Using Cellular Neural. Networks // International Journal of Circuit Theory and Applications. Vol. 20. - 1992. - P.613-628.

148. Said A. and Pearlman W.A. A new fast and efficient image codec based on set partitioning in hierarchical trees // IEEE Trans, on Circuits and Systems for Video Technology. 1996. - Vol. 6. - №3, June. - P. 243-250.

149. Shapiro J.M. Embedded image coding using zerotrees of wavelet coefficients 11 IEEE Trans. Signal Processing, vol. 41, pp. 3445-3462, Dec 1993.

150. Stefanoiu D. Introduction to signal processing with wavelets // Studies on Information and Control. -1994. V.3. - №1. - P. 97-110.

151. Storer J. A. Data compression: Methods and theory. Rockville (Md): Computer science press, 1988. - X, 413 p.

152. Umnyashkin S. V. Image compression based on mixed predictive modeling of wavelet trees // Reports from Vaxjo University (Sweden) Mathematics, natural sciences and technology. - Nr. 11 (September), 2001. - 18 pages

153. Umnyashkin S. V., Strelkov F. V. An RD-optimized scheme for real-time video compression // Reports from Vaxjo University (Sweden) Mathematics, natural sciences and technology. - Nr. 12 (September), 2001. - 15 pages.

154. Van de Walle A., Merging fractal image compression and wavelet transform methods 11 Fractals. 1997. - vol. 5 (Supplementary Issue), April. - P.3-15.

155. Vetterly M., Herley C., Wavelets and Filter Banks: Theory and Design // IEEE Trans. Signal Proc. 1992. - V.40. - №9. - P.2207-2232.

156. Video codec for audiovisual services at p x 64 kbit/s. //Recommendation ITU-T H.261. -1993.

157. Video coding for low bit rate communication //Recommendation ITU-T H.263. Standard ISO/IEC 13818-2: 1998.

158. Wallace G.K. The JPEG algorithm for image compression standard // Communications of the ACM. 1991. -V.34. -№4. - P. 30-44.356

159. WeiD., PaiH.-T., andBovikA. C., Antisymmetric Biorthogonal Coiflets for Image Coding // Proceedings of IEEE International Conference on Image Processing. Chicago, 1998. - Vol. 2. - P. 282-286.

160. Witten I., Neal R.M., Cleary J. G. Arithmetic coding for data compression // Comm. ACM. 1987. - Vol.30. - №6. - P. 520-540.

161. Woods J. W., Huang T.S. Picture bandwidth compression by linear transformation and block quantization // Picture bandwidth compression / Ed.: Huang T.S., Tretiak O.J. -New York: Gordong and Breach, 1972. P.555-573.

162. Xiong Z., Ramchandran K. and OrchardM.T. Space-frequency Quantization for Wavelet Image Coding // IEEE Trans. Image Proc. V.6 - May 1997, P. 677693.

163. Xiong Z., Ramchandran K., and Orchard M. Wavelet packets image coding using space-frequency quantization // IEEE Trans. Image Proc. 1998. - Vol. 7 .-№6. - P. 892-898.

164. Xiong Z., Ramchandran K., Orchard M., Zhang Y.-Q. A comparative Study of DCT- and Wavelet-Based Image Coding // IEEE Trans. On Circuits and Systems for Video Technology. -1999. V.9 - №5. - P.692-695.

165. Zhang Z. and Wei V.K., An on-line universal lossy data compression algorithm via continious codebook refinement. Part I. Basic results // IEEE Trans. Inform. Theory. Vol.42. - May 1996. - P.803-821.