離散正交轉換

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

$[\begin{matrix} y [0] \\ y [1] \\ y [2] \\ ⋮ \\ y [M - 1] \end{matrix}] = [\begin{matrix} a_{0} [0] & a_{0} [1] & a_{0} [2] & \dots & a_{0} [N - 1] \\ a_{1} [0] & a_{1} [1] & a_{1} [2] & \dots & a_{1} [N - 1] \\ a_{2} [0] & a_{2} [1] & a_{2} [2] & \dots & a_{2} [N - 1] \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{M - 1} [0] & a_{M - 1} [1] & a_{M - 1} [2] & \dots & a_{M - 1} [N - 1] \end{matrix}] [\begin{matrix} x [0] \\ x [1] \\ x [2] \\ ⋮ \\ x [N - 1] \end{matrix}] .$

$𝐂 𝐀 𝐒 𝐄 𝟏$

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

$[\begin{matrix} ϕ_{0}^{*} \\ ϕ_{1}^{*} \\ ϕ_{2}^{*} \\ ⋮ \\ ϕ_{M - 1}^{*} \end{matrix}] = [\begin{matrix} ϕ_{0}^{*} [0] & ϕ_{0}^{*} [1] & ϕ_{0}^{*} [2] & \dots & ϕ_{0}^{*} [N - 1] \\ ϕ_{1}^{*} [0] & ϕ_{1}^{*} [1] & ϕ_{1}^{*} [2] & \dots & ϕ_{1}^{*} [N - 1] \\ ϕ_{2}^{*} [0] & ϕ_{2}^{*} [1] & ϕ_{2}^{*} [2] & \dots & ϕ_{2}^{*} [N - 1] \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ ϕ_{M - 1}^{*} [0] & ϕ_{M - 1}^{*} [1] & ϕ_{M - 1}^{*} [2] & \dots & ϕ_{M - 1}^{*} [N - 1] \end{matrix}] = 𝑨 .$

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

$y [m] = ⟨ ϕ_{m}^{*}, x [n] ⟩ = \sum_{n = 0}^{N - 1} ϕ_{m}^{*} [n] x [n], for m = 0, 1, \dots, M - 1 .$

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

$𝐂 𝐀 𝐒 𝐄 𝟐$

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

$[\begin{matrix} β_{0}^{*} & β_{1}^{*} & β_{2}^{*} & \dots & β_{N - 1}^{*} \end{matrix}] = [\begin{matrix} β_{0}^{*} [0] & β_{1}^{*} [0] & β_{2}^{*} [0] & \dots & β_{N - 1}^{*} [0] \\ β_{0}^{*} [1] & β_{1}^{*} [1] & β_{2}^{*} [1] & \dots & β_{N - 1}^{*} [1] \\ β_{0}^{*} [2] & β_{1}^{*} [2] & β_{2}^{*} [2] & \dots & β_{N - 1}^{*} [2] \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ β_{0}^{*} [M - 1] & β_{1}^{*} [M - 1] & β_{2}^{*} [M - 1] & \dots & β_{N - 1}^{*} [M - 1] \end{matrix}] = 𝑨 .$

也可表示成級數和：

$y [m] = \sum_{n = 0}^{N - 1} x [n] β_{n}^{*} [m], for m = 0, 1, \dots, M - 1 .$

假若 $M = N$ 時，則 $d e t (A) \neq 0$ 可得

${\begin{matrix} Y = A X & (Forward transform) \\ X = A^{- 1} X & (Inverse transform) \end{matrix} .$

離散正交轉換

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

正交矩陣by列向量：

$𝑨 = [\begin{matrix} ϕ_{0}^{*} \\ ϕ_{1}^{*} \\ ϕ_{2}^{*} \\ ⋮ \\ ϕ_{M - 1}^{*} \end{matrix}]$

若 ${\begin{matrix} ⟨ ϕ_{l}^{*}, ϕ_{k}^{*} ⟩ = \sum_{n = 0}^{N - 1} ϕ_{l}^{*} [n] {(ϕ_{k}^{*} [n])}^{T} = 0, when l \neq k \\ ⟨ ϕ_{l}^{*}, ϕ_{l}^{*} ⟩ = \sum_{n = 0}^{N - 1} ϕ_{l}^{*} [n] {(ϕ_{l}^{*} [n])}^{T} = C_{l} = C o n s t a n t \end{matrix},$

其中， $ϕ_{0}^{*}, ϕ_{1}^{*}, ϕ_{2}^{*}, \dots,$ 和 $ϕ_{M - 1}^{*}$ 為一組列向量的正交集合且稱 $𝑨$ 為一種離散正交轉換。

再者，若滿足 $C_{l} = 1, for any l$ 。則 $ϕ_{0}^{*}, ϕ_{1}^{*}, ϕ_{2}^{*}, \dots,$ 和 $ϕ_{M - 1}^{*}$ 將組成一組列向量的正規化正交集合且稱 $𝑨$ 為一種離散正規化正交轉換。

此時，我們可利用 $ϕ_{0}^{*}, ϕ_{1}^{*}, ϕ_{2}^{*}, \dots,$ 和 $ϕ_{M - 1}^{*}$ 來求得 $𝑨$ 的反矩陣：

$𝑨^{- 1} = [\begin{matrix} C_{0}^{- 1} ϕ_{0}^{*} [0] & C_{1}^{- 1} ϕ_{1}^{*} [0] & C_{2}^{- 1} ϕ_{2}^{*} [0] & \dots & C_{N - 1}^{- 1} ϕ_{N - 1}^{*} [0] \\ C_{0}^{- 1} ϕ_{0}^{*} [1] & C_{1}^{- 1} ϕ_{1}^{*} [1] & C_{2}^{- 1} ϕ_{2}^{*} [1] & \dots & C_{N - 1}^{- 1} ϕ_{N - 1}^{*} [1] \\ C_{0}^{- 1} ϕ_{0}^{*} [2] & C_{1}^{- 1} ϕ_{1}^{*} [2] & C_{2}^{- 1} ϕ_{2}^{*} [2] & \dots & C_{N - 1}^{- 1} ϕ_{N - 1}^{*} [2] \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ C_{0}^{- 1} ϕ_{0}^{*} [M - 1] & C_{1}^{- 1} ϕ_{1}^{*} [M - 1] & C_{2}^{- 1} ϕ_{2}^{*} [M - 1] & \dots & C_{N - 1}^{- 1} ϕ_{N - 1}^{*} [M - 1] \end{matrix}],$

其中 $C_{m} = ⟨ ϕ_{m}^{*}, ϕ_{m}^{*} ⟩$ 。再者，也可表示成級數和（Summation）形式：

$x [n] = \sum_{m = 0}^{N - 1} C_{m}^{- 1} ϕ_{m}^{*} [n] y [m], for n = 0, 1, \dots, N - 1 .$

若 $C_{m} = 1$ ，即簡化成，

$x [n] = \sum_{m = 0}^{N - 1} ϕ_{m}^{*} [n] y [m], for n = 0, 1, \dots, N - 1 .$

正交矩陣by行向量：

$𝑨 = [\begin{matrix} β_{0}^{*} & β_{1}^{*} & β_{2}^{*} & \dots & β_{N - 1}^{*} \end{matrix}]$

若 ${\begin{matrix} ⟨ β_{l}^{*}, β_{k}^{*} ⟩ = \sum_{m = 0}^{M - 1} {(β_{l}^{*} [m])}^{T} β_{k}^{*} [m] = 0, when l \neq k \\ ⟨ β_{l}^{*}, β_{l}^{*} ⟩ = \sum_{m = 0}^{M - 1} {(β_{l}^{*} [m])}^{T} β_{l}^{*} [m] = C_{l} = C o n s t a n t \end{matrix},$

其中， $β_{0}^{*}, β_{1}^{*}, β_{2}^{*}, \dots,$ 和 $β_{N - 1}^{*}$ 為一組行向量的正交集合且也稱 $𝑨$ 是一種離散正交轉換。

再者，若滿足 $C_{l} = 1, for any l$ 。則 $β_{0}^{*}, β_{1}^{*}, β_{2}^{*}, \dots,$ 和 $β_{N - 1}^{*}$ 將組成一組行向量的正規化正交集合且稱 $𝑨$ 為一種離散正規化正交轉換。

此時，我們再利用 $β_{0}^{*}, β_{1}^{*}, β_{2}^{*}, \dots,$ 和 $β_{N - 1}^{*}$ 來組成 $𝑨$ 的反矩陣：

$𝑨^{- 1} = [\begin{matrix} C_{0}^{- 1} β_{0}^{*} [0] & C_{0}^{- 1} β_{0}^{*} [1] & C_{0}^{- 1} β_{0}^{*} [2] & \dots & C_{0}^{- 1} β_{0}^{*} [N - 1] \\ C_{1}^{- 1} β_{1}^{*} [0] & C_{1}^{- 1} β_{1}^{*} [1] & C_{1}^{- 1} β_{1}^{*} [2] & \dots & C_{1}^{- 1} β_{1}^{*} [N - 1] \\ C_{2}^{- 1} β_{2}^{*} [0] & C_{2}^{- 1} β_{2}^{*} [1] & C_{2}^{- 1} β_{2}^{*} [2] & \dots & C_{2}^{- 1} β_{2}^{*} [N - 1] \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ C_{M - 1}^{- 1} β_{M - 1}^{*} [0] & C_{M - 1}^{- 1} β_{M - 1}^{*} [1] & C_{M - 1}^{- 1} β_{M - 1}^{*} [2] & \dots & C_{M - 1}^{- 1} β_{M - 1}^{*} [N - 1] \end{matrix}],$

其中 $C_{n} = ⟨ β_{n}^{*}, β_{n}^{*} ⟩$ 。再者，也可表示成級數和：

$x [n] = C_{n}^{- 1} \sum_{m = 0}^{N - 1} β_{n}^{*} [m] y [m], for n = 0, 1, \dots, N - 1 .$

若 $C_{n} = 1$ ，即簡化成，

$x [n] = \sum_{m = 0}^{N - 1} β_{n}^{*} [m] y [m], for n = 0, 1, \dots, N - 1 .$

例子

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

特性

其列向量型式與行向量型式為一體兩面的情形：

- 順向轉換（Forward Transform）：列向量型式 $⟹$ 反向轉換（Inverse Transform）：行向量型式。
- 順向轉換（FT）：行向量型式 $⟹$ 反向轉換（IT）：列向量型式。

於正規化正交情況下：

- 若為行向量所組成的正規化正交矩陣，則它所對應的列向量形成的反矩陣 $(A^{- 1})$ 必為正規化正交矩陣。
- 若為列向量所組成的正規化正交矩陣，則它所對應的行向量形成的反矩陣 $(A^{- 1})$ 必為正規化正交矩陣。

優點

彼此間的列向量（或行向量）不會互相產生干擾（Interference）。

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

$𝑶 𝒓 𝒕 𝒉 𝒐 𝒈 𝒏 𝒂 𝒍 : ⟨ ϕ_{l}^{*}, ϕ_{k}^{*} ⟩ = \sum_{n = 0}^{N - 1} ϕ_{l}^{*} [m] ϕ_{k}^{*} [m] = 0, when l \neq k .$

其本身的FT與對應的IT結構為相當類似。

此外，離散正交轉換較非正交轉換（Non-orthogonal Transform）計算上較為簡單。

將DOT應用於影像重建（Reconstruction）或壓縮上，可藉由增加正交基底（Orthogonal basis）來控制誤差的產生，是採用非正交轉換所能及的。

應用於影像重建

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

(a) 正交情況下

$x_{k} [n] = \sum_{m = 0}^{K - 1} C_{m}^{- 1} y [m] ϕ_{m}^{*} [n], for K < N .$

因此，對於局部重建所產生的平方誤差（Sqaure error）： ${‖ x [n] - x_{k} [n] ‖}^{2} = \sum_{n = 0}^{N - 1} {‖ \sum_{m = k}^{N - 1} C_{m}^{- 1} y [m] ϕ_{m} [n] ‖}^{2} = \sum_{n = 0}^{N - 1} \sum_{m = k}^{N - 1} C_{m}^{- 1} y [m] ϕ_{m} [n] \sum_{h = k}^{N - 1} C_{h}^{- 1} y^{*} [h] ϕ_{h}^{*} [n] = \sum_{m = k}^{N - 1} C_{m}^{- 1} {| y [m] |}^{2} .$

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

（b）非正交情況下

$x_{k} [n] = \sum_{m = 0}^{K - 1} B [n, m] y [m], for K < N .$

因此，對於局部重建所產生的平方誤差： ${‖ x [n] - x_{k} [n] ‖}^{2} = \sum_{n = 0}^{N - 1} {‖ \sum_{m = k}^{N - 1} B [n, m] y [m] ‖}^{2} = \sum_{m = k}^{N - 1} \sum_{h = k}^{N - 1} y [m] y^{*} [h] \sum_{n = 0}^{N - 1} B [n, m] B^{*} [n, h] .$

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

參閱

參考文獻

Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
-{R|http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node15.html}- Template:Wayback.
-{R|http://mathworld.wolfram.com/KrawtchoukPolynomial.html}- Template:Wayback.

離散正交轉換

目录

離散正交轉換

正交矩陣by列向量：

正交矩陣by行向量：

例子

特性

優點

應用於影像重建

參閱

參考文獻

导航菜单

離散正交轉換

離散正交轉換

正交矩陣by列向量：

正交矩陣by行向量：

例子

特性

優點

應用於影像重建

參閱

參考文獻

导航菜单

搜索