На правах рукописи

Умняшкин Сергей Владимирович

УДК 004.932 : 004.421 : 519.722

Математические методы и алгоритмы цифровой

компрессии изображений с использованием

ортогональных преобразований

Специальность 05.13.11 - “Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей”

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва – 2001 2

Работа выполнена в Московском государственном институте электронной техники (техническом университете)

Научный консультант: доктор физико-математических наук, профессор Поспелов А.С.

Официальные оппоненты:

Доктор физико-математических наук, профессор Ососков Г.А.

Доктор физико-математических наук, профессор Селищев С.В.

Доктор технических наук профессор Коекин А.И.

Ведущая организация: ФГУП НИИ Радио (г.Москва)

Защита состоится 19 февраля 2002 года в 1430 на заседании диссертационного совета Д.212.134.02 в Московском государственном институте электронной техники по адресу: 103498, Москва, г. Зеленоград, МИЭТ (ТУ).

С диссертацией можно ознакомиться в библиотеке МИЭТ (ТУ).

Автореферат разослан 10 января 2002 года

Ученый секретарь диссертационного /Воробьев Н.В./ совета профессор

Общая характеристика работы

Актуальность темы. Хранение и передача изображений при непосредственном цифровом представлении в виде матрицы пикселей (точек изображения) вызывает необходимость обработки колоссальных объемов данных.

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

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

Направление исследований. Проведенные в диссертационной работе исследования включали в себя рассмотрение следующих вопросов:

1. Исследование и разработка методов теоретического анализа и синтеза дискретных преобразований для схем компрессии коррелированных данных;

2. Разработка новых быстрых алгоритмов вычисления дискретного преобразования Крестенсона-Леви (ДПКЛ) и алгоритма сжатия полутоновых изображений, основанного на статистическом кодировании спектров ДПКЛ;

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

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

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

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

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

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

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

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

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

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

• Детерминированные и вероятностные оценки коэффициентов дискретного косинусного преобразования (ДКП);

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

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

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

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

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

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

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

Реализация результатов работы. Теоретические результаты работы и алгоритмы сжатия видеоизображений внедрены в ГУ НПК «Технологический Центр» МИЭТ (http://www.tcen.ru) и использованы в научно-производственной деятельности НПП «Технология» (Москва) [29,30].

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях и совещаниях:

1. VII саратовская зимняя школа по теории функций и приближений (СГУ, январь 1994 г.) [1].

2. Междунар. конференция по теории функций и приближений, посвященная 90-летию акад. С.М.Никольского (Москва, МИ РАН, май 1995 г.) [2].

3. Всероссийские научно-технические конференции “Электроника и информатика” (Москва, МИЭТ, 1995-2000 г.) [3,6,22].

4. Междунар. конференция по теории приближения функций, посвященная памяти проф. П.П.Коровкина (Калуга, КГПУ, 26-29 июня 1996 г.) [4].

5. Международные конференции «Методы оптимизации вычислений» (Киев, 1997, 2001 г.) [7,26].

6. Международная конференция «Проблемы математического образования», посв. 75-летию чл.-корр. РАН проф. Л.Д.Кудрявцева (1998 г.) [9].

7. Международная конференция «Теория приближений и гармонический анализ» (Тула, 26-29 мая 1998 г.) [10].

8. Международная конференция «Информационные технологии в инновационных проектах» (Ижевск, 20-22 апреля 1999 г.) [13].

9. VII Международная конференция «Математика. Экономика. Экология. Образование» – Международный симпозиум «Ряды Фурье и их приложения»

(Новороссийск, 1999 г.) [13,14].

10. VII Международная конференция «Математика. Компьютер. Образование»

(Дубна, ОИЯИ, 24-29 янв. 2000 г.) [17].

11. Международная конференция, посвященная 80-летию со дня рождения С.Б.Стечкина (Екатеринбург, 28 февраля – 3 марта 2000 г.) [18].

В целом содержание работы обсуждалось на научном семинаре лаборатории информационных технологий в Объединенном институте ядерных исследований (г.Дубна, декабрь 2001 года).

Публикации. Основное содержание диссертации отражено в 30 работах.

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

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

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

Использование алгоритмов сжатия с потерями данных для полутоновых изображений носит повсеместный характер: допустив наличие ошибки в восстановленном изображении, можно добиться намного более высокого уровня компрессии данных. Чаще всего качество обработки изображений оценивают X=(xi,j) – матрица исходного изображения, X = ( xi, j ) – матрица изображения, полученного после обработки (сжатия и восстановления данных). Для логарифмической величины СКО используется общепринятая мера PSNR (peak signal to noise ratio – отношение пикового значения сигнала к шуму), Методы сжатия изображений удобно рассматривать в виде общей схемы, состоящей из трех основных этапов: снижение межэлементной корреляции данных, квантование элементов данных, статистическое кодирование. Квантование является основным инструментом, используемым при сжатии с потерями данных. По сути дела, квантование есть выделение из входных данных некоторой основной части информации, когда ее менее значимая часть опускается.

Применяется как скалярное, так и векторное квантование.

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

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

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

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

Поиск решения задачи (1) в большинстве случаев сводится к громоздким численным процедурам итерационного характера. Если не задаваться ограничением R(X,u)Rb, то для определения оптимальных параметров кодирования u*, соответствующих решению задачи (1) для некоторого (заранее неизвестного) значения Rb, используется упрощенный вариант минимизации RD-функции Лагранжа:

где – неотрицательный параметр, задаваемый внешне. Параметр в функции J(u) устанавливает баланс между качеством и уровнем сжатия данных. Значение =0 соответствует наименьшей ошибке кодирования, увеличивая значение, получаем при оптимизации параметров алгоритма F по (2) меньшую длину кода, но большую ошибку. Тем самым можно настраивать алгоритм кодирования F на необходимые характеристики. Для поиска решения задачи (1) минимизация (2) повторяется итерационно, с различными значениями – данная процедура носит название RD-оптимизации1.

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

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

Реализация программной компрессии видео в реальном масштабе времени, таBerger T. Rate Distortion Theory. – Endlewood Cliffs, NJ: Prentice Hall, 1971.

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

Вторая глава (52 страницы) посвящена изучению эффективности и синтезу ортогональных преобразований, предназначенных для использования в сжатии данных. Предложенный новый метод анализа эффективности основан на следующих рассуждениях. Пусть известна ковариационная матрица KX исходного вектора данных X = ( x0, x1,…, x N 1 )T, вектор-спектр Y получен в результате некоторого ортогонального преобразования с матрицей W: Y=WX.

Средняя безусловная энтропия коэффициента вектор-спектра может быть записана в виде [5]:

где fk(mk,k,x) – функция плотности распределения вероятностей для спектральной характеристики yk (k-ой компоненты вектора Y), mk – математическое ожидание, k – среднеквадратичное отклонение, f k0 ( x ) = f k (0,1, x ). Чем меньше средняя энтропия (3), тем эффективнее будет последующее независимое кодирование компонент спектра. Наложив ограничение, при котором для класса что для оптимального преобразования Карунена-Лоэва (когда матрица W=Wopt составлена из собственных векторов KX и матрица KY=WKXWT имеет диагоN 1 N нальный вид) декоррелирующей эффективности будем рассматривать величину средней избыточной энтропии H (W, K X ) = H cp (W, K X ) H cp (Wopt, K X ), которая выражается через элементы матриц K X = (cov( xi, x j ) )i, j = 0 и W = (wi, j )i, j =0 следующим образом [12]:

Чем больше значение H(W,KX), тем меньше эффективность декоррелирующего преобразования с матрицей W. Численные расчеты величины (4) для различных преобразований и видов ковариационных матриц показали результаты, полностью согласующиеся с известными данными, которые получены другими методами, например, по Пэрл (Pearl J. On coding and filtering stationary signals by discrete Fourier transforms // IEEE Trans. Inf. Theory. - 1973. - Vol. ITP. 229-232.).

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

Данная модель часто используется для описания межстрочной и межстолбцовой корреляции в дискретных изображениях. При =1, когда все компоненты в исходном векторе X одинаковы (для любых двух отсчетов вектора коэффициент корреляции равен единице), расчет введенного критерия (4) для матрицы (5) невозможен, т.к. в этом случае имеем det K X = 0. Вместе с тем, на фоновых областях изображения 1. В главе 2 доказана следующая теорема.

Теорема 2.1. Для любой ортогональной матрицы W (NN) такой, что j = 0,1,… N 1 : w0, j = (базисная функция с нулевым индексом есть нормиN рованная постоянная составляющая) и ковариационной матрицы (5) Различные исследования, в том числе проведенные в главе 2, показывают, что среди дискретных преобразований, имеющих быстрые алгоритмы вычислений (для размерности N реализуемых за ~NlogN арифметических операций) наиболее близкие к оптимальному преобразованию Карунена-Лоэва характеристики декорреляции для марковского процесса (5) дает использование ДКП.

Однако несмотря на наличие хорошо проработанных быстрых алгоритмов вычисления, ДКП принципиально требует для своей реализации выполнения операций умножения и по объему вычислений заметно уступает, например, преобразованиям Хаара, Уолша, Крестенсона-Леви. Отдельным вопросом, рассмотрению которого уделено значительное внимание в главе 2, является построение нового преобразования, имеющего как высокие характеристики декорреляции для модели (5), так и значительно более быстрые, чем для ДКП, алгоритмы вычисления. Полученное в результате дискретное псевдокосинусное преобразование определено для векторов размерности N, которая допускает разложение N=N1…Nn, причем k Nk{2,3,4}. Представление N=N1…Nn необходимо записать минимальным количеством множителей Nk, располагая их без убывания, т.е. k, m>k: NkNm. Например, для N=8 имеем N1=2, N2=4 (но не N1=4, N2=2 и не N1=N2=N2=2). Тогда матрица ДПКП WN (в данном случае нижний индекс указывает на размерность преобразования) строится как прямое произведение2 WN = WN 1 … WN n элементарных матриц ДПКП WN k {W2,W3,W4}, k=1,…,n, где элементарные матрицы ортогональны Под тензорным (прямым) произведением матриц D={dl,m} (l=0,…,-1; m=0,…,-1) и и получены в результате определенных модификаций из матриц ДКП соответствующей размерности. Элементарные матрицы представимы в виде произведения некоторой диагональной матрицы D на матрицу С, а структура С позволяет реализовать умножение на произвольный вектор U только при помощи операций сложения и вычитания чисел (умножение на 2 эквивалентно сложению, 2x=x+x). Именно:

Из свойств тензорного произведения следует представление WN = D N C N, C N = C N 1 … C N n. Матрицы C2, C3, C4, D2, D3, D4 приведены выше. Таким образом, реализация ДПКП Y = WN X = D N C N X заключается в реализации умножения матрицы CN на вектор, Y = C N X, и последующей нормировке полученного вектора Y, Y = D N Y. Для вычисления ДПКП удобно использовать быстрые алгоритмы, основанные на факторизованном представлении для матматриц3:

единичная матрица размерности N j N j. Поскольку матрицы TN j ) состоят из определенным образом разреженных матриц-блоков C N j, умножение матрицы TN j ) на вектор также сводится только к операциям сложения и вычитания чисел. Быстрые алгоритмы обратного ДПКП строятся аналогично, т.к. в силу орT ) () Отметим, что необходимая при вычислении ДПКП и обратного ДПКП нормировка (умножение на матрицу DN) для схемы сжатия со скалярным квантованием коэффициентов преобразования не влечет усложнения вычислений.

Нормировка может быть объединена при сжатии данных с этапом скалярного зованного вектора Y индивидуального шага квантования qj=q/djj (где d jj – элемент диагональной нормировочной матрицы D N ). При деквантовании y j = m~ j множитель для элемента y j следует выбирать в виде mj=qdjj.

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

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

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

x[0;1) в нумерации Пэли определяется следующим образом:

где p2 (целое число), xk x p k (mod p ), m k m p k 1 (mod p ), а число l(m) находится из условия: pl(m)-1mpl(m)-1. Система функций Крестенсона-Леви является обобщением на комплексную плоскость хорошо известной системы функций Уолша, которая получается из (6) при p=2.

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

где X = x0, x1,…, x p n 1 T - исходный вектор, Y = y0, y1,…, y p n 1 T – вектор-спектр ДПКЛ. Нижний индекс n матрицы W(n) указывает на размерность преобразования, N=pn. Элементами симметрической матрицы W(n) являются отсчеты функций системы (6): wk, l = k l p n. Быстрые алгоритмы ДПКЛ основаны на факторизованном представлении матрицы W(n) в виде произведения слабозаполненных матриц. Один из возможных способов факторизации матрицы ДПКЛ предложен автором и может быть сформулирован в виде следующей теоремы [1].

Теорема 3.1. Матрица ДПКЛ представима в виде W( n ) = W((n ) W((n2))…W((n )), (на диагонали матрицы W((nj)) размерности pnpn находятся p матриц W((nj1) размера pn-1pn-1, остальные элементы матрицы W((nj)) – нулевые). Матрица W((n )) ={wj,k} ( j,k=0,1,…,pn-1) имеет следующий вид: w j, k = [jkmod p n1 q jn k 1, где Дискретные (цифровые) полутоновые изображения описываются в виде вещественной матрицы X. При обработке вещественных векторов (матриц) спектр ДПКЛ распадается на пары комплексно сопряженных элементов, поэтому часть элементов спектра можно не вычислять. Учет этих особенностей позволил предложить для обработки вещественных массивов алгоритмы ДПКЛ и обратного ДПКЛ с неполным вычислением. При обработке вещественных наборов данных возможно также применение «совмещённых» преобразований, аналогично тому, как это делается при вычислениях дискретного преобразования Фурье. При этом из двух вещественных векторов X(1) и X(2) формируют комплексный вектор X=X(1)+iX(2) и выполняют преобразование.

Если использовать для комплексных чисел z=x+iy представление в базисе (1,q): z=+q (q= e2 i / 3 ), то вычисление ДПКЛ (при p=3) может быть выполнено без использования операций умножения (нормирующий множитель p n, см. (7) – не учитывается) при помощи операций сложения и вычитания (данный факт установлен А.В.Ефимовым). Использование в алгоритмах с неполным вычислением базиса (1,q) влечет за собой ряд особенностей, которые рассматриваются в главе 3. При размерности матрицы изображения 3n3r вычисление ДПКЛ или обратного ДПКЛ по алгоритмам с неполным вычислением требует выполнения 7(n+r)3n+r-1 операций сложения (вычитания), операции умножения и деления не используются. Использование базиса (1,q) в вычислительном плане является более эффективным и для алгоритмов совмещенных вычислений. Специфика использования ДПКЛ и базиса (1,q) рассмотрена в главе 3, там же получены необходимые для реализации совмещённых ДПКЛ и обратного ДПКЛ расчетные формулы.

Для обработки неподвижных изображений в кандидатской работе автора был предложен алгоритм компрессии, в котором исходное изображение разбивается для обработки на элементарные фрагменты размером 99 точек, и каждая матрица-фрагмент обрабатывается при помощи ДПКЛ. В главе приводится краткое описание алгоритма компрессии [20], который подтвердил обоснованность использования дискретного преобразования Крестенсона-Леви для сжатия изображений. Характер вносимых в процессе сжатиявосстановления ошибок различен для основанного на ДКП метода JPEG и для предложенной схемы: при использовании JPEG имеет место “размывание”, в то время как новая схема сжатия приводит к “зубчатости” изображения. Тем не менее, субъективное качество восприятия при использовании обоих рассмотренных способов сжатия примерно одинаково. Оценки величины искажений по величине PSNR, выполненные для ряда тестовых изображений размерности 720504=362880 точек, также дали близкие результаты: для одних изображений может наблюдаться незначительное преимущество основанного на ДКП стандарта JPEG, для других изображений лучшее качество восстановления возможно при использовании нового метода. Различия невелики, особенно при невысоких уровнях сжатия. Оценки вычислительных затрат показывают, что алгоритм на основе ДПКЛ не уступает JPEG и в части, касающейся вычислительной сложности реализации. Алгоритм компрессии изображений [20], использующий ДПКЛ и имеющий сравнимые с характеристики, представляет собой результат, впервые полученный автором.

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

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

где j=xj–xj–1 – первые разности отсчетов исходного вектора данных X = ( x0, x1,…, x N 1 ). Формула (8) показывает, что разности j имеют различT ный характер влияния на спектр ДКП. Так, разность N/2=xN/2–xN/2–1 (при четном N) входит во все коэффициенты y 2 k +1 с максимальными по модулю (единичными) весами. Разность между отсчётами x 0 и x N 1 вообще не входит в (8), что принципиально отличает ДКП от его «прародителя» – дискретного преобразования Фурье, амплитудный спектр которого инвариантен к циклическим сдвигам (x0x1…xN-1x0) компонент вектора данных X.

В предположении некоррелированности разностей4 j и равенства нулю их математических ожиданий E(j)=0 исследовались также вероятностные оценки, в частности, величина суммарной дисперсии переменных составляюN щих спектра ДКП: E = D( y k ). Данная сумма представима через дисперсии первых разностей вектора данных следующим образом: E = где S(j) – некоторый весовой коэффициент.

Для марковской модели (5) данное допущение не верно.

Доказана теорема 4.1: для коэффициентов S(j) верно соотношение:

S(j)=2j(N-j).

Полученное соотношение вновь подтверждает, что для использовавшейся вероятностной модели вектора X разность N/2 (в данном случае, ее дисперсия) вносит наибольший вклад. Чем ближе номер разности к N/2, тем больше значение веса S(j) и тем больший вклад вносит разность j в энергию переменных составляющих. Исследование спектров ДКП для некоторых характерных сигналов также подтвердило, что при использовании приемов кодирования спектров из JPEG (в частности, кодирование серий нулей – run-length encoding) эффективность кодирования будет ухудшаться в случае, когда информационная насыщенность дискретного сигнала будет приходиться на центральные отсчеты вектора.

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

Для сжатия статических изображений с использованием ДКП 88 в четвертой главе разработан новый алгоритм [24], отличающийся от JPEG этапом статистического кодирования, для которого используется несколько моделей и алгоритм арифметического кодирования. Обозначим Z = ( z0,…, z63 ) – вектор, полученный в результате зигзагообразного считывания по JPEG матрицы скалярно проквантованных коэффициентов ДКП в одномерную последовательM.Crouse and K.Ramchandran. Joint thresholding and quantizer selection for transform imagecoding: entropy-constrained analysis and applications to baseline JPEG // IEEE Trans. on Image Processing. – 1997. - Vol. 6. -№2 - P. 285-297.

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

– Поток D, соответствующий постоянным составляющим яркости z0 = ~0,0.

– N0 потоков {Si }iN 01, в которых кодируются длины нулевых серий.

– N1 потоков {Ci }iN 11, в которых кодируются ненулевые компоненты.

Сначала для каждого вектора Z в потоке D постоянная составляющая яркости z0 кодируется при помощи дифференциальной импульсно-кодовой модуляции. Затем выполняется следующая обработка компонент z1,…,z63.

Шаг 0. (Подготовительный).

Определить индекс jmax последнего ненулевого элемента z jmax 0, Индекс текущей обрабатываемой компоненты zj: j0.

Установить текущий поток (модель) TSN0.

Шаг 1. jj+1. Если j> jmax, то перейти на шаг 3.

Шаг 2. Если zj=0 то 2.1. Длина нулевой серии: nznz+1. Перейти на шаг 1.

2.2. В текущем потоке T закодировать nz; положить nz0.

2.3. Вычислить контекстный прогноз p=pj(z1,…,zj-1).

2.4. Установить текущий поток TСk. Номер k, 1kN1, 2.5. В потоке T закодировать компоненту zj.

2.6. Установить текущий поток (модель) TSk. Номер k, Шаг 3. Если j m : pmj ) pk j ). Для обеспечения возможности адаптации кодовой книги необходимо предусмотреть процедуру альтернативного «невекторного» квантования и кодирования кластеров (назовем такую процедуру непосредственным кодированием), для которой возможно применение различных вариантов, рассмотренных в диссертационной работе. В частности, предложена экспериментальная методика поиска оптимального разбиения дискретных спектров на области для независимого статистического кодирования, когда каждой такой области соответствует отдельная статистическая модель арифметического кодера. Непосредственно закодированный вектор помещается в кодовую книгу на место вектора, имевшего наименьший вес, а если в кодовой книге имеется несколько таких векторов, то удаляется вектор, который попал в кодовую книгу раньше других.

Пусть D(x,y)=||x-y||2 – квадрат евклидовой нормы разности векторов x и y; DHK = D Y ( j ), Y ( j ) – ошибка ( Y ( j ) – декодированный кластер), а RНК=R(Y(j)) – битовые затраты непосредственного кодировании кластера. Предлагаемый алгоритм RD-оптимизированной обработки фрагмента изображения сводится к повторению для каждого кластера Y(j) (j=1,…,M) следующей процедуры.

Шаг 1. Вычислить RD-функцию векторного кодирования Шаг 2. Вычислить RD-функцию непосредственного кодирования Шаг 3. Кодирование по наилучшему варианту.

где НК и ВК) – соответственно частоты непосредственно и векторно кодируемых кластеров в j-ом потоке ( НК + ВК) =1), то /* кодировать векторно */ 3.1. Закодировать битовый признак ВК;

3.2. Закодировать индекс i наилучшего вектора 3.3. Выполнить сортировку кодовой книги C(j):

– выполнить циклическую перестановку векторов и их весов:

иначе /* кодировать непосредственно */ 3.4. Закодировать битовый признак непосредственного кодирования;

3.5. Закодировать скалярно проквантованный вектор Y ( j ) ;

3.6. Обновить кодовую книгу C(j):

– определить индекс начала m векторов с минимальным весом, Конец Сделаем пояснения к приведенному алгоритму адаптивного ВК. Для каждого потока векторов, помимо кодовой книги, изначально задается некоторое распределение p0 j ), …, p L jj )1, которое является внутренней статистической моделью адаптивного арифметического кодера, используемой для кодирования индексов кодовой книги. Изменение веса векторов при кодировании индекса на шаге 3.2 представляет собой адаптацию соответствующей модели к входным данным и является внутренней функцией арифметического кодера; конкретное значение величин, m меняется в зависимости от объема уже обработанных данных и во многом определяется спецификой статистического моделирования кодера. После изменения на шаге 3.2 весов векторов выполняется шаг 3.3, который представляет собой «погружение» только что закодированного вектора j, k > m : pmj ) pk j ). Тем самым внутри серий индексов, соответствующих равным весам (и, соответственно, равным битовым затратам на кодирование), производится сортировка векторов по времени появления, которая гарантирует, что при пополнении кодовой книги новым вектором (шаг 3.6) удален будет наиболее давний из самых редко встречающихся векторов, c (Ljj)1.

Для бинарного признака непосредственного или векторного кодирования необходимо использование отдельной модели арифметического кодера, алфавит которой состоит лишь из двух символов; в приведенном описании алгоритма подразумевается, что необходимое изменение значений частот НК и ВК) (адаптация модели) производится арифметическим кодером при выполнеj нии шага 3.1 или 3.4.

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

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

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

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

Дерево, включающее в себя все свои спектральные коэффициенты, обозначим T. Строчными буквами i будем обозначать индексы узлов дерева, каждый из которых соответствует спектральному коэффициенту. Под Ti понимаем дерево, начинающееся из узла i и включающее в себя этот узел. Таким образом, Ti – это определенная ветвь полного дерева T=T0. Подрезанным деревом Si назовем любое поддерево дерева Ti (SiTi), содержащее узел i. Аналогично, S – это дерево, полученное в результате подрезания ветвей полного дерева T, а все возможные варианты топологии дерева характеризуются множеством {S|ST}.

Деревом остатка Ui будем называть множество всех прямых потомков узла i, т.е. Ui= Ti\{i}. Множество непосредственных потомков узла i обозначаем через ризонтальные слои узлов (см. рис. 1) и обозначаем их как Lk. Для n-шагового преобразования в исходном дереве T имеем n+1 уровень {L0,…,Ln}, при этом нулевой уровень состоит из единственного узла. Таким образом, L0={0}, L1={1,2,3}, L2={4,…,15}, …, Ln={22(n-1),…,22n-1} (слой с номером n состоит из листьев). Ограничим рассмотрение случаем, когда единственным параметром кодирования коэффициентов из дерева S является шаг q скалярного квантования вейвлет-коэффициентов. Основная задача, стоящая перед алгоритмом компрессии, состоит в поиске RD-оптимальной топологии при фиксированных значениях, q: J ( S * ) = min[D ( S ) + R( S )].

Идея предложенного в пятой главе алгоритма сжатия [25,27] основана на работах Lewis-Knowles6 (LK) и Xiong-Ramchandran-Orchard7 (XRO). При кодиLewis A.S., Knowles G. Image Compression Using the 2-D Wavelet Transform // IEEE Trans.

Image Proc. – 1992. – Vol. 1. - №2. – P.244-250.

ровании топологии S в XRO для всех узлов дерева, кроме листьев, использовалась бинарная карта {ni}: если ni=0, то дерево в данном узле подрезается, а если ni=1, то по крайней мере непосредственные потомки сохраняются. Сказанное иллюстрируется рис. 2А. Статистическое кодирование признаков {ni} в алгоритме XRO не используется. Вместе с тем, признаки {ni} соседних (по положению внутри саббэнда) узлов являются коррелированными величинами. Чтобы учесть эту корреляцию, в разработанном алгоритме признаки для соседних узлов {ni }iC j предлагается группировать в единый элемент данных, так что карта подрезания ветвей (топология дерева) описывается новым алфавитом данных с символами Ni=(ni1,ni2,ni3,ni4)=ni1+2ni2+4ni3+8ni4, которые, кроме того, кодируются статистически. Новый расширенный признак Nj оказывается связанным уже с узлом j более высокого уровня, см. рис. 2Б.

Подрезание ветвей Рисунок 2. Способ подрезания ветвей при послойном просмотре узлов: А – алгоритм XRO, Б – предлагаемое кодирование топологии. Ci={i1,i2,i3,i4} Идея, которая восходит к работе LK и в том же виде используется в XRO, заключается в следующем: чем больше абсолютная величина вейвлеткоэффициента wi (или энергия, wi2 ) узла-родителя i, тем менее вероятно появление у данного узла нулевой (т.е. подрезанной) ветви. Более точное предсказание появления нулевой ветви можно составить, если использовать в качестве Xiong Z., Ramchandran K. and Orchard M.T. Space-frequency Quantization for Wavelet Image Coding // IEEE Trans. Image Proc. – V.6 – May 1997, P. 677-693.

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

где множества для индексов суммирования определяются среди соседей узла i в саббэнде в соответствии с рис. 3. Весовые коэффициенты, входящие в сумму, были получены в результате статистической обработки ряда тестовых изображений с целью выявления максимума выборочного значения для коэффициента корреляции между прогнозной величиной (10) и энергией проквантованных вейвлет-коэффициентов непосредственных потомков Сi: Pi, w2 max.

Предлагаемый алгоритм вейвлет-компрессии использует несколько статистических моделей. Функцию арифметического кодера, которая оценивает по внутренним статистическим моделям количество бит, необходимое для кодирования символа с в k-ом потоке, обозначим H(k,c). Обозначение Hspec относится к потокам, в которых кодируются проквантованные вейвлет-коэффициенты, Hmap – к потокам, в которых кодируются признаки начала нулевой ветви. Деревья спектра обрабатываются последовательно; после оптимизации топологии очередного дерева его необходимо закодировать, и тем самым произвести адаптацию статистических моделей арифметического кодера.

Шаг 0. /* инициализация */ i Ln1 : /* просматриваются все узлы предпоследнего уровня */ /*корректировка проквантованных коэффициентов*/ /* расчет RD-функций сохранения и подрезания листьев */ Шаг 2. i Ll : /*просмотр текущего уровня с попыткой подрезания ветвей */ Если i0 то /* не достигли начала дерева */ /* определение оптимальной топологии ветвей */ /*корректировка проквантованных коэффициентов*/ /* подготовка для просмотра следующего уровня */ иначе /* i=0, достигли начала дерева */ /* определение оптимальной топологии дерева */ Шаг 3. /* формирование и выдача результата */ Конец Просмотр узлов дерева проводится от листьев к корню. На первом (подготовительном) шаге просматриваются те узлы i, которые имеют только непосредственных потомков (Ci=Ui), формируются массивы из значений RDфункций, соответствующих вариантам подрезания ( J U i ) и сохранения ( J U i ) листьев. Предварительно, на шаге 1.1, для каждого узла-листа анализируется возможность дополнительной минимизации Лагранжа, характеризующей скалярное квантование вейвлет-коэффициентов. Данная процедура основана на известных свойствах распределения вероятностей вейвлеткоэффициентов, в соответствии с которыми битовые затраты R на кодирование коэффициента априори тем меньше, чем меньше его абсолютное значение (по этой причине для случая w = 0 процедура дополнительной минимизации не применяется). На втором шаге, который выполняется для всех узлов i следующих уровней, iLl (l=n-2,…,0), производится выбор RD-оптимального способа подрезания ветвей (шаги 2.1-2.2), начинающихся из узлов jCi. Шаги 2.3 и 2. несут тот же смысл, что и шаги 1.1, 1.2. Отметим, что введение дополнительной оптимизации скалярного квантования (шаги 1.1 и 2.3) позволяет при том же уровне сжатия дополнительно повысить PSNR на 0,02-0,03 дБ.

Для всех узлов, за исключением корневого, выбор модели для кодирования признаков Ni (на шаге 2.1) производится с использованием правила, определяемого функцией IndMap(i). Для кодирования признака N0, связанного с корнем дерева, используется отдельный поток данных, которому условно присвоен номер 0 (см. шаг 2.6).

Как следует из приведенного описания алгоритма оптимизации, важнейшую роль в его работе играют функции IndMap( Pi ) и IndSpec(i), которые задают правила выбора потоков для кодирования данных. Первая функция производит выбор модели кодирования признака Ni=(ni1,ni2,ni3,ni4) по среднему значению прогнозных величин Pi (10), i=i1,i2,i3,i4, и имеет следующий вид:

Пороги (t1,t2,t3)=(0.3;1.1;4.0) для выбора моделей находились в результате минимизации длины выходного битового кода R(t1,t2,t3) при обработке известных тестовых изображений Lena, Barbara, Goldhill. Эксперименты показали также, что введение большего числа моделей для признаков лишено смысла.

Вторая ключевая функция алгоритма вейвлет-сжатия, IndSpec(i), представляет собой правило выбора модели для кодирования не попавших в нулевые ветви вейвлет-коэффициентов. Для кодирования спектральных коэффициентов более эффективным оказывается использование прогнозной величины, полученной не только по родительскому узлу, но и по вейвлеткоэффициентам узлов, которые находятся в том же саббэнде, рядом с обрабатываемым8. В рассматриваемом алгоритме последовательность кодирования и декодирования узлов вейвлет-спектра определяется схемой рисунка 4 (цифры обозначают порядок обработки саббэндов). Для использования в функции IndSpec(j) прогнозная величина текущего узла j (помечен черным) формируется s j = 0.36 Pi + 1.06 w j y + w jx + 0.4 w jd, где jy – узел-сосед по вертикали, jx – Идея использования контекста соседних вейвлет-коэффициентов предложена в работе Chrysafis С., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet Image Compression // Proc. Data Compression Conference. – Snowbird (Utah), 1997. – P. 241-250.

узел-сосед по горизонталии, jd – узел-сосед по диагонали (которые уже обработаны, см. рис. 4), Pi определяется для узла-родителя i (jCi) по (10). При этом результатам обработки тестовых изображений.

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

Характеристики, которые дает Таблица. 1. Величина PSNR (в дБ), попредложенный алгоритм компрессии лученная при сжатии тестовых изобрадля стандартных тестовых изображе- жений по предложенному алгоритму ний, приведены в табл. 1. В экспериLena Barbara Goldhill ментах применялись пятишаговые вейвлет-преобразования из работы Wei D., Pai H.-T., and Bovik A. C., Antisymmetric Biorthogonal Coiflets for Image Coding // Proc. IEEE International Conference on Image Processing. – Chicago, 1998. – V. 2. – P. 282-286. Сравнение достигнутых характеристик с результатами применения других известных алгоритмов показывает, что предложенный алгоритм имеет весьма высокие показатели.

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

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

Кадром видеопоследовательности назовем матрицу пикселей из M1 строк и M2 столбцов: B=(bk,l), k=0,1,…,M1-1, l=0,1,…,M2-1, а под видеопоследовательностью будем понимать упорядоченный набор кадров B0,B1,…,Bi,…. Назовем (y,x)-блоком кадра B (y, x – целочисленные координаты) некоторую подматрицу By,x=(bk,l), где k=y,y+1,…,y+N1-1, l=x,x+1,…,y+N2-1. В разработанном алгоритме каждый кадр видеопоследовательности разбивается при обработке на смежные матрицы-блоки {Bm,n} размером 88, m,n=0,8,16… Если какой-либо блок Biy,x видеопоследовательности оказался в определенном смысле «похож» на оригинальный блок Bim, n, считаем, что блок Bim,n – это перемещенный фрагмент Biy,x См., например, Davis G.M., A wavelet-based analysis of fractal image compression // IEEE Trans. Image Proc. – 1998. – V.7 – №2. – P.141-154.

предыдущего кадра, и для кодирования (m,n)-блока изображения достаточно задать координаты блока в предыдущем кадре, y и x, либо изменения координат y-m и x-n. Частным случаем перемещенного блока является неподвижный блок, когда m=y, n=x. Если блоку Bim, n нельзя найти похожий в предыдущем кадре, блок должен кодироваться как новый. Для выбора способа кодирования очередного обрабатываемого блока Bim, n вновь руководствуемся критерием минимума функции Лагранжа J(b)=D(b)+R(b). Положим, что аргумент b= соответствует кодированию перемещенного (неподвижного) блока, а b=1 – нового. Т.е. если J(1)>J(0), то блок кодируется как перемещенный, и как новый – в противном случае.

При использовании RD-оптимизации задача поиска перемещенных блоков формулируется следующим образом. Для заданного (m,n)-блока Bim, n i-ого кадра найти в предыдущем восстановленном кадре такой (y,x)-блок B iy,x, чтобы минимальное значение принимала RD-функция Лагранжа Здесь учтено, что координаты найденного блока будут кодироваться как относительные, т.е. вектором перемещений r=(y-m,x-n). Для того чтобы поиск можно было осуществить в реальном масштабе времени, в качестве области необходимо рассматривать лишь точки (v,u), достаточно близко расположенные к точке (m,n). Повышение эффективности поиска за счет расширения области достигается применением различных алгоритмов направленного поиска, ориентированных на минимизацию ошибки представления перемещенного блока Bim, n Biy,1, что соответствует частному случаю (11) при =0. Для того, чтобы учесть вклад битовых затрат в RD-функцию J*, будем проводить минимизацию (11) поэтапно, на каждом из этапов приближенно полагая, что рассматриваемые векторы перемещений влекут одинаковые затраты на статистическое кодирование. Кроме того, для повышения универсальности итерационных алгоритмов поиска малые перемещения будем искать более точно. Действительно, если некоторый блок изображения переместился на значительное расстояние по сравнению с предыдущим кадром, то соответствующий фрагмент изображения воспринимается человеческим глазом смазано, и в точном определении вектора перемещения нет необходимости. Малые же перемещения блоков не только являются преобладающими, но и должны точно отслеживаться в силу специфики визуального восприятия. Предлагаемый алгоритм RD-поиска имеет следующий вид.

Шаг 0. Вычисление значения RD-функции неподвижного блока, r=(0,0):

Шаг 1. Близкий к перебору точный поиск небольших перемещений.

1.1. Среди девяти (y,x)-блоков предыдущего кадра, 1.2. Среди девяти (y,x)-блоков предыдущего кадра, 1.3. Вычисление значения RD-функции Шаг 2. Грубый поиск больших перемещений.

2.1. Среди восьми (y,x)-блоков предыдущего кадра, 2.2. Среди девяти (y,x)-блоков предыдущего кадра, ( y 4, x 4 ) {(0,0), (2,2), ( 2,2), ( 2,2), (2,2), (3,0), (0,3), ( 3,0), (0,3)} 2.3. Вычисление значения RD-функции Шаг 3. Выбор наилучшего варианта перемещения блока.

Конец Для вычисления значения функции J0 необходимо учесть битовые затраты на кодирование признака перемещенного блока: J 0 = J * log2 ( mov ), где mov – частота появления перемещенных блоков в уже обработанных данных.

Основной объем вычислений в приведенном алгоритме связан с подсчетом отклонений B im, n Biy,x. При вычислениях одна пробная точка переходит с шага 0 на шаг 1.1, одна – с шага 1.1 на 1.2, одна – с шага 2.1 на 2.2. В итоге вычисление отклонения требуется выполнить 33 раза.

Для повышения эффективности приведенного алгоритма поиска для вектора ( y, x ) обрабатываемого блока следует строить прогноз по векторам ( ) и ( ) двух уже обработанных соседних блоков (соответственно соседа по вертикали и соседа по горизонтали). Собственно прогноз – это относительные координаты y 0, x 0, которые определяют перенос центра области поиска: из точки (m,n) в точку (m, n) = m + y 0, n + x 0. Эксперименты показывают, что число новых блоков изображения сокращается на 5…25%, если принять следующее правило составления прогноза:

Следуя идеологии стандарта MPEG, обработку новых блоков также осуществляем при помощи квантования с последующим статистическим кодированием коэффициентов двумерного ДКП. Пусть S=F(Вm,n) – результат ДКП блока Вm,n. Обозначим SQ = {~k,l = round( sk,l / qk,l )}k,l =0, SQ = {sk,l = qk,l ~k,l }k,l =0, где Q = {qk,l }k,l =0 – одна из матриц квантования JPEG. Для статистического кодирования матрицы S применен алгоритм контекстного кодирования, рассмотренный в главе 4, в который введен дополнительный этап RD-оптимизации. Пусть вновь ZQ = ( z0,…, z63 ) – вектор, полученный в результате зигзагообразного считывания данных из матрицы SQ по правилу, определяемому стандартом JPEG ( SQ ZQ ), G ( ZQ ) = {g k }C=1 {0,…,63} – множество индексов ненулевых элементов вектора ZQ, т.е. z g k 0, если gkG; gkG: z g k = 0. RD-оптимизация статистического кодирования возможна за счет удлинения нулевых серий путем сокращения количества элементов во множестве G (дополнительного обнуления компонент вектора ZQ). Для того, чтобы в результате не произошло заметного усложнения алгоритма кодирования, будем анализировать лишь возможность увеличения финальной нулевой серии, что дает наибольший вклад в минимизацию функции J(ZQ)=D(ZQ)+R(ZQ). Пусть ZQ – вектор, полученный из вектора ZQ в результате обнуления последних компонент {zk }k = g m +1, т.е.

G ( ZQ ) = {g k }m=1 G ( ZQ ), m=1,…,C. Тогда простейшая RD-оптимизация состоm ит в поиске такого индекса g m * G ( ZQ ), что Рассмотренная выше процедура кодирования нового блока изображения предполагает использование заданной матрицы квантования Q. Универсальный же алгоритм кодирования должен оперировать некоторым набором матриц квантования {Qj} с возможностью выбора требуемой для конкретных условий.

Если набор достаточно большой, то подбор матрицы квантования Q по принципу минимума функции JQ (12) превращается в громоздкую процедуру, нереализуемую в реальном масштабе времени стандартными средствами. Кроме того, при большом диапазоне возможных значений индекса j его кодирование для каждого нового блока по отдельности влечет недопустимо высокие дополнительные битовые затраты. Поэтому в качестве исходного набора были выбраны лишь несколько матриц из множества, рекомендуемого JPEG, которые соответствуют наилучшему, наихудшему и некоторым промежуточным уровням качества. В экспериментах выбиралось число матриц |{Qj}|=4. Для ускорения выполнения операций деления, которые необходимы при квантовании, элементы матриц {Qj} были округлены до ближайшего значения 2k, k=0,1,… Такой подход позволяет заменить операции целочисленного деления и умножения сдвигами разрядов двоичного представления чисел, которые обычно выполняются реальной аппаратурой намного быстрее.

С учетом битовых затрат, которые необходимы для кодирования индекса матрицы квантования, функция Лагранжа, соответствующая кодированию нового блока изображения, определяется следующим образом:

J = min (J Q log 2 Q ) log 2 new, где JQ находится в соответствии с (12), Q – частота появления матрицы Q, new – частота появления новых блоков в ходе предшествовавшей обработки.

При исследовании характеристик итогового алгоритма видеокомпрессии для оценки величины ошибки кодирования в восстановленной последовательности B0, B1,…, B K 1 использовалось отношение пикового значения сигнала к шуму, которое определялось следующим образом:

где M1 и M2 задают размер кадра в пикселях. Для экспериментов были выбраны широко известные тестовые последовательности News, Container ship, Hall monitor, Akiyo, Claire. Все они имеют размер кадра 144176 пикселей. Перед проведением экспериментов оригинальные последовательности были прорежены: только каждый третий кадр, B3k (k=0,…,24), использовался для формирования тех 25-кадровых видеопоследовательностей, которые затем и были подвергнуты обработке. Данное временное прореживание было призвано смоделировать скорость видеозахвата 10 кадров в секунду, вместо оригинальных (для всех вышеназванных последовательностей) 30 кадров в секунду. Обработке подвергалась только яркостная Y-составляющая, и только по яркостной составляющей анализировалась ошибка Программное сжатие видеопоследовательностей при этом удалось осуществить в реальном масштабе времени.

Результаты численных экспериментов, полученные аспирантом Ф.В.Стрелковым [28], отражены в таблице 2. В скобках приведено значение PSNR (13), достигнутое на тех же самых прореженных 25-кадровых тестовых видеопоследовательностях с использованием общедоступного кодера MPEG- http://www.mpeg.org/MSSG. Длина файла сжатых данных, полученного в каждом эксперименте, в точности равна произведению величины битового потока данных (приведена в таблице) на множитель 2.5. Во всех тестах предложенная схема компрессии дает высокие результаты, превосходя характеристики указанного кодера MPEG-2, несмотря на то, что кодек mpeg2encode использовал для поиска перемещенных блоков изображения полный перебор в области из 2323 пикселей.

Таблица 2. Характеристики сжатия предложенного алгоритма Описанный алгоритм видеокомпрессии был реализован программно в рамках работ, проводившихся в ГУ НПК «Технологический Центр» Московского государственного института электронной техники и в НПП «Технология»

[29,30], внедрение разработанных библиотек видеокомпрессии осуществлено в ряде программных систем, среди которых наибольший практический интерес представляет система видео контроля и регистрации Visual Security (см.

http://www.tcen.ru/vs).

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

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

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

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

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

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

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

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

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

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

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

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

2. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Применение преобразования Крестенсона-Леви в задачах цифровой обработки информации // Междунар.

конф. "Функциональные пространства, теория приближений, нелинейный анализ", посв. 90-летию акад. С.М.Никольского (27 апр. - 3 мая 1995 г.): Тез.

докл. - М.: Изд-во МФТИ, 1995. - С.124-125.

3. Умняшкин С.В. Применение дискретного преобразования Крестенсона-Леви (ДПКЛ) для кодирования изображений: сравнение с дискретным преобразованием Фурье (ДПФ) // Всерос. науч.-тех. конф. “Электроника и информатика” 15-17 нояб. 1995 г.: Тез. докл. - М.: МГИЭТ (ТУ), 1995. - С. 265-266.

4. Умняшкин С.В. Оценка дисперсии элементов спектра дискретного косинусного преобразования стационарного марковского процесса первого порядка // Междун. конф. по теор. прибл. функ., посв. памяти проф. П.П.Коровкина (Калуга, 26-29 июня 1996 г.): Тез. докл. -Т.2.-Тверь: ТГУ, 1996. - С. 217-218.

5. Умняшкин С.В. Оценка эффективности использования унитарных преобразований для кодирования дискретных сигналов // Информатика и связь: Сб.

Научных трудов под ред. В.А.Бархоткина. М.: МИЭТ.- 1997. С.73-78.

6. Умняшкин С.В. Оценка эффективности применения дискретных преобразований для сжатия данных // «Электроника и информатика – 97». Вторая всероссийская научно-техническая конференция с международным участием (Зеленоград, 25-26 ноября 1997г.): Тез. док. Часть 2. - С.79.

7. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Теоретические основы и некоторые особенности применения дискретных мультипликативных преобразований в задачах сжатия цифровых изображений // Працi мiжнародноi коференцii “Питання оптимизацii обчислень” (6-8 жовтня 1997 р., м. Киiв) Киiв: Iнститут кiбернетики iменi В.М.Глушкова, 1997. - С. 108-112.

8. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Некоторые свойства мультипликативных ортонормированных систем, используемые в цифровой обработке сигналов // Труды математического института им. В.А.Стеклова РАН.

- Т.219. - 1997. - С 137-182.

9. Ефимов А.В., Умняшкин С.В. О некоторых свойствах обобщенной системы Хаара и оценке эффективности применения ортогональных преобразований для сжатия данных // Функциональные пространства. Дифференциальные операторы. Проблемы математического образования: Труды междун. конф., посв. 75-летию чл.-корр. РАН проф. Л.Д.Кудрявцева. - Том 1. - М.: Рос. ун-т дружбы народов, 1998. - С. 70-73.

10. Умняшкин С.В. О модификации дискретного косинусного преобразования // Теория приближений и гармонический анализ: Тез. докл. междунар. конф.

(Тула, 26-29 мая 1998 г.). - Тула: ТулГУ, 1998. - С.264-265.

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

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

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

14. Умняшкин С.В. Алгоритм кластеризации коррелированных данных // VII Междунар. конф. Математика. Экономика. Экология. Образование. Междунар. симп. Ряды Фурье и их приложения: Тез. док. – Ростов: Рост. гос. эконом. акад., 1999. – С. 211-212.

15. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Некоторые вопросы применения мультипликативных систем и преобразований в задачах цифровой обработки изображений // VII Междунар. конф. Математика. Экономика.

Экология. Образование. Междунар. симп. Ряды Фурье и их приложения: Тез.

док. – Ростов: Рост. гос. эконом. акад., 1999. – С. 154-155.

16. Умняшкин С.В. Псевдокосинусное преобразование для сжатия дискретных сигналов // Информационные технологии и проблемы микроэлектроники.

Сб. науч. тр. – М.: МИЭТ. – 1999. – С.158-170.

17. Умняшкин С.В. Алгоритм компрессии неподвижных изображений на основе дискретного вэйвлет-преобразования // VII международная конференция «Математика. Компьютер. Образование» (Дубна, ОИЯИ, 24-29 янв. 2000):

Тез. док. – Москва: Прогресс-Традиция, 2000. – С.327.

18. Ефимов А.В., Умняшкин С.В. О структуре некоторых прямых и обратных вэйвлет-преобразований // Теория приближений функций и операторов: Тез.

докл. Междунар. конф., посв. 80-лет. со дня рожд. С.Б.Стечкина (Екатеринбург, 28 фев. – 3 мар. 2000). -Екатеринб.: УрГУ, 2000. – С.74-75.

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

– С. 47-55.

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

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

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

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

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

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

26. Умняшкин С. В. Алгоритм фрактального кодирования изображений в области вейвлет-преобразований // Комп`ютерна математика. Оптимiзацiя обчислень: Збiрник наукових праць. – Том 1. – Кив: Iнститут кiбернетики iм.

В.М.Глушкова, 2001. – С. 385-391.

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

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

29. Разработка алгоритмов и программного обеспечения для реализации цифрового анализа и компрессии видеоизображений в реальном масштабе времени на базе программно-аппаратного комплекса общего назначения: Отчет о НИР (закл.) / НПП «Технология»; рук. – Умняшкин С.В. – «Страж»; № гос.

рег. 01990011697; Инв. №01077. – Москва, 1999. – 74 с.

30. Исследование и разработка алгоритмов программного сжатия данных с потерями для цифровой обработки видеоизображений: Отчет о НИР (закл.) / НПП «Технология»; рук. – Умняшкин С.В. – «Дозор»; № гос. рег.

01200004624; Инв. №100704. – Москва, 2000. – 48 с.

Подписано в печать: 25 декабря 2001 года Заказ №332. Тираж 100 экз. Уч.-изд.л. 2,4. Формат 6084 1/