三個(gè)印度人改變壓縮算法,一意孤行整個(gè)暑假,卻因簡單申不到經(jīng)費(fèi)
本文經(jīng)AI新媒體量子位(公眾號(hào)ID:QbitAI)授權(quán)轉(zhuǎn)載,轉(zhuǎn)載請(qǐng)聯(lián)系出處。
世界上最好用的壓縮軟件是什么?
微信。
這個(gè)段子想必很多人都聽過。
一張幾兆的圖片,經(jīng)微信一發(fā),立馬降到幾百kb。
△如果是有損壓縮畫質(zhì)會(huì)下降(右圖天空有波紋)
雖說這是個(gè)吐槽,但u1s1,圖片視頻壓縮其實(shí)是一項(xiàng)非常必要的技術(shù)。
比如視頻通話、傳輸大量圖片時(shí),如果不壓縮的話,要么圖像完全無法傳送,要么就是干等了。
所以在數(shù)字時(shí)代這幾十年里,萌生出了很多相關(guān)的技術(shù),比如JPEG、H.26X。
不過你或許不知道,這些技術(shù)往上追溯,可以從47年前說起。
有三位名不見經(jīng)傳的印度工程師“一意孤行”,在沒申請(qǐng)到研究經(jīng)費(fèi)的情況下,利用暑假時(shí)間鼓搗出來了一項(xiàng)技術(shù),后來直接成為圖像視頻壓縮的行業(yè)標(biāo)準(zhǔn)。
它就是DCT。
全稱為Discrete Cosine Transform,即離散余弦變換。
而有趣的是,DCT誕生之初時(shí),就連作者本人都沒有想到,它后來會(huì)有如此巨大的影響力。
沒有DCT,就沒有JPEG/MPEG
直接說DCT可能很多人不知道是什么,但JPEG大家肯定都聽過。
它除了是一種常見的圖片文件后綴名,其實(shí)也是一種有損壓縮標(biāo)準(zhǔn),可以把一張圖片從左邊這樣變成右邊這樣:
ps.有損和無損的區(qū)別:無損壓縮可以再100%還原圖像;有損不可以,但有損壓縮后的圖像大小會(huì)大大減少。
DCT就是實(shí)現(xiàn)這個(gè)過程的一種基礎(chǔ)技術(shù)。
它是傅立葉變換的一種,可以將圖像從空域轉(zhuǎn)換到頻域,也就是把圖像從像素矩陣變成用帶有頻率等信息的函數(shù)來表示。
具體變換過程,我們以一張圖像中一個(gè)3x3的像素塊為例:
△ 圖源博客園博主@沉默的背影 X-Pacific
對(duì)這個(gè)像素塊做DTC變換,就相當(dāng)于把除了第一個(gè)像素以外,其余像素的部分信息都抽取到第一個(gè)格中。
這樣,第一個(gè)格的像素值表示的就是一張圖的總體樣貌,稱為低頻信息;其余格表示的就是圖像中人物或物體的細(xì)節(jié),稱為高頻信息。
經(jīng)DCT轉(zhuǎn)換后,每個(gè)3x3的像素塊都會(huì)產(chǎn)生1個(gè)DC(直流)系數(shù)(位于第一個(gè)格)及8個(gè)AC(交流)系數(shù)(剩余格),前者是DCT最重要的輸出。
由于大部分的圖像能量會(huì)集中在低頻部分,因此轉(zhuǎn)換之后輸出的DC系數(shù)值比較大,而輸出的AC系值比較小。
利用“人眼對(duì)低頻分量的圖像比對(duì)高頻分量的圖像更敏感”這一原理,再通過量化保存下來低頻分量,舍棄高頻分量(將大部分AC系數(shù)值變?yōu)?)、丟掉那些對(duì)視覺效果影響不大的信息,從而達(dá)到壓縮目的。
從下面這兩張圖像的三維投影,我們可以看到DCT變換帶來的改變:
(上:原圖;下:經(jīng)過DCT變換后)
在實(shí)際的JPEG壓縮標(biāo)準(zhǔn)中,都是將一張圖像分成若干個(gè)8x8的像素塊(不夠的用空白補(bǔ)齊)。
將色彩空間從RGB轉(zhuǎn)為YUV之后,從左至右、從上至下對(duì)每個(gè)塊進(jìn)行DCT變換。
然后對(duì)每個(gè)塊變換得來的系數(shù)進(jìn)行量化,在這個(gè)過程中,一些重要的分量就被去除了,且無法恢復(fù)。
因此,這是一種不可逆的有損壓縮技術(shù)。
接著對(duì)量化后得到的AC系數(shù)和DC系數(shù)再分別進(jìn)行編碼,經(jīng)過哈夫曼編碼后得到下面這樣的一大串?dāng)?shù)字。
解壓縮時(shí)對(duì)每個(gè)圖像塊做DCT反轉(zhuǎn)換(IDCT),就可以重建完整圖像。
具體計(jì)算過程如下:
首先將圖片中每個(gè)像素的原始灰度和亮度值用8bit表示,也就是(0,255)這個(gè)范圍。
由于大多數(shù)值都會(huì)分布在128左右,所以會(huì)將這些值都減去128,這樣會(huì)有更多值為0,有利于壓縮,這時(shí)候范圍變成(-128,127)。
然后再用DCT變換公式進(jìn)行變換,二維的用這個(gè):
變換完后進(jìn)行根據(jù)量化表進(jìn)行量化,將大部分系數(shù)變?yōu)?,完成壓縮。
ps.量化表是根據(jù)人眼對(duì)量化誤差的視覺閾值來確定的,有固定的一張表。
后面就是前面說的一系列編碼過程了。
1974年1月,這項(xiàng)技術(shù)首次被發(fā)表在IEEE Transactions on Computers上面。
自此,圖像和視頻壓縮領(lǐng)域的行業(yè)標(biāo)準(zhǔn)就誕生了。
1998年世界首個(gè)視頻壓縮標(biāo)準(zhǔn)H.261、1992年的JPEG和MPEG、2010年的WebP、2013年的HEIF、2018年谷歌亞馬遜等公司聯(lián)合創(chuàng)建的AV1……等壓縮標(biāo)準(zhǔn)都是基于這項(xiàng)技術(shù),且一直沿用至今。
40多年都名不見經(jīng)傳的發(fā)明者
DCT的作者有3位,分別是Nasir Ahmed(納西爾·艾哈邁德)、K.R. Rao(K.R.拉奧)和T. Natarajan(T.納塔拉詹)。
納西爾是新墨西哥大學(xué)電氣與計(jì)算機(jī)工程系名譽(yù)教授。
他1940年出生于印度班加羅爾,1966年在新墨西哥大學(xué)獲得博士學(xué)位。
1966-1968年,他在霍尼韋爾公司擔(dān)任首席工程師,1968-1983年在堪薩斯州立大學(xué)擔(dān)任教授。
1983-2001年,他回到新墨西哥大學(xué)擔(dān)任電氣與計(jì)算機(jī)工程系首席教授。在此期間,他先后擔(dān)任過系主任、研究生院院長等職位。
今年,納西爾已經(jīng)有82歲高齡。
另一位主要作者是K.R.拉奧。
他同樣是一位美籍印度裔學(xué)者。
1960年,他在佛羅里達(dá)大學(xué)獲得核工程專業(yè)博士學(xué)位。1966年,又在新墨西哥大學(xué)獲得電氣與計(jì)算機(jī)工程專業(yè)博士學(xué)位。
之后50年,他一直在得克薩斯州阿靈頓分校工作,擔(dān)任電氣工程系教授。
與此同時(shí),他還是IEEE Fellow。
2021年1月15日,拉奧教授揮別人世,享年89歲。
T.納塔拉詹當(dāng)時(shí)是納西爾帶的博士生,如今在互聯(lián)網(wǎng)上已經(jīng)檢索不到太多他的相關(guān)信息。
可以說相比于大名鼎鼎的DCT,幾位發(fā)明者稱得上是“名不見經(jīng)傳”了。
實(shí)際上,40多年來,DCT發(fā)明的幕后故事一直鮮有人關(guān)注。
甚至連納西爾的兒子都表示,“從來沒想過父親帶來的影響有如此之大”。
而將納西爾從幕后推至臺(tái)前的,還多虧了一部美劇中的一波致敬。
2020年,《我們的生活》中有一段劇情是納西爾以視頻通話的方式,講述了自己和妻子相愛的故事。
片方表示,設(shè)計(jì)這一橋段的初衷,就是希望更多人意識(shí)到,當(dāng)下我們能夠通過互聯(lián)網(wǎng)快速發(fā)送圖片視頻,都與納西爾的工作離不開關(guān)系。
劇情播出后,不少媒體將DCT定義為“改變世界的算法”,也稱納西爾這位名不見經(jīng)傳的工程師,終于從幕后推到了臺(tái)前。
不過,納西爾在自己的回憶視頻里表示,當(dāng)初真的沒想到DCT會(huì)帶來如此大的影響。
我也無法預(yù)測技術(shù)發(fā)展的速度,對(duì)于FaceTime這些應(yīng)用的出現(xiàn),我感到非常驚訝。
△納西爾年輕時(shí)(圖左)
要知道,DCT最初可能差一點(diǎn)就被扼殺在了搖籃里。
1972年,當(dāng)時(shí)已經(jīng)對(duì)DCT初有構(gòu)思的納西爾向美國國家科學(xué)基金會(huì)(NSF)遞交了一份申請(qǐng),希望NSF能為他研究DCT提供資金支持。
不過令納西爾驚訝的是,這個(gè)申請(qǐng)直接被斃掉了,評(píng)審人給出的意見是“它太簡單了”。
但好在納西爾并沒有放棄,他始終覺得這個(gè)idea很有新意。
唯一令他有所顧慮的是,他可能是只能利用假期來完成DCT的相關(guān)工作了,而且這期間可能沒有任何收入。
所以,納西爾回家和妻子說:
我有直覺,這事兒值得做下去。只不過我們需要計(jì)劃好如何度過一個(gè)沒有薪水的暑假。
妻子沒有任何猶豫就支持了他。
于是,在1973年的夏天,DCT的研究工作正式開始了。
參與到這項(xiàng)研究的,還有納西爾的好友拉奧和博士生納塔拉詹。
拉奧也是支持納西爾研究DCT的重要人物之一。
在納西爾的申請(qǐng)被斃掉后,他第一時(shí)間把自己的想法告訴了好友拉奧。
拉奧給出了這樣的回復(fù):
你要立即把這些結(jié)果以短文的形式發(fā)表。
這就是“How I Came Up with the Discrete Cosine Transform”誕生的始末。
后來,這篇文章幾乎稱得上是圖片視頻壓縮領(lǐng)域的必讀之文。
之后的故事,也就是我們所熟知的了。
1974年,《Discrete Cosine Transform》在IEEE Transactions on Computers上發(fā)表。
截至目前,這篇文章的被引次數(shù)已經(jīng)達(dá)到5878次。
納西爾曾在采訪中表示,自己人生中最大的禮物,就是人們對(duì)DCT的認(rèn)可。