基于密度与分形维数的数据流聚类算法探究.pdf

孙国栋 梅术正 汤汉兵 周振

摘 要： 为了保证基于同步触发双相机的仪表复杂字符识别中误识率为0，采用K最近邻算法对仪表字符特征进行训练分类，结合字符自身特点，提出最优特征提取与高宽维度选择方法，并设计实验获取1～4 096维密度特征的误识率与运行时间。实验结果表明，图像的密度特征总维度在230～260，高宽维度比接近1.4时，误识率为0的概率最大。该规律对采用KNN算法进行分类识别时最优密度特征维数选择具有一定指导意义。

关键词： 复杂仪表； 特征维数； 误识率； KNN算法； 密度特征； 最优特征

中图分类号： TN911.73?34； TP23 文献标识码： A 文章编号： 1004?373X（2018）16?0080?04

Abstract： The K?Nearest Neighbor （KNN） algorithm is adopted to train and classify the character features of the instrument to guarantee the zero error recognition rate during the complex character recognition of the instrument based on the double cameras with synchronous trigger. In combination with the features of the character， a method of extracting the optimum feature and selecting the width and height dimensions is proposed. An experiment was designed to obtain the error recognition rate and running time of 1～4096 dimensions density features. The experimental results show that when the total number of dimensions of the image density feature is 230～260 and the dimension ratio of height to width is close to 1.4， the probability of zero error recognition rate reaches the maximum. This rule has a certain guiding significance to the selection of the optimal density feature dimension when the KNN algorithm is used for classification and recognition.

Keywords： complex instrument； feature dimension； error recognition rate； KNN algorithm； density feature； optimum feature

国家计量单位需定期检测电力仪表以保证其测量精度，对标准表与被试表的读数进行直接比较是最常用的校对方法[1]，而两表的同步触发尤为关键。特别是对不含通信接口的仪表同步相对较难，因此通过同时触发双相机分别识别两表的读数成为了一种新的解决方案。为了保证仪表上复杂字符误识率[2]为0，有必要研究其字符特征提取与维度选择以保证100%的识别率与最低的运行时间。目前常用的字符特征有结构特征[3]和统计特征[4]。其中，结构特征包括圈、断点、交叉点、笔画、轮廓等；统计特征包括点的密度测量、矩、特征区域等。结构特征能描述字符的结构，误识率较低，但相对复杂[5]。统计特征算法简单，鲁棒性强，统计特征的分类器易于训练，且误识率低，但要提取能反映模式精细结构的特征[6]较难。K最近邻（K?Nearest Neighbor，KNN）分类算法[7?8]根据样本邻近性找出最近的K个训练样本作为其K近邻，并根据K近邻采用投票策略预测待分类样本类型[9]。其算法简单，无需估计参数，无需提前训练，适合于多分类问题。因此，本文采用KNN对儀表字符特征进行训练分类，结合字符特点，提出了最优特征提取与维度选择方法，并设计相关实验验证了其正确性。

1 识别流程与方法

识别的字符有‘0～‘9，‘C，‘D，‘m，‘V，‘*，‘H，‘K，‘Z，‘A，‘.，‘；，‘?共22类字符。其识别流程如图1所示。首先，建立字符图像库，并对字符库中图像归一化；然后，提取所有样本图像的特征，并采用KNN进行训练；最后，对测试图像进行分类，同时获取测试图像的误识率和运行时间以对所选特征进行性能分析。

1.1 图像特征分析

本文研究的密度特征是将图像分为n个大小相同的图像块，提取子图像块中白色像素的个数。若标准图像大小为64×64，则图像特征维数最小为1，最大为4 096。当选这两个极限特征维数时，字符误识率难以达到0。特征维数太少，特征区分度低；而特征维数太大，子图像块包含的像素过少，对图像噪声的鲁棒性低，且运算时间增大。故推测图像的特征维数在中间特定范围内误识率最优，稳定地保持在0。并且图像在高度和宽度方向上均分的个数也会导致识别准确率的变化。当图像的高度维数和宽度维数比值与原始图像的高宽比相似时，所选图像特征的区别度应该变大。

如图2所示，图像的大小为116×58，以字符5和2为例，将图像分为8等分，按照从左至右，从上到下对子图像块进行编号。图2a）与图2c）中，子图像按照图像的高宽比划分；图2b）与图2d）中，图像高度分为8等份，宽度划分为1份。可见图2a）和图2c）的图像区别很大；而图2b）和图2d）的特征向量基本相同，区别度很小。因此，推测字符子图像按照图像的高宽比及其字符结构划分会获得更好的效果。对图像库中1 100幅图像的高和宽进行统计，得到图3。从图3可知高宽比在[1.3，2.1]的分布最多。故断定图像的高度与宽度维数比在1.3～2.1范围内，字符识别准确率可能会较高。

1.2 建立图像数据库

KNN算法需要先通过图像库训练KNN模型，才能对测试图像库进行分类，统计误识率，故需建立训练图像库和测试图像库。电力仪表字符图像采集采用大恒MER?131?210U3C相机与50 mm镜头。在采集图像时，相机并非严格垂直电力仪表的屏幕，相机的光轴相对于屏幕的中垂线通常成一定角度。为了提高识别算法的鲁棒性，相机在不同角度采集仪表字符样本图像。采集过程如下：首先调整采集图像的ROI区域，使ROI只包含仪表屏幕中待识别字符部分，接着找到相机光轴[10]与ROI区域的中垂线平行位置作为正中间位置。在保证相机的光轴对准ROI中心点的情况下，水平左右旋转相机，使相机的光轴与中垂线夹角分别为±5°，±10°，总共确定5个位置，如图4所示。每个位置对每类字符采集20张图片，其中一半作为训练图像，另一半作为测试图像，总共得到22类字符，每类字符100张图像。图4中1号与5号位置因夹角最大得到的图像较“胖”；越靠近中间角度越小，图像则稍“瘦”。各种位置拍摄的图像对比效果如图5所示。

1.3 图像归一化

图像库中的图像大小不一，需对图像大小归一化。假设归一化后图像的大小为64×64个像素。设待提取特征的图像大小为128×128。考虑到128并不能够整除1～64，而选取1～64的最小公倍数作为归一化大小会导致运算量剧增。所以根据图像的维数x对图像的高宽取整。取整的公式为：

找到图像库字符图像中包含字符的最大外接矩形图像Rect，设Rect的高为Height，宽为Width，特征高度维数为HeightDim，宽度维数为WidthDim。

将高度维数和宽度维数代入式（1）中得到yH，yW。再比较yH /Height和yW/Width的大小，以Min（yH/Height， yW/Width）为比率缩放Rect，获得图像Rect1。接着把Rect1图像复制到大小为[yh×yw]空白图像的正中间，图像归一化完成。

1.4 特征提取

本文选用密度特征即将分割出的单个字符分成大小相同的多个子图像块，统计每个子图像块中白色像素的个数。设第i幅图像第j个子图像块的白色像素的个数为ni，j。总维数为nDim = HeightDim·HeightDim，则第i幅图像的特征为：

2 实验方案

为了对比在不同的特征维度以及同一特征维度下高度维数和宽度维数不同组合所得到的字符误识率，设计了以下实验。首先，确定KNN算法的参数k。k取太小，分类结果容易受噪声点影响；k太大，近邻中可能包含太多的其他类别的点，故取k为5。取高度方向的维数为1，宽度方向的维数为1，对图像归一化，用KNN算法训练图像并测试，记录实验的误识率以及运行时间。然后，依次将宽度方向的维数增加1，重复试验，直到宽度方向的维数为64。接着，再将高度维数增加1，重复上述实验直到高度维数和宽度维数均为64。最后得到4 096组误识率以及运行时间的实验数据以进行统计分析，找出最优特征维度及其高宽组合。

3 实验结果与分析

图6表示识别率为100%时，高度与宽度方向维数的分布情况。横坐标和纵坐标分别表示特征的高度和宽度方向的维数大小，从图中可以看出高度或宽度维数太小时，误识率达不到0。而高度维数或宽度维数很大时，识别率同样达不到100%。图7表示识别率为100%时，图像的特征维数的分布情况。从图中可以看出，当特征的总维数在[230，240]，[250，260]两个区间内时，识别准确率为100%的频次最多。图8表示识别率为100%时，图像的高度维数和宽度维数的比值分布情况。当图像高度维数和宽度维数的比率在1.4附近时，识别率达到100%的频次最多，这个最优比值在1.3～2.1之间，验证了之前的推断。图像的运行时间随图像的特征维数增加而增加，如图9所示。图中的时间为识别图像测试库中1 100张图像所耗时的总和。

4 结 语

针对电力仪表字符图像的结构特点进行分析，发现特征维数太大或者太小时，图像的误识率均不能达到0，故推断图像的特征维数在中间特定范圍内时误识率将稳定在0，并且最优特征高度维数和宽度维数将与图像的高宽比存在联系。实验统计取1～4 096维密度特征时KNN识别准确率与运行时间。结果表明，选取图像的密度特征维数在230～260，高宽比为1.4左右时，误识率达到0的概率最大。

参考文献

[1] 王达，杨朋威，张平，等.感应电条件下的电流互感器误差测试方法分析[J].内蒙古电力技术，2017，35（2）：75?78.

WANG Da， YANG Pengwei， ZHANG Ping， et al. Analysis of current transformer error test method under induced electricity [J]. Inner Mongolia electric power， 2017， 35（2）： 75?78.

[2] DODIG I， SRUK V， CAFUTA D. Reducing false rate packet recognition using dual counting bloom filter [J]. Telecommunication systems， 2017（1）： 1?12.

[3] 罗辉武，唐远炎，王翊，等.基于结构特征和灰度特征的车牌字符识别方法[J].计算机科学，2011，38（11）：267?270.

LUO Huiwu， TANG Yuanyan， WANG Yi， et al. License plate character recognition based on structural features and grayscale pixel features algorithm [J]. Computer science， 2011， 38（11）： 267?270.

[4] 孙中悦，周天荟.基于特征点统计特征的人脸识别优化算法[J].北京交通大学学报，2015，39（2）：128?134.

SUN Zhongyue， ZHOU Tianhui. A face recognition optimization algorithm based on statistical characteristics of feature points [J]. Journal of Beijing Jiaotong University， 2015， 39（2）： 128?134.

[5] 张爱娟.基于结构特征点的字符分割技术的研究[D].西安：西安电子科技大学，2014.

ZHANG Aijuan. Research on character segmentation based on structure feature points [D]. Xian： Xidian University， 2014.

[6] 张彤，肖南峰.基于BP网络的数字识别方法[J].重庆理工大学学报（自然科学版），2010，24（3）：43?47.

ZHANG Tong， XIAO Nanfeng. Character identification based on a BP neural network [J]. Journal of Chongqing University of Technology （Natural science）， 2010， 24（3）： 43?47.

[7] 刘雨康，张正阳，陈琳琳，等.基于KNN算法的改进的一对多SVM多分类器[J].计算机工程与应用，2015，51（24）：126?131.

LIU Yukang， ZHANG Zhengyang， CHEN Linlin， et al. Improved KNN?based 1?vs?all SVM multi?class classifier [J]. Computer engineering and applications， 2015， 51（24）： 126?131.

[8] ZHANG S， LI X， ZONG M， et al. Learning k for KNN classification [J]. ACM transactions on intelligent systems & technology， 2017， 8（3）： 1?19.

[9] 华辉有，陈启买，刘海，等.一种融合K?means和KNN的网络入侵检测算法[J].计算机科学，2016，43（3）：158?162.

HUA Huiyou， CHEN Qimai， LIU Hai， et al. Hybrid K?means with KNN for network intrusion detection algorithm [J]. Computer science， 2016， 43（3）： 158?162.

[10] KE Xizheng， LI Shiyan. Experimental study on optical axis alignment of the optical antenna under the spot broken [J]. Acta Photonica Sinica， 2017， 46（4）： 1?9.