自适应书法字图像匹配和检索

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

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



自适应书法字图像匹配和检索

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

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

为了解决基于形状匹配的书法字检索计算量大、耗时长、效率低的问题,提出根据样本字特征动态改变剪枝范围的自适应匹配法.离线统计分析数据库中书法字的各特征值分布范围；当用户提交查询样本字后,在线计算查询样本字中各个特征的显著因子,根据不同的显著性因子自适应获取可能相似的候选字集合；利用轮廓形状相似性算法在候选字中进行精确匹配,用匹配值排序检索结果.实验结果表明,与单纯的形状匹配法相比,该方法在提高查全率与查准率的同时,将平均检索时间缩短至5%左右；与层次式匹配法相比,该方法在运行时间上没有明显缩短,平均查全率和查准率提高10%左右.

自适应匹配；显著性因子；书法字

随着各国数字图书馆建设进程的推进,纸张版图书不断以页面方式扫描,以数字形式存储,以便于更好地向学术界提供服务.纸质书籍数字化,不仅存贮、携带方便,而且可以通过网络随时随地提供查阅与检索服务.这些扫描后的页面图像内容,除了有现代印刷体书籍,还有大量古代书法书籍,因为在印刷术出现之前,所有文件和书籍都是手写的.书法指书写法则,优秀的作品有中国的《兰亭集序》、美国的《华盛顿书信》手稿、《圣经》手稿、阿拉伯的《古兰经》以及印度的《妙法莲华经》.书法没有完全被电子产品替代,至今在教学实用中,譬如中国教育部公布的《中小学书法教育指导纲要》于2013年开始执行.西方书法用扁平笔书写,中国的书法通常用毛笔写,不同作者的书写形态各异.

图书馆中打印出来的书籍,扫描后的页面图像内容可以通过光学字符识别(optical character recognition,OCR)转变成文本,进而根据文本提供检索服务.书法作品图像中的书法字笔画和字母不像打印体那样横平竖直,没有固定模板可以匹配,无法OCR成文本.因为不同作品书写笔画粗细不同、笔画间会存在黏连,历史书法作品存在饱经沧桑后的部分笔画模糊与缺失现象.承载着作者独特书写风格的书法字形态各异,给书法艺术带来了美,却因变化多端给书法字识别带来了困难.

随着书法作品图像的增多,近10年来出现了较多关于书法字检索与识别的研究,但尚缺乏一个成熟实用的系统,主要问题在于检索速度和效果.受已成熟的文本检索所采用的词频-逆向文件频率(term frequency-inverse document frequency, TF-IDF)方法的启发,本文提出自适应的书法字匹配和检索方法.离线统计书法字特征向量中各维度上值的分布范围；当获得查询样本的特征向量后,着重计算每维特征的显著性,越显著的权重越大；根据显著特征找出相似的书法字.

1 相关研究

就书法字图像而言,对书法字的检索本质上是一种基于内容的图像检索(content-based information retrieval, CBIR).传统的CBIR多采用颜色[1]、纹理[2]、形状[3]及它们的组合[4].对于书法字,颜色、纹理都不是它的关键特征,只有形状是书法字的关键特征.就书写内容而言,书法字是一种文字的手写体.经数十年的研究发展,各种文字的手写体识别都有不同程度的进展,尤其是以字母为基本元素的文字中,譬如英文[5-6]和阿拉伯文手写体的识别方法[7].以字母为基本元素的文字排列是一维,譬如英文由26个字母组成,希腊文由24个字母组成,都从左到右排列；阿拉伯文由28个字母组成,从右到左排成连续曲线.汉字手写体是二维的,基本部首从上到下、从左到右排列,因此不同文字的手写体识别方法不同.在汉字手写体方面,丁晓青等[8]提出以隐马尔可夫模型 (hidden Markov model, HMM)对脱机手写汉字进行建模、识别的方法,取得了良好的效果.刘成林等[9]给出基于统计部首模型的联机手写汉字识别方法.上述方法主要是针对现代简体汉字的手写体识别,不适用于包含繁体的历史书法字识别.历史书法字存在数量大、类别多、结构复杂、异性字多等特点,而且书写书法字的是软笔的毛笔,运笔速度不同会导致笔画粗细不同,书写过程中蘸墨次数的多寡也会导致笔画形状多变,譬如枯笔是因为写得太快、墨水蘸得太少导致的.历史书法作品中使用了很多繁体,其中的一些字是在现代文学中不再使用的.加之历史书法字年代久远,历经沧桑,字迹可能模糊,甚至缺失部分笔画.与传统的手写体识别相比,历史书法字的检索与识别更困难.

针对书法字检索和识别的研究,CADAL[10]项目的书法研究团队取得了良好的效果,已经成功应用到上线的产品中.章夏芬等[11]提出基于形状相似性的书法字检索方法,利用轮廓相似性,在查全率和查准率方面均取得了较好的效果,但对于大数据量的书法字检索,速度慢,检索效果不理想.为了提高速度,Zhang等[12]对文献[11]进行改进,用由粗及细的分层的方式快速找到候选字,在不降低检索效果的情况下提高了速度,关键在于采用了剪枝算法.该剪枝方法没有考虑特征值的分布范围,对所有特征值设置统一的、固定的剪枝阈值.实际上阈值需要变化,因为能剪去多少枝条取决于样本字的具体特征值.若该值是显著特征,则意味着是少数书法字才具有的,大部分书法字不具有的,可以剪去大部分；若该特征是非显著的,则大部分书法字都有,能够剪去的书法字很少.为了提高速度,俞凯等[13]提出用骨架点而不是轮廓点表征书法字,因为骨架点数比轮廓点数少,能够降低特征维数,加快计算速度.骨架由细化算法产生,细化算法对书法笔画的粗细、黏连敏感,细微的黏连能够导致细化结果的严重畸变和错误的匹配结果.俞凯等[14-15]在文献[11]的基础上,分别提出用骨架点代替轮廓点表示书法字,从而降低维数、提高计算速度.这是因为骨架点个数比轮廓点个数少,计算速度快.因骨架对书法笔画黏连敏感,最终的匹配结果不理想.针对形状匹配速度慢的问题,俞凯等[14]提出用分层检索方法加快检索速度：在第一层中,检索通过提取拐点、端点等关键点特征进行比较,以大幅度减少需要匹配计算的像素点个数.在操作过程中存在以下问题：书法字在书写时横不平、竖不直、圆弧变拐弯,在该折勾的地方,常用圆弧替代,这导致拐点的漏检测；书写时的枯笔会产生毛刺,因为毛刺处点的曲率大而会被误判成拐点.为了加快检索速度,庄毅等[16]提出针对书法字形状特征的高维索引方法,但索引关键字、索引表的值等具体技术细节的描述模糊,笔者难以重现其中的实验.

上述分层剪枝法、用骨架点替代轮廓以降维、用拐点、端点表达书法字以减少特征维数、用高维索引算法加快速度,目标都是让计算速度更快,未考虑相应特征值的分布范围会影响计算速度.本文提出自适应匹配和检索算法,统计分析特征值本身的分布范围,在此基础上计算查询样本字中各个特征的显著性、鉴别力权重,以自适应地快速找到候选字集.

2 特征显著性

2.1 符号说明

F={f1,f2,f3…fk},其中fk为图像特征中的第k个特征.

Y={Yi|i=1,2,…n}是数据库中书法字的集合,其中n为书法字的总个数.

C={ci,k|i=1,2,…,n,k=1,2,3,4,5},其中ci,k为候选集合中第i个候选字的第k个可比特征.

2.2 特征提取

提取书法字笔画复杂度、水平笔画密度、垂直笔画密度、横竖笔画密度比、字的高宽比,一共5项特征.这些特征具有缩放、平移不变性,对书法字整体结构的表达能力强,提取和匹配算法复杂度较低,而且对书法字形变不敏感,适合于书法字图像粗分类.令p(i,j)为一幅M×N二值化的书法字图像,

(1)

各特征的定义如下.

定义1 笔画复杂度complexity是统计书法字轮廓点的像素总数,

(2)

式中：g(i,j)为轮廓点.

书法字的轮廓点数属于书法字的统计特征,反映出一个书法字整体的笔画复杂程度.不同笔画复杂程度的书法字图像轮廓点数不同,例如大小同样是64×64像素的“人”字和“畅”字,它们的轮廓点数分别为97和305,305≫97.此时,该特征具有良好的区分效果.

定义2 笔画密度density包含水平笔画密度和垂直笔画密度.水平笔画密度指横笔的密集程度,可以用垂直扫描线检测；垂直笔画密度指竖笔的密集程度,可以用水平扫描线检测.令Jh,k为第k条垂直扫描线穿越书法字笔画的次数,

(3)

式中：⊗为异或操作.当一个书法字横笔画越多,则扫描线垂直穿越书法字笔画的次数越多,得到的Jh,k越大.

式(3)中i为1～M-2,缺少对图像边缘的处理；令bh,k为边缘穿透数,则有

bh,k=#{f(i,k)=1|i=0∪i=M-1}.

(4)

式中：#表示集合中元素个数.第k条垂直扫描线穿越书法字笔画次数为dh,k=Jh,k+bh,k,dh,k按从小到大排序后,水平笔画密度densityH可以写为

(5)

式中：β为实验值,β=1/1.5.引入参数β是为了尽可能舍弃如图1(b)、(d)所示的噪声.图1(b)中,右侧的多余空白边缘是在页面切分时引入的,两条垂直扫描线区域处返回的穿越次数为0,是干扰正确值的噪声.图1(d)中的噪声是书写时黏连造成的,使中间两条垂直扫描线区域处返回的穿越次数为2,是干扰正确值的噪声.式(5)取均值,是为了吸收噪声.

图1 笔画密度扫描返回噪声的2种情况Fig.1 Two kinds of noise indicated by blue vertical lines

同理可得垂直笔画密度densityV.令Jv,k为第k条水平扫描线穿越书法字次数,则有

(6)

一个书法字竖笔画越多,则扫描线水平穿越书法字的次数越多,即得到的Jv,k越大.令bv,k为水平边缘扫描线的穿透数,则有

bv,k=#{f(k,j)=1|j=0∪j=N-1}.

(7)

式中：#表示集合中元素个数,则第k条垂直扫描线穿越书法字笔画次数为dv,k=Jv,k+bv,k.同理可得水平笔画密度：

(8)

式中：β=1/1.5.水平扫描线和垂直扫描线的笔画穿透数与笔画密度相关,而与笔画的倾斜角无关,这忽略书法书写时“横不平、竖不直”引入的噪声.穿越数统计的是入点和出点,即此处遇到的笔画个数,避免了因书法笔画粗细多变带来的噪声.

书法字的笔画密度特征属于书法字的结构特征,当书法字整体笔画复杂度相同或相近时,横、竖笔画数量未必相同,如汉字“三”和“川”,它们的笔画复杂度大致相同,但横向与竖向笔画密度差距很大.水平笔画密度和垂直笔画密度具有良好的区分效果.

定义3 字的高宽比为单个书法字最小包围盒的高宽比,

(9)

式中：height为单个书法字最小包围盒的高度,width为宽度.

定义4 横竖笔画密度比density_ratio为水平笔画密度与垂直笔画密度的比,

(10)

2.3 显著性表达

表1给出所提取的5个特征对应的详细说明.表中,f1、f2、f3、f4、f5分别为该书法字的笔画复杂度、水平笔画密度、垂直笔画密度、字的高宽比以及横竖笔画密度比.

表1 所提取的特征

图2 高宽比特征值为显著及非显著的2种情况示例Fig.2 Discriminative and non-discriminative examples of feature f4

对于不同的书法字,表1所描述的5个特征具有不同的鉴别力强度,类似于在TF-IDF算法中,对于不同的查询文档,每个词出现的频率不一样.如图2(a)所示的书法字“一”,鉴别力最强的特征为上述5个特征中的高宽比,因为该字的这个特征是其他汉字都不具备的,此时认定高宽比为书法字“一”的关键特征.同样的高宽比对于其他字不一定具有很好的鉴别力,如图2(b)所示的书法字“林”,因为此时大部分书法字的高宽比都与“林”字高宽比差别不大,起不到显著区分效果.

当一个书法字图像中“横”笔画较多时,则“横”笔画是主要特征,即由式(5)得到的水平笔画密度较大,此时认定水平笔画密度为显著性特征.当书法字“竖”的笔画较多时,“竖”笔画是主要特征,即由式(8)得到的垂直笔画密度较大,此时认定垂直笔画密度为显著性特征.当书法字笔画较复杂时,笔画复杂度是主要特征,此时认定笔画复杂度为显著性特征,反之亦然.图3展示了不同形态的原始书法字图像“之”字、“书”字经过预处理后的轮廓效果图以及它们各自对应的笔画复杂度.

图3 不同复杂度的书法字complexity值比较Fig.3 Character examples of different complexity

如图3(a)、(b)、(c)所示为简单书法字“之”的笔画复杂度,图3(d)～(f)所示为较复杂书法字“书”的笔画复杂度.从complexity可以看出,同一个汉字的不同形态的书法字笔画复杂度差异相对较小,而不同汉字的书法字图像的笔画复杂度差异较大,特别是对于极简单或极复杂的书法字,笔画复杂度具有良好的区分效果.

上述5种特征对于不同的书法字,鉴别力的强度不一样,需要对不同书法字的特征进行显著性分析.每个书法字图像都是唯一的,目前书法书籍在持续扫描、切分过程中,书法数据库不断增大；这些书法字的上述5个特征在特征内是互相独立的；即书法字的每个特征都是大量的、互相独立的随机变量,满足中心极限定理的2个前提条件.有理由认为上述书法字的每个特征值的分布逼近图4所示的高斯分布N(μk,σk),可以用高斯分布模型逼近分析结果.

图4 高斯分布模型Fig.4 Gaussian distribution model

图4中,μk、σk为第k个特征的均值和方差.对有限的13 351个书法字单字进行特征统计,如图9所示,发现它们逼近高斯分布趋势.

令X为用户提交的样本书法字,对X提取上述5种特征,记X的第k个特征为xk.根据高斯正态分布规律可知,特征值xk落入不同的范围具有不同数量的相似字：

(11)

由式(11)可知,当xi超出3σk范围之外,即大于μk+3σk或小于μk-3σk时,在该特征上与样本字相似的书法字只占全部书法字数量的(100%-99.73%)/2=0.135%.这意味着仅有极少量书法字在该特征上与样本字有相似之处,该特征为样本字的显著性特征,根据该特征可以快速找到少量相似的书法字.当特征xk落在2σk区间外,则在该特征上可以剪掉数据库中95.45%不相似的字；当特征xk落入[-σk,σk]内时,意味着数据库中68.27%的书法字在该特征上与样本字相似,该特征不是样本字的显著特征,使用该特征不能把相似字从数据库中区分出来.

对于高斯分布区域内的书法字特征,特征xk相对于μk的偏离程度可以用来表示该特征的显著性(鉴别力)的大小.特征xk偏离μk越远,鉴别力越强.例如图1的书法字“一”,它的高宽比为5,偏离接近于1的均值较远,此时“一”的高宽比与其他汉字都不一样,可以作为显著性特征.反之,特征xk偏离μk越近,则显著性(鉴别力)越弱,此时xk即为非显著特征.

2.4 显著因子计算

针对书法字不同特征的显著性情况,需要一个值来表达各特征显著性大小,这个值称为“显著因子”；显著因子越大,则显著性越强.对用户提交的样本书法字X提取上述5种特征,样本书法字的特征向量记为X=[x1,x2,x3,x4,x5],其中x1、x2、x3、x4、x5分别为样本书法字笔画复杂度、水平笔画密度、垂直笔画密度、字的高宽比和横竖笔画密度比.计算书法字数据库中特征fk对应的均值μk和标准差σk,则第k个特征xk的显著性因子wk为

(12)

wk用于表达特征xk对于样本字X的显著性,其中n=3.由式(12)可知,xk偏离μk越远,wk越大,该特征的显著性越强；xk离μk越近,wk越小,该特征的显著性越不明显.式(12)中用绝对值的方式避免出现某项是负值,从而导致正、负值中和的情况.对式(12)中右侧的偏离值作n=3次方运算,是用于放大显著性差异.因为偏离σk之外,偏向于显著特征,wk>1,大于1的数值作乘积后值变大；落入σk之内,偏向于非显著特征,wk<1,小于1的数值作乘积后值变小.就显著性差异区分度而言,n越大越好；就计算量而言,n越小越好,且n最好取整数.折中两方的取向,由实验测试可得n=3时效果最佳.

由式(12)可得,就笔画复杂度这一项,“顺”字的鉴别力w1为

0.8473=0.608.

图5 不同书法字特征值可视化比较Fig.5 Visualization of two different features

由式(8)计算得出“顺”字的x3=9.094,数据库中该特征对应的均值和方差为D(μ3=5.258,σ3=1.598).由式(12)可得,就垂直笔画密度这一项,“顺”字的鉴别力w3为

2.43=13.824.

对于指定的“顺”字,垂直笔画密度相对于笔画复杂度更具有鉴别力.垂直笔画密度特征应赋予更大的权重,w3>w1.由于“顺”字笔画复杂度偏离均值为0.847σ,小于σ,而“顺”字的垂直笔画密度偏离均值距离为2.4σ,大于σ.式(12)作3次方运算,使与均值的偏离程度不超过σ的特征值的显著特征因子wk更小；偏离程度超过σ的特征值作3次方运算,会把显著特征因子wk变得更大.譬如,上述“顺”字的笔画复杂度的权重w1=0.608,垂直笔画密度的权重w3=13.824,w3w1,即x3相对于x1而言,拥有较大权重.

3 自适应匹配

3.1 特征归一化

不同特征值的取值范围在数值上有较大差别,不能直接求差,再求和.对于某项特征值,直接求差值所得的大数值并不能说明该特征是显著特征,也又可能不是显著特征；这要取决于群体中该项特征值间的差异.表2给出数据库中13 351个书法字特征上述5种特征的统计情况.在求差异前,先要将它们归一化到可比空间.

如图5所示,书法字“顺”与“言”的整体笔画复杂度分别为232和210,笔画复杂度差异值为22；垂直笔画密度分别为9.094和3,垂直笔画密度差异值为6.094.通过式(12)可得,此时垂直笔画密度是书法字“顺”与“言”的显著性特征,而整体笔画复杂度不是它们的显著性特征.若在非归一化的情况下,直接进行特征融合来对2个书法字作比较,则会因为笔画复杂度特征差异值22大于垂直笔画密度差异值6.094,成为相对非显著特征,使整体笔画复杂度比显著性特征垂直笔画密度具有更大的影响力,与实际情况相违背.对不同特征进行归一化,以使各特征在相似度量中具有可比性.

表2 书法字特征值的统计

特征归一化方法有线性归一化和非线性归一化.采用非线性归一化的方法.首先计算书法字数据库训练集T中各特征的均值μ与标准差σ,令μ=[μ1,μ2,μ3,μ4,μ5],σ=[σ1,σ2,σ3,σ4,σ5]，其中μ1、μ2、μ3、μ4、μ5分别对应特征f1、f2、f3、f4、f5的均值,σ1、σ2、σ3、σ4、σ5分别对应特征f1、f2、f3、f4、f5的方差.X=[x1,x2,x3,x4,x5]为查询样本字,其中x1、x2、x3、x4、x5为样本中对应特征f1、f2、f3、f4、f5的具体值；样本书法字的第k(k=1,2,3,4,5)个特征值xk可以根据下式进行归一化,获取可比特征值：

(13)

得到样本字X相应的可比特征向量q=[q1,q2,q3,q4,q5]. 令Y={Y1,Y2,…,Yn}表示书法数据库中书法的集合,其中n为书法字数据库中候选字的总个数,所提取的数据库中第i个书法字的特征向量为Yi=[yi,1,yi,2,yi,3,yi,4,yi,5],其中yi,1、yi,2、yi,3、yi,4、yi,5分别为第i个候选书法字对应特征f1、f2、f3、f4、f5的原始特征值.用式(13)计算得到第i个候选书法字的可比特征向量为Ci=[ci,1,ci,2,ci,3,ci,4,ci,5],其中

(14)

3.2 自适应剪枝

Zhang等[12,14-17]针对书法字快速检索的问题,都采用分层的方式,先找到可能与样本字相似的候选字集合,再对集合中的每个书法字作匹配、排序出最相似的书法字.庄毅等[16]提出用高维索引的方式加快书法字检索速度.分层、索引都需要一个标准.俞凯等[14]没有描述是如何分层的,即如何分类,标准是什么.分类的关键在于区分数据库中哪些是可能相似的书法字,哪些是不可能相似的.Zhang等[12,17]给出分层的标准,但该标准是以每一个特征为单位进行实验得到的,即每个特征有一个统一的剪枝阈值,未考虑不同样本在该特征上有不同的差异.如果样本的该特征值是均值,即由式(13)计算得到的可比特征值qk=0,是非显著特征,用固定的阈值剪去部分数据会引入错误.如果样本在该特征值上的可比值接近于极值,譬如图1中“一”字的纵向笔画密度接近极值,使qk≈3,这种情况下用固定不变的阈值剪枝会留下大部分不可能相似的候选字.

在文本方面,TF-IDF算法已成功应用于各搜索引擎上；在图像方面,Rui等[18]提出类似的图像检索算法CI-ICI算法,采用分量重要因子(component importance, CI)和逆集合重要性因子(inverse collection importance, ICI).若直接把式(12)中的wi赋值给cii,则cii=wi=fi/μ,与方差σ无关,不合理.受逆集重要性因子icii=log2(σi+2)的计算方式的启发,构建自适应剪枝标准：

|qk-ci,k|≤3-log2(|qk|+1).

(15)

式中：qk为查询样本字的第k个可比特征值,ci,k为数据库集合中第i个字的第k个可比特征.式(15)右侧3-log2(qk+1)称为剪枝阈值,满足式(15)的ci,k的取值范围称为候选区域,由ci,k对应的数据库中的书法字Yi被归到可能相似的类,保留；其余书法字作为不可能相似的类,剪除.

查询样本字不同,相应的可比特征qk不同.qk所处区域的不同,直接影响到可能相似的类大小.在实际计算中,qk是在(-4,4)内的一个随机值.表3列举了qk取几个特定值时,用式(15)的剪枝标准计算,保留(剩下)的类大小.由表3可知,当qk=0时,剩下的书法字占数据库中的99.73%,几乎没剪去什么字.由式(13)可知,qk=0意味着xk=μk,即该特征等于平均值,是最大众化特征,不是显著特征,不能根据该特征剪去其他字.当qk=3或qk=-3时,该特征值偏离均值,显著性强,剪枝后剩下部分仅有1.1%,即使可选的候选集缩小到原来的1.1%.

表3 特征值不同导致候选区域不同

3.3 自适应排序

不同的查询样本字所剩下的可能相似的集合大小不同.需要进行匹配、排序,用Match(q,Ci)表示样本字q与Ci的相似度：

(16)

式中：wk为由式(12)计算得到的显著性因子,|qk-ci,k|为样本书法字q与候选书法字Ci在第k维特征值上归一化后的差异程度.Match(q,Ci)越大,两个字的相似度越弱.按Match(q,Ci)从小到大排序,排在最前面的是与样本字最相似的候选字.

当用户对响应时间要求较高时,快速返回自适应排序结果；当对检索效果要求高时,则继续运行耗时的形状匹配法,以时间换取更精确的检索结果.

3.4 形状匹配

通过上述自适应算法,可得与样本书法字同一类别的候选书法字,需要进一步对同一类别的候选书法字进行相似度排序,即对书法字图像进行精确匹配,找到与样本书法字最相似的候选字.采用类似基于轮廓相似性的书法字匹配方法[1],对提取的每个轮廓点采用极坐标分块的方法,将周围空间从方向上均分为8个角度,在半径上按近似log2r的长度划分为4份.若书法字归一化大小为64×64像素,则每个分割点位于r=8、r=16、r=32和r=64的位置.

图6展示了空间混合分割坐标系统,该系统将周围空间一共分割为32块.其中,每一块所占的空间从内向外逐渐增大.因为对该点越有鉴别力的点,在空间距离上离该点越近；相对越远的点,对该点的鉴别力越弱.在同一环上,每一块所占的空间大小是一样的,因为四周相同距离的点对该点的鉴别力是一样的.计算落在每一块里轮廓点的个数,再计算书法字中每个关键点与另一个书法字中在关键点一定范围内的相似点之间的距离,得到2个书法字关键点之间的相似度.依据相似度,最终确定类别.

图6 书法字原图像及相应的极坐标系 Fig.6 Original character image and corresponding polar coordinates for extract feature of shape context

由n个点组成的书法字A={ai|i=1,2,…,n},每个轮廓点都会产生32维特征值,则第i个轮廓点的32个特征值可以表示为(ai1,ai2,ai3,…,ai32).对于一个拥有n个轮廓点表征的书法字,可以构造一个n×32的形状矩阵：

与文献[1]使用的方法不同,本文的相似度计算不是采用欧式距离,而是采用余弦相似度.在高维空间中,夹角余弦更好地反映出图像数据点之间的空间分布情况,数据点之间的夹角余弦越大越相似.样本字中第i个轮廓点Mi与候选字中第j个轮廓点Nj的近似匹配程度cos (Mi,Nj)为

(17)

式中：mi,k为样本字第i个轮廓点Mi的第k维的值,nj,k为候选字第j个轮廓点Nj的第k维的值.cos (Mi,Nj)越大,两个点越相似.拥有最大值的点是最相似点或者说是对应点.令Si为样本字点Mi与对应点的匹配值,则有

Si=max{cos (Mi,Nj)；j=0,1,2，…，m}.

(18)

样本字A与数据库中一个候选字C的形状匹配值是它们的所有轮廓点的近似匹配值之和：

Sim(A,C)=

(19)

式中：arcarccos(Mi,corresp(Mi))为点Mi与对应点corresp(Mi)之间的夹角；λ为惩罚因子,两点夹角越大,惩罚值越大.在该实验中,λ=0.2.

4 实验分析

4.1 数据获取

实验所用的原始书法页面图像和书法字图像来自中美百万册数字图书馆CADAL项目[12].书法页面图像扫描的精度是600DPI(Dot Per Inch,每英寸点数),图像格式是TIFF格式.所采用的页面图像已经在笔者的前期研究[11]中切分为单字图像.实验中的数据来自18本扫描得到的《中国书法全集》的页面图像,切分了483个页面,得到13 351个书法字图像.如图7所示,为该实验所采用的单个书法字样例.

图7 单字图像样例Fig.7 Screenshot of individual original characters

原始页面图像扫描精度为600 DPI,其结果是一个尺寸大小为20 cm×20 cm的纸张页面,扫描后得到4 722×4 722个像素点的页面图像文件.若直接处理,则像素点太多,速度太慢.将图像在横向和纵向上均缩小了5倍,即将图像像素大小变为原图的1/25倍.作完缩放处理后的单个书法字图像的大小统计如表4所示.

表4 书法字图像大小

这些数据来自211个作品,最大的作品含1 245个单字,作品名为：蔡玉卿小楷《孝经》.图8给出单个作品中所含字数的统计,只列出字数超过50的作品.图中,n为作品序号,按作品所含字的个数从大到小顺序排列;Nw为统计得到的单个作品的字数.为了给检索结果的正确性提供一个检验标准,采用前期交互式标注法[19],对所有单个汉字的图像内容进行标注,该标注内容称为标签,并构建了书法数据库.对数据库中的单字进行统计[20]后,已发现这些标签在作品中出现的频次大致上遵循齐普夫定律(Zipf’s Law).

图8 作品中包含的字数统计：字数超过50的作品按从大到小顺序排列 Fig.8 Number of character per work, with works contains more than 50 individual characters are counted

对数据库中的每个单字进行预处理、轮廓提取,获取表1中的f1、f2、f3、f4、f5特征.这些特征归一化到64×64像素大小的空间.统计数据库中13 351个书法字图像的特征值,可得各特征数值分布均趋向于正态(高斯)分布,如图9所示.图中，N为具有该特征值的样本个数.

图9 书法字5个特征值的分布图Fig.9 Distribution of five features

由实验统计结果显示样本特征值的分布与正态分布有所偏离,这是因为统计的样本数未真正达到大数据量.数据库中的样本数越大,特征值越趋向于正态分布.由图9知,书法字整体笔画复杂度为66～363；水平笔画密度为1.579～14.396；垂直笔画密度为1.475～11.276.其中,书法字整体笔画复杂度在170～230内比较集中,分布密度较大.若样本书法字的笔画复杂度落在该区间,则在笔画复杂度的显著性因子较小.此时,大部分书法字的整体笔画复杂度都与该字有交叠,起不到区分效果.相反,书法字整体笔画复杂度在趋近于两端时,数量明显减少且分布密度比较松散,若位于该区间,则笔画复杂度的显著因子较大,表示显著性较强.

4.2 运行结果

图10展示了采用自适应层次分类的方法进行分层检索的2个样例.检索界面返回的是检索结果中最相似的前30个书法字,其中第1行为用户提交的书法字图像样例；第2～4行为检索结果,按相似度由高到低排序.每个图像的下方数字为该字与样本字相似性计算的匹配值,匹配值越大越相似.

图10 运行自适应匹配和检索例子Fig.10 Screenshot of one adaptive matching example

如图10(a)所示为书法字“可”的检索结果,在前24个检索结果中没有错字出现.在前30个检索结果中,第25个和第28个均出现被误识的“耳”字,这是因为“耳”字与“可”字在形状上较相似,在使用基于形状相似性的检索方法时,被认为是形状相似,出现误差.可以看出,随着相似度的降低,“可”字书体风格出现了明显变化.图10(b)展示的是书法字“无”的检索结果,其中出现一个“无”字排在检索结果的第29位,相似度较低.这是因为该候选字的书写风格发生明显变化,产生了较大的形变,从而导致相似度下降.

4.3 性能分析

采用Visual C++作为开发平台,PC配置Intel(R) Core(TM) i5-4300处理器,2.50 GHz主频,8 GB内存,Windows 7操作系统.

为了验证自适应层次分类检索方法的总体运行性能,用查全率、查准率和查询时间衡量运行性能.

(20)

(21)

用random函数随机选取数据库中的50个书法字图像作为样本进行测试,剩下的书法字作为实验用的检索数据库.图11给出随机选取的50个样本字作检索时的平均查全率和查准率曲线.将自适应层次分类检索方法与基于轮廓相似性的单层检索方法[1]和基于分层检索方法[13]进行比较.

图11 平均查全率与平均查准率对比Fig.11 Comparison of recall and precision ratio for three approaches

图11的结果显示,与文献[13]相比,在相同的数据库下,本文的自适应方法在查全率相等的情况下,查准率平均上升了10%左右.图11的对比结果显示,自适应方法的查全率和查准率优于文献[13]的分层匹配法.将图11与文献[13]中图9的查全率和查准率进行对比,会发现文献[13]的分层匹配法在该实验中的具体查全率和查准率有所下降,这主要有以下2个原因：1)俞凯等[13]使用的数据库大小是3 012个,而本文使用的是13 351个,扩大了4.43倍；2)俞凯等[13]对每个特征使用统一的阈值剪枝,不考虑查询样本间的差异,这样的剪枝法容易造成误剪,尤其是当数据库扩大之后,会在剪枝过程中错误剪掉相似书法候选字.与文献[1]相比,数据库大小上升后,采用单一的形状匹配法得到的查准率和查全率迅速下降,主要由以下2个原因造成：1)文献[1]中的数据库大小是1 650个,该实验中为13 351个,扩大了8倍； 2)形状匹配用的是轮廓点表达书法字,轮廓点是底层特征,与高层的笔画结构存在语义上的差异；同理,用像素点集的相似性去表达图像内容的相似性存在语义上的鸿沟.由此可知,要提高匹配的效率,需要结合高层语义特征,譬如书法字的笔画密度特征.

表5给出随机选取的50个样本字,在3种不同方法下的平均检索时间t的比较.可以看出：采用自适应层次分类的检索方法在速度上比文献[1]的检索方法有了明显提升,这是因为自适应算法有剪枝,与形状匹配所用的特征维数(平均为150)相比,剪枝所用的特征维数(5)降低30倍.与文献[13]的检索时间相比,没多大提高,基本持平.

表5 平均检索时间对比

5 结 语

本文提出自适应的书法字图像匹配和检索方法,先离线分析了数据库中各特征值分布范围,发现它们趋向于高斯分布,这是对前期研究发现书法字标签符合齐普夫定律(Zipf’s Law)的一个进步.在此基础上,根据不同查询样本的不同特征值,作自适应剪枝、匹配.实验结果表明,该方法比以往2种书法检索算法的效果好.

在书法数据库进一步增大的情况下,匹配和检索速度降低,须针对书法字数据库维数高、数据量大的特点,进一步研究大数据量书法字的高维索引法.譬如将大数据量书法字图像的索引与处理部署到云计算平台Hadoop上,利用云计算平台高效的处理能力来提高书法字检索的整体运算效率和速度.

[1] SETLUR V, STONE M C. A linguistic approach to categorical color assignment [J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 22(1): 45-49.

[2] LIU L, FIEGUTH P W. Texture classification from random features [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(3): 574-586.

[3] BERRETTI S, BIMBO A D, PALA P. Retrieval by shape similarity with perceptual distance and effective indexing [J]. IEEE Transaction on Multimedia, 2000,2(4): 225-239.

[4] 潘云鹤, 吴飞. 网上多媒体信息分析与检索[M]. 北京: 清华大学出版社, 2002: 28-37.

[5] PLAMONDON R, SRIHARI S N. Online and off-line handwriting recognition: a comprehensive survey [J]. PatternAnalysis and Machine Intelligence, 2000, 22(1): 63-84.

[6] RATH T M, KANE S, LEHMAN A, et al. Indexing for a digital library of George Washington’s manuscripts: a study of word matching techniques [R]. Massachusetts: University of Massachusetts, 2004.

[7] ITAY Y, KLARA K, MALACHI B A, et al. Classification of Hebrew calligraphic handwriting styles: preliminary results [C]∥Proceedings of the 1st International Workshop on Document Image Analysis for Libraries. Palo Alto: [s. n.], 2006: 299-305.

[8] 冯兵,丁晓青.HMM方法识别脱机手写汉字[J].模式识别与人工智能,2002, 15(1): 84-88. FENG Bing, DING Xiao-qing. Off-line handwriting Chinese character recognition [J]. Journals of Pattern Recognition and Artificial Intelligence, 2002, 15(1): 84-88.

[9] 马龙龙,刘成林.基于统计部首模型的联机手写汉字识别方法[J].智能系统学报, 2010, 5(5): 385-391. MA Long-long, LIU Cheng-lin. On-line handwritten Chinese character recognition using statistical radical models [J]. CAAI Transactions on Intelligent Systems, 2010, 5(5): 385-391.

[10] Chinese calligraphy character recognition of CADAL [EB/OL]. [2015-12-16]. http:∥www.cadal.zju.edu.cn/ Calligraphy.

[11] 章夏芬,庄越挺,鲁伟明,等.根据形状相似性的书法内容检索[J].计算机辅助设计与图形学学报, 2005,17 (11): 2565-2569. ZHANG Xia-fen, ZHUANG Yue-ting, LU Wei-ming, et al. Shape based calligraphy image retrieval [J]. Journal of Computer-Aided Design and Computer Graphics, 2005, 17 (11): 2565-2569.

[12] ZHANG X F, ZHUANG Y T, WU J Q, et al. Hierarchical approximate matching for retrieval of Chinese historical calligraphy character [J]. Computer Science and Technology, 2007, 22 (4): 633-640.

[13] 俞凯,吴江琴,庄越挺.基于骨架相似性的书法字检索[J].计算机辅助设计与图形学学报,2009, 21(6): 746-751. YU Kai, WU Jiang-qin, ZHUANG Yue-ting. Calligraphic characters retrieval based on skeleton similarity [J]. Journal of Computer-Aided Design and Computer Graphics, 2009, 21(6): 746-751.

[14] 俞凯,吴江琴.书法字快速多层检索方法[J].计算机辅助设计与图形学学报,2011, 23(8): 1415-1419. YU Kai, WU Jiang-qin. Fast multi-level retrieval for calligraphic characters [J]. Journal of Computer-Aided Design and Computer Graphics, 2011, 23(8): 1415-1419.

[15] 陈颉,朱福喜.根据骨架结构相似性的书法内容分层检索[J].小型微型计算机系统,2010, 31(1): 138-142. CHEN Jie, ZHU Fu-xi. Hierarchical matching for Chinese calligraphic retrieval based on skeleton similarity [J]. Journal of Chinese Computer Systems, 2010,31(1): 138-142.

[16] 庄毅,庄越挺,吴飞.基于数据网格的书法字k近邻查询[J].软件学报, 2006, 17(11): 2289-2301. ZHUANG Yi, ZHUANG Yue-ting, WU Fei.Answering k-NN query of Chinese calligraphic character based on data grid [J]. Journal of Software, 2006, 17(11): 2289-2301.

[17] ZHANG X F, ZHUANG Y T. Dynamic time warping for Chinese calligraphic character matching and recognition [J]. Pattern Recognition Letter, 2012, 33(16): 2262-2269.

[18] RUI Y, HUANG S. T, MEHROTRA S. Content-based image retrieval with relevance feedback in MARS [C]∥ Proceedings of IEEE International Conference on Image Processing. Santa Barbara: IEEE, 1997: II815-818.

[19] NAGY G, ZHANG X F. CalliGUI: interactive labeling of calligraphic character images [C]∥Proceedings of 11th International Conference on Document Analysis and Recognition. Beijing [s. n.], 2011: 977-981.

[20] ZHANG X F, NAGY G. The CADAL calligraphicdatabase [C]∥ Proceedings of the 2011 Workshop on Historical Document Imaging and Processing. Beijing:[s. n.], 2011: 37-42.

Adaptive matching and retrieval for calligraphic character

ZHANG Xia-fen1, ZHANG Long-hai2, HAN De-zhi1, BI Kun1

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

An adaptive matching algorithm was proposed according to discrimination power of each visual feature in order to overcome the large computing and time-consuming in shape-based calligraphy character matching. Each feature value’s distribution range was analyzed statistically off-line. When a query was submitted, its features were extracted and the corresponding significance factors were computed based on which self-adaptive algorithm was employed to find a shortened list of possible similar candidates from the database. Then contour shape matching was run on the shortened list to rank and display the similar. The experimental results showed that the adaptive matching approach shortened the retrieval time to 5% of the original shape matching approach. The approach didn’t significantly speed up the retrieval, but raised the precision ratio about 10% on the condition of the same recall ratio compared with the hierarchical approach.

adaptive matching; significance factor; Chinese calligraphy

2014-12-31. 浙江大学学报(工学版)网址： www.journals.zju.edu.cn/eng

国家自然科学基金资助项目(61303100)；上海海事大学校基金资助项目(20130467).

章夏芬(1977—)，女，讲师，从事图像处理、模式识别的研究. ORCID: 0000-0001-9287-8029. E-mail: xfzhang@shmtu.edu.cn

10.3785/j.issn.1008-973X.2016.04.023

TP 391

A

1008-973X(2016)04-0766-11