Книги по разным темам Pages:     | 1 | 2 | Обратная классификация вейвлет-коэффициентов при компрессии изображений Ж Владимир Главнов, Андрей Крапивенко Московский Авиационный Институт, Москва, Россия Аннотация ность соседних коэффициентов в той же полосе и том же уровне декомпозиции.

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

выигрыш в степени компрессии статичных изображений при применении новой классификации.

2 КЛАССИФИКАЦИЯ ОТСЧЕТОВ Работа создана при поддержке гранта Президента РФ МК-1128.2003.01 СИГНАЛА Ключевые слова: классификация, компрессия изображеПредположим, что каждый класс Xi сигнала X кодируетния, вейвлет-преобразование ся со скоростью Ri и дает среднеквадратичное искажение Di(Ri), тогда согласно [5]:

Di(Ri) = i2i22-2Ri, (1) 1 ВВЕДЕНИЕ где i - константа, зависящая от схемы кодирования, а i2 На Международной Конференции по Обработке Изобра- - дисперсия отсчетов i-го класса. Задача классификации 1 на J классов сводится к минимизации искажения сигнала жения в 1994 было представлено сразу три, написанных независимо друг от друга работы по компрессии изобра- в целом:

J жений [1, 2, 3]. Сущность всех трех работ сводилась к min piDi(Ri), (2) одной идее, отличались они только тонкостями реализаi=ции.

где pi - вероятность попадания отсчета сигнала в класс Основой служило разделение сигнала высокочастотных Xi, при фиксированной средней скорости кодирования:

вейвлет-коэффициентов X на несколько частей {Xi} с заJ ведомо различными статистическими характеристиками.

piRi = R. (3) Далее эти части группировались в классы. Можно поi=казать, что суммарная энтропия этих частей, а следовательно и затраты на кодирование, может оказаться ниже, Воспользовавшись методом множителей Лагранжа, можчем энтропия исходного сигнала, поскольку происходит но найти минимальное искажение:

классификация упорядочивание отсчетов сигнала.

J В работе [4] был предложен метод обратной классификаj Dopt(R) = (4) (22)p 2-2R, j j ции. Данный метод, в большинстве случаев, дает меньj=шее качество классификации по сравнению с ранее уподостигается оно при:

мянутыми методами. Но при этом свободен от ряда недостатков последних и имеет меньший перерасход бит при кодировании, что дает ему преимущество при кодироRi = R + 0.5log2 j j. (5) вании на низких скоростях. Однако, при классифика(22)pj J=1 j j j ции коэффициентов, метод опирается только на актив При этом получаем выигрыш в величине искажения в e-mail: vglavnov@cboss.ru Ж e-mail:kav@elias.ru 2 x x 2-2RT Gc = (6) (22)pj 2-2R J=1 j j j раз, где RT скорость кодирования, которая складывается из скорости кодирования сигнала и скорости кодирования признаков принадлежности отсчетов сигнала к тому или иному классу:

International Conference on Image Processing 1994 RT = R + Rs. (7) International Conference Graphicon 2004, Moscow, Russia, Если при передаче информации от кодера к декодеру, фициентов (рис. 1). Активность коэффициента X33 опрепомимо сжатой информации об отсчетах, приходится пе- деляется по формуле:

редавать еще и информацию о принадлежности отсчетов сигнала к определенным классам, то классификация M(X33) = a0|X23| + a1|X32| + a2|X22|+ (8) называется прямой. Если декодер сам в состоянии опреa3|X24| + a4|X13| + a5|X31|, делить принадлежность каждого отсчета к его классу, основываясь на уже переданной информации о других где ai - некоторые весовые коэффициенты.

отсчетах, то классификация называется обратной.

3 КОМПРЕССИЯ ИЗОБРАЖЕНИЙ С ПРИМЕНЕНИЕМ КЛАССИФИКАЦИИ При разложении изображения по вейвлет-базису, низкочастотные коэффициенты имеют корреляционную модель подобную корреляционной модели исходного изображения. Поэтому к низкочастотным коэффициентам повторно применяется разложение по вейвлет-базису.

Высокочастотные коэффициенты разложения слабо коррелируют между собой, поэтому к ним применяется энтропийное кодирование. Сигнал высокочастотных коэффициентов имеет явно нестационарную природу, поскольку значимые отсчеты стремятся сосредотачиваться Рис. 2: Гистограммы отсчетов, распределенных по класв так называемых активных областях областях, где сам методом [4] для изображения Лена.

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

ась предсказанная активность коэффициента, его отноПри компрессии с применением прямой классифика- сят к тому или иному классу. Пример распределений отции, каждое направление разложения каждой субполосы счетов в отдельных классах для тестового изображения (кроме низкочастотной) изображения обычно разбивает- Лена с использованием фильтров CDF-97 приведен на ся на прямоугольные области и определяется принадлеж- рис. 2. Математические ожидания и дисперсии распреденость каждой области к определенному классу. Способов лений в классах приведены в таблице 1.

построения разбиения на классы достаточно много, основные из них описаны в [6].

Статистика Класс 0 Класс 1 Класс 2 Класс Мат.ожидание 0.0075 0.0083 -0.0272 0.Информация о принадлежности коэффициентов прямоДисперсия 1.4618 2.7450 4.6767 5.угольным областям передается декодеру, создавая тем самым некоторую избыточность битов.

Таблица 1: Статистические характеристики классов, построеных методом [4] для изображения Лена.

Существует масса способов уменьшить этот перерасход за счет использования зависимостей между соседними по площади и по субполосам блоками. Ряд из них описан в Ввиду отсутствия необходимости передавать информа[6].

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

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

мации.

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

X X X 31 4 ОРИГИНАЛЬНЫЙ МЕТОД КЛАСРис. 1: Шаблон оценки активности отсчета в методе [4].

СИФИКАЦИИ Один из методов обратной классификации приведен в [4].

Авторами данной работы было предложено определять Предлагаемый в работе метод основан на выделении активность каждого коэффициента, основываясь на зна- зон высокой активности высокочастотных коэффициенчениях соседних, уже переданных и определенных коэф- тов, основываясь на величине перепада уровней отсчетов International Conference Graphicon 2004, Moscow, Russia, изображения, полученного на предыдущем шаге восста- 4. Наращиваем уровень декомпозиции: s=s+1. Если новления (рис. 3). проведено недостаточное число декомпозиций: s < S, то возвращаемся к шагу 2.

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

1. Восстанавливаем низкочастотную область из L в L.

Инициализируем уровень декомпозиции: s = S - 1.

2. На основе восстановленного в L изображения, проводим вычисление значений активностей коэффициентов Vs: Mvs,m,n = |Lm+1,n - Lm,n|.

3. Находим значение максимальной активности:

Mmax = maxm,n Mvs,m,n и инициализируем пороги класMvs, j+сов: Mvs,0 = -,Mvs,J = Mmax,Mvs, j =, j = J - 1..4. Группируем коэффициенты из Vs в классы: CVs, j = {v : v Vs,Mvs, j-1 < Mvs,m,n <= Mvs, j}.

Рис. 3: Определение активности отсчета.

5. Итерационно улучшаем значения порогов исходя из минимизации критерия: pvs, jH(CVs, j), где H() J=L j Hоператор вычисления энтропии, pvs, j - вероятность VHпопадания коэффициента из Vs в класс j.

VH6. Квантуем сгруппированные по классам коэффици енты CVs, j = Qs, j(CVs, j). Деквантуем коэффициенты Vи восстанавливаем изображение (применяем обратное вейвлет преобразование) в L.

7. Квантованные коэффициенты CVs, j подвергаем Рис. 4: Способ разделения двумерной декомпозиции.

арифметическому кодированию.

Метод накладывает некоторые ограничения на способ 8. Выполняем шаги со второго по седьмой для гориразделения двумерного преобразования. В частности, зонтального направления.

высокочастотные коэффициенты не должны подвергать9. Снижаем уровень декомпозиции: s = s - 1. Если прося дальнейшему разложению. Как пример, можно исведено недостаточное число декомпозиций: s>=0, то пользовать преобразование, приведенное на рис. 4. Снавозвращаемся к шагу 2.

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

ную по DPCM низкочастотную субполосу L, пороги квантования направлений субполос Mvs, j и Mhs, j, и подвернутые арифметическому кодированию сгруп4.1 Алгоритм декомпозиции с классификацией пированные по классам коэффициенты направлений субполос Vs, j и Cs, j.

Задача: провести S-уровневую декомпозицию изображения X = {Xm,n} и провести разделение высокочастотных коэффициентов на J классов.

Алгоритм двупроходный.

Прямой проход:

1. Инициализируем уровень декомпозиции: s=0. Инициализируем область низкочастотных коэффициентов L начальным изображением.

2. Проводим декомпозицию области низкочастотных Рис. 5: Декомпозиции тестового изображения Лена.

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

4.2 Пример классификации с использованием предложенного метода 3. Проводим декомпозицию области низкочастотных коэффициентов по столбцам изображения. Полученную область низкочастотных коэффициентов запо- В качестве примера было взято тестовое изображение минаем в L, полученную область высокочастотных Лена. Для разложения применялась лифтинговая схекоэффициентов запоминаем в Vs. ма преобразования с кубическим предсказанием (рис. 5).

International Conference Graphicon 2004, Moscow, Russia, Исходн Клас Выигрыш % V2 0.507160 0.413012 18.H2 1.106624 0.965310 12.V1 0.279689 0.219135 21.H1 0.614068 0.518748 15.V0 0.041457 0.033975 18.H0 0.183458 0.147336 19.Таблица 3: Энтропии исходного сигнала, сигнала после классификации и выигрыши от классификации.

5 ЗАКЛЮЧЕНИЕ Приведенный пример показывает, что описанный метод классификации заслуживает детального рассмотрения и более глубокого исследования.

Возможными путями развития метода являются:

Рис. 6: Гистограммы отсчетов H0, распределенных по классам оригинальным методом классификации.

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

Х использование более сложных шаблонов предсказаПри этом использовался однородный неадаптивный ния активности отсчетов;

квантователь, шаг которого подбирался под скорость выходного потока 0.2 бита в секунду (при идеальном ариф- Х использование метода с нестандартными схемами разделения двумерного преобразования и нераздеметическом кодере).

яемыми двумерными преобразованиями;

Х использование в методе сеточного квантования.

Статистика Кл.1 Кл.2 Кл.3 Кл.4 Кл.Мат.ожид. 0.001 0.003 0.007 0.013 -0.Описанный метод может показать сравнимые, а в ряде Дисперсия 0.003 0.013 0.034 0.085 0.случаев и превосходящие результаты по сравнению с суЭнтропия 0.030 0.098 0.215 0.443 1.ществующими на сегодняшний день методами классифиПорог 0 4 9 21 кации вейвлет-коэффициентов Кол-во 73544 23094 18799 8751 отсчетов Список литературы Таблица 2: Статистические характеристики классов H0, распределенных по классам оригинальным методом классификации.

[1] H. Jafarkhani, N. Farvardin, C.-C. Lee Adaptive image coding based on the discrete wavelet transform Proc. Int. Conf. Image Proc. vol. 3, pp. 343-347, На рис. 6 приведены гистограммы значений отсчетов, 1994.

распределенных по классам для H0. Из них видно, что распределения в классах сохраняют свой вид и могут [2] R. L. Joshi, T. R. Fischer, R. H. Bamberger быть аппроксимированы обобщенным распределением Optimum>

чи на арифметический декодер только трех параметров [3] J. H. Kasner, M. W. Marcellin Adaptive wavelet coding of распределения.

images Proc. Int. Conf. Image Proc. vol. 3, pp. 358-362, 1994.

В таблице 2 приведены некоторые статистические характеристики классов, полученных оригинальным методом [4] Y. Yoo, A. Ortega, B. Yu Image subband coding using классификации. Из них можно сделать ряд выводов. Перprogressive>

вое: математические ожидания в классах близки к нулю of the 4th Human Tech Thesis Prize, Korea, 1998.

и в большинстве случаев могут быть заменены нулями.

[5] N. S. Jayant, P. Noll Digital coding of waveforms PrenticeВторое: число отсчетов в классах с меньшей дисперсиHall, Englewood Cliffs, 1984.

ей гораздо выше, чем в классах с большей дисперсией, в подходе предложенном в [4] такой закономерности не [6] R. L. Joshi, H. Jafarkhani, J. H. Kasner, T. R. Fischer, наблюдалось.

N. Farvardin, M. W. Marcellin, R. H. Bamberger Comporision of different methods of> Pages:     | 1 | 2 |    Книги по разным темам