基于空間關系的維吾爾文圖像關鍵詞檢索

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

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

0 引 言

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

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

圖1 系統框架

1 維吾爾文單詞圖像切分

1.1 圖像預處理

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

1.2 單詞圖像切分

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

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

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

M=(A+B)/2+1

(1)

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

圖3 單詞切分效果

1.3 單詞位置信息

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

2 特征提取與查詢

2.1 空間關系特征

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

圖4 單詞空間關系特征

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

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

2.2 特征提取

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

(2)

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

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

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

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

2.3 特征文件

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

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

2.4 關鍵詞查詢

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

3 實驗結果與分析

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

(3)

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

圖6 不同連體段數目的單詞統計結果

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

表1 不同連體段數目的單詞檢索結果

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

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

表2 本文方法對10張關鍵詞圖像檢索結果

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

圖7 3種方法對10張關鍵詞圖像檢索結果的準確率對比

圖8 3種方法對10張關鍵詞圖像檢索結果的召回率對比

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

4 結束語

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