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

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

　　

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

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

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

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

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

參考文獻(xiàn)
[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] 劉怡，黃自力，王經(jīng)緯，等.FPGA雙線性插值圖像變換系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).中國(guó)測(cè)量技術(shù)，2008，34(5).
[5] 王祚棟，魏少軍.一種適用于指紋識(shí)別ASIC的圖像旋轉(zhuǎn)算法，微電子學(xué)，2004，34(10).