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

（西藏大學，西藏 拉薩 850000）

0 引 言

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

1 基本原理

1.1 希爾伯特曲線

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

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

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

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

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

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

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

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

圖2 灰度處理后

圖3 轉(zhuǎn)文本后

3 模型構(gòu)建

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

圖4 實驗?zāi)Ｐ?/p>

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

4 評估方法

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

5 實驗結(jié)果

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

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

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

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

5.3 實驗環(huán)境

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

5.4 實驗過程

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

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

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

6 結(jié) 論

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