三个印度人改变压缩算法,一意孤行整个暑假,却因“太简单”申不到经费
用了47年一直到今天
明敏 丰色 发自 凹非寺
量子位 | 公众号 QbitAI
世界上最好用的压缩软件是什么?
微信。
这个段子想必很多人都听过。
一张几兆的图片,经微信一发,立马降到几百kb。
△如果是有损压缩画质会下降(右图天空有波纹)
虽说这是个吐槽,但u1s1,图片视频压缩其实是一项非常必要的技术。
比如视频通话、传输大量图片时,如果不压缩的话,要么图像完全无法传送,要么就是干等了。
所以在数字时代这几十年里,萌生出了很多相关的技术,比如JPEG、H.26X。
不过你或许不知道,这些技术往上追溯,可以从47年前说起。
有三位名不见经传的印度工程师“一意孤行”,在没申请到研究经费的情况下,利用暑假时间鼓捣出来了一项技术,后来直接成为图像视频压缩的行业标准。
它就是DCT。
全称为Discrete Cosine Transform,即离散余弦变换。
而有趣的是,DCT诞生之初时,就连作者本人都没有想到,它后来会有如此巨大的影响力。
没有DCT,就没有JPEG/MPEG
直接说DCT可能很多人不知道是什么,但JPEG大家肯定都听过。
它除了是一种常见的图片文件后缀名,其实也是一种有损压缩标准,可以把一张图片从左边这样变成右边这样:
ps.有损和无损的区别:无损压缩可以再100%还原图像;有损不可以,但有损压缩后的图像大小会大大减少。
DCT就是实现这个过程的一种基础技术。
它是傅立叶变换的一种,可以将图像从空域转换到频域,也就是把图像从像素矩阵变成用带有频率等信息的函数来表示。
具体变换过程,我们以一张图像中一个3×3的像素块为例:
△ 图源博客园博主@沉默的背影 X-Pacific
对这个像素块做DTC变换,就相当于把除了第一个像素以外,其余像素的部分信息都抽取到第一个格中。
这样,第一个格的像素值表示的就是一张图的总体样貌,称为低频信息;其余格表示的就是图像中人物或物体的细节,称为高频信息。
经DCT转换后,每个3×3的像素块都会产生1个DC(直流)系数(位于第一个格)及8个AC(交流)系数(剩余格),前者是DCT最重要的输出。
由于大部分的图像能量会集中在低频部分,因此转换之后输出的DC系数值比较大,而输出的AC系值比较小。
利用“人眼对低频分量的图像比对高频分量的图像更敏感”这一原理,再通过量化保存下来低频分量,舍弃高频分量(将大部分AC系数值变为0)、丢掉那些对视觉效果影响不大的信息,从而达到压缩目的。
从下面这两张图像的三维投影,我们可以看到DCT变换带来的改变:
(上:原图;下:经过DCT变换后)
在实际的JPEG压缩标准中,都是将一张图像分成若干个8×8的像素块(不够的用空白补齐)。
将色彩空间从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的认可。
参考链接:
[1]https://spectrum.ieee.org/krrao-tribute
https://www.islamicity.org/80703/nasir-ahmeds-algorithm-that-transformed-the-world/
[2]https://cloud.tencent.com/developer/article/1862531
[3]https://mp.weixin.qq.com/s?__biz=MzU1NTEzOTM5Mw==&mid=2247512538&idx=1&sn=57f46386002cf5554681f8ef9f61a3e0&chksm=fbda19f4ccad90e219bf224db522e9999086dff886bae09562e1aeba4450d4ba0247a73c3138&scene=21#wechat_redirect
[4]https://blog.csdn.net/freee12/article/details/109953732
[5]https://blog.csdn.net/weixin_52779958/article/details/124413405
[6]https://www.youtube.com/watch?v=I9VXaVVs7WY
- Sora突遭泄露!能力又进化了,OpenAI紧急拔线,抗议联名信惊现马斯克2024-11-27
- 黄仁勋港科大之行全程高能:对话沈向洋,现场发显卡,与梁朝伟共同获得荣誉博士学位2024-11-25
- 王炸!谁能想到年底杀出的黑马是美图啊2024-11-22
- 汽车上的《Her》:模型竟然想做个人了,甩掉机械感,来自吉利2024-11-22