離散正交轉換

數學上，任一的 $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<N.
$$

因此，對於局部重建所產生的平方誤差（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<N.
$$

因此，對於局部重建所產生的平方誤差： $\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 （頁面存檔備份，存於網際網路檔案館）.