三個印度人改變壓縮演算法,一意孤行整個暑假,卻因簡單申不到經費

明敏 豐色 發自 凹非寺

量子位 | 公眾號 QbitAI

世界上最好用的壓縮軟體是什麼?

微信。

這個段子想必很多人都聽過。

一張幾兆的圖片,經微信一發,立馬降到幾百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的認可。

參考連結:

[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

x— 完 —

量子位 QbitAI · 頭條號簽約

頂部