基于指针排序的快速中值滤波算法研究

摘"要：为实现航空发动机控制系统采集信号的快速中值滤波，设计一种基于指针排序的快速中值滤波算法，将中值滤波过程分解为窗口数据更新和窗口数据中值求取两个算法片段。针对窗口数据更新算法片段，提出一种环形数据窗口更新算法，通过指针指向平移实现数据窗口的滑动，缩短了窗口数据更新的耗时。针对窗口数据中值求取算法片段，提出一种基于指针排序的数据比较和移位算法，在运算内存开销较小的情况下实现了窗口数据中值的快速求取。实验结果表明：基于指针排序的快速中值滤波算法能够在耗时减少的情况下，实现信号随机噪声的有效滤除。

关键词：航空发动机；控制系统；中值滤波；指针；排序算法；快速排序

中图分类号：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