压缩算法的极限(三个印度人改变压缩算法)

明敏 丰色 发自 凹非寺量子位 | 公众号 QbitAI

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

微信。

这个段子想必很多人都听过。

一张几兆的图片,经微信一发,立马降到几百kb。

压缩算法的极限(三个印度人改变压缩算法)(1)

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

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

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

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

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

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

它就是DCT

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

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

没有DCT,就没有JPEG/MPEG

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

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

压缩算法的极限(三个印度人改变压缩算法)(2)

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

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

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

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

压缩算法的极限(三个印度人改变压缩算法)(3)

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

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

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

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

压缩算法的极限(三个印度人改变压缩算法)(4)

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

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

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

(上:原图;下:经过DCT变换后)

压缩算法的极限(三个印度人改变压缩算法)(5)

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

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

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

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

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

压缩算法的极限(三个印度人改变压缩算法)(6)

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

具体计算过程如下:

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

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

压缩算法的极限(三个印度人改变压缩算法)(7)

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

压缩算法的极限(三个印度人改变压缩算法)(8)

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

压缩算法的极限(三个印度人改变压缩算法)(9)

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岁高龄。

压缩算法的极限(三个印度人改变压缩算法)(10)

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

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

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

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

与此同时,他还是IEEE Fellow。

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

压缩算法的极限(三个印度人改变压缩算法)(11)

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

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

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

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

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

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

压缩算法的极限(三个印度人改变压缩算法)(12)

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

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

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

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

压缩算法的极限(三个印度人改变压缩算法)(13)

△纳西尔年轻时(图左)

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

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

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

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

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

所以,纳西尔回家和妻子说:

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

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

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

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

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

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

拉奥给出了这样的回复:

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

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

压缩算法的极限(三个印度人改变压缩算法)(14)

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

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

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

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

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

参考链接:[1]https://spectrum.ieee.org/krrao-tributehttps://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

x— 完 —

量子位 QbitAI · 头条号签约

关注我们,第一时间获知前沿科技动态

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页