Строительные исследования

назад Оглавление вперед

страница - 0

РЕАЛИЗАЦИЯ АЛГОРИТМА СЖАТИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЧЕБЫШЕВСКИХ ПРЕОБРАЗОВАНИЙ (АЛГОРИТМ GDCT)

Ю.С. Радченко (rad@sendmail.ru)

Воронежский госуниверситет

Предложен метод сжатия изображения, основанный на разложении по полиномам Чебышева и применении квадратурных формул Гаусса - Чебышева (алгоритм GDCT). Показано, что алгоритм GDCT является обобщением дискретного косинусного преобразования, используемого в алгоритмах JPEG и MPEG. Алгоритм имеет четыре ступени сжатия: прореживание исходного изображения, усечение спектра, обнаружение изменяющихся фрагментов, определение вектора движения фрагментов. На примерах обработки искусственных текстур и натурных изображений продемонстрированы возможности алгоритма GDCT .

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

Пусть в подобласти (x,y}eQ наблюдается поле s(x,y,x), представляющее собой фрагмент u(x,y)IQ(x,y) пространственного сигнала. Здесь IQ (x, y) - индикаторная функция подобласти, T=(tx, Ty) параметры сдвига фрагмента в данном кадре. Базисные функции <pmk(x,y), используемые для дискретного представления сигнала s(x,y,x), определяются аналитическими свойствами самого сигнала и геометрической формой подобласти Q. Однако, реализация процедуры сжатия, особенно для полиномиальных базисов, существенно упрощается, если имеет место факторизация функций <pmk(x,y)= <pm(x) (pk(y).Здесь (pm(x), (pk(y) - одномерные функции, основанные на ортогональных полиномах. Тогда для полезного сигнала s(x,y,x) имеет место пара преобразований

s(x,y,т) = XECmk(mWPkX Cmk(T) = JJs(x,y5т)(рm(x)(pk(y)dxdy- (1) mkQ

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

ортогональные многочлены: а) Эрмита; б) Лежандра; в) полиномы Чебышева I и II рода.

Если обозначить ax,ay - характерные размеры подобласти Q, z1=x/ax, z2=y/ay, то (1) можно

переписать с использованием ортогональных полиномов в виде

s(x,y) = X Cmkpm(x/ax)pk(y/ay)

m,k

Cmk = (dmdk) 1 JJ s(axz1 ,ayz2)p(z1 )pm(z1 )p(z2)pk(z2)dz1dz2 =

О*(2)

= (dmdk)-1 Jp(z1 )pm(z1 )dz1 J s(axz1 ,ayz2)p(z2)pk(z2)dz2. Здесь dm - норма ортогонального с весом p(z) полинома pm(z). Поскольку для разложимых базисных функций 9mk(x,y)= cpm(x) cpk(y) вычисление спектральных коэффициентов производится последовательным интегрированием по координатам (x,y), то для упрощения анализа рассмотрим сначала одномерные преобразования, а затем обобщим их на двумерный случай.

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

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

точности порядка 2N-1 как J f(z)p(z)dz = IАnf(zn) . Здесь zn - нули полиномов рN (z),

n=1

ортогональных с весом p(z); An - числа Кристоффеля. Узлы и веса {zn}, {An} однозначно определяются видом ортогонального с весом p(z) полинома рш). Для полиномов Чебышева получается формула Меллера (Гаусса-Чебышева)

dm -1 V1 - z2dmNn=0

Здесь zn=cos(n(2n+1)/2N) -нули полинома Чебышева I рода TN(z); An=n/N - то есть все весовые коэффициенты одинаковы, норма полинома Чебышева dm=n/2, если m0, и dm=n, если m=0. Учитывая, что Tm(zn)=cos(m-arccos(zn))=cos(nm(n+0.5)/N), приходим к выражению для прямого и обратного преобразований

1 N-1 C0 = J- I s(zn)

n=0NVNn=0

SM(z) = gm

2 m[2 m

N ICmTm(z)= §11117 ICm

N m =0

cos(m • arccos(z))

Nm=0

, /0.5 ,m = 0

Здесь gm = <. В формуле (4) использована симметричная нормировка

1 ,m > 0

базисных функций, удобная для практической реализации преобразований в матричном виде. Выражение (4) весьма похоже на так называемое четное дискретное косинусное преобразование (ДКП) [2]. Но имеет три важных отличия: 1)Точки отсчета zn = cos(n(n + 0.5)/N) сигнала s(z) берутся неравномерно. 2)Синтез сигнала SM(z)

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

Если при восстановлении взять неравномерную сетку отсчетов по закону zj=cos(n(j+0.5)/L), j=0,.. .L-1, то обратное преобразование принимает вид

S ( )2 M C ( j + 0.5)

sm(zj) = gnn - I Cmcos(nm--).

N m=0L

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

интересует равномерная сетка отсчетов zj=2j/(L-1) -1 +8, где 8 - некоторый сдвиг, j=0,.. Х-1,

то

SM(zj) ёш-

2 м N ЕСш

N ш=0

cos(m • arccos(2j /(L -1) -1 + 8)

(6)

Алгоритм преобразования (4), (6) назовем обобщенным дискретным косинусным преобразованием (GDCT) . В формулах (5), (6) L число точек в блоке восстановленного изображения может быть произвольным. В таком случае возникает эффект масштабирования восстановленного изображения по сравнению с размерами исходного блока с изображением. Если использовать разложение по полиномам Чебышева II рода, то получаем

Сш = - ]л11 - z2s(z)Um(z)dz = 1

N+. Е s(zk)sin(nV J , л )sin(n);

N +1

ivi

Sm(z) = Е CmUm(z). Здесь учтено, что zk=cos(n(k+1)/(N+1)) и

(7)

Um(zk):

sin((M +1) arccos(zk)) = sin(n(k + 1)(m +1) /(N +1))

1 - zk

sin( (k +1) /(N +1))

(8)

Алгоритм преобразований (7) сходен с дискретным синусным преобразованием

Для использования квадратурных формул типа Гаусса (3) при переходе от интегральных преобразований к дискретным требуется определить число узлов N, обеспечивающее вычисление необходимого числа спектральных коэффициентов Сш с заданной точностью. Как уже указывалось выше, формулы типа Гаусса являются точными для всех полиномов l2N-1(z) степени 2N-1, а порядок ошибки формулы (3) e~s(2N)(z). Однако эта оценка чисто качественная. Кроме того, ряд моделей полезных сигналов имеет ряд особых точек, в которых функция не дифференцируема. Поэтому необходимы расчеты для типовых моделей сигналов, с помощью которых можно оценить необходимое число отсчетов N. Вопросы точности аппроксимации сигналов и выбора числа узлов квадратурной формулы исследовались на примере следующих тестовых моделей: непрерывных дифференцируемых и недифференцируемых на множестве точек, финитных, разрывных (импульсных).

Например, если в качестве модельного сигнала, взять s(z) = V1 - z2

то точные

значения спектральных коэффициентов имеют значения

1 s(z)

T = 2 }s(z)Tm(z)dx = 1

С= m

п-1 л/1 - z2

+ Tm +1(z)"

m-1

(z)

--1

(9)

содержание:
[стр.Введение] [стр.1] [стр.2]