自適應(yīng)書法字圖像匹配和檢索

章夏芬, 張龍海, 韓德志, 畢 坤

(1. 上海海事大學(xué) 信息工程學(xué)院,上海 201306；2.中海網(wǎng)絡(luò)科技股份有限公司,上海 200135)

?

自適應(yīng)書法字圖像匹配和檢索

章夏芬1, 張龍海2, 韓德志1, 畢 坤1

(1. 上海海事大學(xué) 信息工程學(xué)院,上海 201306；2.中海網(wǎng)絡(luò)科技股份有限公司,上海 200135)

為了解決基于形狀匹配的書法字檢索計(jì)算量大、耗時(shí)長、效率低的問題,提出根據(jù)樣本字特征動(dòng)態(tài)改變剪枝范圍的自適應(yīng)匹配法.離線統(tǒng)計(jì)分析數(shù)據(jù)庫中書法字的各特征值分布范圍；當(dāng)用戶提交查詢樣本字后,在線計(jì)算查詢樣本字中各個(gè)特征的顯著因子,根據(jù)不同的顯著性因子自適應(yīng)獲取可能相似的候選字集合；利用輪廓形狀相似性算法在候選字中進(jìn)行精確匹配,用匹配值排序檢索結(jié)果.實(shí)驗(yàn)結(jié)果表明,與單純的形狀匹配法相比,該方法在提高查全率與查準(zhǔn)率的同時(shí),將平均檢索時(shí)間縮短至5%左右；與層次式匹配法相比,該方法在運(yùn)行時(shí)間上沒有明顯縮短,平均查全率和查準(zhǔn)率提高10%左右.

自適應(yīng)匹配；顯著性因子；書法字

隨著各國數(shù)字圖書館建設(shè)進(jìn)程的推進(jìn),紙張版圖書不斷以頁面方式掃描,以數(shù)字形式存儲(chǔ),以便于更好地向?qū)W術(shù)界提供服務(wù).紙質(zhì)書籍?dāng)?shù)字化,不僅存貯、攜帶方便,而且可以通過網(wǎng)絡(luò)隨時(shí)隨地提供查閱與檢索服務(wù).這些掃描后的頁面圖像內(nèi)容,除了有現(xiàn)代印刷體書籍,還有大量古代書法書籍,因?yàn)樵谟∷⑿g(shù)出現(xiàn)之前,所有文件和書籍都是手寫的.書法指書寫法則,優(yōu)秀的作品有中國的《蘭亭集序》、美國的《華盛頓書信》手稿、《圣經(jīng)》手稿、阿拉伯的《古蘭經(jīng)》以及印度的《妙法蓮華經(jīng)》.書法沒有完全被電子產(chǎn)品替代,至今在教學(xué)實(shí)用中,譬如中國教育部公布的《中小學(xué)書法教育指導(dǎo)綱要》于2013年開始執(zhí)行.西方書法用扁平筆書寫,中國的書法通常用毛筆寫,不同作者的書寫形態(tài)各異.

圖書館中打印出來的書籍,掃描后的頁面圖像內(nèi)容可以通過光學(xué)字符識(shí)別(optical character recognition,OCR)轉(zhuǎn)變成文本,進(jìn)而根據(jù)文本提供檢索服務(wù).書法作品圖像中的書法字筆畫和字母不像打印體那樣橫平豎直,沒有固定模板可以匹配,無法OCR成文本.因?yàn)椴煌髌窌鴮懝P畫粗細(xì)不同、筆畫間會(huì)存在黏連,歷史書法作品存在飽經(jīng)滄桑后的部分筆畫模糊與缺失現(xiàn)象.承載著作者獨(dú)特書寫風(fēng)格的書法字形態(tài)各異,給書法藝術(shù)帶來了美,卻因變化多端給書法字識(shí)別帶來了困難.

隨著書法作品圖像的增多,近10年來出現(xiàn)了較多關(guān)于書法字檢索與識(shí)別的研究,但尚缺乏一個(gè)成熟實(shí)用的系統(tǒng),主要問題在于檢索速度和效果.受已成熟的文本檢索所采用的詞頻-逆向文件頻率(term frequency-inverse document frequency, TF-IDF)方法的啟發(fā),本文提出自適應(yīng)的書法字匹配和檢索方法.離線統(tǒng)計(jì)書法字特征向量中各維度上值的分布范圍；當(dāng)獲得查詢樣本的特征向量后,著重計(jì)算每維特征的顯著性,越顯著的權(quán)重越大；根據(jù)顯著特征找出相似的書法字.

1 相關(guān)研究

就書法字圖像而言,對書法字的檢索本質(zhì)上是一種基于內(nèi)容的圖像檢索(content-based information retrieval, CBIR).傳統(tǒng)的CBIR多采用顏色[1]、紋理[2]、形狀[3]及它們的組合[4].對于書法字,顏色、紋理都不是它的關(guān)鍵特征,只有形狀是書法字的關(guān)鍵特征.就書寫內(nèi)容而言,書法字是一種文字的手寫體.經(jīng)數(shù)十年的研究發(fā)展,各種文字的手寫體識(shí)別都有不同程度的進(jìn)展,尤其是以字母為基本元素的文字中,譬如英文[5-6]和阿拉伯文手寫體的識(shí)別方法[7].以字母為基本元素的文字排列是一維,譬如英文由26個(gè)字母組成,希臘文由24個(gè)字母組成,都從左到右排列；阿拉伯文由28個(gè)字母組成,從右到左排成連續(xù)曲線.漢字手寫體是二維的,基本部首從上到下、從左到右排列,因此不同文字的手寫體識(shí)別方法不同.在漢字手寫體方面,丁曉青等[8]提出以隱馬爾可夫模型 (hidden Markov model, HMM)對脫機(jī)手寫漢字進(jìn)行建模、識(shí)別的方法,取得了良好的效果.劉成林等[9]給出基于統(tǒng)計(jì)部首模型的聯(lián)機(jī)手寫漢字識(shí)別方法.上述方法主要是針對現(xiàn)代簡體漢字的手寫體識(shí)別,不適用于包含繁體的歷史書法字識(shí)別.歷史書法字存在數(shù)量大、類別多、結(jié)構(gòu)復(fù)雜、異性字多等特點(diǎn),而且書寫書法字的是軟筆的毛筆,運(yùn)筆速度不同會(huì)導(dǎo)致筆畫粗細(xì)不同,書寫過程中蘸墨次數(shù)的多寡也會(huì)導(dǎo)致筆畫形狀多變,譬如枯筆是因?yàn)閷懙锰?、墨水蘸得太少?dǎo)致的.歷史書法作品中使用了很多繁體,其中的一些字是在現(xiàn)代文學(xué)中不再使用的.加之歷史書法字年代久遠(yuǎn),歷經(jīng)滄桑,字跡可能模糊,甚至缺失部分筆畫.與傳統(tǒng)的手寫體識(shí)別相比,歷史書法字的檢索與識(shí)別更困難.

針對書法字檢索和識(shí)別的研究,CADAL[10]項(xiàng)目的書法研究團(tuán)隊(duì)取得了良好的效果,已經(jīng)成功應(yīng)用到上線的產(chǎn)品中.章夏芬等[11]提出基于形狀相似性的書法字檢索方法,利用輪廓相似性,在查全率和查準(zhǔn)率方面均取得了較好的效果,但對于大數(shù)據(jù)量的書法字檢索,速度慢,檢索效果不理想.為了提高速度,Zhang等[12]對文獻(xiàn)[11]進(jìn)行改進(jìn),用由粗及細(xì)的分層的方式快速找到候選字,在不降低檢索效果的情況下提高了速度,關(guān)鍵在于采用了剪枝算法.該剪枝方法沒有考慮特征值的分布范圍,對所有特征值設(shè)置統(tǒng)一的、固定的剪枝閾值.實(shí)際上閾值需要變化,因?yàn)槟芗羧ザ嗌僦l取決于樣本字的具體特征值.若該值是顯著特征,則意味著是少數(shù)書法字才具有的,大部分書法字不具有的,可以剪去大部分；若該特征是非顯著的,則大部分書法字都有,能夠剪去的書法字很少.為了提高速度,俞凱等[13]提出用骨架點(diǎn)而不是輪廓點(diǎn)表征書法字,因?yàn)楣羌茳c(diǎn)數(shù)比輪廓點(diǎn)數(shù)少,能夠降低特征維數(shù),加快計(jì)算速度.骨架由細(xì)化算法產(chǎn)生,細(xì)化算法對書法筆畫的粗細(xì)、黏連敏感,細(xì)微的黏連能夠?qū)е录?xì)化結(jié)果的嚴(yán)重畸變和錯(cuò)誤的匹配結(jié)果.俞凱等[14-15]在文獻(xiàn)[11]的基礎(chǔ)上,分別提出用骨架點(diǎn)代替輪廓點(diǎn)表示書法字,從而降低維數(shù)、提高計(jì)算速度.這是因?yàn)楣羌茳c(diǎn)個(gè)數(shù)比輪廓點(diǎn)個(gè)數(shù)少,計(jì)算速度快.因骨架對書法筆畫黏連敏感,最終的匹配結(jié)果不理想.針對形狀匹配速度慢的問題,俞凱等[14]提出用分層檢索方法加快檢索速度：在第一層中,檢索通過提取拐點(diǎn)、端點(diǎn)等關(guān)鍵點(diǎn)特征進(jìn)行比較,以大幅度減少需要匹配計(jì)算的像素點(diǎn)個(gè)數(shù).在操作過程中存在以下問題：書法字在書寫時(shí)橫不平、豎不直、圓弧變拐彎,在該折勾的地方,常用圓弧替代,這導(dǎo)致拐點(diǎn)的漏檢測；書寫時(shí)的枯筆會(huì)產(chǎn)生毛刺,因?yàn)槊烫廃c(diǎn)的曲率大而會(huì)被誤判成拐點(diǎn).為了加快檢索速度,莊毅等[16]提出針對書法字形狀特征的高維索引方法,但索引關(guān)鍵字、索引表的值等具體技術(shù)細(xì)節(jié)的描述模糊,筆者難以重現(xiàn)其中的實(shí)驗(yàn).

上述分層剪枝法、用骨架點(diǎn)替代輪廓以降維、用拐點(diǎn)、端點(diǎn)表達(dá)書法字以減少特征維數(shù)、用高維索引算法加快速度,目標(biāo)都是讓計(jì)算速度更快,未考慮相應(yīng)特征值的分布范圍會(huì)影響計(jì)算速度.本文提出自適應(yīng)匹配和檢索算法,統(tǒng)計(jì)分析特征值本身的分布范圍,在此基礎(chǔ)上計(jì)算查詢樣本字中各個(gè)特征的顯著性、鑒別力權(quán)重,以自適應(yīng)地快速找到候選字集.

2 特征顯著性

2.1 符號(hào)說明

F={f1,f2,f3…fk},其中fk為圖像特征中的第k個(gè)特征.

Y={Yi|i=1,2,…n}是數(shù)據(jù)庫中書法字的集合,其中n為書法字的總個(gè)數(shù).

C={ci,k|i=1,2,…,n,k=1,2,3,4,5},其中ci,k為候選集合中第i個(gè)候選字的第k個(gè)可比特征.

2.2 特征提取

提取書法字筆畫復(fù)雜度、水平筆畫密度、垂直筆畫密度、橫豎筆畫密度比、字的高寬比,一共5項(xiàng)特征.這些特征具有縮放、平移不變性,對書法字整體結(jié)構(gòu)的表達(dá)能力強(qiáng),提取和匹配算法復(fù)雜度較低,而且對書法字形變不敏感,適合于書法字圖像粗分類.令p(i,j)為一幅M×N二值化的書法字圖像,

(1)

各特征的定義如下.

定義1 筆畫復(fù)雜度complexity是統(tǒng)計(jì)書法字輪廓點(diǎn)的像素總數(shù),

(2)

式中：g(i,j)為輪廓點(diǎn).

書法字的輪廓點(diǎn)數(shù)屬于書法字的統(tǒng)計(jì)特征,反映出一個(gè)書法字整體的筆畫復(fù)雜程度.不同筆畫復(fù)雜程度的書法字圖像輪廓點(diǎn)數(shù)不同,例如大小同樣是64×64像素的“人”字和“暢”字,它們的輪廓點(diǎn)數(shù)分別為97和305,305?97.此時(shí),該特征具有良好的區(qū)分效果.

定義2 筆畫密度density包含水平筆畫密度和垂直筆畫密度.水平筆畫密度指橫筆的密集程度,可以用垂直掃描線檢測；垂直筆畫密度指豎筆的密集程度,可以用水平掃描線檢測.令Jh,k為第k條垂直掃描線穿越書法字筆畫的次數(shù),

(3)

式中：?為異或操作.當(dāng)一個(gè)書法字橫筆畫越多,則掃描線垂直穿越書法字筆畫的次數(shù)越多,得到的Jh,k越大.

式(3)中i為1～M-2,缺少對圖像邊緣的處理；令bh,k為邊緣穿透數(shù),則有

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

(4)

式中：#表示集合中元素個(gè)數(shù).第k條垂直掃描線穿越書法字筆畫次數(shù)為dh,k=Jh,k+bh,k,dh,k按從小到大排序后,水平筆畫密度densityH可以寫為

(5)

式中：β為實(shí)驗(yàn)值,β=1/1.5.引入?yún)?shù)β是為了盡可能舍棄如圖1(b)、(d)所示的噪聲.圖1(b)中,右側(cè)的多余空白邊緣是在頁面切分時(shí)引入的,兩條垂直掃描線區(qū)域處返回的穿越次數(shù)為0,是干擾正確值的噪聲.圖1(d)中的噪聲是書寫時(shí)黏連造成的,使中間兩條垂直掃描線區(qū)域處返回的穿越次數(shù)為2,是干擾正確值的噪聲.式(5)取均值,是為了吸收噪聲.

圖1 筆畫密度掃描返回噪聲的2種情況Fig.1 Two kinds of noise indicated by blue vertical lines

同理可得垂直筆畫密度densityV.令Jv,k為第k條水平掃描線穿越書法字次數(shù),則有

(6)

一個(gè)書法字豎筆畫越多,則掃描線水平穿越書法字的次數(shù)越多,即得到的Jv,k越大.令bv,k為水平邊緣掃描線的穿透數(shù),則有

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

(7)

式中：#表示集合中元素個(gè)數(shù),則第k條垂直掃描線穿越書法字筆畫次數(shù)為dv,k=Jv,k+bv,k.同理可得水平筆畫密度：

(8)

式中：β=1/1.5.水平掃描線和垂直掃描線的筆畫穿透數(shù)與筆畫密度相關(guān),而與筆畫的傾斜角無關(guān),這忽略書法書寫時(shí)“橫不平、豎不直”引入的噪聲.穿越數(shù)統(tǒng)計(jì)的是入點(diǎn)和出點(diǎn),即此處遇到的筆畫個(gè)數(shù),避免了因書法筆畫粗細(xì)多變帶來的噪聲.

書法字的筆畫密度特征屬于書法字的結(jié)構(gòu)特征,當(dāng)書法字整體筆畫復(fù)雜度相同或相近時(shí),橫、豎筆畫數(shù)量未必相同,如漢字“三”和“川”,它們的筆畫復(fù)雜度大致相同,但橫向與豎向筆畫密度差距很大.水平筆畫密度和垂直筆畫密度具有良好的區(qū)分效果.

定義3 字的高寬比為單個(gè)書法字最小包圍盒的高寬比,

(9)

式中：height為單個(gè)書法字最小包圍盒的高度,width為寬度.

定義4 橫豎筆畫密度比density_ratio為水平筆畫密度與垂直筆畫密度的比,

(10)

2.3 顯著性表達(dá)

表1給出所提取的5個(gè)特征對應(yīng)的詳細(xì)說明.表中,f1、f2、f3、f4、f5分別為該書法字的筆畫復(fù)雜度、水平筆畫密度、垂直筆畫密度、字的高寬比以及橫豎筆畫密度比.

表1 所提取的特征

圖2 高寬比特征值為顯著及非顯著的2種情況示例Fig.2 Discriminative and non-discriminative examples of feature f4

對于不同的書法字,表1所描述的5個(gè)特征具有不同的鑒別力強(qiáng)度,類似于在TF-IDF算法中,對于不同的查詢文檔,每個(gè)詞出現(xiàn)的頻率不一樣.如圖2(a)所示的書法字“一”,鑒別力最強(qiáng)的特征為上述5個(gè)特征中的高寬比,因?yàn)樵撟值倪@個(gè)特征是其他漢字都不具備的,此時(shí)認(rèn)定高寬比為書法字“一”的關(guān)鍵特征.同樣的高寬比對于其他字不一定具有很好的鑒別力,如圖2(b)所示的書法字“林”,因?yàn)榇藭r(shí)大部分書法字的高寬比都與“林”字高寬比差別不大,起不到顯著區(qū)分效果.

當(dāng)一個(gè)書法字圖像中“橫”筆畫較多時(shí),則“橫”筆畫是主要特征,即由式(5)得到的水平筆畫密度較大,此時(shí)認(rèn)定水平筆畫密度為顯著性特征.當(dāng)書法字“豎”的筆畫較多時(shí),“豎”筆畫是主要特征,即由式(8)得到的垂直筆畫密度較大,此時(shí)認(rèn)定垂直筆畫密度為顯著性特征.當(dāng)書法字筆畫較復(fù)雜時(shí),筆畫復(fù)雜度是主要特征,此時(shí)認(rèn)定筆畫復(fù)雜度為顯著性特征,反之亦然.圖3展示了不同形態(tài)的原始書法字圖像“之”字、“書”字經(jīng)過預(yù)處理后的輪廓效果圖以及它們各自對應(yīng)的筆畫復(fù)雜度.

圖3 不同復(fù)雜度的書法字complexity值比較Fig.3 Character examples of different complexity

如圖3(a)、(b)、(c)所示為簡單書法字“之”的筆畫復(fù)雜度,圖3(d)～(f)所示為較復(fù)雜書法字“書”的筆畫復(fù)雜度.從complexity可以看出,同一個(gè)漢字的不同形態(tài)的書法字筆畫復(fù)雜度差異相對較小,而不同漢字的書法字圖像的筆畫復(fù)雜度差異較大,特別是對于極簡單或極復(fù)雜的書法字,筆畫復(fù)雜度具有良好的區(qū)分效果.

上述5種特征對于不同的書法字,鑒別力的強(qiáng)度不一樣,需要對不同書法字的特征進(jìn)行顯著性分析.每個(gè)書法字圖像都是唯一的,目前書法書籍在持續(xù)掃描、切分過程中,書法數(shù)據(jù)庫不斷增大；這些書法字的上述5個(gè)特征在特征內(nèi)是互相獨(dú)立的；即書法字的每個(gè)特征都是大量的、互相獨(dú)立的隨機(jī)變量,滿足中心極限定理的2個(gè)前提條件.有理由認(rèn)為上述書法字的每個(gè)特征值的分布逼近圖4所示的高斯分布N(μk,σk),可以用高斯分布模型逼近分析結(jié)果.

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

圖4中,μk、σk為第k個(gè)特征的均值和方差.對有限的13 351個(gè)書法字單字進(jìn)行特征統(tǒng)計(jì),如圖9所示,發(fā)現(xiàn)它們逼近高斯分布趨勢.

令X為用戶提交的樣本書法字,對X提取上述5種特征,記X的第k個(gè)特征為xk.根據(jù)高斯正態(tài)分布規(guī)律可知,特征值xk落入不同的范圍具有不同數(shù)量的相似字：

(11)

由式(11)可知,當(dāng)xi超出3σk范圍之外,即大于μk+3σk或小于μk-3σk時(shí),在該特征上與樣本字相似的書法字只占全部書法字?jǐn)?shù)量的(100%-99.73%)/2=0.135%.這意味著僅有極少量書法字在該特征上與樣本字有相似之處,該特征為樣本字的顯著性特征,根據(jù)該特征可以快速找到少量相似的書法字.當(dāng)特征xk落在2σk區(qū)間外,則在該特征上可以剪掉數(shù)據(jù)庫中95.45%不相似的字；當(dāng)特征xk落入[-σk,σk]內(nèi)時(shí),意味著數(shù)據(jù)庫中68.27%的書法字在該特征上與樣本字相似,該特征不是樣本字的顯著特征,使用該特征不能把相似字從數(shù)據(jù)庫中區(qū)分出來.

對于高斯分布區(qū)域內(nèi)的書法字特征,特征xk相對于μk的偏離程度可以用來表示該特征的顯著性(鑒別力)的大小.特征xk偏離μk越遠(yuǎn),鑒別力越強(qiáng).例如圖1的書法字“一”,它的高寬比為5,偏離接近于1的均值較遠(yuǎn),此時(shí)“一”的高寬比與其他漢字都不一樣,可以作為顯著性特征.反之,特征xk偏離μk越近,則顯著性(鑒別力)越弱,此時(shí)xk即為非顯著特征.

2.4 顯著因子計(jì)算

針對書法字不同特征的顯著性情況,需要一個(gè)值來表達(dá)各特征顯著性大小,這個(gè)值稱為“顯著因子”；顯著因子越大,則顯著性越強(qiáng).對用戶提交的樣本書法字X提取上述5種特征,樣本書法字的特征向量記為X=[x1,x2,x3,x4,x5],其中x1、x2、x3、x4、x5分別為樣本書法字筆畫復(fù)雜度、水平筆畫密度、垂直筆畫密度、字的高寬比和橫豎筆畫密度比.計(jì)算書法字?jǐn)?shù)據(jù)庫中特征fk對應(yīng)的均值μk和標(biāo)準(zhǔn)差σk,則第k個(gè)特征xk的顯著性因子wk為

(12)

wk用于表達(dá)特征xk對于樣本字X的顯著性,其中n=3.由式(12)可知,xk偏離μk越遠(yuǎn),wk越大,該特征的顯著性越強(qiáng)；xk離μk越近,wk越小,該特征的顯著性越不明顯.式(12)中用絕對值的方式避免出現(xiàn)某項(xiàng)是負(fù)值,從而導(dǎo)致正、負(fù)值中和的情況.對式(12)中右側(cè)的偏離值作n=3次方運(yùn)算,是用于放大顯著性差異.因?yàn)槠xσk之外,偏向于顯著特征,wk>1,大于1的數(shù)值作乘積后值變大；落入σk之內(nèi),偏向于非顯著特征,wk<1,小于1的數(shù)值作乘積后值變小.就顯著性差異區(qū)分度而言,n越大越好；就計(jì)算量而言,n越小越好,且n最好取整數(shù).折中兩方的取向,由實(shí)驗(yàn)測試可得n=3時(shí)效果最佳.

由式(12)可得,就筆畫復(fù)雜度這一項(xiàng),“順”字的鑒別力w1為

0.8473=0.608.

圖5 不同書法字特征值可視化比較Fig.5 Visualization of two different features

由式(8)計(jì)算得出“順”字的x3=9.094,數(shù)據(jù)庫中該特征對應(yīng)的均值和方差為D(μ3=5.258,σ3=1.598).由式(12)可得,就垂直筆畫密度這一項(xiàng),“順”字的鑒別力w3為

2.43=13.824.

對于指定的“順”字,垂直筆畫密度相對于筆畫復(fù)雜度更具有鑒別力.垂直筆畫密度特征應(yīng)賦予更大的權(quán)重,w3>w1.由于“順”字筆畫復(fù)雜度偏離均值為0.847σ,小于σ,而“順”字的垂直筆畫密度偏離均值距離為2.4σ,大于σ.式(12)作3次方運(yùn)算,使與均值的偏離程度不超過σ的特征值的顯著特征因子wk更??；偏離程度超過σ的特征值作3次方運(yùn)算,會(huì)把顯著特征因子wk變得更大.譬如,上述“順”字的筆畫復(fù)雜度的權(quán)重w1=0.608,垂直筆畫密度的權(quán)重w3=13.824,w3w1,即x3相對于x1而言,擁有較大權(quán)重.

3 自適應(yīng)匹配

3.1 特征歸一化

不同特征值的取值范圍在數(shù)值上有較大差別,不能直接求差,再求和.對于某項(xiàng)特征值,直接求差值所得的大數(shù)值并不能說明該特征是顯著特征,也又可能不是顯著特征；這要取決于群體中該項(xiàng)特征值間的差異.表2給出數(shù)據(jù)庫中13 351個(gè)書法字特征上述5種特征的統(tǒng)計(jì)情況.在求差異前,先要將它們歸一化到可比空間.

如圖5所示,書法字“順”與“言”的整體筆畫復(fù)雜度分別為232和210,筆畫復(fù)雜度差異值為22；垂直筆畫密度分別為9.094和3,垂直筆畫密度差異值為6.094.通過式(12)可得,此時(shí)垂直筆畫密度是書法字“順”與“言”的顯著性特征,而整體筆畫復(fù)雜度不是它們的顯著性特征.若在非歸一化的情況下,直接進(jìn)行特征融合來對2個(gè)書法字作比較,則會(huì)因?yàn)楣P畫復(fù)雜度特征差異值22大于垂直筆畫密度差異值6.094,成為相對非顯著特征,使整體筆畫復(fù)雜度比顯著性特征垂直筆畫密度具有更大的影響力,與實(shí)際情況相違背.對不同特征進(jìn)行歸一化,以使各特征在相似度量中具有可比性.

表2 書法字特征值的統(tǒng)計(jì)

特征歸一化方法有線性歸一化和非線性歸一化.采用非線性歸一化的方法.首先計(jì)算書法字?jǐn)?shù)據(jù)庫訓(xùn)練集T中各特征的均值μ與標(biāo)準(zhǔn)差σ,令μ=[μ1,μ2,μ3,μ4,μ5],σ=[σ1,σ2,σ3,σ4,σ5]，其中μ1、μ2、μ3、μ4、μ5分別對應(yīng)特征f1、f2、f3、f4、f5的均值,σ1、σ2、σ3、σ4、σ5分別對應(yīng)特征f1、f2、f3、f4、f5的方差.X=[x1,x2,x3,x4,x5]為查詢樣本字,其中x1、x2、x3、x4、x5為樣本中對應(yīng)特征f1、f2、f3、f4、f5的具體值；樣本書法字的第k(k=1,2,3,4,5)個(gè)特征值xk可以根據(jù)下式進(jìn)行歸一化,獲取可比特征值：

(13)

得到樣本字X相應(yīng)的可比特征向量q=[q1,q2,q3,q4,q5]. 令Y={Y1,Y2,…,Yn}表示書法數(shù)據(jù)庫中書法的集合,其中n為書法字?jǐn)?shù)據(jù)庫中候選字的總個(gè)數(shù),所提取的數(shù)據(jù)庫中第i個(gè)書法字的特征向量為Yi=[yi,1,yi,2,yi,3,yi,4,yi,5],其中yi,1、yi,2、yi,3、yi,4、yi,5分別為第i個(gè)候選書法字對應(yīng)特征f1、f2、f3、f4、f5的原始特征值.用式(13)計(jì)算得到第i個(gè)候選書法字的可比特征向量為Ci=[ci,1,ci,2,ci,3,ci,4,ci,5],其中

(14)

3.2 自適應(yīng)剪枝

Zhang等[12,14-17]針對書法字快速檢索的問題,都采用分層的方式,先找到可能與樣本字相似的候選字集合,再對集合中的每個(gè)書法字作匹配、排序出最相似的書法字.莊毅等[16]提出用高維索引的方式加快書法字檢索速度.分層、索引都需要一個(gè)標(biāo)準(zhǔn).俞凱等[14]沒有描述是如何分層的,即如何分類,標(biāo)準(zhǔn)是什么.分類的關(guān)鍵在于區(qū)分?jǐn)?shù)據(jù)庫中哪些是可能相似的書法字,哪些是不可能相似的.Zhang等[12,17]給出分層的標(biāo)準(zhǔn),但該標(biāo)準(zhǔn)是以每一個(gè)特征為單位進(jìn)行實(shí)驗(yàn)得到的,即每個(gè)特征有一個(gè)統(tǒng)一的剪枝閾值,未考慮不同樣本在該特征上有不同的差異.如果樣本的該特征值是均值,即由式(13)計(jì)算得到的可比特征值qk=0,是非顯著特征,用固定的閾值剪去部分?jǐn)?shù)據(jù)會(huì)引入錯(cuò)誤.如果樣本在該特征值上的可比值接近于極值,譬如圖1中“一”字的縱向筆畫密度接近極值,使qk≈3,這種情況下用固定不變的閾值剪枝會(huì)留下大部分不可能相似的候選字.

在文本方面,TF-IDF算法已成功應(yīng)用于各搜索引擎上；在圖像方面,Rui等[18]提出類似的圖像檢索算法CI-ICI算法,采用分量重要因子(component importance, CI)和逆集合重要性因子(inverse collection importance, ICI).若直接把式(12)中的wi賦值給cii,則cii=wi=fi/μ,與方差σ無關(guān),不合理.受逆集重要性因子icii=log2(σi+2)的計(jì)算方式的啟發(fā),構(gòu)建自適應(yīng)剪枝標(biāo)準(zhǔn)：

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

(15)

式中：qk為查詢樣本字的第k個(gè)可比特征值,ci,k為數(shù)據(jù)庫集合中第i個(gè)字的第k個(gè)可比特征.式(15)右側(cè)3-log2(qk+1)稱為剪枝閾值,滿足式(15)的ci,k的取值范圍稱為候選區(qū)域,由ci,k對應(yīng)的數(shù)據(jù)庫中的書法字Yi被歸到可能相似的類,保留；其余書法字作為不可能相似的類,剪除.

查詢樣本字不同,相應(yīng)的可比特征qk不同.qk所處區(qū)域的不同,直接影響到可能相似的類大小.在實(shí)際計(jì)算中,qk是在(-4,4)內(nèi)的一個(gè)隨機(jī)值.表3列舉了qk取幾個(gè)特定值時(shí),用式(15)的剪枝標(biāo)準(zhǔn)計(jì)算,保留(剩下)的類大小.由表3可知,當(dāng)qk=0時(shí),剩下的書法字占數(shù)據(jù)庫中的99.73%,幾乎沒剪去什么字.由式(13)可知,qk=0意味著xk=μk,即該特征等于平均值,是最大眾化特征,不是顯著特征,不能根據(jù)該特征剪去其他字.當(dāng)qk=3或qk=-3時(shí),該特征值偏離均值,顯著性強(qiáng),剪枝后剩下部分僅有1.1%,即使可選的候選集縮小到原來的1.1%.

表3 特征值不同導(dǎo)致候選區(qū)域不同

3.3 自適應(yīng)排序

不同的查詢樣本字所剩下的可能相似的集合大小不同.需要進(jìn)行匹配、排序,用Match(q,Ci)表示樣本字q與Ci的相似度：

(16)

式中：wk為由式(12)計(jì)算得到的顯著性因子,|qk-ci,k|為樣本書法字q與候選書法字Ci在第k維特征值上歸一化后的差異程度.Match(q,Ci)越大,兩個(gè)字的相似度越弱.按Match(q,Ci)從小到大排序,排在最前面的是與樣本字最相似的候選字.

當(dāng)用戶對響應(yīng)時(shí)間要求較高時(shí),快速返回自適應(yīng)排序結(jié)果；當(dāng)對檢索效果要求高時(shí),則繼續(xù)運(yùn)行耗時(shí)的形狀匹配法,以時(shí)間換取更精確的檢索結(jié)果.

3.4 形狀匹配

通過上述自適應(yīng)算法,可得與樣本書法字同一類別的候選書法字,需要進(jìn)一步對同一類別的候選書法字進(jìn)行相似度排序,即對書法字圖像進(jìn)行精確匹配,找到與樣本書法字最相似的候選字.采用類似基于輪廓相似性的書法字匹配方法[1],對提取的每個(gè)輪廓點(diǎn)采用極坐標(biāo)分塊的方法,將周圍空間從方向上均分為8個(gè)角度,在半徑上按近似log2r的長度劃分為4份.若書法字歸一化大小為64×64像素,則每個(gè)分割點(diǎn)位于r=8、r=16、r=32和r=64的位置.

圖6展示了空間混合分割坐標(biāo)系統(tǒng),該系統(tǒng)將周圍空間一共分割為32塊.其中,每一塊所占的空間從內(nèi)向外逐漸增大.因?yàn)閷υ擖c(diǎn)越有鑒別力的點(diǎn),在空間距離上離該點(diǎn)越近；相對越遠(yuǎn)的點(diǎn),對該點(diǎn)的鑒別力越弱.在同一環(huán)上,每一塊所占的空間大小是一樣的,因?yàn)樗闹芟嗤嚯x的點(diǎn)對該點(diǎn)的鑒別力是一樣的.計(jì)算落在每一塊里輪廓點(diǎn)的個(gè)數(shù),再計(jì)算書法字中每個(gè)關(guān)鍵點(diǎn)與另一個(gè)書法字中在關(guān)鍵點(diǎn)一定范圍內(nèi)的相似點(diǎn)之間的距離,得到2個(gè)書法字關(guān)鍵點(diǎn)之間的相似度.依據(jù)相似度,最終確定類別.

圖6 書法字原圖像及相應(yīng)的極坐標(biāo)系 Fig.6 Original character image and corresponding polar coordinates for extract feature of shape context

由n個(gè)點(diǎn)組成的書法字A={ai|i=1,2,…,n},每個(gè)輪廓點(diǎn)都會(huì)產(chǎn)生32維特征值,則第i個(gè)輪廓點(diǎn)的32個(gè)特征值可以表示為(ai1,ai2,ai3,…,ai32).對于一個(gè)擁有n個(gè)輪廓點(diǎn)表征的書法字,可以構(gòu)造一個(gè)n×32的形狀矩陣：

與文獻(xiàn)[1]使用的方法不同,本文的相似度計(jì)算不是采用歐式距離,而是采用余弦相似度.在高維空間中,夾角余弦更好地反映出圖像數(shù)據(jù)點(diǎn)之間的空間分布情況,數(shù)據(jù)點(diǎn)之間的夾角余弦越大越相似.樣本字中第i個(gè)輪廓點(diǎn)Mi與候選字中第j個(gè)輪廓點(diǎn)Nj的近似匹配程度cos (Mi,Nj)為

(17)

式中：mi,k為樣本字第i個(gè)輪廓點(diǎn)Mi的第k維的值,nj,k為候選字第j個(gè)輪廓點(diǎn)Nj的第k維的值.cos (Mi,Nj)越大,兩個(gè)點(diǎn)越相似.擁有最大值的點(diǎn)是最相似點(diǎn)或者說是對應(yīng)點(diǎn).令Si為樣本字點(diǎn)Mi與對應(yīng)點(diǎn)的匹配值,則有

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

(18)

樣本字A與數(shù)據(jù)庫中一個(gè)候選字C的形狀匹配值是它們的所有輪廓點(diǎn)的近似匹配值之和：

Sim(A,C)=

(19)

式中：arcarccos(Mi,corresp(Mi))為點(diǎn)Mi與對應(yīng)點(diǎn)corresp(Mi)之間的夾角；λ為懲罰因子,兩點(diǎn)夾角越大,懲罰值越大.在該實(shí)驗(yàn)中,λ=0.2.

4 實(shí)驗(yàn)分析

4.1 數(shù)據(jù)獲取

實(shí)驗(yàn)所用的原始書法頁面圖像和書法字圖像來自中美百萬冊數(shù)字圖書館CADAL項(xiàng)目[12].書法頁面圖像掃描的精度是600DPI(Dot Per Inch,每英寸點(diǎn)數(shù)),圖像格式是TIFF格式.所采用的頁面圖像已經(jīng)在筆者的前期研究[11]中切分為單字圖像.實(shí)驗(yàn)中的數(shù)據(jù)來自18本掃描得到的《中國書法全集》的頁面圖像,切分了483個(gè)頁面,得到13 351個(gè)書法字圖像.如圖7所示,為該實(shí)驗(yàn)所采用的單個(gè)書法字樣例.

圖7 單字圖像樣例Fig.7 Screenshot of individual original characters

原始頁面圖像掃描精度為600 DPI,其結(jié)果是一個(gè)尺寸大小為20 cm×20 cm的紙張頁面,掃描后得到4 722×4 722個(gè)像素點(diǎn)的頁面圖像文件.若直接處理,則像素點(diǎn)太多,速度太慢.將圖像在橫向和縱向上均縮小了5倍,即將圖像像素大小變?yōu)樵瓐D的1/25倍.作完縮放處理后的單個(gè)書法字圖像的大小統(tǒng)計(jì)如表4所示.

表4 書法字圖像大小

這些數(shù)據(jù)來自211個(gè)作品,最大的作品含1 245個(gè)單字,作品名為：蔡玉卿小楷《孝經(jīng)》.圖8給出單個(gè)作品中所含字?jǐn)?shù)的統(tǒng)計(jì),只列出字?jǐn)?shù)超過50的作品.圖中,n為作品序號(hào),按作品所含字的個(gè)數(shù)從大到小順序排列;Nw為統(tǒng)計(jì)得到的單個(gè)作品的字?jǐn)?shù).為了給檢索結(jié)果的正確性提供一個(gè)檢驗(yàn)標(biāo)準(zhǔn),采用前期交互式標(biāo)注法[19],對所有單個(gè)漢字的圖像內(nèi)容進(jìn)行標(biāo)注,該標(biāo)注內(nèi)容稱為標(biāo)簽,并構(gòu)建了書法數(shù)據(jù)庫.對數(shù)據(jù)庫中的單字進(jìn)行統(tǒng)計(jì)[20]后,已發(fā)現(xiàn)這些標(biāo)簽在作品中出現(xiàn)的頻次大致上遵循齊普夫定律(Zipf’s Law).

圖8 作品中包含的字?jǐn)?shù)統(tǒng)計(jì)：字?jǐn)?shù)超過50的作品按從大到小順序排列 Fig.8 Number of character per work, with works contains more than 50 individual characters are counted

對數(shù)據(jù)庫中的每個(gè)單字進(jìn)行預(yù)處理、輪廓提取,獲取表1中的f1、f2、f3、f4、f5特征.這些特征歸一化到64×64像素大小的空間.統(tǒng)計(jì)數(shù)據(jù)庫中13 351個(gè)書法字圖像的特征值,可得各特征數(shù)值分布均趨向于正態(tài)(高斯)分布,如圖9所示.圖中，N為具有該特征值的樣本個(gè)數(shù).

圖9 書法字5個(gè)特征值的分布圖Fig.9 Distribution of five features

由實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果顯示樣本特征值的分布與正態(tài)分布有所偏離,這是因?yàn)榻y(tǒng)計(jì)的樣本數(shù)未真正達(dá)到大數(shù)據(jù)量.數(shù)據(jù)庫中的樣本數(shù)越大,特征值越趨向于正態(tài)分布.由圖9知,書法字整體筆畫復(fù)雜度為66～363；水平筆畫密度為1.579～14.396；垂直筆畫密度為1.475～11.276.其中,書法字整體筆畫復(fù)雜度在170～230內(nèi)比較集中,分布密度較大.若樣本書法字的筆畫復(fù)雜度落在該區(qū)間,則在筆畫復(fù)雜度的顯著性因子較小.此時(shí),大部分書法字的整體筆畫復(fù)雜度都與該字有交疊,起不到區(qū)分效果.相反,書法字整體筆畫復(fù)雜度在趨近于兩端時(shí),數(shù)量明顯減少且分布密度比較松散,若位于該區(qū)間,則筆畫復(fù)雜度的顯著因子較大,表示顯著性較強(qiáng).

4.2 運(yùn)行結(jié)果

圖10展示了采用自適應(yīng)層次分類的方法進(jìn)行分層檢索的2個(gè)樣例.檢索界面返回的是檢索結(jié)果中最相似的前30個(gè)書法字,其中第1行為用戶提交的書法字圖像樣例；第2～4行為檢索結(jié)果,按相似度由高到低排序.每個(gè)圖像的下方數(shù)字為該字與樣本字相似性計(jì)算的匹配值,匹配值越大越相似.

圖10 運(yùn)行自適應(yīng)匹配和檢索例子Fig.10 Screenshot of one adaptive matching example

如圖10(a)所示為書法字“可”的檢索結(jié)果,在前24個(gè)檢索結(jié)果中沒有錯(cuò)字出現(xiàn).在前30個(gè)檢索結(jié)果中,第25個(gè)和第28個(gè)均出現(xiàn)被誤識(shí)的“耳”字,這是因?yàn)椤岸弊峙c“可”字在形狀上較相似,在使用基于形狀相似性的檢索方法時(shí),被認(rèn)為是形狀相似,出現(xiàn)誤差.可以看出,隨著相似度的降低,“可”字書體風(fēng)格出現(xiàn)了明顯變化.圖10(b)展示的是書法字“無”的檢索結(jié)果,其中出現(xiàn)一個(gè)“無”字排在檢索結(jié)果的第29位,相似度較低.這是因?yàn)樵摵蜻x字的書寫風(fēng)格發(fā)生明顯變化,產(chǎn)生了較大的形變,從而導(dǎo)致相似度下降.

4.3 性能分析

采用Visual C++作為開發(fā)平臺(tái),PC配置Intel(R) Core(TM) i5-4300處理器,2.50 GHz主頻,8 GB內(nèi)存,Windows 7操作系統(tǒng).

為了驗(yàn)證自適應(yīng)層次分類檢索方法的總體運(yùn)行性能,用查全率、查準(zhǔn)率和查詢時(shí)間衡量運(yùn)行性能.

(20)

(21)

用random函數(shù)隨機(jī)選取數(shù)據(jù)庫中的50個(gè)書法字圖像作為樣本進(jìn)行測試,剩下的書法字作為實(shí)驗(yàn)用的檢索數(shù)據(jù)庫.圖11給出隨機(jī)選取的50個(gè)樣本字作檢索時(shí)的平均查全率和查準(zhǔn)率曲線.將自適應(yīng)層次分類檢索方法與基于輪廓相似性的單層檢索方法[1]和基于分層檢索方法[13]進(jìn)行比較.

圖11 平均查全率與平均查準(zhǔn)率對比Fig.11 Comparison of recall and precision ratio for three approaches

圖11的結(jié)果顯示,與文獻(xiàn)[13]相比,在相同的數(shù)據(jù)庫下,本文的自適應(yīng)方法在查全率相等的情況下,查準(zhǔn)率平均上升了10%左右.圖11的對比結(jié)果顯示,自適應(yīng)方法的查全率和查準(zhǔn)率優(yōu)于文獻(xiàn)[13]的分層匹配法.將圖11與文獻(xiàn)[13]中圖9的查全率和查準(zhǔn)率進(jìn)行對比,會(huì)發(fā)現(xiàn)文獻(xiàn)[13]的分層匹配法在該實(shí)驗(yàn)中的具體查全率和查準(zhǔn)率有所下降,這主要有以下2個(gè)原因：1)俞凱等[13]使用的數(shù)據(jù)庫大小是3 012個(gè),而本文使用的是13 351個(gè),擴(kuò)大了4.43倍；2)俞凱等[13]對每個(gè)特征使用統(tǒng)一的閾值剪枝,不考慮查詢樣本間的差異,這樣的剪枝法容易造成誤剪,尤其是當(dāng)數(shù)據(jù)庫擴(kuò)大之后,會(huì)在剪枝過程中錯(cuò)誤剪掉相似書法候選字.與文獻(xiàn)[1]相比,數(shù)據(jù)庫大小上升后,采用單一的形狀匹配法得到的查準(zhǔn)率和查全率迅速下降,主要由以下2個(gè)原因造成：1)文獻(xiàn)[1]中的數(shù)據(jù)庫大小是1 650個(gè),該實(shí)驗(yàn)中為13 351個(gè),擴(kuò)大了8倍； 2)形狀匹配用的是輪廓點(diǎn)表達(dá)書法字,輪廓點(diǎn)是底層特征,與高層的筆畫結(jié)構(gòu)存在語義上的差異；同理,用像素點(diǎn)集的相似性去表達(dá)圖像內(nèi)容的相似性存在語義上的鴻溝.由此可知,要提高匹配的效率,需要結(jié)合高層語義特征,譬如書法字的筆畫密度特征.

表5給出隨機(jī)選取的50個(gè)樣本字,在3種不同方法下的平均檢索時(shí)間t的比較.可以看出：采用自適應(yīng)層次分類的檢索方法在速度上比文獻(xiàn)[1]的檢索方法有了明顯提升,這是因?yàn)樽赃m應(yīng)算法有剪枝,與形狀匹配所用的特征維數(shù)(平均為150)相比,剪枝所用的特征維數(shù)(5)降低30倍.與文獻(xiàn)[13]的檢索時(shí)間相比,沒多大提高,基本持平.

表5 平均檢索時(shí)間對比

5 結(jié) 語

本文提出自適應(yīng)的書法字圖像匹配和檢索方法,先離線分析了數(shù)據(jù)庫中各特征值分布范圍,發(fā)現(xiàn)它們趨向于高斯分布,這是對前期研究發(fā)現(xiàn)書法字標(biāo)簽符合齊普夫定律(Zipf’s Law)的一個(gè)進(jìn)步.在此基礎(chǔ)上,根據(jù)不同查詢樣本的不同特征值,作自適應(yīng)剪枝、匹配.實(shí)驗(yàn)結(jié)果表明,該方法比以往2種書法檢索算法的效果好.

在書法數(shù)據(jù)庫進(jìn)一步增大的情況下,匹配和檢索速度降低,須針對書法字?jǐn)?shù)據(jù)庫維數(shù)高、數(shù)據(jù)量大的特點(diǎn),進(jìn)一步研究大數(shù)據(jù)量書法字的高維索引法.譬如將大數(shù)據(jù)量書法字圖像的索引與處理部署到云計(jì)算平臺(tái)Hadoop上,利用云計(jì)算平臺(tái)高效的處理能力來提高書法字檢索的整體運(yùn)算效率和速度.

[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] 潘云鶴, 吳飛. 網(wǎng)上多媒體信息分析與檢索[M]. 北京: 清華大學(xué)出版社, 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方法識(shí)別脫機(jī)手寫漢字[J].模式識(shí)別與人工智能,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] 馬龍龍,劉成林.基于統(tǒng)計(jì)部首模型的聯(lián)機(jī)手寫漢字識(shí)別方法[J].智能系統(tǒng)學(xué)報(bào), 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ù)形狀相似性的書法內(nèi)容檢索[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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ù)骨架結(jié)構(gòu)相似性的書法內(nèi)容分層檢索[J].小型微型計(jì)算機(jī)系統(tǒng),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] 莊毅,莊越挺,吳飛.基于數(shù)據(jù)網(wǎng)格的書法字k近鄰查詢[J].軟件學(xué)報(bào), 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. 浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

國家自然科學(xué)基金資助項(xiàng)目(61303100)；上海海事大學(xué)校基金資助項(xiàng)目(20130467).

章夏芬(1977—)，女，講師，從事圖像處理、模式識(shí)別的研究. 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