基于H-KNN的藏文字符的識別研究

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

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

0 引 言

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

1 基本原理

1.1 希爾伯特曲線

希爾伯特曲線是一種空間填充曲線，它是由德國數學家David Hilbert（1862—1943）發現，之后的擴展應用有希爾伯特變換和希爾伯特黃變換，希爾伯特變換經常被應用于基礎信號的處理上，連續時間信號的希爾伯特轉換（）輸出響應（）該信號在通過具有脈沖響應的線性系統之后的（）=1/.

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

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

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

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

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

2 數據采集及文本預處理

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

圖2 灰度處理后

圖3 轉文本后

3 模型構建

在如圖4所示的實驗模型中描述了本次實驗的主要步驟，而其中的核心內容為降維方法和KNN算法，傳統KNN算法的步驟一般為以下四步：（1）根據已知的訓練集重新分類。（2）在訓練集中挑選出與測試集最相似的個類型。（3）在測試集的個鄰居中依次計算每個類的權重。（4）比較類的權重將文本分到權重最大的那個類別中。

圖4 實驗模型

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

4 評估方法

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

5 實驗結果

5.1 數據樣本

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

5.2 數據預處理

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

5.3 實驗環境

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

5.4 實驗過程

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

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

表1 傳統KNN與H-KNN對比

6 結 論

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