FPGA 的高性能暗原色先驗算法設計

蔣守歡，汪榮貴，王 晶，張冬梅，李 想

JIANG Shouhuan,WANG Ronggui,WANG Jing,ZHANG Dongmei,LI Xiang

合肥工業大學 計算機與信息學院，合肥230009

School of Computer and Information,Hefei University of Technology,Hefei 230009,China

1 引言

霧天退化圖像的處理一直以來是圖像增強研究的熱點，特別是近幾年北京等地區出現霧霾，嚴重影響了戶外交通的安全。近年來，He 等[1]提出地暗原色先驗去霧算法，對霧天圖像有很好的處理效果。該算法基于一個先驗規律，即大多數戶外無霧圖像的局部區域的R、G、B三個通道中，至少存在一個通道的值很低幾乎為零，該值稱為暗原色值。由暗原色值可以初步估計出透射率，接著用軟摳圖的方法進一步對透射率求精，得到恢復后的圖像。該算法使用軟摳圖來細化透射率，耗費了大量的運行時間和資源，不滿足實際的應用。

針對上述問題，研究人員提出了一些基于暗原色先驗的改進算法，其中楊靖宇等[2]用內插值的方法對透射率求精，但這種方法僅針對航空影像特有的環境進行處理；很多學者用雙邊濾波對透射率進行處理[3-9]，但是雙邊濾波的二維實現方式和浮點型空間臨近度因子不利于硬件實現，且計算量大，實時性難以得到滿足。引導濾波[10]是He 等提出來的一種新型濾波算法，主要應用在圖像平滑和圖像細節增強。引導濾波在圖像平滑時，具有較好的保邊去噪的效果。本文用引導濾波器對透射率求精[10]，采用自頂向下[11-15]的設計方式，把暗原色先驗算法劃分為兩個模塊：透射率模塊和引導濾波器模塊，其中引導濾波器模塊是設計的重點，它的核心模塊是均值濾波，通過保存局部窗口最左邊與最右邊兩列的值，加上/減去其相應列中某個像素的點的值，設計出了一種資源占有率低、延遲低的均值濾波器。與傳統的均值濾波相比，文中提出的快速算法可以消除很多冗余的計算，能有效地降低計算復雜度，達到每個時鐘周期處理一個像素，模塊的設計具有并行流水的特點，適合FPGA的設計方式，有效提高了系統的性能。用Altera 公司CycloneII 系列的EP2C70 的FPGA 開發板實現提出的快速算法。綜合實驗結果表明，快速暗原色先驗算法的邏輯資源使用量和內存資源使用量較低，低端FPGA 可滿足要求，系統最大運行頻率可達107 MHz。另一方面，把FPGA 實現的快速方法處理結果與Matlab 結果作比較，最大誤差率不大于0.8%，并且每秒可以處理1 024×1 024 大小圖像100 幀，完全滿足實時性要求。

2 暗原色先驗算法

2.1 暗原色先驗模型

大氣散射模型[10]是由McCartney 首次提出，該模型描述了霧天圖像的退化過程，可用如下公式表示：

I表示觀測圖像，J是需要恢復的圖像，A為全球大氣光，t為透射率，去霧的目標就是從I中恢復J。

暗原色先驗理論是He 等對大量戶外無霧圖像做統計試驗得到的，該理論認為在大多數非天空的局部區域內，總是存在某些像素點，其R、G、B三個通道中至少有一個通道的像素值趨近于0，即：

Jc即像素J的某一顏色通道，Ω(x)是以像素x為中心的一塊方形區域，Jdark是圖像J在Ω(x)區域內的暗原色。

在公式（1）中，首先假設A 為常量，t在一個局部區域內的值為固定值～t，那么對公式（1）兩次取最小值運算，為使還原后的圖像更有真實感和深度感，引入一個常量ω，表達如下：

最后由下式計算去霧后的清晰圖像：

2.2 引導濾波器對透射率求精

由于基于暗原色先驗假設求出的透射圖存在偽影或者塊狀效應，因此采用引導濾波器對透射圖作進一步處理。

圖像引導濾波是一個線性平移可變的濾波過程，基本思想為：引導圖像與平滑后的圖像之間存在局部線性的關系，設引導圖像為I，輸入圖像為p，則輸出圖像q為：

其中ak、bk為線性系數，且在局部窗口wk中為常數；Ii為引導圖像中的一個像素點；qi為輸出圖像中的一個像素點。為確定以上公式中的線性系數，并滿足使得q與p的差別最小，可將該系數的確定轉化為最優化問題進行求解：

其中ε為防止ak取值過大的調整參數，則ak、bk求解表達式為：

其中μk和分別表示引導圖像I中局部窗口wk的均值和方差；|w|表示局部窗口wk的像素個數；表示輸入圖像p在局部窗口wk的均值。結合公式（7）和（8）得到：

本文選取的引導圖像為t，則公式（7）和（8）可以簡化為：

最終處理后的透射率圖為：

3 引導濾波的快速計算

由2.2 節所述，本文引導濾波圖像的選取和待處理的圖像是同一幅。其中公式（9）是一個典型的線性變換，其線性變換系數，可由公式（7）和（8）得出；而公式（10）、（11）需計算每個窗口內的均值和方差，由方差公式可得：

3.1 傳統均值濾波計算方法

傳統的均值濾波計算方法是對每一個新的像素點計算其鄰域內(2W+1)×(2W+1)個像素點的和。這樣每一次的計算復雜度為Ο((2W+1)2)，對于大小為M×N的圖像，其復雜度為Ο(MN(2W+1)2)，若圖像窗口(2W+1)較大，不僅使得計算復雜度增加，同時不符合FPGA 的并行流水的處理方式，會耗費很大的邏輯資源，降低系統的最大運行頻率，不利于硬件的實現。

3.2 改進的均值濾波計算方法

針對傳統均值濾波計算復雜度高的問題，本文設計一種與計算復雜度和窗口大小無關的均值濾波器，優化后的濾波器其時間復雜度不依賴于窗口的大小，節省資源的同時，提高了系統的頻率。

一幅圖像I中，I(x,y)表示像素點(x,y)的亮度值，定義SUM(x,y)表示以(x,y)為中心(2W+1)2個像素點的和，SUM(x,y)表示第x列，行坐標范圍為[y-W,y+W]共2W+1 個像素點的和，mean(x,y)表示以(x,y)為中心(2W+1)2個像素點的均值。圖1（1）為SUM(x-1,y)，圖1（2）為SUM(x,y)，二者的區別是圖1（2）所示的標記為“ + ”和“ - ”的部分。其中：

（1）SUM(x+W,y)通過標記為“ + ”的2W+1 個像素計算；

（2）SUM(x-W-1,y) 通過標記為“ - ”的2W+1個像素計算。

SUM(x,y)和mean(x,y)可通過下式求得：

圖1（2）中，標記為“-”的且有陰影線部分共2W個像素的和存儲在sum buffer 中，這個和的計算可以通過SUM(x-W-1,y)減去左上角標記為“ - ”的亮度值I(x-W-1,y-W)得到。通過這種方法，SUM(x,y)的時間復雜度降低為O(2W+1)。

當一行中所有的像素都計算完成，此時要產生下一行以(x,y+1)為中心，(2W+1)2個像素的和SUM(x,y+1)，如圖1（3）所示。SUM(x,y+1)的計算同樣可以使用上述所描述的方法。回顧在計算SUM(x+2W+1,y)時，由于陰影部分帶有“+”標注的和已經存儲到sum buffer中，通過讀取陰影部分的sum buffer，加上I(x+W,y+W+1)，就能得到SUM(x+W,y+1)。同理SUM(x-W-1,y+1)可由計算SUM(x-2W-1,y+1)時，存儲在sum buffer的值加上左上角“- ”標注像素得到。

圖1 改進的均值濾波器方法

圖2 窗口的掃描方式

綜上且由公式（14），把得到的SUM(x-W-1,y+1)和SUM(x+W,y+1)存儲到temporal sum buffer 中，分別用來計算SUM(x,y+1)和SUM(x+2W+1,y+1)，如圖1（4）所示。通過這種優化，算法的時間復雜度為常數，與窗口的大小無關。

上述方法中，為了計算所有的SUM(x,y)，需要擴大掃描范圍得到對應的SUM(x+W,y)和SUM(x-W-1,y)。如圖2（1），當掃描窗口進入圖像第一個點的時候，雖然這時的I(-W,-W) 超出圖像范圍，仍需要計算SUM(0,-W)。圖2（2）中隨著窗口沿著x軸移動，超出圖像一列時，被訪問的I(X,0)用來計算SUM(X,-W)。此時，實際上是I(0,1) 代替了I(X,0)，計算得到的是SUM(0,-W+1)，由于I(X,0)已經超出圖像范圍，在計算SUM(x-W,-W)時不需要加上SUM(X,-W)的值，SUM(0,-W+1)的值用來計算SUM(-W,-W+1)。圖2（3）為兩個不同窗口交替進行處理。當窗口移動到圖2（4）時，已經掃描了X×(Y+W)個像素，但是此時仍需要多掃描W個像素如圖2（5）所示，即掃描窗口到達圖2（6）時共掃描了X×(Y+W)+W個像素。當W遠小于Y時，最后的W個像素可忽略，但是在實際應用中一般不忽略。

4 暗原色先驗算法的FPGA 實現

由前文對算法的理論分析，整個算法的流程是先求透射率，然后對透射率求精，最后得出處理結果，因此本文按照自頂向下的設計方式，暗原色先驗算法的模塊如圖3 虛線框內所示。整個算法模塊由透射率模塊和引導濾波器模塊兩部分組成，其中透射率模塊主要是求暗原色的值，引導濾波器模塊主要是均值濾波器的設計。

圖3 算法模塊框圖

4.1 透射率t 模塊

由公式（2）和公式（3）可知，透射率t的計算首先是求暗原色即局部窗口內3 個通道的最小值，然后由暗原色的值與大氣光A 作乘加運算。因此該模塊主要的設計是2W+1 行數據的存儲(2W+1 表示局部窗口的大小），以及局部窗口內像素的比較。以3×3 窗口為例，設計的投射率模塊如圖4 所示。

圖4 透射率t 的電路結構

其處理流程如下：第一行的數據到來時，先經過空間轉換，變換到R、G、B空間，由比較器對3 個通道的數據作比較，得到一個最小值，將其存入Line Buffer0 中；當第二行數據到來時，把Line Buffer0 存儲的第一行數據讀出，存入到Line Buffer1 中，同時把第二行的數據寫入Line Buffer0 中；當第三行的數據到來時，作同樣的操作，并將三行的數據進入其后的9 個寄存器中，經過比較器比較，得出暗原色的值。暗原色的值再與大氣光A 作乘加運算，求得透射率t。

4.2 引導濾波器模塊的實現

由第3 章分析可知，引導濾波器的實現就是要設計4 個均值濾波器，其結構框圖如圖5 所示。

圖5 引導濾波器結構框圖

4.2.1 提出的快速均值濾波器實現

在3.2節提出的均值濾波器改進方法，可將濾波器電路設計如圖6 所示。假設SUM(x,y)，SUM(x+W,y)，SUM(x-W-1,y)分別存放在寄存b（或b′），bp，bm中。如圖2（2）圖2（3）所示，當兩個不同窗口（當前行和下一行）同時對圖像掃描時，寄存器b′用來存放當前行局部窗口中心點超出圖像范圍，并且局部窗口中心點還未到達下一行圖像時局部窗口的和，寄存器b用來存放當前行局部窗口中心點未超出圖像范圍的局部窗口的和。分別用mask_p，mask_m，reset 清零控制信號來控制bp，bm，b′的清零。假設SUM(x-1,y)已經計算出并且存入寄存器b中，同時可以I(x+W,y+W)與sum buffer 對應位置的值求和，得到的結果為SUM(x+W,y)，存儲到寄存器bp中。然后把寄存器b中的值與寄存器bp中的值相加，得到的結果與寄存器bm中的值相減，結果為SUM(x,y)，重新寫入寄存器b中。與此同時，把寄存器bp中的值存入temporal sum buffer，延時(2W+1)個時鐘周期后轉變為寄存器bm的值，用來計算SUM(x+2W+1,y)。把寄存器bm中的值與I(x-W-1,y-W)的差寫入sum buffer，為計算下一行的SUM(x-2W+1,y+1)做準備，最后由SUM(x,y)除以局部窗口的像素個數得到均值mean(x,y)。整個設計符合流水線的特征，并且每個時鐘周期能計算得到一個SUM(x,y)。

圖6 均值濾波器產生單元

4.2.2 引導濾波器電路設計

引導濾波器的處理過程可由公式（9）、（10）、（11）來描述，硬件結構如圖7 所示。先通過兩個mean filter 得到像素點在窗口內的方差，求出ak、bk，然后經過兩個mean filter分別求出其均值，最后經過一個乘加器得到處理結果。

圖7 引導濾波器電路結構

4.3 整體電路設計

整個算法流程如圖3 所示，結合公式（4），整體電路結構如圖8 所示。先通過透射率t模塊，得到初步的透射率估計，然后經過引導濾波器對t求精，求精后得到的t～與閾值t0作比較，再與經過fifo 延遲后的原圖數據作乘加運算，最后得到輸出結果。

圖8 所示的整體電路結構，采用全流水線設計，每個時鐘周期處理一個像素，從而實現即時輸出，另外文中所有用到小數處理的部分均采用擴大整數倍來實現（本文統一采用擴大倍數為512 倍）。整個處理過程的延遲時間由窗口的大小決定。例如，在投射率t模塊窗口大小選擇為3×3，向導濾波器窗口大小選擇為5×5，則整個系統有13 行的延時。

圖8 整體電路結構

5 實驗結果

本文在Quartus II環境下對改進的暗原色先驗算法進行綜合，選擇Altera 的EP2C70F672I8 芯片，輸入圖像為8 位，大小為720×576。表1 為選取不同窗口大小時，引導濾波的資源使用量和能達到的最大工作頻率。表2給出了暗原色先驗算法的處理實驗數據，其中引導濾波器選擇窗口大小為5×5，局部暗原色窗口大小為7×7。

表1 引導濾波器的資源需求

表2 暗原色先驗算法的資源需求

如表1 所示，一方面，隨著窗口大小加倍LEs 的使用量基本不變，Memory 的使用量增加，相應的平滑效果也得到提升；另一方面，即使窗口大小加倍，系統最大工作頻率仍可達到110 MHz，能夠達到實時性需求。

從表2可以看出，整個算法LEs和Memory的使用量不高，系統最高頻率可達107 MHz，每個時鐘周期處理一個像素，處理速度可達240 f/s，完全滿足實時處理的要求。

圖9 給出了FPGA 實現的效果。圖（a）和圖（b）是原始圖像，圖（c）和圖（d）是在FPGA 上實現的暗原色先驗算法結果，圖（e）和圖（f）是在MATLAB 實現的暗原色先驗處理結果。從圖（c）和圖（d）可以看出，經過FPGA 的處理，能夠達到去霧的效果，圖像細節部分得到明顯增強，而且基本上不存在光暈偽影。將（e）、（f）與（c）、（d）的各個像素值作差，絕對值最大為2，則FPGA 處理精度上的誤差不大于2/255 ≈0.8%，屬于舍去誤差，可滿足實際處理需求。

圖9 實驗結果對比圖

6 總結

由前文所述，暗原色先驗算法理論在圖像去霧方面取得了較好的效果，但暗原色先驗算法中軟摳圖部分計算復雜度高，無法滿足實際應用需求。文中用引導濾波器代替軟摳圖，并提出了引導濾波器的快速計算方法，不僅可以實現在軟件上的加速，而且在硬件實現上更加符合流水特性，可應用于嵌入式系統的前端，實現各種實時圖像處理功能。綜合結果表明，在CycloneII系列FPGA上系統最大可運行頻率達到107 MHz，每秒能夠處理1 024×1 024大小的圖像100幀，完全能滿足實時性要求。

[1] He Kaiming，Sun Jian，Tang Xiaoou.Single image haze removal using dark channel prior[J].IEEE Trans on PAMI，2011，33（12）：2341-2353.

[2] 楊靖宇，張永生，鄒曉亮，等.利用暗原色先驗知識實現航空影像快速去霧[J].武漢大學學報，2010，35（11）：1292-1295.

[3] 龐春穎，嵇曉強，孫麗娜，等.一種改進的圖像快速去霧新方法[J].光子學報，2013，42（7）：872-877.

[4] Xu Haoran，Guo Jianming，Liu Qing，et al.Fast image dehazing using improved dark channel prior[C]//Proceedings of International Conference on Information Science and Technology（ICIST），Hubei，China，2012.

[5] Sun Kang，Wang Bo，Zheng Zhihui，et al.Fast Single Image Dehazing Using Iterative Biateral Filter[C]//Proceedings of Information Engineering and Computer Science（ICIECS），Wuhan，China，2010.

[6] 蔡超，丁明躍，周成平，等.小波域中的雙邊濾波[J].電子學報，2004，16（1）：128-131.

[7] 范彥革，劉旭敏，陳婧.各向異性擴散和雙邊濾波關系的研究[J].微計算機信息，2006（10）：245-247.

[8] Paris S，Durand F.A fast approximation of the bilateral filter using a signal processing approach[C]//Proceedings of European Conference on Computer Vision，Graz，Austria，2006.

[9] Elad M.On the origin of the bilateral filter and ways to improve it[J].IEEE Transactions on Image Processing，2002，11（10）：1141-1151.

[10] He Kaiming，Sun Jian，Tang Xiaoou.Guided image filtering[C]//Proceedings of European Conference on Computer Vision（ECCV），Heraklion，Crete，Greece，2010.

[11] 高清遠，李學初.自適應濾波器的FPGA 實現[J].電子測量與儀器學報，2005，19（1）：25-29.

[12] 靖固，劉璐楊，于曉洋.基于FPGA 多變量模糊神經網絡控制器設計[J].哈爾濱理工大學學報，2011，16（2）：44-48.

[13] 胡同花，周維龍.基于FPGA的OFDM調制器設計與實現[J].電子設計工程，2011，19（15）：139-141.

[14] 張立，張光新，柴磊，等.FPGA 在多功能計費器系統中的應用[J].儀器儀表學報，2005，26（8）：735-737.

[15] McCartney E J.Optics of atmosphere：Scattering by molecoles and particles[M].New York：John Wiley and Sons，1976：23-30.