在已有的实现图像翘曲变换的方案中，使用图形处理器(Graphic Processing Unit，GPU)内置的数千个内核并行处理数据[6-7]时速度快、实时性好，但数据传输过程复杂，开销大。行缓冲器及其改进方案[8-10]不需使用外存储器时，对于高分辨率的图像，片上压力过大；使用外存储器加行缓冲器时，存储资源较为紧张。考虑到实现复杂程度及高分辨率图像可拓展性，本文将原始图像像素存储在双倍速率同步动态随机存储器(Double Data Rate Synchronous Dynamic Random Access Memory，DDR SDRAM)中。
在图像翘曲变换过程中，通过逐点计算已知目的像素坐标获得原始像素坐标，读取原始像素，但读取顺序是非线性的，即读取不是从左到右逐点、从上到下逐行按顺序进行。由于DDR最高效的访问方式是对连续地址的突发式(burst)读写，非线性读取原始像素会极大增加访问次数、降低访问效率。通常使用高速缓冲存储器(Cache)解决以上问题，通用图像Cache[11]功能结构复杂，实现难度大。专门用于图像翘曲变换的Cache[12]效果较好，但更适用于预先确定像素访问顺序而不是逐点计算目的像素坐标，且Cache存储资源使用量较大。
为实现HUD系统中的图像翘曲变换，并解决非线性读取原始像素造成的存储器访问效率下降问题，本文设计实现了一种高效率Cache，研究创新性体现在以下3个方面。①考虑到在小规模应用场景下的灵活配置优势，将原始图像像素存储在分布式随机存储器(Random Access Memory，RAM)中[13]。在Cache存储结构确定的情况下，存储不同图像位深度的像素数据会造成存储资源的浪费，本文提出存储空间分离管理技术来节省存储资源。②Cache地址命中判断过程中进行多位地址比较时，逻辑资源使用量大，本文提出地址分级比较技术来节省逻辑资源。③Cache容量不足会影响命中率，容量过大会增加面积和功耗[14-15]，本文提出一种Cache容量动态调整的方法，在保证命中率的前提下减小Cache容量，降低动态功耗及静态功耗。
1 图像翘曲变换模型分析 图像翘曲变换过程包括坐标映射和插值运算2个步骤。贝塞尔曲面具有良好的自由特性，仅通过改变控制点的位置及权重就可以改变曲面的形状。HUD系统采用贝塞尔曲面模拟汽车的前挡风玻璃。原始图像与目的图像像素坐标映射关系为
 | (1) |
式中：P(x, y)为原始图像像素点；Q(u, v)为目的图像像素点；H为两者之间映射关系。在实际应用中，由已知的目的像素坐标求得原始像素坐标：
 | (2) |
(x, y)整数部分为像素坐标，小数部分为像素权重。用于双线性插值的4个像素点坐标为
 |
| 图 1 图像翘曲变换像素坐标映射关系 Fig. 1 Coordinate mapping of pixels in image warping |
| 图选项 |
输入一个目的像素坐标，得到4个原始像素坐标，插值运算模块依次读取位于原始图像两行内的4个像素点。DDR的实际访问效率与突发式读、写数据的个数N有关，每次从DDR中读取一个像素数据时，实际访问效率变为突发式读取访问效率与突发式读取数据个数N的比值。此外，不同的目的像素可能对应相同的原始像素，对于同一原始像素的反复读取会增加DDR访问次数。
2 存储空间分离管理技术 图像位深度代表色彩等级，即一个像素包含的位数信息M(单位：bit)，常见的图像位深度有16、20、24、32 bit等。Cache内的Cache块数为L，给每个Cache块编号0~(L-1)。Cache块深度为一次突发式读取的像素个数N，宽度为图像位深度M，则每个Cache块存储N个M bit的原始像素数据。
分布式RAM基于查找表(Look Up Table，LUT)进行配置，在逻辑密集型应用及小规模应用场景中具有灵活配置优势。而RAM块更适合于大规模应用场景且存储配置较为固定，难以满足Cache块深度配置要求。因此本文采用分布式RAM存储原始像素数据，每个Cache块由M个深度为N的分布式RAM块构成，结构如图 2所示。
 |
| 图 2 Cache块存储结构 Fig. 2 Storage structure of Cache block |
| 图选项 |
在图 2所示的存储结构下，存储图像位深度小于M的图像时，每个Cache块内会有一部分存储单元被浪费。针对常见的图像位深度，本文提出存储空间分离管理技术：
1) Cache块宽度设置为可存储图像的最大位深度M。
2) Cache块深度设置为一次突发式读取的像素个数N。
3) 当图像位深度小于M/2时，一个Cache块内存储两次突发式读取的像素。
4) 当图像位深度处于M/2~3M/4之间时，将每个Cache块内的存储单元按照图像位深度分为两组：被使用存储单元3M/4和空闲存储单元M/4。图 2所示地址线直接连接每个分布式RAM块内部的N个存储单元，地址不需要重新分配，每个Cache块连接一个地址比较器对其余像素地址进行比较。Cache块内每个分布式RAM块上带有一个使能信号，被使用存储单元连接原有的地址比较器，空闲存储单元内分布式RAM块上的使能信号置位后，每3个Cache块的空闲存储单元额外连接一个地址比较器，等同于增加一个Cache块。实际上增加的是比较器以及Cache块编号，数据存取方式不变。对于整个Cache，多连接了
 |
| 图 3 存储空间分离管理技术示意图 Fig. 3 Schematic diagram of storage separation management technology |
| 图选项 |
5) 当图像位深度处于3M/4~M之间时，像素数据正常存储。
3 地址分级比较技术 访问Cache内存储的数据需进行地址命中判断，通常数据的低若干位地址会直接连到Cache内部，用于确定被访问数据处于Cache中的具体位置，其余地址用于命中比较。访问像素时比较的像素地址位数越多，逻辑资源使用量越大。为节省逻辑资源，对像素地址细化分级。
3.1 地址分级 图像分辨率为A(列数)×B(行数)，则像素地址位数为
1) 高位地址
像素地址的高
2) 中位地址
除去高位地址和低位地址，剩余的
3) 低位地址
像素地址的低
3.2 地址命中比较过程 1) 比较行表中的高位地址与图像翘曲变换模块生成的高位地址，生成是否命中的信息。
2) 将命中行信息转换为命中行编码，简化行表到Cache块之间的命中信息传递关系。
3) 比较命中行编码与Cache块原本所属行编码，相等则选通相应Cache块上的中位地址比较器。
4) 比较Cache块对应的中位地址与图像翘曲变换模块生成的中位地址，命中后选通相应的Cache块，根据图像翘曲变换模块生成的低位地址读取像素数据。
5) 任一级未命中都会生成未命中(miss)信息，DDR更新Cache内数据，并将更新信息传回行表，及时更新行表内高位地址。
地址命中判断过程如图 4所示。
 |
| 图 4 Cache地址分级比较过程 Fig. 4 Multi-level comparison process of Cache addresses |
| 图选项 |
3.3 替换算法 为保证Cache命中率，需采用替换算法[16-17]更新Cache内数据。最近最少使用(Least Recently Used，LRU)替换算法根据数据的历史访问记录进行数据替换，Cache中每个Cache块带有一个计数器记录最近被访问的情况，实现方案如下。
对Cache块进行命中排队，每次命中的Cache块直接放到队头，命中Cache块之前的Cache块全部后移一个位置，Cache块都未命中时替换队尾的Cache块。实际设计中不能移动Cache块，所以对Cache块的计数值进行加减操作来等同于排队。Cache块的编号为0~(L-1)，初始计数值与编号相同。对于当前Cache块，计数值变化情况如下：
1) 若当前Cache块之前有Cache块命中，则其计数值保持不变，如图 5(a)所示。
 |
| 图 5 LRU替换算法示意图 Fig. 5 Schematic diagram of LRU replacement algorithm |
| 图选项 |
2) 若当前Cache块命中，则其计数值取最大值为L-1，如图 5(b)所示。
3) 若当前Cache块之后有Cache块命中，则其计数值减1，如图 5(c)所示。
每次访问之后，同步调整每个Cache块的计数值，有未命中情况时将队尾计数值为0的Cache块替换掉。通过比较当前Cache块与命中Cache块的计数值确定两者的前后位置关系。
4 动态调整技术 4.1 Cache容量 Cache容量不足会导致部分像素点的误替换现象，Cache容量过大会增加面积和功耗。像素访问过程中，对命中Cache块未改变之前的计数值进行统计，记录最小命中计数值Lmin。每个Cache块带一个控制自身是否关断的使能信号，将所有计数值小于Lmin的Cache块上的使能信号置位，对时钟信号进行关断。具体做法为：将相应Cache块上的使能信号与Xilinx Virtex 7环境内部BUFGCE上的使能端CE进行连接，控制相应Cache块进行关断，进而动态调整使用Cache的容量。
4.2 行表行数 一定时间内像素访问具有集中性，不会出现相邻访问的像素跨多行的现象。在确定的图像尺寸A(列数)×B(行数)下，存储高位地址的行表行数与Cache块数L及Cache块深度N相对应，最多
5 结果与分析 本文设计的应用于图像翘曲变换的Cache及其改进方案为在专用集成电路(Application Specific Integrated Circuit，ASIC)环境中实现车载HUD系统的预研工作，当前研究内容均基于现场可编程逻辑门阵列(Field Programmable Gata Array，FPGA)开发环境实现，并对像素访问过程进行软件模拟。测试图像的分辨率为1 920×1 080，Cache可存储最大图像位深度为32 bit。未经改进的Cache包含64个Cache块，每块最多存储64个32 bit的像素数据，Cache容量为128 Kbit。此情况下系统使用5 182个可配置逻辑查找表(Configurable Logic Block LUTs, CLB LUTs)，3 743个可配置逻辑寄存器(CLB Registers)和2 048个存储资源(LUTRAM)，Cache的命中率为98.786%。
5.1 Cache的使用对实验结果的影响 不使用Cache时从DDR中读取像素数据。使用Cache后，命中时从Cache中读取，未命中时从DDR中读取。Cache的命中率即为DDR访问次数减少的比例，则使用Cache时DDR访问次数减少了98%以上，数据访问效率得到保证。
5.2 Cache容量动态调整技术对实验结果的影响 本实验测试加入Cache容量动态调整技术确定可对部分Cache块进行关断后，Cache块数为64、32、16，Cache块宽度为32 bit，深度为64时，命中率及功耗对比情况，如表 1所示。Cache块数由64块减少至16块后，Cache容量减少75%，命中率不会明显降低，且动态功耗减少67.578%，静态功耗减少14.060%。
表 1 Cache容量动态调整技术对实验结果的影响 Table 1 Effect of Cache capacity dynamic adjustment technology on experimental results
| Cache块数 | 命中率/% | 动态功耗/W | 静态功耗/W |
| 64 | 98.786 | 20.076 | 3.293 |
| 32 | 98.736 | 11.610 | 2.988 |
| 16 | 98.716 | 6.509 | 2.830 |
| 变化量/% | -0.071 | -67.578 | -14.060 |
表选项
5.3 存储空间分离管理技术对实验结果的影响 本实验测试Cache块数分别为64、32、16，Cache块宽度为32 bit，深度为64，存储图像位深度为16~24 bit的像素数据时，使用存储空间分离管理技术前后资源变化情况，如表 2所示。当Cache块数为32和16时，逻辑资源(CLB LUTs和CLB Registers)增减基本持平，Cache块数为64时，逻辑资源增加较为严重。在不同Cache块数下，存储资源(LUTRAM)可节省25%，此技术在节省存储资源方面更有优势。
表 2 存储空间分离管理技术对资源使用情况的影响 Table 2 Effect of storage separation management technology on resource usage
| 资源 | Cache块数 | 改进前 | 改进后 | 变化量/% |
| CLB LUTs | 64 | 5182 | 6594 | 27.248 |
| 32 | 2628 | 2951 | 12.291 | |
| 16 | 1209 | 1387 | 14.723 | |
| LUTRAM | 64 | 2048 | 1536 | -25.000 |
| 32 | 1024 | 768 | -25.000 | |
| 16 | 512 | 384 | -25.000 | |
| CLB Registers | 64 | 3743 | 3242 | -13.385 |
| 32 | 1855 | 1604 | -13.531 | |
| 16 | 927 | 807 | -12.945 |
表选项
5.4 地址分级比较技术对实验结果的影响 本实验测试Cache块数分别为64、32、16，Cache块宽度为32 bit，深度为64时，使用地址分级比较技术前后资源变化情况，如表 3所示。在不同的Cache块数情况下，可有效节省近10%的逻辑资源(CLB LUTs和CLB Registers)。
表 3 地址分级比较技术对资源使用情况的影响 Table 3 Effect of address multi-level comparison technology on resource usage
| 资源 | Cache块数 | 改进前 | 改进后 | 变化量/% |
| CLB LUTs | 64 | 5182 | 5252 | 1.351 |
| 32 | 2628 | 2559 | -2.626 | |
| 16 | 1209 | 1217 | 0.662 | |
| CLB Registers | 64 | 3743 | 3374 | -9.858 |
| 32 | 1855 | 1710 | -7.817 | |
| 16 | 927 | 842 | -9.169 |
表选项
6 结论 在HUD系统中图像翘曲变换部分加入Cache可以有效解决像素数据访问连续性问题，极大地降低DDR访问次数，节省图像访问时间。
1) 通过Cache容量动态调整的手段，在保证Cache命中率的前提下，确定合理且尽可能小的Cache容量，降低功耗。
2) 针对常见的图像位深度，存储空间分离管理技术可有效节省25%存储资源，Cache块数较少的情况下效果更好。
3) 地址分级比较技术可有效节省近10%逻辑资源。
本文提出的应用于图像翘曲变换的Cache及其改进方案同样适用于图像旋转、缩放等图像处理应用。
参考文献
| [1] | LEE M, KIM H, PAIK J. Correction of barrel distortion in fisheye lens images using image-based estimation of distortion parameters[J]. IEEE Access, 2019, 7: 45723-45733. DOI:10.1109/ACCESS.2019.2908451 |
| [2] | YUAN X, HU C, CHEN J, et al.Correction of capsule endoscope image distortion based on two-dimensional look-up table[C]//Proceeding of the 11th World Congress on Intelligent Control and Automation.Piscataway, NJ: IEEE Press, 2014: 553-557. |
| [3] | SHETE P P, MADHUKAR S D, BOSE S K.A real-time stereo rectification of high definition image stream using GPU[C]//2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI).Piscataway, NJ: IEEE Press, 2014: 158-162. |
| [4] | MENG G, XIANG S, PAN C, et al. Active rectification of curved document images using structured beams[J]. International Journal of Computer Vision, 2017, 122(1): 34-60. |
| [5] | TAN Z, ZHANG S, WANG R. Stable stitching method for stereoscopic panoramic video[J]. CAAI Transactions on Intelligence Technology, 2018, 3(1): 1-7. |
| [6] | LIN C, TSAI Y M, WANG W, et al.GPU-accelerated high-resolution image stitching with better initial guess[C]//2018 IEEE International Conference on Consumer Electronics(ICCE).Piscataway, NJ: IEEE Press, 2018: 1-3. |
| [7] | MELO R, FALCAO G, BARRETO J P. Real-time HD image distortion correction in heterogeneous parallel computing systems using efficient memory access patterns[J]. Journal of Real-Time Image Processing, 2016, 11(1): 83-91. DOI:10.1007/s11554-012-0304-3 |
| [8] | RYOO J R, LEE E S, PARK H K.Real-time implementation of an LUT-based image warping system[C]//IEEE Intelligence and Safty for Robotics 2013.Piscataway, NJ: IEEE Press, 2013: 1-4. |
| [9] | RYOO J R, LEE E S, DOH T Y. An implementation of real-time image warping using FPGA[J]. Journal of Embedded Systems & Applications, 2014, 9(6): 335-344. |
| [10] | LU Y, LUO X, WANG Y, et al.Line buffer reduction for LUT-based real-time image inverse warping[C]//2016 14th IEEE International New Circuits and Systems Conference(NEWCAS).Piscataway, NJ: IEEE Press, 2016: 1-4. |
| [11] | GREISEN P, HEINZLE S, GROSS M, et al. An FPGA-based processing pipeline for high-definition stereo video[J]. EURASIP Journal on Image & Video Processing, 2011, 2011: 18. |
| [12] | JOON C Y, RAE R J. Image Cache for FPGA-based real-time image warping[J]. Journal of the Institute of Electronics and Information Engineers, 2016, 53(6): 91-100. DOI:10.5573/ieie.2016.53.6.091 |
| [13] | HAN X, CHEN S L, WU L, et al.Design and verification of distributed RAM using look-up tables in an SOI-based FPGA[C]//2010 10th IEEE International Conference on Solid-State and Integrated Circuit Technology.Piscataway, NJ: IEEE Press, 2010: 306-308. |
| [14] | PENG M, LIU X.Adaptive rapid reconfigurable algorithm for low power Cache[C]//International Conference on Computational & Information Sciences.Piscataway, NJ: IEEE Press, 2013: 203-206. |
| [15] | UPADHYAY B R, SUDARSHAN T S B.Low power predictive placement Cache scheme for embedded system[C]//2014 International Conference on Embedded Systems(ICES).Piscataway, NJ: IEEE Press, 2014: 250-254. |
| [16] | KUMAR S, SINGH P K.An overview of modern Cache memory and performance analysis of replacement policies[C]//2016 IEEE International Conference on Engineering and Technology(ICETECH).Piscataway, NJ: IEEE Press, 2016: 210-214. |
| [17] | 杜建海, 吕江花, 高世伟, 等. 面向航天器综合测试系统的Web缓存替换策略[J]. 北京航空航天大学学报, 2018, 44(8): 1609-1619. DU J H, LYU J H, GAO S W, et al. A Web Cache replacement strategy for spacecraft comprehensive testing system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(8): 1609-1619. (in Chinese) |
