基于密度特征與KNN算法的最優特征維數選擇

孫國棟 梅術正 湯漢兵 周振

摘 要： 為了保證基于同步觸發雙相機的儀表復雜字符識別中誤識率為0，采用K最近鄰算法對儀表字符特征進行訓練分類，結合字符自身特點，提出最優特征提取與高寬維度選擇方法，并設計實驗獲取1～4 096維密度特征的誤識率與運行時間。實驗結果表明，圖像的密度特征總維度在230～260，高寬維度比接近1.4時，誤識率為0的概率最大。該規律對采用KNN算法進行分類識別時最優密度特征維數選擇具有一定指導意義。

關鍵詞： 復雜儀表； 特征維數； 誤識率； KNN算法； 密度特征； 最優特征

中圖分類號： TN911.73?34； TP23 文獻標識碼： A 文章編號： 1004?373X（2018）16?0080?04

Abstract： The K?Nearest Neighbor （KNN） algorithm is adopted to train and classify the character features of the instrument to guarantee the zero error recognition rate during the complex character recognition of the instrument based on the double cameras with synchronous trigger. In combination with the features of the character， a method of extracting the optimum feature and selecting the width and height dimensions is proposed. An experiment was designed to obtain the error recognition rate and running time of 1～4096 dimensions density features. The experimental results show that when the total number of dimensions of the image density feature is 230～260 and the dimension ratio of height to width is close to 1.4， the probability of zero error recognition rate reaches the maximum. This rule has a certain guiding significance to the selection of the optimal density feature dimension when the KNN algorithm is used for classification and recognition.

Keywords： complex instrument； feature dimension； error recognition rate； KNN algorithm； density feature； optimum feature

國家計量單位需定期檢測電力儀表以保證其測量精度，對標準表與被試表的讀數進行直接比較是最常用的校對方法[1]，而兩表的同步觸發尤為關鍵。特別是對不含通信接口的儀表同步相對較難，因此通過同時觸發雙相機分別識別兩表的讀數成為了一種新的解決方案。為了保證儀表上復雜字符誤識率[2]為0，有必要研究其字符特征提取與維度選擇以保證100%的識別率與最低的運行時間。目前常用的字符特征有結構特征[3]和統計特征[4]。其中，結構特征包括圈、斷點、交叉點、筆畫、輪廓等；統計特征包括點的密度測量、矩、特征區域等。結構特征能描述字符的結構，誤識率較低，但相對復雜[5]。統計特征算法簡單，魯棒性強，統計特征的分類器易于訓練，且誤識率低，但要提取能反映模式精細結構的特征[6]較難。K最近鄰（K?Nearest Neighbor，KNN）分類算法[7?8]根據樣本鄰近性找出最近的K個訓練樣本作為其K近鄰，并根據K近鄰采用投票策略預測待分類樣本類型[9]。其算法簡單，無需估計參數，無需提前訓練，適合于多分類問題。因此，本文采用KNN對儀表字符特征進行訓練分類，結合字符特點，提出了最優特征提取與維度選擇方法，并設計相關實驗驗證了其正確性。

1 識別流程與方法

識別的字符有‘0～‘9，‘C，‘D，‘m，‘V，‘*，‘H，‘K，‘Z，‘A，‘.，‘；，‘?共22類字符。其識別流程如圖1所示。首先，建立字符圖像庫，并對字符庫中圖像歸一化；然后，提取所有樣本圖像的特征，并采用KNN進行訓練；最后，對測試圖像進行分類，同時獲取測試圖像的誤識率和運行時間以對所選特征進行性能分析。

1.1 圖像特征分析

本文研究的密度特征是將圖像分為n個大小相同的圖像塊，提取子圖像塊中白色像素的個數。若標準圖像大小為64×64，則圖像特征維數最小為1，最大為4 096。當選這兩個極限特征維數時，字符誤識率難以達到0。特征維數太少，特征區分度低；而特征維數太大，子圖像塊包含的像素過少，對圖像噪聲的魯棒性低，且運算時間增大。故推測圖像的特征維數在中間特定范圍內誤識率最優，穩定地保持在0。并且圖像在高度和寬度方向上均分的個數也會導致識別準確率的變化。當圖像的高度維數和寬度維數比值與原始圖像的高寬比相似時，所選圖像特征的區別度應該變大。

如圖2所示，圖像的大小為116×58，以字符5和2為例，將圖像分為8等分，按照從左至右，從上到下對子圖像塊進行編號。圖2a）與圖2c）中，子圖像按照圖像的高寬比劃分；圖2b）與圖2d）中，圖像高度分為8等份，寬度劃分為1份。可見圖2a）和圖2c）的圖像區別很大；而圖2b）和圖2d）的特征向量基本相同，區別度很小。因此，推測字符子圖像按照圖像的高寬比及其字符結構劃分會獲得更好的效果。對圖像庫中1 100幅圖像的高和寬進行統計，得到圖3。從圖3可知高寬比在[1.3，2.1]的分布最多。故斷定圖像的高度與寬度維數比在1.3～2.1范圍內，字符識別準確率可能會較高。

1.2 建立圖像數據庫

KNN算法需要先通過圖像庫訓練KNN模型，才能對測試圖像庫進行分類，統計誤識率，故需建立訓練圖像庫和測試圖像庫。電力儀表字符圖像采集采用大恒MER?131?210U3C相機與50 mm鏡頭。在采集圖像時，相機并非嚴格垂直電力儀表的屏幕，相機的光軸相對于屏幕的中垂線通常成一定角度。為了提高識別算法的魯棒性，相機在不同角度采集儀表字符樣本圖像。采集過程如下：首先調整采集圖像的ROI區域，使ROI只包含儀表屏幕中待識別字符部分，接著找到相機光軸[10]與ROI區域的中垂線平行位置作為正中間位置。在保證相機的光軸對準ROI中心點的情況下，水平左右旋轉相機，使相機的光軸與中垂線夾角分別為±5°，±10°，總共確定5個位置，如圖4所示。每個位置對每類字符采集20張圖片，其中一半作為訓練圖像，另一半作為測試圖像，總共得到22類字符，每類字符100張圖像。圖4中1號與5號位置因夾角最大得到的圖像較“胖”；越靠近中間角度越小，圖像則稍“瘦”。各種位置拍攝的圖像對比效果如圖5所示。

1.3 圖像歸一化

圖像庫中的圖像大小不一，需對圖像大小歸一化。假設歸一化后圖像的大小為64×64個像素。設待提取特征的圖像大小為128×128。考慮到128并不能夠整除1～64，而選取1～64的最小公倍數作為歸一化大小會導致運算量劇增。所以根據圖像的維數x對圖像的高寬取整。取整的公式為：

找到圖像庫字符圖像中包含字符的最大外接矩形圖像Rect，設Rect的高為Height，寬為Width，特征高度維數為HeightDim，寬度維數為WidthDim。

將高度維數和寬度維數代入式（1）中得到yH，yW。再比較yH /Height和yW/Width的大小，以Min（yH/Height， yW/Width）為比率縮放Rect，獲得圖像Rect1。接著把Rect1圖像復制到大小為[yh×yw]空白圖像的正中間，圖像歸一化完成。

1.4 特征提取

本文選用密度特征即將分割出的單個字符分成大小相同的多個子圖像塊，統計每個子圖像塊中白色像素的個數。設第i幅圖像第j個子圖像塊的白色像素的個數為ni，j。總維數為nDim = HeightDim·HeightDim，則第i幅圖像的特征為：

2 實驗方案

為了對比在不同的特征維度以及同一特征維度下高度維數和寬度維數不同組合所得到的字符誤識率，設計了以下實驗。首先，確定KNN算法的參數k。k取太小，分類結果容易受噪聲點影響；k太大，近鄰中可能包含太多的其他類別的點，故取k為5。取高度方向的維數為1，寬度方向的維數為1，對圖像歸一化，用KNN算法訓練圖像并測試，記錄實驗的誤識率以及運行時間。然后，依次將寬度方向的維數增加1，重復試驗，直到寬度方向的維數為64。接著，再將高度維數增加1，重復上述實驗直到高度維數和寬度維數均為64。最后得到4 096組誤識率以及運行時間的實驗數據以進行統計分析，找出最優特征維度及其高寬組合。

3 實驗結果與分析

圖6表示識別率為100%時，高度與寬度方向維數的分布情況。橫坐標和縱坐標分別表示特征的高度和寬度方向的維數大小，從圖中可以看出高度或寬度維數太小時，誤識率達不到0。而高度維數或寬度維數很大時，識別率同樣達不到100%。圖7表示識別率為100%時，圖像的特征維數的分布情況。從圖中可以看出，當特征的總維數在[230，240]，[250，260]兩個區間內時，識別準確率為100%的頻次最多。圖8表示識別率為100%時，圖像的高度維數和寬度維數的比值分布情況。當圖像高度維數和寬度維數的比率在1.4附近時，識別率達到100%的頻次最多，這個最優比值在1.3～2.1之間，驗證了之前的推斷。圖像的運行時間隨圖像的特征維數增加而增加，如圖9所示。圖中的時間為識別圖像測試庫中1 100張圖像所耗時的總和。

4 結 語

針對電力儀表字符圖像的結構特點進行分析，發現特征維數太大或者太小時，圖像的誤識率均不能達到0，故推斷圖像的特征維數在中間特定范圍內時誤識率將穩定在0，并且最優特征高度維數和寬度維數將與圖像的高寬比存在聯系。實驗統計取1～4 096維密度特征時KNN識別準確率與運行時間。結果表明，選取圖像的密度特征維數在230～260，高寬比為1.4左右時，誤識率達到0的概率最大。

參考文獻

[1] 王達，楊朋威，張平，等.感應電條件下的電流互感器誤差測試方法分析[J].內蒙古電力技術，2017，35（2）：75?78.

WANG Da， YANG Pengwei， ZHANG Ping， et al. Analysis of current transformer error test method under induced electricity [J]. Inner Mongolia electric power， 2017， 35（2）： 75?78.

[2] DODIG I， SRUK V， CAFUTA D. Reducing false rate packet recognition using dual counting bloom filter [J]. Telecommunication systems， 2017（1）： 1?12.

[3] 羅輝武，唐遠炎，王翊，等.基于結構特征和灰度特征的車牌字符識別方法[J].計算機科學，2011，38（11）：267?270.

LUO Huiwu， TANG Yuanyan， WANG Yi， et al. License plate character recognition based on structural features and grayscale pixel features algorithm [J]. Computer science， 2011， 38（11）： 267?270.

[4] 孫中悅，周天薈.基于特征點統計特征的人臉識別優化算法[J].北京交通大學學報，2015，39（2）：128?134.

SUN Zhongyue， ZHOU Tianhui. A face recognition optimization algorithm based on statistical characteristics of feature points [J]. Journal of Beijing Jiaotong University， 2015， 39（2）： 128?134.

[5] 張愛娟.基于結構特征點的字符分割技術的研究[D].西安：西安電子科技大學，2014.

ZHANG Aijuan. Research on character segmentation based on structure feature points [D]. Xian： Xidian University， 2014.

[6] 張彤，肖南峰.基于BP網絡的數字識別方法[J].重慶理工大學學報（自然科學版），2010，24（3）：43?47.

ZHANG Tong， XIAO Nanfeng. Character identification based on a BP neural network [J]. Journal of Chongqing University of Technology （Natural science）， 2010， 24（3）： 43?47.

[7] 劉雨康，張正陽，陳琳琳，等.基于KNN算法的改進的一對多SVM多分類器[J].計算機工程與應用，2015，51（24）：126?131.

LIU Yukang， ZHANG Zhengyang， CHEN Linlin， et al. Improved KNN?based 1?vs?all SVM multi?class classifier [J]. Computer engineering and applications， 2015， 51（24）： 126?131.

[8] ZHANG S， LI X， ZONG M， et al. Learning k for KNN classification [J]. ACM transactions on intelligent systems & technology， 2017， 8（3）： 1?19.

[9] 華輝有，陳啟買，劉海，等.一種融合K?means和KNN的網絡入侵檢測算法[J].計算機科學，2016，43（3）：158?162.

HUA Huiyou， CHEN Qimai， LIU Hai， et al. Hybrid K?means with KNN for network intrusion detection algorithm [J]. Computer science， 2016， 43（3）： 158?162.

[10] KE Xizheng， LI Shiyan. Experimental study on optical axis alignment of the optical antenna under the spot broken [J]. Acta Photonica Sinica， 2017， 46（4）： 1?9.