摘"要：為實(shí)現(xiàn)航空發(fā)動(dòng)機(jī)控制系統(tǒng)采集信號(hào)的快速中值濾波，設(shè)計(jì)一種基于指針排序的快速中值濾波算法，將中值濾波過程分解為窗口數(shù)據(jù)更新和窗口數(shù)據(jù)中值求取兩個(gè)算法片段。針對(duì)窗口數(shù)據(jù)更新算法片段，提出一種環(huán)形數(shù)據(jù)窗口更新算法，通過指針指向平移實(shí)現(xiàn)數(shù)據(jù)窗口的滑動(dòng)，縮短了窗口數(shù)據(jù)更新的耗時(shí)。針對(duì)窗口數(shù)據(jù)中值求取算法片段，提出一種基于指針排序的數(shù)據(jù)比較和移位算法，在運(yùn)算內(nèi)存開銷較小的情況下實(shí)現(xiàn)了窗口數(shù)據(jù)中值的快速求取。實(shí)驗(yàn)結(jié)果表明：基于指針排序的快速中值濾波算法能夠在耗時(shí)減少的情況下，實(shí)現(xiàn)信號(hào)隨機(jī)噪聲的有效濾除。

關(guān)鍵詞：航空發(fā)動(dòng)機(jī)；控制系統(tǒng)；中值濾波；指針；排序算法；快速排序

中圖分類號(hào)：TP274""文獻(xiàn)標(biāo)志碼：B""文章編號(hào)：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"引言

滑油液位傳感器用于航空發(fā)動(dòng)機(jī)控制，由于航空發(fā)動(dòng)機(jī)的工作環(huán)境比較惡劣，導(dǎo)致滑油液位信號(hào)會(huì)出現(xiàn)隨機(jī)噪聲干擾，干擾過大時(shí)會(huì)引起航空發(fā)動(dòng)機(jī)的控制異常?；诎l(fā)動(dòng)機(jī)運(yùn)行試驗(yàn)統(tǒng)計(jì)分析，滑油液位信號(hào)的干擾類型為脈沖噪聲。中值濾波算法能夠有效去除隨機(jī)脈沖噪聲的影響并有效保留原始信號(hào)的細(xì)節(jié)信息，因此采用中值濾波算法對(duì)滑油液位信號(hào)進(jìn)行濾波［1］。

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

發(fā)動(dòng)機(jī)控制分為定點(diǎn)型和浮點(diǎn)型兩種運(yùn)算類型，其中浮點(diǎn)型運(yùn)算明確禁止數(shù)值比較相等，且控制芯片對(duì)于運(yùn)算速度和運(yùn)算內(nèi)存均有較高要求。因此，研究適用于任意數(shù)據(jù)類型、時(shí)間復(fù)雜度和空間復(fù)雜度均較低的快速中值濾波算法具有重要意義。

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

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

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

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

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

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

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

步驟2更新指針數(shù)組P的指針指向，實(shí)現(xiàn)窗口數(shù)組B中數(shù)據(jù)元素的排序，以圖2為例。

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

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

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

綜上，基于指針排序的快速中值濾波算法主要思路是通過對(duì)比最新元素與左側(cè)或右側(cè)指針?biāo)赶虻臄?shù)據(jù)元素大小，更改指針的指向，重新獲得有序的指針數(shù)組，最終求取窗口數(shù)組的中值。

2"快速中值濾波算法實(shí)現(xiàn)與復(fù)雜度分析

基于指針排序的快速中值濾波算法的數(shù)據(jù)更新過程復(fù)雜度為O（1），不再進(jìn)行單獨(dú)分析。本節(jié)對(duì)求取窗口數(shù)據(jù)中值過程進(jìn)行詳細(xì)分析。

如圖3所示，與算法原理對(duì)應(yīng)，求取窗口數(shù)據(jù)中值過程分為步驟1、步驟2及返回中值等3個(gè)步驟，在進(jìn)行算法復(fù)雜度分析時(shí)設(shè)n=2N+1。

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

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

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

通過上述算法分析，基于指針排序的中值濾波算法的算法語句最大頻度為T（n）=6N+3，算法語句最小頻度T（n）=5，算法語句平均頻度T（n）=3N+4，時(shí)間復(fù)雜度為O（n）?；谥羔樑判虻闹兄禐V波算法求取窗口數(shù)據(jù)中值過程開辟大小為n的指針數(shù)組，因此空間復(fù)雜度為O（n）。

3"實(shí)驗(yàn)結(jié)果分析

3.1"快速中值濾波算法有效性驗(yàn)證實(shí)驗(yàn)

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

如圖4中標(biāo)注1所示，基于指針排序的中值濾波算法在濾波開始的N個(gè)周期不能有效發(fā)揮濾波的作用，濾波窗口內(nèi)的更新數(shù)據(jù)個(gè)數(shù)必須大于N，濾波才可能生效。

如圖4中標(biāo)注2所示，當(dāng)波形由單調(diào)遞增變?yōu)閱握{(diào)遞減，濾波后的波形峰值會(huì)降低。同理，當(dāng)波形由單調(diào)遞減變?yōu)閱握{(diào)遞增，濾波后的波形峰值會(huì)增高。濾波后的峰值大小取決于濾波窗口寬度2N+1和采樣頻率f（Hz）以及波形的單調(diào)速率。

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

tdelay=N/f（1）

完成中值濾波算法測(cè)試驗(yàn)證后，將該算法應(yīng)用于XX航空發(fā)動(dòng)機(jī)數(shù)字電子控制器中進(jìn)行飛行器試飛。如圖5所示，截取試飛過程中一段時(shí)間內(nèi)具有脈沖噪聲干擾特征的XX信號(hào)采樣波形及中值濾波后波形，可以看出中值濾波算法能夠有效地實(shí)現(xiàn)XX信號(hào)的濾波。為觀察濾波細(xì)節(jié)，將圖5中區(qū)域1放大，得到如圖6所示的波形。

如圖6所示，區(qū)域2中原始波形有細(xì)微的毛刺，經(jīng)過中值濾波后毛刺消失，驗(yàn)證了中值濾波對(duì)于微小波動(dòng)的平滑作用。如區(qū)域3和區(qū)域4所示，中值濾波算法對(duì)于飛行過程中XX信號(hào)突然出現(xiàn)的脈沖噪聲具有良好的濾除作用。

圖6"XX信號(hào)原始波形及濾波波形局部放大圖

3.2"快速中值濾波算法運(yùn)算速度對(duì)比實(shí)驗(yàn)

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

3.3"快速中值濾波算法的應(yīng)用約束

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

1）由于中值濾波算法前N個(gè)周期不能有效發(fā)揮濾波作用，因此在使用中值濾波時(shí)，應(yīng)充分考慮前N個(gè)周期的信號(hào)處理措施。例如：上電的前N個(gè)周期不進(jìn)行濾波或者設(shè)置中值濾波算法的濾波窗口數(shù)據(jù)為信號(hào)安全值，以便消除前N個(gè)周期不能有效發(fā)揮濾波作用的影響。

2）由于中值濾波算法會(huì)導(dǎo)致波形滯后，因此在使用中值濾波時(shí)，應(yīng)充分考慮采樣頻率和濾波窗口長(zhǎng)度對(duì)滯后時(shí)間的影響。如果控制系統(tǒng)對(duì)于信號(hào)值的實(shí)時(shí)性要求較高，不能采用中值濾波。

3）由于中值濾波算法會(huì)導(dǎo)致波形的峰值改變，因此在波形峰值較為關(guān)鍵的應(yīng)用場(chǎng)合，應(yīng)當(dāng)根據(jù)濾波窗口寬度、采樣速率和波形單調(diào)速率對(duì)峰值差值進(jìn)行計(jì)算，選取合適的濾波參數(shù)。

4"結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

收稿日期：20220927