世界快资讯丨三个印度人改变压缩算法 一意孤行整个暑假 却因“太简单”申不到经费

• 2022-07-11 05:50:26 来源：凤凰网

世界上最好用的压缩软件是什么？微信。

(资料图)

这个段子想必很多人都听过。一张几兆的图片，经微信一发，立马降到几百 kb。

△ 如果是有损压缩画质会下降（右图天空有波纹）

虽说这是个吐槽，但 u1s1，图片视频压缩其实是一项非常必要的技术。

比如视频通话、传输大量图片时，如果不压缩的话，要么图像完全无法传送，要么就是干等了。

所以在数字时代这几十年里，萌生出了很多相关的技术，比如 JPEG、H.26X。

不过你或许不知道，这些技术往上追溯，可以从 47 年前说起。

有三位名不见经传的印度工程师“一意孤行”，在没申请到研究经费的情况下，利用暑假时间鼓捣出来了一项技术，后来直接成为图像视频压缩的行业标准。

它就是 DCT。

全称为 Discrete Cosine Transform，即离散余弦变换。

而有趣的是，DCT 诞生之初时，就连作者本人都没有想到，它后来会有如此巨大的影响力。

没有 DCT，就没有 JPEG / MPEG

直接说 DCT 可能很多人不知道是什么，但 JPEG 大家肯定都听过。

它除了是一种常见的图片文件后缀名，其实也是一种有损压缩标准，可以把一张图片从左边这样变成右边这样：

ps.有损和无损的区别：无损压缩可以再 100% 还原图像；有损不可以，但有损压缩后的图像大小会大大减少。

DCT 就是实现这个过程的一种基础技术。

它是傅立叶变换的一种，可以将图像从空域转换到频域，也就是把图像从像素矩阵变成用带有频率等信息的函数来表示。

具体变换过程，我们以一张图像中一个 3x3 的像素块为例：

△ 图源博客园博主 @沉默的背影 X-Pacific

对这个像素块做 DTC 变换，就相当于把除了第一个像素以外，其余像素的部分信息都抽取到第一个格中。

这样，第一个格的像素值表示的就是一张图的总体样貌，称为低频信息；其余格表示的就是图像中人物或物体的细节，称为高频信息。

经 DCT 转换后，每个 3x3 的像素块都会产生 1 个 DC（直流）系数（位于第一个格）及 8 个 AC（交流）系数（剩余格），前者是 DCT 最重要的输出。

由于大部分的图像能量会集中在低频部分，因此转换之后输出的 DC 系数值比较大，而输出的 AC 系值比较小。

利用“人眼对低频分量的图像比对高频分量的图像更敏感”这一原理，再通过量化保存下来低频分量，舍弃高频分量（将大部分 AC 系数值变为 0）、丢掉那些对视觉效果影响不大的信息，从而达到压缩目的。

从下面这两张图像的三维投影，我们可以看到 DCT 变换带来的改变：

（上：原图；下：经过 DCT 变换后）

在实际的 JPEG 压缩标准中，都是将一张图像分成若干个 8x8 的像素块（不够的用空白补齐）。

将色彩空间从 RGB 转为 YUV 之后，从左至右、从上至下对每个块进行 DCT 变换。

然后对每个块变换得来的系数进行量化，在这个过程中，一些重要的分量就被去除了，且无法恢复。

因此，这是一种不可逆的有损压缩技术。

接着对量化后得到的 AC 系数和 DC 系数再分别进行编码，经过哈夫曼编码后得到下面这样的一大串数字。

解压缩时对每个图像块做 DCT 反转换（IDCT），就可以重建完整图像。

具体计算过程如下：

首先将图片中每个像素的原始灰度和亮度值用 8bit 表示，也就是 (0，255) 这个范围。

由于大多数值都会分布在 128 左右，所以会将这些值都减去 128，这样会有更多值为 0，有利于压缩，这时候范围变成 (-128，127)。

然后再用 DCT 变换公式进行变换，二维的用这个：

变换完后进行根据量化表进行量化，将大部分系数变为 0，完成压缩。

ps.量化表是根据人眼对量化误差的视觉阈值来确定的，有固定的一张表。

后面就是前面说的一系列编码过程了。

1974 年 1 月，这项技术首次被发表在 IEEE Transactions on Computers 上面。

自此，图像和视频压缩领域的行业标准就诞生了。

1998 年世界首个视频压缩标准 H.261、1992 年的 JPEG 和 MPEG、2010 年的 WebP、2013 年的 HEIF、2018 年谷歌亚马逊等公司联合创建的 AV1…… 等压缩标准都是基于这项技术，且一直沿用至今。

40 多年都名不见经传的发明者

DCT 的作者有 3 位，分别是 Nasir Ahmed（纳西尔・艾哈迈德）、K.R. Rao（K.R.拉奥）和 T. Natarajan（T.纳塔拉詹）。

纳西尔是新墨西哥大学电气与计算机工程系名誉教授。

他 1940 年出生于印度班加罗尔，1966 年在新墨西哥大学获得博士学位。

1966-1968 年，他在霍尼韦尔公司担任首席工程师，1968-1983 年在堪萨斯州立大学担任教授。

1983-2001 年，他回到新墨西哥大学担任电气与计算机工程系首席教授。在此期间，他先后担任过系主任、研究生院院长等职位。

今年，纳西尔已经有 82 岁高龄。

另一位主要作者是 K.R.拉奥。

他同样是一位美籍印度裔学者。

1960 年，他在佛罗里达大学获得核工程专业博士学位。1966 年，又在新墨西哥大学获得电气与计算机工程专业博士学位。

之后 50 年，他一直在得克萨斯州阿灵顿分校工作，担任电气工程系教授。

与此同时，他还是 IEEE Fellow。

2021 年 1 月 15 日，拉奥教授挥别人世，享年 89 岁。

T.纳塔拉詹当时是纳西尔带的博士生，如今在互联网上已经检索不到太多他的相关信息。

可以说相比于大名鼎鼎的 DCT，几位发明者称得上是“名不见经传”了。

实际上，40 多年来，DCT 发明的幕后故事一直鲜有人关注。

甚至连纳西尔的儿子都表示，“从来没想过父亲带来的影响有如此之大”。

而将纳西尔从幕后推至台前的，还多亏了一部美剧中的一波致敬。

2020 年，《我们的生活》中有一段剧情是纳西尔以视频通话的方式，讲述了自己和妻子相爱的故事。

片方表示，设计这一桥段的初衷，就是希望更多人意识到，当下我们能够通过互联网快速发送图片视频，都与纳西尔的工作离不开关系。

剧情播出后，不少媒体将 DCT 定义为“改变世界的算法”，也称纳西尔这位名不见经传的工程师，终于从幕后推到了台前。

不过，纳西尔在自己的回忆视频里表示，当初真的没想到 DCT 会带来如此大的影响。

我也无法预测技术发展的速度，对于 FaceTime 这些应用的出现，我感到非常惊讶。

△ 纳西尔年轻时（图左）

要知道，DCT 最初可能差一点就被扼杀在了摇篮里。

1972 年，当时已经对 DCT 初有构思的纳西尔向美国国家科学基金会（NSF）递交了一份申请，希望 NSF 能为他研究 DCT 提供资金支持。

不过令纳西尔惊讶的是，这个申请直接被毙掉了，评审人给出的意见是“它太简单了”。

但好在纳西尔并没有放弃，他始终觉得这个 idea 很有新意。

唯一令他有所顾虑的是，他可能是只能利用假期来完成 DCT 的相关工作了，而且这期间可能没有任何收入。

所以，纳西尔回家和妻子说：

我有直觉，这事儿值得做下去。只不过我们需要计划好如何度过一个没有薪水的暑假。

妻子没有任何犹豫就支持了他。

于是，在 1973 年的夏天，DCT 的研究工作正式开始了。

参与到这项研究的，还有纳西尔的好友拉奥和博士生纳塔拉詹。

拉奥也是支持纳西尔研究 DCT 的重要人物之一。

在纳西尔的申请被毙掉后，他第一时间把自己的想法告诉了好友拉奥。

拉奥给出了这样的回复：

你要立即把这些结果以短文的形式发表。

这就是“How I Came Up with the Discrete Cosine Transform”诞生的始末。

后来，这篇文章几乎称得上是图片视频压缩领域的必读之文。

之后的故事，也就是我们所熟知的了。

1974 年，《Discrete Cosine Transform》在 IEEE Transactions on Computers 上发表。

截至目前，这篇文章的被引次数已经达到 5878 次。

纳西尔曾在采访中表示，自己人生中最大的礼物，就是人们对 DCT 的认可。

标签： jpeg

推荐阅读

猜您喜欢