基于k-means的纸质心电图数字化信息提取研究

闫 磊，罗 晶

(海军总医院计算机管理中心，北京 100048)



基于k-means的纸质心电图数字化信息提取研究

闫 磊，罗 晶

(海军总医院计算机管理中心，北京 100048)

针对临床诊断中纸质心电图容易遭到不同程度的损坏，且不便于保存的问题，探讨了纸质心电图的数字化问题。采用均值法降噪，在Sobel算法中加入了45°和135° 2个方向的模板，利用k-means方法进行了改进，从而得到更加精准的心电图的数字化提取图形。实际验证发现，心电图的数字化提取精度得到了有效提升，有望在医疗实际中推广应用。

信息处理技术其他学科；纸质心电图；数字化；心电波形；k-means

心电图是检查心脏异常的重要手段。目前，心电图的检查结果使用热敏纸，由患者自己保存。因其不稳定、易消褪的特点，长期保存下来的心电图图像会有不同程度的破坏，不能用于后续的研究和分析，给临床实验和科学研究带来巨大的损失[1]。海军总医院是一所综合性三甲医院，医院基于DICOM(digital imaging and communications in medicine)标准实现了大部分科室的心电图的数字化传输、存储、管理，并可与医院信息系统、PACS(picture archiving and communication systems)系统数据共享，方便医务人员使用，为医疗、教学和科研提供了有力支持。因神经内科监护室、神经外科监护室、内分泌科不具备无线网络环境，远程会诊时申请会诊方将以图片格式传输心电图检查结果，夜间或加急情况时更会受到时间的限制，所以只能采取以提取数字化心电图检查结果的方式进行查看。为实现心电图信息全部数字化，给疾病诊断与研究提供更加完善的支持，纸质心电图的数字化迫在眉睫[2]。

1 几种数字化信息提取方法

随着医院管理的信息化和智能化水平的不断提高，医院信息系统的功能也在不断丰富与加强。作为医院信息储存的重要组成部分，心电图数字化研究与存储在海量的医学图像处理中有着不可替代的作用。目前常见的信息数字化提取方法分别是：轨迹追踪法、模型匹配法、阈值变换法、Snake模型方法[3]。

轨迹追踪法首先需要手动校准心电图波形位置的出发点，之后在探测过程中依次完成整个波形上点的探测或在波形窗口和向下的轨迹点初始化为一个固定大小的窗口[4]。整个过程需要人工引导，同时探测点容易被心电图纸网格线干扰，精度较低[5]，最终提取的心电图波形与实际波形相差较大，不适合用于医学研究和临床诊断。

模型匹配法在PR间期和T波区域按照轨迹跟踪法进行波形点的跟踪，在QRS 波群处用预先建好的模型取代[5]。该方法提取出的波形因QRS波群准确率低，无法反应左、右心室的悸动，不利于心脏疾病的检测[6]。

阈值变换法[7-8]基于心电图曲线与背景网格在灰度上有一定差别的特点，通过合理的阈值将曲线从网栅格中分离。这种方法适合成像清晰且对比度较大的图像。纸质心电图由于存在损坏及噪点等随机因素影响，阈值选取困难，提取清晰准确的波形难度较大[2]。

Snake模型方法是预先用一个圆形的像素圈套住图形作为初始的Snake线，取一定个数的点来离散化Snake线，然后求出Snake线与原始图像间的曲线能量Esnake，最后通过运算循环逼近Esnake最小的Snake线从而得出轮廓。尽管Snake模型具有稳定性和简易性，但该方法对初始轮廓敏感，在波形波峰、波谷处因无法收敛到全局极值造成提前停止搜索，导致结果不准确。此外，实际操作中多心电波形轮廓初始化是十分耗时的[9-10]。

基于以上所述，需要对现有算法进行改进研究，改正上述算法中提取精度不高、实际验证起来耗时耗力等缺点，取其精华，借鉴现有算法的优点。文中对基于k-means算法进行了筛选，减少图片处理的繁琐量，并对其进行改进，提高了现有算法中纸质心电图数字化的精度。

2 基于k-means算法的纸质心电图数字化提取

在介绍前人研究过的几种数字化信息提取过程中，发现其具有精度低、提取到的波形准确率不高、阈值选取困难和波峰、波谷处无法收敛导致结果不准确等多种缺点。本研究采取改进的k-means算法进行纸质心电图的数字化提取，该算法的阈值最后分割和方差法中的最大类间与现有方法有很明显的不同。

2.1 心电图像的倾斜检测与校正的预处理

扫描获得的心电图往往是倾斜的，给心电波形的数字化处理带来不便。所以，首先采用Hough变换检测心电图纸与背景的边缘，得到图像的倾斜角度，然后利用坐标系变换对扫描心电图进行旋转校正，倾斜校正结果如图1所示。

图1 纸质心电图倾斜校正结果Fig.1 Tilt correction result of paper ECG

2.2 数字化提取

为了改进先前提取精度不准确的缺点，本文基于Sobel_MCO (Sobel_morphological closed operation)筛选机制，在前人研究的3乘3的矩阵中加入了45°和135° 2个角度的模板，进行快速卷积，采用改进的k-means方法对波形进行提取，减小了误差，提高了波形提取的准确性。

2.2.1 降噪处理

为了便于研究，将心电曲线转换成坐标形式。在心电图的实际测试过程中，因患者紧张或情绪不稳产生的肌肉颤动、肢体活动或波形宽度和扫描的分辨率等因素，造成心电图波形的某些区域对应多个像素，比如横坐标会对应2个或3个纵坐标的点，这时需要对图像进行降噪、光滑处理等[8]。

使用均值法降噪，将横坐标相对应的点的纵坐标取平均值，作为新的纵坐标，如横坐标为5的点有3个，并且分别为(10,7,4)，这样将纵坐标的平均值(10+7+4)/3也就是7作为降噪之后对应的横坐标的新的纵坐标。这样横坐标为5的点就只有一个纵坐标为7的值。经比较，通过降噪处理过的重构数据图形与原图像相同，不存在失真现象。

2.2.2 筛选定位

为降低工作量，节省后期图片处理时间，先通过Sobel算子对原始图像的边缘信息进行处理，再对图像进行二值化处理[11]，对所得的图像矩在基于边缘上进行分块的实体取出。

传统Sobel算子定位精度差，提取边缘较粗，因此本文在Sobel算子的基础上进行了改进。在算子模板上加入45°和135° 2个方向的模板，以提高边缘定位的精度，同时采用局部梯度均值作为阈值对初始梯度的图像进行筛选，最终提高定位的准确性和连续性[12-13]。

Sobel算子用来运算图像亮度函数的灰度近似值。Sobel卷积算子为

横向:-101-202-101,

纵向:121000-1-2-1,

该算子包含2组3×3的矩阵，分别为横向及纵向2个方向，将之与图像作平面卷积，即可分别得出横向及纵向的亮度差分近似值。以I代表原始图像，Gx及Gy分别代表经横向及纵向边缘检测的图像灰度值，其公式如下：

在图像的任何一点使用此算子，图像的每一个像素的横向及纵向灰度值可结合下式来计算该点灰度的大小：

Sobel算子的45°和135° 2个模板的算子为

45°:0-1-210-1210,

135°:-2-10-101012。

2.2.3 改进的k-means 的波形提取

1)k-means聚类方法

k-means算法是要接收输入量k，为了将聚类得到满足，所以再将n个数据对象划分为k个聚类[14]。因为同一个类中的对象相似度很高，所以需要先对特征值进行确定，然后再确定一个中心对象，这样计算出来才会得到有效分类。

2)确定聚类中心

首先，初始化聚类中心为空集，聚类个数为k，生成U的关于属性集P的距离矩阵和归一化矩阵，并计算所有对象之间距离的平均值。其次，在各个距离的平均值之中选择一个小邻域，生成邻域矩阵。在生成的U矩阵中所有对象的邻域矩阵又分为上近似矩阵和下近似矩阵，在计算中求出来所有对象的上近似矩阵和下近似矩阵[15]。由于进行筛选时是基于样本间的距离来进行的，所以这样做降低了孤立点对聚类中心的影响，选出来的初始值不容易受样本输入顺序的影响，排除了可能的孤立点对象。将筛选出来的点按照由高到低的顺序来排序，排序后的第1个值则为第1个初始中心，然后在这个邻域中依次循环，又有新的初始中心，当聚类中心为k时，算法将会终止。

为了减少由于各个属性量纲不一致对结果的影响，邻域要尽量标准化到[0,1]区间，与此同时，可以得到所有对象的平均距离。如果邻域太小的话，就没有了其他对象包含在邻域内；如果邻域太大的话，就可能导致对象之间的分离度变低，所以邻域的选取也是非常重要的。经实验研究，发现邻域选取在0到平均距离之间是最好的，这样做有利于聚类中心的确定，为后面基于k-means算法的实现打下基础。

3)k-means 算法用于波形数据的提取

k-means 聚类算法是硬聚类算法，是基于划分的聚类方法的代表，这种算法具有简单、快速的优点，而且对大数据集有比较高的效率和良好的可伸缩性。由Sobel 算法得到梯度矩阵后，需要选取适当的阈值以将实数值矩阵转换为二值矩阵，这就需要人为选取阈值，而人为选取阈值带有随意性。

为了自适应获取最佳阈值，将k-means算法应用到阈值选取中，依照梯度的分布及每个点的梯度值，可以将图像中的每个像素点分为边缘和背景两类。k-means算法将N维的P个点分成k个聚类，当N和P比较小且k=2时，可以使聚类的效果达到最好，即不会陷入局部最优解。处理过程描述如下。

Step1: 由Sobel算子处理得到的梯度图像为G，其梯度点总数为N；

Step2: 随机选取2个质心点Z1和Z2，也即2个初始聚类中心；

Step3: 把每个点的梯度值gi归类到与聚类中心Zi差值最小的类ci，

ci=argmin‖gj-Zi‖,i∈{1,2},j∈{1,2,…,N};

Step5: 按上式进行计算，结果为所有样本到新的聚类中心距离的平方和；

Step6: 重复Step3—Step5，使得聚类中心不再发生变化或小于一个很小的阈值S；

Step7: 由此获得梯度阈值Gth，根据梯度阈值二值化梯度图像，得到图像边缘。

4)心电图波形与背景栅格的分离

在经过2.3.2和2.3.3步骤后，波形被提取出来，这样只剩下较为完整的曲线和没有办法避免的噪声点。以图像为模板，与原始图像进行掩模变换，将带噪声点的心电图曲线波形提取出来，实现波形与背景栅格的初步分离。

通过采用ECG背景网格重建的方法，可以求出每个大格中包含的像素点的个数pn：

式中：pn为大格中包含的像素点个数；t为大格的时间；DPI为扫描仪分辨率；v为走纸速度。

2.3 实际验证

为了验证改进的k-means聚类算法提取波形的准确性和可靠性，抽取100名具有代表性的患者的纸质心电图进行测试，结果如表1所示。通过对比数字化后的 ECG 波形和纸张心电图波形，发现该方法能够有效地剔除背景栅格，保留比较完整的曲线，提取出准确率高达98%的心电波形曲线。

表1 患者心电图数字化提取前后对比

将如图2所示的纸质心电图进行数字化处理，利用阈值法处理的结果如图3所示。由图3可见，选择不同的灰度阈值会得到不同的结果，阈值过大会造成背景噪声过多，阈值过小会使心电波形不连续。利用k-means算法提取的结果如图4所示，由图4可见，该方法不仅有效提取了心电波形，而且背景噪声被有效滤除。

图2 纸质心电图Fig.2 Paper ECG

图3 灰度阈值方法的波形提取结果Fig.3 Waveform extraction results of gray threshold method

图4 k-means算法的波形提取结果Fig.4 Waveform extraction results of k-means algorithm

3 结 语

纸质心电图由纵横交错的背景协调网络、心电图波形曲线、导联字符及校准电压组成。数字化信息提取是在一系列的智能处理技术上将纸面上的波形数据提取出来并保存的数字化过程。纸质心电图数字化一直是比较热门的话题，但因存在很多技术性问题，提取结果精度较低，实际应用并不广泛。所以本文在前人的经验基础上，采用改进的k-means技术，将纸质心电图数字化，提取出高精确度的波形，使患者信息保留的更加完整，信息更完全。但是由于提取出来的数字化波形与原来的纸质版还是有细微差别，而医学上的微小误差也会给临床诊断带来极大的影响，所以本文所采用的算法精度还有待进一步提高。

[1] 秦晓华．一种老年人移动健康监护系统的研究[D]．北京：清华大学，2010． QIN Xiaohua. A Mobile Health Monitoring System for the Elderly[D]. Beijing: Tsinghua University, 2010.

[2] 王志祯，陈兆学，赵晓静．基于高斯模糊技术的心电图曲线提取方法[J]．中国组织工程研究与临床康复，2010，14(39)：7346-7349． WANG Zhizhen, CHEN Zhaoxue, ZHAO Xiaojing. Electrocardio gram curves extraction method based on Gaussian blur technique[J]. Journal of Clinical Rehabilitative Tissue Engineering Research, 2010, 14(39): 7346-7349.

[3] 孙佳新．基于信号质量评估的可穿戴运动心电监护系统[D]．上海：东华大学，2011． SUN Jiaxin. Wearable Dynamic ECG Monitoring System Based on the Signal Quality Evalution[D]. Shanghai: Donghua University, 2011.

[4] 陈安，陈宁．数据挖掘技术及应用[M]．北京：科学出版社，2006．

[5] 程凡，高荣，魏义祥．扫描心电图心电轨迹的跟踪算法[J]．生物医学工程学杂志，2001，18(2)：169-172．

CHENG Fan, GAO Rong, WEI Yixiang. Tracing algorithms of ECG tracks from scanned image[J]. Journal of Biomedical Engineering, 2001, 18(2): 169-172.

[6] 杨荣峰，魏义祥．扫描心电图心电轨迹的连续跟踪算法[J]．医疗卫生装备，2003(6)：1-3． YANG Rongfeng,WEI Yixiang. Continuously tracing algorithms of ECG tracks from scanned image[J]. Medical Equipment Journal,2003(6):1-3.

[7] 史国洁．纸质心电图数字化信息提取的关键问题研究[D]．天津：天津理工大学，2011. SHI Guojie. Study of Key Techniques on Electrocardiogram Printouts Digitizing[D]. Tianjin: Tianjin University of Technology, 2011.

[8] 王志成，胡阳，黄瑛，等．ECG记录图纸数字化过程中的幅值定标方法及其后处理[J]．中国医疗器械杂志，2014，28(1)：19-22． WANG Zhicheng, HU Yang, HUANG Ying,et al. Amplitude scaling and post-processing methods for digitalization of paper-recorded ECG curves[J]. Chinese Journal of Medical Instrumentation, 2014, 28(1): 19-22.

[9] PARK S,CHU W W,YOON J,et al. Efficient searches for similar subsequences of different lengths in sequence database[C]//Proceedings of the 16th International Conference on Data Engineering.Washtington:IEEE Computer Society,2000:23-32.

[10]SHI Guojie, ZHENG Gang,DAI Min，et al. Study of key techniques on electrocardiogram printouts digitizing[J].Key Engineering Materials，2011, 467/468/469:1979-1984.

[11]乔万波，曹银杰．一种改进的灰度图像二值化方法[J]．电子科技，2008，21(11)：63-64． QIAO Wanbo, CAO Yinjie. An improved binarization method for gray images[J]. Electronic Science and Technology, 2008, 21(11): 63-64.

[12]赵志华，许爱华．基于形态学的 ECG 小波自适应去噪算法[J]．计算机工程与设计，2008，29(8)：2140-2142． ZHAO Zhihua, XU Aihua. ECG adaptive wavelet transform of denoising algorithm based on morphology[J]. Computer Engineering and Design, 2008, 29(8): 2140-2142.

[13] 高清维，李海鹰，庄镇泉，等．基于平稳小波变换的心电信号噪声消除方法[J]．电子学报，2003，31(2)：238-240． GAO Qingwei, LI Haiying, ZHUANG Zhenquan,et al. De-noising of ECG signal based on stationary wavelet transform[J]. Acta Electronica Sinica, 2003, 31(2): 238-240.

[14] 练仕榴．生物医学信号的相似性度量研究[D]．天津：天津理工大学，2011． LIAN Shiliu. Research of Similarity Measurement for Biomedical Signal[D]. Tianjin: Tianjin University of Technology, 2011.

[15] 张海进．基于嵌入式的个人健康监护系统的研究与开发[D]．成都：电子科技大学，2012． ZHANG Haijin. Personal Health Monitoring System Based on Embedded in the Research and Development[D]. Chengdu: University of Electronic Science and Technology of China,2012.

Research of digital information extraction from paper ECG based on thek-means algorithm

YAN Lei, LUO Jing

(Computer Management Center, Navy General Hospital, Beijing 100048)

Aiming at the problems of paper ECG in the clinical diagnosis, such as vulnerable to suffer different degrees of damage and inconvenient to save, the digitization of paper ECG is discussed. Averaging method is adopted to reduce noise, templates in two directions at 45° and 135°are added into Sobel algorithm, and the algorithm is improved byk-means method, then more accurate extracted ECG digital graphics are obtained. Actual verification shows that the digital extraction accuracy of ECG is promoted effectively, and the method is expected to be popularized and applied in medical practice.

other discipline of information processing technology; paper electrocardiogram(ECG); digital; ECG waveform;k-means

1008-1534(2016)04-0337-05

2016-05-18;

2016-06-12；责任编辑：陈书欣

闫 磊(1988—)，男，河北石家庄人，助理工程师，主要从事医院数字化信息研究方面的工作。

E-mail:ylei_mailbox@163.com

TP391;TP274

A

10.7535/hbgykj.2016yx04014

闫 磊，罗 晶.基于k-means的纸质心电图数字化信息提取研究[J].河北工业科技,2016,33(4):337-341. YAN Lei, LUO Jing.Research of digital information extraction from paper ECG based on thek-means algorithm[J].Hebei Journal of Industrial Science and Technology,2016,33(4):337-341.