基于排序網(wǎng)絡(luò)的高效中值濾波方法

Vivado的高層次綜合功能將幫助您為嵌入式視頻應(yīng)用設(shè)計更好的排序網(wǎng)絡(luò)。

從汽車到安全系統(tǒng)再到手持設(shè)備，如今采用嵌入式視頻功能的應(yīng)用越來越多。每一代新產(chǎn)品都需要更多的功能和更好的圖像質(zhì)量。但是，對于一些設(shè)計團(tuán)隊來說，實現(xiàn)高質(zhì)量的圖像并非易事。

作為賽靈思的一名DSP設(shè)計現(xiàn)場應(yīng)用工程師，我經(jīng)常被問到有關(guān)IP和高效視頻濾波實現(xiàn)方法這方面的問題。我發(fā)現(xiàn)利用最新Vivado?設(shè)計套件的高層次綜合(HLS)功能，很容易在任何賽靈思7系列All Programmable器件中實現(xiàn)基于排序網(wǎng)絡(luò)的高效中值濾波方法。

在詳細(xì)探討該方法之前，我們先來回顧一下設(shè)計人員在圖像完整性方面所面臨的一些挑戰(zhàn)以及解決這些問題常用的濾波技術(shù)。

數(shù)字圖像噪聲大多出現(xiàn)在系統(tǒng)獲取或傳輸圖像的過程中。例如，掃描儀或數(shù)碼相機(jī)的傳感器和電路可以產(chǎn)生幾種類型的不規(guī)則噪聲。通信通道中的隨機(jī)比特錯誤或模數(shù)轉(zhuǎn)換器錯誤會導(dǎo)致特別麻煩的“脈沖噪聲”。這種噪聲經(jīng)常被稱為胡椒鹽(salt-and-pepper)噪聲，因為它以隨機(jī)白點或黑點的形式出現(xiàn)在顯示器的圖像表面，嚴(yán)重降低了圖像質(zhì)量（圖1）。

為降低圖像噪聲，視頻工程師通常會在設(shè)計中應(yīng)用空間濾波器。這些濾波器利用噪聲點周圍像素的優(yōu)質(zhì)特性或數(shù)值對圖像中渲染較差的像素進(jìn)行替換或加強(qiáng)?？臻g濾波器主要分為線性和非線性兩種。最常用的線性濾波器被稱為均值濾波器。它用鄰近像素的均值替換每個像素值。這樣，渲染較差的像素就可根據(jù)圖像中其它像素點的平均值得到改善。均值濾波器能以低通方式快速去除圖像噪聲。但是，該方式通常伴有副作用——使整體圖像的邊緣變得模糊。

大多數(shù)情況下，非線性濾波法比線性均值濾波法更好。非線性濾波特別善于消除脈沖噪聲。最常用的非線性濾波器是次序統(tǒng)計濾波器。而最受歡迎的非線性次序統(tǒng)計濾波器是中值濾波器。

中值濾波器廣泛用于視頻與圖像處理，因為此種濾波器具有出色的降噪能力，而且模糊程度比相同尺寸的線性平滑濾波器低得多。與均值濾波器類似，中值濾波器也要依次分析圖像中的每個像素，并觀察其鄰近的像素以判定該像素是否能代表其周圍像素。但是，中值濾波器并非簡單地將像素值用周圍像素的平均值進(jìn)行替換，而是用周圍像素值的中值來替換。由于中值必須是鄰近某個像素的實際值，因此中值濾波器在跨越邊緣時不會創(chuàng)建新的虛擬像素值（避免了均值濾波器的邊界模糊影響）。因此，中值濾波器在保留銳邊方面比其它任何濾波器做得都要好。這種濾波器在計算中值時，首先將周圍窗口中的所有像素值按數(shù)值大小順序進(jìn)行排序，然后用中間像素值替換待過濾的像素（如果待計算區(qū)域包含偶數(shù)個像素，那么使用中間兩個像素的平均值）。

例如，假設(shè)一個3x3像素窗口以值為229的像素為中心，該窗口值如下
39 83 225
5 229 204
164 61 57

我們可以對像素進(jìn)行排序，獲得順序列表為5 39 57 61 83 164 204 225 229。

中值就是位于中間的像素值，即83。在輸出圖像中用該值替代初始值229。圖2表明在圖1噪聲輸入圖像中應(yīng)用3x3中值濾波器后的效果。待過濾像素周圍的窗口越大，濾波效果越顯著。

中值濾波器具備出色的降噪能力，因此也被廣泛應(yīng)用于掃描速率視頻轉(zhuǎn)換系統(tǒng)的內(nèi)插級，例如為實現(xiàn)隔行視頻信號而將場速率從50Hz轉(zhuǎn)換為100Hz的運動補(bǔ)償內(nèi)插程序，或者隔行至逐行轉(zhuǎn)換中的邊緣定向內(nèi)插程序。如欲了解有關(guān)中值濾波器更詳盡的介紹，有興趣的讀者可以參考 [1]和 [2]。

在運用中值濾波器時最為關(guān)鍵的是確定使用哪種排序方法，以獲得用來生成每個輸出像素的像素排序列表。排序過程需要大量計算時鐘周期。

目前，賽靈思在Vivado設(shè)計套件中可提供高層次綜合。我通常會告訴人們，可以根據(jù)排序網(wǎng)絡(luò)概念在C語言中運用一種簡單而有效的方法來設(shè)計中值濾波器。我們可使用Vivado HLS [3]來獲得Zynq?-7000 All Pro-grammableSoC的FPGA架構(gòu)的實時性能 [4]。

下面的內(nèi)容里，我們假設(shè)圖像格式是每像素8位，每行1,920像素，每幀1,080行，幀速率為60Hz，因此最小像素速率至少為124MHz。不過，為了設(shè)置一些設(shè)計難度，我將要求Vivado HLS工具提供200MHz的目標(biāo)時鐘頻率，如果得到比124MHz更大的頻率值效果會更好（由于實際視頻信號中還包含空白數(shù)據(jù)，因此時鐘速率比活動像素所要求的速率高）。

什么是排序網(wǎng)絡(luò)？
排序是指將陣列中的元素按照升序或降序的方式重新進(jìn)行排列的過程。排序是很多嵌入式計算系統(tǒng)中最重要的操作之一。

由于排序在眾多應(yīng)用中起到關(guān)鍵作用，因此很多科學(xué)文獻(xiàn)中的大量文章都對眾所周知的排序方法的復(fù)雜性和速度進(jìn)行了分析，例如冒泡排序、希爾排序、歸并排序和快速排序。對于大數(shù)據(jù)集來說快速排序是速度最快的排序算法 [5]，而冒泡排序是最簡單的。通常，所有這些技術(shù)都應(yīng)該以軟件任務(wù)的形式在RISC CPU上運行，而且每次只執(zhí)行一個對比。它們的工作負(fù)載不是恒定的，而是取決于有多少輸入數(shù)據(jù)已部分排序。例如，需要對一套N個樣本進(jìn)行排序，假設(shè)快速排序的計算復(fù)雜性在最差、一般和最好的情況下分別是N2、NlogN和NlogN。同時，冒泡排序的復(fù)雜性分別是N2、N2和N。不得不承認(rèn)我還尚未發(fā)現(xiàn)關(guān)于此類復(fù)雜性數(shù)字的統(tǒng)一觀點。但在我讀過的有關(guān)此問題的所有文章中似乎都贊同一個觀點，那就是計算某種排序算法的復(fù)雜性并不簡單。這本身似乎成為了尋找備選方案的主要原因。

在進(jìn)行圖像處理時，我們需要在排序方法上獲得確定的行為，以便以恒定的吞吐量產(chǎn)生輸出圖片。因此，上述算法都無法成為采用Vivado HLS的FPGA設(shè)計的理想備選方案。

排序網(wǎng)絡(luò)可通過使用并列執(zhí)行實現(xiàn)更快的運行速度。排序網(wǎng)絡(luò)的基礎(chǔ)構(gòu)成模塊是比較器。比較器是一種簡單組件，能對a和b兩個數(shù)據(jù)進(jìn)行排序，然后將最大值和最小值分別輸出到頂部和底部輸出結(jié)果中，必要時還可進(jìn)行交換。排序網(wǎng)絡(luò)對于經(jīng)典排序算法的優(yōu)勢在于比較器的數(shù)量在給定輸入數(shù)量下是固定的。因此，排序網(wǎng)絡(luò)在FPGA硬件中易于實現(xiàn)。圖3舉例說明了一個針對五個樣本的排序網(wǎng)絡(luò)（采用賽靈思System Generator生成[6]）。需要注意到的是處理延遲正好是五個時鐘周期，且與輸入樣本數(shù)值無關(guān)。此外還應(yīng)注意到右側(cè)的五個并行輸出信號包含排序后的數(shù)據(jù)，其中最大值在頂部，最小值在底部。

在C語言中通過排序網(wǎng)絡(luò)實現(xiàn)中值濾波器是很簡單的，如圖4中的代碼所示。Vivado HLS指令被嵌入到C語言代碼自身內(nèi)(#pragma HLS)。Vivado HLS只需要兩個優(yōu)化指令即可生成最佳RTL代碼。首先是利用1的初始間隔 (II)將整個函數(shù)流水線化，使輸出像素速率等于FPGA時鐘速率。第二步優(yōu)化是將像素窗口重新劃分為單獨的寄存器，以便同步并行訪問所有數(shù)據(jù)，從而提高帶寬。

頂層函數(shù)
圖5中的代碼段是中值濾波器的初級實現(xiàn)，我們將其作為參考。最里面的回路已進(jìn)行流水線化處理，以便在任何時鐘周期內(nèi)都能生成一個輸出像素。為了生成延遲估計報告，我們需要利用TRIPCOUNT指令通知Vivado HLS編譯器有關(guān)回路L1和L2中可能出現(xiàn)的迭代次數(shù)，因為它們是“不受控”的。也就是說，假設(shè)該設(shè)計可在運行期間處理低于最大允許分辨率為1,920 x 1,080像素的圖像分辨率，這些環(huán)路的極限值就是圖片的高度和寬度，而這兩個值在編譯期間都是未知的。

在C語言代碼中，待濾波的像素窗口可訪問圖像中不同的行。因此，利用存儲器位置來降低存儲帶寬需求的優(yōu)勢比較有限。盡管Vivado HLS可對代碼進(jìn)行綜合，但吞吐量并未達(dá)到最優(yōu)值，如圖6所示?；芈稬1_L2的初始化間隔（最里面回路L2完全展開的結(jié)果，由HLS編譯器自動執(zhí)行）為五個時鐘周期，而非一個，因此得到的輸出數(shù)據(jù)速率無法支持實時性能。從整個函數(shù)的最大延遲中也能明確這一點。在一個5納秒的目標(biāo)時鐘周期中，用來計算輸出圖像的周期數(shù)量為10,368,020，這意味著幀速率為19.2Hz而非60Hz。正如參考文獻(xiàn)[7]中詳細(xì)描述的，Vivado HLS設(shè)計人員必須明確地將視頻線路緩沖器的行為代碼寫入用于生成RTL的C語言模型中，因為HLS工具無法自動將新存儲器插到用戶代碼中。

全新的頂層函數(shù)C語言代碼如圖8所示。由于當(dāng)前的像素坐標(biāo)（行，列）顯示為in_pix[r][c]，因此需在坐標(biāo)(r-1, c-1)中的待濾波輸出像素周圍創(chuàng)建一個滑動窗口。對于3x3大小的窗口，其結(jié)果是out_pix[r-1][c-1]。需要注意到的是當(dāng)窗口尺寸為5x5或7x7的時候，輸出像素坐標(biāo)分別為(r-2, c-2)和(r-3, c-3)。靜態(tài)陣列線路_緩沖器可存儲KMED視頻線路數(shù)量等同于中值濾波器中垂直樣本的數(shù)量（當(dāng)前情況下的數(shù)量為3個）；而且由于靜態(tài)C語言關(guān)鍵字的原因，Vivado HLS編譯器可自動將內(nèi)容映射到FPGA雙端口Block RAM (BRAM)元件中。

這樣僅需很少的HLS指令就可實現(xiàn)實時性能。需對最里面的回路L2進(jìn)行流水線化處理，以便在任何時鐘周期內(nèi)都能生成一個輸出像素。輸入與輸出圖像陣列in_pix和out_pix被映射為RTL中的FIFO流接口。將該線路_緩沖器陣列劃分成多個KMED獨立陣列，以便Vivado HLS編譯器將每個陣列映射到獨立的雙端口BRAM中。由于這樣會有更多的可用端口，從而增加了載入/存儲操作次數(shù)（每個雙端口BRAM在每個周期內(nèi)能完成兩次載入或存儲操作）。圖7是Vivado HLS性能估算報告。目前，最大延遲為2,073,618個時鐘周期。在5.58ns的估計時鐘周期下，我們可以獲得86.4Hz的幀速率。這已超越了我們的需求值！回路L1_L2正如我們所希望的那樣得到II=1。應(yīng)注意到的是需要兩個BRAM以存放KMED線路緩沖存儲器。

利用高層次綜合進(jìn)行架構(gòu)探索
在我看來，Vivado HLS的最佳特性之一是能夠通過改變工具的優(yōu)化指令或C語言代碼本身這樣的方式來探索不同設(shè)計架構(gòu)并對性能進(jìn)行權(quán)衡，從而實現(xiàn)富有創(chuàng)造性的設(shè)計自由度。兩種操作方式都非常簡單而且并不耗時。

如果需要更大的中值濾波器窗口該怎么做？例如需要5x5而不是3x3的窗口尺寸。我們只需將KMED在C語言代碼中的定義從“3”變?yōu)椤?”，并再次運行Vivado HLS即可。圖9是單獨在3x3、5x5和7x7三種窗口尺寸情況下對中值濾波器例程進(jìn)行綜合所得到的HLS對比報告。在所有三種情況下，例程已完全流水線化 (II=1)，并且滿足目標(biāo)時鐘周期；延遲分別為9、25和49個時鐘周期，與人們對于排序網(wǎng)絡(luò)的預(yù)期表現(xiàn)相符。顯然，由于待排序的數(shù)據(jù)總量從9增至25甚至達(dá)到49，因此所使用的資源（觸發(fā)器和查找表）也相應(yīng)增加。

由于獨立函數(shù)已完全流水線化，因此頂層函數(shù)的延遲保持恒定，同時當(dāng)增大窗口尺寸的時候時鐘頻率會略有減小。到目前為止我們只討論了將Zynq-7000 All Programmable SoC作為目標(biāo)器件的這種情況，但采用Vivado HLS時我們可在相同項目中輕松嘗試不同目標(biāo)器件。例如，如果我們選用Kintex?-7 325T并對相同的3x3中值濾波器設(shè)計進(jìn)行綜合，所用的布局布線資源包括兩個BRAM、一個DSP48E、1,323個觸發(fā)器和705個查找表(LUT)，時鐘和數(shù)據(jù)速率為403MHz；而使用ZynqSoC器件時，則需使用兩個BRAM、一個DSP48E、751個觸發(fā)器和653個查找表，時鐘和數(shù)據(jù)速率為205MHz。

最后，如果我們想查看3x3中值濾波器處理每樣本為11位（而非8位）灰色圖像時的資源使用情況，我們可通過應(yīng)用ap_int C++類型來改變pix_t數(shù)據(jù)類型的定義，這樣就可規(guī)定任意位寬的定點數(shù)。我們只需通過啟動C語言預(yù)處理符號GRAY11就可重新編譯該項目。在這種情況下，ZynqSoC上的資源使用估算量為四個BRAM、一個DSP48E、1,156個觸發(fā)器和1,407個查找表。圖10給出了最后兩種情況的綜合估算報告。

短短數(shù)個工作日
此外，我們還可以看到，對于具有不同窗口尺寸甚至不同位數(shù)/像素的中值濾波器，生成時序和面積估算值到底有多簡單。尤其是在使用3x3 (或5x5)中值濾波器的情況下，由Vivado HLS自動生成的RTL只在ZynqSoC器件上占用很小面積（-1速度級），布局布線完成后，F(xiàn)PGA時鐘頻率為206（5x5版本為188）MHz，有效數(shù)據(jù)速率為206（或188）MSPS。

得到這些結(jié)果所需的總設(shè)計時間僅為五個工作日。其中大部分時間都用于構(gòu)建MATLAB?和C模型，而非運行Vivado HLS工具本身；后者所需時間不足兩個工作日。