離散正交轉換

數學上，任一的$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]$不一定為正的，所以無法利用增加基底數來改善平方誤差。

## 參閱

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