摘 要： 在FPGA平臺上，設(shè)計了包括坐標(biāo)旋轉(zhuǎn)引擎和插值" title="雙線性插值">雙線性插值器的數(shù)字圖像旋轉(zhuǎn)系統(tǒng)。闡述了基于CORDIC算法坐標(biāo)旋轉(zhuǎn)引擎的設(shè)計原理，并采用高速的流水線架構(gòu)實現(xiàn)上述電路。綜合后的仿真結(jié)果表明，旋轉(zhuǎn)后的圖像色彩豐富，細(xì)節(jié)部分清晰，可望達(dá)到100幀/s的速度，滿足高分辨率實時應(yīng)用場合的要求。
　　關(guān)鍵詞： 圖像旋轉(zhuǎn)；CORDIC；流水線；雙線性插值

　　數(shù)字圖像旋轉(zhuǎn)是一種常用的數(shù)字圖像處理技術(shù)被廣泛應(yīng)用于醫(yī)療、軍工、航天、計算機視覺處理等領(lǐng)域。由于數(shù)字圖像旋轉(zhuǎn)涉及到三角函數(shù)的計算，所以傳統(tǒng)的圖像旋轉(zhuǎn)多采用軟件方式實現(xiàn)。然而軟件處理的速度慢，無法應(yīng)用于高分辨率實時處理的場合。有文章提出用LUT實現(xiàn)三角函數(shù)，但這種方法要占用大量的存儲空間。本文設(shè)計的圖像旋轉(zhuǎn)系統(tǒng)采用基于CORDIC算法的坐標(biāo)旋轉(zhuǎn)引擎，所設(shè)計的電路轉(zhuǎn)換速度快、精度高，能夠適應(yīng)實時高分辨率場合的高性能要求。
1 坐標(biāo)旋轉(zhuǎn)引擎的算法原理
　　本文所述的圖像坐標(biāo)旋轉(zhuǎn)引擎基于坐標(biāo)旋轉(zhuǎn)數(shù)字計算CORDIC(Coordinated Rotation Digital Computer)算法思想。式(1)為圖像坐標(biāo)旋轉(zhuǎn)的基本公式：

　　

　　觀察式(2)可知，通過上述代換，復(fù)雜的三角函數(shù)運算變換為能夠在FPGA上實現(xiàn)的加法、移位和乘法運算。然而，式(2)的運算還只能計算特定角度的旋轉(zhuǎn)坐標(biāo)，例如arctan2^-1、arctan2^-2、arctan2^-3等。要想計算任意角度的旋轉(zhuǎn)角θ，還需將旋轉(zhuǎn)角θ分解為若干次旋轉(zhuǎn)角度之和。第i次旋轉(zhuǎn)的角度為θ_i=arctan2^-(i-1)(i=1，2，3，…，n)，這樣式(2)變?yōu)椋?br />　　

從式(4)可知，當(dāng)z_n→0時，z₀→δ₁θ₁+δ₂θ₂+…+δ_nθ_n，即：n次迭代運算使旋轉(zhuǎn)的角度之和近似等于θ。這實際上是一種逐次逼近的坐標(biāo)旋轉(zhuǎn)方法，每次旋轉(zhuǎn)，都使累加的旋轉(zhuǎn)角度之和與目標(biāo)旋轉(zhuǎn)角θ更接近。在理想的情況下，當(dāng)n為無窮大時，累加的旋轉(zhuǎn)角度等于目標(biāo)旋轉(zhuǎn)角θ。但在實際中，硬件資源有限，因此要根據(jù)實際應(yīng)用場合，確定可以接受的角度誤差大小，從而確定迭代次數(shù)n。對于n次迭代運算，旋轉(zhuǎn)角度的精度為arctan2^-(n-1)。
　　觀察式(3)，每次迭代運算都包括一次乘法，這樣n次迭代運算就要用n次乘法，這將十分浪費硬件資源。實際上，對n迭代運算，k值的累積為，與旋轉(zhuǎn)角度?茲無關(guān)。例如，對于6次迭代運算，k的累積為k≈0.607 3。也就是說，只需要在最后的一次移位加法運算后，再作一次乘法。
2 坐標(biāo)旋轉(zhuǎn)引擎電路設(shè)計
　　實現(xiàn)基于CORDIC算法的坐標(biāo)旋轉(zhuǎn)引擎，可采用較簡潔的狀態(tài)機結(jié)構(gòu)或高速的n級流水線結(jié)構(gòu)（n為迭代次數(shù)）。狀態(tài)機結(jié)構(gòu)使用的資源較少，但需要n個時鐘才能完成一個坐標(biāo)的變換。流水線結(jié)構(gòu)使用的資源較多，但每一時鐘就能完成一個坐標(biāo)的變換。本設(shè)計是針對實時應(yīng)用的圖像旋轉(zhuǎn)，對坐標(biāo)轉(zhuǎn)換的速度要求較高，因此采用流水線結(jié)構(gòu)。
　　圖1為采用8級流水線的電路結(jié)構(gòu)圖，角度的精度可以達(dá)到±0.447 6°。每一級流水線完成一次移位和加法（或減法）運算，然后將這一級迭代運算的結(jié)果送到下一級寄存器，供下一級流水線運算使用。運算過程的中間結(jié)果包含小數(shù)，因此要將寄存器的低位進(jìn)行擴(kuò)展，以儲存小數(shù)結(jié)果。這相當(dāng)于將小數(shù)整數(shù)化，例如，4位小數(shù)寄存器中的4’b0111表示的數(shù)值為5/2⁴=0.312 5。最后一次迭代結(jié)果要乘以k值，但是k值是小數(shù)，F(xiàn)PGA內(nèi)又只有整數(shù)乘法器。為此，取k乘以2^m的整數(shù)部分，即將k值整數(shù)化。一個數(shù)乘以2^m，相當(dāng)于將這個數(shù)左移m位。這樣，只要最后再將乘法器值右移m位即可。m的值取決于設(shè)計要求的坐標(biāo)精度，m值越大，k值的有效位越多，坐標(biāo)的精度就越高。

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

　　
其中，f_A、f_B、f_C、f_D是像點1、2、3、4處的灰度值。雙線性插值利用了周圍四個相鄰點的灰度值，在X、Y兩個方向上作線性內(nèi)插求得待采樣點的灰度值。四個相鄰點所占的權(quán)值由它們與待采樣點在X、Y方向的距離決定。
　　　　

　　如果采用式(5)實現(xiàn)電路，則每條路徑要經(jīng)過兩次乘法和一次加法，路徑延時較大。為了優(yōu)化電路實現(xiàn)，把式(5)分解成式(6)。與式(5)相比，增加了中間量ftemp1、ftemp2，這兩個中間量可以用一組中間寄存器儲存。這樣，可以把電路分為兩級流水線，每級流水線的路徑上只要經(jīng)過一次乘法和一次加法，減少了一個乘法器的路徑延時，有利于提高時鐘頻率。圖2（b）是采用兩級流水線結(jié)構(gòu)的雙線性插值器的電路。
4 系統(tǒng)的架構(gòu)設(shè)計
　　圖3是圖像旋轉(zhuǎn)電路的架構(gòu)圖，它由5個模塊組成：控制單元、坐標(biāo)產(chǎn)生器、坐標(biāo)旋轉(zhuǎn)引擎、地址產(chǎn)生器及雙線性插值器。坐標(biāo)旋轉(zhuǎn)引擎和雙線性插值器在前面已經(jīng)作了詳細(xì)的描述。下面介紹其余幾個模塊。

　　控制單元：為系統(tǒng)提供時鐘和復(fù)位信號，并協(xié)調(diào)系統(tǒng)各模塊的運行。當(dāng)系統(tǒng)復(fù)位時，各個模塊數(shù)據(jù)通路上的寄存器被清零，數(shù)據(jù)加載重新開始。經(jīng)過若干個時鐘后，當(dāng)?shù)谝患壞K的處理數(shù)據(jù)到達(dá)輸出端時（即下一級模塊的輸入端），向控制單元發(fā)出done信號，控制單元向該模塊的下一級模塊發(fā)出啟動信號run，其他模塊的控制順序類似。
　　坐標(biāo)產(chǎn)生器：產(chǎn)生一幅圖像的x和y坐標(biāo)。可用兩個計數(shù)器（x計數(shù)器和y計數(shù)器）實現(xiàn)，以1024×768的分辨率為例，在時鐘信號的驅(qū)動下，x計數(shù)器從0開始計數(shù)，每個時鐘加1，直到1 024，x計數(shù)器重置為零。每當(dāng)x計數(shù)器加到1 024時，y計數(shù)器加1。當(dāng)y計數(shù)器值為768時，x計數(shù)器和y計數(shù)器都重置為零，然后再重新開始產(chǎn)生下一幅圖像的坐標(biāo)。
　　地址產(chǎn)生器：如前所述，旋轉(zhuǎn)后圖像的像素灰度，要用到原圖像的四個相鄰像素作插值計算得到。地址產(chǎn)生就是根據(jù)映射到原圖像的坐標(biāo)，尋址RAM中A、B、C、D四個像素的灰度值，并送到雙線性插值器。另外，地址產(chǎn)生器還要判斷坐標(biāo)轉(zhuǎn)換器輸入的坐標(biāo)是否超出了原圖像的范圍。如果超出，則A、B、C、D四個像素的RGB值為零。
5 驗證方法及結(jié)果
　　本設(shè)計的目標(biāo)器件是Altera cycloneII EP2C35F672C8。驗證的軟件平臺包括Altera QuartusII7.2 SP3，Modelsim6.1g，Matlab7.3。設(shè)計使用Verilog HDL語言開發(fā)，并用QuartusII進(jìn)行綜合，綜合后產(chǎn)生整個設(shè)計的門級網(wǎng)表.vo文件和帶門級延時信息的.sdo文件。在Modelsim中編寫testbench，調(diào)用上述.vo和.sdo文件進(jìn)行仿真，仿真的庫是altera cycloneii庫。測試的圖像是用Matlab讀出一幅JPG圖像的RGB數(shù)據(jù)。在testbench用＄readmemh命令，將RGB數(shù)據(jù)導(dǎo)入虛擬的memory（記為RAM_IN）中。仿真的圖像結(jié)果保存在另一片虛擬的memory(記為RAM_OUT)中。在Modelsim仿真結(jié)束后，將RAM_OUT的數(shù)據(jù)導(dǎo)出到MATLAB中，并用這些數(shù)據(jù)顯示圖像。Matlab在整個仿真過程中沒有對圖像做任何算法處理，只作為圖像數(shù)據(jù)的產(chǎn)生和顯示平臺。
　　仿真結(jié)果如圖4。圖4(a)是原始圖像，圖4(b)是本文設(shè)計的仿真結(jié)果。原圖像分辨率為512×512，旋轉(zhuǎn)后的圖像分辨率為700×700，超出原圖像部分填黑像素。旋轉(zhuǎn)后的圖像色彩豐富，細(xì)節(jié)部分清晰，可以滿足大多數(shù)應(yīng)用場合要求。速度方面，設(shè)計綜合后，經(jīng)QuartusII7.2的Timing analyzer分析，設(shè)計的像素時鐘可以達(dá)到120 MHz。以此推算，在1 280×1 024的分辨率下，可以達(dá)到100幀/s的速度。因此，本系統(tǒng)設(shè)計能夠滿足高分辨率實時應(yīng)用場合的速度要求。

參考文獻(xiàn)
[1] BHANDARKAR S M，YU H.VLSI implementation of real-time image rotation.Proceedings of international conferenceon image processing，Vol.2，1996：1015-1018.

[2] HORMIGO J，VILLALBA J，ZAPATA E L.CORDICprocessor for variable-precision interval arithmetic.Journalof VLSI signal processing 37，2004：21-39.
[3] DUPRAT J，MULLER J M.The CORDIC algorithm：Newresults for fast VLSI implementation.IEEE Trans.onComputers，1993，42(12)：168-178.
[4] 劉怡，黃自力，王經(jīng)緯，等.FPGA雙線性插值圖像變換系統(tǒng)的設(shè)計與實現(xiàn).中國測量技術(shù)，2008，34(5).
[5] 王祚棟，魏少軍.一種適用于指紋識別ASIC的圖像旋轉(zhuǎn)算法，微電子學(xué)，2004，34(10).