Nasir Ahmed

聲影傳奇

#003#

前段時間，LiveVideoStack發(fā)布了一篇文章《視頻壓縮簡史：從1920到2020》，這篇文章獲得了很高的閱讀量，文章中記錄了一個又一個視頻壓縮歷史上的里程碑事件，而其中最引人注目，也最重要的發(fā)明之一就是DCT。沒有DCT，后面的H.26X， JPEG等一系列壓縮標準將無從談起。

什么是DCT？

隨著現(xiàn)代人越來越依賴計算機，需要傳輸?shù)臄?shù)據(jù)數(shù)量和種類也越來越多，比如我們經(jīng)常分享給別人的照片和視頻。如何在不丟失主要信息的情況下，縮減數(shù)據(jù)量，提升存儲空間，從而提高傳輸效率，降低傳輸成本呢？

數(shù)據(jù)壓縮技術(shù)登場了。數(shù)據(jù)壓縮分為無損壓縮和有損壓縮。無損壓縮是指數(shù)據(jù)在解壓縮時可以100%被恢復，而有損壓縮（常用于聲音、圖片和視頻的壓縮）在解壓縮的過程中會舍棄一部分數(shù)據(jù)，達到相對較高的壓縮比，同時圖像質(zhì)量也會有所下降。但顯而易見，有損壓縮可以大大壓縮文件數(shù)據(jù)，節(jié)省磁盤空間，并提高傳輸效率。

而有損壓縮的核心之一就是DCT。

DCT全稱為Discrete Cosine Transform，即離散余弦變換。DCT變換屬于傅里葉變換的一種，常用于對信號和圖像（包括圖片和視頻）進行有損數(shù)據(jù)壓縮。

DCT將圖像分成由不同頻率組成的小塊，然后進行量化。在量化過程中，舍棄高頻分量，剩下的低頻分量被保存下來用于后面的圖像重建。

簡單介紹一下整個圖像壓縮過程：

將圖像分解為8*8的圖像塊

將表示像素的RGB系統(tǒng)轉(zhuǎn)換成YUV系統(tǒng)

然后從左至右，從上至下對每個圖像塊做DCT變換，舍棄高頻分量，保留低頻分量

對余下的圖像塊進行量化壓縮，由壓縮后的數(shù)據(jù)所組成的圖像大大縮減了存儲空間

解壓縮時對每個圖像塊做DCT反轉(zhuǎn)換（IDCT），然后重建一幅完整的圖像

由于舍棄了某些頻率的圖像，所以最終呈現(xiàn)出來的圖像清晰度會有差異。

可以看到，壓縮后的圖像比原始圖像模糊一些，但圖像的主要特征仍然可以識別。

本質(zhì)上，離散余弦變換需要一組N個相關(guān)（相似）的數(shù)據(jù)點，變換之后，返回N個去相關(guān)（不相似）的數(shù)據(jù)點（系數(shù)），其特點是能量被壓縮在僅有的M個系數(shù)中，其中M《N。

技術(shù)文獻中通常這樣描述DCT，說它具備去相關(guān)性和能量集中的特性，初看可能稍有點難以理解。其中，DCT將矩陣的能量壓縮到第一個元素中，被稱為直流（DC）系數(shù)。其余的系數(shù)被稱為交流（AC）系數(shù)。

這意味著輸出的二維DCT的左上角被稱為DC系數(shù)。它是DCT最重要的輸出，包含了很多關(guān)于原始圖像的信息。其余的系數(shù)被稱為交流系數(shù)（AC coefficients）。如果你使用DCT對圖像進行轉(zhuǎn)換，AC系數(shù)包含了圖像的更多細節(jié)。同時，如果把這些DCT系數(shù)應用于反向的2D-DCT，將得到原始系數(shù)。DCT本身并不會壓縮數(shù)據(jù)，它為隨后的量化之類的操作，提供了一個良好的基礎。

DCT是誰發(fā)明的？

第一個提出DCT的人是Nasir Ahmed。

1940年，Nasir出生于印度的班加羅爾，并在那里完成了電機工程的本科學業(yè)。隨后，他來到美國求學。在新墨西哥大學，他獲得了電子和計算機工程專業(yè)的碩士和博士學位。

1966~1968年，Nasir就職于霍尼韋爾公司，之后在堪薩斯州立大學開始了他的教學生涯。1984年，他成為新墨西哥大學電子和計算機工程專業(yè)的教授，并一直留在那里任教，直到2001年退休。他現(xiàn)在是新墨西哥大學的榮譽退休教授。

在任教期間，Nasir同時還是桑迪亞國家實驗室的顧問（1976~1990），這所實驗室歸屬于霍尼韋爾公司，專注于與大學和公司合作進行科技創(chuàng)新。

DCT是Nasir一生中最重要的成就。

20世紀70年代中期，Nasir在堪薩斯州立大學帶領(lǐng)一組研究人員開發(fā)了DCT技術(shù)。

DCT是世界上應用最廣泛的數(shù)據(jù)壓縮轉(zhuǎn)換技術(shù)，同時也是大多數(shù)數(shù)字媒體標準（圖像、視頻和音頻）的基礎。

DCT是如何被創(chuàng)造出來的？

在上世紀60~70年代，關(guān)于數(shù)字正交變換及其在圖像數(shù)據(jù)壓縮中應用的研究層出不窮。許多變換聲稱與其他變換相比具有更好的性能，但這些對比全部是建立在定性比較的基礎上，即查看一組使用變換編碼技術(shù)進行數(shù)據(jù)壓縮的“標準”圖像。

同一時期，在定量比較方面取得了重要進展。方差準則（variance criterion）和率失真標準（rate distortion criterion）被開發(fā)出來并廣泛用于評估圖像數(shù)據(jù)壓縮的性能指標。此外，KLT（Karhunen-Loeve transform，K-L變換）一躍成為用作比較目的的最優(yōu)變換。

正是在這樣的技術(shù)背景下，Nasir才能開始著手解決DCT問題。

Nasir發(fā)現(xiàn)，KLT確實是基于均方誤差準則和一階馬爾科夫模型的最佳變換，但是卻缺少有效算法來計算它。于是，如何有效計算 KLT 的最佳近似值成為了他的研究重點。

他當時想到一種值得研究的方法——切比雪夫插值。1972年，他將這一想法寫成一份提案，提交給了美國國家科學基金會（NSF），希望獲得該基金會的資助。在提案中，Nasir提出使用切比雪夫多項式來研究“余弦變換”——也就是后來大名鼎鼎的DCT：

但令他非常失望的是，NSF 并沒有為該提案提供資金，其中一位審查者給出的原因竟然是“太簡單”。

不過Nasir并沒有放棄，他找到了他的博士生T. Natarajan和他的朋友K.R.Rao，1973年的整個夏天，他們都在研究這一問題。最終，他們的研究有了結(jié)果，但這個結(jié)果好得讓Nasir不敢相信。正巧之后Nasir要和Harry Andrews（美國數(shù)學家）一起出席新奧爾良的一個數(shù)學會議，所以Nasir決定在會上向他請教。

Harry Andrews建議Nasir使用率失真標準來檢查這個“余弦變換”的性能，并發(fā)給他一個計算機程序幫助他計算結(jié)果。

最終，結(jié)果再次表明，DCT變換比其他所有變換都表現(xiàn)得更好，在性能上也與KLT十分接近。隨后Harry Andrews建議Nasir發(fā)表這一成果。Nasir聽從了他的建議，將論文以信件的形式發(fā)給了IEEE Computer Transactions（IEEE的通訊期刊），并在1974年1月獲得發(fā)表。

據(jù)Nasir后來回憶，當初誰也沒有想到DCT會在未來造成如此大的轟動。

DCT的重要性和其被發(fā)現(xiàn)的時間遠不匹配，以至于Gilbert Strang在一篇1999年的論文中寫道：“離散問題是如此之尋常，而且?guī)缀跏且粋€不可避免的問題，而讓人異常驚訝的一個事實在于，業(yè)界直到1974年才由Nasir Ahmed等人發(fā)現(xiàn)了DCT。”最近也有一些研究證據(jù)表明，雖然DCT由 Ahmed 等人開發(fā)是一個無可置疑的事實，但馮諾依曼（John von Neumann）在1941年左右也對DCT做了一些開創(chuàng)性的研究，不過馮諾依曼自身可能并未意識到其重要性。

DCT的實現(xiàn)簡介

DCT有8種形態(tài)，我們通常所說的DCT，其實指的是DCT-II，其對應的反變換是DCT-III。DCT-II、DCT-III的原始定義非常簡單：

其中：X：X 是DCT輸出.x：x 是DCT輸入.k：k 是計算結(jié)果的輸出數(shù)據(jù)索引， 從 0 to N?1N：N 變換元素的數(shù)目.s：s是縮放函數(shù)， 除去s（0）=0.5，其他s（y）=1

原始的N點的DCT-II變換算法最樸素的實現(xiàn)大概可以這樣：

void dct_ii（int N， const double x［］， double X［］） { for （int k = 0; k 《 N; ++k） { double sum = 0.; double s = （k == 0） ？ sqrt（0.5） ： 1.; for （int n = 0; n 《 N; ++n） { sum += s * x［n］ * cos（PI * （n + 0.5） * k / N）; } X［k］ = sum * sqrt（2.0 / N）; }}

隨后，DCT的一些快速算法陸續(xù)被開發(fā)出來，其中最引入注目的大概是LLM DCT（LLM 來自于三位對應算法的作者：Loeffler、Ligtenberg和 Moschytz，其論文“Practical Fast 1-D DCT Algorithms with 11 Multiplications”）和AAN DCT（AAN 的名字也來自于三位算法作者： Arai、Agui 和 Nakajima，其對應的論文是“A fast DCT-SQ scheme for images”）。

LLM DCT的算法流程如下：

它引入了非常經(jīng)典的蝶形：

需要注意的是，LLM DCT的算法論文中，蝶形圖的標識說明里面還有一個明顯的錯誤在上面，其描述中，O1 均出現(xiàn)兩次，明顯第一個應該是O0。

AAN DCT的計算流程如下，該算法使用了五個乘法（加上八個用于縮放的后乘法，文章中認為這不算，因為它們可以被移到后面的量化矩陣中被平攤掉）。

以H.264標準為例，它實際上是把DCT 變換和后續(xù)的量化放在了一起，以減輕DCT變換計算的復雜度，所以有時候看H.264的DCT變換系數(shù)，你甚至第一眼很難想象它其實是個DCT的變換；從H.264的時代開始，DCT的變換開始使用整數(shù)變換，避免類似MPEG2年代因不同DCT、IDCT實現(xiàn)精度帶來的編碼、解碼不完全匹配的問題。

DCT的應用

DCT的去相關(guān)和能量壓縮特性使其在圖像和視頻壓縮中極具吸引力。Karhunen-Loève變換（KLT）通常被稱為理想變換，具有更好的去重特性，但在計算上是難以解決的。另一方面，DCT很容易編程，這使得它迅速占領(lǐng)了圖像和視頻壓縮領(lǐng)域。現(xiàn)在常見的圖片、視頻壓縮，如JPEG、H.26X、MPEG等，都用到了DCT。

圖像

Nasir近況

今年二月份，在熱播美劇《我們的生活》（This is Us）第5季第8集中，穿插了一段“艾哈邁德夫婦的故事”。這段故事取材于現(xiàn)實，講述的正是Nasir和他的太太Esther之間發(fā)生的事。兩人是新墨西哥大學的校友，在一次大學國際學生聚會中偶然結(jié)識并相戀，然后步入了婚姻殿堂，并且一直相知相守到今天。2018年，Nasir和Esther還出版了一本講述他們生活故事的限量版圖書——Parallel Lives In Curved Space。去年，兩人慶祝了他們的結(jié)婚56周年紀念日。

《我們的生活》劇組工作人員正在和Nasir、Esther視頻對話

為什么要在《我們的生活》劇集中穿插這樣一段故事？

原來導演是想通過這個故事向DCT技術(shù)的發(fā)明者Nasir Ahmed致敬。如果沒有Nasir，劇中的皮爾森一家不可能在新冠疫情期間通過視頻會話保持聯(lián)系，慰藉彼此。

現(xiàn)實中的我們也是一樣。

編輯：jq