2021年第40卷第4期传感器与微系统(Transducer and Microsystem Technologies)
131
DOI ： 10.13873/J. 1000-9787(2021)04-0131-04
面向ECG 的二分法稀疏度自适应匹配追踪重构算法*
*收稿日期：2019-09-29
*基金项目：中央高校基本科研业务费专项资金资助项目(JUSRP51510)；江苏省研究生科研与实践创新计划项目(SJCX18-0647)；江苏省物 联网应用技术重点建设实验室资助项目
王 涛▽，田
青】，虞致国孙益洲-顾晓峰|
(1.物联网技术应用教育部工程研究中心江南大学电子工程系，江苏无锡214122；
2.无锡太湖学院，江苏无锡214064)
摘要：为了减少无线传感器网络(WSNs)心电信号的压缩感知重构时间，提出一种面向心电(ECG)信
号的二分法稀疏度自适应匹配追踪重构算法。基于二分法快速接近真实稀疏度的值，并通过相邻迭代之
间残差范数值差的绝对值确定下一轮迭代计算区间。实验结果表明：与传统稀疏自适应匹配追踪重构算
法相比较，改进算法可显著降低重构时间并接近子空间追踪算法和正交匹配追踪算法；与子空间追踪算法
和正交匹配追踪算法相比，峰值信噪比平均提升了 6.29%和5.43 %。
关键词：压缩感知；心电(ECG)；重构；自适应匹配追踪
中图分类号：TP391； TP212
文献标识码：A 文章编号：1000-9787(2021)04-0131-04
Dichotomy sparsity adaptive matching pursuit in compressed
sensing reconstruction algorithm for ECG *
WANG Tao 1'2, TIAN Qing 1, YU Zhiguo 1, SUN Yizhou 1, GU Xiaofeng 1
(1・ Engineering Research Center of Internet of Things Technology Applications , Ministry of Education ,
Department of Electronic Engineering , Jiangnan University , Wuxi 214122, China ；
2. Taihu University of Wuxi,Wuxi 214064,China)
Abstract : To reduce the time consumption in the reconstruction of electrocardiograph ( ECG ) signals for the
wireless sensor networks ( WSNs ) , a dichotomy spars 让y adaptive matching pursuit ( DSAMP ) algorithm for
compressed sensing without knowing sparsity is proposed ・ The algorithm calculates the stage value for approaching
the real sparsity based on dichotomy , and determines the direction of stage switching by the absolute value of the
difference in residual norm between two adjacent iterations. Results show that the runtime of DSAMP can be reduced compared with that of sparsity adaptive matching pursuit and is similar to those of subspace pursuit and
orthogonal matching pursuit. The peak signal to noise ratio of the DSAMP is improved 6. 29 % and 5. 43 % , compared with the that of orthogonal matching pursuit and subspace pursuit on average , respectively.
Keywords : compressed sensing ； electrocardiograph (ECG ) ； reconstruction ； adaptive matching pursuit
0引言
随着人工智能和无线传感器技术的飞速发展，现代医 学已经进入了智能医疗和远程医疗的时代⑴。老年人的
健康诊断费用高昂，疾病护理面临越来越大的挑战⑵。其
中，远程心电(electrocardiograph , ECG )信号监控的推广有
望建立起一种全新的心血管疾病医疗模式。目前远程
ECG 的检测与传输是无线传感器网络(wireless sensor net
works, WSNs) 的重要组成部分。由于在传输过程中存在大 量的EEG 数据，如何降低数据传输量和能耗而又保证可靠 的信号质量，成为WSNs 应用的关键问题。
压缩感知(compressed sensing, CS)是一种新兴的采样
理论，不仅可以降低对数据存储的要求，而且可以减小设备
的体积，因此广泛应用在医疗、护理和体育等领域⑶幻。CS
的研究主要包括信号稀疏表示，测量矩阵和重构算法⑸。
目前主流上的重构算法中，迭代贪婪追踪算法具有低复杂
度、高精度和高速的特点，研究人员进行了相关研究，包括
匹配追踪(matching pursuit, MP)算法"，正交匹配追踪(or
thogonal matching pursuit , OMP )算法⑺，分段 OMP (stagewise
orthogonal matching pursuit, StOMP)算法⑻，正则化正交匹
配追踪(regularized orthogonal matching pursuit, ROMP)19 算
法，子空间追踪(subspace pursuit, SP )算法〔创和压缩采样
匹配追 踪(compressive sampling matching pursuit , CoSaMP )
132传感器与微系统第40卷
算法⑴】。然而，上述算法都需要稀疏度作为完成迭代的先验条件，使得它们不适合某些实际应用。因此，稀疏自适应匹配追踪(sparsity adaptive matching pursuit,SAMP)算法被提出用以重构信号而不需稀疏度的先验信息①•⑶o于志文提出了可变步长稀疏自适应匹配追踪(variable step-size sparsity adaptive matching pursuit,VSSAMP)算法，选择可变步长来加速重构〔⑷。黄伟强提岀了稀疏性和步长自适应正则化匹配追踪(sparsity and step-size adaptive regularized matching pursuit,SSARMP)，使用稀疏性软估计并在候选集中添加第二列元素〔⑸。然而，上述改进的算法仍然采取线型增加逐步逼近方法，对提高SAMP算法的重构速度效果有限。
本文提出了一种新的基于二分法的稀疏自适应匹配追踪(dichotomy-based sparsity adaptive matching pursuit, DSAMP)算法，可在无信号稀疏度的先验条件下快速重构ECG信号。与SAMP和相关改进算法相比，DSAMP将二分法引入迭代逼近，并使用两轮迭代之间残差范数值差的绝对值控制迭代的计算区间。
1CS和SAMP原理
1.1CS基本原理
根据CS理论N维信号X可以通过测量矩阵0被压缩为维数为M(MWN)的列向量少］
y=^>x(1)通常，假设x是％稀疏的，可表示为
x=W(2)式中矶严为稀疏基,0为原始信号x的在稀疏基上的稀疏表示。将式(1)和式(2)结合起来，即
y=(pip0=A0(3)其中，任何K稀疏矢量&都可以通过求解10最小化问题来重构卫］
min||x||=A0(4)然而厶最小化是一个非确定性多项式问题，可以通过转换为h最小化来解决
min||x||=A0(5)另外，峰值信噪比(peak signal to noise ratio,PSNR)通常用于评估原始信号X和重构信号£之间的差异咖沁晋軒⑹
1.2SAMP算法
近年来，陆续提出了各类匹配追踪算法都能够很好地解决线性规划问题，如OMP算法、SP算法和SAMP算法。OMP算法是每次迭代一个原子，共迭代k次，是一种自下而上的迭代方式。而SP算法每
次迭代A：个原子，共迭代％次，每次移除与预估信号不相关的原子，有效地提高重构精度，是一种自上而下的迭代方式。SAMP算法吸收了两者的优点，通过阈值控制迭代值的逐次逼近，通过回溯机制保证了重构的精度。如图1所示,SAMP算法采用了SP的回溯机制，也有着预选集测试和最终集测试两轮，从图1中可以看岀SAMP的重构流程与SP的重构流程非常相似，但候选集C,，和最终集F,，相比SP算法具有了适应性，正是这个关键的步骤给无需先验稀疏度k提供了保证。然而每轮迭代步长L的合理选择没有定值，只能通过仿真来决定最佳初始步长的选取或者保守地将$设为1。因为若s被设置为大于1，则可能导致稀疏度不匹配。例如当实际稀疏度鸟是31且步长s被设置为3时，在11次迭代后估计稀疏度k将是33。稀疏性显然被高估。因此，这种情况下原始信号的重构需要大量时间。
相关性测试］更新F"卜广［更新残差r”
-
t一賂|
(a)OMP算法
|C|非自适应用半自适应
广］预选集测试卜［候选集C”｝*［最终集测试卜［更新F”制更新残差r”h
]----------------|
(b)SP算法
|C”|自适应1柑自适应
广［预选集测试卜｛候选集G卜［最终集测试｝更新F n b*［更新残差片h
E1
(c)DSAMP算法
图1算法重构流程图
2本文所提出的DSAMP算法
2.1二分法的基本思想
SAMP算法对稀疏度地自适应逼近过程如图2 (a)所示，每次迭代步长厶增加s，共迭代k/s次，迭代过程可以视作对一条长度为M的线段上一点k的线性增加逐次逼近。但当线段长度M值较大的情况下，往往二分法能实现更快的逼近，图2(b)所示，预估起点设为线段的中点匕，然后逐次选取目标线段中点向
佥点逼近。P”的值是每一轮迭代该区间的中点，"是迭代次数。
Si S2S3S n
A…—►
I I I
0M
(a)SAMP算法线性逼近思想
1、
rri
1
0P2Pn Li-*H M
(b)DSAMP算法二分法逼近思想
图2稀疏度逼近示意
2.2残差范数的基本思想
由于SAMP算法迭代步长厶越过真实稀疏度％后，缺乏回拉机制，所以SAMP将初始步长s设为1，并通过阈值控制使厶W%。为了引入二分法作为稀疏度逼近的方法，必须引入迭代值回拉机制。在SAMP算法中，残差范数||r”||在迭代中起着重要作用。当新的残差范数大于或等于固定
第4期王涛，等：面向ECG的二分法稀疏度自适应匹配追踪重构算法133
阈值时，更新迭代步长和最终集。基于SAMP算法重构了来自MIT-BIT标准ECG库的No.100原始ECG信号〔⑻。长度N设置为10000，压缩比C设置为10，实际稀疏度k为110，结果如图3所示。当迭代步长从1变为110时，残差范数从19.63迅速下降到1.57；当迭代步长超过稀疏度k (110)时，残差范数从1.57缓慢减小到0.19，此时迭代步长从110增加到1000。其他编号ECG信号也有相同结果。因此，当两个相邻迭代之间的残差范数差的绝对值小于一个特定值&时，可以认为当前一轮迭代值已经很逼近真实的稀疏度％并可以停止迭代。
2.3算法流程设计
DSAMP算法的重构算法涉及大量矩阵运算和参数符号，重构参数如表1所示。
表1DSAMP算法参数定义
参数定义
A MxN观测矩阵，
M,N维度具体值
C压缩倍数，等于N/M
k原始信号的稀疏度
迭代次数和第n次迭代残差
C”,F”第n次的候选集和最终集
第n次的索引集和支撑集
p”第n次的迭代值
6，&2上阈值和下阈值
在DSAMP算法的重构过程中，最关键的是对每轮迭代值P”的计算。通常重构开始时的第一轮迭代中，计算区间设定为[0,M]时；同时左端点P，和右端点P，分别设置为0和M o每轮迭代值P n的计算公式如下
P”=[(P/+P”)/2](7)其中，[•]为取整函数。
基于在真实稀疏度附近残差范数值前后两次之差小于特定阈值的特点，设定3个新值△，下阈值匂和上阈值勺，6和创用来判断迭代值P.在下一轮迭代中作为计算区间的左端点还是右端点，而△用作判定阈值，其计算公式如下A=abs(||r”||2-r”_i||2)(8)式中abs(•)为取•绝对值,||•||2为取2范数，r n为本轮迭代的残差值，为上一轮的残差值。如果
将被更新为下一轮计算区间的左端点匕，上一轮的右端点保留匕；如果6>勺,P n将要被更新为下一轮计算区间的右端点上一轮的左端点保留匕；如果A^s2,F n,r n,n 将会更新。其中,6和&2数值的选取是个合理化选择的过程，可通过对大量ECG信号的仿真结果得出。图4为DSAMP算法的流程图。
下面给出DSAMP算法的详细步骤。
输入：传感矩阵A"
*"；测量向量y。
输出：重构信号九
步骤1初始化残差「。=儿感知矩阵A的列向量索引集人=0，候选集C。=0，支撑集為=0，迭代中间值P”=M/2,P t=0,P r=M，迭代次数n=1©=0.1和^=0.8；
步骤2计算叫nabsMhJ，从“”中选取匕个最大值对应的A的列向量索引存入索引集4。中；
步骤3合并索引4-与支撑集得到候选集C”，即C”=4”t U2t；
步骤4求y=AQ最小二乘解，玄=argmin Q-必”||;
步骤5从瓦中选出绝对值最大的P n项记为e p，对应A”中的P”列记为A p，对应A序列号为A p，记最终集F”=A p;
步骤6更新残差r n=y-A p(A；A P)-l A；yi
步骤7判断迭代停止条件：计算前后两轮残差范数值之差△，若满足△W&2，则退出迭代；
若满足A>6，则P”=[(匕+匕)/2]，更新P n为左端点鬥=P”，返回步骤2；
若满足&2VA，则P n=[(P,+PJ/2]，更新P”为右端点P r=P n，返回步骤2；
否则更新支撑集亿和残差r n,n=n+l，返回步骤2。
步骤8重构原始信号X。
3仿真结果
本文将DSAMP,OMP,SP和SAMP应用于MIT-BIT心律失常数据库""的信号重构。为了保证ECG信号的统一，必要时对ECG信号进行了重采样以满足仿真要求。分别采用高斯随机矩阵和离散余弦变换基作为测量矩阵和稀疏基。计算机处理器为主频3.6GHz的Intel13-4160
四核
CPU，并在MATLAB中进行仿真。
3.1不同M情况下的运行时间
仿真过程中，选择No.100ECG记录,ECG信号的长度N设置为10000，测量长度M设置为500至4000，并且SAMP的步长s设置为1。图5为不同M下四种不同算法的运行时间。SAMP比其他三种算法消耗更多时间，并且其重构时间呈指数增长。此外,DSAMP在未知稀疏度的情况下，运行时间几乎与已知稀疏度的OMP和SP接近。
亠OMP
■-SP
—DSAMP
■
■
标准ECG信号测量长度M标准ECG信号测量长度M 图5不同M下四种不同算法的重构时间
3.2不同/V情况下的运行时间
仿真过程采用了MIT-BIT标准ECG信号库的No.100号数据作为测试数据，压缩倍数设置为10.ECG信号长度N设置为从5000到10000,SAMP算法的起始步长s 设置为1。图6反映了No.100ECG信号由四种算法分别重构的时间随ECG信号长度N的变化，显然,SAMP重构时间最缓慢，且呈指数增长,OMP,SP和DSAMP都可以以非常高的速度重构信号。在这些算法中，DSAMP的运行时间最短，并且随着N的增加以最慢的速度增加。与OMP和SP相比,DSAMP的最大运行时间改善分别为70.05%和83.10%；DSAMP的平均运行时间改善分别为68.12%和79.26%。
图6不同N下四种不同算法的重构时间
3.3不同N情况DSAMP算法重构峰值信噪比
测试采用了MIT-BIT标准ECG信号库的No.100号数据作为测试数据，信号长度统一设置为10000,ECG压缩倍数设置为从5到20,SAMP算法的起始步长s设置为l o 图7为ECG信号由四种算法分别重构的PSNR随压缩倍数C的变化。在压缩倍数小于10时,DSAMP的重构精度都优于OMP和SP，但当压缩倍数大于10时,DSAMP重构精度出现了比较大下降。SAMP算法由于初始步长s较小的关系，始终保持了最优的重构精度。在压缩倍数为5的情况下,DSAMP算法相较OMP和SP有着最大的峰值信噪比(peak signal to noise ratio,PSNR)提高，分别为20.64%和20.03%o DSAMP相较于OMP和SP的平均精度提高为6.29%和5.43%。
图7PSNR随压缩倍数C变化
4结束语
本文提出了一种新的DSAMP方法，在无需先验稀疏度%的情况下重构大样本ECG信号。DSAMP携弃线性增加逐步逼近的方法，采用二分法迭代逼近真正的稀疏度虑实验结果表明，DSAMP算法能够在保证重构精度的条件下，显著降低对ECG信号的重构时间。
参考文献：
[1]GORUNESCU F.Intelligent decision systems in medicine—A
short survey on medical diagnosis and patient management[C
IEEE E-Health and Bioengineering Conference,Piscataway,NJ:
IEEE Press,2015：l-9.
[2]岳廷明，王金海，王慧泉.融合加速度信息的动态心电EMD
滤波算法[J]•计算机工程与应用,2015,51(20)：192-197. [3]DONOHO D L.Compressed sensing[J].IEE
E Transactions on
Information Theory,2006,52(4)：1289—1306.
[4]韩二江，孙剑，郝晶，等•基于压缩感知的激光成像方法[J]・
传感器与微系统,2019,38(4):15-17,21.
[5]赵磊，俞阿龙，徐冬平，等•压缩感知在传感器节点信息采集
中的应用[J]•传感器与微系统,2016,35(8):141-143,147.
[6]MALLAT S G,ZHANG Z F.Matching pursuits with time-frequen
cy dictionaries[J].IEEE Trans on Signal Processing,2013,
41(12)：3397-3415.
[7]TROPP J A,GILBERT A C.Signal recovery from random measurements
via orthogonal matching pursuit[J].IEEE Trans on Information Theory,2017,53(12)：4655—4666.
[8]DONOHO D L,TSAIG Y,DRORI I,et al.Sparse solution of
underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].IEEE Trans on Information Theory,
2012,58(2):1094-1121.
[9]NEEDELL D,VERSHYNIN R.Signal recovery from incomplete
and inaccurate measurements via regularized orthogonal matching pursuit[J].IEEE Journal of Selected Topics in Signal Proces-sing,2010,4(2)：310-316.
[10]吕伟杰，陈霞，刘红珍.基于压缩感知的图像自适应子空间追
踪算法[J]•计算机工程与应用,2016,52(3):220-223. [11]NEEDELL D,TROPP J A.CoSamp iterative signal recovery from
incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2009,26(3)：301—321.
(下转第138
页)
此外在查准率上YOLO也是优于另外两种方法，这一点对于扣件安全检测具有重要的意义。但在查全率上三种方法的差距不太明显，是因为线振相机拍的本是灰度图，扣件图为实地拍摄并非来自实验室环境下，背景误判发生的可能性较高，但综合三个测试集的结果来看,YOLO的背景误判率还是优于另外两种算法。纵向对比来看只有在测试集2 下的YOLO的查全率略低于Faster-R-CNN，后期检测发现是因为在测试集2下照片中扣件视角普遍较深而网格划分参数M设置较小（M=7），并且测试集2下多数扣件存在部分遮挡的情况，导致检测这些扣件时可能出现了漏检。但综合考虑到在检测速度获得极大提升和检测的准确率得到保证的同时，查全率还能达到85.1%，在本实验数据集下的YOLO表现出的
查全率、查准率和检测速度已经足够优秀。当然在保证了查准率和检测速度的前提下如何进一步提高模型的查全率也需要后续的不断实验来探索。
4结论
本文应用YOLO检测算法实现了对实拍轨道扣件照片的检测，从而判断出该照片中扣件状态的好坏，在检测速度（60f/s）和准确率（94.2%）方面均获得了较大提升。而本实验研究的出发点是为了提供一种高效率的轨道扣件状态检测方法，来代替人工巡检的低效率方式。通过以上研究基本满足了这一需求，并且在不改变模型结构的前提下，该方法还可以应用到其他检测邻域，具有很好的适应性。
参考文献：
[1]龙炎•基于深度学习的铁路扣件检测系统的研究[D].北京：
北京交通大学,201&[2]KRIZHEYSKY A,SUTSKEVER I,HINTON G E.Image net clas-
sificalion with deep convolutional neural networks[C]//Proceedings of2012International Conference on Neural Information Systems,：S.l],ACM,2012：1097-1105.
[3]GIRSHICK R.Fast R-CNN[CProceedings of2015IEEE
International Conference on Computer Vision,Santiago：IEEE, 2015：1440-1448.
[4]REN S,HE K,GIRSHICK R.Faster R-CNN：Towards real-time
object detection with region proposal networks[J]・IEEE Transactions on Pattern Analysis&Machine Intelligence,2017, 39(6):1137.
[5]JOSEPH R,SANTOSH D.You only look once:Unified,real-time
object detection[C]//Proceedings of2016IEEE Conference on Computer Vision and Pattern Recognition,Las Vegas：IEEE, 2016：779-788.
[6]张军，张婷，杨正令瓦，等•深度卷积神经网络的汽车车型识别
方法[J]•传感器与微系统,2016,35(11)：19-22.
[7]LE CUN Y A,BOTTOU L,ORR G B,el al.Efficient back-
rop[M].Berlin:Springer,2012.
[8]DOLLAR P,WOJEK C,SCHIELE B,et al.Pedestrian detection：
A benchmark[C]//2009IEEE Conference on Computer Vision
and Pattern Recognition,[S.1.]：IEEE,2009：304—311.
作者简介：
王兵水(1994-)，男，硕士研究生，研究方向为轨道智能检测，E-mail:wangbingshuiO1@163 o
郑树彬(1979-)，男，通讯作者，博士，主要研究领域为轨道交通车辆/轨道设备状态检测技术与理论的教学与研究,E-mail：zhengshubin@126 o
(上接第134页)
[12]DO T T,LU G,NGUYEN N,et al.Sparsity adaptive matching
pursuit algorithm for practical compressed sensing[C]//Proceedings of the42n d Asilomar Conference on Signals,Systems,and Computers, Piscataway,NJ:IEEE Press,2008：581—587. [13]GAN W,XU L P,ZHANG H,et al.Greedy adaptive recovery
algorithm for compressed sensing[J].Journal of Xidian University,2012,33(9)：1948-1953.
[14]YU Z W.Variable step-size compressed sensing-based sparsityadaptive
adaptive matching pursuit algorithm for speech reconstruction[C]// Proceedings of the33rd China Control Conference,Piscataway,
NJ：IEEE Press,2014：7344—7349.
[15]HUANG W Q,ZHAO J L,LU Z Q,et al・Spareity and step-size
adaptive regularized matching pursuit algorithm for compressed sensing[C~\J/Proceedings of IEEE7th Joint International Information Technology and Artificial Intelligence Conference,Piscataway,NJ:
IEEE Press,2014：536-540.[16]TSAIG Y,DONOHO D L.Extensions of compressed sensing[J].
Signal Processing,2006,86(3)：549—571.
[17]DONOIIO D L.For most large underdetermined stems of linear
equations,the minimal Zj-norm solution is also the sparsest
solution[J]・Communications on Pure and Applied Mathematics,
2006,59(6):797-829.
[18]MOODY G B,MARK R G.The impact of the MIT-BIH arrhyth
mia database[J].IEEE Engineering in Medicine and Biology,
2001,20(3)：45-50.
作者简介：
王涛(1990-)，男，硕士研究生，助教，研究方向为工业机器视觉与人工智能，工业机器人故障检测。
田青(1993-)，男，硕士研究生，研究方向为信号处理，专用集成电路设计和测试。
虞致国(1979-)，男，博士，副教授，主要研究领域为信号处理，大规模集成电路设计与测试,E-mail:yuzhiguo@jiangnan.edu. cn o
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论