Книги по разным темам Pages:     | 1 | 2 | Электронный журнал ИССЛЕДОВАНО В РОССИИ 917 РЕАЛИЗАЦИЯ АЛГОРИТМА СЖАТИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЧЕБЫШЕВСКИХ ПРЕОБРАЗОВАНИЙ (АЛГОРИТМ GDCT) Ю.С. Радченко (rad@sendmail.ru) Воронежский госуниверситет Предложен метод сжатия изображения, основанный на разложении по полиномам Чебышева и применении квадратурных формул Гаусса - Чебышева (алгоритм GDCT). Показано, что алгоритм GDCT является обобщением дискретного косинусного преобразования, используемого в алгоритмах JPEG и MPEG. Алгоритм имеет четыре ступени сжатия: прореживание исходного изображения, усечение спектра, обнаружение изменяющихся фрагментов, определение вектора движения фрагментов. На примерах обработки искусственных текстур и натурных изображений продемонстрированы возможности алгоритма GDCT.

Системы связи нового поколения ориентированы на передачу информационных потоков различного вида, то есть являются мультимедийными телекоммуникационными системами [1,2]. В связи с этим передача телевизионных и компьютерных изображений, видеоконференции и видеосотовая связь предполагают применение процедур сжатия изображений. В последнее время выполнен ряд работ, в которых предлагается применять разложения по базису классических ортогональных полиномов Эрмита, Якоби (Лежандра, Чебышева) [3,4]. Эти преобразования обладают весьма компактными спектрами, которые чувствительны к сдвигу анализируемого фрагмента. В данной работе приводятся результаты исследования одного из вариантов полиномиальных преобразований - разложение и синтез по базису полиномов Чебышева I и II рода. Вычисление спектральных коэффициентов производится с помощью квадратурной формулы Гаусса - Чебышева, обладающей наивысшей степенью алгебраической точности при заданном числе отсчетов. Показано, что при этом получаются преобразования, которые являются обобщением дискретного косинусного и синусного преобразований.

1. Разложение сигналов по базису ортогональных полиномов.

Пусть в подобласти {x,y} наблюдается поле s(x,y,), представляющее собой фрагмент u(x,y)I(x, y) пространственного сигнала. Здесь I (x, y) - индикаторная функция подобласти, =(x, y) параметры сдвига фрагмента в данном кадре. Базисные функции mk(x,y), используемые для дискретного представления сигнала s(x,y,), определяются аналитическими свойствами самого сигнала и геометрической формой подобласти.

Однако, реализация процедуры сжатия, особенно для полиномиальных базисов, существенно упрощается, если имеет место факторизация функций mk(x,y)= m(x) k(y).Здесь m(x), k(y) - одномерные функции, основанные на ортогональных полиномах. Тогда для полезного сигнала s(x,y,) имеет место пара преобразований s(x,y,) = C ()m(x)k(y), Cmk () = mk s(x, y, )m (x)k (y)dxdy. (1) m k Для разложения сигналов и изображений можно применять следующие классические ортогональные многочлены: а) Эрмита; б) Лежандра; в) полиномы Чебышева I и II рода.

Если обозначить ax,ay - характерные размеры подобласти, z1=x/ax, z2=y/ay, то (1) можно переписать с использованием ортогональных полиномов в виде s(x, y) = C pm (x / ax )pk (y / ay ) mk m,k Электронный журнал ИССЛЕДОВАНО В РОССИИ 918 Cmk = (dmdk )-1 z1,ayz2 )(z1)pm (z1)(z2 )pk (z2 )dz1dz2 = s(ax (2) = (dmdk )-1 )pm (z1)dz1 z1,ayz2 )(z2 )pk (z2 )dz2.

(z1 s(ax Здесь dm - норма ортогонального с весом (z) полинома pm(z). Поскольку для разложимых базисных функций mk(x,y)= m(x) k(y) вычисление спектральных коэффициентов производится последовательным интегрированием по координатам (x,y), то для упрощения анализа рассмотрим сначала одномерные преобразования, а затем обобщим их на двумерный случай.

2. Алгоритм преобразований Чебышева.

Пусть имеется процесс f(z), квадратично интегрируемый с весом (z). Тогда можно записать квадратурную формулу гауссовского типа наивысшей алгебраической степени N точности порядка 2N-1 как f (z)(z)dz = f (zn ). Здесь zn - нули полиномов рN (z), n n=ортогональных с весом (z); n - числа Кристоффеля. Узлы и веса {zn}, {n} однозначно определяются видом ортогонального с весом (z) полинома рm(z). Для полиномов Чебышева получается формула Меллера (Гаусса-Чебышева) N -1 s(z)Tm (z) dz = s(z )Tm (zn ).(3) n dm -1 1 - z2 dmN n =Здесь zn=cos((2n+1)/2N) Цнули полинома Чебышева I рода TN(z); n=/N - то есть все весовые коэффициенты одинаковы, норма полинома Чебышева dm=/2, если m0, и dm=, если m=0. Учитывая, что Tm(zn)=cos(marccos(zn))=cos(m(n+0.5)/N), приходим к выражению для прямого и обратного преобразований N -1 N -2 n + 0.5 Cm = s(zn )cos(m ), C0 = s(z ) n N N N n=0 n=(4) M M 2 SM(z) = gm C Tm(z)= gm N C cos(m arccos(z)) m m N m=0 m= = 0.5, m Здесь gm =. В формуле (4) использована симметричная нормировка 1, m > базисных функций, удобная для практической реализации преобразований в матричном виде. Выражение (4) весьма похоже на так называемое четное дискретное косинусное преобразование (ДКП) [2]. Но имеет три важных отличия: 1)Точки отсчета zn = cos((n + 0.5) / N) сигнала s(z) берутся неравномерно. 2)Синтез сигнала SM(z) выполняется в произвольной точке z[-1,1], а не в дискретном наборе точек отсчета, как в ДКП. 3)Точность формулы (4) при преобразовании достаточно гладких функций существенно выше, чем у ДКП. Поэтому число отсчетов можно взять значительно меньше.

Если при восстановлении взять неравномерную сетку отсчетов по закону zj=cos((j+0.5)/L), j=0,ЕL-1, то обратное преобразование принимает вид M 2 j + 0.SM (z ) = gm Cm cos(m ). (5) j N L m=Преобразование (5) выглядит аналогично ДКП, однако спектральные коэффициенты отличаются от спектральных коэффициентов обычного ДКП. В том случае, если нас Электронный журнал ИССЛЕДОВАНО В РОССИИ 919 интересует равномерная сетка отсчетов zj=2j/(L-1) Ц1 +, где - некоторый сдвиг, j=0,ЕL-1, то M SM(z ) = gm C cos(m arccos(2 j/(L -1) -1 + ).(6) j m N m=Алгоритм преобразования (4), (6) назовем обобщенным дискретным косинусным преобразованием (GDCT). В формулах (5), (6) L число точек в блоке восстановленного изображения может быть произвольным. В таком случае возникает эффект масштабирования восстановленного изображения по сравнению с размерами исходного блока с изображением.

Если использовать разложение по полиномам Чебышева II рода, то получаем Cm = 1- z2s(z)Um(z)dz = -N-2 (k +1)(m +1) k += s(zk)sin( )sin( );

(7) N +1 N +1 N +k=M SM(z) = C Um(z).

m m=Здесь учтено, что zk=cos((k+1)/(N+1)) и sin((M +1)arccos(zk )) sin((k +1)(m +1) /(N +1)) Um(zk ) = = (8) sin((k +1) /(N +1)) 1- zk Алгоритм преобразований (7) сходен с дискретным синусным преобразованием Для использования квадратурных формул типа Гаусса (3) при переходе от интегральных преобразований к дискретным требуется определить число узлов N, обеспечивающее вычисление необходимого числа спектральных коэффициентов Cm с заданной точностью. Как уже указывалось выше, формулы типа Гаусса являются точными для всех полиномов l2N-1(z) степени 2N-1, а порядок ошибки формулы (3) |s(2N)(z)|. Однако эта оценка чисто качественная. Кроме того, ряд моделей полезных сигналов имеет ряд особых точек, в которых функция не дифференцируема. Поэтому необходимы расчеты для типовых моделей сигналов, с помощью которых можно оценить необходимое число отсчетов N. Вопросы точности аппроксимации сигналов и выбора числа узлов квадратурной формулы исследовались на примере следующих тестовых моделей: непрерывных дифференцируемых и недифференцируемых на множестве точек, финитных, разрывных (импульсных).

Например, если в качестве модельного сигнала, взять s(z) = 1 - z2, то точные значения спектральных коэффициентов имеют значения 1 s(z) CT = dz = 1- z-2 s(z)Tm(z) 1 1 CT = dx = (9) m m Tm+1(z) - m -1Tm-1(z) = - + 1- z-Электронный журнал ИССЛЕДОВАНО В РОССИИ 920 - при четном m > 0, = (m2 -1) 0 при нечетном m.

При вычислении по формуле (4) соответствующие коэффициенты имеют значения:

N -1 k + 0.C0 = sin( ), N N k=(10) N -2 k + 0.5 m(k + 0.5) Cm = sin( )cos( ).

N N N r=В таблице 1приведены значения CT и Сm при различном числе квадратурных точек N m (N=4,8,12,16).

Как видно из таблицы достаточно точно вычисляются коэффициенты с номером m3N/4.

Таблица m 0 246810 T 0.673 -0.424 -0.085 -0.036 -0.02 -0.013 -0.Cm Cm(N=4) 0.653 -0.383 -0 0.383 -1.307 0.Cm(N=8) 0.641 -0.416 -0.075 -0.023 0 0.023 0.Cm(N=12) 0.638 -0.421 -0.081 -0.032 -0.015 -0.0065 Cm(N=16) 0.638 -0.422 -0.083 -0.034 -0.018 -0.01 -0.Были исследованы ошибки восстановления сигналов с использованием метрик p 1/ p } dp(SM,S) ={ SM (x) - S(x) dx в пространстве Lp измеримых и интегрируемых функций для значений p=1,2,. Расчеты для различных классов сигналов показали достаточность 6-8 точек для использования чебышевских преобразований.

3. Блочные преобразования (GDCT).

Перейдем теперь к двумерному варианту преобразований сигнала s(x,y). Пусть в пределах блока из N1N1 точек, берутся отсчеты сигнала NN штук по закону xn = ROUND(0.5 (N1 - 1) (1 + cos((n + 0.5) / N))) yk = ROUND(0.5 (N1-1) (1 + cos((k + 0.5) / N))) (11) Отсчеты сигнала образуют матрицуS = snk = s(xn, yk ). Затем эта матрица преобразуется в матрицу спектральных коэффициентов C размером MM. При обратном преобразовании может использоваться прямоугольная матрица размером LM. То есть восстановленный блок имеет размеры LL. Прямое и обратное преобразование Чебышева (GDCT) в матричном виде определяются операциями C = C = ST S = TC (12) m,l Матрицы прямого и обратного преобразования GDCT имеют вид 0. = m (n) = (n + 0.5) NM N cos(m N 2 j () = cos m arccos(z ) = cos(m arccos( -1 + )) (13) j LM L -Электронный журнал ИССЛЕДОВАНО В РОССИИ 921 В частном случае можно полагать =0. Дискретизация аргументов {x,y} по правилу (11) приводит к появлению погрешности квадратурной формулы и неточному вычислению спектральных коэффициентов. Для уточнения расчетов можно произвести интерполяцию значения поля s(x,y) в точках расположения нулей полиномов Чебышева по ближайшим отсчетам.. Например, для этого можно использовать четырехточечную интерполяционную формулу Бесселя s(xn,yk)=0.25(s00+s01+s10+s11)+0.5(u-0.5)(s10-s00+s11-s01)+ +0.5(v-0.5)(s01-s00+s11-s10)+(u-0.5)(v-0.5)(s11-s10-s01+s00), (14) где u=xn-x00, v=yk-y00, si,j (i,j=0..1) - значения сигнала в ближайших четырех пикселях, окружающих точку xn,yk. Применение интерполяции улучшает передачу мелкомасштабной текстуры изображений при реализации процедуры сжатия - восстановления сигналов.

4. Результаты исследования алгоритма GDCT.

Итак, в блоке изображений размером N1N1 элементов выбирается матрица NN отсчетов (N

Для экспериментов был выбран набор искусственных изображений и натурных фотографий. Цветные изображения были представлены в 24 битовом формате BMP. С этими изображениями осуществлялись следующие операции. 1) Перекодировка 8-битовых R, G, B Цкомпонент цвета в Y,U,V по правилу: Y=int(0.299R+ 0.587G +0.114), U=int(R-Y=0.701R0.587G-0.114B), V= B-Y=int(-0.299R-0.587G+0.886B). 2) Субдискретизация матриц Y,U,V по одному из законов: 4:4:4, 4:2:2, 4:2:0. 3) Спектральное преобразование матриц Y,U,V на основе GDCT. В зависимости от типа изображения на первой ступени сжатия проводилось прореживание в пропорции N1/N=16/6, 16/8, 8/6. Затем проводилось преобразование спектральной матрицы C для реализации второй ступени сжатия изображения. 4) Для упрощения сопоставления исходного и восстановленного изображений проводилось восстановление блока размером N1N1, то есть было выбрано N1=L. Затем производилась визуальная оценка качества изображения. На фигурах 1-4 показаны результаты преобразований объекта типа портрет с помощью алгоритмов GDCT и JPEG. Степень сжатия за счет усечения спектров в алгоритмах JPEG и GDCT взята 5.6.Но в алгоритме GDCT проведено дополнительно сжатие первой ступени в 1.8 (фигура 2) и 4 раза (фигура 3).

Поскольку алгоритм сжатия и восстановления на основе чебышевских преобразований обладают свойством масштабирования восстановленных изображений по сравнению с оригиналами, было проведено исследование такой возможности GDCT. В зависимости от степени гладкости исходного изображения коэффициент пространственного увеличения (L/N1) может доходить до 20. Исследование преобразований типовых натурных изображений с резкими границами и мелкомасштабной текстурой показало, что при коэффициенте увеличения (L/N1)>4 начинает проявляться блочная структура изображений.

Выводы Исследования показали, что изображения с плавными градациями яркости и цвета могут быть подвергнуты сильному сжатию уже на I ступени процедуры. Насыщенные мелкими деталями текстуры и натурные изображения испытывают искажения в GDCT, и рекомендуемая степень сжатия I ступени порядка 30-50%. Скорость убывания спектров в GDCT такого же порядка, как и в классическом дискретном косинусном преобразовании.

Поэтому сжатие на II ступени такого же порядка, как и в алгоритме JPEG. Так как положение узлов полиномов Чебышева образуют дробные числа, то были исследованы Электронный журнал ИССЛЕДОВАНО В РОССИИ 922 две реализации GDCT - с округлением положения узлов до ближайшего пикселя, и с межпиксельной линейной интерполяцией. Эксперименты показали, что интерполяция улучшает передачу тонких деталей и наклонных краев изображений. Выполнено сравнение в статическом режиме алгоритмов сжатия GDCT и классического JPEG для различных типов изображений. Показано, что в зависимости от типа изображений алгоритм GDCT в статическом режиме позволяет увеличить степень сжатия до 3 раз по сравнению с алгоритмом JPEG.

Автор благодарен М.Ю. Радченко и к.т.н. А.Ю. Савинкову за помощь при разработке программного кодека алгоритма GDCT на языке С++.

итература 1. А.В. Дворкович, В.П. Дворкович, Б.Н. Мохин и др. Единые принципы сжатия цветных динамических изображений различного разрешения. Цифровая обработка сигналов, №1, 1999, с. 27-35.

2. Цифровая обработка телевизионных и компьютерных изображений./ Под ред. Ю.Б.

Зубарева и В.П. Дворковича. М.: МЦНТИ, 1997, - 217 с.

3. Ю.С. Радченко, М.Ю. Радченко Оптимальные быстрые алгоритмы представления изображений в базисе ортогональных полиномов. Труды I международной конференции Цифровая обработка сигналов и ее применения DSPA'98, 1998, Москва, т. III, с. 163-166.

Pages:     | 1 | 2 |    Книги по разным темам