Частные случаи линейных преобразований

1.) Разделимые линейные преобразования

A(n₁, n₂, m₁, m₂) = A_c(n₁, m₁) ∙ A_s(n₂, m₂)

B(n₁, n₂, m₁, m₂) = B_c(n₁, m₁) ∙ B_s(n₂, m₂)

F = A_c ∙ F ∙ A_s^T

F = B_c ∙ ∙ B_s^T; B_c = A_c^-1; B_s = A_s^-1.

2.) Свёртка

V_R(x, y) = V_S(i, j) ∙ Q’(x-i, y-j)

A(x, i, y, j) – ядро.

Самое главное

L = (2m +1) (2n +1) – для каждой точки   сложность вычисления пространственной области. S1 = L ∙ N2

A

V_s F_s

B

[N*N]

[N*N]

	A

поэлементное умножение

[N*N]

[N*N]

Q’ F_Q

V_R(r₁, r₂) = V_S(i, j) ∙ Q’(r₁-i, r₂-j) (1)

F_s(m₁, m₂) = V_S(n₁, n₂) ∙ A(n₁, n₂, m₁, m₂) (2)

F_Q(q₁, q₂) = Q’(l₁, l₂) ∙ A(l₁, l₂, q₁, q₂) (3)

V_R(r₁, r₂) = F_R(p₁, p₂) ∙ B(p₁, p₂ , r₁, r₂) (4)

F_R(i,j) = F_S(i,j) ∙ F_Q(i,j) (5)

i, j = 0……………N-1.

Подставим величины из формул (2), (3), (5) в формулу (4).

В результата этого мы получим:

V_R(r₁, r₂) = ( V_S(n₁, n₂) ∙ A(n₁, n₂, p₁, p₂) ∙ Q’(l₁, l₂) ∙

A(l₁, l₂, p₁, p₂)) ∙ B(p₁, p₂ , r₁, r₂) = V_S(n₁, n₂) ∙ Q’(l₁, l₂) ∙ A(n₁, n₂, p₁, p₂) ∙ A(l₁, l₂, p₁, p₂) ∙ B(p₁, p₂ , r₁, r₂)

Выделенная в формуле подчёркиванием часть зависит только от ядер.

Она равна 1 при n₁= r₁ – l₁ или n₂= r₂ – l₂

0, иначе

d(n₁+l₁– r₁) ∙ d(n₂+l₂– r₂) (дельта – функция.)

d(x)

A(n₁, n₂, p₁, p₂) = A_S(n₁, p₁) ∙ A_C(n₂, p₂)

допущение

A_S = A_C = A

B_S = B_C = B

B(p₁, p₂, r₁, r₂) = B_S(p₁, r₁) ∙ B_C(p₂, r₂)

(**)

A(n₁, n₂, p₁, p₂) ∙ A(l₁, l₂, p₁, p₂) ∙ B(p₁, p₂ , r₁, r₂) = d(n₁+l₁– r₁) ∙ d(n₂+l₂– r₂)

d(x)

A(n₁, n₂, p₁, p₂) = A_S(n₁, p₁) ∙ A_C(n₂, p₂) (1)

A_S = A_C A’

B(p₁, p₂, r₁, r₂) = B’(p₁, r₁) ∙ B’(p₂, r₂) (2)

Воспользовавшись формулами (1) и (2) преобразуем выражение (**):

A’(n₁, p₁) ∙A’(l₁, p₁) ∙ B’(p₁, r₁) ∙ A’(n₂, p₂) ∙A’(l₂, p₂) ∙ B’(p₂, r₂) =

= d(n₁+l₁– r₁) ∙ d(n₂+l₂– r₂)

A’(n, p) = a^np ; A’(l, p) = a^lp ; B’(p, r) = a^-pr

a^p(n+l-r) = d (n+l– r)

n+l– r n

Пусть n = 0, N.

Эквивалентность выражения (*) докажем, домножив обе части уравнения на

(1 - aⁿ).

(1 - aⁿ) a^pn = a^pn - a^n(p+1) = 1+ a^pn - a^pN – a^nN =1 – (a^N)ⁿ = 0

1 = N∙ d(0); аналогично для n=N,-N.

Теперь уравнение (***) будет основным

Решим его:

a^N =1 = e^i∙2p - комплексное преобразование 1.

a = e^i∙2p/N – решение в области комплексных чисел.

Re + i∙Im

) = a^nm ∙F(n) = e^{i∙(2p/N) ∙n∙m} ∙F(n) =

= F(n) ∙cos ( ∙n ∙m) + i ∙ F(n) ∙sin( ∙n ∙m) =

	Re		Im

F(n) = ∙ a^-nm ∙ ) = e^{i∙(2p/N) ∙n∙m} ∙ ) = ) ∙cos ( ∙n ∙m) –

- i∙ ) ∙ sin( ∙n ∙m)

Связь между спектральными коэффициентами и корреляционной функцией

Пусть имеется входной сигнал, описываемый функцией F(n). Тогда квадрат коэффициента корреляции k равен:

k² = F(n) ∙ sin( ∙n ∙m +y) = F(n) ∙ sin( ∙n ∙m) ∙ cos(y) + F(n) ∙ cos( ∙n ∙m) ∙ sin(y)

Так как

Принимая , и , получим:

; ;

Оценка сложности:

1. Вычисляются спектральные коэффициенты строк

2. Вычисляются спектральные коэффициенты столбцов

Для каждого отсчета надо сделать N операций

,

где N — сложность вычисления одного коэффициента, k — коэффициент сложности работы с комплексными числами

Сложность прямого преобразования:

— это только по строкам

Аналогично получается сложность по столбцам

Тогда общая сложность:

— суммарная сложность прямого преобразования

S_S = S_пр + S_обр = 2N³∙k

k – коэффицент, отражающий специфику работы с комплексными числами.

Сравним S_S и S:

Проверка

Пусть N=512; k=2.

Ответ: L > 45. – выгодно использовать пространственное преобразование при больших фильтрах.