摘 要： 在FPGA平臺上，設計了包括坐標旋轉引擎和插值" title="雙線性插值">雙線性插值器的數字圖像旋轉系統。闡述了基于CORDIC算法坐標旋轉引擎的設計原理，并采用高速的流水線架構實現上述電路。綜合后的仿真結果表明，旋轉后的圖像色彩豐富，細節部分清晰，可望達到100幀/s的速度，滿足高分辨率實時應用場合的要求。
　　關鍵詞： 圖像旋轉；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)可知，當z_n→0時，z₀→δ₁θ₁+δ₂θ₂+…+δ_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/2⁴=0.312 5。最后一次迭代結果要乘以k值，但是k值是小數，FPGA內又只有整數乘法器。為此，取k乘以2^m的整數部分，即將k值整數化。一個數乘以2^m，相當于將這個數左移m位。這樣，只要最后再將乘法器值右移m位即可。m的值取決于設計要求的坐標精度，m值越大，k值的有效位越多，坐標的精度就越高。

　　另外，還要注意到，在圖像處理中，一般以圖像的左上角為坐標原點。而做圖像旋轉時一般是以圖像的中心為坐標原點，所以在進行坐標轉換前后，要進行坐標系平移，這部分電路容易實現，未在圖1中畫出。
3 雙線性插值器的設計
　　經過坐標轉換電路，就可得到旋轉后的像素點(x，y)對應的原圖像的像素點(x′，y′)。也就是說，可以用原圖像像素點(x′，y′)處的RGB值填充旋轉后的圖像像素點(x，y)處的RGB值。但是，還須注意到，求得的(x′，y′)帶有小數，而原圖像的像素坐標為整數。
　　如圖2(a)所示，空心點表示(x′，y′)的像素，實心點表示原圖像中的整數坐標像素。其中（x_M，y_M）是(x′，y′)的整數部分，Δx和Δy是其小數部分。(x′，y′)處的RGB值未知，需要通過圖像插值求解。常用的圖像插值方法有最近鄰插值、雙線性插值、雙三次插值等。最近鄰插值直接取與(x′，y′)最接近像素點的RGB值，所需要的硬件資源最少，但插值效果很差，圖像容易出現鋸齒；雙三次插值充分考慮了(x′，y′)鄰近像素的RGB值及其變化的連續性，插值效果最好，但所需要的硬件資源很多；雙性線插值的效果比最近鄰插值的效果好得多，在大多數應用場合都能滿足要求，其所需要的硬件資源也比雙三次插值少得多。綜合權衡硬件資源和圖像插值效果，本設計采用雙線性插值。式(5)表示了雙線性插值的原理。

　　
其中，f_A、f_B、f_C、f_D是像點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).