摘 要： 在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).