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

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

?

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

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

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

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

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

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

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

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

1 相關(guān)研究

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

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

上述分層剪枝法、用骨架點(diǎn)替代輪廓以降維、用拐點(diǎn)、端點(diǎn)表達(dá)書(shū)法字以減少特征維數(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)說(shuō)明

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

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

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

2.2 特征提取

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

(1)

各特征的定義如下.

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

(2)

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

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

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

(3)

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

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

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

(4)

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

(5)

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

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

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

(6)

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

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

(7)

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

(8)

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

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

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

(9)

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

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

(10)

2.3 顯著性表達(dá)

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

表1 所提取的特征

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

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

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

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

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

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

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

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

令X為用戶提交的樣本書(shū)法字,對(duì)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í),在該特征上與樣本字相似的書(shū)法字只占全部書(shū)法字?jǐn)?shù)量的(100%-99.73%)/2=0.135%.這意味著僅有極少量書(shū)法字在該特征上與樣本字有相似之處,該特征為樣本字的顯著性特征,根據(jù)該特征可以快速找到少量相似的書(shū)法字.當(dāng)特征xk落在2σk區(qū)間外,則在該特征上可以剪掉數(shù)據(jù)庫(kù)中95.45%不相似的字；當(dāng)特征xk落入[-σk,σk]內(nèi)時(shí),意味著數(shù)據(jù)庫(kù)中68.27%的書(shū)法字在該特征上與樣本字相似,該特征不是樣本字的顯著特征,使用該特征不能把相似字從數(shù)據(jù)庫(kù)中區(qū)分出來(lái).

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

2.4 顯著因子計(jì)算

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

(12)

wk用于表達(dá)特征xk對(duì)于樣本字X的顯著性,其中n=3.由式(12)可知,xk偏離μk越遠(yuǎn),wk越大,該特征的顯著性越強(qiáng)；xk離μk越近,wk越小,該特征的顯著性越不明顯.式(12)中用絕對(duì)值的方式避免出現(xiàn)某項(xiàng)是負(fù)值,從而導(dǎo)致正、負(fù)值中和的情況.對(duì)式(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)測(cè)試可得n=3時(shí)效果最佳.

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

0.8473=0.608.

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

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

2.43=13.824.

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

3 自適應(yīng)匹配

3.1 特征歸一化

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

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

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

特征歸一化方法有線性歸一化和非線性歸一化.采用非線性歸一化的方法.首先計(jì)算書(shū)法字?jǐn)?shù)據(jù)庫(kù)訓(xùn)練集T中各特征的均值μ與標(biāo)準(zhǔn)差σ,令μ=[μ1,μ2,μ3,μ4,μ5],σ=[σ1,σ2,σ3,σ4,σ5]，其中μ1、μ2、μ3、μ4、μ5分別對(duì)應(yīng)特征f1、f2、f3、f4、f5的均值,σ1、σ2、σ3、σ4、σ5分別對(duì)應(yīng)特征f1、f2、f3、f4、f5的方差.X=[x1,x2,x3,x4,x5]為查詢樣本字,其中x1、x2、x3、x4、x5為樣本中對(duì)應(yīng)特征f1、f2、f3、f4、f5的具體值；樣本書(shū)法字的第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ū)法數(shù)據(jù)庫(kù)中書(shū)法的集合,其中n為書(shū)法字?jǐn)?shù)據(jù)庫(kù)中候選字的總個(gè)數(shù),所提取的數(shù)據(jù)庫(kù)中第i個(gè)書(shū)法字的特征向量為Yi=[yi,1,yi,2,yi,3,yi,4,yi,5],其中yi,1、yi,2、yi,3、yi,4、yi,5分別為第i個(gè)候選書(shū)法字對(duì)應(yīng)特征f1、f2、f3、f4、f5的原始特征值.用式(13)計(jì)算得到第i個(gè)候選書(shū)法字的可比特征向量為Ci=[ci,1,ci,2,ci,3,ci,4,ci,5],其中

(14)

3.2 自適應(yīng)剪枝

Zhang等[12,14-17]針對(duì)書(shū)法字快速檢索的問(wèn)題,都采用分層的方式,先找到可能與樣本字相似的候選字集合,再對(duì)集合中的每個(gè)書(shū)法字作匹配、排序出最相似的書(shū)法字.莊毅等[16]提出用高維索引的方式加快書(shū)法字檢索速度.分層、索引都需要一個(gè)標(biāo)準(zhǔn).俞凱等[14]沒(méi)有描述是如何分層的,即如何分類(lèi),標(biāo)準(zhǔn)是什么.分類(lèi)的關(guān)鍵在于區(qū)分?jǐn)?shù)據(jù)庫(kù)中哪些是可能相似的書(shū)法字,哪些是不可能相似的.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中“一”字的縱向筆畫(huà)密度接近極值,使qk≈3,這種情況下用固定不變的閾值剪枝會(huì)留下大部分不可能相似的候選字.

在文本方面,TF-IDF算法已成功應(yīng)用于各搜索引擎上；在圖像方面,Rui等[18]提出類(lèi)似的圖像檢索算法CI-ICI算法,采用分量重要因子(component importance, CI)和逆集合重要性因子(inverse collection importance, ICI).若直接把式(12)中的wi賦值給cii,則cii=wi=fi/μ,與方差σ無(wú)關(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ù)庫(kù)集合中第i個(gè)字的第k個(gè)可比特征.式(15)右側(cè)3-log2(qk+1)稱為剪枝閾值,滿足式(15)的ci,k的取值范圍稱為候選區(qū)域,由ci,k對(duì)應(yīng)的數(shù)據(jù)庫(kù)中的書(shū)法字Yi被歸到可能相似的類(lèi),保留；其余書(shū)法字作為不可能相似的類(lèi),剪除.

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

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

3.3 自適應(yīng)排序

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

(16)

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

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

3.4 形狀匹配

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

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

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

由n個(gè)點(diǎn)組成的書(shū)法字A={ai|i=1,2,…,n},每個(gè)輪廓點(diǎn)都會(huì)產(chǎn)生32維特征值,則第i個(gè)輪廓點(diǎn)的32個(gè)特征值可以表示為(ai1,ai2,ai3,…,ai32).對(duì)于一個(gè)擁有n個(gè)輪廓點(diǎn)表征的書(shū)法字,可以構(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)或者說(shuō)是對(duì)應(yīng)點(diǎn).令Si為樣本字點(diǎn)Mi與對(duì)應(yīng)點(diǎn)的匹配值,則有

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

(18)

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

Sim(A,C)=

(19)

式中：arcarccos(Mi,corresp(Mi))為點(diǎn)Mi與對(duì)應(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ū)法頁(yè)面圖像和書(shū)法字圖像來(lái)自中美百萬(wàn)冊(cè)數(shù)字圖書(shū)館CADAL項(xiàng)目[12].書(shū)法頁(yè)面圖像掃描的精度是600DPI(Dot Per Inch,每英寸點(diǎn)數(shù)),圖像格式是TIFF格式.所采用的頁(yè)面圖像已經(jīng)在筆者的前期研究[11]中切分為單字圖像.實(shí)驗(yàn)中的數(shù)據(jù)來(lái)自18本掃描得到的《中國(guó)書(shū)法全集》的頁(yè)面圖像,切分了483個(gè)頁(yè)面,得到13 351個(gè)書(shū)法字圖像.如圖7所示,為該實(shí)驗(yàn)所采用的單個(gè)書(shū)法字樣例.

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

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

表4 書(shū)法字圖像大小

這些數(shù)據(jù)來(lái)自211個(gè)作品,最大的作品含1 245個(gè)單字,作品名為：蔡玉卿小楷《孝經(jīng)》.圖8給出單個(gè)作品中所含字?jǐn)?shù)的統(tǒng)計(jì),只列出字?jǐn)?shù)超過(guò)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],對(duì)所有單個(gè)漢字的圖像內(nèi)容進(jìn)行標(biāo)注,該標(biāo)注內(nèi)容稱為標(biāo)簽,并構(gòu)建了書(shū)法數(shù)據(jù)庫(kù).對(duì)數(shù)據(jù)庫(kù)中的單字進(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ù)超過(guò)50的作品按從大到小順序排列 Fig.8 Number of character per work, with works contains more than 50 individual characters are counted

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

圖9 書(shū)法字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ù)庫(kù)中的樣本數(shù)越大,特征值越趨向于正態(tài)分布.由圖9知,書(shū)法字整體筆畫(huà)復(fù)雜度為66～363；水平筆畫(huà)密度為1.579～14.396；垂直筆畫(huà)密度為1.475～11.276.其中,書(shū)法字整體筆畫(huà)復(fù)雜度在170～230內(nèi)比較集中,分布密度較大.若樣本書(shū)法字的筆畫(huà)復(fù)雜度落在該區(qū)間,則在筆畫(huà)復(fù)雜度的顯著性因子較小.此時(shí),大部分書(shū)法字的整體筆畫(huà)復(fù)雜度都與該字有交疊,起不到區(qū)分效果.相反,書(shū)法字整體筆畫(huà)復(fù)雜度在趨近于兩端時(shí),數(shù)量明顯減少且分布密度比較松散,若位于該區(qū)間,則筆畫(huà)復(fù)雜度的顯著因子較大,表示顯著性較強(qiáng).

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

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

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

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

4.3 性能分析

采用Visual C++作為開(kāi)發(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)層次分類(lèi)檢索方法的總體運(yùn)行性能,用查全率、查準(zhǔn)率和查詢時(shí)間衡量運(yùn)行性能.

(20)

(21)

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

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

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

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

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

5 結(jié) 語(yǔ)

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

在書(shū)法數(shù)據(jù)庫(kù)進(jìn)一步增大的情況下,匹配和檢索速度降低,須針對(duì)書(shū)法字?jǐn)?shù)據(jù)庫(kù)維數(shù)高、數(shù)據(jù)量大的特點(diǎn),進(jìn)一步研究大數(shù)據(jù)量書(shū)法字的高維索引法.譬如將大數(shù)據(jù)量書(shū)法字圖像的索引與處理部署到云計(jì)算平臺(tái)Hadoop上,利用云計(jì)算平臺(tái)高效的處理能力來(lái)提高書(shū)法字檢索的整體運(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ī)手寫(xiě)漢字[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ī)手寫(xiě)漢字識(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ù)形狀相似性的書(shū)法內(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] 俞凱,吳江琴,莊越挺.基于骨架相似性的書(shū)法字檢索[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] 俞凱,吳江琴.書(shū)法字快速多層檢索方法[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)相似性的書(shū)法內(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)格的書(shū)法字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

國(guó)家自然科學(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