DCT如此重要，作者当初竟然不知道？
點(diǎn)擊上方“LiveVideoStack”關(guān)注我們
作者 |?Alex、趙軍
技術(shù)審校 | 趙軍
Nasir Ahmed
聲影傳奇
#003#
前段時間，LiveVideoStack發(fā)布了一篇文章《視頻壓縮簡史：從1920到2020》，這篇文章獲得了很高的閱讀量，文章中記錄了一個又一個視頻壓縮歷史上的里程碑事件，而其中最引人注目，也最重要的發(fā)明之一就是DCT。沒有DCT，后面的H.26X， JPEG等一系列壓縮標(biāo)準(zhǔn)將無從談起。
?
什么是DCT？
隨著現(xiàn)代人越來越依賴計算機(jī)，需要傳輸?shù)臄?shù)據(jù)數(shù)量和種類也越來越多，比如我們經(jīng)常分享給別人的照片和視頻。如何在不丟失主要信息的情況下，縮減數(shù)據(jù)量，提升存儲空間，從而提高傳輸效率，降低傳輸成本呢？
?
數(shù)據(jù)壓縮技術(shù)登場了。數(shù)據(jù)壓縮分為無損壓縮和有損壓縮。無損壓縮是指數(shù)據(jù)在解壓縮時可以100%被恢復(fù)，而有損壓縮（常用于聲音、圖片和視頻的壓縮）在解壓縮的過程中會舍棄一部分?jǐn)?shù)據(jù)，達(dá)到相對較高的壓縮比，同時圖像質(zhì)量也會有所下降。但顯而易見，有損壓縮可以大大壓縮文件數(shù)據(jù)，節(jié)省磁盤空間，并提高傳輸效率。
?
而有損壓縮的核心之一就是DCT。
?
DCT全稱為Discrete Cosine Transform，即離散余弦變換。DCT變換屬于傅里葉變換的一種，常用于對信號和圖像（包括圖片和視頻）進(jìn)行有損數(shù)據(jù)壓縮。
DCT將圖像分成由不同頻率組成的小塊，然后進(jìn)行量化。在量化過程中，舍棄高頻分量，剩下的低頻分量被保存下來用于后面的圖像重建。
?
簡單介紹一下整個圖像壓縮過程：
DCT 8*8圖像塊
?
將圖像分解為8*8的圖像塊
將表示像素的RGB系統(tǒng)轉(zhuǎn)換成YUV系統(tǒng)
然后從左至右，從上至下對每個圖像塊做DCT變換，舍棄高頻分量，保留低頻分量
對余下的圖像塊進(jìn)行量化壓縮，由壓縮后的數(shù)據(jù)所組成的圖像大大縮減了存儲空間
解壓縮時對每個圖像塊做DCT反轉(zhuǎn)換（IDCT），然后重建一幅完整的圖像
?
由于舍棄了某些頻率的圖像，所以最終呈現(xiàn)出來的圖像清晰度會有差異。
?
使用DCT壓縮前后：
圖片By Sid Shanker
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
可以看到，壓縮后的圖像比原始圖像模糊一些，但圖像的主要特征仍然可以識別。
?
本質(zhì)上，離散余弦變換需要一組N個相關(guān)（相似）的數(shù)據(jù)點(diǎn)，變換之后，返回N個去相關(guān)（不相似）的數(shù)據(jù)點(diǎn)（系數(shù)），其特點(diǎn)是能量被壓縮在僅有的M個系數(shù)中，其中M<N。
?
技術(shù)文獻(xiàn)中通常這樣描述DCT，說它具備去相關(guān)性和能量集中的特性，初看可能稍有點(diǎn)難以理解。其中，DCT將矩陣的能量壓縮到第一個元素中，被稱為直流(DC)系數(shù)。其余的系數(shù)被稱為交流(AC)系數(shù)。
?
這意味著輸出的二維DCT的左上角被稱為DC系數(shù)。它是DCT最重要的輸出，包含了很多關(guān)于原始圖像的信息。其余的系數(shù)被稱為交流系數(shù)（AC coefficients）。如果你使用DCT對圖像進(jìn)行轉(zhuǎn)換，AC系數(shù)包含了圖像的更多細(xì)節(jié)。同時，如果把這些DCT系數(shù)應(yīng)用于反向的2D-DCT，將得到原始系數(shù)。DCT本身并不會壓縮數(shù)據(jù)，它為隨后的量化之類的操作，提供了一個良好的基礎(chǔ)。
?
DCT是誰發(fā)明的？
第一個提出DCT的人是Nasir Ahmed。
?
?
Nasir Ahmed
?
1940年，Nasir出生于印度的班加羅爾，并在那里完成了電機(jī)工程的本科學(xué)業(yè)。隨后，他來到美國求學(xué)。在新墨西哥大學(xué)，他獲得了電子和計算機(jī)工程專業(yè)的碩士和博士學(xué)位。
?
1966~1968年，Nasir就職于霍尼韋爾公司，之后在堪薩斯州立大學(xué)開始了他的教學(xué)生涯。1984年，他成為新墨西哥大學(xué)電子和計算機(jī)工程專業(yè)的教授，并一直留在那里任教，直到2001年退休。他現(xiàn)在是新墨西哥大學(xué)的榮譽(yù)退休教授。
?
在任教期間，Nasir同時還是桑迪亞國家實(shí)驗(yàn)室的顧問（1976~1990），這所實(shí)驗(yàn)室歸屬于霍尼韋爾公司，專注于與大學(xué)和公司合作進(jìn)行科技創(chuàng)新。
?
DCT是Nasir一生中最重要的成就。
?
20世紀(jì)70年代中期，Nasir在堪薩斯州立大學(xué)帶領(lǐng)一組研究人員開發(fā)了DCT技術(shù)。
?
DCT是世界上應(yīng)用最廣泛的數(shù)據(jù)壓縮轉(zhuǎn)換技術(shù)，同時也是大多數(shù)數(shù)字媒體標(biāo)準(zhǔn)（圖像、視頻和音頻）的基礎(chǔ)。
DCT是如何被創(chuàng)造出來的？
在上世紀(jì)60~70年代，關(guān)于數(shù)字正交變換及其在圖像數(shù)據(jù)壓縮中應(yīng)用的研究層出不窮。許多變換聲稱與其他變換相比具有更好的性能，但這些對比全部是建立在定性比較的基礎(chǔ)上，即查看一組使用變換編碼技術(shù)進(jìn)行數(shù)據(jù)壓縮的“標(biāo)準(zhǔn)”圖像。
?
同一時期，在定量比較方面取得了重要進(jìn)展。方差準(zhǔn)則（variance criterion）和率失真標(biāo)準(zhǔn)（rate distortion criterion）被開發(fā)出來并廣泛用于評估圖像數(shù)據(jù)壓縮的性能指標(biāo)。此外，KLT（Karhunen-Loeve transform，K-L變換）一躍成為用作比較目的的最優(yōu)變換。
?
正是在這樣的技術(shù)背景下，Nasir才能開始著手解決DCT問題。
?
Nasir發(fā)現(xiàn)，KLT確實(shí)是基于均方誤差準(zhǔn)則和一階馬爾科夫模型的最佳變換，但是卻缺少有效算法來計算它。于是，如何有效計算 KLT 的最佳近似值成為了他的研究重點(diǎn)。他當(dāng)時想到一種值得研究的方法——切比雪夫插值。1972年，他將這一想法寫成一份提案，提交給了美國國家科學(xué)基金會（NSF），希望獲得該基金會的資助。在提案中，Nasir提出使用切比雪夫多項(xiàng)式來研究“余弦變換”——也就是后來大名鼎鼎的DCT：
?
?
但令他非常失望的是，NSF 并沒有為該提案提供資金，其中一位審查者給出的原因竟然是“太簡單”。
?
不過Nasir并沒有放棄，他找到了他的博士生T. Natarajan和他的朋友K.R.Rao，1973年的整個夏天，他們都在研究這一問題。最終，他們的研究有了結(jié)果，但這個結(jié)果好得讓Nasir不敢相信。正巧之后Nasir要和Harry Andrews（美國數(shù)學(xué)家）一起出席新奧爾良的一個數(shù)學(xué)會議，所以Nasir決定在會上向他請教。
?
Harry Andrews建議Nasir使用率失真標(biāo)準(zhǔn)來檢查這個“余弦變換”的性能，并發(fā)給他一個計算機(jī)程序幫助他計算結(jié)果。
?
最終，結(jié)果再次表明，DCT變換比其他所有變換都表現(xiàn)得更好，在性能上也與KLT十分接近。隨后Harry Andrews建議Nasir發(fā)表這一成果。Nasir聽從了他的建議，將論文以信件的形式發(fā)給了IEEE Computer Transactions（IEEE的通訊期刊），并在1974年1月獲得發(fā)表。
?
據(jù)Nasir后來回憶，當(dāng)初誰也沒有想到DCT會在未來造成如此大的轟動。
?
DCT的重要性和其被發(fā)現(xiàn)的時間遠(yuǎn)不匹配，以至于Gilbert Strang在一篇1999年的論文中寫道：“離散問題是如此之尋常，而且?guī)缀跏且粋€不可避免的問題，而讓人異常驚訝的一個事實(shí)在于，業(yè)界直到1974年才由Nasir Ahmed等人發(fā)現(xiàn)了DCT?！弊罱灿幸恍┭芯孔C據(jù)表明，雖然DCT由 Ahmed 等人開發(fā)是一個無可置疑的事實(shí)，但馮諾依曼（John von Neumann）在1941年左右也對DCT做了一些開創(chuàng)性的研究，不過馮諾依曼自身可能并未意識到其重要性。
DCT的實(shí)現(xiàn)簡介
DCT有8種形態(tài)，我們通常所說的DCT，其實(shí)指的是DCT-II，其對應(yīng)的反變換是DCT-III。DCT-II、DCT-III的原始定義非常簡單：
?
其中：
X：X 是DCT輸出.
x：x 是DCT輸入.
k：k 是計算結(jié)果的輸出數(shù)據(jù)索引, 從 0 to N?1
N：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ù)被開發(fā)出來，其中最引入注目的大概是LLM DCT(LLM 來自于三位對應(yīng)算法的作者：Loeffler、Ligtenberg和 Moschytz，其論文“Practical Fast 1-D DCT Algorithms with 11 Multiplications”)和AAN DCT(AAN 的名字也來自于三位算法作者: Arai、Agui 和 Nakajima，其對應(yīng)的論文是“A fast DCT-SQ scheme for images”）。
?
LLM DCT的算法流程如下：
?
?
它引入了非常經(jīng)典的蝶形：
?
?
需要注意的是，LLM DCT的算法論文中，蝶形圖的標(biāo)識說明里面還有一個明顯的錯誤在上面，其描述中，O1 均出現(xiàn)兩次，明顯第一個應(yīng)該是O0。
?
AAN DCT的計算流程如下，該算法使用了五個乘法（加上八個用于縮放的后乘法，文章中認(rèn)為這不算，因?yàn)樗鼈兛梢员灰频胶竺娴牧炕仃囍斜黄綌偟?#xff09;。
?
?
以H.264標(biāo)準(zhǔn)為例，它實(shí)際上是把DCT 變換和后續(xù)的量化放在了一起，以減輕DCT變換計算的復(fù)雜度，所以有時候看H.264的DCT變換系數(shù)，你甚至第一眼很難想象它其實(shí)是個DCT的變換；從H.264的時代開始，DCT的變換開始使用整數(shù)變換，避免類似MPEG2年代因不同DCT、IDCT實(shí)現(xiàn)精度帶來的編碼、解碼不完全匹配的問題。
?
DCT的應(yīng)用
DCT的去相關(guān)和能量壓縮特性使其在圖像和視頻壓縮中極具吸引力。Karhunen-Loève變換（KLT）通常被稱為理想變換，具有更好的去重特性，但在計算上是難以解決的。另一方面，DCT很容易編程，這使得它迅速占領(lǐng)了圖像和視頻壓縮領(lǐng)域?，F(xiàn)在常見的圖片、視頻壓縮，如JPEG、H.26X、MPEG等，都用到了DCT。
?
下列表格中是DCT在圖像和視頻壓縮中的應(yīng)用（表格來自：https://en.wikipedia.org/wiki/Discrete_cosine_transform）
圖像
?
圖像壓縮標(biāo)準(zhǔn) | 發(fā)布年份 | 常見應(yīng)用 |
JPEG | 1992 | 應(yīng)用最廣泛的圖像壓縮標(biāo)準(zhǔn)和數(shù)字圖像格式 |
JPEG ? XR | 2009 | 由微軟開發(fā)，同時支持無損和有損壓縮，是XPS的首選圖像格式 |
WebP | 2010 | 由谷歌開發(fā)，支持?jǐn)?shù)字圖像有損壓縮 |
HEIF | 2013 | 基于HEVC的圖像壓縮格式，支持動畫，在壓縮方面，比GIF更高效 |
BPG | 2014 | 基于HEVC壓縮 |
JPEG ? XL | 2020 | 免版稅，支持無損和有損壓縮，光柵圖形文件格式 |
?
視頻
?
視頻編碼標(biāo)準(zhǔn) | 發(fā)布年份 | 常見應(yīng)用 |
H.261 | 1988 | 第一個正式的視頻壓縮標(biāo)準(zhǔn)，常用于過去的視頻會議和視頻電話產(chǎn)品 |
MJPEG | 1992 | QuickTime、視頻編輯、非線性編輯、數(shù)碼相機(jī) |
MPEG-1 | 1993 | CD、互聯(lián)網(wǎng)視頻 |
MPEG-2（H.262） | 1995 | 廣播、數(shù)字電視、HDTV、有線、衛(wèi)星、高速互聯(lián)網(wǎng)、DVD中存儲和處理數(shù)字圖像 |
DV | 1995 | 攝像機(jī)、數(shù)字磁帶 |
H.263 ? (MPEG-4 第二部分) | 1996 | PSTN、H.320和ISDN上的視頻電話會議 |
AVC / ? H.264 / MPEG-4 | 2003 | 最常見的高清視頻錄制/壓縮/分發(fā)格式，應(yīng)用于互聯(lián)網(wǎng)視頻、YouTube、藍(lán)光光盤、高清電視廣播、Web瀏覽器、流媒體電視、移動設(shè)備、消費(fèi)設(shè)備、Netflix、視頻電話、Facetime等 |
Theora | 2004 | 網(wǎng)絡(luò)視頻、Web瀏覽器 |
VC-1 | 2006 | Windows媒體、藍(lán)光光盤 |
Apple ? ProRes | 2007 | 專業(yè)視頻制作 |
WebM ? Video | 2010 | 由谷歌開發(fā)的多媒體開源格式，目的是和HTML5一起使用 |
HEVC / ? H.265 | 2013 | 繼H.264/ ? MPEG-4 AVC?之后的下一代編碼標(biāo)準(zhǔn)，顯著改進(jìn)壓縮能力 |
Daala | 2013 | 由Xiph.Org ? 基金會開發(fā)，目標(biāo)是在性能上超越H.265和VP9 |
H.266/VVC | 2020 | 最新發(fā)布的壓縮標(biāo)準(zhǔn)，主要面向4K和8K視頻服務(wù) |
?
Nasir近況
今年二月份，在熱播美劇《我們的生活》（This is Us）第5季第8集中，穿插了一段“艾哈邁德夫婦的故事”。這段故事取材于現(xiàn)實(shí)，講述的正是Nasir和他的太太Esther之間發(fā)生的事。兩人是新墨西哥大學(xué)的校友，在一次大學(xué)國際學(xué)生聚會中偶然結(jié)識并相戀，然后步入了婚姻殿堂，并且一直相知相守到今天。2018年，Nasir和Esther還出版了一本講述他們生活故事的限量版圖書——Parallel Lives In Curved Space。去年，兩人慶祝了他們的結(jié)婚56周年紀(jì)念日。
?
《我們的生活》劇組工作人員正在和Nasir、Esther視頻對話
?
為什么要在《我們的生活》劇集中穿插這樣一段故事？
?
原來導(dǎo)演是想通過這個故事向DCT技術(shù)的發(fā)明者Nasir Ahmed致敬。如果沒有Nasir，劇中的皮爾森一家不可能在新冠疫情期間通過視頻會話保持聯(lián)系，慰藉彼此。
?
現(xiàn)實(shí)中的我們也是一樣。
參考文獻(xiàn)：
1. Y. Arai, T. Agui, and M. Nakajima, “A fast DCT-SQ scheme for images,” IEICE Transactions, vol. E71, pp. 1095–1097, Nov. 1988. 1, 8, 9, 10, 11
2. C. Loeffler, A. Ligtenberg, and G. S. Moschytz, “A practical fast 1-D DCT algorithms with 11 multiplications,” in International Conference on Acoustics, Speech, and Signal Processing, vol. 2, pp. 988–991, May 1989. 1, 4, 9, 10?
3. N. Ahmed and K. R. Rao, Orthogonal Transforms for Digital Signal Processing. New York,NY: Springer-Verlag, 1975. 1, 10
4. Ahmed, Nasir; Natarajan, T.; Rao, K. R. (January 1974), "Discrete Cosine Transform" (PDF), IEEE Transactions on Computers, C-23 (1): 90–93, doi:10.1109/T-C.1974.223784
5. Ahmed, Nasir (January 1991). "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing. 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
掃描圖中二維碼或點(diǎn)擊閱讀原文
了解大會更多信息
喜歡我們的內(nèi)容就點(diǎn)個“在看”吧！
總結(jié)
以上是生活随笔為你收集整理的DCT如此重要，作者当初竟然不知道？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 李超：WebRTC传输与服务质量
- 下一篇： 音视频技术开发周刊 | 208