明敏 豐色 發自 凹非寺
量子位 | 公眾號 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 · 頭條號簽約