離散正交轉換

數學上，任一的 M \times N 離散線性轉換皆可表示成矩陣（Matrix） 的型式： \boldsymbol{Y = AX}

\begin{bmatrix} y\left[{0}\right] \\ y\left[{1}\right] \\ y\left[{2}\right] \\ \vdots \\ y\left[{M-1}\right] \end{bmatrix} = \begin{bmatrix} {a_0\left[0\right]} & {a_0\left[1\right]} & {a_0\left[2\right]} & \cdots & {a_0\left[N-1\right]} \\ {a_1\left[0\right]} & {a_1\left[1\right]} & {a_1\left[2\right]} & \cdots & {a_1\left[N-1\right]} \\ {a_2\left[0\right]} & {a_2\left[1\right]} & {a_2\left[2\right]} & \cdots & {a_2\left[N-1\right]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {a_{M-1}\left[0\right]} & {a_{M-1}\left[1\right]} & {a_{M-1}\left[2\right]} & \cdots & {a_{M-1}\left[N-1\right]} \end{bmatrix} \begin{bmatrix} x\left[{0}\right] \\ x\left[{1}\right] \\ x\left[{2}\right] \\ \vdots \\ x\left[{N-1}\right] \end{bmatrix}.

\mathbf{{CASE} \, {1}}

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

\begin{bmatrix} {\boldsymbol{\phi}_0^} \\ {\boldsymbol{\phi}_1^} \\ {\boldsymbol{\phi}_2^} \\ \vdots \\ {\boldsymbol{\phi}_{M-1}^} \end{bmatrix} = \begin{bmatrix} {\phi_0^\left[0\right]} & {\phi_0^\left[1\right]} & {\phi_0^\left[2\right]} & \cdots & {\phi_0^\left[N-1\right]} \\ {\phi_1^\left[0\right]} & {\phi_1^\left[1\right]} & {\phi_1^\left[2\right]} & \cdots & {\phi_1^\left[N-1\right]} \\ {\phi_2^\left[0\right]} & {\phi_2^\left[1\right]} & {\phi_2^\left[2\right]} & \cdots & {\phi_2^\left[N-1\right]} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {\phi_{M-1}^\left[0\right]} & {\phi_{M-1}^\left[1\right]} & {\phi_{M-1}^\left[2\right]} & \cdots & {\phi_{M-1}^\left[N-1\right]} \end{bmatrix} = \boldsymbol{A}.

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

y\left[m\right] = \left \langle {\boldsymbol{\phi}_m^} , x\left[n\right] \right \rangle = \sum_{n=0}^{N-1} {\phi_m^\left[n\right]} x\left[n\right], \quad \mbox{for }m = 0,\, 1,\, \cdots,\, M-1.

其中 \left \langle \cdot \,, \cdot \right \rangle 代表內積運算（Inner product）。

\mathbf{{CASE} \, {2}}

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

\begin{bmatrix} {\boldsymbol{\beta}_0^} & {\boldsymbol{\beta}_1^} & {\boldsymbol{\beta}_2^} & \cdots & {\boldsymbol{\beta}_{N-1}^} \end{bmatrix} = \begin{bmatrix} {\beta_0^\left[0\right]} & {\beta_1^\left[0\right]} & {\beta_2^\left[0\right]} & \cdots & {\beta_{N-1}^\left[0\right]} \\ {\beta_0^\left[1\right]} & {\beta_1^\left[1\right]} & {\beta_2^\left[1\right]} & \cdots & {\beta_{N-1}^\left[1\right]} \\ {\beta_0^\left[2\right]} & {\beta_1^\left[2\right]} & {\beta_2^\left[2\right]} & \cdots & {\beta_{N-1}^\left[2\right]} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {\beta_0^\left[M-1\right]} & {\beta_1^\left[M-1\right]} & {\beta_2^\left[M-1\right]} & \cdots & {\beta_{N-1}^\left[M-1\right]} \end{bmatrix} = \boldsymbol{A}.

也可表示成級數和：

y\left[m\right] = \sum_{n=0}^{N-1} x\left[n\right]{\beta_n^*\left[m\right]}, \quad \mbox{for }m = 0,\, 1,\, \cdots,\, M-1.

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

\begin{cases} Y = AX & (\mbox{Forward transform}) \\ X = A ^{-1} X & (\mbox{Inverse transform}) \end{cases}.

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

正交矩陣by列向量：
\boldsymbol{A} = \begin{bmatrix} {\boldsymbol{\phi}_0^} \\ {\boldsymbol{\phi}_1^} \\ {\boldsymbol{\phi}_2^} \\ \vdots \\ {\boldsymbol{\phi}_{M-1}^} \end{bmatrix}

若 \begin{cases} \; \left \langle \boldsymbol{\phi}_l^,\boldsymbol{\phi}_k^ \right \rangle = \sum_{n=0}^{N-1} {\phi_l^\left[n\right]} \left({\phi_k^\left[n\right]} \right)^T = 0, \quad \mbox{when } l \neq k \\ \; \left \langle \boldsymbol{\phi}_l^,\boldsymbol{\phi}_l^ \right \rangle = \sum_{n=0}^{N-1} {\phi_l^\left[n\right]} \left({\phi_l^\left[n\right]} \right)^T = C_l = Constant \end{cases},

其中，{\;\boldsymbol{\phi}_0^},\; {\boldsymbol{\phi}_1^},\; {\boldsymbol{\phi}_2^},\; \ldots,\; 和 {\;\boldsymbol{\phi}_{M-1}^} 為一組列向量的正交集合且稱 \boldsymbol{A}\ 為一種離散正交轉換。

再者，若滿足 C_l = 1, \; \mbox{for any }l 。則 {\;\boldsymbol{\phi}_0^},\; {\boldsymbol{\phi}_1^},\; {\boldsymbol{\phi}_2^},\; \ldots,\; 和 {\;\boldsymbol{\phi}_{M-1}^} 將組成一組列向量的正規化正交集合且稱 \boldsymbol{A}\ 為一種離散正規化正交轉換。

此時，我們可利用{\;\boldsymbol{\phi}_0^},\; {\boldsymbol{\phi}_1^},\; {\boldsymbol{\phi}_2^},\; \ldots,\; 和 {\;\boldsymbol{\phi}_{M-1}^} 來求得 \boldsymbol{A} 的反矩陣：

\boldsymbol{A}^{-1} = \begin{bmatrix} {C_0^{-1}\phi_0^\left[0\right]} & {C_1^{-1}\phi_1^\left[0\right]} & {C_2^{-1}\phi_2^\left[0\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^\left[0\right]} \\ {C_0^{-1}\phi_0^\left[1\right]} & {C_1^{-1}\phi_1^\left[1\right]} & {C_2^{-1}\phi_2^\left[1\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^\left[1\right]} \\ {C_0^{-1}\phi_0^\left[2\right]} & {C_1^{-1}\phi_1^\left[2\right]} & {C_2^{-1}\phi_2^\left[2\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^\left[2\right]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {C_0^{-1}\phi_0^\left[M-1\right]} & {C_1^{-1}\phi_1^\left[M-1\right]} & {C_2^{-1}\phi_2^\left[M-1\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^\left[M-1\right]} \end{bmatrix},

其中 C_m = \left \langle \boldsymbol{\phi}_m^,\boldsymbol{\phi}_m^ \right \rangle 。再者，也可表示成級數和（Summation）形式：

x\left[{n}\right] = \sum_{m=0}^{N-1} C_m^{-1} {\phi_m^*\left[n\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.

若 C_m = 1 ，即簡化成，

x\left[{n}\right] = \sum_{m=0}^{N-1} {\phi_m^*\left[n\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.

正交矩陣by行向量：
\boldsymbol{A} = \begin{bmatrix} {\boldsymbol{\beta}_0^} & {\boldsymbol{\beta}_1^} & {\boldsymbol{\beta}_2^} & \cdots & {\boldsymbol{\beta}_{N-1}^} \end{bmatrix}

若 \begin{cases} \; \left \langle \boldsymbol{\beta}_l^,\boldsymbol{\beta}_k^ \right \rangle = \sum_{m=0}^{M-1} \left({\beta_l^\left[m\right]} \right)^T {\beta_k^\left[m\right]} = 0, \quad \mbox{when } l \neq k \\ \; \left \langle \boldsymbol{\beta}_l^,\boldsymbol{\beta}_l^ \right \rangle = \sum_{m=0}^{M-1} \left({\beta_l^\left[m\right]} \right)^T {\beta_l^\left[m\right]} = C_l = Constant \end{cases},

其中，{\;\boldsymbol{\beta}_0^},\; {\boldsymbol{\beta}_1^},\; {\boldsymbol{\beta}_2^},\; \ldots,\; 和 {\;\boldsymbol{\beta}_{N-1}^} 為一組行向量的正交集合且也稱 \boldsymbol{A}\ 是一種離散正交轉換。

再者，若滿足 C_l = 1, \; \mbox{for any }l 。則{\;\boldsymbol{\beta}_0^},\; {\boldsymbol{\beta}_1^},\; {\boldsymbol{\beta}_2^},\; \ldots,\; 和 {\;\boldsymbol{\beta}_{N-1}^} 將組成一組行向量的正規化正交集合且稱 \boldsymbol{A}\ 為一種離散正規化正交轉換。

此時，我們再利用{\;\boldsymbol{\beta}_0^},\; {\boldsymbol{\beta}_1^},\; {\boldsymbol{\beta}_2^},\; \ldots,\; 和 {\;\boldsymbol{\beta}_{N-1}^} 來組成 \boldsymbol{A} 的反矩陣：

\boldsymbol{A}^{-1} = \begin{bmatrix} {C_0^{-1}\beta_0^\left[0\right]} & {C_0^{-1}\beta_0^\left[1\right]} & {C_0^{-1}\beta_0^\left[2\right]} & \cdots & {C_0^{-1}\beta_0^\left[N-1\right]} \\ {C_1^{-1}\beta_1^\left[0\right]} & {C_1^{-1}\beta_1^\left[1\right]} & {C_1^{-1}\beta_1^\left[2\right]} & \cdots & {C_1^{-1}\beta_1^\left[N-1\right]} \\ {C_2^{-1}\beta_2^\left[0\right]} & {C_2^{-1}\beta_2^\left[1\right]} & {C_2^{-1}\beta_2^\left[2\right]} & \cdots & {C_2^{-1}\beta_2^\left[N-1\right]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {C_{M-1}^{-1}\beta_{M-1}^\left[0\right]} & {C_{M-1}^{-1}\beta_{M-1}^\left[1\right]} & {C_{M-1}^{-1}\beta_{M-1}^\left[2\right]} & \cdots & {C_{M-1}^{-1}\beta_{M-1}^\left[N-1\right]} \end{bmatrix},

其中 C_n = \left \langle \boldsymbol{\beta}_n^,\boldsymbol{\beta}_n^ \right \rangle 。再者，也可表示成級數和：

x\left[{n}\right] = C_n^{-1} \sum_{m=0}^{N-1} {\beta_n^*\left[m\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.

若 C_n = 1 ，即簡化成，

x\left[{n}\right] = \sum_{m=0}^{N-1} {\beta_n^*\left[m\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.

例子
*離散傅里葉變換
*離散餘弦變換、離散正弦變換、離散哈特利轉換
*瓦希轉換、哈爾小波轉換
*離散勒詹德轉換
*離散正交多項式轉換

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

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

**順向轉換（Forward Transform）：列向量型式 \Longrightarrow 反向轉換（Inverse Transform）：行向量型式。
**順向轉換（FT）：行向量型式 \Longrightarrow 反向轉換（IT）：列向量型式。

*於正規化正交情況下：

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

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

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

\boldsymbol{Orthognal:} \quad \left \langle \boldsymbol{\phi}_l^,\boldsymbol{\phi}_k^ \right \rangle = \sum_{n=0}^{N-1} {\phi_l^\left[m\right]} {\phi_k^\left[m\right]} = 0, \quad \mbox{when } l \neq k.

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

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

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

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

(a) 正交情況下

x_k\left[{n}\right] = \sum_{m=0}^{K-1} C_m^{-1} y\left[{m}\right] {\phi_m^*\left[n\right]}, \quad \mbox{for }K

因此，對於局部重建所產生的平方誤差（Sqaure error）：
\left \| x\left[n\right] - x_k\left[n\right] \right \|^2 = \sum_{n=0}^{N-1} \left \| \sum_{m=k}^{N-1} C_m^{-1}y\left[{m}\right] \phi_m\left[n\right] \right \|^2 = \sum_{n=0}^{N-1} \sum_{m=k}^{N-1} C_m^{-1}y\left[{m}\right] \phi_m\left[n\right] \sum_{h=k}^{N-1} C_h^{-1}y^\left[{h}\right] \phi_h^\left[n\right] = \sum_{m=k}^{N-1} C_m^{-1}\left|\ y\left[{m}\right] \right|^2.

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

（b）非正交情況下

x_k\left[{n}\right] = \sum_{m=0}^{K-1} B\left[{n,m}\right] y\left[m\right], \quad \mbox{for }K

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

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

參閱
*離散傅里葉變換
*離散餘弦變換
*離散正弦變換
*哈爾小波轉換
*正交矩陣

參考文獻
*Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
*http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node15.html .
*http://mathworld.wolfram.com/KrawtchoukPolynomial.html .