离散正交转换

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