你们知道DCT究竟有多重要吗

Nasir Ahmed

声影传奇

#003#

前段时间，LiveVideoStack发布了一篇文章《视频压缩简史：从1920到2020》，这篇文章获得了很高的阅读量，文章中记录了一个又一个视频压缩历史上的里程碑事件，而其中最引人注目，也最重要的发明之一就是DCT。没有DCT，后面的H.26X， JPEG等一系列压缩标准将无从谈起。

什么是DCT？

随着现代人越来越依赖计算机，需要传输的数据数量和种类也越来越多，比如我们经常分享给别人的照片和视频。如何在不丢失主要信息的情况下，缩减数据量，提升存储空间，从而提高传输效率，降低传输成本呢？

数据压缩技术登场了。数据压缩分为无损压缩和有损压缩。无损压缩是指数据在解压缩时可以100%被恢复，而有损压缩（常用于声音、图片和视频的压缩）在解压缩的过程中会舍弃一部分数据，达到相对较高的压缩比，同时图像质量也会有所下降。但显而易见，有损压缩可以大大压缩文件数据，节省磁盘空间，并提高传输效率。

而有损压缩的核心之一就是DCT。

DCT全称为Discrete Cosine Transform，即离散余弦变换。DCT变换属于傅里叶变换的一种，常用于对信号和图像（包括图片和视频）进行有损数据压缩。

DCT将图像分成由不同频率组成的小块，然后进行量化。在量化过程中，舍弃高频分量，剩下的低频分量被保存下来用于后面的图像重建。

简单介绍一下整个图像压缩过程：

将图像分解为8*8的图像块

将表示像素的RGB系统转换成YUV系统

然后从左至右，从上至下对每个图像块做DCT变换，舍弃高频分量，保留低频分量

对余下的图像块进行量化压缩，由压缩后的数据所组成的图像大大缩减了存储空间

解压缩时对每个图像块做DCT反转换（IDCT），然后重建一幅完整的图像

由于舍弃了某些频率的图像，所以最终呈现出来的图像清晰度会有差异。

可以看到，压缩后的图像比原始图像模糊一些，但图像的主要特征仍然可以识别。

本质上，离散余弦变换需要一组N个相关（相似）的数据点，变换之后，返回N个去相关（不相似）的数据点（系数），其特点是能量被压缩在仅有的M个系数中，其中M《N。

技术文献中通常这样描述DCT，说它具备去相关性和能量集中的特性，初看可能稍有点难以理解。其中，DCT将矩阵的能量压缩到第一个元素中，被称为直流（DC）系数。其余的系数被称为交流（AC）系数。

这意味着输出的二维DCT的左上角被称为DC系数。它是DCT最重要的输出，包含了很多关于原始图像的信息。其余的系数被称为交流系数（AC coefficients）。如果你使用DCT对图像进行转换，AC系数包含了图像的更多细节。同时，如果把这些DCT系数应用于反向的2D-DCT，将得到原始系数。DCT本身并不会压缩数据，它为随后的量化之类的操作，提供了一个良好的基础。

DCT是谁发明的？

第一个提出DCT的人是Nasir Ahmed。

1940年，Nasir出生于印度的班加罗尔，并在那里完成了电机工程的本科学业。随后，他来到美国求学。在新墨西哥大学，他获得了电子和计算机工程专业的硕士和博士学位。

1966~1968年，Nasir就职于霍尼韦尔公司，之后在堪萨斯州立大学开始了他的教学生涯。1984年，他成为新墨西哥大学电子和计算机工程专业的教授，并一直留在那里任教，直到2001年退休。他现在是新墨西哥大学的荣誉退休教授。

在任教期间，Nasir同时还是桑迪亚国家实验室的顾问（1976~1990），这所实验室归属于霍尼韦尔公司，专注于与大学和公司合作进行科技创新。

DCT是Nasir一生中最重要的成就。

20世纪70年代中期，Nasir在堪萨斯州立大学带领一组研究人员开发了DCT技术。

DCT是世界上应用最广泛的数据压缩转换技术，同时也是大多数数字媒体标准（图像、视频和音频）的基础。

DCT是如何被创造出来的？

在上世纪60~70年代，关于数字正交变换及其在图像数据压缩中应用的研究层出不穷。许多变换声称与其他变换相比具有更好的性能，但这些对比全部是建立在定性比较的基础上，即查看一组使用变换编码技术进行数据压缩的“标准”图像。

同一时期，在定量比较方面取得了重要进展。方差准则（variance criterion）和率失真标准（rate distortion criterion）被开发出来并广泛用于评估图像数据压缩的性能指标。此外，KLT（Karhunen-Loeve transform，K-L变换）一跃成为用作比较目的的最优变换。

正是在这样的技术背景下，Nasir才能开始着手解决DCT问题。

Nasir发现，KLT确实是基于均方误差准则和一阶马尔科夫模型的最佳变换，但是却缺少有效算法来计算它。于是，如何有效计算 KLT 的最佳近似值成为了他的研究重点。

他当时想到一种值得研究的方法——切比雪夫插值。1972年，他将这一想法写成一份提案，提交给了美国国家科学基金会（NSF），希望获得该基金会的资助。在提案中，Nasir提出使用切比雪夫多项式来研究“余弦变换”——也就是后来大名鼎鼎的DCT：

但令他非常失望的是，NSF 并没有为该提案提供资金，其中一位审查者给出的原因竟然是“太简单”。

不过Nasir并没有放弃，他找到了他的博士生T. Natarajan和他的朋友K.R.Rao，1973年的整个夏天，他们都在研究这一问题。最终，他们的研究有了结果，但这个结果好得让Nasir不敢相信。正巧之后Nasir要和Harry Andrews（美国数学家）一起出席新奥尔良的一个数学会议，所以Nasir决定在会上向他请教。

Harry Andrews建议Nasir使用率失真标准来检查这个“余弦变换”的性能，并发给他一个计算机程序帮助他计算结果。

最终，结果再次表明，DCT变换比其他所有变换都表现得更好，在性能上也与KLT十分接近。随后Harry Andrews建议Nasir发表这一成果。Nasir听从了他的建议，将论文以信件的形式发给了IEEE Computer Transactions（IEEE的通讯期刊），并在1974年1月获得发表。

据Nasir后来回忆，当初谁也没有想到DCT会在未来造成如此大的轰动。

DCT的重要性和其被发现的时间远不匹配，以至于Gilbert Strang在一篇1999年的论文中写道：“离散问题是如此之寻常，而且几乎是一个不可避免的问题，而让人异常惊讶的一个事实在于，业界直到1974年才由Nasir Ahmed等人发现了DCT。”最近也有一些研究证据表明，虽然DCT由 Ahmed 等人开发是一个无可置疑的事实，但冯诺依曼（John von Neumann）在1941年左右也对DCT做了一些开创性的研究，不过冯诺依曼自身可能并未意识到其重要性。

DCT的实现简介

DCT有8种形态，我们通常所说的DCT，其实指的是DCT-II，其对应的反变换是DCT-III。DCT-II、DCT-III的原始定义非常简单：

其中：X：X 是DCT输出.x：x 是DCT输入.k：k 是计算结果的输出数据索引， 从 0 to N?1N：N 变换元素的数目.s：s是缩放函数， 除去s（0）=0.5，其他s（y）=1

原始的N点的DCT-II变换算法最朴素的实现大概可以这样：

void dct_ii（int N， const double x［］， double X［］） { for （int k = 0; k 《 N; ++k） { double sum = 0.; double s = （k == 0） ？ sqrt（0.5） ： 1.; for （int n = 0; n 《 N; ++n） { sum += s * x［n］ * cos（PI * （n + 0.5） * k / N）; } X［k］ = sum * sqrt（2.0 / N）; }}

随后，DCT的一些快速算法陆续被开发出来，其中最引入注目的大概是LLM DCT（LLM 来自于三位对应算法的作者：Loeffler、Ligtenberg和 Moschytz，其论文“Practical Fast 1-D DCT Algorithms with 11 Multiplications”）和AAN DCT（AAN 的名字也来自于三位算法作者： Arai、Agui 和 Nakajima，其对应的论文是“A fast DCT-SQ scheme for images”）。

LLM DCT的算法流程如下：

它引入了非常经典的蝶形：

需要注意的是，LLM DCT的算法论文中，蝶形图的标识说明里面还有一个明显的错误在上面，其描述中，O1 均出现两次，明显第一个应该是O0。

AAN DCT的计算流程如下，该算法使用了五个乘法（加上八个用于缩放的后乘法，文章中认为这不算，因为它们可以被移到后面的量化矩阵中被平摊掉）。

以H.264标准为例，它实际上是把DCT 变换和后续的量化放在了一起，以减轻DCT变换计算的复杂度，所以有时候看H.264的DCT变换系数，你甚至第一眼很难想象它其实是个DCT的变换；从H.264的时代开始，DCT的变换开始使用整数变换，避免类似MPEG2年代因不同DCT、IDCT实现精度带来的编码、解码不完全匹配的问题。

DCT的应用

DCT的去相关和能量压缩特性使其在图像和视频压缩中极具吸引力。Karhunen-Loève变换（KLT）通常被称为理想变换，具有更好的去重特性，但在计算上是难以解决的。另一方面，DCT很容易编程，这使得它迅速占领了图像和视频压缩领域。现在常见的图片、视频压缩，如JPEG、H.26X、MPEG等，都用到了DCT。

图像

Nasir近况

今年二月份，在热播美剧《我们的生活》（This is Us）第5季第8集中，穿插了一段“艾哈迈德夫妇的故事”。这段故事取材于现实，讲述的正是Nasir和他的太太Esther之间发生的事。两人是新墨西哥大学的校友，在一次大学国际学生聚会中偶然结识并相恋，然后步入了婚姻殿堂，并且一直相知相守到今天。2018年，Nasir和Esther还出版了一本讲述他们生活故事的限量版图书——Parallel Lives In Curved Space。去年，两人庆祝了他们的结婚56周年纪念日。

《我们的生活》剧组工作人员正在和Nasir、Esther视频对话

为什么要在《我们的生活》剧集中穿插这样一段故事？

原来导演是想通过这个故事向DCT技术的发明者Nasir Ahmed致敬。如果没有Nasir，剧中的皮尔森一家不可能在新冠疫情期间通过视频会话保持联系，慰藉彼此。

现实中的我们也是一样。

编辑：jq