你們知道DCT究竟有多重要嗎

Nasir Ahmed

聲影傳奇

#003#

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

什么是DCT？

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

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

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

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

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

簡(jiǎn)單介紹一下整個(gè)圖像壓縮過(guò)程：

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

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

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

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

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

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

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

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

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

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

DCT是誰(shuí)發(fā)明的？

第一個(gè)提出DCT的人是Nasir Ahmed。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Harry Andrews建議Nasir使用率失真標(biāo)準(zhǔn)來(lái)檢查這個(gè)“余弦變換”的性能，并發(fā)給他一個(gè)計(jì)算機(jī)程序幫助他計(jì)算結(jié)果。

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

據(jù)Nasir后來(lái)回憶，當(dāng)初誰(shuí)也沒(méi)有想到DCT會(huì)在未來(lái)造成如此大的轟動(dòng)。

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

DCT的實(shí)現(xiàn)簡(jiǎn)介

DCT有8種形態(tài)，我們通常所說(shuō)的DCT，其實(shí)指的是DCT-II，其對(duì)應(yīng)的反變換是DCT-III。DCT-II、DCT-III的原始定義非常簡(jiǎn)單：

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

原始的N點(diǎn)的DCT-II變換算法最樸素的實(shí)現(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ù)被開(kāi)發(fā)出來(lái)，其中最引入注目的大概是LLM DCT（LLM 來(lái)自于三位對(duì)應(yīng)算法的作者：Loeffler、Ligtenberg和 Moschytz，其論文“Practical Fast 1-D DCT Algorithms with 11 Multiplications”）和AAN DCT（AAN 的名字也來(lái)自于三位算法作者： Arai、Agui 和 Nakajima，其對(duì)應(yīng)的論文是“A fast DCT-SQ scheme for images”）。

LLM DCT的算法流程如下：

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

需要注意的是，LLM DCT的算法論文中，蝶形圖的標(biāo)識(shí)說(shuō)明里面還有一個(gè)明顯的錯(cuò)誤在上面，其描述中，O1 均出現(xiàn)兩次，明顯第一個(gè)應(yīng)該是O0。

AAN DCT的計(jì)算流程如下，該算法使用了五個(gè)乘法（加上八個(gè)用于縮放的后乘法，文章中認(rèn)為這不算，因?yàn)樗鼈兛梢员灰频胶竺娴牧炕仃囍斜黄綌偟簦?/p>

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

DCT的應(yīng)用

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

圖像

Nasir近況

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

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

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

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

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

編輯：jq