离散余弦变换(DCT)是一类数学变换,将有限数列表示为余弦函数的加权和。它把按位置或时间索引的数据转换为按空间频率或时间频率索引的系数。与一般的离散傅里叶变换不同,DCT 完全在实数范围内运算,并对应于有限数据在边界之外如何延拓的特定对称性假设。
DCT 之所以重要,是因为许多自然信号在较短区间内变化平滑。这些信号的 DCT 表示往往将大部分幅值平方集中在相对少量的系数上,因此这种变换可用于压缩、降噪、近似和特征提取。II 型 DCT 是最广为人知的形式,通常在不加限定地提到“DCT”时,指的就是这一形式。其他形式则适用于不同的采样方式、边界条件和计算用途。
纳西尔·艾哈迈德、T. 纳塔拉詹和 K. R. 拉奥在 1974 年发表的一篇奠基性论文中提出了 DCT,此后它成为数字图像和视频编码的核心组成部分。其数学意义并不限于压缩:余弦基还能使一些重要的离散微分算子对角化,与多项式近似建立联系,并为求解数值问题提供高效的坐标表示。
定义与频率解释
对于实数序列 ,采用正交归一化的 II 型离散余弦变换定义为
其中
每个系数都衡量输入与某个特定余弦模式的匹配程度。下标 标识采样点,而 标识该模式的频率。半个采样间隔的偏移 至关重要:它决定了变换的对称性,也使这种离散余弦变换区别于其他相关的余弦变换。
系数 通常称为直流系数,表示常量分量:
其中, 是样本均值。其余系数称为交流系数。较小的 值描述缓慢变化的模式,较大的值则描述更快速的交替变化。如果采样点之间的物理时间间隔为 ,则相应的余弦频率为 。这些频率对应的是变换所隐含的延拓序列,并不一定对应原始物理信号源中独立存在的振荡。
在这种归一化方式下,重建公式为
因此,变换本身不会丢失任何信息。常量序列 的变换结果为 ,所有交流系数均为零。若序列与某个归一化余弦基模式一致,则只会产生一个非零系数。一般数据则表示为这些模式的叠加。
同一运算也可写为 ,其中 是一个 的矩阵,各行由归一化余弦模式构成。这种记法对多维数据尤其有用。对于一个 的图像矩阵 ,可分离的二维变换为
因此,可以先对每一行进行变换,再对每一列进行变换,也可以按相反的顺序计算。所得的每个系数都对应一个垂直方向余弦与一个水平方向余弦的乘积。对于图像块,左上角的系数表示平均水平;沿系数阵列的水平或垂直方向移动,分别对应水平或垂直空间频率的增大。
不同教材、软件库和编码标准采用的归一化约定各不相同。有些省略因子 ,有些则将全部缩放因子放在逆变换中。只有将这些约定的差异考虑在内,不同实现所得的系数才具有可比性。
变换类型与边界对称性
DCT 这一名称指的是一族变换,而非单一公式。根据采样点位置以及边界处偶反射或奇反射方式的不同,通常可分为八种类型,编号为 I 至 VIII。其中,I–IV 型最为常见。它们的差异在于数学结构,而不只是系数缩放方式不同:各类型采用不同的余弦网格,并隐含不同的输入延拓方式。
前四种类型的一种常见非归一化约定如下:
所有输出索引均从 到 ;DCT-I 要求 。将这些表达式转换为正交归一变换时,必须调整端点的权重。
对于 DCT-I,输入分别以 和 处的采样点为中心作偶对称延拓。由此隐含的周期序列,其周期为 。由于反射中心与实际采样点重合,两个端点需要采用特殊权重。当数值网格包含区间的两个端点时,这种类型便会自然出现。
DCT-II 则以 和 为中心对输入作偶对称反射,这两个位置分别位于首尾采样点向外半个采样间隔处。这样,长度为 的序列便对应于一个长度为 的周期延拓序列。这也是 DCT-II 非常适合处理像素值块的原因之一:这种反射方式不要求块内最后一个采样值与第一个采样值相同。
DCT-III 对应于以 为中心的偶反射和以 为中心的奇反射。DCT-IV 则结合了以 为中心的偶反射和以 为中心的奇反射。这里的“奇反射”是指反射后的值改变符号,并不意味着原始采样值的正负号交替出现。
在正交归一约定下,DCT-II 与 DCT-III 互为转置,也互为逆变换。DCT-I 和 DCT-IV 经适当归一化后,其逆变换就是自身。V–VIII 型采用与之相关的对称性配置,其逻辑延拓长度为奇数。它们在主流媒体编码中较少使用,但补全了这一分类,并且可能适用于某些特定的变换网格。
因此,应该选择哪种类型,取决于采样点的位置以及预期的边界行为。如果仅仅因为某种变换带有“余弦”之名就选用它,可能会在数值区间的两端施加不恰当的模型。
正交性、能量及与傅里叶变换的关系
归一化的 DCT-II 基向量构成实向量空间 的一组标准正交基。不同基向量之间的内积为零,且每个基向量的长度均为 1。因此,变换矩阵满足
所以它是一个正交矩阵,其逆矩阵就是其转置矩阵。
正交性给出了帕塞瓦尔恒等式的有限维形式:
这里所说的信号“能量”是各采样值幅度的平方和,不一定是以焦耳为单位的物理能量。变换也保持距离不变。对于两个序列 和 ,有
借助这一恒等式,可以直接从原始采样域的角度理解变换域中的误差。
如果重建时只保留索引集 中的系数,那么重建误差的平方恰好为
因此,在从这组特定的基中选取指定数量的基向量进行近似时,保留绝对值最大的系数就能得到最佳近似。这是正交投影的结论,并不意味着 DCT 能为每一种信号提供最优的基。针对其他信号类别设计的基可能表现得更好。
DCT 与傅里叶变换之间的关系可以明确写出。对一个长度为 的序列作偶延拓:
若 是 的长度为 的 DFT,并采用负指数约定,则
去掉已知的相位因子后,就能得到实数余弦系数。复相位的出现并不意味着 DCT 是复值变换;它反映的是偶延拓序列的索引相对于 DFT 原点的位置关系。
这一关系既解释了基于傅里叶变换的 DCT 算法,也说明了这种变换的频率含义。它还揭示了两种变换在边界处理上的一个重要区别。DFT 将原始有限序列视为周期序列,直接把最后一个采样点与第一个采样点相接。DCT-II 则先对序列作镜像延拓。镜像消除了连接处可能出现的数值跳变,但仍可能引入导数的不连续。系数的衰减速度取决于延拓后信号的光滑性,而不仅仅取决于原始数据块内部的数值。
能量集中与统计模型
DCT 在压缩中的作用源于能量集中:许多相关信号的幅值平方期望主要集中在相对少量的系数中。在图像的平滑区域,相邻像素的值通常相近。与原始像素坐标表示相比,由缓慢变化的模式构成的基可以用更少的显著系数来表示这一区域。
统计学上的一个参照是 Karhunen–Loève 变换(KLT)。对于一个均值为零、协方差矩阵为 的随机向量,KLT 以 的特征向量为基。它使变换后的系数互不相关;在维数固定的正交投影中,保留最大特征值所对应的方向,能够使重建误差的平方期望最小。对于有限维随机向量,这种构造与主成分分析密切相关。
KLT 依赖于数据。当信源的统计特性变化时,它的基也可能改变,而传输或估计这组基会带来实际开销。DCT 则使用一组固定的、由解析形式给定的基。因此,它牺牲了对数据的精确适应,换取了简单的实现、可复现的系数以及高效的快速算法。
一种经常研究的模型具有如下协方差:
它描述了平稳一阶自回归过程的协方差结构。当相邻样本具有很强的正相关性时,余弦模式能很好地近似 KLT 的特征向量。在强相关极限下,两者的联系尤为紧密。这并不意味着对于任意 ,DCT 都能将这类协方差矩阵精确对角化,也不意味着所有自然图像都遵循这一模型。
对于正交变换 ,系数的协方差矩阵为
当该矩阵接近对角矩阵时,各系数近似互不相关。不相关性弱于统计独立性:对于联合高斯变量,不相关意味着独立,但对于具有任意统计特性的图像或音频数据则不成立。变换编码既利用了各系数方差的差异,也利用了变换后仍然存在的其他依赖关系。
如果事先固定要保留的系数集合 ,且数据均值为零,则截断误差的平方期望为
压缩系统通常对系数进行量化,而不只是将其丢弃。在简化的细粒度均匀量化模型下,量化步长为 的系数,其误差方差约为 。实际量化器可能明显偏离这一近似,尤其是在大量系数被量化为零时。
能量集中程度取决于信源。白噪声在每个标准正交坐标上的期望能量都相同,因此 DCT 平均而言并不能使其能量集中。锐利边缘、孤立脉冲和精细纹理都可能使能量分散到许多频率上。因此,低频占主导是许多信号具有的一项有用的经验性质,而不是适用于所有有限数据的定理。
快速算法与实现
直接计算一个 点 DCT,需要的算术运算次数约为 量级。对于常见的变换长度,快速算法利用余弦恒等式、对称性和递归分解,将计算量降至 量级。用大O记号表示,两者分别为 和 。对于大型数组和反复执行的变换,这种计算量的降低具有决定性意义。
一种方法是对经过适当延拓或重排的序列进行快速傅里叶变换,由此计算 DCT。从数学构造上看,这种方法可能需要将输入长度加倍,但实际算法会避免显式存储所有镜像样本。专门针对实数数据的 FFT 算法和 DCT 分解方法能够消除冗余运算,并通过解析方式处理相位与缩放。
另一种方法是将变换直接分解为规模更小的余弦变换,以及由加减运算构成的简单“蝶形”运算。Wen-Hsiung Chen、C. Harrison Smith 和 Stanley C. Fralick 于 1977 年提出的算法,是早期颇具影响力的快速 DCT 算法。后续方法则针对特定的分块大小,进一步改进了乘法次数、数据排列方式和缩放策略。
八点 DCT 因其在图像编码中的作用而受到特别关注。1988 年发表的 Arai–Agui–Nakajima 算法仅用五次非平凡乘法和 29 次加法,就能计算出经过缩放的八点 DCT。这里的经过缩放十分重要:上述运算次数并未包含完整施加各输出缩放因子所需的运算。在压缩编码器中,这些因子可以并入量化过程,因此这种缩放变换的计算成本尤其低。
对于一个 数组,可分离性使计算能够化为沿各坐标方向进行的一维变换。采用快速一维算法时,算术运算量约为
实际执行时间还取决于内存访问方式。行变换通常访问连续数据,而列变换则可能需要跨步读取、转置或分块处理。向量指令和并行计算可以加速大量独立数据块的处理。
数值表现取决于具体实现。采用浮点运算时,舍入误差使得一次正变换及其逆变换无法逐位精确还原所有输入。正交归一变换本身在欧几里得范数下的条件数为一,因此不会因病态性而在内在机制上放大相对扰动。不过,中间步骤的缩放、运算顺序和有限精度仍会影响实现误差。
定点系统必须控制溢出和舍入,常见做法是将移位操作分散到各个计算阶段。视频标准通常采用基于类 DCT 基函数设计的整数变换,而非使用精确的无理数余弦系数。一个在数学上等价的实数公式,并不意味着它可以直接替代编解码器中的实现:规定的缩放、舍入、限幅和逆运算,可能决定编码器与解码器的重建结果是否一致。
图像和视频压缩
DCT 最广为人知的应用是 JPEG图像编码标准中的图像编码。广泛使用的基于 DCT 的处理流程将图像分量划分为 块,并对每个块独立进行变换。对于常见的八位采样值,变换前先减去 128,完成电平平移,使数值以零为中心分布。随后,每个块都转换为 64 个系数,分别表示水平和垂直余弦模式的不同组合。
对一个块进行二维正交归一变换的公式为
其中,,且当 时,。JPEG 的其他等价公式只是对常数因子的安排有所不同。
主要的不可逆步骤是系数量化:
其中, 是量化表中的一个元素。量化表中的数值越大,舍弃的系数精度就越多。量化表通常为低频结构保留较高精度,而对许多高频分量采用较低精度,这既考虑了图像的统计特性,也考虑了视觉敏感度。
量化后的系数按之字形顺序排列,这种顺序通常会先访问较低频率的系数。这样,连续出现的大量零值就可以用紧凑的形式表示。直流预测、零游程符号和熵编码进一步减小了比特流的大小。DCT 本身并不减少数据值的数量,而是重新组织其中的信息,使其成为后续编码能够利用的表示形式。
在高压缩率下,分块处理会产生特有的失真。块效应源于相邻块各自独立量化,重建后的块边缘不一定能彼此衔接。剧烈变化区域附近的振铃效应,则是用数量有限或经过粗量化的振荡基函数来表示不连续变化所致。细微纹理也可能因相应系数受到抑制而消失。
视频编码通常对预测残差进行变换,而不是将每一帧都视为一张互不相关的照片。首先通过运动补偿预测或空间预测估计一个块,再用变换表示该估计块与实际块之间的差异。MPEG-1 和 MPEG-2 采用了基于八点 DCT 的分块编码。后续标准引入了更多样的变换尺寸,以及适合解码器精确运算的整数近似变换。
H.264/AVC 于 2003 年首次成为标准,其主要的 残差变换采用了与 DCT 相关的整数变换。HEVC 于 2013 年成为标准,支持多种变换尺寸,并针对一种特定的小块帧内编码情形采用了基于正弦的变换。这些选择表明,“基于 DCT 的视频编码”指的是一类广泛的设计思路,而非对所有块都应用同一个通用矩阵。预测质量、变换选择、量化、滤波和熵编码共同决定了压缩性能。
音频编码与信号特征
在音频领域,DCT 既用于压缩系统,也用于特征提取,但与现代感知音频编码关系最密切的变换是修正离散余弦变换(MDCT)。它与普通 DCT 相关,但有一个关键区别:相邻的分析块相互重叠,而且每个块产生的系数数量少于其输入样本数量。
一种常见的 MDCT 定义将 个加窗样本映射为 个系数:
其中, 为分析窗。相邻块通常以 个样本为步长推进,因此重叠率为 50%。虽然单个块的系数数量只有输入样本数量的一半,但重叠块序列整体上仍满足临界采样。
单个块经逆变换后含有混叠分量。通过适当加窗和重叠相加合成,相邻块中的这些分量可以相互抵消,这一机制称为时域混叠消除。在分析与合成使用同一个对称窗的常见配置中,一个核心的窗函数条件为
同时还须满足所要求的对称性和归一化约定。这种构造能够在量化前实现完美重建,同时减少编码块之间的不连续性。
AAC、Vorbis 等音频格式采用了基于 MDCT 的结构;MPEG Layer III 则将 MDCT 与多相滤波器组级相结合。感知编码器根据听觉掩蔽模型对系数进行量化。较长的窗能提高频率分辨能力,较短的窗则能改善瞬态附近的时间定位。窗切换有助于抑制预回声,即与突发声音相关的量化噪声在该声音起始之前就已变得可闻的现象。
普通 DCT 的另一种用途见于梅尔频率倒谱系数(MFCC)。典型的处理流程是先计算短时频谱,在按梅尔尺度分布的滤波器中累积频谱能量,然后取对数,再进行 DCT-II 变换。所得系数概括的是滤波器组对数谱的形状,而非原始波形。
仅保留低阶倒谱系数,可以紧凑地描述频谱包络的整体结构。这种表示已广泛用于语音识别和说话人分析。DCT 还往往能降低滤波器组相邻通道对数输出之间的相关性,这在过去很适合协方差结构受限的统计模型。不过,这种去相关只是近似的,保留下来的系数并不能保存全部语音信息。
这些应用体现了两种不同的作用:由余弦变换衍生的重叠变换可用于能够重建信号的音频编码,而常规 DCT 则可用于生成有意精简的描述性特征。
微分方程与谱计算
余弦变换在数值分析中很有用,因为它的基向量是某些离散微分算子的特征向量。其中,边界处的对称性至关重要。偶延拓自然对应于反射边界上法向导数为零的条件,因此,DCT 方法与具有齐次诺伊曼条件的边值问题密切相关。
考虑一个一维网格,其中有 个定义在网格单元中心的数值,网格间距为 。定义取正号的离散负拉普拉斯算子如下:
以及
端点处的公式对应于通过反射设置的虚拟网格值 和 。DCT-II 的基向量可将该算子对角化,其特征值为
因此,求解 可归结为:对 进行 DCT,将每个非零频率的系数除以 ,再进行逆变换。这就构成了相应离散泊松方程的一种快速直接求解方法。
零频率对应的特征值为 ,这反映出:给诺伊曼问题的解加上一个常数,并不会改变其导数。只有当源项满足离散相容性条件时,解才存在;这里的相容性条件就是均值为零。此时,解仅在相差一个加性常数的意义下确定;指定解的均值即可消除这一自由度。
在多维矩形区域中,各坐标方向上的特征值相加。因此,二维问题在非全零模态下可写为
可分离性使这类求解方法十分高效,但能否直接使用,取决于算子、网格、几何形状和边界条件。对于变系数和不规则区域,通常还需要借助其他方法。
DCT 还通过切比雪夫多项式与多项式逼近联系起来。切比雪夫多项式定义为
在以下节点对函数采样:
便可将采样值与切比雪夫展开系数之间的转换化为与 DCT-II 相关的运算。如果采用包含两个端点的采样节点 ,则相应地使用 DCT-I。这一联系为光滑函数的快速插值和谱方法提供了基础。
这两种用途需要对频率作出不同的解释。在微分算子的情形中,余弦向量描述的是空间网格上的模态;而在切比雪夫逼近中,同样的三角函数结构通过非线性坐标变换表示,成为多项式基。
历史发展与其他变换方案
Ahmed、Natarajan 和 Rao 于 1974 年发表的论文《离散余弦变换》,确立了这种变换在去除相关数据的相关性及紧凑表示这类数据方面的价值。它的吸引力在于兼具固定基、对重要信源模型下统计自适应变换的良好近似,以及适合快速算法的计算结构。
此后,快速实现方法的发展对其实际应用至关重要。Chen、Smith 和 Fralick 于 1977 年开展的研究及后续的因子分解方法降低了算术运算成本,并推动了专用变换硬件的实现。对广义离散变换族的研究,则阐明了各类离散余弦变换、正弦变换、傅里叶变换、对称性及边界条件之间的关系。
标准化使离散余弦变换成为广泛部署的基础组件。JPEG 的首个国际标准于 1992 年发布,MPEG-1 随后于 1993 年成为国际标准。这些系统将变换编码引入了数字摄影、图像交换、存储式视频和多媒体分发领域。它们的成功并非仅仅依靠离散余弦变换,还得益于它与量化、预测、系数排序及高效符号编码的结合。
不过,这种变换仍存在结构上的局限。普通的分块离散余弦变换所用的基函数局限于单个块内,却遍及整个块。与整幅图像的傅里叶变换相比,它能更好地将信息局部化,但无法使其支撑域适应任意形状的边缘。小块能改善空间局部化,但代价是频率分辨能力下降、块边界增多。大块能提高频率分辨率,却可能使局部不连续性的影响扩散到更多系数上。
小波变换采用不同的时频或空频组织方式,具有多个尺度和局部化的基函数。JPEG 2000 于 2000 年首次标准化,采用基于小波的编码,而非传统 JPEG 所用的分块离散余弦变换。重叠变换通过块间重叠来处理块边界问题,而方向性表示能够更高效地描述边缘和细长特征。
自适应变换和学习型变换则寻求另一种权衡。与固定的余弦基相比,它们能更贴合特定的信源分布,但可能需要传输模型、进行训练、增加计算量,或采用更复杂的解码器规范。提高系数稀疏性的变换并不一定能提高总体编码效率:描述变换和编码其系数的开销同样重要。
当固定、可分离且良态的变换适合任务需求时,离散余弦变换依然有用。因此,它的数学意义远超任何单一的编解码器:同一种余弦结构既可用作压缩基、近似的统计去相关工具或特征构建操作,也可作为某个给定离散算子的精确特征基。