一种自适应深度压缩算法设计与实现

郑新建，龙 强，张 骏

(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.