基于试探的未知类别聚类的识别算法应用研究

张 飞

(安徽广播电视大学 计算机系，安徽 阜阳 236000)

长期以来手写字体识别技术是图像处理领域的研究重点，不仅在交通运输、刑侦、智能农业上有着广泛的应用，在学习网络、机器学习等模式识别领域也占据着十分重要的地位[1].手写字体识别技术有很多，包括卷积神经网络、机器视觉、深度学习、BP算法等[2-5].罗麟等人利用精简化网络层次的卷积神经网络对低质量笔迹图像进行特征识别，避免了神经网络受制于原图学习模式的限制问题[2].陈施硕通过机器视觉技术对手写字体轮廓边缘特征进行提取识别，与传统试卷手写字体分数识别方法相比更省时省力，但对于小字体或模糊字体的轮廓特征提取精准度较低[4].陈子宁借助BP算法(人工神经网络)对手写脱机字符进行模式识别，通过log-sigmoid函数设计隐含层神经元能够准确对手写字母进行分类识别，但是汉字数量大，分类和识别效果不好[5].目前仍没有一套很完善的识别算法，真正的无限制手写体字符识别的研究还有待进一步加强.同时，类似于神经网络、BP算法、主成分分析等深层次算法尽管可以获取高精度的图像识别效果，但对于编程和软件具有较强的依赖性因而限制其发展[6-8].而类别聚类算法的识别技术是通过数据集的相似性样本进行归类的识别算法，利用距离标准化处理消除特征之间量纲差异从而实现字体的识别[9].本文依据聚类寻找标准模式，建立基于试探的未知类别聚类算法的手写字体识别系统.通过手写字体与编制字体的数字特征提取，结合聚类分析的模式相似性测量实现目标字体的有效识别，为建立高效手写字体聚类识别技术奠定基础.

1 聚类算法的概述

1.1 基于试探的未知类别聚类算法

基于试探的未知类别聚类算法是一种简单的运算方法，定义误差平方和为：

(1)

其中，M是聚类中心的个数，M应该小于样品的总个数；wi是聚类中心；Xwi是wi的重心；针对所有样品假设某种分类方案，计算J值最小的那一种分类方案，则认为该种方法为最优分类.

1.2 模式相似性测量

(1)样品与样品之间的距离

假设两个样品特征值分别为Xi，Xj，即

Xi=(Xi1,Xi2,…Xim)T，Xj=(Xj1,Xj2,…Xjm)T,

(2)

为了评定两个样品是否属于同一类，可以通过两个样品之间的距离进行判断，距离的大小决定了样品的类别归属[10].样品距离计算的方法有很多种，包括二值法、夹角余弦法、欧式距离法等[11].本文主要研究欧式距离法.计算公式如下所示：

(3)

Dij越小则两个样品距离越近，就越相似.

(2)样品与类之间的距离

假设ω代表某类样品的集合，ω中有n个样品，X是某一个待测样品.样品与类之间的距离可描述为：

(4)

2 识别系统的设计与实现

利用vc++6.0环境进行手写体数字识别系统设计，如图1所示.该系统横向主要分为字体输入、预处理、特征提取、分类决策和结果输出5个部分；纵向可分为未知类别模式的分类和分类器的训练两个部分.其中未知类别模式的分类，主要用于对手写字体的数据特征提取分类，而分类器的训练主要通过已有的标准字体对手写字体进行训练，利用固有的判别函数对分类决策进行误差分析，从而实现准确的聚类识别.

图1 手写体数字识别系统结构

2.1 数字的录入

本系统为处理的聚类问题提供了2种数据录入方式，分别为手写字体输入和标准字体输入.以随机书写数字1、2、4、3、5、1、2、5、8、4、3为例，进行识别系统识别能力考察，如图2所示.

(a) 标准数字录入

(b)手写数字录入图2 数字录入示例

其中，手写录入通过按住鼠标左键，在左视图中移动鼠标，可以输入手写数字.手写数字的笔画必须连续，不能断裂，否则将被认为是不同的数字.部分代码实现如下：

void CModeView∷OnLButtonDown(UINT nFlags,CPoint point)

lButtonDown=true；

CView∷OnLButtonDown(nFlags,point)；

void CModeView∷OnMouseMove(UINT nFlags,CPoint point)

if (stateDoc && lButtonDown)

if (point.x>4 && point.x+34 && point.y+4

CRect rc；

rc.left=point.x-5；

rc.right=point.x+5；

rc.top=point.y-5；

rc.bottom=point.y+5；

for(int x=point.x-4；x

for(int y=point.y-4；y

if((x-point.x)*(x-point.x)+(y-point.y)*(y-point.y)<25)

if (statePen)

2.2 图像的标识及特征提取

图像的标识是通过连通域判别的方式进行.其中，图像中与像素(x，y)对应的点集合{(x+p，y+q)；((p，q)是一对有意义的整数)}称之为像素(x，y)的邻域.一般可以分为4邻域和8邻域.而有像素f(x，y)=f(x+i，y+j)，i，j在图像区域R内存在，f(x，y)与f(x+i，y+j)路径中的邻接点存在4点邻域连通成分(如图3)或8点邻域连通成分(如图3)，则点f(x，y)与f(x+i，y+j)连通.在图像内可能存在多个连通成分，每个非连通成分都对应一个目标图像区，给各目标图像区分配相应标号的工作称为标记.在二值图像中进行物体标识，采用8连通域判别方法，如图3所示，图中有A，B，C 3个不连通的物体.

图3 物体标识示意图

对各个样品进行标号，检测缓冲区，从左到右、从上到下，依次检测每个像素，如果发现某像素点像素值小于阈值T，则依次检测该点的右上、正上、左上及左前共4个点的像素值，根据前面介绍的8个准则进行连通性的判断，并标识物体，将物体的像素值改为标号.依次逐行检测至扫描结束.获得各个样品所在位置及编号.在上述基础上，将每个物体分成7*7等份，计算每一等份中黑像素所占比例，作为特征值，因此，每个物体提取了49个特征.调用voidCCluster∷CalFeature(int index,CPoint It,CPoint rb)函数，获得所有样品特征放入m_pattern的特征值中，m_pattern是样品的特征数据结构.

2.3 基于试探的未知类别聚类算法的识别结果

设有n个样品X1,X2,…Xn，patternnum=n.选一个样品作为第一个聚类中心C1，不妨令C1=X1.Centernum记录当前中心的数目，centernum=1.通过对话框读入阈值T，输出所有样品之间的最大与最小距离为T的参考.对所有样品，计算该样品m_pattern[i]到所有聚类中心m_center[j]的距离，找到最小值Dj(0≤j

图4 聚类结果

从图4中可以看出，手写数字1、2、4、3、5、1、2、5、8、4、3聚类后总共分为6类，分别为1、2、4、3、5、8.而数字4和3存在两个数字重复，在类别上分别为类别3和类别4；所有的数字识别和分类均准确，准确率达到100%，说明该聚类识别系统的手写数字识别效果还是满足实际需求的.

3 结 论

将聚类法应用于手写体数字识别是聚类法研究最为成功的方面之一，它为手写体数字识别提供了一种新的、行之有效的方法.本文对手写数字特征进行提取，采用最邻近规则算法进行聚类分析，并运用VC++语言编写数字手写识别系统，加强对聚类法应用方面的认识和实际运用能力.但由于最邻近规则的试探法受到阈值T的影响很大，造成系统设计应用新的识别算法的识别率不高，后续应该深化降低对阈值T影响的程度.