查看“︁離散正交轉換”︁的源代码

{{copyedit|time=2014-06-26T13:43:18+00:00}}
數學上，任一的<math> M \times N </math>離散線性轉換皆可表示成[[矩陣]]（Matrix） 的型式：<math> \boldsymbol{Y = AX} </math>

<math>\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}. </math>

<math> \mathbf{{CASE} \, {1}} </math>

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

<math> \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}. </math>

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

<math> 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.</math>

其中<math> \left \langle \cdot \,, \cdot \right \rangle  </math>代表[[內積]]運算（Inner product）。

<math> \mathbf{{CASE} \, {2}} </math>

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

<math> \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}. </math>

也可表示成級數和：

<math> 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.</math>

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

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

== 離散正交轉換 ==

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

=== 正交矩陣by列向量： ===

<math> \boldsymbol{A} = \begin{bmatrix} {\boldsymbol{\phi}_0^*} \\ {\boldsymbol{\phi}_1^*} \\ {\boldsymbol{\phi}_2^*} \\ \vdots \\ {\boldsymbol{\phi}_{M-1}^*} \end{bmatrix} </math>

'''若'''<math> \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}, </math>

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

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

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

<math> \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}, </math>

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

<math> 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. </math>

若<math> C_m = 1 </math>，即簡化成，

<math> 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. </math>

=== 正交矩陣by行向量： ===

<math> \boldsymbol{A} = \begin{bmatrix} {\boldsymbol{\beta}_0^*} & {\boldsymbol{\beta}_1^*} & {\boldsymbol{\beta}_2^*} & \cdots & {\boldsymbol{\beta}_{N-1}^*} \end{bmatrix} </math>

'''若'''<math> \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}, </math>

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

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

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

<math> \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}, </math> 

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

<math> 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. </math>

若<math> C_n = 1 </math>，即簡化成，

<math> 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. </math>

== 例子 ==

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

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

== 特性 ==

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

**順向轉換（Forward Transform）：[[列向量]]型式<math> \Longrightarrow </math>反向轉換（Inverse Transform）：[[行向量]]型式。
**順向轉換（FT）：[[行向量]]型式<math> \Longrightarrow </math>反向轉換（IT）：[[列向量]]型式。

*於正規化正交情況下：

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

== 優點 ==

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

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

<math> \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. </math>

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

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

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

== 應用於影像重建 ==

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

(a) [[正交]]情況下

<math> 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. </math>

因此，對於局部重建所產生的[[平方誤差]]（Sqaure error）：
<math> \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. </math>

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

（b）非正交情況下

<math> x_k\left[{n}\right] = \sum_{m=0}^{K-1} B\left[{n,m}\right] y\left[m\right], \quad \mbox{for }K < N. </math>

因此，對於局部重建所產生的[[平方誤差]]：
<math> \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]. </math>

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

== 參閱 ==

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

== 參考文獻 ==

*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 {{Wayback|url=http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node15.html |date=20200217170110 }}. 
*http://mathworld.wolfram.com/KrawtchoukPolynomial.html {{Wayback|url=http://mathworld.wolfram.com/KrawtchoukPolynomial.html |date=20150402142850 }}.

[[Category:數學工具]]