離散正交轉換

来自testwiki
跳转到导航 跳转到搜索

Template:Copyedit 數學上，任一的M×N離散線性轉換皆可表示成矩陣（Matrix） 的型式：𝒀=𝑨𝑿

[y[0]y[1]y[2]⋮y[M−1]]=[a0[0]a0[1]a0[2]⋯a0[N−1]a1[0]a1[1]a1[2]⋯a1[N−1]a2[0]a2[1]a2[2]⋯a2[N−1]⋮⋮⋮⋱⋮aM−1[0]aM−1[1]aM−1[2]⋯aM−1[N−1]][x[0]x[1]x[2]⋮x[N−1]].

𝐂𝐀𝐒𝐄𝟏

再進一步假設，若矩陣𝑨 by正交基底 (Orthogonal basis) 列向量（Row vector） 所組成：

[𝝓0∗𝝓1∗𝝓2∗⋮𝝓M−1∗]=[ϕ0∗[0]ϕ0∗[1]ϕ0∗[2]⋯ϕ0∗[N−1]ϕ1∗[0]ϕ1∗[1]ϕ1∗[2]⋯ϕ1∗[N−1]ϕ2∗[0]ϕ2∗[1]ϕ2∗[2]⋯ϕ2∗[N−1]⋮⋮⋮⋮⋮ϕM−1∗[0]ϕM−1∗[1]ϕM−1∗[2]⋯ϕM−1∗[N−1]]=𝑨.

也可表示成級數和形式（Summation form）：

y[m]=⟨𝝓m∗,x[n]⟩=∑n=0N−1ϕm∗[n]x[n],for m=0,1,⋯,M−1.

其中⟨⋅,⋅⟩代表內積運算（Inner product）。

𝐂𝐀𝐒𝐄𝟐

同理也可假設，若矩陣𝑨 by正交基底行向量（Column vector） 所組成：

[𝜷0∗𝜷1∗𝜷2∗⋯𝜷N−1∗]=[β0∗[0]β1∗[0]β2∗[0]⋯βN−1∗[0]β0∗[1]β1∗[1]β2∗[1]⋯βN−1∗[1]β0∗[2]β1∗[2]β2∗[2]⋯βN−1∗[2]⋮⋮⋮⋮⋮β0∗[M−1]β1∗[M−1]β2∗[M−1]⋯βN−1∗[M−1]]=𝑨.

也可表示成級數和：

y[m]=∑n=0N−1x[n]βn∗[m],for m=0,1,⋯,M−1.

假若M=N時，則det(A)≠0可得

{Y=AX(Forward transform)X=A−1X(Inverse transform).

離散正交轉換

大致上，可簡單化將矩陣分類由（a）列向量（Row Vector）或（b）行向量（Column Vector）所組成。

正交矩陣by列向量：

𝑨=[𝝓0∗𝝓1∗𝝓2∗⋮𝝓M−1∗]

若{⟨𝝓l∗,𝝓k∗⟩=∑n=0N−1ϕl∗[n](ϕk∗[n])T=0,when l≠k⟨𝝓l∗,𝝓l∗⟩=∑n=0N−1ϕl∗[n](ϕl∗[n])T=Cl=Constant,

其中，𝝓0∗,𝝓1∗,𝝓2∗,…,和𝝓M−1∗為一組列向量的正交集合且稱𝑨 為一種離散正交轉換。

再者，若滿足Cl=1,for any l。則𝝓0∗,𝝓1∗,𝝓2∗,…,和𝝓M−1∗將組成一組列向量的正規化正交集合且稱𝑨 為一種離散正規化正交轉換。

此時，我們可利用𝝓0∗,𝝓1∗,𝝓2∗,…,和𝝓M−1∗來求得𝑨的反矩陣：

𝑨−1=[C0−1ϕ0∗[0]C1−1ϕ1∗[0]C2−1ϕ2∗[0]⋯CN−1−1ϕN−1∗[0]C0−1ϕ0∗[1]C1−1ϕ1∗[1]C2−1ϕ2∗[1]⋯CN−1−1ϕN−1∗[1]C0−1ϕ0∗[2]C1−1ϕ1∗[2]C2−1ϕ2∗[2]⋯CN−1−1ϕN−1∗[2]⋮⋮⋮⋱⋮C0−1ϕ0∗[M−1]C1−1ϕ1∗[M−1]C2−1ϕ2∗[M−1]⋯CN−1−1ϕN−1∗[M−1]],

其中Cm=⟨𝝓m∗,𝝓m∗⟩。再者，也可表示成級數和（Summation）形式：

x[n]=∑m=0N−1Cm−1ϕm∗[n]y[m],for n=0,1,⋯,N−1.

若Cm=1，即簡化成，

x[n]=∑m=0N−1ϕm∗[n]y[m],for n=0,1,⋯,N−1.

正交矩陣by行向量：

𝑨=[𝜷0∗𝜷1∗𝜷2∗⋯𝜷N−1∗]

若{⟨𝜷l∗,𝜷k∗⟩=∑m=0M−1(βl∗[m])Tβk∗[m]=0,when l≠k⟨𝜷l∗,𝜷l∗⟩=∑m=0M−1(βl∗[m])Tβl∗[m]=Cl=Constant,

其中，𝜷0∗,𝜷1∗,𝜷2∗,…,和𝜷N−1∗為一組行向量的正交集合且也稱𝑨 是一種離散正交轉換。

再者，若滿足Cl=1,for any l。則𝜷0∗,𝜷1∗,𝜷2∗,…,和𝜷N−1∗將組成一組行向量的正規化正交集合且稱𝑨 為一種離散正規化正交轉換。

此時，我們再利用𝜷0∗,𝜷1∗,𝜷2∗,…,和𝜷N−1∗來組成𝑨的反矩陣：

𝑨−1=[C0−1β0∗[0]C0−1β0∗[1]C0−1β0∗[2]⋯C0−1β0∗[N−1]C1−1β1∗[0]C1−1β1∗[1]C1−1β1∗[2]⋯C1−1β1∗[N−1]C2−1β2∗[0]C2−1β2∗[1]C2−1β2∗[2]⋯C2−1β2∗[N−1]⋮⋮⋮⋱⋮CM−1−1βM−1∗[0]CM−1−1βM−1∗[1]CM−1−1βM−1∗[2]⋯CM−1−1βM−1∗[N−1]],

其中Cn=⟨𝜷n∗,𝜷n∗⟩。再者，也可表示成級數和：

x[n]=Cn−1∑m=0N−1βn∗[m]y[m],for n=0,1,⋯,N−1.

若Cn=1，即簡化成，

x[n]=∑m=0N−1βn∗[m]y[m],for n=0,1,⋯,N−1.

例子

如：哈恩轉換、Krawtchouk多項式、Charlier多項式。

特性

  • 其列向量型式與行向量型式為一體兩面的情形：
    • 順向轉換（Forward Transform）：列向量型式⟹反向轉換（Inverse Transform）：行向量型式。
    • 順向轉換（FT）：行向量型式⟹反向轉換（IT）：列向量型式。
  • 於正規化正交情況下：

優點

  • 彼此間的列向量（或行向量）不會互相產生干擾（Interference）。
    • 在同一維度（dimension）下，DOT提供正交矩陣內的列向量（或行向量） 彼此間重要的正交特性，可藉由此避免其他使用者干擾進而來實現多工存取技術。

𝑶𝒓𝒕𝒉𝒐𝒈𝒏𝒂𝒍:⟨𝝓l∗,𝝓k∗⟩=∑n=0N−1ϕl∗[m]ϕk∗[m]=0,when l≠k.

  • 其本身的FT與對應的IT結構為相當類似。
  • 此外，離散正交轉換較非正交轉換（Non-orthogonal Transform）計算上較為簡單。
  • 將DOT應用於影像重建（Reconstruction） 或壓縮上，可藉由增加正交基底（Orthogonal basis）來控制誤差的產生，是採用非正交轉換所能及的。

應用於影像重建

通常對於影像重建或壓縮上大都採用局部重建（Parital reconstruction）的機制，即：

(a) 正交情況下

xk[n]=∑m=0K−1Cm−1y[m]ϕm∗[n],for K<N.

因此，對於局部重建所產生的平方誤差（Sqaure error）： ‖x[n]−xk[n]‖2=∑n=0N−1‖∑m=kN−1Cm−1y[m]ϕm[n]‖2=∑n=0N−1∑m=kN−1Cm−1y[m]ϕm[n]∑h=kN−1Ch−1y∗[h]ϕh∗[n]=∑m=kN−1Cm−1| y[m]|2.

從此結果可發現Cm−1| y[m]|2必定為正的，因此可藉由增加正交基底數來改善影像重建後的平方誤差值。

（b）非正交情況下

xk[n]=∑m=0K−1B[n,m]y[m],for K<N.

因此，對於局部重建所產生的平方誤差： ‖x[n]−xk[n]‖2=∑n=0N−1‖∑m=kN−1B[n,m]y[m]‖2=∑m=kN−1∑h=kN−1y[m]y∗[h]∑n=0N−1B[n,m]B∗[n,h].

從此結果可發現y[m]y∗[h]∑n=0N−1B[n,m]B∗[n,h]不一定為正的，所以無法利用增加基底數來改善平方誤差。

參閱

參考文獻

检索自“https://zh.wiki.beta.math.wmflabs.org/w/index.php?title=離散正交轉換&oldid=4507”