離散正交轉換

數學上，任一的$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 （頁面存檔備份，存於互聯網檔案館）.