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

量子位 2022/7/10 13:44:20 责编:问舟

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

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

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

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

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

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

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

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

它就是 DCT。

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

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

没有 DCT,就没有 JPEG / MPEG

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

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

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

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

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

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

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

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

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

经 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 的认可。

相关文章

关键词:压缩

软媒旗下网站: IT之家 辣品 - 超值导购,优惠券 最会买 - 返利返现优惠券 iPhone之家 Win7之家 Win10之家 Win11之家

软媒旗下软件: 魔方 云日历 酷点桌面 Win7优化大师 Win10优化大师 软媒手机APP应用