基于H-KNN的藏文字符的識(shí)別研究

吳玉龍，卓嘎，扎西平措，趙智龍，吳紹乾

（西藏大學(xué)，西藏 拉薩 850000）

0 引 言

隨著全國(guó)信息化的發(fā)展，OCR技術(shù)已經(jīng)越來越普及，但在我國(guó)少數(shù)民族地區(qū)所使用的語言依然信息化不成熟，而藏文作為藏族人民日常交流的主要語言，藏文OCR技術(shù)卻依然不成熟，因此，研究藏文字符識(shí)別是很有必要的，本文使用希爾伯特曲線與最鄰近算法識(shí)別藏文數(shù)字字符，以求利用更少的資源來實(shí)現(xiàn)更高的識(shí)別率，為藏文的信息化出一份力。

1 基本原理

1.1 希爾伯特曲線

希爾伯特曲線是一種空間填充曲線，它是由德國(guó)數(shù)學(xué)家David Hilbert（1862—1943）發(fā)現(xiàn)，之后的擴(kuò)展應(yīng)用有希爾伯特變換和希爾伯特黃變換，希爾伯特變換經(jīng)常被應(yīng)用于基礎(chǔ)信號(hào)的處理上，連續(xù)時(shí)間信號(hào)的希爾伯特轉(zhuǎn)換（）輸出響應(yīng)（）該信號(hào)在通過具有脈沖響應(yīng)的線性系統(tǒng)之后的（）=1/.

希爾伯特曲線被構(gòu)造成當(dāng)?shù)螖?shù)為1時(shí)，將正方形分成四個(gè)相等的小正方形，然后從左下角的小正方形開始，到右下角的小正方形結(jié)束，依次將小正方形的中心與線段連接起來。當(dāng)?shù)螖?shù)為2時(shí)，每一個(gè)小平方被分成四個(gè)相等的小平方，然后使用上述方法，操作中心被無限連接以填充整個(gè)曲線。結(jié)果表明，一維形式下的相鄰特征點(diǎn)在二維形式下仍處于相鄰位置，最大限度地減少了對(duì)原有數(shù)據(jù)結(jié)構(gòu)的破壞。再結(jié)合最鄰近算法就能實(shí)現(xiàn)KNN算法的最好效果，圖1是一階希爾伯特曲線到八階希爾伯特曲線的展示圖。

圖1 一階希爾伯特曲線到八階希爾伯特曲線

1.2 最鄰近算法（KNN）[3]

KNN（K-Nearest Neighbor）是K最近鄰居的分類法，它結(jié)合K最接近的歷史記錄來識(shí)別新紀(jì)錄。KNN是一種經(jīng)典的分類統(tǒng)計(jì)方法，在早期的研究策略中被用于文本分類。在本文中，我們提出了一種基于改進(jìn)的聚類算法的文本分類方法。KNN算法的基本思想是，在添加新數(shù)據(jù)之后，訓(xùn)練最接近新數(shù)據(jù)集的數(shù)據(jù)根據(jù)種數(shù)據(jù)所屬的類別確定與新添加數(shù)據(jù)相同的類別。

該KNN算法的核心思想是，如果特征空間中最鄰近的大多數(shù)樣本都屬于一個(gè)類別，則該樣本也屬于該類別并具有該類別中樣本的特征。此方法的分類決策僅基于最近的樣本或樣本的類別。在一些情況下，如果一個(gè)樣本在類別決策時(shí)的類別與它周圍有限的樣本中的每一個(gè)類的樣本的平均值和標(biāo)準(zhǔn)差都可以在決策時(shí)直接計(jì)算得到。在類別決策時(shí)，KNN方法只適用于極少數(shù)相鄰的樣本。因?yàn)镵NN方法依賴于有限數(shù)量的相鄰樣本而不是判別類域，所以KNN方法比其他方法更適合于類間重疊或更多重疊的待分樣本集。該算法的主要缺點(diǎn)之一是，當(dāng)樣本容量不平衡時(shí)，例如當(dāng)一個(gè)類有較大的樣本容量而其他類有較小的樣本容量時(shí)，當(dāng)輸入一個(gè)新的樣本容量時(shí)，樣本鄰域中的樣本容量可能占大多數(shù)。這種方法的另一個(gè)缺點(diǎn)是計(jì)算量大，因?yàn)閷?duì)每一個(gè)要待分類的文本來說，計(jì)算到所有已知樣本的距離是為了得到其最近的近鄰。目前，對(duì)KNN算法的改進(jìn)可分為四類：一類是用距離函數(shù)找到更接近實(shí)際的距離來代替標(biāo)準(zhǔn)的歐氏距離，如加權(quán)歐氏距離。其次，選擇比較合理的值時(shí)，通常采用奇數(shù)來嘗試，一般方法是試錯(cuò)比較，也可采用自適應(yīng)選擇的選擇方法；第三，采用更精確的概率估測(cè)方法，用多數(shù)代替少數(shù)的選擇機(jī)制。本文對(duì)現(xiàn)有的一些改進(jìn)方法進(jìn)行了總結(jié)和分析，并指出了目前研究的熱點(diǎn)和難點(diǎn)，提出了未來的研究方向。四是建立一個(gè)能提高KNN算法運(yùn)行效率的有效索引，可以通過KD樹等方法進(jìn)行加速。在對(duì)已有的幾種典型的基于樣本相似度的類別決策方法進(jìn)行比較和評(píng)估方面，已經(jīng)有很多改進(jìn)方法被提出來。還有一些改進(jìn)方法將上述許多方面結(jié)合起來。

2 數(shù)據(jù)采集及文本預(yù)處理

在數(shù)據(jù)采集的過程中，我們使用統(tǒng)一7行7列的方格紙采集藏文數(shù)字，再利用Python程序語言對(duì)采取的數(shù)據(jù)進(jìn)行統(tǒng)一的灰度化處理與轉(zhuǎn)文本處理，轉(zhuǎn)換后的文本為行列都為32的文本文件在轉(zhuǎn)化為文本時(shí)，我們使用希爾伯特曲線將32行32列的文本數(shù)據(jù)轉(zhuǎn)化為1行1 024列的數(shù)據(jù)，在此處采用希爾伯特曲線的原因是相較于傳統(tǒng)以行列為標(biāo)準(zhǔn)的變換方式，希爾伯特曲線在變換后能顯然提升KNN算法的處理速度以及處理數(shù)據(jù)的精確度。圖2是灰度化處理后的數(shù)據(jù)，在灰度化時(shí)，我們采取圖像處理軟件將圖片對(duì)比度調(diào)整為黑白。圖3是轉(zhuǎn)換完成之后的文本圖片，我們將圖片數(shù)據(jù)中白色像素點(diǎn)轉(zhuǎn)換為文本1黑色像素點(diǎn)轉(zhuǎn)化為文本0，最后得出32行32列的文本數(shù)據(jù)。本實(shí)驗(yàn)主要采集了藏文基礎(chǔ)字符三十個(gè)數(shù)據(jù)共1 292個(gè)其中訓(xùn)練數(shù)據(jù)集分配數(shù)據(jù)1 200個(gè)測(cè)試數(shù)據(jù)集分配數(shù)據(jù)92個(gè)，其中三十個(gè)字符不平均分布。

圖2 灰度處理后

圖3 轉(zhuǎn)文本后

3 模型構(gòu)建

在如圖4所示的實(shí)驗(yàn)?zāi)Ｐ椭忻枋隽吮敬螌?shí)驗(yàn)的主要步驟，而其中的核心內(nèi)容為降維方法和KNN算法，傳統(tǒng)KNN算法的步驟一般為以下四步：（1）根據(jù)已知的訓(xùn)練集重新分類。（2）在訓(xùn)練集中挑選出與測(cè)試集最相似的個(gè)類型。（3）在測(cè)試集的個(gè)鄰居中依次計(jì)算每個(gè)類的權(quán)重。（4）比較類的權(quán)重將文本分到權(quán)重最大的那個(gè)類別中。

圖4 實(shí)驗(yàn)?zāi)Ｐ?/p>

在數(shù)據(jù)分類中使用字符類型_第幾個(gè)字符的命名方式，在訓(xùn)練中分別測(cè)試值為1、3、5、7、9為值測(cè)試測(cè)試數(shù)據(jù)集的識(shí)別率，再采用交叉驗(yàn)證的方法來反復(fù)實(shí)驗(yàn)。

4 評(píng)估方法

目前一般的分類器的評(píng)估指標(biāo)有分類正確率：定義為分類的數(shù)據(jù)正確的和所有分類數(shù)據(jù)的比例，影響分類正確率的因素有數(shù)據(jù)集的數(shù)目，屬性中的信息，測(cè)試數(shù)據(jù)集的分布情況等。其他的評(píng)估指標(biāo)還有平均準(zhǔn)確率、查準(zhǔn)率、查全率，在本文中的分類模型中，由于采用了KNN算法，所以模型不具備訓(xùn)練功能，所以影響實(shí)驗(yàn)結(jié)果的主要因素還是數(shù)據(jù)集的分布和數(shù)據(jù)集的質(zhì)量。

5 實(shí)驗(yàn)結(jié)果

5.1 數(shù)據(jù)樣本

在字符識(shí)別的過程中所采用的圖片樣本均來自于手動(dòng)收集的圖片樣本，共計(jì)1 920個(gè)高清圖片，源數(shù)據(jù)的圖片像素值為160×160，壓縮處理后的圖片數(shù)據(jù)的像素值為32×32，共計(jì)1 024個(gè)像素點(diǎn)。圖片數(shù)據(jù)分為兩個(gè)部分，第一個(gè)部分有1 200個(gè)數(shù)據(jù)，第二個(gè)部分有92個(gè)數(shù)據(jù)，兩個(gè)部分內(nèi)的字符數(shù)據(jù)不平均分布，分別存放在兩個(gè)文件夾中。

5.2 數(shù)據(jù)預(yù)處理

在灰度圖片轉(zhuǎn)化為文本的過程中使用三個(gè)RGB值與127相除后相加后是否為0判斷灰度值為0還是1，當(dāng)所計(jì)算后的值為0則將所計(jì)算的像素值轉(zhuǎn)化為數(shù)值1，否則轉(zhuǎn)化為0。

5.3 實(shí)驗(yàn)環(huán)境

本次實(shí)驗(yàn)的環(huán)境在軟件為Visual Studio Code，程序環(huán)境在Python3.8中，在實(shí)驗(yàn)中使用了Python PIL庫和Numpy庫以及更多的一些處理數(shù)據(jù)的函數(shù)。

5.4 實(shí)驗(yàn)過程

首先對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理，預(yù)處理完成之后，首先使用傳統(tǒng)KNN算法對(duì)處理后的數(shù)據(jù)進(jìn)行識(shí)別，在訓(xùn)練階段，將1 200個(gè)數(shù)據(jù)按照字符順序命名排列，之后放入模型中進(jìn)行識(shí)別，得出實(shí)驗(yàn)結(jié)果如圖4，然后使用H-KNN對(duì)所處理后的數(shù)據(jù)做重新識(shí)別，然后對(duì)所得結(jié)果與傳統(tǒng)KNN所識(shí)別的結(jié)果進(jìn)行對(duì)比，在識(shí)別時(shí)對(duì)值分別取1、3、5、7、9對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，對(duì)比表如表1所示；從表1中可以看出相較于傳統(tǒng)KNN算法，H-KNN對(duì)相同情況下的數(shù)據(jù)識(shí)別率更高，這種結(jié)果直接證明了相較于傳統(tǒng)KNN算法，H-KNN對(duì)藏文字符有更好的識(shí)別率。

實(shí)驗(yàn)結(jié)果見表1。從實(shí)驗(yàn)結(jié)果看在值為3、5、7時(shí)識(shí)別正確率比較高，且在值為3、5、7時(shí)識(shí)別正確率相同，分析此次試驗(yàn)結(jié)果，相較于傳統(tǒng)CNN、BP神經(jīng)網(wǎng)絡(luò)、SVM支持向量機(jī)的識(shí)別率遠(yuǎn)遠(yuǎn)不如，究其原因，有幾個(gè)方面，一方面是數(shù)據(jù)量少，另一方面沒有在KNN算法上做重大改變，導(dǎo)致其與傳統(tǒng)的KNN算法并無太大差別；所以我們總結(jié)了以下結(jié)果，預(yù)處理的數(shù)據(jù)完成度對(duì)實(shí)驗(yàn)的結(jié)果非常大，這其中的影響因素有所處理的數(shù)據(jù)是否統(tǒng)一，字體是否相同，所處理后的數(shù)據(jù)的像素大小，圖片壓縮后的信息保留程度，和灰度圖片的處理之后的顏色校正，字體是否傾斜，由于圖片處理后的像素格特別少而其中的有效信息就更加少，所以每一個(gè)小的因素都會(huì)影響識(shí)別率，所以我們?cè)谶@里不與其他算法的識(shí)別率做比較，而是與傳統(tǒng)的KNN算法和本次實(shí)驗(yàn)所采用的H-KNN算法進(jìn)行比較，其結(jié)果顯示相較于傳統(tǒng)KNN算法H-KNN算法在識(shí)別率上有明顯的提升，以此驗(yàn)證了此種算法的可行性及有效性。

表1 傳統(tǒng)KNN與H-KNN對(duì)比

6 結(jié) 論

藏文字符的識(shí)別對(duì)于藏文的信息化有著關(guān)鍵的作用，在信息化愈發(fā)成熟的今天，研究藏文字符識(shí)別有著很大的意義，本文識(shí)別的一次實(shí)驗(yàn)性質(zhì)的實(shí)驗(yàn)，雖然未有很好地識(shí)別效果，但為藏文字符識(shí)別提出了一種新的方法，希望為藏文字符的研究添磚加瓦，貢獻(xiàn)屬于自己的一份力量。