融合余弦度量的书法字图像匹配算法

张龙海， 章夏芬， 韩德志， 毕 坤

(1.中海网络科技股份有限公司，上海 200135；2.上海海事大学 信息工程学院，上海 201306)



融合余弦度量的书法字图像匹配算法

张龙海1， 章夏芬2， 韩德志2， 毕 坤2

(1.中海网络科技股份有限公司，上海 200135；2.上海海事大学 信息工程学院，上海 201306)

对数字化书法作品检索的相关理论、方法及技术进行研究,提出一种新的融合余弦度量的形状匹配算法，通过把轮廓点间的余弦度量融合到欧氏距离中，更准确地反映出图像数据点之间的空间分布情况。试验结果表明，相对于采用基于欧氏距离的单一相似性度量匹配方法，融合余弦度量的形状匹配方法更能提高书法字检索的准确率。

欧氏距离；夹角余弦；书法字;数字图书馆

0 引 言

随着大数据时代的到来，承载着知识存储、检索、利用和开发重任的传统图书馆开始向更高效的数字图书馆转型。数字化技术的引入不仅使这些历史久远、日益“脆化”的书法瑰宝得以有效保存，而且可通过网络对传统文化进行传承与发展。然而，书法作品不同于标准的汉字，其存在笔画多样、作品多样、风格各异的特点，加之其通常时代久远，出现模糊与缺失，无法通过常规光学字符识别(Optical Character Recognition,OCR)技术进行检索识别。随着实际工作的开展，如何为用户提供快速准确的检索服务是计算机书法技术研究的一个难题。

数字化的书法字本质上就是图像，其检索实质上就是一种基于内容的图像检索(Content-Based Information Retrieval, CBIR)。然而,针对书法字本身的特点，只有形状才是其关键特征,颜色和纹理等都不是。因此，对书法字的检索实质是基于形状的图像检索。文献[1]提出一种基于书法字轮廓相似性的检索方法，根据欧氏距离度量书法字轮廓点之间的相似性。相似性度量是书法字精确匹配的基础，决定着检索效果的优劣。然而，基于欧氏距离的相似性度量只能描述两点间的直线距离，在高维空间的情况下并不能真实地反映出书法字轮廓点之间的空间分布情况。针对该问题，这里提出一种融合余弦度量的书法字形状匹配方法，以更好地反映出图像数据点之间的空间分布情况。

1 轮廓形状表征

1.1 轮廓特征提取

轮廓可很好地保留笔划宽度信息，不仅能较好地还原书法字的原始形状,而且能大大减少表示书法字所需的象素点个数。这里采用Canny最佳边缘检测算法[2]提取书法字轮廓。Canny算法通过二维高斯函数的一阶导数对图像进行平滑[3]。

1.2 轮廓特征极坐标分块

通过提取轮廓特征，可得到书法字对应的二值化轮廓图像。每个二值化的轮廓图像都对应一个由0和1组成的二维数组。因此，为便于对书法字进行轮廓相似度计算，需将这些无结构化的特征数据转化为能表征书法字轮廓形状特征的结构化数据。

采用极坐标分块法提取书法字每个轮廓点的特征，将待考察的轮廓点周围空间在方向上均分为8个角度，在半径上按近似log2r的长度划分为4份。即若书法字归一化大小为64×64像素，则各个分割点位于r=8，r=16，r=32和r=64的位置处。采用极坐标分块的方法将像素点间的距离因素和像素点间的方向关系很好地结合在一起，能有效地表征书法字的轮廓特征。图1为书法字原图像及相应的极坐标系，其共将周围空间分割为32块。

a) 原始书法字

b) 轮廓特征极坐标分块示意

与文献[1]中表征每块空间特征值的方法不同，这里采用计算每块空间点密度的方法来表征每块空间的特征值，降低整体形变带来的影响。

1.3 形状矩阵

按照上述方法，书法字的每个轮廓点都会产生32维特征属性值，则第i个轮廓采样点的32个属性值可表示为(ai1,ai2,ai3,…,ai32)。对于拥有n个轮廓点表征的书法字A={ai|i=1,2,…,n}，可构造一个n×32的特征矩阵：

(1)

2 融合余弦度量的形状匹配

传统的基于欧式距离的相似度计算仅能反映出2个轮廓点之间的直线距离差异。当维数变多时，可能无法反映出书法字轮廓点之间真实的空间分布情况。对此，提出一种融合余弦和欧氏距离度量的形状匹配算法。该方法通过把轮廓点间的夹角融合到欧氏距离中，更好地反映出图像数据点之间的空间分布情况，提高采样点向量间距离描述的准确性。

传统的基于欧氏距离来对2个轮廓点之间的相似性进行度量的算法如下。

对于样本字中的轮廓点Mi，在候选字中寻找对应点Nj，令D(Mi,Nj)为两点的近似匹配程度，则有

(2)

图2 基于欧氏距离的单一相似性度量方法

式(2)中:mi,k为样本字第i个轮廓点Mi的第k维的值;nj,k为候选字第j个轮廓点Nj的第k维的值。D(Mi,Nj)值越小，2个点就越相似。因此,对应点Nj是一种近似程度上的对应点，这说明基于欧氏距离的度量方法可能会存在多个解(见图2)。

在三维空间中，“三维球面”上包括特征向量N在内的所有点都与特征向量M的距离相等。欧氏距离主要反映两点间直线距离的度量，对特征向量的方向性并不敏感,在高维空间的情况下不一定能真实地反映出书法字轮廓点之间的空间分布情况。

2.1 向量间的夹角余弦

轮廓点在空间分布中的相似程度可由轮廓点之间的夹角余弦反映出来，夹角余弦值越大就越相似。目前，余弦相似度已被广泛应用到图像的相似性匹配中[4]。令样本字中第i个轮廓点Mi与候选字中第j个轮廓点Nj的近似匹配程度表示为cos(Mi,Nj)，则有

(3)

式(3)中:mi,k为样本字第i个轮廓点Mi的第k维的值;nj,k为候选字第j个轮廓点Nj的第k维的值。cos(Mi,Nj)值越大，2个点就越相似。

通过计算书法字轮廓间的夹角余弦来判断书法字图像的相似性增加了描述高维空间中书法字图像真实分布的准确度。因此，通过将轮廓点之间的角度信息融合到欧式距离中，增加了高维空间中轮廓点相似度判断的准确性，更真实地反映出轮廓点之间的空间分布关系。

2.2 融合余弦与欧氏距离的度量

通过融合夹角与欧氏距离，进行书法字轮廓数据点之间相似度的计算。该方法可同时兼顾采样点间距离与采样点向量间夹角两方面的相似性度量，能更好地反映出图像数据点之间的空间分布情况，提高采样点向量间距离描述的准确性。

令样本字中第i个轮廓点Mi与候选字中第j个轮廓点Nj的近似匹配程度用C(Mi,Nj)来表示，值越小就越近似。

(4)

式(4)中:mi,k为样本字第i个轮廓点Mi的第k维的值;nj,k为候选字第j个轮廓点Nj的第k维的值。

在上述融合夹角余弦与欧式距离的度量公式中，欧式距离部分的计算并没有采用式(2)所示的方法，而是在度量公式中加入mi,k+nj,k。这是因为式(2)中定义的方法没有考虑到区域本身所拥有的像素点个数。

令Si为样本字点Mi与对应点的匹配值，则有

(5)

图3为试验系统中采用不同相似性度量方法的轮廓点匹配效果对比,下方为样本书法字,上方为候选书法字,匹配点对的连线颜色代表相似度的大小，颜色越深相似度就越大。通过对比匹配结果可看出，采用融合余弦相似性度量方法的匹配效果整体上优于采用基于欧氏距离单一相似性度量方法的匹配效果。

a) 基于欧氏距离单一相似性度量方法

b) 融合余弦相似性度量方法

图4为试验系统中采用不同相似性度量方法的具体轮廓匹配点对查看。通过具体轮廓匹配点对查看可看出，对样本字轮廓坐标点(30，27)进行匹配时，采用基于欧氏距离单一相似性度量方法出现匹配错误的情况。图4a中，下方样本字“人”的轮廓坐标点(30，27)误匹配到上方候选字“人”的轮廓坐标点(28，29)上，即将样本字下边缘轮廓点错误地匹配到候选字的上边缘轮廓点中。而对于同一样本字轮廓坐标点(30，27)，采用融合余弦相似性度量方法则可准确地将其匹配到候选字的下边缘轮廓对应点上(见图4b)。

a) 基于欧氏距离单一相似性度量方法

b) 采用融合余弦相似性度量方法

样本字A与数据库中的候选字C的形状匹配值是其所有轮廓点的近似匹配值之和,即

(6)

3 试验结果与分析

3.1 数据获取与检索结果

这里所采用的原始书法页面图像和书法字图像来自于中美百万册数字图书馆CADAL[5]项目;试验采用VisualC++作为开发平台;PC配置Intel(R)Core(TM)i5-3470处理器，3.20GHz主频，8GB内存和Windows7操作系统。

图5a为对书帖样本字采用融合余弦相似性度量方法的检索结果样例,检索界面返回的是检索结果中最相似的前20个书法字，其中:第一行为用户提交的书法字图像样例；第二行和第三行为检索结果，并按相似度由高到低排序。图像下方数字为该字与样本字相似性计算的匹配值，匹配值越小就越相似。图5b为对相同书法字采用基于欧氏距离单一相似性度量方法的检索结果样例。

图5a中:前10个检索结果没有出现错误;前20个检索结果中的第17个和第18个出现被误识的“用”字，这是因为“用”字与“月”字在形状上较为相似。因此,在使用基于形状相似性的检索方法时会出现个别误检索的候选字。图5b中:前10个检索结果中的第9个出现被误识别的“危”字；前20个检索结果中的第17个出现被误识别的“石”字，第18个和第19个出现被误识的“用”字，第20个出现被误识别的繁体“興”字。通过对比检索结果可知，对书帖样本字采用融合余弦相似性度量方法的检索效果要优于采用基于欧氏距离单一相似性度量方法的检索效果。

a) 融合余弦相似性度量方法的检索结果

b) 基于欧氏距离相似性度量方法的检索结果

3.2 运行性能

为验证检索方法的总体运行性能，采用查全率、查准率及查询时间衡量运行性能。

(7)

(8)

式(7)和式(8)中：P1为查全率；P2为查准率；N为返回样本总数；nR为返回正确的样本数；NR为样本中正确的样本数；n为返回的样本数。

图6 2种相似性度量方法的平均查全率与平均查准率对比

用random函数随机选取数据库中30个书法字图像作为样本进行测试，剩下的6 676个书法字作为试验用的检索数据库。分别采用融合余弦相似性度量方法和基于欧氏距离的单一相似性度量方法进行检索。图6为随机选取的30个样本字采用2种相似性质量方法的平均查全率与平均查准率对比。

从图6中可看出，采用融合余弦相似性度量方法得到的平均查全率和平均查准率均高于基于欧氏距离的单一相似性度量方法。通过把轮廓点间的余弦度量融合到欧氏距离中，可更好地反映出图像数据点之间的空间分布情况，提高采样点向量间距离描述的准确性。

4 结 语

对基于形状的书法字匹配方法进行研究，构造出表征书法字图像的形状矩阵，并提出一种新的融合余弦度量的形状匹配算法，通过把轮廓点间的余弦度量融合到欧氏距离中，更准确地反映出图像数据点之间的空间分布情况。试验结果表明，相对于采用基于欧氏距离的单一相似性度量匹配方法，融合余弦度量的形状匹配方法更能提高书法字检索的准确率。研究过程中提取的能用数学公式表达的量化的书法特征和书法规律能促进书法艺术的教学与传播。该过程中检索算法的研究将为后续的模式识别和导航领域的研究提供参考。

[1] 章夏芬, 庄越挺, 鲁伟明, 等. 根据形状相似性的书法内容检索[J]. 计算机辅助设计与图形学学报, 2005, 17(11): 2565-2569.

[2] CANNY J. A Computational Approach to Edge Detection[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 1986,8(6):679-698.

[3] 王植,贺赛先. 一种基于Canny理论的自适应边缘检测方法[J]. 中国图象图形学报,2004,9(8):65-70.

[4] 谌德荣,孙波,陶鹏, 等. 基于核光谱角余弦的高光谱图像空间邻域聚类方法[J]. 电子学报,2008,36(10):1992-1995.

[5] Chinese Calligraphy Character Recognition of CADAL[EB/OL].[2016-03-10]. http://cadal.lib.sjtu.edu.cn/.

Calligraphic Character Shape Matching Algorithm Augmented with Angle Cosine Measurement

ZHANG Longhai1, ZHANG Xiafen2, HAN Dezhi2, BI Kun2

(1.ChinaShippingNetworkTechnologyCo.,Ltd.,Shanghai200135,China;2.InformationEngineeringCollege,ShanghaiMaritimeUniversity,Shanghai201306,China)

This paper proposes a new similarity measurement method based on the combination of Euclidean distance and angle cosine to better decide the spatial distribution of contour points set in a high dimensional space so as to improve the retrieval of calligraphy works. The experiments show that the proposed method is capable of recognize calligraphy characters with higher reliability than that the conventional similarity measurement solely based on Euclidean distance can achieve.

Euclidean distance; included angle cosine; Chinese calligraphy; digital library

2016-06-02

国家自然科学基金(61303100);上海海事大学校基金(20130467)

张龙海(1988—)，男，河南信阳人，助理工程师，硕士，研究方向为模式识别与图像处理。

1674-5949(2016)03-0084-05

TP391.41

A