查看“︁离散余弦变换”︁的源代码

{{NoteTA
|G1 = Math
}}
{{For|同樣縮寫為DCT的一種[[汽車]][[變速箱]]|雙離合變速箱}}
[[File:Dandelion clock quarter dft dct.png|thumb|350px|right|2d DCT（type II） 與[[离散傅里叶变换]]的比較. ]]
'''离散余弦变换'''（{{lang-en|'''discrete cosine transform, DCT'''}}）是与[[傅里叶变换]]相关的一种变换，类似于[[离散傅里叶变换]]，但是只使用[[实数]]。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实[[偶函数]]进行的（因为一个实偶函数的傅里叶变换仍然是一个实偶函数），在有些变形里面需要将输入或者输出的位置移动半个单位（DCT有8种标准类型，其中4种是常见的）。

最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为「反离散余弦变换」，「逆离散余弦变换」或者「IDCT」。

有两个相关的变换，一个是[[离散正弦变换]]，它相当于一个长度大概是它两倍的实[[奇函数]]的[[离散傅里叶变换]]；另一个是[[改进的离散余弦变换]]，它相当于对交叠的数据进行离散余弦变换。

== 应用 ==
离散余弦变换，尤其是它的第二种类型，经常被[[信号处理]]和[[图像处理]]使用，用于对[[信号]]和[[图像]]进行[[有损数据压缩]]。这是由于离散余弦变换具有很强的「能量集中」特性：大多数的信号資訊（包括声音和图像）往往集中在离散余弦变换后的低频部分，而且当信号具有接近[[马尔可夫过程]]的统计特性时，离散余弦变换的去相关性接近于[[K-L变换]]（{{lang|en|Karhunen-Loève}}变换——它具有最优的去相关性）的性能。

例如，在图像编码标准[[JPEG]]與[[視訊]]编码标准[[MJPEG]]和[[MPEG]]的各个标准中都使用了离散余弦变换。在这些标准制中都使用了二维的第二种类型离散余弦变换，并将结果进行[[量化 (信号处理)|量化]]之后进行[[熵编码]]。这时对应第二种类型离散余弦变换中的''n''通常是8，并用该公式对每个8x8块的每行进行变换，然后每列进行变换。得到的是一个8x8的变换系数矩阵。其中（0,0）位置的元素就是直流分量，矩阵中的其他元素根据其位置表示不同频率的交流分量。

一个类似的变换，[[改进的离散余弦变换]]被用在[[高级音频编码]]、[[Vorbis]]和[[MP3]]音频压缩当中。

离散余弦变换也经常被用来使用谱方法来解[[偏微分方程]]，这时候离散余弦变换的不同的变量对应着数组两端不同的奇/偶边界条件。

===常見應用===

*[[音频信号处理]] — 音訊編碼、音訊資料壓縮（有損和無損）<ref name="Ochoa129">{{cite book |last1=Ochoa-Dominguez |first1=Humberto |last2=Rao |first2=K. R. |author2-link=K. R. Rao |title=Discrete Cosine Transform, Second Edition |date=2019 |publisher=[[CRC Press]] |isbn=9781351396486 |pages=1–3, 129 |url=https://books.google.com/books?id=dVOWDwAAQBAJ}}</ref>、環繞聲<ref name="Luo"/>、[[回音消除]]、[[音位]]辨識、[[修改型離散餘弦轉換|時域混疊消除法]]（TDAC）<ref name="Ochoa">{{cite book|url=https://books.google.com/books?id=dVOWDwAAQBAJ&pg=PA1|title=Discrete Cosine Transform, Second Edition|last1=Ochoa-Dominguez|first1=Humberto|last2=Rao|first2=K. R.|author2-link=K. R. Rao|date=2019|publisher=[[CRC Press]]|isbn=9781351396486|pages=1–3}}</ref>
**[[數位音訊]]<ref name="Stankovic" />
**[[數位廣播]] — [[數位聲音廣播]]（DAB+）<ref name="Britanak" />
**[[語音處理]] — [[語音編碼]]<ref name="Hersent" /><ref name="AppleInsider standards 1" />、[[語音辨識]]、[[語音活性檢測]]（VAD）<ref name="Ochoa" />
**數位電話 — [[VoIP]]<ref name="Hersent" />、[[行動電話]]、[[視訊通話]]<ref name="AppleInsider standards 1" /><ref name="Stankovic" />
*[[生物辨識技術]] — [[指紋]]定向、[[臉部辨識系統]]、生物辨識[[數位浮水印|浮水印]]、掌紋辨識<ref name="Ochoa"/>
**[[人臉檢測]]<ref name="Ochoa"/>


== 形式化定义 ==
形式上来看，离散余弦变换是一个[[线性函数|线性]]的[[可逆函数|可逆]][[函数]]<math>F:R^n\rightarrow R^n</math>其中'''R'''是[[实数]]集，或者等价的说一个<math>n \times n</math>的[[方块矩阵|方阵]]。离散余弦变换有几种变形的形式， 它们都是根据下面的某一个公式把<math>n</math>个实数<math>x_0,\ldots ,x_{n-1}</math>变换到另外<math>n</math>个实数<math>f_0,\ldots ,f_{n-1}</math>的操作。

=== DCT-I ===
:<math>f_m = \frac{1}{2} (x_0 + (-1)^m x_{n-1}) 
     + \sum_{k=1}^{n-2} x_k \cos \left[\frac{\pi}{n-1} m k \right]</math>

有些人认为应该将<math>x_0</math>和<math>x_{n-1}</math>乘以<math>\sqrt{2}</math>，相应的将<math>f_0</math>和<math>f_{n-1}</math>乘以<math>\frac{1}{\sqrt{2}}</math>。这样做的结果是这种DCT-I矩阵变为了[[正交矩阵]]（再乘一个系数的话），但是这样就不能直接和一个实偶[[离散傅里叶变换]]对应了。

一个<math>n=5</math>的对实数''abcde''的DCT-I型变换等价于一个8点的对实数''abcdedcb''（偶对称）的DFT变换，结果再[[除以2]]（对应的，DCT-II~DCT-IV相对等价的DFT有一个半个抽样的位移）。需要指出的是，DCT-I不适用于<math>n<2</math>的情况（其它的DCT类型都适用于所有的整数''n''）。

所以，DCT-I暗示的边界条件是：<math>x_k</math>相对于<math>k=0</math>点偶对称，并且相对于<math>k=n-1</math>点偶对称； 对<math>f_m</math>的情况也类似。

=== DCT-II ===
:<math>f_m =
   \sum_{k=0}^{n-1} x_k \cos \left[\frac{\pi}{n} m \left(k+\frac{1}{2}\right) \right]</math>

DCT-II大概是最常用的一种形式，通常直接被称为DCT。

有些人更进一步的将<math>f_0</math>再乘以<math>\frac{1}{\sqrt{2}}</math>（参见下面的DCT-III型的对应修改）。这将使得DCT-II成为[[正交矩阵]]（再乘一个系数的话），但是这样就不能直接和一个有半个抽样位移的实偶[[离散傅里叶变换]]对应了。

所以，DCT-II暗示的边界条件是：<math>x_k</math>相对于<math>k=-\frac{1}{2}</math>点偶对称，并且相对于<math>k=n-\frac{1}{2}</math>点奇对称； 对<math>f_m</math>相对于<math>m=0</math>点偶对称，并且相对于<math>m=n</math>点奇对称。

=== DCT-III ===
:<math>f_m = \frac{1}{2} x_0 +
   \sum_{k=1}^{n-1} x_k \cos \left[\frac{\pi}{n} \left(m+\frac{1}{2}\right) k \right]</math>

因为这是DCT-II的逆变换（再乘一个系数的话），这种变形通常被简单的称为逆离散余弦变换。

有些人更进一步的将<math>x_0</math>再乘以<math>\sqrt{2}</math>（参见上面的DCT-II型的对应修改），这将使得DCT-III成为[[正交矩阵]]（再乘一个系数的话），但是这样就不能直接和一个结果有半个抽样位移的实偶[[离散傅里叶变换]]对应了。

所以，DCT-III暗示的边界条件是：<math>x_k</math>相对于<math>k=0</math>点偶对称，并且相对于<math>k=n</math>点奇对称； 对<math>f_m</math>相对于<math>m=-\frac{1}{2}</math>点偶对称，并且相对于<math>m=n-\frac{1}{2}</math>点偶对称。

=== DCT-IV ===
:<math>f_m =
   \sum_{k=0}^{n-1} x_k \cos \left[\frac{\pi}{n} \left(m+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right]</math>

DCT-IV对应的矩阵是[[正交矩阵]]（再乘一个系数的话）。

一种DCT-IV的变形，将不同的变换的数据重叠起来，被称为[[改进的离散余弦变换]]。

DCT-IV暗示的边界条件是：<math>x_k</math>相对于<math>k=-\frac{1}{2}</math>点偶对称，并且相对于<math>k=n-\frac{1}{2}</math>点奇对称；对<math>f_m</math>类似。

=== DCT V~VIII ===
上面提到的DCT I~IV是和偶数阶的实偶DFT对应的。原则上，还有四种DCT变换（Martucci, 1994）是和奇数阶的实偶DFT对应的，它们在分母中都有一个<math>n+\frac{1}{2}</math>的系数。但是在实际应用中，这几种变型很少被用到。

最平凡的和奇数阶的实偶DFT对应的DCT是1阶的DCT（1也是奇数），可以说变换-{}-只是乘上一个系数<math>a</math>而已，对应于DCT-V的长度为1的状况。

== 反变换 ==
DCT-I的反变换是把DCT-I乘以系数<math>\frac{2}{n-1}</math>。
DCT-IV的反变换是把DCT-IV乘以系数<math>\frac{2}{n}</math>。
DCT-II的反变换是把DCT-III乘以系数<math>\frac{2}{n}</math>，反之亦然。

和[[离散傅里叶变换]]类似，变化前面的归一化系数仅仅是常规而已，改变这个系数并不改变变换的性质。例如，有些人喜欢在DCT-II变换的前面乘以<math>\sqrt{\frac{2}{n}}</math>，这样反变换从形式上就和变换更相似，而不需要另外的归一化系数。

== 计算 ==
尽管直接使用公式进行变换需要进行<math>O(n^2)</math>次操作，但是和[[快速傅里叶变换]]类似，我们有复杂度为<math>O(n \log(n))</math>的快速算法，这就是常常被称做[[蝶形变换]]的一种分解算法。另外一种方法是通过[[快速傅里叶变换]]来计算DCT，这时候需要<math>O(n)</math>的预操作和后操作。

以下簡單介紹兩種利用DFT來計算DCT-II的方法

=== 方法一<ref>Rao, R. K., & Yip, P. (1990). Discrete Cosine Transform: Algorithms, Advantages, Applications (1st ed.). Academic Press.</ref> ===


令輸入信號為<math> x(n) \, , n=0,1,...,N-1</math>


並將<math>y(n)</math>以<math>x(n)</math>在<math>(2N-1)/2</math>處對稱表示


即<math> y(n)=\left\{\begin{matrix} x(n), & \mbox{if }n=0,1,...,N-1 \\  x(2N-n-1), & \mbox{if }n=N,N+1,...2N-1 \end{matrix}\right.</math>


此時令<math>W_{2N}</math> 表示 <math>e^{\frac{-j2\pi}{2N}}</math>


則<math>y(n)</math>之DFT為


<math>Y(m) = \Sigma_{n=0}^{2N-1}y(n)W_{2N}^{nm}</math>


將<math>Y(m)</math> 做以下化簡


<math>\begin{align}
Y(m) &= \sum_{n=0}^{N-1}y(n)W_{2N}^{nm} + \sum_{n=N}^{2N-1}y(n)W_{2N}^{nm} \\
& = \sum_{n=0}^{N-1}y(n)W_{2N}^{nm} + \sum_{n=N}^{2N-1}x(2N-n-1)W_{2N}^{nm} \\
& = \sum_{n=0}^{N-1}y(n)W_{2N}^{nm} + \sum_{n=0}^{N-1}x(n)W_{2N}^{(2N-n-1)m} \\
& = \sum_{n=0}^{N-1}x(n)[W_{2N}^{nm}+W_{2N}^{-(n+1)m}], \, \,\,\,  m=0,1,...,2N-1 
\end{align}</math>


此時兩側同乘 <math> \frac{1}{2}W_{2N}^{m/2}</math>


可得<math> \frac{1}{2} W_{2N}^{m/2} Y(m) = \sum_{n=0}^{N-1} x(n)\cos{[(2n+1)\frac{m\pi}{2N}]}, \,\,\,\,\,\, m=0,1,...,N-1 </math>


此時右式即為欲求之DCT轉換，而左式可藉由2N點數的DFT來計算，使用快速演算法的情況下，運算之時間複雜度為<math>O(NlogN)</math>

=== 方法二 <ref>On the Computation of the Discrete Cosine Transform. (1978, June 1). IEEE Journals & Magazine | IEEE Xplore. https://ieeexplore.ieee.org/document/1094144 {{Wayback|url=https://ieeexplore.ieee.org/document/1094144 |date=20220617042124 }}</ref> ===


第二個方法由Narasimha與Peterson在1978年提出，此方法係藉由巧妙的編排<math>y(n)</math>來達成，首先令


<math> y(n)=x(2n)</math> 並且 <math> y(N-1-n)=x(2n+1), \,\, \,\,\,\, n=0,1,...,\frac{N}{2}-1</math>


此時X(m)可化簡為


<math> X(m)= \sum_{n=0}^{N/2-1}y(n)\cos{[\frac{(4n+1)m\pi}{2N}]}+ \sum_{n=0}^{N/2-1}y(N-n-1)\cos{[\frac{(4n+3)m\pi}{2N}]}, \,\,\, \,\,\,\, m=0,1,...,N-1</math>


令第二項之<math>n</math>改為 <math>n'=N-1-n</math>，則兩式可合併為


<math>X(m)=\sum_{n=0}^{N-1}y(n)\cos{[\frac{(4n+1)m\pi}{2N}]}, \,\,\,\,\,\, m=0,1,...,N-1</math>


右側為對<math>y(n)</math>之N點的scaled DFT


因此，<math>X(m)=Re[Z(m)]</math>，其中


<math>Z(m)=W_{4N}^{m}Y(m)=W_{4N}^{m}\sum_{n=0}^{N-1}y(n)W_{N}^{nm},\,\,\, \,\,\,\, m=0,1,...,N-1</math>


其中<math> Y(m) </math> 是對<math>y(n)</math>之N點的DFT，並且可以簡單的驗證<math>Z(m)</math>具有如下性質


<math>Z(N-m)=-jZ(m)^{*}</math>


而因<math> y(n) </math> 為實數輸入，


因此欲求之<math> X(m) = Re[Z(m)] </math> ，<math> X(N-m) = -Im[Z(m)],\,\,\, \, \, \, \, m=0,1,...,\frac{N}{2}</math> 


在使用FFT快速演算法的情況下，運算之時間複雜度同樣為<math>O(NlogN)</math>

但此方法較方法一直接運算2N點數的DFT快上約2倍。

== 参考 ==
* K. R. Rao and P. Yip, ''离散余弦变换：算法、优点和应用''（''Discrete Cosine Transform: Algorithms, Advantages, Applications''） (Academic Press, Boston, 1990).
* A. V. Oppenheim, R. W. Schafer, and J. R. Buck, ''时间离散信号处理'' (''Discrete-Time Signal Processing''), second edition (Prentice-Hall, New Jersey, 1999).
* S. A. Martucci, ''对称卷积和离散正弦余弦变换'' (''Symmetric convolution and the discrete sine and cosine transforms''), ''IEEE Trans. Sig. Processing'' '''SP-42''', 1038-1051 (1994).
* Matteo Frigo and Steven G. Johnson: ''FFTW'', http://www.fftw.org/ {{Wayback|url=http://www.fftw.org/ |date=20190925140738 }}. 一个免费的[[C语言]]库[[GPL]]，可以计算DCT-I~IV的1维到多维的任意大小的变换 
* M. Frigo and S. G. Johnson, "[http://fftw.org/fftw-paper-ieee.pdf FFTW3的设计和实现] {{Wayback|url=http://fftw.org/fftw-paper-ieee.pdf |date=20190716053010 }}," ''Proceedings of the IEEE'' '''93''' (2), 216–231 (2005).
* On the Computation of the Discrete Cosine Transform. (1978, June 1). IEEE Journals & Magazine | IEEE Xplore. https://ieeexplore.ieee.org/document/1094144 {{Wayback|url=https://ieeexplore.ieee.org/document/1094144 |date=20220617042124 }}
== 外部链接 ==
* [http://planetmath.org/?op=getobj&from=objects&id=1469 离散余弦变换] {{Wayback|url=http://planetmath.org/?op=getobj&from=objects&id=1469 |date=20210225094628 }}

[[Category:数字信号处理]]
[[Category:数学分析]]
[[Category:变换编码]]