Быстрый алгоритм аппроксимации изображения в скользящем окне

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

• 2.Локальная аппроксимация изображения

Пусть х(ш,п) - функции яркости изображения в точке Qiipi^eG, G - область определения изображения. Аппроксимация изображения х(м,л) в симметричном прямоугольном окне И^{ (А',О | -MsksM, -N^kN } размером (2М+1)х(2Л'+1) заключается в том, что для каждого положения центра окна ишется приближенное представление функции яркости в виде полинома степени Р.

x(m-k,n-iy £ a^m,n) k'l', U-Пей                                      (1)

(m,n)t?G , (k,l)e W где D={ (zj) | (УУР, УуР, O^j^P } - множество показателей степеней, соответствующих полиному степени Р. Заметим, что коэффициенты полинома а^т,л) являются функциями от положения центра окна (/щи).

Найдем коэффициенты а^т.п) в (1) из условия минимума среднеквадратичной ошибки аппроксимации:

е2(т,л) = £ -x^m-k.n-^-x^m-k.n-^2 - min tk.l^W по коэффициентам полинома, получаем систему линейных уравнений относительно неизвестных коэффициентов:

Е e^fVa^m.nl^p^m.n) , (s.r)eQ ,   (2)

UPeQ где pst(m,n)= ^ к*Гх(.т-к,п-1) -моментфунк-(k.l)eW ции яркости изображения порядка (уд) при положении центра окна в точке ^т.п). 6s t= V ksl' (k.l)eW

- постоянные коэффициенты, определяемые размерами окна И<

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

Рассмотрим случай аппроксимации квадратичным полиномом:

x(m-*,n-/)=A(m,n)*2^S(m,n)*/+(3)

+ С(л7,л)л2+£?(л?,л)А+Е’(т1л)/+Г(л?,л)

Решение системы (2) в этом случае будет иметь следующий вид:

А(т,л) =

ЕЦт.пу

45 ^(ЛТ, л)--------- J

M^M^2N^8M³*A2M²-2M-3^ ___ 9Ац( т.л)___

M(M*1)/V(^1)(2M+1)(2M-1) ’

С(Л7,Л) =

0(П7,Л) =

Е^т.пу

F(m,ny

^Ау^т.пУ 45 ^ог(т,л)J

N(N-1)(2AM)(8N3 + 12N?-2N3)

Зн0(л7,л)

М(АМ)(2АМ)(2АМ) ’

3-ц₀₁(т ,л)

А/(АМ)(2ЛМ)(2АМ) *

Иоо(т,л)

(2ЛМ)(2М+1)

Ц^.пу ^^^

(2^-1)(8М3^12М2-2М-3)

1ц02(т,л)--—- — J

(2ЛМ)(8А/М2Л/² 2N 3)

Из выше приведенных формул видно, что вычислительная сложность алгоритма локаль-

Приравнивая нулю частные производные

ной аппроксимации определяется, в основном, затратами времени на вычисление моментных характеристик ц,^т,пУ

• 3.    Рекурсивный алгоритм вычисления моментов.

Сначала построим рекурсивный алгоритм для расчета моментных характеристик функции одной переменной. Момент порядка к в точке п определяется по формуле:

N v^Y. skx(n-s} .

*=-N

Установим связь между ^к(и) и моментами р0(/г-1), Pi(«-1),—, Pk(«-i) в предыдущей точке (л-1):

N            ЛМ

52 skx(n-sV 52 s*x(n-s)+(-W)*x(n+W)-e=-N«—IM

(NA^n-NA)

W*1

52 SkX(.n-sV 52 (s+1)*x(n-1-s)= s—fMs—N

N кк

-£ ^с^х^и-^сЬф-^.

»=-N /=0/=О где Ск' - биноминальные коэффициенты.

Таким образом, рекуррентное соотношение для вычисления моментов функции одной переменной имеет вид:

^п>У С/*р_/(л-1)*(-Л/)*х(л+Л/)-       ₍₄₎

АНА^х^п-МА^ .

По аналогии с (4) получим рекурсивный алгоритм расчета моментных характеристик функции двух переменных:

ц^т.л)^ C/-n;(m-1,n)*(-*f)*x(m+/V,n)-мо

I

Ukil^m-ⁿ) =Е C* H*/(m,n-1) A-N)^^m,n*N)-

Л»

ANAy^m,n-NA^ .

Данный алгоритм позволяет за один проход изображения скользящим окном вы-числить все требуемые моментные характеристики за счет некоторого увеличения требуемого объема оперативной памяти для хране ния промежуточных одномерных моментов рк(л),Л-0,..., Р. Другой особенностью алгоритма является независимость объема вычислений от размеров окна обработки (23/+1)(2.У+1).

Для случая аппроксимации квадратичным полиномом (3) требуется вычислить моменты до второго порядка включительно, и система (5) принимает следующий вид:

цДт,л)=р0(т-1,л)+х(т<-М,л)-х(т-М-1,/7)

^m.ri^v^mA ,п) ^(т-1 ,л) -

+Мх(т*М,л)-(АМ)х(т-М-1,л)

ц2(т,^=н0(т-1, л) +2-^ (т-1 ,л) *

*ц2(т-1,л) + М2х(т+М,л)-(М+1)2х(т-М-1,п)

Цад(т,л)=1100(т,л-1)+р0(т1л*/У)-^

ц01(т,л)=ц00(т,л-1) *BOi(m. л-1) -

-М ц0(т,л+/У)-(/УИ) р0(т,л-А/-1)(6)

рО2(т,л) = Роо(т,п-1)+2цО1(т,п-1) + *и02(т,л-1)+Л/2ц0(т,л+ЛО-

-(^1)2110(т,л-А/-1)

и10(т,л)=ц10(т,л-1)^1(т,л*А/)-ц1(т,л-У-1) р11(т,л)=ц10(т,л-1)*р11(т,л-1)-

-/V-n^m.n+AO-tAMpn^m.n-N-l)

Vi20(1m,ri) = \i20(lm,n-AV^m>n^-vi2(m.n-N-A') .

Для расчетов моментов по рекуррентным соотношениям (6) требуется лишь 10 операций умножения и 27 операций сложения для каждого положения окна (умножение на два считается сложением). Рассмотренный алгоритм существенно эффективнее метода непосредственного вычисления моментов, для которого в данном случае требуется приблизительно 6(2Л/+1)(2У+1) операций умножения и сложения. Как показывает анализ, рекурсивный алгоритм вычисления моментов также эффективнее вычислений на основе быстрых алгоритмов дискретного преобразования Фурье.

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

1. Треногин В А. Функциональный анализ. М.: