Nasir Ahmed

聲影傳奇

#003#

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

什么是DCT？

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

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

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

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

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

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

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

將表示像素的RGB系統轉換成YUV系統

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

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

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

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

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

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

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

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

DCT是誰發明的？

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

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

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

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

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

20世紀70年代中期，Nasir在堪薩斯州立大學帶領一組研究人員開發了DCT技術。

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

DCT是如何被創造出來的？

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

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

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

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

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

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

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

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

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

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

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

DCT的實現簡介

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

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

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

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的一些快速算法陸續被開發出來，其中最引入注目的大概是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的算法流程如下：

它引入了非常經典的蝶形：

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

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

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

DCT的應用

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

圖像

Nasir近況

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

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

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

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

現實中的我們也是一樣。

編輯：jq