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

曹炯清

（貴州電子信息職業技術學院 計算機科學系，貴州 凱里 556000）

1 引言

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

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

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

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

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

圖1 物流編號示意圖

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

2.1 物流編號圖像預處理

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

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

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

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

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

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

2.2 數字字符分割

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

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

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

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

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

2.3 編號特征提取

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

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

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

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

3.1 SVM原理簡介

支持向量機（Support Vector Machines，SVM）是于1995 年由Vapnik 等人提出的一種機器學習方法，該方法是由統計學習方法發展而來，目的是在訓練樣本集中找到一個最優超平面，能夠將兩類樣本正確地分開并且使得分類間隔最大。SVM能夠解決非線性、小樣本和高維數據等問題，并能夠推廣到函數擬合等機器學習的問題當中，近年來得到廣泛的關注與應用，如車牌字符識別[4-5]。

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

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

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

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

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

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

圖4 最優分類面的示意圖

根據拉格朗日乘數法可以得到以下的函數

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

則可以得到最終的優化問題：

通過求解（9）可以得到最優解α*，再根據α*求得w*和b*，并可以得到最優分類判別函數

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

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

其中，C為懲罰參數，相應的最終優化問題為

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

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

常用的核函數有以下幾種：

（1）線性核函數：

（2）多項式核函數：

（3）高斯核函數：

（4）Sigmoid核函數：

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

3.2 基于LapSVM的多分類算法

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

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

這就構成了LapSVM分類器。

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

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

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

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

從結果可以看出：在極少標記樣本的情況下，LapSVM 能夠取得準確的識別，識別正確率遠高于SVM。

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

4 結論

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

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

[2]謝勇,王紅衛,李再進.基于電子標簽的物流路徑跟蹤系統研究[J].物流技術,2005,(12):27-30.

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

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

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