离散正交转换

数学上，任一的 $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 （页面存档备份，存于互联网档案馆）.