呂偉新 ，李清清，婁俊嶺

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

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

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

1 比較矩陣排序器原理

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

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

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

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

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

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

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

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

圖1 排序器比較矩陣原理

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

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

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

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

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

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

(1)比較矩陣模塊。

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

A_DE_B 子模塊Verilog 關鍵代碼為:

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

A_D_B 子模塊Verilog 關鍵代碼為:

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

代碼中，A，B 為多bit 輸入信號，out 為1bit 比較矩陣輸出結果值信號。

(2)加法器模塊。

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

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

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

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

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

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 為要實現(xiàn)排序的5 個輸入數(shù)據(jù)。Outj 為排序后的第j 路輸出。Sel1，Sel2，Sel3，Sel4，Sel5 為各加法器模塊輸出的信號。

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

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

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

2.1.2 FPGA 時序仿真分析

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

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

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

表1 不同類型排序器的仿真指標

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

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

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

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

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

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

3.1 構造一維中值濾波器

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

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

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

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

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

表2 一維中值濾波器仿真指標

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

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

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

3.2 構造二維中值濾波器

將本文提出的硬件排序器方法，與文獻［11］和文獻［12］提出的二維快速中值方法結合起來，通過流水線技術，設計二維方窗中值濾波器，可以得到快速而準確的中值濾波結果。下文以5×5 窗口中值濾波器為例，介紹其應用方法。

根據(jù)文獻［11］和文獻［12］所述的二維5×5 窗口中值濾波器計算過程如圖7 所示，圖中有圓圈的方格為25 數(shù)據(jù)中所有要進行排序的數(shù)據(jù)，一個箭頭穿過的方格為一個排序集合，箭頭所指的方向為排序后由小到大的排列方向。二維5×5 窗口中值濾波計算要經(jīng)過4 步:第1 步，對所有列排序;第2 步，對所有行排序;第3 步，從中心開始三個45 度對角線上的數(shù)據(jù)排序;第4 步，從中心開始錯2 格的右上斜對角線上的數(shù)據(jù)排序。經(jīng)過上述排序后，圖7(d)中帶交叉線陰影圓圈所示的中心方格數(shù)據(jù)即為中值輸出。

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

圖7所示5×5 窗口中值濾波器，在FPGA 實現(xiàn)時，在第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ù)二維中值濾波器的構造方法，同樣可以構造其他窗口尺寸的中值濾波器。在EP2C20 芯片中設計3×3 窗口二維中值濾波器和5×5 窗口二維中值濾波器，經(jīng)波形仿真可以輸出正確的中值，對比此兩種中值濾波器的仿真指標，如表3 所示。

表3 二維中值濾波器仿真指標

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

4 結論

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

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

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

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

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

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

［6］ 申俊琦，胡繩蓀，馮勝強. 自使用中值濾波在焊縫視覺跟蹤中的應用［J］.焊接學報，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］.微計算機信息，2007，23(7－3):299－300.

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

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

［11］ 張道德，胡新宇，楊光友. 基于模糊增強信息的圖像邊緣檢測改進算法［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.