基于密度特征與KNN算法的最優(yōu)特征維數(shù)選擇

孫國棟 梅術(shù)正 湯漢兵 周振

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

關(guān)鍵詞： 復(fù)雜儀表； 特征維數(shù)； 誤識率； KNN算法； 密度特征； 最優(yōu)特征

中圖分類號： TN911.73?34； TP23 文獻標(biāo)識碼： 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

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

1 識別流程與方法

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

1.1 圖像特征分析

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

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

1.2 建立圖像數(shù)據(jù)庫

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

1.3 圖像歸一化

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

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

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

1.4 特征提取

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

2 實驗方案

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

3 實驗結(jié)果與分析

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

4 結(jié) 語

針對電力儀表字符圖像的結(jié)構(gòu)特點進行分析，發(fā)現(xiàn)特征維數(shù)太大或者太小時，圖像的誤識率均不能達到0，故推斷圖像的特征維數(shù)在中間特定范圍內(nèi)時誤識率將穩(wěn)定在0，并且最優(yōu)特征高度維數(shù)和寬度維數(shù)將與圖像的高寬比存在聯(lián)系。實驗統(tǒng)計取1～4 096維密度特征時KNN識別準(zhǔn)確率與運行時間。結(jié)果表明，選取圖像的密度特征維數(shù)在230～260，高寬比為1.4左右時，誤識率達到0的概率最大。

參考文獻

[1] 王達，楊朋威，張平，等.感應(yīng)電條件下的電流互感器誤差測試方法分析[J].內(nèi)蒙古電力技術(shù)，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] 羅輝武，唐遠炎，王翊，等.基于結(jié)構(gòu)特征和灰度特征的車牌字符識別方法[J].計算機科學(xué)，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] 孫中悅，周天薈.基于特征點統(tǒng)計特征的人臉識別優(yōu)化算法[J].北京交通大學(xué)學(xué)報，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] 張愛娟.基于結(jié)構(gòu)特征點的字符分割技術(shù)的研究[D].西安：西安電子科技大學(xué)，2014.

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

[6] 張彤，肖南峰.基于BP網(wǎng)絡(luò)的數(shù)字識別方法[J].重慶理工大學(xué)學(xué)報（自然科學(xué)版），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].計算機工程與應(yīng)用，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的網(wǎng)絡(luò)入侵檢測算法[J].計算機科學(xué)，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.