基于指針排序的快速中值濾波算法研究

摘"要：為實現航空發動機控制系統采集信號的快速中值濾波，設計一種基于指針排序的快速中值濾波算法，將中值濾波過程分解為窗口數據更新和窗口數據中值求取兩個算法片段。針對窗口數據更新算法片段，提出一種環形數據窗口更新算法，通過指針指向平移實現數據窗口的滑動，縮短了窗口數據更新的耗時。針對窗口數據中值求取算法片段，提出一種基于指針排序的數據比較和移位算法，在運算內存開銷較小的情況下實現了窗口數據中值的快速求取。實驗結果表明：基于指針排序的快速中值濾波算法能夠在耗時減少的情況下，實現信號隨機噪聲的有效濾除。

關鍵詞：航空發動機；控制系統；中值濾波；指針；排序算法；快速排序

中圖分類號：TP274""文獻標志碼：B""文章編號：1671-5276（2024）02-0175-04

Research on Fast Median Filter Algorithm Based on Pointer Sorting

ZHANG Bo， ZHANG Jie， LUO Wei， ZHOU Yi

（Software Department of AECC Aero Engine Control System Institute，Wuxi 214063，China）

Abstract：In order to realize the fast median filtering of the signals collected by aeroengine control system，a fast median filtering algorithm based on pointer sorting is designed. The median filtering process is divided into two algorithm segments： updating window data and calculaiting the median of window data. For the algorithm segment of updating window data，an updated algorithm based on the ring data window is proposed， which realizes the sliding of the data window by translating the pointer， effectively shortening the time-consuming of updating the window data. For the algorithm segment of calculaiting the median of window data， a data comparison and shift algorithm based on pointer sorting is put forward， which achieves the rapid calculaition of the median value of window data with small computational memory overhead. The experimental results show that the fast median filtering algorithm can effectively filter the random noise of signals with less time consumption.

Keywords：aeroengine；control system；median filtering；pointer；sorting algorithm；quick sorting

0"引言

滑油液位傳感器用于航空發動機控制，由于航空發動機的工作環境比較惡劣，導致滑油液位信號會出現隨機噪聲干擾，干擾過大時會引起航空發動機的控制異常。基于發動機運行試驗統計分析，滑油液位信號的干擾類型為脈沖噪聲。中值濾波算法能夠有效去除隨機脈沖噪聲的影響并有效保留原始信號的細節信息，因此采用中值濾波算法對滑油液位信號進行濾波［1］。

傳統中值濾波算法主要針對窗口內的數據進行排序求取中值，因此傳統中值濾波算法的最小平均時間復雜度為O（nlog2n）。吳小培等［2］利用相鄰濾波窗口的數據關聯性，將相鄰2次中值濾波合并為1次進行，減少了中值濾波時間，但其平均時間復雜度為O（nlog2n），未根本解決中值濾波的效率問題。葉曉東等［3］對初次排序得到有序序列進行2次對分查找和內插，實現了時間復雜度為O（n）的算法，效率極大提升，但對分查找時直接使用數值比較相等，使得對浮點信號進行濾波時可能會出現風險。靳斌、朱冰蓮、鮑祥生、梅各各等［4-7］則是通過設計特定的數據結構，利用空間復雜度來換取時間復雜度的降低，最終實現了時間復雜度為O（n）的算法，但由于算法實現開辟了數個與濾波窗口長度相同的內存空間，使得濾波窗口長度增大時，內存消耗嚴重。

發動機控制分為定點型和浮點型兩種運算類型，其中浮點型運算明確禁止數值比較相等，且控制芯片對于運算速度和運算內存均有較高要求。因此，研究適用于任意數據類型、時間復雜度和空間復雜度均較低的快速中值濾波算法具有重要意義。

1"快速中值濾波算法原理

中值濾波算法的窗口通常表示為{B［0］， B［1］，…， B［2N］} ，窗口寬度為2N+1，通過窗口的滑動和窗口數據中值的求取實現中值的獲取。本文為分析方便，取窗口寬度為5，即N=2。

基于指針排序的快速中值濾波算法對窗口的滑動和窗口數據中值的求取進行優化。如圖1所示，定義環形窗口數組B = {B［0］， B［1］， B［2］， B［3］， B［4］}，將環形窗口數組中最老數據的數組索引定義為head用以指示最老的數據位置。圖1中B［3］為最老數據，head的值為3。定義指針數組P = { P［0］， P［1］， P［2］， P［3］， P［4］}，其中P［0］指向數值最大的元素，P［1］—P［4］依次有序指向數值更小的元素。

經過上述定義以后，假設已經得到如圖2所示的初始狀態有序窗口數組，其中head=3，并約定圖中虛線箭頭為當前步驟指針更新指向。

與窗口滑動進行數據更新的方式不同，當有數據更新時，如圖2中數據更新步驟所示，基于指針排序的快速中值濾波算法將最老位置的元素更新，即B［3］更新為600；在窗口數據中值求取結束后，將head更新為4。相比于窗口滑動進行數據更新的時間復雜度O（n），基于指針排序的快速中值濾波算法將數據更新的時間復雜度降低為O（1）。

基于指針排序的快速中值濾波算法求取窗口數據中值的過程如圖2中步驟1和步驟2所示。

步驟1遍歷指針數組P，獲取指向最新數據元素地址amp;B［3］的指針P［2］。

步驟2更新指針數組P的指針指向，實現窗口數組B中數據元素的排序，以圖2為例。

1）將窗口數組B最新元素B［3］600與P［1］指向的數據元素B［2］400進行比較，由于B［3］600大于B［2］400，因此，令P［2］指向數據元素B［2］400。

2）將窗口數組B最新元素B［3］600與P［0］指向的數據元素B［4］500進行比較，由于B［3］600大于B［4］500，因此，令P［1］指向數據元素B［4］500。

3）令P［0］指向數據元素B［3］600，重新獲得有序的指針數組P，中值即為P［N］指向的數值。

綜上，基于指針排序的快速中值濾波算法主要思路是通過對比最新元素與左側或右側指針所指向的數據元素大小，更改指針的指向，重新獲得有序的指針數組，最終求取窗口數組的中值。

2"快速中值濾波算法實現與復雜度分析

基于指針排序的快速中值濾波算法的數據更新過程復雜度為O（1），不再進行單獨分析。本節對求取窗口數據中值過程進行詳細分析。

如圖3所示，與算法原理對應，求取窗口數據中值過程分為步驟1、步驟2及返回中值等3個步驟，在進行算法復雜度分析時設n=2N+1。

步驟1遍歷指針數組，指針元素與amp; B［head］進行比較，如果相等則退出循環，此時循環因子i1為指向數組B最新元素的指針數組下標，即P［i1］指向數組B最新元素。算法語句最大頻度T（n）=2N+1，算法語句最小頻度T（n）=1，算法語句平均頻度T（n）=N+1，時間復雜度為O（n）。

步驟2根據P［i1］指向數值元素與左右指針指向數值元素的大小關系，向左或向右遍歷指針數組，變更指針的指向。算法語句最大頻度T（n）=4N+1，算法語句最小頻度T（n）=3，算法語句平均頻度T（n）=2N+2，時間復雜度為O（n）。

返回中值步驟僅對指針解引用獲取中值，算法語句最大頻度為T（n）=1，算法語句最小頻度T（n）=1，算法語句平均頻度T（n）=1，時間復雜度為O（1）。

通過上述算法分析，基于指針排序的中值濾波算法的算法語句最大頻度為T（n）=6N+3，算法語句最小頻度T（n）=5，算法語句平均頻度T（n）=3N+4，時間復雜度為O（n）。基于指針排序的中值濾波算法求取窗口數據中值過程開辟大小為n的指針數組，因此空間復雜度為O（n）。

3"實驗結果分析

3.1"快速中值濾波算法有效性驗證實驗

為驗證基于指針排序中值濾波算法的有效性，選取正弦波進行驗證。首先，使用波形生成器生成幅值為1.0、周期為5s、采樣頻率為40Hz的正弦波，并疊加取值［0.0，1.0］之間的隨機噪聲；然后，將波形數據使用窗口寬度分別為15、31、63的中值濾波算法進行濾波處理。濾波處理完畢后，結果如圖4所示，從繪制正弦波的原始波形圖及不同窗口寬度下的濾波波形，可以看出基于指針排序的中值濾波算法能夠有效地進行濾波處理。

如圖4中標注1所示，基于指針排序的中值濾波算法在濾波開始的N個周期不能有效發揮濾波的作用，濾波窗口內的更新數據個數必須大于N，濾波才可能生效。

如圖4中標注2所示，當波形由單調遞增變為單調遞減，濾波后的波形峰值會降低。同理，當波形由單調遞減變為單調遞增，濾波后的波形峰值會增高。濾波后的峰值大小取決于濾波窗口寬度2N+1和采樣頻率f（Hz）以及波形的單調速率。

如圖4中標注3所示，基于指針排序的中值濾波算法會導致濾波后的波形滯后于原始波形，滯后的時間tdelay（s）取決于濾波窗口寬度2N+1和采樣頻率f（Hz）：

tdelay=N/f（1）

完成中值濾波算法測試驗證后，將該算法應用于XX航空發動機數字電子控制器中進行飛行器試飛。如圖5所示，截取試飛過程中一段時間內具有脈沖噪聲干擾特征的XX信號采樣波形及中值濾波后波形，可以看出中值濾波算法能夠有效地實現XX信號的濾波。為觀察濾波細節，將圖5中區域1放大，得到如圖6所示的波形。

如圖6所示，區域2中原始波形有細微的毛刺，經過中值濾波后毛刺消失，驗證了中值濾波對于微小波動的平滑作用。如區域3和區域4所示，中值濾波算法對于飛行過程中XX信號突然出現的脈沖噪聲具有良好的濾除作用。

圖6"XX信號原始波形及濾波波形局部放大圖

3.2"快速中值濾波算法運算速度對比實驗

為驗證基于指針排序的中值濾波算法的運算速度，利用XX航空發動機數字電子控制器開展實驗。如表1所示，算法1為基于指針排序的中值濾波算法，算法2為文獻［7］的快速中值濾波算法，算法3為基于Hoare C A R快速排序算法的傳統中值濾波算法。針對不同中值濾波算法，實驗選取5種數據窗口長度開展15組實驗，每組實驗運行20 000個數據采樣周期，重復運行50次取算法耗時平均值，對耗時均值進行單位歸一化處理。可以看出，算法1和算法2的耗時呈現時間復雜度為O（n）的增長趨勢，算法3的耗時呈現時間復雜度為O（nlog2n）的增長趨勢，算法1相比算法2耗時減少約50%。

3.3"快速中值濾波算法的應用約束

基于指針排序的中值濾波算法作為中值濾波算法的一種，其應用場景在于消除緩變信號的隨機噪聲干擾，這是中值濾波算法應用的最頂層約束。此外，基于指針排序的中值濾波算法具有以下幾個使用約束。

1）由于中值濾波算法前N個周期不能有效發揮濾波作用，因此在使用中值濾波時，應充分考慮前N個周期的信號處理措施。例如：上電的前N個周期不進行濾波或者設置中值濾波算法的濾波窗口數據為信號安全值，以便消除前N個周期不能有效發揮濾波作用的影響。

2）由于中值濾波算法會導致波形滯后，因此在使用中值濾波時，應充分考慮采樣頻率和濾波窗口長度對滯后時間的影響。如果控制系統對于信號值的實時性要求較高，不能采用中值濾波。

3）由于中值濾波算法會導致波形的峰值改變，因此在波形峰值較為關鍵的應用場合，應當根據濾波窗口寬度、采樣速率和波形單調速率對峰值差值進行計算，選取合適的濾波參數。

4"結語

本文提出了基于指針排序的中值濾波算法，通過設計環形數據窗口進行濾波窗口數據的快速更新，通過基于指針排序的窗口中值獲取算法進行窗口中值的快速獲取，實現了中值濾波算法運算速度的大幅提升。由于基于指針排序的中值濾波算法不涉及元素數值的相等判斷操作，因此該算法適用于任意數據類型的中值濾波。該算法除了能夠獲取窗口中值元素外，能夠獲取窗口任意位置的元素，具有較為廣泛的應用前景。

參考文獻：

［1］ 俞莎莎，朱如鵬，李苗苗，等. 基于機器視覺的齒面點蝕面積特征提取的研究［J］. 機械制造與自動化，2020，49（1）：87-90.

［2］ 吳小培，柴曉冬，張德龍. 一種中值濾波的快速算法［J］. 數據采集與處理，1995，10（2）：151-155.

［3］ 葉曉東，朱兆達. 中值濾波的快速算法［J］. 信號處理，1997，13（3）：227-230.

［4］ 靳斌，郭永彩，楊冠玲，等. 一種中值濾波的快速算法［J］. 重慶大學學報（自然科學版），1999，22（5）：13-16.

［5］ 朱冰蓮，潘哲明，李單單.一種中值濾波的快速算法［J］. 信號處理， 2008， 24（4）：684-686.

［6］ 鮑祥生，尹成，田繼東，等. 中值濾波的一種快速算法［J］. 石油物探，2005，44（4）：325-328.

［7］ 梅各各，靳斌，龔偉.一種快速中值濾波算法［J］. 西華大學學報：自然科學版， 2012， 31（6）：77-80.

收稿日期：20220927