基于空間關(guān)系的維吾爾文圖像關(guān)鍵詞檢索

徐學(xué)斌，阿里木江·阿布迪日依木，朱亞俐, 阿力木江·艾沙，庫爾班·吾布力+

(1.新疆大學(xué) 信息科學(xué)與工程學(xué)院(網(wǎng)絡(luò)空間安全學(xué)院)，新疆 烏魯木齊 830046；2.新疆維吾爾自治區(qū)科技項目服務(wù)中心 項目服務(wù)部，新疆 烏魯木齊 830002；3.新疆大學(xué) 教師工作部，新疆 烏魯木齊 830046)

0 引 言

隨著文檔圖像的規(guī)模越來越大，快速準(zhǔn)確度檢索此類文檔逐漸成為研究熱點(diǎn)。對于中文、英文等語言，ORC[1](光學(xué)字符識別)技術(shù)已非常成熟，檢索速度快，準(zhǔn)確率高。對于我國新疆地區(qū)常用的少數(shù)民族語言維吾爾語而言，投入的研究資源較少，并且字符的黏連特性加大了字符的識別難度，因此目前尚無較成熟的維吾爾語OCR技術(shù)[2]。近來有學(xué)者提出針對文檔圖像的關(guān)鍵詞檢索方法，首先對文檔圖像進(jìn)行單詞切分并提取特征，然后將輸入單詞圖像與切分后的單詞圖像庫中的單詞圖像逐一進(jìn)行特征匹配，返回相似度較高的單詞圖像的頁碼等信息。關(guān)鍵詞檢索無需對構(gòu)成單詞的字符進(jìn)行精確切分和識別，大大降低了檢索系統(tǒng)的復(fù)雜度，對于不易進(jìn)行字符切分和識別的文檔，如字符粘連型語言文檔、手寫體文檔、古籍文檔等文獻(xiàn)的檢索有重要意義。周文杰等用形態(tài)學(xué)梯度算法對維吾爾文檔圖像進(jìn)行單詞切分[3]，然后根據(jù)切分后單詞圖像的LBP(局部二制模式)等特征來實現(xiàn)關(guān)鍵詞檢索[4]。李靜靜[5]提出基于層級匹配的維吾爾文關(guān)鍵詞檢索，將匹配過程分為粗匹配和精匹配兩個階段，來提高檢索效率。喻庚等[6]提出了基于索引的快速手寫體中文文檔檢索方法，通過提取文本的候選切分-識別網(wǎng)格來生成索引文件，然后在索引文件中查找對應(yīng)關(guān)鍵詞。白淑霞等[7]提出了基于線性判別分析主題模型[8,9]的關(guān)鍵詞檢索方法，實現(xiàn)了蒙古文古籍文獻(xiàn)的檢索。

基于空間關(guān)系的維吾爾文關(guān)鍵詞檢索方法首先對印刷體維吾爾文檔圖像進(jìn)行單詞切分，生成單詞圖像集合，然后提取單詞圖像中各連體段之間的空間關(guān)系特征并生成特征文件，提取輸入單詞圖像的特征并在特征文件中查找與其相似的特征，返回該特征對應(yīng)的文檔信息，從而實現(xiàn)印刷體維吾爾文檔圖像的關(guān)鍵詞檢索，檢索系統(tǒng)框架如圖1所示。

圖1 系統(tǒng)框架

1 維吾爾文單詞圖像切分

1.1 圖像預(yù)處理

單詞切分的準(zhǔn)確性直接影響關(guān)鍵詞檢索的效果，為了更好執(zhí)行單詞切分任務(wù)，在切分之前需要對文檔圖像進(jìn)行預(yù)處理，主要包括圖像去噪、傾斜校正[10]、亮度調(diào)整以及灰度化二值化[11]等。預(yù)處理工作的目的是使圖像中文字的筆畫信息更加清晰，突出文字像素和背景像素之間的差別，同時減小不同圖像之間的亮度和對比度差別。

1.2 單詞圖像切分

單詞圖像切分[12]主要分為文本行圖像切分、連體段切分[13]以及合并屬于同一單詞的連體段。首先對預(yù)處理后的文檔圖像進(jìn)行水平投影，得到每一行的行像素累加值。經(jīng)過預(yù)處理后圖像中有文字信息的黑色像素點(diǎn)的像素值為0，空白像素點(diǎn)的像素值為255，所以文本行的行像素累加值明顯小于空白行的行像素累加值。根據(jù)文本行和空白行的行像素累加值的大小，通過設(shè)定閾值，并將每一行的像素累加值與閾值比較大小，大于設(shè)定閾值則說明此行沒有文字信息，為空白行，反之則說明此行為含有文字信息，屬于文本行。閾值的大小設(shè)為空白行的行像素累加值減去300，即可區(qū)分文本行和空白行，減去300的目的是減小二值化過程中引入的噪聲對判別的干擾。由于文本行和空白行在垂直方向上都有一定的連續(xù)性，不會單獨(dú)出現(xiàn)一行，根據(jù)這一特點(diǎn)即可找出所有文本行在垂直方向上的始末位置，從而將其準(zhǔn)確切分出來。完成文本行切分后，需要對文本行圖像進(jìn)行連體段切分。連體段的切分原理同文本行切分原理相同，通過對文本行圖形進(jìn)行垂直投影，根據(jù)列像素累加值的差異性，即可將文本行圖像中連體段之間的空白列與包含文字信息的文本列區(qū)分出來，從而找到所有連體段在文本行中水平方向的始末位置，將其切分出來，投影示意圖如圖2所示。

圖2 文本行和連體段切分效果

完成文本行圖像中的連體段切分后，需要對屬于同一單詞的連體段進(jìn)行合并才能獲得完整單詞的位置坐標(biāo)，從而實現(xiàn)單詞圖像切分。由于在維吾爾文中，單詞之間的空白間隙與單詞內(nèi)部連體段之間的空白間隙有明顯的不同，根據(jù)此差異性，設(shè)置合理的閾值來區(qū)分不同的空白間隙。根據(jù)維吾爾語的書寫規(guī)則，連體段的合并從右往左進(jìn)行，若連體段間的間隙值小于設(shè)定閾值，則說明此間隙屬于單詞內(nèi)部，將與此間隙相鄰的連體段的位置進(jìn)行合并，反之則說明此間隙屬于單詞之間的間隙，記錄此間隙右側(cè)經(jīng)過合并的連體段的位置，此位置即為一個完成單詞的位置。以此規(guī)則從右往左依次進(jìn)行，即可找出文本行圖像中所有單詞的位置，從而將其切分出來。由于任意文本行中的空白間隙由單詞內(nèi)部的間隙與單詞之間的間隙組成，當(dāng)單詞的字體、字號等不同時，間隙的值也會發(fā)生相應(yīng)變化。通過對文本行中的間隙進(jìn)行K-means聚類[14]處理來獲得判別閾值，來減小上述變化對設(shè)置閾值的影響。設(shè)間隙判別閾值為M，則M的計算公式如下

M=(A+B)/2+1

(1)

其中，A與B分別為對文本行中所有間隙采用K-means聚類時獲得的兩個聚類中心，完整的單詞切分效果圖如圖3所示。

圖3 單詞切分效果

1.3 單詞位置信息

在單詞切分中，獲得單詞圖像在文檔圖像中的位置信息后，將單詞圖像單獨(dú)保存在文件中，同時需要將單詞圖像的位置信息保存在文件中，使其能夠在最終返回給用戶的文檔圖像中用矩形框標(biāo)注出檢索出的目標(biāo)單詞。為此，首先將單詞圖像按一定規(guī)則命名，如文件名為“3_12_6.bmp”的單詞圖像表示第三張文檔圖像的第12行中從右往左數(shù)第6個單詞。然后創(chuàng)建“.csv”文件來保存對應(yīng)單詞的位置信息，格式如“3，12，6，264，740，61，25”，前三位代表單詞圖像的文件名稱，后四位為該單詞圖像在該頁文檔中的位置坐標(biāo)信息。

2 特征提取與查詢

2.1 空間關(guān)系特征

中文和英文等大多數(shù)語言中單詞都是由輪廓大小基本一致的字或者字母排列組合而成，不同單詞中字符的輪廓大小與位置都有著相同的規(guī)律，很難作為分類特征。維吾爾語中單詞由不同數(shù)量的連體段構(gòu)成，每個連體段由一定數(shù)量的字母黏連書寫而成，構(gòu)成連體段的字母數(shù)量可以是一個或者多個。由于每個連體段的寬度、高度不同，空間位置也不按規(guī)則排列，所以與其它語言相比，維吾爾語單詞具有豐富的空間關(guān)系。本文提取的針對維吾爾語單詞的空間關(guān)系特征包括連體段的寬度、高度以及在單詞圖像中的水平方向坐標(biāo)、單詞圖像中垂直方向的頂部和底部位置的坐標(biāo)，每個連體段的空間關(guān)系特征由上述5個位置信息構(gòu)成。本文中將單詞圖像的上述特征統(tǒng)稱為空間關(guān)系特征，這種特征的優(yōu)點(diǎn)是對圖像的細(xì)節(jié)變化不敏感，因此對不同質(zhì)量的圖像有很強(qiáng)的魯棒性，但是對于單詞圖像的空間尺度變化較為敏感。單詞圖像的空間關(guān)系特征如圖4所示。

圖4 單詞空間關(guān)系特征

如圖4所示，圖中展示了一個由4個連體段構(gòu)成的單詞的特征示意圖，我們以單詞圖像的下邊界為X軸，左邊界為Y軸建立坐標(biāo)系，根據(jù)坐標(biāo)軸中標(biāo)出的坐標(biāo)即可求出單詞圖像的所有空間關(guān)系特征。每個連體段的特征由5維向量構(gòu)成，加上單詞圖像的寬度信息，一個由4個連體段構(gòu)成的單詞將會產(chǎn)生一個21維的特征向量。單詞的特征向量的維數(shù)會隨著構(gòu)成單詞的連體段數(shù)目的變化而變化，連體段數(shù)目越多，則特征向量維數(shù)越高，特征信息越豐富。圖4中構(gòu)成單詞的每個連體段均由單個字母構(gòu)成，而維吾爾語中單詞內(nèi)部的連體段一般都由多個字母通過不同的順序與連接方式書寫而成，這種特點(diǎn)使連體段的寬度、高度、空間位置等信息變化多樣。構(gòu)成單詞的各連體段以不同的順序排列組合后進(jìn)一步豐富了單詞的空間關(guān)系特征，使我們能夠用這種空間關(guān)系特征來表征對應(yīng)單詞。

對于連體段數(shù)目較少的單詞，比如由一個連體段構(gòu)成的單詞，這類單詞只能提取6維的空間關(guān)系特征，由于特征維數(shù)較少，很難用空間關(guān)系特征直接表征這類單詞。由一個連體段構(gòu)成的單詞，連體段中字母的數(shù)量通常較多，連體段的寬度也較寬。因此對這類單詞的連體段按照一定規(guī)則進(jìn)行拆分處理，使其拆分后由若干個不完整的連體段構(gòu)成，這樣按照上述規(guī)則提取其空間關(guān)系特征，將會成倍增加單詞的特征維數(shù)，使提取的特征更易于表征單詞。

2.2 特征提取

采用投影法來獲取連體段的對應(yīng)坐標(biāo)，通過坐標(biāo)求得該連體段的空間關(guān)系特征。設(shè)圖4中單詞圖像的第一個連體段的5維特征分別為A、B、C、D、E，首先對單詞圖像進(jìn)行垂直投影，得到水平坐標(biāo)A1、B1。然后根據(jù)此坐標(biāo)，將第一個連體段圖像在垂直方向切分出來，對切分后的圖像進(jìn)行水平投影，得到垂直坐標(biāo)C2、D1，該連體段的5維空間關(guān)系特征計算公式如下

(2)

同理可求得其它連體段的空間關(guān)系特征，將所有連體段的特征依次排列即可生成完整單詞圖像的特征向量。

對于只有一個連體段構(gòu)成的單詞，由于連體段數(shù)目太少，在使用上述方法提取特征之前，對單詞圖像進(jìn)行基線置白處理，僅保留單詞圖像中垂直方向比較突出的部分，將其看作一個連體段并按照上述規(guī)則提取特征，來擴(kuò)充單詞圖像的特征信息，單連體段單詞基線置白如圖5所示。

圖5 單連體段單詞基線置白

從圖5中可以看出，單連體段單詞如果直接進(jìn)行特征提取，則只能提取5維空間關(guān)系特征，經(jīng)過基線置白后的單詞圖像可以看作由6個連體段組成的單詞，能夠提取30維的空間關(guān)系特征，特征數(shù)據(jù)量擴(kuò)充了6倍。

2.3 特征文件

生成的特征文件中每個單詞圖像的特征向量由包含單詞不同方面信息的4部分構(gòu)成，第一部分為單詞的寬度信息，因為維吾爾語單詞的寬度變化范圍較大，根據(jù)寬度信息可以非常快速地篩選出與其寬度相似的單詞，大大減小查找范圍。第二部分為單詞的空間關(guān)系特征，由5個小部分構(gòu)成，每個部分包含了單詞中不同連體段的同一特征，用于單詞的精確匹配。第三部分為單詞圖像的頁碼信息，頁碼格式如“23,12,6”表示單詞屬于第23頁第12行從右往左的第6個單詞。由于在單詞切分后的單詞圖像的文件名的命名規(guī)則與此相同，因此可以直接從輸入單詞圖像的文件名中獲得單詞的頁碼信息。第四部分為單詞圖像的位置信息，即在對應(yīng)文檔圖像中最小外接矩形框的坐標(biāo)，用于返回給用戶檢索結(jié)果時標(biāo)注單詞，單詞圖像的位置信息需要在單詞切分后生成的單詞位置信息文件中讀取。

為提高查詢速度，預(yù)先將所有單詞圖像的特征信息生成特征文件。單詞圖像的連體段數(shù)目不同，則單詞的特征向量的維數(shù)也會有很大差異，為便于查詢，建立多個“.csv”文件來存儲不同連體段數(shù)目的單詞圖像的特征，如文件名為“LTD3.csv”的文件中存儲所有連體段數(shù)目為3的單詞圖像的特征。建立8個“.csv”來分別存儲單詞圖像的特征，表示最多能存儲到連體段數(shù)目為8的單詞圖像的特征,8個文件中每一行的數(shù)據(jù)維數(shù)分別為13、18、23、28、33、38、43、48，其中“LDT1.csv”中存儲經(jīng)過基線置白后仍舊只有一個連體段的單詞圖像的特征向量。

2.4 關(guān)鍵詞查詢

在開始查詢前將已生成的6個單詞特征文件分別讀取到計算機(jī)內(nèi)存當(dāng)中。查詢時首先將輸入的待查詢關(guān)鍵詞圖像進(jìn)行水平方向和垂直方向的等比例縮放，縮放后的單詞圖像與單詞圖像庫中的單詞圖像高度相同。然后對單詞圖像進(jìn)行預(yù)處理，并進(jìn)行水平投影，得到單詞圖像的連體段數(shù)目。若單詞圖像的連體段數(shù)目為1，則對該單詞圖像進(jìn)行基線置白處理后再提取其空間關(guān)系特征，若連體段數(shù)目大于1，則直接進(jìn)行特征提取。提取單詞圖像的空間關(guān)系特征后，根據(jù)預(yù)處理后單詞中包含的連體段數(shù)目，在相應(yīng)的特征文件中尋找與其特征相似的單詞圖像。尋找過程分為兩步，第一步尋找與其寬度相似的單詞，根據(jù)經(jīng)驗略去那些與其寬度之差大于10的單詞圖像。第二步為對寬度與其相似的單詞圖像，逐一比對二者的空間關(guān)系特征，若二者空間關(guān)系特征對應(yīng)位置的數(shù)據(jù)差值大于3，則停止與該單詞比對，繼續(xù)尋找下一單詞，反之則繼續(xù)下一位比對。最后返回與其單詞圖像寬度只差不大于10，且相對應(yīng)的每一位空間關(guān)系特征的差值都不大于3的單詞圖像的頁碼信息。

3 實驗結(jié)果與分析

本文實驗所用電腦配置為64位win7系統(tǒng)，處理器為Intel core i3 4150，4 GB內(nèi)存。檢索性能的評價指標(biāo)有準(zhǔn)確率(precision)、召回率(recall)、F值和檢索耗時，上述指標(biāo)的計算公式如下

(3)

文檔圖像庫的來源為新疆大學(xué)出版社出版發(fā)行的書籍《馬列主義經(jīng)典著作選編》的維吾爾語版本，為模擬不同的辦公環(huán)境，用不同型號的打印機(jī)將紙質(zhì)書籍掃描為文檔圖像,尺寸為716*1011，100 dpi。從掃描后的文檔圖像庫中隨機(jī)抽取了115張文檔圖像進(jìn)行關(guān)鍵詞檢索實驗，經(jīng)過單詞切分后生成24 460張單詞圖像，單詞圖像庫中不同連體段數(shù)目的單詞統(tǒng)計結(jié)果如圖6所示。

圖6 不同連體段數(shù)目的單詞統(tǒng)計結(jié)果

從圖6可知，維吾爾語常用單詞的連體段數(shù)目集中在1至6之間，其中連體段數(shù)目為2、3、4的單詞圖像最多。單詞的連體段數(shù)目不同時，單詞圖像的特征維數(shù)也會不同，為了驗證單詞圖像的連體段數(shù)目對檢索結(jié)果的影響，在單詞庫中分別找出連體段數(shù)目為1至6且出現(xiàn)次數(shù)較多的單詞圖像各3張作為輸入關(guān)鍵詞進(jìn)行實驗，分別統(tǒng)計每張單詞的查詢結(jié)果的準(zhǔn)確率，查詢結(jié)果見表1。

表1 不同連體段數(shù)目的單詞檢索結(jié)果

從表1中可知，連體段數(shù)目為1和2時，輸入的3張關(guān)鍵詞圖像的查詢準(zhǔn)確率相對較低，分別為91.2%和85.6%。當(dāng)連體段數(shù)目介于3到6之間時，輸入關(guān)鍵詞的的查詢準(zhǔn)確率都在95.5%以上，尤其是當(dāng)連體段數(shù)目分別為4、5、6的9張輸入單詞的查詢結(jié)果中總共只有兩張分類錯誤，原因是隨著單詞的連體段的數(shù)目的增加，單詞圖像的特征維數(shù)也在增加，所以查詢結(jié)果的準(zhǔn)確率較高。對于連體段數(shù)目為1和2的單詞，雖然對其連體段進(jìn)行了拆分處理使其特征維數(shù)在20維以上，但由于拆分過程存在誤差，所以關(guān)鍵詞查詢結(jié)果的準(zhǔn)確率相對較低。其中連體段數(shù)目為1的輸入關(guān)鍵詞查詢結(jié)果的平均準(zhǔn)確率反而高于連體段數(shù)目為2的關(guān)鍵詞，原因是一般由一個連體段構(gòu)成的單詞的連體段都比較寬，包含的字母較多。而某些連體段數(shù)目為2的單詞，其內(nèi)部連體段可能較窄，經(jīng)過拆分處理后的連體段總數(shù)反而少于原本連體段數(shù)目為1的單詞拆分后的數(shù)目。從表2還可以看出18張輸入關(guān)鍵詞圖像的平均查詢時間為0.23 s，查詢速度較快。

為了綜合評價提出的針對維吾爾文檔圖像的關(guān)鍵詞檢索系統(tǒng)的性能，在切分好的單詞圖像庫中隨機(jī)選取了10張在出現(xiàn)頻率較高且有豐富詞意的單詞，如“國家”、“世界”、“生活”等，并人工統(tǒng)計了每個關(guān)鍵詞在115張文檔圖像庫中的出現(xiàn)的次數(shù)。10張關(guān)鍵詞的檢索結(jié)果見表2。

表2 本文方法對10張關(guān)鍵詞圖像檢索結(jié)果

由表2可知在選取的10張關(guān)鍵詞檢索實驗中，除第二張關(guān)鍵詞準(zhǔn)確率相對較低為73.3%，其它單詞的準(zhǔn)確率都在97%以上。在召回率方面，第五張關(guān)鍵詞的召回率最低為87.5%，其余關(guān)鍵詞召回率都保持在90%以上。分析第二張關(guān)鍵詞圖像查詢結(jié)果準(zhǔn)確率較低的原因時發(fā)現(xiàn)，第二張單詞由3個連體段構(gòu)成，召回錯誤的單詞與輸入單詞極為相似，有兩個連體段完全相同，只有一個連體段的輔助標(biāo)點(diǎn)不同，說明本文方法對于外部輪廓及空間位置都相似而內(nèi)部有細(xì)微變化的連體段區(qū)分能力較差。10張單詞圖像查詢結(jié)果的平均準(zhǔn)確率達(dá)到了96.47%，平均召回率達(dá)到了93.74%，綜合性能為95%，平均檢索耗時0.25 s，驗證了本方法在維吾爾文檔圖像檢索中的有效性。為進(jìn)一步驗證該方法的性能，用相同的數(shù)據(jù)庫與測試單詞圖像分別在已有的上采樣+BHPF+MB-LBP+OSVM[4]的檢索方法與模板匹配+HOG+SVM[5]的檢索方法中做了對比實驗，3種方法的準(zhǔn)確率和召回率的對比分別如圖7、圖8所示。

圖7 3種方法對10張關(guān)鍵詞圖像檢索結(jié)果的準(zhǔn)確率對比

圖8 3種方法對10張關(guān)鍵詞圖像檢索結(jié)果的召回率對比

由圖7、圖8可知，基于上采樣+BHPF+MB-LBP+OSVM的檢索方法的平均檢索準(zhǔn)確率為86.7%，平均召回率為78.3%。基于模板匹配+HOG+SVM的檢索方法的平均準(zhǔn)確率為91.14%，平均召回率為79.31%。兩種基于經(jīng)典特征與SVM的方法都存在準(zhǔn)確率和召回率波動較大的問題。基于空間關(guān)系特征的檢索方法與以上兩種方法相比，檢索結(jié)果的準(zhǔn)確率和召回率都有很大的提高，且針對不同的單詞，檢索性能基本保持穩(wěn)定，波動較小。在檢索耗時方面，以上兩種檢索方法的平均檢索時長都大于10 s，而基于空間關(guān)系特征的檢索方法平均檢索時長僅為0.25 s，在時間性能方面有較大優(yōu)勢。

4 結(jié)束語

針對維吾爾文檔圖像的檢索問題，提出一種基于單詞內(nèi)連體段的空間位置關(guān)系的檢索方法，特征提取簡單，系統(tǒng)復(fù)雜性低，并且保持較高的檢索準(zhǔn)確率與召回率以及較短的檢索耗時。該方法無需知道單詞圖像中筆畫的全部細(xì)節(jié)，只需知道每個連體段的空間位置與大小，因此對帶有不同噪聲的文檔圖像適應(yīng)性較強(qiáng)，召回率較高。同時提出了特征分類存儲檢索框架，根據(jù)單詞連體段的數(shù)目尋找特定的特征文件進(jìn)行查詢，進(jìn)一步降低了查詢時間，給用戶較好的檢索體驗。但該方法也有多處不足之處，針對連體段數(shù)目為1和2時特征較少而進(jìn)行的連體段拆分處理方法仍然需要改進(jìn)，檢索系統(tǒng)對單詞中被連體段包裹在內(nèi)部的附加標(biāo)點(diǎn)符號變化不敏感。因此下一步的工作中將尋找新的特征與本文特征進(jìn)行融合來克服檢索系統(tǒng)的這方面的缺點(diǎn)。同時，單詞切分方法也有待改進(jìn)，實驗中測試關(guān)鍵詞的數(shù)目以及文檔數(shù)據(jù)庫的規(guī)模都需要進(jìn)一步擴(kuò)展來驗證方法的有效性，降低偶然因素對檢索結(jié)果的影響。