脱机汉字识别的研究.doc

此文档收集于网络，如有侵权，请联系网站删除目 录摘要11.导言22.新的特征优劣量度标准23.噪声去除44.归一化预处理64.1.细化64.2.提取轮廓84.3.弹性网格94.3.1.矩形弹性网格94.3.2.扇形弹性网格124.4.改进的弹性网格145.汉字特征145.1.方向分解145.1.1.合取方向分解155.1.2.析取方向分解165.1.3.方向长度分解175.1.4.边缘检测分解195.1.4.1.Prewitt边缘算子205.1.4.2.Sobel边缘算子215.1.4.3.Kirsch边缘算子225.1.5.边缘梯度方向角分解235.1.5.1.Prewitt边缘梯度方向角分解245.1.5.2.Sobel边缘梯度方向角分解255.1.6.汉字特征的实验比较分析及改进265.2.Gabor方向分解365.3.黑像素分布特征385.4.不变矩特征385.4.1.Hu不变矩395.4.2.仿射不变矩395.4.3.不变矩实验416.分类器设计446.1.模板分类器456.2.神经网络BP网络分类器及改进476.3.神经网络LVQ网络分类器526.4.隐马尔可夫过程分类器537.总结55参考文献56毕业论文（设计）任务书58毕业论文（设计）考核表59脱机汉字识别的研究 摘要：本文提出了一种独立于分类器的特征优劣量度标准类间类内方差比，用其比较了用不同方法提取出的汉字特征的优劣，并改进了预处理和特征提取的方法，取得了更好的效果。对各种分类器用于汉字特征的分类识别做了实验比较，改进了BP神经网络分类器的结构，使其对类似汉字识别的超多类别分类有较好的效果。最后得到了一套可行的脱机汉字识别方案。关键词：脱机汉字识别 特征提取 分类器Abstract: This paper proposes a classifier-irrelevant feature measure, which is used to compare the diverse feature of Chinese character extracted by different methods. A meliorated method is proposed in pre-processing and feature extraction with improved efficiency. Various classifiers used in Chinese character recognition are compared by experiments. Improvements are also made to the BP neural network classifier for a better solution in the issue of categorization of excessive classes when dealing with Chinese character recognition. In the end, this paper comes to an applicable scheme of offline Chinese character recognition.Key words: Offline Chinese character recognition, Feature extraction, Classifier1. 导言在社会信息化的今天，大量的信息使用了计算机来存储、处理和传输。将纸质媒介上的信息输入计算机，最简便的方法就是使用扫描仪。但是，扫描进计算机的是图像，图像占用的空间大，而且查找、修改等处理都非常不便，传输也要花费大量的时间，没有体现出计算机强大的信息处理能力，因此有必要将图像中的汉字识别出来，用内码存储，这样对信息的各种处理都会非常方便，而且能节省大量的资源，包括存储空间和传输时间。让计算机自动地从图像中识别出汉字，就是本文研究的脱机汉字识别方法。汉字识别是模式识别的一个应用。汉字识别可分为联机汉字识别和脱机汉字识别两类。联机汉字识别，是把汉字写在一种叫手写版的设备上，由它将按时间采样的坐标序列输入计算机，再由计算机识别出汉字。脱机汉字识别，是把扫描入计算机的图像中的汉字识别出来，转换成汉字内码。联机汉字识别，因为其直接得到汉字的笔划顺序、方向以及提笔、落笔等信息，较脱机汉字识别更容易获得汉字结构，也就是说脱机汉字识别难度更大。脱机汉字识别的一般过程是，将扫描入计算机的汉字图像经去噪、行字切割、归一化等预处理后，对每个单字图像提取其特征，然后根据特征使用分类器对其识别，得到的类别就是识别结果，可进一步对其进行基于上下文语法的后处理，降低误识率。本文尝试探讨汉字图像去噪方法、各种特征提取方法以及不同分类器的优劣，并尝试找出一整套可行的汉字识别方案。本文没有涉及汉字行字切割和基于语法的后处理。本文处理的是二值化后的单字的图像，0代表白像素，1代表黑像素。2. 新的特征优劣量度标准在探讨汉字特征之前，先对特征优劣量度标准作一分析。如何评价两种特征提取方案的优劣？一般的方法是设计一个分类器，用从训练样本提取出来的某种特征训练分类器，然后用从测试样本提取出来的这种特征测试，可以获得正确识别率。正确识别率高的特征优秀。这个方法依赖整个识别过程，分类器的结构对其影响很大，有可能出现用不同分类器得到的好的方案不一致。特征的优劣应该是不依赖于分类器的。因此，我提出了一个新的特征优劣量度标准，这是不依赖于分类器的特征优劣量度标准。为获得独立于分类器的特征优劣量度方法，考虑何谓优秀的特征。同类别的样本提取出的特征的值尽可能接近，不同类别的样本提取出的特征的值尽可能有大的差异，这样的特征就能很好地表示出类别间的差异、类别内的共性，这就是好的特征。反之，若同类别的样本提取出来的特征的值有很大差异，而不同类别的样本提取出的特征的值差异却不大，那这样的特征就不能很好地区分类别了。用样本方差能量度这种差异的大小：各个样本的特征的值接近，表现为样本方差小；各个样本的特征的值差异大，表现为样本方差大。特征一般为矢量，标量看成是一维矢量。n个p维矢量(i=1,2n)的样本方差为其中为样本均值用每一类别中的所有样本特征的平均值作此类别的特征，m类就有m个矢量，用这m个矢量计算的样本方差就是类间方差，此值越大表明不同类别之间的特征的值差异越大。在每一类别中计算这类别所有样本的特征的方差，就是类内方差，m类就有m个方差，求它们的平均值，就是类内方差均值，此值越小表明同类别内样本的特征的值越接近。定义类间类内方差比（简称方差比）为类间方差除以类内方差均值，此值越大，表明这种特征越好。就以这个方差比作为特征优劣量度标准。设总共有m个类别，每个类别有n个样本，是第j类的第i个样本，是第j类的样本均值是所有m类样本均值的平均值方差比的数学表达式如下：注意，在求样本方差的时候需计算两个矢量的距离的平方，而这个距离的平方是与矢量的维数有关的，是每一维距离的平方的和，维数越多，求和项越多，也就是说维数越多，方差的值趋于越大，因此，这种方法只适应于比较两种维数相同的特征的优劣。对于维数不同的特征，仍然需要通过整个识别过程得到的正确识别率来比较，这时两种特征下的分类器因为特征的维数不同结构会显著不同了，这样得到的结果严格来说是特征加上此特征下的分类器共同作用下的结果。 方差比是一般的特征优劣量度方法，不仅适用于汉字特征的比较，只要两种特征的维数相同。3. 噪声去除手写的汉字会因墨与纸的关系而出现毛刺，也就是笔画边缘凹凸不平，而且笔画内部也会有空洞，这些与汉字无关的噪声如果不去除，会影响特征的提取，进而影响对其识别。对噪声的去除是很重要的预处理过程。中值滤波器具有能有效去除数字图像的噪声而又不会使图像中物体边界模糊的特点。它的一般算法为：1遍历图像的每一个像素，将它和与它相邻的八个像素的灰度排序，取排在中间的像素的灰度值作输出图像的这个像素的灰度。将其用于对汉字二值图像滤波，可以得到很简单的不需要排序的算法：遍历图像的每一个像素，计算它和与它相邻的八个像素中黑像素的个数，如果大于或等于5，则输出图像的这个像素为黑像素，否则为白像素。这是因为对二值图像的九个像素排序后，排在中间的像素为黑像素当且仅当九个像素中黑像素的总数大于或等于5。此算法的复杂度为O(9N)，N为图像的像素总数。每一个单字的图像像素若固定，例如6464，N则固定，此算法复杂度为常数。 图一是手写汉字的图像，每个字大小是6464像素。图二是用上述中值滤波器对其滤波的结果。可以看到，滤波后汉字的边缘光滑多了，一些多余的噪声点也去除了。图三是没有滤波就直接细化的结果，图四是滤波后再细化的结果。可以看到不滤波就直接细化的汉字骨架上有不少多余的短笔画，这是由于原汉字的毛刺造成的，这些多余的毛刺或者笔画中的空洞在细化后就会形成多余的短笔画，而滤波后再细化的汉字骨架就少了这样的毛刺笔画。中值滤波确能很好地去除汉字图像的噪音，包括笔画边缘的毛刺，复杂度又极低，因此中值滤波器可以作为汉字图像噪声去除的好算法。下面的实验使用的汉字图像都是经过中值滤波处理后的图像。图一：手写汉字图像 图二：中值滤波后的图像图三：未滤波直接细化的结果 图四：中值滤波后细化的结果4. 归一化预处理归一化预处理的目的是减少不同人写的字的差异，使不同风格的同一个汉字能提取出相近的特征。不同的特征提取方法需要的归一化预处理是不同的，下面先将不同的归一化预处理方法给出，第5部分汉字特征提取将比较这些归一化预处理在不同的特征提取方法中使用的效果。4.1. 细化细化的目的是为减少笔画粗细对汉字特征的影响。不同人写的同一个字提取出的特征应该尽可能相同，但不同人写的字粗细不同，同一个字内部笔画的粗细也会有不同，这些不同会影响提取出的特征。细化的思路是：反复遍历图像，删除处在边界上的满足条件的黑像素，直到得到保持原物体拓扑结构的单像素宽的线。细化的关键在于寻找可以删除的黑像素：处在边界上且删除后不会改变物体拓扑结构的黑像素可以删除。我通过分析，找到了如下的条件：NWNNEWPESWSSE图五：相邻像素的字母代号如上图，P为待处理的像素，其余八个像素是与P相邻的像素，它们的代号见图中的字母。如果P为0，则其不是黑像素，不用处理。如果P为1，N、E、S、W有一个是0，则P是边界点，考虑其能否被删除。又因为N、E、S、W地位相同，这里只讨论N为0的情况。如果与P相邻的八个像素至多有一个黑像素，则P是线段的端点，不能删除；如果S也为0，同时左边那列（NW、W、SW）至少有一个像素为1，右面那列（NE、E、SE）至少有一个像素为1，此时若删除P，将破坏黑像素的连通性，因此不能删；如果S为0，左边、右边两列中有一列全为0，另一列至多有两个1，那么P或者是端点或者删除会破坏黑像素连通性，不能删除；如果S为1，E和W为0，NW或NE为1，则删除P会破坏黑像素连通性，不能删除；如果S、E和NW为1，那么P或者是被包围的像素，或者删除后会破坏黑像素的连通性，不能删除；如果S、W和NE为1，那么P或者是被包围的像素，或者删除后会破坏黑像素的连通性，不能删除；否则P可删除。这是N为0的情况，对于E、S、W为0的情况，只需将其旋转就可得到删除条件。细化算法如下：做如下循环：1） 从图像开始遍历每个像素，若P为1，N为0，根据上面所述条件判断其是否应被删除，若应该删除，将其标记，遍历完后在原图像中将标记应被删除的1改为0；2） 从图像开始遍历每个像素，若P为1，E为0，根据类似上面所述条件判断其是否应被删除，若应该删除，将其标记，遍历完后在原图像中将标记应被删除的1改为0；3） 从图像开始遍历每个像素，若P为1，S为0，根据类似上面所述条件判断其是否应被删除，若应该删除，将其标记，遍历完后在原图像中将标记应被删除的1改为0；4） 从图像开始遍历每个像素，若P为1，W为0，根据类似上面所述条件判断其是否应被删除，若应该删除，将其标记，遍历完后在原图像中将标记应被删除的1改为0；直到没有黑像素被删除为止，退出循环。每个循环都对图像做四次遍历，这是因为如果四个方向的边界都在同一次遍历中细化会导致在物体拐角处出现多余毛刺边，所以我分四次遍历，每次删除一个方向的边界。这个算法的复杂度为O(4mn)，n是图像像素总数，对汉字图像，其固定，如6464，m是汉字笔画的最大宽度的一半，因此此算法复杂度是随汉字笔画宽度增加而线形增大的。用此算法细化汉字的结果见图三、图四。4.2. 提取轮廓提取轮廓也可以看成是一种细化方法，但其结果是使汉字的每个笔画成为两条边界线而不是细化后的一条线。提取轮廓算法比细化简单，当某黑像素周围八个像素都是黑像素时把它删除，则留下来的就是汉字轮廓。这是因为黑像素处于轮廓位置当且仅当与其相邻的八个像素不全为黑像素。算法如下：遍历图像的每一个像素，若其为黑像素，则计算与其相邻的黑像素总数，如果为八，则将其标记，遍历完后将标记了的像素的值改为0。可以看出，此算法不需要像细化那样反复遍历图像，复杂度比细化小，是O(8n),n是图像像素总数，对于汉字图像，其值固定，则复杂度是常数。用此算法提取的汉字轮廓见图六。图六：汉字轮廓提取结果4.3. 弹性网格弹性网格划分是为了消除汉字大小、位置、笔划粗细和局部扭转对识别的影响在提取特征之前作的预处理。4.3.1. 矩形弹性网格矩形弹性网格划分结果每个网格都是矩形。它使用密度均衡原则，将汉字分成MN的网格，水平方向上的M份每份的黑像素个数相等，垂直方向的N份也是每份的黑像素个数相等，这是全局矩形弹性网格；在此基础上，在每一个网格中，再进行同样的密度均衡划分，这就是局部矩形弹性网格。这样的划分可以不断地进行下去。每次划分作为一层，则全局矩形弹性网格是一层矩形弹性网格，局部矩形弹性网格是多层矩形弹性网格。这样的划分，将能适应汉字全局与局部的位移、缩放等变形，但网格不可以划分得太多，若太多则汉字局部划分太细模糊程度减小，不利于对不同风格汉字的容忍；网格也不能分得太少，若太少则汉字局部特征就会被抹杀掉了。2矩形弹性网格是多层的，可使用树结构。每个节点存储一个网格的左上角和右下角坐标以及子节点的指针。一个节点的所有子节点构成对这个节点所表示的网格的划分，子节点个数是动态的。矩形弹性网格划分的算法采用递归，如下：输入参数：层数layer,划分的行数M，划分的列数N,父节点指针开始：1） 子节点数为MN，申请MN个节点空间，将父节点的子节点指针指向它们；2） 计算父节点中的网格内黑像素的个数sum；3） 计算划分的M行每行的黑像素数sum/M；4） 根据每行的黑像素数对父节点的网格进行M行划分，将划分后的坐标记录在相应的子节点中；5） 计算划分的N列每列的黑像素数sum/N；6） 根据每列的黑像素数对父节点的网格进行N列划分，将划分后的坐标记录在相应的子节点中；7） 如果这是最后一层，则将所有子节点对应的网格输出至结果队列，否则对每一个子节点递归调用本算法，参数是：layer为下一层，划分的行列数为下一层的行列数，父节点就为此子节点；8） 将申请的空间释放；结束。结果队列的每个节点记录的就是最后划分好的每个网格的左上角和右下角坐标。对每一层的划分都要遍历三次图像的每个像素：第一次计算黑像素总数，第二次对其行划分，第三次对其列划分。所以时间复杂度是O(3mn)，n是图像像素总数，m是划分的层数。图七是矩形弹性网格的划分结果，可以看到，在划分的同一层中每行、每列的像素是均衡的像素密的地方划分的行数、列数也多。图八是矩形弹性网格对细化后的汉字划分的结果。 (a) (b) (c)图七：矩形弹性网格划分。(a)全局88矩形弹性网格 (b)两层矩形弹性网格：第一层22，第二层22 (c)两层矩形弹性网格：第一层33，第二层22(a) (b) (c)图八：矩形弹性网格对细化后的汉字划分。(a)全局88矩形弹性网格 (b)两层矩形弹性网格：第一层22，第二层22 (c)两层矩形弹性网格：第一层33，第二层224.3.2. 扇形弹性网格扇形弹性网格划分的结果是每一个网格都是扇形（扇环）。首先确定汉字图像黑像素的重心，然后从重心向外引射线和以重心为圆心作同心圆，射线与同心圆相交，就构成了扇形网格。以黑像素均衡为原则作射线与同心圆，也就是说相邻两条射线之间的每个部分的黑像素的个数相等，相邻两个同心圆之间的每个圆环的黑像素的个数相等，这就是扇形弹性网格。3扇形弹性网格的划分可以转换为矩形弹性网格的划分。可以将直角坐标转换为极坐标的方法用于此，将直角坐标的图像变换成极坐标的图像，然后在极坐标的图像上使用矩形弹性网格划分，相应于原来的图像就是扇形弹性网格划分。如果使用多层矩形弹性网格对极坐标图像划分，那么相应于原来的图像就是多层扇形弹性网格划分，也称为局部扇形弹性网格划分。极坐标图像横轴是离原点的距离，纵轴是与正方向的夹角。将直角坐标的图像转换成极坐标的图像的方法如下：1）首先找到图像黑像素的重心。2）以重心作为极坐标圆点，以水平向右作为极坐标正方向。为求出极坐标图像，遍历每一个带求的像素，u是距离，v是夹角，根据下式计算其值：g是待求的极坐标图像，f是原图像。上面等式右边有一个因子u，其意义是如果黑像素与重心的距离为N，则在极坐标相应位置有N个黑像素，这是因为图像是离散的。此算法的复杂度是O（3m+n），m是原图像的像素数，n是极坐标图像的像素数，这是因为求图像重心的时间复杂度是O（3m），求极坐标图像的时间复杂度是O(n)。转换成极坐标图像后就可以用4.3.1节的矩形弹性网格划分的算法对极坐标图像进行划分了。 图九是扇形弹性网格划分结果。图十是扇形网格对细化后的汉字划分的结果。(a) (b) (c)图九：扇形弹性网格划分。(a)全局88扇形弹性网格 (b)两层扇形弹性网格：第一层22，第二层22 (c)两层扇形弹性网格：第一层33，第二层22(a) (b) (c)图十：扇形弹性网格对细化后汉字划分 (a)全局88扇形弹性网格 (b)两层扇形弹性网格第一层22第二层22 (c)两层扇形弹性网格第一层33第二层224.4. 改进的弹性网格上面描述的弹性网格算法对图像划分的网格是互斥的，任何相邻的网格都不相交。然而，手写汉字笔画变形是很严重的，不同人写的同一汉字的某一笔画通过弹性网格算法划分入不同的网格的可能性是很大的。因此，我将弹性网格做一改进：考虑相邻网格部分重叠，使原来在网格边界的笔画划分入两个网格，以减少笔画位移带来的同一汉字网格划分的差异。4.3.1节的弹性网格划分算法的改进算法如下：在对图像划分时水平方向、垂直方向都做两倍的划分，这时在水平方向和垂直方向上的每两个网格就是原来互斥的每一个网格；划分完后增加网格合并步骤：在水平和垂直方向上每隔两个网格取四个网格作为一个新网格，但在图像的边界部分取三个网格作为一个新网格。这样相当于原来互斥的网格向相邻网格“扩张”，“扩张”部分与相邻网格对自己的“扩张”共同构成了重叠。鉴于网格划分算法的时间复杂度与划分的网格数无关，而在网格合并时只需对划分的网格做一次遍历，网格数远小于图像像素数，故此改进的算法复杂度没有增加。5. 汉字特征汉字特征有两大类：结构特征和统计特征。汉字可以分解为偏旁部首，偏旁部首可以分解为笔画，笔画又可以分解为方向不变的笔段，这种使用文法分析的方法将汉字一级一级的分解得到的特征就是汉字的结构特征。但由于汉字结构复杂，手写汉字的笔画多余或缺失都很常见，而且变形严重，因此结构特征提取困难，识别率也不高，现在很少单独采用，往往采用统计特征，或者两类特征结合。汉字蕴含着丰富的结构信息，本文不单独采用统计特征，而是将统计特征与结构特征结合。5.1. 方向分解汉字有横、竖、撇、捺四种基本方向的笔画。汉字方向分解就是把一个汉字图像分解成四幅图像，每幅图像只含横、竖、撇、捺四个方向的笔画中的一个，每个图像称为某方向的子图像。这是一种简单有效的结构特征。在方向分解后再在四个方向的图像上提取统计特征，这样就利用了汉字的结构信息，将结构特征和统计特征结合了起来。方向分解有不同方法，下面分别论述之。另外，Gabor滤波也是一种方向分解方法，在5.2节中对其深入探讨。5.1.1. 合取方向分解这是根据与黑像素相邻的八个像素的情况决定其属于哪个方向子图像的方法。如图五，P是待处理的黑像素，如果E和W都是黑像素，则P分入横方向子图像；如果S和N都是黑像素，则P分入竖方向子图像；如果NE和SW都是黑像素，则P分入撇方向子图像；如果NW和SE都是黑像素，则P分入捺方向子图像4。算法如下：遍历图像每个像素，对黑像素，分别判断上面四个条件是否成立，若成立则将其分入相应方向的子图像中。这四个方向的条件是并行的，若同一个像素满足不止一个条件时则将其分入不止一个方向的子图像中。由于条件是合取形式，例如横方向的条件是“E是黑像素”合取“W是黑像素”，因此称这种方法为合取方向分解。这个算法的时间复杂度是O（4n）,n是图像的像素总数，对于固定大小的汉字图像，复杂度是常数。用这种方法分解的结果见图十一。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。图十一：对提取轮廓后的汉字做合取方向分解的结果5.1.2. 析取方向分解这也是根据与黑像素相邻的八个像素的情况决定其属于哪个方向子图像的方法。如图五，P是待处理的黑像素，如果E或W是黑像素，则P分入横方向子图像；如果S或N是黑像素，则P分入竖方向子图像；如果NE或SW是黑像素，则P分入撇方向子图像；如果NW或SE是黑像素，则P分入捺方向子图像4。算法如下：遍历图像每个像素，对黑像素，分别判断上面四个条件是否成立，若成立则将其分入相应方向的子图像中。这四个方向的条件也是并行的，若同一个像素满足不止一个条件时则将其分入不止一个方向的子图像中。由于条件是析取形式，例如横方向的条件是“E是黑像素”析取“W是黑像素”，因此称这种方法为析取方向分解。这个算法的时间复杂度也是O（4n）,n是图像的像素总数，对于固定大小的汉字图像，复杂度是常数。用这种方法分解的结果见图十二。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。图十二：对提取轮廓后的汉字做析取方向分解的结果5.1.3. 方向长度分解某一笔画若属于某方向，则在这一方向上的连续相邻的黑像素个数就会比其它方向上连续相邻的黑像素个数多。黑像素的某一方向长度是指与这个黑像素在某一方向连续相邻的黑像素的总数。有四个方向的方向长度：横、竖、撇、捺方向长度。对黑像素，统计出其四个方向的方向长度，将其分入最长的长度对应的方向，若次长的长度超过汉字的笔画宽度，一般为一个固定的经验值，那么也将其分入这个次长长度对应的方向2。这个经验值对于6464点阵的汉字图像，一般取5-10，我在实验中用6。算法如下：遍历图像每个像素，对黑像素， 1）统计在它右边连续相邻的黑像素的总数，统计在它左边连续相邻的黑像素的总数，两者之和就是此黑像素横方向长度；2）统计在它上边连续相邻的黑像素的总数，统计在它下边连续相邻的黑像 素的总数，两者之和就是此黑像素竖方向长度；3）统计在它右上连续相邻的黑像素的总数，统计在它左下连续相邻的黑像素的总数，两者之和就是此黑像素撇方向长度；4）统计在它左上连续相邻的黑像素的总数，统计在它右下连续相邻的黑像素的总数，两者之和就是此黑像素捺方向长度；将上面四个长度排序，将此像素分入长度最大的方向，如果次大值大于汉字笔画宽度的经验值，也把它分入次大的方向。在用此方法分解之前，不能对汉字作细化或者提取轮廓处理，因为此方法提取的是笔画内部连续像素的特征，而不是骨架或轮廓的特征。这个算法的时间复杂度为O()，a是图像每边的像素个数，这是因为汉字图像的总像素为aa，需要遍历每个像素，对每个像素，与其相邻的某方向的最大连续像素总数为a，因此复杂度即为O()。对于汉字图像，图像每边的像素个数固定，则复杂度也是常数，但比上面的算法大些。用这种方法分解的结果见图十三。图十三：方向长度分解结果为适应笔画形变，可将此算法作一小改进，就是在遍历的时候先不将黑像素分入某方向，而将四个方向长度记录下来，在遍历完后，再一次遍历图像，这时取出黑像素及其相邻的八个像素的最长的方向长度，对应的方向作为此黑像素的方向，如果在剩下的三个方向中的最大的方向长度大于笔画宽度的经验值，也把它分入此方向。称此方法为改进的方向长度分解法。复杂度与原算法差不多。用这种方法分解的结果见图十四。图十四：改进的方向长度分解结果它们的优劣见5.1.6节各种方法优劣的实验比较分析。5.1.4. 边缘检测分解对图像中每个像素求0, ,四个方向的方向导数，垂直于最大方向导数的方向就是图像中物体边缘的方向。用不同方向的离散偏微分算子边缘检测算子对图像进行卷积就可以得到图像中物体边缘的方向。对于离散的图像，假设f(x,y)是原图像，g(x,y)是卷积核，f与g的卷积是：如果卷积核是33矩阵，则卷积运算时间复杂度是O(9n)，n是图像的像素总数，对于固定大小的汉字图像，复杂度是常数。5.1.4.1. Prewitt边缘算子Prewitt边缘算子是33的矩阵，图十五至图十八就是Prewitt边缘算子5。对每个像素，分别用这四个矩阵做卷积，取出四个值的绝对值的最大者，若其是由图十五矩阵做卷积的结果，则此像素分入横方向；若其是由图十六矩阵做卷积的结果，则此像素分入竖方向；若其是由图十七矩阵做卷积的结果，则此像素分入撇方向；若其是由图十八矩阵做卷积的结果，则此像素分入捺方向4。用这种方法分解的结果见图十九。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。-101-101-101图十六：Prewitt边缘算子之二-1-1-1000111图十五：Prewitt边缘算子之一 0-1-110-1110图十八：Prewitt边缘算子之四-1-10-101011图十七：Prewitt边缘算子之三图十九：Prewitt边缘分解结果5.1.4.2. Sobel边缘算子Sobel边缘算子是33的矩阵，图二十至图二十三就是Sobel边缘算子5。对每个像素，分别用这四个矩阵做卷积，取出四个值的绝对值的最大者，若其是由图二十矩阵做卷积的结果，则此像素分入横方向；若其是由图二十一矩阵做卷积的结果，则此像素分入竖方向；若其是由图二十二矩阵做卷积的结果，则此像素分入撇方向；若其是由图二十三矩阵做卷积的结果，则此像素分入捺方向。用这种方法分解的结果见图二十四。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。-101-202-101图二十一：Sobel边缘算子之二-1-2-1000121图二十：Sobel边缘算子之一 0-1-210-1210图二十三：Sobel边缘算子之四-2-10-101012图二十二：Sobel边缘算子之三图二十四：Sobel边缘分解结果5.1.4.3. Kirsch边缘算子Kirsch边缘算子也是33矩阵，它有八个矩阵，如图二十五至图三十二5。对每个像素，分别用这八个矩阵做卷积，取出八个值的绝对值的最大者，若其是由图二十五或图二十六矩阵做卷积的结果，则此像素分入横方向；若其是由图二十七或图二十八矩阵做卷积的结果，则此像素分入竖方向；若其是由图二十九或图三十矩阵做卷积的结果，则此像素分入撇方向；若其是由图三十一或图三十二矩阵做卷积的结果，则此像素分入捺方向。用这种方法分解的结果见图三十三。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。555-30-3-3-3-3图二十六：Kirsch边缘算子之二-3-3-3-30-3555图二十五：Kirsch边缘算子之一 -3-35-305-3-35图二十八：Kirsch边缘算子之四5-3-350-35-3-3图二十七：Kirsch边缘算子之三-3-3-3-305-355图三十：Kirsch边缘算子之六55-350-3-3-3-3图二十九：Kirsch边缘算子之五 -355-305-3-3-3图三十二：Kirsch边缘算子之八-3-3-350-355-3图三十一：Kirsch边缘算子之七图三十三：Kirsch边缘分解结果5.1.5. 边缘梯度方向角分解可以求出笔画的边缘梯度方向角，根据角度将笔画分入不同的子图像中。对图像上的每一个像素首先用边缘检测算子卷积求出水平方向和垂直方向的偏导数Dx和Dy，arctan()就是梯度方向角，梯度方向角与汉字笔画方向垂直。当梯度方向角落在)时此像素分入捺方向，当其落在-)时此像素分入竖方向，当其落在-)时此像素分入撇方向，否则此像素分入横方向。另外，将横、竖、撇、捺都逆时针旋转，以适应人手写习惯例如横笔画会向右上倾斜，因此还可以这样划分：当此值落在)时此像素分入捺方向，当此值落在)时此像素分入竖方向，当此值落在-)时此像素分入撇方向，否则此像素分入横方向。称此法为改进的边缘梯度方向角分解。这两种方法哪个好见下面对实验的讨论。65.1.5.1. Prewitt边缘梯度方向角分解对图像的每个像素，用图十五的矩阵做卷积，就得到Dy，用图十六的矩阵做卷积，就得到Dx，然后用上面说的办法分解即可。用这种方法分解的结果见图三十四和图三十五。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。图三十四：Prewitt边缘梯度方向角分解图三十五：改进的Prewitt边缘梯度方向角分解5.1.5.2. Sobel边缘梯度方向角分解对图像的每个像素，用图二十的矩阵做卷积，就得到Dy，用图二十一的矩阵做卷积，就得到Dx，然后用上面说的办法分解即可。用这种方法分解的结果见图三十六和图三十七。这种分解方法的优劣见5.1.6节各种方法优劣的实验比较分析。图三十六：Sobel边缘梯度方向角分解图三十七：改进的Sobel边缘梯度方向角分解5.1.6. 汉字特征的实验比较分析及改进实验使用三套手写汉字样本和四套印刷体汉字样本。每套样本含国标一级字库3755个汉字图像，每个汉字是6464点阵图像。三套手写汉字样本分别是三个不同的作者手写3755个汉字的图像；四套印刷体汉字样本分别是宋体、仿宋体、黑体和楷体一级字库汉字图像。优劣比较标准用第2部分论述的类间类内方差比对相同维数的矢量特征，方差比大的方法优秀。汉字特征采用弹性网格黑像素分布统计特征。对黑像素分布统计特征的讨论详见5.3节，此处简单说明一下。首先对汉字进行弹性网格划分，然后对汉字进行方向分解，再把网格应用到其分解出的四个方向的子图像上，统计每个网格中的黑像素占这个子图像总像素的比例，四个子图像的所有网格的比例值共同构成的矢量作为特征。全局88网格的特征是256维矢量；局部两层网格，第一层22，第二层22的特征是64维矢量，下面简写为局部两层22|22网格；局部两层网格，第一层33，第二层22的特征是144维矢量，下面简写为局部两层33|22网格。首先实验矩形弹性网格划分。实验的汉字方向分解方法是细化后合取分解、细化后析取分解、提取轮廓后合取分解、提取轮廓后析取分解、方向长度分解及其改进、三种边缘分解（Prewitt、Sobel、Kirsch）、细化后三种边缘分解（Prewitt、Sobel、Kirsch）、提取轮廓后三种边缘分解（Prewitt、Sobel、Kirsch）、两种边缘梯度方向角分解（Prewitt、Sobel）及它们的改进、细化后两种边缘梯度方向角分解（Prewitt、Sobel）及它们的改进、提取轮廓后两种边缘方向角分解（Prewitt、Sobel）及它们的改进。考虑到使用边缘算子对原汉字的分解（包括边缘分解和边缘梯度方向角分解）实际上分解的是原汉字的轮廓，因此我提出一种新的方法：在以均衡为原则划分网格时不使用原汉字来划分，而使用提取轮廓后的汉字来划分，然后在方向分解时使用原汉字分解，称这样改进的方法为“轮廓边缘”，意即轮廓汉字网格划分，原汉字基于边缘算子的方向分解。不同分解方法的方差比数据见下面的表格。表一(a)和(b)分别是对三套手写汉字和四套印刷体汉字提取的局部两层22|22网格的64维矢量特征计算结果；表二(a)和(b)分别是对手写汉字和印刷体汉字提取的局部两层33|22网格的144维矢量特征计算结果；表三(a)和(b)分别是对手写汉字和印刷体汉字提取的全局88网格的256维矢量特征计算结果。合取析取方向长度改进方向长度Prewitt边缘Sobel边缘Kirsch边缘Prewitt方向角改进Prewitt方向角Sobel方向角改进Sobel方向角原汉字/0.9550.9090.9871.1771.0791.2101,1961.2091.196细化后0.8001.045/0.8411.0620.8061.0711.0571.0761.076提取轮廓1.0401.046/0.9501.1280.9561.1581.1491.1621.163轮廓边缘/0.9741.1821.0411.2161.2041.2131.204表一(a)：手写汉字局部两层22|22网格64维矢量特征各种分解方法方差比合取析取方向长度改进方向长度Prewitt边缘Sobel边缘Kirsch边缘Prewitt方向角改进Prewitt方向角Sobel方向角改进Sobel方向角原汉字/1.4251.3531.4921.7851.6331.9051.9051.8781.908细化后1.1051.811/1.3851.8361.0631.8921.9101.9201.911提取轮廓1.7111.173/1.4931.7721.3771.9441.9231.9281.986轮廓边缘/1.6632.1061.8382.2952.2942.2522.298表一（b）：印刷汉字局部两层22|22网格64维矢量特征各种分解方法方差比合取析取方向长度改进方向长度Prewitt边缘Sobel边缘Kirsch边缘Prewitt方向角改进Prewitt方向角Sobel方向角改进Sobel方向角原汉字/0.8780.8440.8761.0270.9431.0511.0381.0491.038细化后0.7370.934/0.7670.9350.7340.9430.9340.9490.946提取轮廓0.9190.948/0.8480.9800.8621.0081.0011.0121.011轮廓边缘/0.8591.0260.9131.0501.0391.0481.039表二(a)：手写汉字局部两层33|22网格144维矢量特征各种分解方法方差比合取析取方向长度改进方向长度Prewitt边缘Sobel边缘Kirsch边缘Prewitt方向角改进Prewitt方向角Sobel方向角改进Sobel方向角原汉字/1.2571.1871.1461.3671.2501.4471.4441.4291.446细化后0.9341.532/1.0961.4390.8811.4851.4891.5121.502提取轮廓1.3861.051/1.1721.3891.1171.5151.4961.5041.540轮廓边缘/1.2751.6191.4261.7521.7441.7211.747表二(b)：印刷汉字局部两层33|22网格144维矢量特征各种分解方法方差比合取析取方向长度改进方向长度Prewitt边缘Sobel边缘Kirsch边缘Prewitt方向角改进Prewitt方向角Sobel方向角改进Sobel方向角原汉字/0.8180.8000.8160.9450.8680.9650.9540.9640.954细化后0.6890.833/0.7190.8670.7020.8660.8590.8710.868提取轮廓0.8360.872/0.7930.9130.8170.9280.9210.9300.927轮廓边缘/0.7980.9310.8390.9490.9390.9470.939表三(a)：手写汉字的全局88网格256维矢量特征各种分解方法的方差比合取析取方向长度改进方向长度Prewitt边缘Sobel边缘Kirsch边缘Prewitt方向角改进Prewitt方向角Sobel方向角改进Sobel方向角原汉字/1.1591.1021.0021.1921.0871.2541.2491.2381.250细化后0.8551.358/0.9981.3390.8201.3561.3591.3811.367提取轮廓1.1941.058/1.0651.3021.0571.3731.3561.3621.386轮廓边缘/1.1111.3871.2301.4871.4791.4611.481表三(b)：印刷体汉字全局88网格256维矢量特征各种分解方法的方差比比较上面三个表的每个表中的数据，可以得到以下结论：1、 印刷体汉字的方差比比手写汉字大。这是由于印刷体汉字工整，变形小。2、 改进的方向长度分解法并不比方向长度分解法优异。基于方向长度的方法不比其它方法优异，这是因为方向长度是基于笔画内部的黑像素的，不能在细化或轮廓提取后使用，受笔画粗细的影响比较大。3、 提取轮廓和细化效果相近，除了印刷体汉字的析取方向分解、Sobel方向分解外提取轮廓的效果略微比细化好。而提取轮廓只需遍历一次图像，时间复杂度远比需要遍历多次图像的细化小。4、 合取分解、析取分解的方差比比基于边缘算子的边缘分解和梯度方向角分解小。从上面的分解子图像可以看出，对于合取分解和析取分解，它们分解结果精确度高，对汉字变形的容忍程度就小了，相比之下，基于边缘算子的分解方法获得的笔画方向精确度不高，正是这种“模糊”使其对汉字变形容忍程度增大了。5、 基于边缘算子的方法边缘分解和边缘梯度方向角分解对汉字是否细化不敏感。这是因为使用边缘算子滤波实际上是在轮廓上将汉字分解，轮廓是无所谓宽度的。每个笔画有两个轮廓，如果在提取轮廓之后再进行边缘滤波，则每个笔画就会产生四个轮廓，从表中看出效果也是和细化后分解、原汉字直接分解很接近。甚至对手写汉字使用原汉字直接分解的效果比细化和提取轮廓后再分解还要好。因此对于基于边缘算子的方法没有必要先将汉字进行细化或轮廓提取。6