基于LapSVM的物流編號圖像自動識別算法

曹炯清

（貴州電子信息職業(yè)技術(shù)學(xué)院 計算機科學(xué)系，貴州 凱里 556000）

1 引言

隨著物流需求的快速增長，物流企業(yè)的信息管理技術(shù)也需要不斷的提高。信息化管理需要記錄貨物各個時期的信息，還要對貨物進行跟蹤。傳統(tǒng)的物流信息管理是以手工錄入為主，速度慢、效率低，不利于物流管理。如何快速實現(xiàn)自動識別和信息獲取是目前物流企業(yè)所關(guān)注的重點之一。

目前，條形碼識別和射頻識別相繼出現(xiàn)，成為提高物流管理效率的主要方法。條形碼技術(shù)是通過快遞員對貨物標(biāo)簽上的條形碼進行掃描，以獲取相應(yīng)的貨物信息，這是目前最主要的物流編號識別方法[1]。該方式成本低，方便易行，但是也存在著諸多缺陷，如條形碼的信息容量小，信息單一，需要人工干預(yù)，識別的距離短等。而射頻識別技術(shù)利用一個相當(dāng)于內(nèi)存卡和發(fā)射器的芯片，該芯片記錄了產(chǎn)品的信息，能夠通過非接觸進行識別[2]。該方法具有快速掃描、數(shù)據(jù)記憶容量大和安全等特點，但是投入成本高。

在物流運輸過程中，許多物流企業(yè)主要通過識別貨物的物流編號來實現(xiàn)對貨物的提取、分析和配送工作[3]，同時該編號還能記錄貨物的運輸狀態(tài)，便于企業(yè)和客戶對貨物進行跟蹤和查詢，所以有越來越多的物流企業(yè)開始重視物流編號在物流管理和運作中的作用。若能夠自動識別物流編號，同樣可以高效地獲取到貨物的運輸信息。

2 基于圖像處理的物流編號識別過程

基于圖像處理的物流編號識別算法首先需要進行圖像采集，以獲取物流訂單的編號。當(dāng)傳感器檢測到有貨物進入拍攝區(qū)域時，則給采集設(shè)備發(fā)信號，設(shè)備接受到信號后，對貨物進行拍照，獲取到物流編號圖像，如圖1所示。接著以采集得到的圖像為基礎(chǔ)，對其進行圖像預(yù)處理，如圖像去噪和二值化，之后對處理過的圖像上的數(shù)字字符進行分割，將連續(xù)的字符圖像切分成為單個字符圖像。然后，對分割后的各個數(shù)字字符圖像進行特征提取，將提取出的特征向量作為輸入，用來訓(xùn)練SVM分類器，訓(xùn)練好分類器之后，可以使用該分類器對新輸入的數(shù)字字符進行分類識別，得到物流編號信息。整個過程可以自動進行，減少人工的干預(yù)。

圖1 物流編號示意圖

該算法過程主要包括圖像采集，圖像預(yù)處理，數(shù)字字符分割，字符特征提取，分類器訓(xùn)練與識別，其流程圖如圖2所示。

2.1 物流編號圖像預(yù)處理

在圖像的采集和傳輸過程中，由于受到采集設(shè)備的影響或者環(huán)境的變化，圖像會出現(xiàn)噪聲干擾的情況，圖像預(yù)處理階段能夠有效地消除噪聲的影響，恢復(fù)出有效的信息，增強信息識別的可靠性。預(yù)處理過程包括圖像去噪和圖像二值化。

圖2 基于圖像處理的物流編號識別算法流程圖

圖像去噪就是要將圖像包含的各種噪聲濾除掉，中值濾波是一種常用的非線性濾波方法，該方法用某像素的相鄰像素區(qū)域的灰度中值替代該像素的灰度值，主要作用就是將一些與周圍領(lǐng)域像素值相差較大的像素灰度值改為與鄰域像素值接近的灰度值，從而去除一些過亮或過暗的像素。中值濾波簡單易行，能夠有效保留圖像的邊緣信息，同時起到去除噪聲的作用，該算法的步驟如下：

（1）使用一個3×3的模板，沿著行或列的方向移動；（2）每次移動后，對模板內(nèi)的像素區(qū)域進行排序；（3）用排序后得到的中值作為模板中心像素的灰度值。

為了使后續(xù)的數(shù)字字符分割和單個字符識別有效進行，在對圖像進行去噪之后需要進行二值化處理。圖像二值化的實質(zhì)就是閾值分割，首先要選定一個合適的閾值，將圖像中的每一個像素點與設(shè)定的閾值進行對比，如果小于該閾值，則用0（黑色）來代替原始的像素灰度值；反之，如果大于該閾值，則用255（白色）進行替代。該方法的公式表述如下：

其中，T為預(yù)先設(shè)定的閾值，f（x,y）為去噪后的物流編號圖像，g（x,y）為二值化后的物流編號圖像。二值化后的圖像只有黑白兩種顏色，能夠有效地區(qū)分出背景和圖像的目標(biāo)，本文中使用白色背景，黑色數(shù)字。

2.2 數(shù)字字符分割

數(shù)字字符分割就是將如圖1中的整個字符圖像中的每一個字符分割出來，形成單一的數(shù)字圖像，如果字符分割得不夠準(zhǔn)確，對后續(xù)的特征提取和識別會有很大的影響?？爝f單上的物流編號中的數(shù)字大小一致，在一定程度上降低了分割的難度。

字符分割的算法有很多種，最常用的辦法就是通過連通域進行分割。通常情況下，每一個數(shù)字都能夠構(gòu)成一個連通域，只要能夠找到這個連通域的行與列的起點和終點位置，就可以確定數(shù)字的最小矩形，從而實現(xiàn)數(shù)字字符的分割。

由于圖像采集時照相距離的不同導(dǎo)致拍攝到的數(shù)字圖片大小不同，因此對分割后的圖像進行大小歸一化，使這些數(shù)字圖像成為大小一致的尺寸，利于特征提取時的標(biāo)準(zhǔn)一致。在進行大小歸一化的過程中，不能改變數(shù)字的拓撲結(jié)構(gòu)，最大程度的減小數(shù)字字符的失真，確保識別的正確率。

令v(x,y)為原始圖像，v′(x′,y′)為歸一化后的圖像，兩者坐標(biāo)的映射關(guān)系為；

其中，width、width'分別為歸一化前后的圖像寬度，height、height′分別為歸一化前后的圖像高度，同時，歸一化后(x′,y′)處的灰度值v′(x′,y′)與v(x,y)相等?？梢钥闯?，歸一化后的點可能為原圖像的浮點數(shù)處，需要通過插值算法計算其像素值，此處通過雙線性插值法將圖像歸一化為同一尺寸。

2.3 編號特征提取

所謂的識別過程，重要就是依據(jù)特征進行判斷，故在此之前，需要對數(shù)字符號特征進行提取，得到特征向量，然后在特征空間中采取相應(yīng)的算法對待識別目標(biāo)的特征進行判別，實現(xiàn)識別的目的。良好的特征應(yīng)該具備以下幾點要求：

（1）可區(qū)分性：同類目標(biāo)的特征向量相似，不同類別的特征向量差異顯著；（2）可靠性：所用的特征易于提取，并且具有一定的抗干擾能力和魯棒性；（3）獨立性：各個特征之間彼此不相關(guān)，具有獨立性；（4）數(shù)量少：特征向量的維度往往對分類器的計算復(fù)雜度有很大的影響，所以需要提取能夠保證分類最少的特征數(shù)。

本文使用的是粗網(wǎng)格特征，該特征屬于局部特征，又稱為局部灰度特征。首先將數(shù)字字符圖像劃分為n×n個網(wǎng)格（如8×8），統(tǒng)計每個網(wǎng)格內(nèi)目標(biāo)像素（黑色像素）的數(shù)量，得到一個n2維的組網(wǎng)格特征向量，該特征向量表示目標(biāo)像素在網(wǎng)格中的多少，能夠很好的反映出數(shù)字的整體結(jié)構(gòu)分布情況，提取出的特征用于后面的識別分類過程。

3 基于LapSVM的物流編號識別算法

3.1 SVM原理簡介

支持向量機（Support Vector Machines，SVM）是于1995 年由Vapnik 等人提出的一種機器學(xué)習(xí)方法，該方法是由統(tǒng)計學(xué)習(xí)方法發(fā)展而來，目的是在訓(xùn)練樣本集中找到一個最優(yōu)超平面，能夠?qū)深悩颖菊_地分開并且使得分類間隔最大。SVM能夠解決非線性、小樣本和高維數(shù)據(jù)等問題，并能夠推廣到函數(shù)擬合等機器學(xué)習(xí)的問題當(dāng)中，近年來得到廣泛的關(guān)注與應(yīng)用，如車牌字符識別[4-5]。

（1）線性可分的情況。如果兩類樣本可以通過一個線性函數(shù)完全分開，則將這些樣本稱為線性可分的，反之，不能夠由一個線性函數(shù)分開的樣本成為線性不可分的。圖3給出線性可分與線性不可分的簡單實例。

假設(shè)有一個線性可分的樣本數(shù)據(jù)集{ }( )xi,yi，i=1,…,n，樣本向量x∈Rd，類標(biāo)簽y∈{ }+1,-1 ，通常+1 為正例，-1 為反例。對樣本進行分類就是要確定能使得分類間隔最大化的超平面，設(shè)其方程為：

由點到面的距離公式可以得到樣本x與超平面間的距離，對f（x）進行歸一化使得兩類樣本中距離超平面最近的樣本滿足|f（x）|=1，此時最近樣本到分類邊界的距離為：

圖3 線性可分與線性不可分

分類間隔就等于2 ‖w‖，則使得間隔最大與使‖w‖（或‖w‖2）最小等價，對于所有樣本分類正確時還需要滿足一定的約束條件，則有：

所求的分類面就是最優(yōu)超平面，那些使式（6）等號成立的樣本成為支持向量。圖4給出最優(yōu)分類面的示意圖。

圖4 最優(yōu)分類面的示意圖

根據(jù)拉格朗日乘數(shù)法可以得到以下的函數(shù)

其中，αi＞0 為拉格朗日系數(shù)。函數(shù)L(w,b,α)分別對w和b求偏導(dǎo)數(shù)，令其為零，可以得到下面的形式：

則可以得到最終的優(yōu)化問題：

通過求解（9）可以得到最優(yōu)解α*，再根據(jù)α*求得w*和b*，并可以得到最優(yōu)分類判別函數(shù)

將測試樣本x代入判別函數(shù)中就可以得到分類的結(jié)果。

（2）線性不可分的情況。在樣本集為線性不可分時，引入松弛變量ξi≥0，允許某些樣本點的函數(shù)間隔小于1，即在最大分隔區(qū)域內(nèi)，此時得到新的目標(biāo)函數(shù)以及相應(yīng)的約束條件

其中，C為懲罰參數(shù)，相應(yīng)的最終優(yōu)化問題為

同樣在求得α*、w*和b*后可以得到與式（10）形式相同的判別函數(shù)。

（3）核函數(shù)。核函數(shù)的引入能夠解決低維空間的線性不可分問題，且在變換到高維空間后，并不需要知道變換的具體形式，因為判別函數(shù)中只包括內(nèi)積運算，所以只需要定義變換后的內(nèi)積運算。統(tǒng)計學(xué)習(xí)理論中指出，只要核函數(shù)K(x,y)滿足Mercer 條件就可以作為某變換空間中的內(nèi)積進行使用，也就是最優(yōu)判別函數(shù)表示為：

常用的核函數(shù)有以下幾種：

（1）線性核函數(shù)：

（2）多項式核函數(shù)：

（3）高斯核函數(shù)：

（4）Sigmoid核函數(shù)：

支持向量機先通過非線性變換將輸入數(shù)據(jù)集投影到高維空間中，再在這個高維空間內(nèi)對最優(yōu)線性分類面進行求解，此過程中不需要知道非線性變換的具體形式，只需知道核函數(shù)即可。

3.2 基于LapSVM的多分類算法

SVM 模型能夠獲得較高的識別，但是需要較多的訓(xùn)練樣本。半監(jiān)督學(xué)習(xí)是最近機器學(xué)習(xí)中的一個熱點，它能同時利用標(biāo)記樣本與未標(biāo)記樣本的信息，在極少標(biāo)記樣本的情況下，獲得準(zhǔn)確的識別結(jié)果。其原理如下：首先用未標(biāo)記樣本構(gòu)造一個Laplacian正則項：

其中cij代表樣本xi,xj的相似程度。將公式（18）加入（9），得到：

這就構(gòu)成了LapSVM分類器。

SVM 的提出是用于解決二分類問題，而物流編號識別屬于多分類問題。目前，使用SVM進行多分類的方法主要有：一對一（One against one）、一對多（One against the others）和SVM決策樹法（SVM decision tree）。由于一對多算法簡單且易實現(xiàn)，所以本文選用一對多方法進行物流編號的識別。

一對多方法就是將某一類的樣本與其它剩余類別的樣本劃為兩個類別，在這兩類中構(gòu)建超平面，在這種分類算法中，需要構(gòu)建多個SVM 分類器，每一個分類器用于將某一類與其他類進行分類，將多分類問題轉(zhuǎn)換為多個二分類問題。

物流編號識別當(dāng)中的數(shù)字為0-9，共有10個類別，故需要構(gòu)造10個SVM分類器。訓(xùn)練之前，需先提取數(shù)字字符的粗網(wǎng)格特征，用于訓(xùn)練分類器。在訓(xùn)練第i 個分類器時，將屬于該類的樣本標(biāo)記為+1，不屬于該類的樣本標(biāo)記為-1。訓(xùn)練時需先選定核函數(shù)K(x,y)和懲罰參數(shù)C，將訓(xùn)練樣本代入SVM 算法中，得到相應(yīng)的判別函數(shù)f(x)。進行數(shù)字字符識別時，將提取得到的特征向量輸入到每一個分類器當(dāng)中，循環(huán)檢查每個分類器的輸出。當(dāng)某個分類器的輸出為1時，則輸入的數(shù)字字符屬于該類別；若所有輸出均為-1，則拒絕識別該數(shù)字。在識別過程中遇到多個分類器輸出為1時，則該數(shù)字屬于第一個輸出為1的分類器的類別。

在每類標(biāo)記樣本取成不同數(shù)目的情況下，測試SVM 和LapSVM 對1 000 個物流編號圖像的識別結(jié)果，得到結(jié)果見表1。

從結(jié)果可以看出：在極少標(biāo)記樣本的情況下，LapSVM 能夠取得準(zhǔn)確的識別，識別正確率遠高于SVM。

表1 物流編號圖像識別正確率(%)

4 結(jié)論

物流編號中包含了貨物的運輸信息，便于客戶和企業(yè)對貨物進行跟蹤，本文提出的基于圖像處理的物流編號識別算法，對采集到的物流編號圖像進行預(yù)處理和數(shù)字字符分割，對分割后的各個圖像提取特征，獲得特征向量，用于訓(xùn)練LapSVM分類器，使用訓(xùn)練好的分類器進行編號的分類與識別。該算法簡潔高效，能夠降低人工干預(yù)，提高自動識別效率。

[1]楊長勇.條形碼技術(shù)在物流生產(chǎn)過程中應(yīng)用探索[J].信息通信,2011,(3):68-69.

[2]謝勇,王紅衛(wèi),李再進.基于電子標(biāo)簽的物流路徑跟蹤系統(tǒng)研究[J].物流技術(shù),2005,(12):27-30.

[3]黃孝平,林雯.基于計算機視覺圖像的物流編號智能識別技術(shù)[J].網(wǎng)絡(luò)與信息化,2013,32(3):449-451.

[4]高珊,劉萬春,朱玉文.基于SVM的車牌字符分割和識別方法[J].微電子學(xué)與計算機,2005,22(6):34-36.

[5]王曉光,王曉華.一種基于SVM的車牌漢字的有效識別方法[J].計算機工程與應(yīng)用,2004,(24):208-209.