一種自適應深度壓縮算法設計與實現

鄭新建，龍 強，張 駿

(1.航空工業西安航空計算技術研究所，陜西 西安710068; 2.集成電路與微系統設計航空科技重點實驗室，陜西 西安710068)

0 引言

3D圖形繪制時使用深度表示物體的相對位置關系，圖形繪制過程中深度數據會被頻繁地從深度緩沖區讀出進行深度測試，然后更新進行寫回，占用了極大的存儲帶寬。嵌入式圖形處理器大多采用基于Tile的延時渲染，該方法可以減少深度緩存的讀寫[1]。文獻[2-4]都指出桌面圖形處理器設計中一般采用立即渲染模式，同時采用深度Cache和深度壓縮的方法來減少存儲器的帶寬需求，加快圖形繪制。圖形的深度值需要在繪制過程中多次讀寫測試，所以深度壓縮必須采用無損壓縮，常見的深度壓縮算法有：深度偏移DO算法[5]、錨編碼Anchor算法[6]、差分脈沖編碼調制DDPCM算法[7]和二維DDPCM算法及其改進[8]等，這些壓縮算法的原理都是基于“深度數據值是通過線性插值得到，相鄰的像素之間的深度值分布范圍較窄”的特點進行壓縮的[9-10]。本文首先分析了圖形處理器中最常用的DDPCM壓縮算法和二維DDPCM壓縮算法，結合DO偏移算法提出了一種自適應的壓縮算法，最后對該算法的實現進行了評估。

1 國內外相關研究

1.1 DDPCM深度壓縮算法

DDPCM算法是DeRoo等提出的針對8×8的Tile深度進行壓縮的算法[11]，ATI的Radeon系列GPU中使用了類似的編碼[12]。該算法基于這樣一個假設：深度值是通過線性插值得到的，如果一個Tile被一個三角形覆蓋，那么Tile內的所有點都在同一個平面上，所以可以存儲這個平面以及每個點到平面的距離來表示整個tile的深度。

DDPCM算法編碼時將8×8的tile塊左上角值作為參考值存儲，然后通過二階差值定義平面并表示tile中其余點的值，編碼步驟如下：

① 計算列方向的差值，存儲第1行的值為參考值，第2行的值為一階差值，其余行的值為二階差值；

② 處理第1行和第2行，計算行方向的差值，存儲第1列的值為參考值，第2列的值為一階差值，其余列的值為二階差值；

③ 處理后結果只有最左上角值為原始參考值，第2行第1列，第1行第2列為一階差值，其余都為二階差值，如圖1示。存儲時參考值z，一階差值dx，dy用全精度存儲，其余二階差值用2 bit存儲其可能的差值{-1，0，+1}。

深度緩沖區采用32 bit格式存儲時，壓縮后參考點及一階差值采用32 bit表示，二階差值采用2 bit表示。按照8×8的Tile進行壓縮，原始數據8×8×32 bit=2 048 bit，DDPCM的壓縮后數據：32+32+32+61×2=218 bit，由于外部DDR存儲器帶寬一般是2的整數冪，設計上采用128 bit總線傳輸，所以DDPCM的壓縮后數據占用的實際帶寬需求為256 bit，實際的DDPCM壓縮率為8∶1。

圖1 DDPCM編碼

如果一個Tile的數據被一個三角形覆蓋，那么所有像素點應該位于一個平面內，其深度值必然是連續的，此時DDPCM的可壓縮率會很高。但如果一個Tile的數據處于2個三角形內，由于這2個三角形的深度值差別較大，DDPCM編碼往往會失敗。DeRoo等[5]又針對2個三角形覆蓋的Tile數據提出了二維DDPCM的算法。

1.2 二維DDPCM深度壓縮算法

二維DDPCM用于處理當圖形中的一個Tile并不是被一個三角形覆蓋，而是被2個三角形覆蓋時的壓縮方式。此時應該在Tile中有一條分界線，在分界線的一邊被一個三角形覆蓋，可以使用DDPCM編碼。分界線另外一邊為另一個三角形覆蓋，也可以使用DDPCM編碼。二維DDPCM原理如圖2所示。

圖2 二維DDPCM編碼

二維DDPCM以左上和左下2個頂點對Tile進行DDPCM掃描編碼。首先使用左上角作為參考點進行DDPCM掃描，然后使用左下角作為參考點進行DDPCM掃描，每個象素點用2個bit表示{-1，0，+1}，在Tile內部每一列定義一個斷點(BreakPoint)，該斷點以上的像素深度值使用左上角為參考的DDPCM編碼，該斷點以下的像素深度值使用左下角為參考的DDPCM編碼。采用8×8的Tile塊進行壓縮編碼時，每個斷點需要4 bit表示，一共需要8個斷點。所以總的二維DDPCM壓縮率可計算如下：

2個參考點和4個一階差值采用32 bit表示：6×32 bit=192 bits，其余58個二階差值采用2 bit表示：58×2 bit=174 bits，每個斷點存儲4 bit表示：8×4 bit=32 bit。一個8×8的Tile深度塊壓縮后存儲為340 bits，由于DDR總線位寬為128 bit，所以壓縮后存儲帶寬占用實際為384 bits，壓縮率為：5.3∶1。

1.3 DO編碼算法

DO編碼算法假設在一個Tile中的深度值通常位于某1個或幾個參考值附近的區域，DO壓縮算法通常選擇Zmin和Zmax作為存儲的參考值，認為Tile中的深度值大多介于大于Zmin或者小于Zmax的較窄區間內。DO壓縮算法可表示的范圍應該是距離Zmin和Zmax較近的點。DO算法的壓縮率計算如下：

保存2個參考值Zmin和Zmax：32+32=64 bits，使用7 bit保存所有點到Zmin或Zmax的距離，總共需要：64×7=448 bits，所以一個8×8的Tile深度塊壓縮后存儲為512 bit，壓縮比為4∶1。可表示的范圍是{Zmin，Zmin+27-1}，以及{Zmax-27-1，Zmax}。

2 一種高效的自適應深度壓縮算法

2.1 自適應DDPCM

二維DDPCM編碼只能針對部分處于2個三角形內部的Tile，該編碼過程可以進一步擴展以適應任意的2個三角形覆蓋區域的深度緩沖區壓縮。從一個Tile的4個頂點分別進行編碼，當一個頂點編碼成功則采用一維DDPCM編碼，如果第1個頂點編碼失敗則在Tile的剩余數據中繼續進行第2個頂點進行編碼，第2個頂點編碼成功則采用二維DDPCM編碼。如果第2個頂點編碼失敗，丟棄第2個頂點的編碼值，并以第3個頂點為二維DDPCM的第二個參考頂點進行編碼，遍歷4個頂點編碼，能夠提高深度數據的可壓縮率。自適應DDPCM編碼適用的三角形覆蓋如圖3所示。

圖3 自適應DDPCM

從頂點A開始DDPCM編碼，編碼成功則該Tile保存為一維DDPCM的格式，壓縮比存儲為8∶1，同時設置該Tile的壓縮標記為2'b01表示當前Tile使用了一維DDPCM壓縮算法進行壓縮。如果A頂點開始的DDPCM壓縮失敗，則保存Tile中已壓縮的像素深度，同時對剩余的未編碼像素啟動以B頂點開始的DDPCM壓縮算法，如果剩余的像素使用頂點B壓縮成功則按照二維DDPCM壓縮格式存儲，壓縮標記為2'b10，壓縮比為5.3∶1；如果失敗則丟棄以頂點B進行的DDPCM編碼值，同時啟動以C頂點開始的DDPCM壓縮算法，如果剩余的像素使用頂點C壓縮成功則按照二維DDPCM壓縮格式存儲，壓縮標記為2'b10，壓縮比為5.3∶1；如果失敗則丟棄以頂點C進行的DDPCM編碼值，同時啟動以D頂點開始的DDPCM壓縮算法，如果剩余的像素使用頂點D壓縮成功則按照二維DDPCM壓縮格式存儲，壓縮標記為2'b10，壓縮比為5.3∶1。如果4個頂點遍歷后仍然壓縮失敗，則當前Tile壓縮失敗，存儲為原始格式，并設計標記2'b00。

也就是說自適應DDPCM編碼算法壓縮時如果一維DDPCM壓縮成功則存儲為高壓縮比的一維DDPCM格式，否則在一維DDPCM算法失敗后再選擇其他頂點對剩余的像素進行二維DDPCM壓縮，如果二維DDPCM能夠成功則壓縮為較低壓縮比的二維DDPCM格式，如果其余幾個頂點進行二維DDPCM都失敗，壓縮才失敗，存儲為原始格式。

這種自適應的DDPCM算法的壓縮率高于DDPCM和二維DDPCM，由于采用4個頂點依次進行DDPCM編碼，其硬件實現資源上等效于DDPCM，壓縮性能針對不同的深度場景，在同樣壓縮率的前提下能提供不低于DDPCM或二維DDPCM的性能。

由于自適應DDPCM算法第2個參考頂點不固定，且4個頂點的編碼過程是獨立的，所以需要額外存儲當前Tile的第2個參考頂點標記，設計上不再采用斷點的方式，而是每個壓縮深度值直接增加1 bit表示其使用了第1個參考頂點編碼還是第2個參考頂點編碼。自適應DDPCM算法如果采用一維壓縮成功，則存儲為一維DDPCM的標準格式，壓縮比為8∶1，如果存儲為二維DDPCM壓縮格式，壓縮率計算如下：

2個參考點及4個一階差值點存儲為32 bit：(32 bit+32 bit+32 bit)×2 = 192 bits，其余58個二階差值點存儲為2 bit的差值和1 bit的頂點選擇(表示使用第1個參考點還是第2個參考點)：58×3 bit = 174，另外還需要保存第2個參考點選擇：2 bit(第1個參考點默認選擇A點，第2個參考點可能選擇B/C/D)，一個8X8的深度Tile壓縮后的數據量為：368 bits，由于外部DDR存儲器帶寬一般是2的整數冪，設計上采用128 bit總線傳輸，所以DDPCM的壓縮后數據占用的實際帶寬需求為384 bit，壓縮比為5.3∶1。實際的自適應DDPCM壓縮率為介于5.3∶1到8∶1之間。

2.2 自適應DDPCM與DO編碼算法

在繪制低分辨率圖形時，DO算法能夠得到較高的可壓縮率，實現簡單，速度快。而且DO算法的實現與DDPCM等平面編碼從原理上不同，混合使用2種編碼方式能夠進一步提高深度數據的可壓縮率。設計中采用DO算法作為自適應DDPCM壓縮算法的補充，深度數據同時使用DO和自適應DDPCM算法進行壓縮，如果自適應DDPCM一維壓縮成功，則存儲為DDPCM 8∶1壓縮格式，設計標記2'b01，否則如果自適應DDPCM二維壓縮成功則存儲為DDPCM 5.3∶1的壓縮格式，設計標記2'b10，否則如果DO壓縮成功則輸出DO格式4∶1的壓縮編碼，并設計標記2'b11，3種壓縮都失敗則存儲為原始格式，并標記為2'b00。

自適應深度壓縮實現流程如圖4所示。

圖4 自適應深度壓縮流程

2.3 自適應壓縮前后深度數據映射關系

由于深度數據采用的是無損壓縮，某個Tile的數據可能壓縮成功，也可能壓縮失敗，每個Tile壓縮后所需的存儲容量不同，所以進行壓縮后數據存儲時，每個Tile必須按照最大的未壓縮Tile的存儲空間進行存儲，也就是說深度壓縮算法只能降低存儲帶寬需求，不會減少存儲容量需求[13]。當采用DO壓縮算法壓縮成功時，數據帶寬需求減少為原始格式的1/4，當采用自適應DDPCM壓縮成功時，數據存儲帶寬減少為原來的1/5.3或1/8。壓縮后的DDR數據存儲的格式如圖5所示，其中Tile1采用了DDPCM一維壓縮，壓縮比為8∶1，壓縮標志2'b01；Tile2壓縮失敗采用原始格式存儲，壓縮標志2'b00；Tile3采用了DDPCM的自適應壓縮壓縮比為5.3∶1，壓縮標志2'b10；Tile4采用了DO壓縮格式存儲，壓縮比為4∶1，壓縮標志2'b11；Tile5壓縮失敗采用原始格式存儲，壓縮標志2'b00。

圖5 壓縮前后深度數據映射關系

壓縮標志存儲在片上SRAM實現的TileTable中。當片斷操作讀取該Tile的數據時根據TileTable中的標志按不同的解壓縮算法對Tile進行解壓縮。當片斷操作進行深度數據寫操作時，根據壓縮結果更新TileTable中的相應標志。

3 試驗結果分析

采用Verilog HDL對自適應深度壓縮算法進行描述，下載到Xilinx Vertex6系列開發板上進行綜合，工作頻率可以達到220 MHz，在SMIC 65 nm CMOS工藝下，采用Synopsys Design-Compiler對設計進行綜合，電路工作頻率達到370 MHz，可以滿足設計需求。

對不同的深度壓縮算法進行試驗，選取典型的試驗繪制場景圖如6所示。

圖6 深度壓縮算法選取繪制場景

對于壓縮應考慮2個指標：可壓縮率ρ和壓縮比t。可壓縮率ρ是指某場景下所有Tile中有多少Tile可以被某種壓縮算法壓縮，壓縮比t則是每種壓縮算法固定的壓縮效率[14-15]。

幾種壓縮算法的壓縮比t、可壓縮率ρ及壓縮效率的比較如表1所示。其中本文的自適應算法自動選擇DDPCM不同壓縮率算法或DO算法，其壓縮比t介于4∶1到8∶1之間。

表1中本文算法自適應選擇DDPCM或二維DDPCM或DO算法進行壓縮，可壓縮率ρ中包含了一維DDPCM的可壓縮率ρ1，二維DDPCM的可壓縮率ρ2，DO的可壓縮率ρ3，如場景(a)的最終可壓縮率51.2%，其中有43.3%采用了DDPCM 8∶1模式壓縮，3.8%采用了DDPCM 5.3∶1模式壓縮，剩余4.1%采用了DO壓縮算法壓縮，所以總的壓縮效率計算為：

表1 幾種壓縮算法壓縮效率比較

場景本文算法DDPCM2D-DDPCMDOtρ/%效率tρ/%效率tρ/%效率tρ/%效率(a)843．31．615．346．21．60443．31．48-51．21．79(b)833．71．425．335．81．41433．71．34-40．31．53(c)830．71．385．332．81．42430．71．30-35．51．44

4 結束語

嵌入式圖形處理器的存儲帶寬問題是現代GPU設計的瓶頸，設計中針對紋理圖像、像素數據、深度數據等采用不同的壓縮算法[16-17]，并結合相應的Cache系統以提高存儲帶寬[18-19]。本文設計的自適應深度壓縮算法結合了DDPCM和二維DDPCM及深度偏移壓縮算法的優點，自適應DDPCM深度壓縮算法能夠有更好的場景適應性，可以獲得比DDPCM更高的壓縮效率，在保證了處于一個三角形區域的Tile數據的高壓縮率基礎上，能夠提供比二維DDPCM提供更高的壓縮比。自適應DDPCM壓縮算法與DO壓縮算法互為補充，進一步提高了深度數據的壓縮效率，能夠很好地應用于嵌入式圖形處理器設計中。

[1] 王佳.Tlie-based嵌入式圖形處理器的研究與設計[D].濟南：山東大學，2014：3-4.

[2] MOREIN S，WRIGHT M，YEE K.Method and Apparatus for Controlling Compressed Z Information in a Video Graphics System[P].US Patent：6636226，2003.

[3] 蔣毅飛，張戈.場景前顏色緩沖區壓縮[J].計算機輔助設計與圖形學學報，2010，22(9)：1502-1507.

[4] 王平.LZW無損壓縮算法的實現與研究[J].計算機工程，2002，28(7)：98-99.

[5] DEROO J，MOREIN S，FAVELA B，et al.Method and Apparatus for Compressing Parameter Values for Pixels in a Display Frame[P].US Patent：6476811，2002.

[6] HASSELGREN J.Efficient Depth Buffer Compression[C]∥ACM Siggraph/eurographics Symposium on Graphics Hardware.ACM，2006：103-110.

[7] JUNG T R，VAN L D，SHEU T Y，et al.Design of Multi-mode Depth Buffer Compression for 3D Graphics System[C]∥ IEEE International Conference on Multimedia and Expo.IEEE，Hannover，Germany，2008 ：789-792.

[8] LOK K H，LU Y C，CHIEN S Y.Low Latency Universal Buffer Compression and Decompression for Mobile Graphics Applications[C]∥IEEE International Conference on Multimedia and Expo.IEEE，2010：814-819.

[9] MOREIN S，NATALE M.System，Method，and Apparatus for Com-pression of Video Data using Offset Values[P].US Patent：6762758，2004.

[10] DYKE J V，MARGESON J.Method and Apparatus for Managingand Accessing Depth Data in a Computer Graphics System[P].US Patent：6961057，2005.

[11] PARK W C，YOON D K，KIM D S，et al.The Design of Compressed Memory System for Depth Data in 3D Rendering Processors[J].Ieice Electron Express，2010，7(21)：1622-1628.

[12] MOREIN S.Technology[M].Hot3d-Graphics Hardware Workshop.ACM.Siggraph，2000.

[13] CHEN C H，LEE C Y.Two-level Hierarchical Z-buffer with Compression Technique for 3D Graphics Hardware[J].Visual Computer，2003，19(7-8)：467-479.

[14] IOURCHA K I，NAYAK K S，HONG Z.System and Method for Fixed-rate Block-based Image Compression with Inferred Pixel Values[P].US Patent：5956431，1999.

[15] HONG Z，IOURCHA K I，NAYAK K S.Fixed-rate Block-based Image Compression with Inferred Pixel Values[P].US Patent：6683978，2004.

[16] NYSTAD J，LASSEN A，POMIANOWSKI A，et al.Adaptive Scalable Texture Compression[C]∥The Eurographics Association，2012：105-114.

[17] SREEDEVI P，HWANG W L，LEI S.An Examplar-Based Approach for Texture Compaction Synthesis and Retrieval[J].IEEE Transactions on Image Processing，2010，19(5)：1307-1318.

[18] 蔣毅飛.嵌入式圖形系統的訪存帶寬優化[D].北京：中國科學院大學，2011：32-37.

[19] 孟超，嚴冰，林殷茵.一種交錯并行隱式刷新增益單元eDRAM設計[J].半導體技術，2011，36(6)：466-469.