基于CORDIC算法的数字图像旋转实现

　　摘 要： 　　关键词： 图像旋转；CORDIC；流水线；双线性插值
    
   　　数字图像旋转是一种常用的数字图像处理技术被广泛应用于医疗、军工、航天、计算机视觉处理等领域。由于数字图像旋转涉及到三角函数的计算，所以传统的图像旋转多采用软件方式实现。然而软件处理的速度慢，无法应用于高分辨率实时处理的场合。有文章提出用LUT实现三角函数，但这种方法要占用大量的存储空间。本文设计的图像旋转系统采用基于CORDIC算法的坐标旋转引擎，所设计的电路转换速度快、精度高，能够适应实时高分辨率场合的高性能要求。
1 坐标旋转引擎的算法原理
　　本文所述的图像坐标旋转引擎基于坐标旋转数字计算CORDIC(Coordinated Rotation Digital Computer)算法思想。式(1)为图像坐标旋转的基本公式：

　　
   　　观察式(2)可知，通过上述代换，复杂的三角函数运算变换为能够在FPGA上实现的加法、移位和乘法运算。然而，式(2)的运算还只能计算特定角度的旋转坐标，例如arctan2-1、arctan2-2、arctan2-3等。要想计算任意角度的旋转角θ，还需将旋转角θ分解为若干次旋转角度之和。第i次旋转的角度为θi=arctan2-(i-1)(i=1，2，3，…，n)，这样式(2)变为：
　　

从式(4)可知，当zn→0时，z0→δ1θ1+δ2θ2+…+δnθn，即：n次迭代运算使旋转的角度之和近似等于θ。这实际上是一种逐次逼近的坐标旋转方法，每次旋转，都使累加的旋转角度之和与目标旋转角θ更接近。在理想的情况下，当n为无穷大时，累加的旋转角度等于目标旋转角θ。但在实际中，硬件资源有限，因此要根据实际应用场合，确定可以接受的角度误差大小，从而确定迭代次数n。对于n次迭代运算，旋转角度的精度为arctan2-(n-1)。
　　观察式(3)，每次迭代运算都包括一次乘法，这样n次迭代运算就要用n次乘法，这将十分浪费硬件资源。实际上，对n迭代运算，k值的累积为 ，与旋转角度?兹无关。例如，对于6次迭代运算，k的累积为k≈0.607 3。也就是说，只需要在最后的一次移位加法运算后，再作一次乘法。
2 坐标旋转引擎电路设计
　　实现基于CORDIC算法的坐标旋转引擎，可采用较简洁的状态机结构或高速的n级流水线结构（n为迭代次数）。状态机结构使用的资源较少，但需要n个时钟才能完成一个坐标的变换。流水线结构使用的资源较多，但每一时钟就能完成一个坐标的变换。本设计是针对实时应用的图像旋转，对坐标转换的速度要求较高，因此采用流水线结构。
　　图1为采用8级流水线的电路结构图，角度的精度可以达到±0.447 6°。每一级流水线完成一次移位和加法（或减法）运算，然后将这一级迭代运算的结果送到下一级寄存器，供下一级流水线运算使用。运算过程的中间结果包含小数，因此要将寄存器的低位进行扩展，以储存小数结果。这相当于将小数整数化，例如，4位小数寄存器中的4’b0111表示的数值为5/24=0.312 5。最后一次迭代结果要乘以k值，但是k值是小数，FPGA内又只有整数乘法器。为此，取k乘以2m的整数部分，即将k值整数化。一个数乘以2m，相当于将这个数左移m位。这样，只要最后再将乘法器值右移m位即可。m的值取决于设计要求的坐标精度，m值越大，k值的有效位越多，坐标的精度就越高。
   
   
   
　　另外，还要注意到，在图像处理中，一般以图像的左上角为坐标原点。而做图像旋转时一般是以图像的中心为坐标原点，所以在进行坐标转换前后，要进行坐标系平移，这部分电路容易实现，未在图1中画出。
3 双线性插值器的设计
　　经过坐标转换电路，就可得到旋转后的像素点(x，y)对应的原图像的像素点(x′，y′)。也就是说，可以用原图像像素点(x′，y′)处的RGB值填充旋转后的图像像素点(x，y)处的RGB值。但是，还须注意到，求得的(x′，y′)带有小数，而原图像的像素坐标为整数。
　　如图2(a)所示，空心点表示(x′，y′)的像素，实心点表示原图像中的整数坐标像素。其中（xM，yM）是(x′，y′)的整数部分，Δx和Δy是其小数部分。(x′，y′)处的RGB值未知，需要通过图像插值求解。常用的图像插值方法有最近邻插值、双线性插值、双三次插值等。最近邻插值直接取与(x′，y′)最接近像素点的RGB值，所需要的硬件资源最少，但插值效果很差，图像容易出现锯齿；双三次插值充分考虑了(x′，y′)邻近像素的RGB值及其变化的连续性，插值效果最好，但所需要的硬件资源很多；双性线插值的效果比最近邻插值的效果好得多，在大多数应用场合都能满足要求，其所需要的硬件资源也比双三次插值少得多。综合权衡硬件资源和图像插值效果，本设计采用双线性插值。式(5)表示了双线性插值的原理。
   
   　　
其中，fA、fB、fC、fD是像点1、2、3、4处的灰度值。双线性插值利用了周围四个相邻点的灰度值，在X、Y两个方向上作线性内插求得待采样点的灰度值。四个相邻点所占的权值由它们与待采样点在X、Y方向的距离决定。
　　 　　
   　　如果采用式(5)实现电路，则每条路径要经过两次乘法和一次加法，路径延时较大。为了优化电路实现，把式(5)分解成式(6)。与式(5)相比，增加了中间量ftemp1、ftemp2，这两个中间量可以用一组中间寄存器储存。这样，可以把电路分为两级流水线，每级流水线的路径上只要经过一次乘法和一次加法，减少了一个乘法器的路径延时，有利于提高时钟频率。图2（b）是采用两级流水线结构的双线性插值器的电路。
4 系统的架构设计
　　图3是图像旋转电路的架构图，它由5个模块组成：控制单元、坐标产生器、坐标旋转引擎、地址产生器及双线性插值器。坐标旋转引擎和双线性插值器在前面已经作了详细的描述。下面介绍其余几个模块。
   
   　　控制单元：为系统提供时钟和复位信号，并协调系统各模块的运行。当系统复位时，各个模块数据通路上的寄存器被清零，数据加载重新开始。经过若干个时钟后，当第一级模块的处理数据到达输出端时（即下一级模块的输入端），向控制单元发出done信号，控制单元向该模块的下一级模块发出启动信号run，其他模块的控制顺序类似。
　　坐标产生器：产生一幅图像的x和y坐标。可用两个计数器（x计数器和y计数器）实现，以1024×768的分辨率为例，在时钟信号的驱动下，x计数器从0开始计数，每个时钟加1，直到1 024，x计数器重置为零。每当x计数器加到1 024时，y计数器加1。当y计数器值为768时，x计数器和y计数器都重置为零，然后再重新开始产生下一幅图像的坐标。
　　地址产生器：如前所述，旋转后图像的像素灰度，要用到原图像的四个相邻像素作插值计算得到。地址产生就是根据映射到原图像的坐标，寻址RAM中A、B、C、D四个像素的灰度值，并送到双线性插值器。另外，地址产生器还要判断坐标转换器输入的坐标是否超出了原图像的范围。如果超出，则A、B、C、D四个像素的RGB值为零。
5 验证方法及结果
　　本设计的目标器件是Altera cycloneII EP2C35F672C8。验证的软件平台包括Altera QuartusII7.2 SP3，Modelsim6.1g，Matlab7.3。设计使用Verilog HDL语言开发，并用QuartusII进行综合，综合后产生整个设计的门级网表.vo文件和带门级延时信息的.sdo文件。在Modelsim中编写testbench，调用上述.vo和.sdo文件进行仿真，仿真的库是altera cycloneii库。测试的图像是用Matlab读出一幅JPG图像的RGB数据。在testbench用＄readmemh命令，将RGB数据导入虚拟的memory（记为RAM_IN）中。仿真的图像结果保存在另一片虚拟的memory(记为RAM_OUT)中。在Modelsim仿真结束后，将RAM_OUT的数据导出到MATLAB中，并用这些数据显示图像。Matlab在整个仿真过程中没有对图像做任何算法处理，只作为图像数据的产生和显示平台。
　　仿真结果如图4。图4(a)是原始图像，图4(b)是本文设计的仿真结果。原图像分辨率为512×512，旋转后的图像分辨率为700×700，超出原图像部分填黑像素。旋转后的图像色彩丰富，细节部分清晰，可以满足大多数应用场合要求。速度方面，设计综合后，经QuartusII7.2的Timing analyzer分析，设计的像素时钟可以达到120 MHz。以此推算，在1 280×1 024的分辨率下，可以达到100帧/s的速度。因此，本系统设计能够满足高分辨率实时应用场合的速度要求。
   
   
  
   参考文献
[1] BHANDARKAR S M，YU H.VLSI implementation of real-time image rotation.Proceedings of international conference on image processing，Vol.2，1996：1015-1018.
   [2] HORMIGO J，VILLALBA J，ZAPATA E L.CORDIC processor for variable-precision interval arithmetic.Journal of VLSI signal processing 37，2004：21-39.
[3] DUPRAT J，MULLER J M.The CORDIC algorithm：New results for fast VLSI implementation.IEEE Trans.on Computers，1993，42(12)：168-178.
[4] 刘怡，黄自力，王经纬，等.FPGA双线性插值图像变换系统的设计与实现.中国测量技术，2008，34(5).
[5] 王祚栋，魏少军.一种适用于指纹识别ASIC的图像旋转算法，微电子学，2004，34(10).