基于LUT实时图像矫正的行缓存优化

卢宇峰，罗小华，俞　淼，李益航

(浙江大学 超大规模集成电路研究所，杭州 310027)



基于LUT实时图像矫正的行缓存优化

卢宇峰，罗小华，俞淼，李益航

(浙江大学 超大规模集成电路研究所，杭州 310027)

基于反向映射的图像矫正被广泛应用于解决光学镜头透视引起的非线性畸变失真问题，该方法将映射坐标固化在LUT内，避免了复杂的坐标计算，但需要大量行缓存储备图像数据用以执行反向映射.为了减少行缓存的使用，本文提出了一种基于读扩展的环形行缓存读写算法，利用行同步信号的消隐间隔扩展读周期，使读写指针循序错开，保证上下映射的空间.相比传统的以最大偏移作为行缓存的结构，改进的专用控制算法可以减少近一半的内存使用.本文中的实时图像矫正系统已经在FPGA上实现，实验结果表明所提出的读扩展行缓存算法显著地改善了内存的消耗，并且获得良好的实时图像矫正效果.

LUT； FPGA； 图像反向映射； 行缓存； 实时； 图像矫正； 畸变失真

在遥感、医学图像、计算机视觉、多摄像头视频和全景图像等众多应用领域中，借助图像映射来矫正由光学镜头或者某一特殊视点导致的非线性畸变失真是一项重要的研究课题.图像映射也通常被用来实现特殊的图像处理应用如图像缩放、旋转、平移和拼接等[1].图像映射是依据某种几何关系将带有失真的图像投射到一个正确平面上的一种转变过程，其中反向映射因便于插值而被广泛采用于硬件实现.而在基于反向映射的图像矫正模块中需要各像素点相应的正确坐标值，这些坐标值可以在线计算获得或者被事先储存在LUT内.在求取映射坐标时涉及繁琐的坐标变换和浮点数的多阶矩阵乘法，因而往往不会采用FPGA去实现这些复杂的运算逻辑.Vancea[2]选择在Xilinx的FPGA中调用软核MicroBlaze来设计软件，进行在线计算映射坐标值.借助坐标LUT的方法可省去复杂的运算，因而不仅显著提高处理速度并节省大量FPGA中的DSP资源，此外在FPGA系统内也易于控制和实现.

图像矫正系统中的内存消耗主要来自坐标LUT和行缓存，而在FPGA的硬件平台上内存的消耗往往不能被低估.Akin[3]提出了一种算法来压缩用于存取反向映射坐标LUT的大小，并且使用较低复杂度的解压缩处理得到每一个正确的坐标值，本文也采用类似的LUT压缩机制使其内存消耗仅为1/256.在执行反向映射时，用来储备图像数据的行缓存因为视频流的实时性而难以被压缩.因此在众多设计中，片外的内存(如SDRAM、SRAM等)被广泛使用作为输入图像的缓存[2，4-5].Motten[6]则考虑反向映射坐标的各种潜在模式而提出了一种适应性的内存分配架构来减少行缓存的消耗.Ryoo[7]采用图像传感器输出的bayer格式图片进行色彩重构再作图像矫正，其从图像采集源头来减少图像大小从而降低后级的内存负荷.

本文提出了一种基于读扩展的环形行缓存读写算法，相比传统的以最大偏移作为行缓存的结构，此种改进的专用控制算法可以减少近半的内存消耗.该算法不同于Motten的方法，不需要针对特殊的潜在模型进行优化，是一种较为通用的算法，适用于绝大多数的镜头畸变矫正.流水线架构的二线性插值结构[8]也被应用到图像矫正系统中，以获得子像素的精度.采用的结构和算法都已在单片FPGA中实现，实验结果表明所提出的读扩展行缓算法显著地改善了内存的消耗，并获得良好的实时图像矫正效果.

1　基于LUT的图像矫正

1.1反向映射矫正图像

对于镜头的非线性失真导致的图像变形，扭曲不存在同一的规律，由相机固有特性得到的通用齐次矩阵并不能去除这些非线性失真.而图像映射是被广泛应用于矫正镜头的非线性畸变失真的有效方法.图像映射是一种图像的几何空间变化，定义了输入和输出图像之间的对应关系.图像空间变换的计算方法通常可以归为两类： 利用正向映射的方法和利用反向映射的方法，如表达式(1)所示：

Forwardmapping： (u，v)=[Fu(x，y)，Fv(x，y)]；

Inversemapping： (x，y)=[Fx(u，v)，Fy(u，v)]；

(1)

u，v是输出图像坐标，而x，y是源图像坐标.基于正向映射的方法按顺序扫描每个输入像素，然后在由Fu，Fv函数得到输出图像的位置赋予像素值.正向映射过程存在一个问题，即可能存在两个及以上的输入点对应同一个像素点，这可能导致有些输出像素没有被赋值.反向映射则是按照像素格点顺序扫描每个输出像素，根据Fx，Fy函数所计算出输入图像上的对应关系，并存储在LUT内如图1所示，再由相应的坐标找到源图像正确的位置.同时，输出的像素值依据周围的像素值进行重采样来获得子像素精度.如此反向映射就不存在空点像素的问题，同时也易于插值算法实现.本文便采用反向映射的方法来进行图像的非线性失真矫正.

1.2反向映射的坐标LUT

在FPGA应用中，广泛采用LUT进行硬件加速.某些固定的常数如参数、坐标值等会被固化在LUT内，这不仅可以获得较高的精度还不需要消耗大量的DSP和逻辑资源去进行复杂的在线计算.因此本文的图像矫正系统便将反向映射对应的坐标存于LUT内.

由镜头导致的畸变通常有两部分： 径向畸变和切向畸变.而主要的失真来自径向畸变，因此在许多应用场景下切向畸变可以被忽略.通过相机标定，图像的畸变参数(包括径向和切向畸变)被记录在5×1的向量kc中.若设r2=x2+y2，包含镜头畸变的标准化坐标点Xd定义如下：

(2)

因此像素坐标向量与标准化的坐标点向量存在以下的等式(3)的关系：

(3)

相机的内在参数可表示为一个3×3的矩阵称为相机矩阵KK.根据以上的公式，输出的像素坐标(xp，yp)就被存到LUT内用以反向映射如图1.一套相机以及镜头系统对应一个唯一的LUT.而LUT内每个单元又分成两个部分，x坐标部分和y坐标部分，其中x坐标与y坐标都包含整数和小数部分.整数部分被用作定位到相应的源图像点上，而小数部分则被用作重采样所需像素的权值.

2　行缓存读写算法

行缓存是图像畸变矫正系统中的重要组成部分，但是需占用大量的内存来缓存多行图像数据以执行实时的图像反向映射，因此采取一种适当的、改进的行缓存算法是非常有必要的.若能节省行缓存的内存使用，便可在单片FPGA内矫正多个摄像头并拼接成一个全景图像而不需要片外内存的支持.

为矫正镜头的畸变失真，在执行图像的反向映射操作后，输出图像会丢失源图像四周的部分像素区，其最终的实际有效部分便如图2(a)黑色桶型区域部分.由畸变失真的特性可知，在图像的上半部分需要之后的行缓存来定位到对应的像素点，称为下映射；而相反在图像的下半部分时则需要之前的行缓存来定位寻点，称为上映射.

整个行缓存的大小主要是由反向映射的垂直坐标决定，图像的畸变失真越明显所需要的行缓存则越大.图像数据流持续无间断地进入暂存块，因此图像的水平像素数决定了行缓存每一行的尺寸.若以目标像素的当前行作为参考，向下映射为正，向上映射为负，可得到如图2(b)所示的每一像素行对应的映射范围图，数据来自一枚640×480分辨率的图像传感器和一枚焦距2.1mm的广角镜头.

2.1传统环形行缓存

环形行缓存定义了一片内存，并在整帧图像中重复使用，在传统的图像矫正系统中被广泛使用作为映射像素的缓存.映射后像素和源像素间的坐标差值称为反向映射的坐标，反向映射垂直坐标的最大值决定了环形行缓存的大小.图2(b)展示了最大下映射的垂直坐标偏移是ΔL1行，最大上映射的垂直坐标偏移是ΔL2行.

Linebufferusage： ΔL=ΔL1+ΔL2.

(4)

ΔL行(等式(4))是整个图像所需的最大行偏移，因此至少需要ΔL行的内存空间来执行反向映射.基于上述这种缓存架构，环形缓存被分为两个部分如图3所示.上半部分内存空间提供给负性的反向映射坐标的点进行寻址定位到正确的源图像的位置，而下半部分内存空间则是为正性的反向映射坐标点进行寻址定位.

传统行缓存结构的读写算法在初始化时读写指针会停留在环形内存的基地址处.基地址的位置由下映射和上映射的最大范围决定，图3的ΔL2行处则被定为环形行缓存的基地址.当写控制信号有效时，持续流入的图像值被存入行缓存内，直到写指针移动到行缓存的末尾，然后跳转到缓存的起始位置.这是环形行缓存的特性，有效地利用内存.而读控制信号会落后写信号ΔL1行激活，这是为第一次图像反向映射作准备.如果读控制信号有效得过早会导致映射得到空像素或者未更新的像素值，从而产生错误的映射.在整个图形反向映射执行过程中，读写指针被同一时钟所驱动，保持相等的位移ΔL1行进行跳转.值得注意的是，本文提到的读指针并非真正的内存的读地址，而是读基地址.因此实际输出像素的地址=读指针+反向映射的坐标.

2.2读扩展环形行缓存

在传统环形缓存中，将上映射和下映射的最大垂直偏移之和作为整体环形缓存的大小.假设上映射所需的前行缓存区或者下映射的后行缓存区可被作为全部环形缓存所需的内存，也就意味着上映射和下映射使用同一片内存空间.基于这种构想下，等式(5)中的ΔL行将被作为行缓存，相比传统的环形缓存，在反向映射过程中此种方案将减少近一半的内存使用.但是在执行反向映射时需提供正确的像素值而不被新流入的像素点所覆盖，需要有一种机制能够保证读写指针的这种动态跳转，如图4所示，而非传统环形行缓存那样保持读写指针相同的位移差.

Linebufferusage： ΔL=max[ΔL1，ΔL2].

(5)

图像传感器的视频流时序中有行同步信号(HSYNC)和场同步信号(VSYNC)，如图5所示.VSYNC高电平信号被作为一帧图像开始的标志信号，HSYNC则定义了像素输入的有效行区间信号.在视频流信号中的每个行周期HSYNC信号内有一段非显示区间称之为行消隐间隔.鉴于此种特性，本文提出了一种改进的环形缓存读写算法，即读扩展环形缓存，这是一种控制读写指针线性动态变化的算法.每当环形缓存填充了一行像素后，在HSYNC周期内的行消隐区内会多读ΔP个像素点，如图5所示.

随着大量的图像数据地不断流入，读写指针间的位移也变得越来越大.则往上可寻址的空间会变得越来越大，而往下可寻址的空间会变得越来越小，这也符合镜头失真的特性，因此该算法是一种通用的图像矫正的行缓存解决方案.其中要为读扩展像素数ΔP取一个合理值，如公式(6)所示：

(6)

ΔL是ΔL1和ΔL2间的最大值如式(4)所示，Hp是水平方向上的像素数，而Vp是垂直方向的像素数，这两个值由图像的分辨率所决定.Δt则指的是一个浮动像素数，若Δt过大将导致在新的帧刷新信号来之前还未完成所有像素点的反向映射.ΔP可取区间内的任意整数值，利用读扩展环形行缓存算法完成图像矫正.

图6读扩展环形行缓存的读写算法描述

Fig.6The write and read algorithm description for a circular buffer with reading extended

图6描述了带读扩展行缓存读写算法的主要步骤，在反向映射的初始阶段，读写指针处在内存的起始位置.与传统环形行缓存算法相似的是，读控制信号在初始化时也会滞后写控制信号若干行(ΔL行).但是不同于写有效信号(HSYNC信号)，读有效信号在每个行周期内会扩展ΔP个像素周期.VSYNC中的低电平信号是场消隐信号，场消隐信号又包括场同步时间，场消隐前肩时间和场消隐后肩时间.在HSYNC进入同步脉冲的显示后沿(即场消隐后肩)时，读控制信号会持续保持有效(ΔPe段信号，如图5所示)，直到所有像素都完成反向映射.这是由初始阶段，Read_valid信号的ΔL行延迟以及Δt的取值所导致的.

该算法使得读写指针保持一种线性的动态变化，保证向上映射和向下映射都有充足的空间，而不被新进入的图像数据所覆盖或映射到未更新的像素点.同时保证反向映射在新一帧的图像来之前完成所有像素的映射.读扩展环形行缓存在内存的消耗上有较大优势，而且没有带来复杂的控制逻辑，易于实现.

2.3图像矫正系统实现

图7展示了一个完整的图像矫正系统的架构，主要由LUT模块，行缓存读写控制模块，行缓存以及RGB插值模块四部分构成.行缓存控制模块接收到来自摄像头的图像数据，并放置在行缓存内.同时从LUT中获取对应的反向映射的坐标.其中整数部分，x_diff和y_diff，用来指定行缓存中用以反向映射的窗处理的四角.而小数部分，x_fraction和y_fraction，用来进行二线性插值算法以完成像素的重采样，从而获得子像素精度，避免像素间对齐上的错误.行缓存控制模块在整个系统中占据绝对重要地位，它根据之前描述的带读扩展行缓存算法，不断得到读写地址，指引着整个反向映射的执行.该算法在图像矫正系统的应用，旨在减少内存的消耗，这为矫正系统以及其他所需的硬件应用在单片FPGA内得以实现.

3　实验结果分析

本文提到的图像矫正架构和读扩展行缓存算法均已在Terasic DE1-SoC平台内实现，其基于Alter Cycle V的FPGA，拥有32075的逻辑资源和3970Kb的内存块.实验采用了一枚焦距2.1mm的广角镜头，有较大的畸变失真，经相机标定计算，反向映射中有最大50行的下映射范围和最大30行的上映射范围.图像来自于一块640×480分辨率的图像传感器，24M的像素时钟，30帧的刷新频率.

表1　资源消耗

表1记录了之前描述的每种行缓存算法的资源消耗，综合结果来自Quartus Ⅱ 13.1工具套件.帧缓存作为输入图像的暂存器实现起来最为简便，不用考虑畸变失真的大小，不用计算所需的最大偏移行数，这也导致其会占用最大的内存资源.采用16位RGB 565的编码格式的640×480分辨率的图像，一帧的图像缓存总共需要0.586Mb.FPGA的片上存储资源非常有限，片内的内存往往连一帧的图像缓存都无法承担.本文提出的读扩展环形行缓存算法比传统环形行缓存减少了45%的内存消耗，却只额外消耗了基本可忽略的片内逻辑资源.因为80行所需的行缓存对应FPGA内部的双口RAM，需要16位地址空间的RAM大小；而50行的行缓存则只需15位地址空间的RAM大小，从实际RAM调用结果可知会减少一半.其他存储器资源的消耗来自于存储压缩过的映射坐标LUT[3].基于这种改进的专用行缓存控制算法，超过6个的摄像头可不借助额外的片外存储器，完成同时实时矫正并拼接成一张全景图像.

图8展示了图像矫正前后的变化，很明显图像的畸变失真在(b)图中得以良好的矫正，特别是图像上半部分的桌子边缘处和下半部分的桌面的纹理以及边缘，黑白标定板的边缘(已由红色虚线标注)，由非线性失真导致的明显弯曲(左图)，在右图中已被矫正成物体原本应有的平直形态.同时因为矫正特性会丢失源图像四周边缘部分的图像数据，也在右图中体现了出来.因此实验结果充分表明了读扩展行缓存算法可以节省大量的行缓存消耗，同时在不损失硬件系统性能的情况下获得良好的图像矫正效果.

4　结　论

为了实时矫正光学镜头导致的非线性畸变失真，本文采用基于LUT的图像反向映射方案，并提出了优化内存消耗的读扩展环形行缓存算法.此种专用行缓存读写算法相比传统环形行缓存算法可节省近一半的内存消耗，并能解决通用的镜头失真问题.该矫正系统已在FPGA中实现，实验结果充分表明了此种算法的有效性，并获得良好的矫正效果.利用这个改进的行缓存读写算法，更多基于图像矫正预处理的复杂的应用也得以在单块FPGA内实现，如特殊应用的多摄像头系统(全景视频和虚拟视角合成等).

[1]WOLBERG G. Digital image warping [M]. Los Alamitos： IEEE Computer Society Press， 1990.

[2]VANCEA， C， NEDEVSCHI S. LUT-based image rectification module implemented in FPGA[C]∥2007 IEEE International Conference on Intelligent Computer Communication and Processing. Cluj-Napoca， Romania： IEEE Press， 2007： 147-154.

[3]AKIN A， BAZ I， GAEMPERLE L M， SCHMID A，etal. Compressed look-up-table based real-time rectification hardware[C]∥2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration(VLSI-SoC). Istanbul， Turkey： IEEE Press， 2013： 272-277.

[4]RYOO J R， LEE E S， PARK H K. Real-time implementation of an LUT-based image warping system[C]∥2013 44th International Symposium on Robotics(ISR). Seoul， Korea： IEEE Press， 2013： 1-4.

[5]RODRIGUES J G P， FERREIRA J C. FPGA-based rectification of stereo images[C]∥2010 Conference on Design and Architectures for Signal and Image Processing(DASIP). Edinburgh， United Kingdom： IEEE Press， 2010： 199-206.

[6]MOTTEN A， CLAESEN L， PAN Y. Adaptive memory architecture for real-time image warping[C]∥2012 IEEE 30th International Conference on Computer Design(ICCD). Montreal， Canada： IEEE Press， 2012： 466-471.

[7]RYOO J R， KIM B K， DOH T Y. Computationally efficient colour image warping for real-time video applications [J].ElectronicsLetters， 2015，51(14)： 1067-1069.

[8]GRIBBON， K T， BAILEY D G. A novel approach to real-time bilinear interpolation[C]∥2004 IEEE International Conference on Field-Programmable Technology. Brisbane， Australia： IEEE Press， 2004： 126-131.

Line Buffer Reduction for LUT-Based Real-Time Image Rectification

LU Yufeng， LUO Xiaohua， YU Miao， LI Yihang

(InstituteofVLSIDesign，ZhejiangUniversity，Hangzhou310027，China)

Inverse warping is widely adopted to rectify the image with non-linear distortion， which is caused by the perspective feature of optical lens. This scheme stores warping coordinates into look-up table(LUT) to avoid complex coordinates calculation， but requires large amounts of line buffer to place image date to perform inverse warping. To reduce the line buffer usage， this paper presents a line buffer algorithm basing on reading extended， which utilizes the horizontal banking to extend the reading period. The algorithm guarantees the write and read pointers dynamical jumping to provide the space for up and down mapping. The dedicated control scheme can reduce nearly half of the memory usage in contrast to a general circular buffer of maximum offset. The image rectification module has been implemented on a FPGA to remove lens distortions in real time. The experimental results prove that the proposed line buffer algorithm is highly effective in both memory reduction and distortion rectification.

LUT； FPGA； image inverse warping； line buffer； real-time； image rectification； lens distortion

0427-7104(2016)04-0418-07

2015-11-05

浙江省自然科学基金(LY15F040001)

卢宇峰(1991—)，男，硕士研究生；罗小华，男，副教授，通讯联系人，E-mail： luoxh@vlsi.zju.edu.cn.

TN 79

A