盧宇峰，羅小華，俞　淼，李益航

(浙江大學 超大規(guī)模集成電路研究所，杭州 310027)

?

基于LUT實時圖像矯正的行緩存優(yōu)化

盧宇峰，羅小華，俞淼，李益航

(浙江大學 超大規(guī)模集成電路研究所，杭州 310027)

基于反向映射的圖像矯正被廣泛應用于解決光學鏡頭透視引起的非線性畸變失真問題，該方法將映射坐標固化在LUT內(nèi)，避免了復雜的坐標計算，但需要大量行緩存儲備圖像數(shù)據(jù)用以執(zhí)行反向映射.為了減少行緩存的使用，本文提出了一種基于讀擴展的環(huán)形行緩存讀寫算法，利用行同步信號的消隱間隔擴展讀周期，使讀寫指針循序錯開，保證上下映射的空間.相比傳統(tǒng)的以最大偏移作為行緩存的結(jié)構(gòu)，改進的專用控制算法可以減少近一半的內(nèi)存使用.本文中的實時圖像矯正系統(tǒng)已經(jīng)在FPGA上實現(xiàn)，實驗結(jié)果表明所提出的讀擴展行緩存算法顯著地改善了內(nèi)存的消耗，并且獲得良好的實時圖像矯正效果.

LUT； FPGA； 圖像反向映射； 行緩存； 實時； 圖像矯正； 畸變失真

在遙感、醫(yī)學圖像、計算機視覺、多攝像頭視頻和全景圖像等眾多應用領域中，借助圖像映射來矯正由光學鏡頭或者某一特殊視點導致的非線性畸變失真是一項重要的研究課題.圖像映射也通常被用來實現(xiàn)特殊的圖像處理應用如圖像縮放、旋轉(zhuǎn)、平移和拼接等[1].圖像映射是依據(jù)某種幾何關(guān)系將帶有失真的圖像投射到一個正確平面上的一種轉(zhuǎn)變過程，其中反向映射因便于插值而被廣泛采用于硬件實現(xiàn).而在基于反向映射的圖像矯正模塊中需要各像素點相應的正確坐標值，這些坐標值可以在線計算獲得或者被事先儲存在LUT內(nèi).在求取映射坐標時涉及繁瑣的坐標變換和浮點數(shù)的多階矩陣乘法，因而往往不會采用FPGA去實現(xiàn)這些復雜的運算邏輯.Vancea[2]選擇在Xilinx的FPGA中調(diào)用軟核MicroBlaze來設計軟件，進行在線計算映射坐標值.借助坐標LUT的方法可省去復雜的運算，因而不僅顯著提高處理速度并節(jié)省大量FPGA中的DSP資源，此外在FPGA系統(tǒng)內(nèi)也易于控制和實現(xiàn).

圖像矯正系統(tǒng)中的內(nèi)存消耗主要來自坐標LUT和行緩存，而在FPGA的硬件平臺上內(nèi)存的消耗往往不能被低估.Akin[3]提出了一種算法來壓縮用于存取反向映射坐標LUT的大小，并且使用較低復雜度的解壓縮處理得到每一個正確的坐標值，本文也采用類似的LUT壓縮機制使其內(nèi)存消耗僅為1/256.在執(zhí)行反向映射時，用來儲備圖像數(shù)據(jù)的行緩存因為視頻流的實時性而難以被壓縮.因此在眾多設計中，片外的內(nèi)存(如SDRAM、SRAM等)被廣泛使用作為輸入圖像的緩存[2，4-5].Motten[6]則考慮反向映射坐標的各種潛在模式而提出了一種適應性的內(nèi)存分配架構(gòu)來減少行緩存的消耗.Ryoo[7]采用圖像傳感器輸出的bayer格式圖片進行色彩重構(gòu)再作圖像矯正，其從圖像采集源頭來減少圖像大小從而降低后級的內(nèi)存負荷.

本文提出了一種基于讀擴展的環(huán)形行緩存讀寫算法，相比傳統(tǒng)的以最大偏移作為行緩存的結(jié)構(gòu)，此種改進的專用控制算法可以減少近半的內(nèi)存消耗.該算法不同于Motten的方法，不需要針對特殊的潛在模型進行優(yōu)化，是一種較為通用的算法，適用于絕大多數(shù)的鏡頭畸變矯正.流水線架構(gòu)的二線性插值結(jié)構(gòu)[8]也被應用到圖像矯正系統(tǒng)中，以獲得子像素的精度.采用的結(jié)構(gòu)和算法都已在單片F(xiàn)PGA中實現(xiàn)，實驗結(jié)果表明所提出的讀擴展行緩算法顯著地改善了內(nèi)存的消耗，并獲得良好的實時圖像矯正效果.

1　基于LUT的圖像矯正

1.1反向映射矯正圖像

對于鏡頭的非線性失真導致的圖像變形，扭曲不存在同一的規(guī)律，由相機固有特性得到的通用齊次矩陣并不能去除這些非線性失真.而圖像映射是被廣泛應用于矯正鏡頭的非線性畸變失真的有效方法.圖像映射是一種圖像的幾何空間變化，定義了輸入和輸出圖像之間的對應關(guān)系.圖像空間變換的計算方法通?？梢詺w為兩類： 利用正向映射的方法和利用反向映射的方法，如表達式(1)所示：

Forwardmapping： (u，v)=[Fu(x，y)，F(xiàn)v(x，y)]；

Inversemapping： (x，y)=[Fx(u，v)，F(xiàn)y(u，v)]；

(1)

u，v是輸出圖像坐標，而x，y是源圖像坐標.基于正向映射的方法按順序掃描每個輸入像素，然后在由Fu，F(xiàn)v函數(shù)得到輸出圖像的位置賦予像素值.正向映射過程存在一個問題，即可能存在兩個及以上的輸入點對應同一個像素點，這可能導致有些輸出像素沒有被賦值.反向映射則是按照像素格點順序掃描每個輸出像素，根據(jù)Fx，F(xiàn)y函數(shù)所計算出輸入圖像上的對應關(guān)系，并存儲在LUT內(nèi)如圖1所示，再由相應的坐標找到源圖像正確的位置.同時，輸出的像素值依據(jù)周圍的像素值進行重采樣來獲得子像素精度.如此反向映射就不存在空點像素的問題，同時也易于插值算法實現(xiàn).本文便采用反向映射的方法來進行圖像的非線性失真矯正.

1.2反向映射的坐標LUT

在FPGA應用中，廣泛采用LUT進行硬件加速.某些固定的常數(shù)如參數(shù)、坐標值等會被固化在LUT內(nèi)，這不僅可以獲得較高的精度還不需要消耗大量的DSP和邏輯資源去進行復雜的在線計算.因此本文的圖像矯正系統(tǒng)便將反向映射對應的坐標存于LUT內(nèi).

由鏡頭導致的畸變通常有兩部分： 徑向畸變和切向畸變.而主要的失真來自徑向畸變，因此在許多應用場景下切向畸變可以被忽略.通過相機標定，圖像的畸變參數(shù)(包括徑向和切向畸變)被記錄在5×1的向量kc中.若設r2=x2+y2，包含鏡頭畸變的標準化坐標點Xd定義如下：

(2)

因此像素坐標向量與標準化的坐標點向量存在以下的等式(3)的關(guān)系：

(3)

相機的內(nèi)在參數(shù)可表示為一個3×3的矩陣稱為相機矩陣KK.根據(jù)以上的公式，輸出的像素坐標(xp，yp)就被存到LUT內(nèi)用以反向映射如圖1.一套相機以及鏡頭系統(tǒng)對應一個唯一的LUT.而LUT內(nèi)每個單元又分成兩個部分，x坐標部分和y坐標部分，其中x坐標與y坐標都包含整數(shù)和小數(shù)部分.整數(shù)部分被用作定位到相應的源圖像點上，而小數(shù)部分則被用作重采樣所需像素的權(quán)值.

2　行緩存讀寫算法

行緩存是圖像畸變矯正系統(tǒng)中的重要組成部分，但是需占用大量的內(nèi)存來緩存多行圖像數(shù)據(jù)以執(zhí)行實時的圖像反向映射，因此采取一種適當?shù)摹⒏倪M的行緩存算法是非常有必要的.若能節(jié)省行緩存的內(nèi)存使用，便可在單片F(xiàn)PGA內(nèi)矯正多個攝像頭并拼接成一個全景圖像而不需要片外內(nèi)存的支持.

為矯正鏡頭的畸變失真，在執(zhí)行圖像的反向映射操作后，輸出圖像會丟失源圖像四周的部分像素區(qū)，其最終的實際有效部分便如圖2(a)黑色桶型區(qū)域部分.由畸變失真的特性可知，在圖像的上半部分需要之后的行緩存來定位到對應的像素點，稱為下映射；而相反在圖像的下半部分時則需要之前的行緩存來定位尋點，稱為上映射.

整個行緩存的大小主要是由反向映射的垂直坐標決定，圖像的畸變失真越明顯所需要的行緩存則越大.圖像數(shù)據(jù)流持續(xù)無間斷地進入暫存塊，因此圖像的水平像素數(shù)決定了行緩存每一行的尺寸.若以目標像素的當前行作為參考，向下映射為正，向上映射為負，可得到如圖2(b)所示的每一像素行對應的映射范圍圖，數(shù)據(jù)來自一枚640×480分辨率的圖像傳感器和一枚焦距2.1mm的廣角鏡頭.

2.1傳統(tǒng)環(huán)形行緩存

環(huán)形行緩存定義了一片內(nèi)存，并在整幀圖像中重復使用，在傳統(tǒng)的圖像矯正系統(tǒng)中被廣泛使用作為映射像素的緩存.映射后像素和源像素間的坐標差值稱為反向映射的坐標，反向映射垂直坐標的最大值決定了環(huán)形行緩存的大小.圖2(b)展示了最大下映射的垂直坐標偏移是ΔL1行，最大上映射的垂直坐標偏移是ΔL2行.

Linebufferusage： ΔL=ΔL1+ΔL2.

(4)

ΔL行(等式(4))是整個圖像所需的最大行偏移，因此至少需要ΔL行的內(nèi)存空間來執(zhí)行反向映射.基于上述這種緩存架構(gòu)，環(huán)形緩存被分為兩個部分如圖3所示.上半部分內(nèi)存空間提供給負性的反向映射坐標的點進行尋址定位到正確的源圖像的位置，而下半部分內(nèi)存空間則是為正性的反向映射坐標點進行尋址定位.

傳統(tǒng)行緩存結(jié)構(gòu)的讀寫算法在初始化時讀寫指針會停留在環(huán)形內(nèi)存的基地址處.基地址的位置由下映射和上映射的最大范圍決定，圖3的ΔL2行處則被定為環(huán)形行緩存的基地址.當寫控制信號有效時，持續(xù)流入的圖像值被存入行緩存內(nèi)，直到寫指針移動到行緩存的末尾，然后跳轉(zhuǎn)到緩存的起始位置.這是環(huán)形行緩存的特性，有效地利用內(nèi)存.而讀控制信號會落后寫信號ΔL1行激活，這是為第一次圖像反向映射作準備.如果讀控制信號有效得過早會導致映射得到空像素或者未更新的像素值，從而產(chǎn)生錯誤的映射.在整個圖形反向映射執(zhí)行過程中，讀寫指針被同一時鐘所驅(qū)動，保持相等的位移ΔL1行進行跳轉(zhuǎn).值得注意的是，本文提到的讀指針并非真正的內(nèi)存的讀地址，而是讀基地址.因此實際輸出像素的地址=讀指針+反向映射的坐標.

2.2讀擴展環(huán)形行緩存

在傳統(tǒng)環(huán)形緩存中，將上映射和下映射的最大垂直偏移之和作為整體環(huán)形緩存的大小.假設上映射所需的前行緩存區(qū)或者下映射的后行緩存區(qū)可被作為全部環(huán)形緩存所需的內(nèi)存，也就意味著上映射和下映射使用同一片內(nèi)存空間.基于這種構(gòu)想下，等式(5)中的ΔL行將被作為行緩存，相比傳統(tǒng)的環(huán)形緩存，在反向映射過程中此種方案將減少近一半的內(nèi)存使用.但是在執(zhí)行反向映射時需提供正確的像素值而不被新流入的像素點所覆蓋，需要有一種機制能夠保證讀寫指針的這種動態(tài)跳轉(zhuǎn)，如圖4所示，而非傳統(tǒng)環(huán)形行緩存那樣保持讀寫指針相同的位移差.

Linebufferusage： ΔL=max[ΔL1，ΔL2].

(5)

圖像傳感器的視頻流時序中有行同步信號(HSYNC)和場同步信號(VSYNC)，如圖5所示.VSYNC高電平信號被作為一幀圖像開始的標志信號，HSYNC則定義了像素輸入的有效行區(qū)間信號.在視頻流信號中的每個行周期HSYNC信號內(nèi)有一段非顯示區(qū)間稱之為行消隱間隔.鑒于此種特性，本文提出了一種改進的環(huán)形緩存讀寫算法，即讀擴展環(huán)形緩存，這是一種控制讀寫指針線性動態(tài)變化的算法.每當環(huán)形緩存填充了一行像素后，在HSYNC周期內(nèi)的行消隱區(qū)內(nèi)會多讀ΔP個像素點，如圖5所示.

隨著大量的圖像數(shù)據(jù)地不斷流入，讀寫指針間的位移也變得越來越大.則往上可尋址的空間會變得越來越大，而往下可尋址的空間會變得越來越小，這也符合鏡頭失真的特性，因此該算法是一種通用的圖像矯正的行緩存解決方案.其中要為讀擴展像素數(shù)ΔP取一個合理值，如公式(6)所示：

(6)

ΔL是ΔL1和ΔL2間的最大值如式(4)所示，Hp是水平方向上的像素數(shù)，而Vp是垂直方向的像素數(shù)，這兩個值由圖像的分辨率所決定.Δt則指的是一個浮動像素數(shù)，若Δt過大將導致在新的幀刷新信號來之前還未完成所有像素點的反向映射.ΔP可取區(qū)間內(nèi)的任意整數(shù)值，利用讀擴展環(huán)形行緩存算法完成圖像矯正.

圖6讀擴展環(huán)形行緩存的讀寫算法描述

Fig.6The write and read algorithm description for a circular buffer with reading extended

圖6描述了帶讀擴展行緩存讀寫算法的主要步驟，在反向映射的初始階段，讀寫指針處在內(nèi)存的起始位置.與傳統(tǒng)環(huán)形行緩存算法相似的是，讀控制信號在初始化時也會滯后寫控制信號若干行(ΔL行).但是不同于寫有效信號(HSYNC信號)，讀有效信號在每個行周期內(nèi)會擴展ΔP個像素周期.VSYNC中的低電平信號是場消隱信號，場消隱信號又包括場同步時間，場消隱前肩時間和場消隱后肩時間.在HSYNC進入同步脈沖的顯示后沿(即場消隱后肩)時，讀控制信號會持續(xù)保持有效(ΔPe段信號，如圖5所示)，直到所有像素都完成反向映射.這是由初始階段，Read_valid信號的ΔL行延遲以及Δt的取值所導致的.

該算法使得讀寫指針保持一種線性的動態(tài)變化，保證向上映射和向下映射都有充足的空間，而不被新進入的圖像數(shù)據(jù)所覆蓋或映射到未更新的像素點.同時保證反向映射在新一幀的圖像來之前完成所有像素的映射.讀擴展環(huán)形行緩存在內(nèi)存的消耗上有較大優(yōu)勢，而且沒有帶來復雜的控制邏輯，易于實現(xiàn).

2.3圖像矯正系統(tǒng)實現(xiàn)

圖7展示了一個完整的圖像矯正系統(tǒng)的架構(gòu)，主要由LUT模塊，行緩存讀寫控制模塊，行緩存以及RGB插值模塊四部分構(gòu)成.行緩存控制模塊接收到來自攝像頭的圖像數(shù)據(jù)，并放置在行緩存內(nèi).同時從LUT中獲取對應的反向映射的坐標.其中整數(shù)部分，x_diff和y_diff，用來指定行緩存中用以反向映射的窗處理的四角.而小數(shù)部分，x_fraction和y_fraction，用來進行二線性插值算法以完成像素的重采樣，從而獲得子像素精度，避免像素間對齊上的錯誤.行緩存控制模塊在整個系統(tǒng)中占據(jù)絕對重要地位，它根據(jù)之前描述的帶讀擴展行緩存算法，不斷得到讀寫地址，指引著整個反向映射的執(zhí)行.該算法在圖像矯正系統(tǒng)的應用，旨在減少內(nèi)存的消耗，這為矯正系統(tǒng)以及其他所需的硬件應用在單片F(xiàn)PGA內(nèi)得以實現(xiàn).

3　實驗結(jié)果分析

本文提到的圖像矯正架構(gòu)和讀擴展行緩存算法均已在Terasic DE1-SoC平臺內(nèi)實現(xiàn)，其基于Alter Cycle V的FPGA，擁有32075的邏輯資源和3970Kb的內(nèi)存塊.實驗采用了一枚焦距2.1mm的廣角鏡頭，有較大的畸變失真，經(jīng)相機標定計算，反向映射中有最大50行的下映射范圍和最大30行的上映射范圍.圖像來自于一塊640×480分辨率的圖像傳感器，24M的像素時鐘，30幀的刷新頻率.

表1　資源消耗

表1記錄了之前描述的每種行緩存算法的資源消耗，綜合結(jié)果來自Quartus Ⅱ 13.1工具套件.幀緩存作為輸入圖像的暫存器實現(xiàn)起來最為簡便，不用考慮畸變失真的大小，不用計算所需的最大偏移行數(shù)，這也導致其會占用最大的內(nèi)存資源.采用16位RGB 565的編碼格式的640×480分辨率的圖像，一幀的圖像緩存總共需要0.586Mb.FPGA的片上存儲資源非常有限，片內(nèi)的內(nèi)存往往連一幀的圖像緩存都無法承擔.本文提出的讀擴展環(huán)形行緩存算法比傳統(tǒng)環(huán)形行緩存減少了45%的內(nèi)存消耗，卻只額外消耗了基本可忽略的片內(nèi)邏輯資源.因為80行所需的行緩存對應FPGA內(nèi)部的雙口RAM，需要16位地址空間的RAM大?。欢?0行的行緩存則只需15位地址空間的RAM大小，從實際RAM調(diào)用結(jié)果可知會減少一半.其他存儲器資源的消耗來自于存儲壓縮過的映射坐標LUT[3].基于這種改進的專用行緩存控制算法，超過6個的攝像頭可不借助額外的片外存儲器，完成同時實時矯正并拼接成一張全景圖像.

圖8展示了圖像矯正前后的變化，很明顯圖像的畸變失真在(b)圖中得以良好的矯正，特別是圖像上半部分的桌子邊緣處和下半部分的桌面的紋理以及邊緣，黑白標定板的邊緣(已由紅色虛線標注)，由非線性失真導致的明顯彎曲(左圖)，在右圖中已被矯正成物體原本應有的平直形態(tài).同時因為矯正特性會丟失源圖像四周邊緣部分的圖像數(shù)據(jù)，也在右圖中體現(xiàn)了出來.因此實驗結(jié)果充分表明了讀擴展行緩存算法可以節(jié)省大量的行緩存消耗，同時在不損失硬件系統(tǒng)性能的情況下獲得良好的圖像矯正效果.

4　結(jié)　論

為了實時矯正光學鏡頭導致的非線性畸變失真，本文采用基于LUT的圖像反向映射方案，并提出了優(yōu)化內(nèi)存消耗的讀擴展環(huán)形行緩存算法.此種專用行緩存讀寫算法相比傳統(tǒng)環(huán)形行緩存算法可節(jié)省近一半的內(nèi)存消耗，并能解決通用的鏡頭失真問題.該矯正系統(tǒng)已在FPGA中實現(xiàn)，實驗結(jié)果充分表明了此種算法的有效性，并獲得良好的矯正效果.利用這個改進的行緩存讀寫算法，更多基于圖像矯正預處理的復雜的應用也得以在單塊FPGA內(nèi)實現(xiàn)，如特殊應用的多攝像頭系統(tǒng)(全景視頻和虛擬視角合成等).

[1]WOLBERG G. Digital image warping [M]. Los Alamitos： IEEE Computer Society Press， 1990.

[2]VANCEA， C， NEDEVSCHI S. LUT-based image rectification module implemented in FPGA[C]∥2007 IEEE International Conference on Intelligent Computer Communication and Processing. Cluj-Napoca， Romania： IEEE Press， 2007： 147-154.

[3]AKIN A， BAZ I， GAEMPERLE L M， SCHMID A，etal. Compressed look-up-table based real-time rectification hardware[C]∥2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration(VLSI-SoC). Istanbul， Turkey： IEEE Press， 2013： 272-277.

[4]RYOO J R， LEE E S， PARK H K. Real-time implementation of an LUT-based image warping system[C]∥2013 44th International Symposium on Robotics(ISR). Seoul， Korea： IEEE Press， 2013： 1-4.

[5]RODRIGUES J G P， FERREIRA J C. FPGA-based rectification of stereo images[C]∥2010 Conference on Design and Architectures for Signal and Image Processing(DASIP). Edinburgh， United Kingdom： IEEE Press， 2010： 199-206.

[6]MOTTEN A， CLAESEN L， PAN Y. Adaptive memory architecture for real-time image warping[C]∥2012 IEEE 30th International Conference on Computer Design(ICCD). Montreal， Canada： IEEE Press， 2012： 466-471.

[7]RYOO J R， KIM B K， DOH T Y. Computationally efficient colour image warping for real-time video applications [J].ElectronicsLetters， 2015，51(14)： 1067-1069.

[8]GRIBBON， K T， BAILEY D G. A novel approach to real-time bilinear interpolation[C]∥2004 IEEE International Conference on Field-Programmable Technology. Brisbane， Australia： IEEE Press， 2004： 126-131.

Line Buffer Reduction for LUT-Based Real-Time Image Rectification

LU Yufeng， LUO Xiaohua， YU Miao， LI Yihang

(InstituteofVLSIDesign，ZhejiangUniversity，Hangzhou310027，China)

Inverse warping is widely adopted to rectify the image with non-linear distortion， which is caused by the perspective feature of optical lens. This scheme stores warping coordinates into look-up table(LUT) to avoid complex coordinates calculation， but requires large amounts of line buffer to place image date to perform inverse warping. To reduce the line buffer usage， this paper presents a line buffer algorithm basing on reading extended， which utilizes the horizontal banking to extend the reading period. The algorithm guarantees the write and read pointers dynamical jumping to provide the space for up and down mapping. The dedicated control scheme can reduce nearly half of the memory usage in contrast to a general circular buffer of maximum offset. The image rectification module has been implemented on a FPGA to remove lens distortions in real time. The experimental results prove that the proposed line buffer algorithm is highly effective in both memory reduction and distortion rectification.

LUT； FPGA； image inverse warping； line buffer； real-time； image rectification； lens distortion

0427-7104(2016)04-0418-07

2015-11-05

浙江省自然科學基金(LY15F040001)

盧宇峰(1991—)，男，碩士研究生；羅小華，男，副教授，通訊聯(lián)系人，E-mail： luoxh@vlsi.zju.edu.cn.

TN 79

A