呂偉新 ，李清清，婁俊嶺

(1.哈爾濱工業(yè)大學(xué)機(jī)器人研究所，哈爾濱150001;2.哈爾濱工業(yè)大學(xué)機(jī)器人研究所，哈爾濱150001;3.哈爾濱工業(yè)大學(xué)機(jī)器人研究所，哈爾濱150001)

排序是將一個(gè)集合中的所有元素按序排列成一個(gè)新的有序數(shù)列的運(yùn)算，其應(yīng)用范圍很廣，如用于構(gòu)造中值運(yùn)算器，最大值運(yùn)算器，最小值運(yùn)算器等。國內(nèi)外學(xué)者一直致力于提高運(yùn)算速度的研究，曾提出了利用多種軟件實(shí)現(xiàn)快速排序的算法［1－3］。硬件邏輯電路具有并行運(yùn)算的特點(diǎn)，用其實(shí)現(xiàn)排序算法能極大提高運(yùn)算速度，適合于信號(hào)和圖像處理等實(shí)時(shí)性要求比較高的場合［4－7］。

本文提出了一種將輸入數(shù)據(jù)按行列構(gòu)成矩陣比較器，其比較結(jié)果的第j 行輸出值之和即為第j 個(gè)輸入數(shù)據(jù)在一個(gè)集合中的序列值的排序方法。相對(duì)其他算法，F(xiàn)PGA 實(shí)現(xiàn)此方法原理簡單，運(yùn)算速度快。除可作為排序器外，本文將此方法應(yīng)用于構(gòu)造一維和二維中值濾波器，具有廣泛的應(yīng)用價(jià)值。

1 比較矩陣排序器原理

排序問題可以描述為:輸入一個(gè)長度為N 的集合{xi，1≤i≤N}，若升序排列，則輸出一個(gè)長度為N的序列{Yi，1≤i≤N 且Yi≤Yi+1};若降序排列，則輸出一個(gè)長度為N 的序列{Yi，1≤i≤N 且Yi≥Yi+1}。升序排列和降序排列運(yùn)算方法基本相同，這里只討論按升序排列的情況，將要實(shí)現(xiàn)排序的集合中的數(shù)據(jù)分為兩種情況:

(1)各數(shù)據(jù)互不相等

此時(shí)，已知x(1)，x(2)，x(3)…x(N)，求其中某一個(gè)數(shù)x(j)在整個(gè)集合按從小到大排序后的序列值，可使它與其他的所有數(shù)據(jù)依次做比較，若大于被比較的數(shù)據(jù)，則比較的結(jié)果記為1，否則記為0，可知將所有比較結(jié)果中1 的個(gè)數(shù)相加即為x(j)在這個(gè)集合中的序列值。

(2)數(shù)據(jù)中有相同值

此時(shí)，添加約束條件，將相等的數(shù)據(jù)做排序修正，下標(biāo)較小的數(shù)據(jù)其值較大。如若x(k)= x(m)=x(n)=…，k＜m＜n＜…則認(rèn)為x(k)＞x(m)＞x(n)＞….，這樣就可以將集合中相同的數(shù)據(jù)在排序中按順序排列，而不會(huì)影響最終的排序結(jié)果。

基于以上兩種情況的分析，可用式(1)描述如下:

其中Judge(j)(i)為x(j)與x(i)比較的結(jié)果值。則x(j)在集合從小到大排序后的序列值為:

上述排序過程可用圖1 中的比較矩陣更直觀地表述，圖1 中輸入數(shù)據(jù)x(1)，x(2)，x(3)…x(N)在方格左側(cè)從上到下依次排列，再將輸入數(shù)據(jù)在方格的上側(cè)從左到右依次排列，行列值相比較構(gòu)成比較矩陣。去除從左上到右下的對(duì)角線上的數(shù)據(jù)，左下角斜杠紋理區(qū)域中的數(shù)據(jù)滿足x(j)＞x(i)條件時(shí)，判斷結(jié)果為1;右上角交叉紋理區(qū)域中的數(shù)據(jù)滿足x(j)≥x(i)條件時(shí)，判斷結(jié)果為1，則第j 行的所有比較值累加后，即為x(j)的序列值Order(j)。

圖1 排序器比較矩陣原理

該排序算法易于理解，運(yùn)算速度快，信號(hào)從輸入到輸出之間的硬件電路對(duì)稱性好，并行處理能力強(qiáng)，是一種簡單可靠的排序方法。構(gòu)造的比較矩陣總共需做N×(N－1)次比較運(yùn)算。并行處理構(gòu)造比較器矩陣，雖耗用了一定的硬件資源，但換取了運(yùn)算速度的提高。

2 比較矩陣排序器的FPGA 實(shí)現(xiàn)

2.1 排序器各子模塊的FPGA 實(shí)現(xiàn)

根據(jù)比較矩陣排序器的原理繪制的FPGA 實(shí)現(xiàn)框圖如圖2 所示，框圖中需要用到比較矩陣模塊、加法器模塊和多路判斷選通器模塊。圖2 中左側(cè)x(j)，1≤j≤N 為要進(jìn)行排序的數(shù)據(jù)，經(jīng)比較矩陣比較后，以第j 行的矩陣輸出為例，比較值為Judge(j)(i)，1≤i≤N 且i≠j，然后將第j 行輸出的比較結(jié)果值在加法器模塊中相加得Order(j)，然后在多路判斷選通器中，判斷此值并選通x(j)與Y(Order(j)+1)之間的硬件連接。

圖2 FPGA 實(shí)現(xiàn)框圖

2.1.1 FPGA 實(shí)現(xiàn)的各組成模塊介紹

(1)比較矩陣模塊。

比較矩陣是將輸入的數(shù)據(jù)按行列排布之后按圖1 所示排序過程進(jìn)行比較，比較矩陣中右上角數(shù)據(jù)的比較運(yùn)算使用大于等于二值比較器A_DE_B 子模塊，子模塊中A、B 兩值比較，若A≥B，則輸出1，否則輸出0;比較矩陣中左下角數(shù)據(jù)的比較運(yùn)算使用大于二值比較器A_D_B 子模塊，子模塊中A、B兩值比較，若A＞B，則輸出1，否則為0。將比較的結(jié)果作為加法器的輸入數(shù)據(jù)。

A_DE_B 子模塊Verilog 關(guān)鍵代碼為:

“assign out=(A＞=B)?1‘b1:1’b0;”

A_D_B 子模塊Verilog 關(guān)鍵代碼為:

“assign out=(A＞B)?1‘b1:1’b0;”

代碼中，A，B 為多bit 輸入信號(hào)，out 為1bit 比較矩陣輸出結(jié)果值信號(hào)。

(2)加法器模塊。

此模塊將比較矩陣一行輸出的值相加，以5 輸入數(shù)據(jù)為例，加法器模塊ADD，其Verilog 關(guān)鍵代碼為:

assign out=((IN1+IN2)+(IN3+IN4));

其中，IN1，IN2，IN3，IN4 為比較矩陣一行輸出結(jié)果值，out 為相加之后的3 bit 結(jié)果輸出。

(3)多路判斷選通器模塊。

此模塊對(duì)每一路加法器的輸出值進(jìn)行判斷，選通x(j)與Y(Order(j)+1)之間的硬件連接。實(shí)現(xiàn)5輸入數(shù)據(jù)多路選通器SelectData_Order5 模塊輸出值之一Y(j)的判斷選通，Verilog 關(guān)鍵代碼為:

assign Outj=(Sel1==j－1)?A1:8＇hzz;

assign Outj=(Sel2==j－1)?A2:8＇hzz;

assign Outj=(Sel3==j－1)?A3:8＇hzz;

assign Outj=(Sel4==j－1)?A4:8＇hzz;

assign Outj=(Sel5==j－1)?A5:8＇hzz;

其中，A1，A2，A3，A4，A5 為要實(shí)現(xiàn)排序的5 個(gè)輸入數(shù)據(jù)。Outj 為排序后的第j 路輸出。Sel1，Sel2，Sel3，Sel4，Sel5 為各加法器模塊輸出的信號(hào)。

(4)各子模塊之間的連接。

將上述模塊按照?qǐng)D2 所示結(jié)構(gòu)連接起來，就可構(gòu)造硬件排序器。以5 數(shù)據(jù)輸入排序器為例，在Altera 公司的QuartusⅡ開發(fā)工具中的模塊連接框圖如圖3 所示，圖3(a)中左側(cè)為輸入的5 個(gè)數(shù)據(jù)輸入Data_A，矩陣模塊MatrixOut5 進(jìn)行行列比較后輸出到4 值相加模塊ADD4，經(jīng)SelectData_Order5 判斷選通后輸出排序結(jié)果Data_Out。

圖3 比較矩陣排序器模塊連接框圖

2.1.2 FPGA 時(shí)序仿真分析

在Quartus Ⅱ仿真軟件中，對(duì)5 數(shù)據(jù)輸入排序器進(jìn)行編譯，然后使用波形仿真工具驗(yàn)證其排序邏輯，其波形仿真如圖4 所示，圖中Data_A 為數(shù)據(jù)輸入，Data_OUT 為排序輸出，輸入數(shù)據(jù)變換為不同值時(shí)，輸出值的情況如圖4 中所示。

從圖4 中可以看出，由于門級(jí)電路的延遲時(shí)間不同，經(jīng)過一段短暫的數(shù)據(jù)競爭之后，達(dá)到穩(wěn)定，輸出值即為從小到大的正確排序。

本文選用了Altera 公司的EP2C20 芯片，具有18752 個(gè)邏輯單元，設(shè)計(jì)多種不同輸入數(shù)據(jù)個(gè)數(shù)的排序器，將其耗用資源大小、最大仿真延時(shí)和占用總資源大小列于表1。

表1 不同類型排序器的仿真指標(biāo)

從表1 中可以看出，耗用邏輯單元呈指數(shù)增長，但時(shí)間延遲增長很少，而且是幾十ns 級(jí)的延時(shí)，計(jì)算速度很快，在實(shí)際應(yīng)用中很有應(yīng)用價(jià)值。

3 比較矩陣排序器實(shí)現(xiàn)中值濾波

中值濾波，算法簡單且對(duì)椒鹽噪聲的濾波效果非常好，經(jīng)常被使用于數(shù)字圖像處理當(dāng)中。中值濾波中最關(guān)鍵的是排序算法，軟件處理時(shí)，傳統(tǒng)的排序方法是冒泡法，軟件實(shí)現(xiàn)容易，但時(shí)間復(fù)雜度高，采用快速中值濾波算法［8］可以減少計(jì)算的次數(shù)，但仍不能滿足高速圖像處理的要求。使用硬件電路實(shí)現(xiàn)中值濾波，利用其并行處理特性，速度可以成倍提高，很多人研究了中值濾波的硬件實(shí)現(xiàn)方法［9－12］，但大多算法復(fù)雜，在實(shí)現(xiàn)二維中值濾波功能時(shí)，忽略了對(duì)一維快速排序硬件實(shí)現(xiàn)問題的研究。

一維快速排序是解決多維快速排序的基礎(chǔ)，將本文提出的硬件矩陣比較器用于實(shí)現(xiàn)中值濾波器，算法原理簡單，當(dāng)窗口尺寸增加時(shí)，其運(yùn)算速度基本保持不變。

中值濾波是將一個(gè)數(shù)據(jù)集合中的中間值作為其輸出值，可用式(3)表述如下:

其中N 為數(shù)據(jù)集合的大小，media 方法為取集合排序后的中值，x 為集合元素，y 為集合中值輸出結(jié)果。

3.1 構(gòu)造一維中值濾波器

從式(2)所示排序器序列值求解原理中可知，若Order(j)=floor(N/2)，其中floor 為取小于或等于括號(hào)中表達(dá)式的最大整數(shù)，則x(j)即為集合的中值，因此在多路判斷選通模塊中，判斷各行數(shù)據(jù)加法器的值是否與floor(N/2)相等，模塊的輸出通道中只保留中間的輸出通道，去除其他的排序通道，即可實(shí)現(xiàn)中值輸出，F(xiàn)PGA 實(shí)現(xiàn)一維中值濾波器框圖如圖5 所示。

圖5 FPGA 實(shí)現(xiàn)一維中值濾波器框圖

在QuartusⅡ仿真軟件中，設(shè)計(jì)8 位寬5 數(shù)據(jù)輸入中值濾波器，其波形仿真如圖6 所示，圖中Data_A 為輸入數(shù)據(jù)，經(jīng)過一段時(shí)間后變換5 個(gè)輸入數(shù)據(jù)的值，輸出數(shù)據(jù)Data_OUT 穩(wěn)定后，輸出了準(zhǔn)確的中值結(jié)果。

圖6 一維5 數(shù)據(jù)輸入中值濾波器波形仿真圖

依據(jù)上述方法，選用Altera 公司的EP2C20 芯片，設(shè)計(jì)不同輸入數(shù)據(jù)個(gè)數(shù)的中值濾波器，對(duì)比不同類型一維中值濾波器的仿真指標(biāo)，如表2 所示。

表2 一維中值濾波器仿真指標(biāo)

通過5 個(gè)輸入數(shù)據(jù)、9 個(gè)輸入數(shù)據(jù)和25 個(gè)輸入數(shù)據(jù)的中值濾波器的比較可知，應(yīng)用本文排序器原理設(shè)計(jì)的一維中值濾波器，計(jì)算速度隨輸入數(shù)據(jù)個(gè)數(shù)的增多而增加較少，滿足大尺寸數(shù)據(jù)實(shí)時(shí)高速計(jì)算的要求。

一維中值濾波器是只使用排序器的一路輸出，因而各個(gè)數(shù)據(jù)之間的競爭較少，達(dá)到穩(wěn)定的時(shí)間更快些。

窗口尺寸太大時(shí)將占用較多硬件邏輯資源，因此在二維窗口尺寸小于5×5 時(shí)，可以將二維中值濾波變?yōu)橐痪S中值濾波計(jì)算;其他不同窗口形狀的中值濾波計(jì)算也可以變?yōu)橐痪S數(shù)據(jù)求中值問題，使用本文一維中值濾波器構(gòu)造方法解決。

3.2 構(gòu)造二維中值濾波器

將本文提出的硬件排序器方法，與文獻(xiàn)［11］和文獻(xiàn)［12］提出的二維快速中值方法結(jié)合起來，通過流水線技術(shù)，設(shè)計(jì)二維方窗中值濾波器，可以得到快速而準(zhǔn)確的中值濾波結(jié)果。下文以5×5 窗口中值濾波器為例，介紹其應(yīng)用方法。

根據(jù)文獻(xiàn)［11］和文獻(xiàn)［12］所述的二維5×5 窗口中值濾波器計(jì)算過程如圖7 所示，圖中有圓圈的方格為25 數(shù)據(jù)中所有要進(jìn)行排序的數(shù)據(jù)，一個(gè)箭頭穿過的方格為一個(gè)排序集合，箭頭所指的方向?yàn)榕判蚝笥尚〉酱蟮呐帕蟹较?。二維5×5 窗口中值濾波計(jì)算要經(jīng)過4 步:第1 步，對(duì)所有列排序;第2 步，對(duì)所有行排序;第3 步，從中心開始三個(gè)45 度對(duì)角線上的數(shù)據(jù)排序;第4 步，從中心開始錯(cuò)2 格的右上斜對(duì)角線上的數(shù)據(jù)排序。經(jīng)過上述排序后，圖7(d)中帶交叉線陰影圓圈所示的中心方格數(shù)據(jù)即為中值輸出。

圖7 二維5×5 窗口中值濾波器

圖7所示5×5 窗口中值濾波器，在FPGA 實(shí)現(xiàn)時(shí)，在第1 步和第2 步中需要用到5 輸入數(shù)據(jù)排序器模塊;在第3 步中需要用到4 輸入數(shù)據(jù)取最小值模塊、4 輸入數(shù)據(jù)取最大值模塊和5 輸入數(shù)據(jù)取中值模塊，輸出值如圖7(c)中帶交叉線陰影圓圈的方格所示;在第4 步中，需要用到3 輸入數(shù)據(jù)取中值模塊。FPGA 模塊連接框圖，如圖8 所示。

圖8 二維5×5 方窗中值濾波器FPGA 模塊連接框圖

依據(jù)二維中值濾波器的構(gòu)造方法，同樣可以構(gòu)造其他窗口尺寸的中值濾波器。在EP2C20 芯片中設(shè)計(jì)3×3 窗口二維中值濾波器和5×5 窗口二維中值濾波器，經(jīng)波形仿真可以輸出正確的中值，對(duì)比此兩種中值濾波器的仿真指標(biāo)，如表3 所示。

表3 二維中值濾波器仿真指標(biāo)

從表3 中可以看出，二維中值濾波窗口尺寸在5×5及以上時(shí)，耗用資源比將二維窗口轉(zhuǎn)化為一維求中值方法要少，窗口尺寸越大此優(yōu)勢越明顯，但伴隨著整體延時(shí)相比一維要稍大一些。本文實(shí)現(xiàn)方法與文獻(xiàn)［11］中實(shí)現(xiàn)二維中值濾波器耗用資源相比，在5×5 窗口下差不多，在3×3 下則耗用資源明顯較少。

4 結(jié)論

本文提出的比較矩陣排序法，其矩陣比較結(jié)果的第j 行輸出值之和即為第j 個(gè)輸入數(shù)據(jù)在輸入數(shù)據(jù)集合中的序列值，原理簡單，硬件容易實(shí)現(xiàn)。使用EP2C20 芯片實(shí)現(xiàn)基于比較矩陣排序方法的排序器，實(shí)現(xiàn)排序速度均在幾十ns 數(shù)量級(jí)。除作為排序器外，本文將此排序方法應(yīng)用于構(gòu)造一維和二維中值濾波器，經(jīng)仿真延時(shí)小于50 ns，雖犧牲了部分硬件資源，但保證了輸入數(shù)據(jù)個(gè)數(shù)增多后，運(yùn)算仍具有很高實(shí)時(shí)性，這在大規(guī)模集成芯片資源成倍增長的背景下是可取的。使用矩陣比較排序法構(gòu)造高速排序器和中值濾波器為進(jìn)一步提高信號(hào)采集、圖像處理等實(shí)時(shí)性提供了一種途徑。

［1］ 王秋芬，邵艷玲.一種新的基于哈希函數(shù)的排序算法［J］.計(jì)算機(jī)與現(xiàn)代化，2010，(10):47－49.

［2］ 湯亞玲，秦鋒.高效快速排序算法研究［J］. 計(jì)算機(jī)工程，2011，37(6):77－78.

［3］ 秦玉平，馬靖善. 一種改進(jìn)的計(jì)數(shù)排序算法［J］. 渤海大學(xué)學(xué)報(bào)，2010，31(2):174－176.

［4］ 王敬美，楊春玲.基于FPGA 和UART 的數(shù)據(jù)采集器設(shè)計(jì)［J］.電子器件，2009，32(2):386－393.

［5］ 蔡學(xué)森，戴金波，李曉寧. 中值濾波與均值濾波法在條形碼去噪中的應(yīng)用［J］.長春師范學(xué)院學(xué)報(bào)，2008，27(4):40－42.

［6］ 申俊琦，胡繩蓀，馮勝強(qiáng). 自使用中值濾波在焊縫視覺跟蹤中的應(yīng)用［J］.焊接學(xué)報(bào)，2011，32(3):57－60.

［7］ Baker Z K，Gokhale M B，Tripp J L，et al.Matched Filter Computation on FPGA，Cell and GPU［J］. Field－Programmable Custom Computing Machines，2007. FCCM 2007 15th Annual IEEE Symposium，2007:207－216.

［8］ 李婧，黃進(jìn).一種圖像測量中的快速中值濾波算法［J］.微計(jì)算機(jī)信息，2007，23(7－3):299－300.

［9］ 葉巧文，林偉.基于折疊結(jié)構(gòu)的半帶濾波器的設(shè)計(jì)［J］.電子器件，2010，33(1):85－89.

［10］ 陳加成，徐熙平，吳瓊. 基于FPGA 的中值濾波算法研究與硬件設(shè)計(jì)［J］.長春理工大學(xué)學(xué)報(bào)，2008，31(1):8－14.

［11］ 張道德，胡新宇，楊光友. 基于模糊增強(qiáng)信息的圖像邊緣檢測改進(jìn)算法［J］.電子器件，2009，32(6):1118－1122.

［12］ Priyadarshan Kolte，Roger Smith，Wen Su.A Fast Median Filter Using AltiVec［C］//IEEE International Conference on Computer Design，1999:384－391.