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

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

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

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

中圖分類(lèi)號(hào)： TN911.73?34； TP23 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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

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

1 識(shí)別流程與方法

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

1.1 圖像特征分析

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

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

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

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

1.3 圖像歸一化

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

找到圖像庫(kù)字符圖像中包含字符的最大外接矩形圖像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 特征提取

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

2 實(shí)驗(yàn)方案

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

3 實(shí)驗(yàn)結(jié)果與分析

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1] 王達(dá)，楊朋威，張平，等.感應(yīng)電條件下的電流互感器誤差測(cè)試方法分析[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] 羅輝武，唐遠(yuǎn)炎，王翊，等.基于結(jié)構(gòu)特征和灰度特征的車(chē)牌字符識(shí)別方法[J].計(jì)算機(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] 孫中悅，周天薈.基于特征點(diǎn)統(tǒng)計(jì)特征的人臉識(shí)別優(yōu)化算法[J].北京交通大學(xué)學(xué)報(bào)，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] 張愛(ài)娟.基于結(jié)構(gòu)特征點(diǎn)的字符分割技術(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ù)字識(shí)別方法[J].重慶理工大學(xué)學(xué)報(bào)（自然科學(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] 劉雨康，張正陽(yáng)，陳琳琳，等.基于KNN算法的改進(jìn)的一對(duì)多SVM多分類(lèi)器[J].計(jì)算機(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] 華輝有，陳啟買(mǎi)，劉海，等.一種融合K?means和KNN的網(wǎng)絡(luò)入侵檢測(cè)算法[J].計(jì)算機(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.