0 引言

    圖像分類是計算機視覺領域的研究熱點，在互聯網、人工智能等領域應用廣泛^[1]。目前，圖像分類方法主要分為兩類：基于圖像空間的分類方法和基于特征空間的分類方法^[2-5]。前者是指直接利用圖像的顏色和紋理等底層特征進行圖像分類，如采用灰度共現矩陣描述圖像的紋理特征、依據紋理的差異來進行圖像分類^[6]。近些年隨著深度學習研究的深入，也可以將圖像直接輸入深度學習網絡來進行圖像分類，如文獻[7]提出一種基于受限玻爾茲曼機與卷積神經網絡混合模型遷移學習的圖像分類方法，該方法使用受限玻爾茲曼機代替卷積神經網絡模型中的全連接層，在目標集上重新訓練受限玻爾茲曼機層和Softmax層，消除了數據集間內容差異對遷移學習特征識別能力的影響。深度學習方法提高了圖像分類的正確率，但此類方法的運算效率偏低。后者是先對圖像進行描述，采用不同的特征來區分圖像，然后再借助機器學習方法實現圖像分類。如文獻[8]提取圖像的局部特征描述子，采用一種類似Fisher的核特征以及擴展的詞袋模型來描述圖像并進行圖像分類。文獻[9]提出了一種基于稀疏編碼的多尺度空間潛在語義分析的圖像分類方法，主要思想是利用稀疏編碼對圖像各個局部塊特征進行軟量化，構建共生矩陣，然后結合概率潛在語義分析獲取每個局部塊的潛在語義信息并進行加權融合，最后采用支持向量機（Support Vector Machines，SVM）分類器實現圖像分類。

    本文提出一種結合圖像的多尺度字符串表示以及改進的編輯距離和SVM分類器進行圖像分類方法，采用字符串組合來描述多尺度圖像，通過字符串之間的編輯距離來測量兩幅圖像的相似度，作為圖像分類的依據。

1 本文方法

    本文方法結合圖像的多尺度字符串表示以及改進編輯距離和SVM分類方法實現圖像分類，基本流程如圖1所示。首先，對圖像進行多尺度分塊，然后提取各個歸一化圖像子塊上的方向梯度直方圖（Histogram of Oriented Gradient，HOG）特征，將生成的多尺度特征向量用多個字符串進行表示；接著計算兩幅圖像對應的兩組字符串之間的改進編輯距離，測試兩幅圖像的相似度。最后采用改進的SVM分類方法進行圖像分類，詳細過程描述如下。

1.1 多尺度字符串表示

    在圖像分類之前，首先要提取圖像特征，將圖像抽象為特征向量。圖像特征提取方法很多，如Haar^[10]、局部二元模式^[11]、HOG^[12]等。相對而言，HOG特征的區分能力強于其他兩種方法，因此本文采用HOG特征描述圖像。

    HOG特征提取的基本步驟為：

    (1)圖像預處理，包括圖像灰度化、伽馬校正等；

    (2)將圖像劃分為許多細胞單元塊；

    (3)計算每一個細胞單元塊的梯度；

    (4)統計每一個細胞單元的塊的方向梯度直方圖，形成HOG描述子。

    HOG特征對幾何和光學形變具有魯棒性，但對尺度的魯棒性不強。因此，本文在進行圖像分類前，先將圖像劃分為不同尺度的圖像子塊，然后再提取HOG特征。通過分析同一類別圖像中目標出現的位置規律，本文將圖像分為如圖2所示的33個尺度的圖像子塊。然后將每一個圖像子塊都歸一化到32×32的尺寸，提取HOG特征向量。其中，HOG特征提取所用的單元格和塊尺寸在實驗部分討論。本文將每一個圖像子塊的HOG特征向量看作一個字符串。那么，一幅圖像可以用33個字符串表示。后續通過對字符串進行匹配來實現圖像的分類。

1.2 改進的編輯距離計算

    傳統的編輯距離用于計算兩個字符串所對應的符號的最優排列，具體是通過一系列的編輯操作，將輸入的字符串X=x₁，x₂，…，x_N轉換為輸出字符串Y=y₁，y₂，…，y_M。

    常用的編輯操作有3種，分別為^[13]：

    (1)插入：將符號y_j插入到字符串X中。

    (2)刪除：從字符串X中刪除符號x_i。

    (3)替換：用符號y_j替換字符串X中符號x_i。

    這樣，對于任意兩個字符串X和Y，總存在一個有序的編輯操作集合，可以將字符串X變換到Y。

    將字符串X轉換為字符串Y可以通過多個有序的編輯操作集合來實現，每一種編輯操作集合所對應的代價可能是不同的。將字符串X轉換為字符串Y的最小編輯代價定義字符串X與字符串Y之間的編輯距離。這樣，字符串X與Y越相似，那么將字符串X轉換到字符串Y所需要采用的必要編輯操作的代價越小，也即對應的編輯距離越小。因此，編輯距離可以測量兩個字符串之間的相似度。

    編輯距離的計算可以看作是一個最優化問題，采用動態規劃算法來進行求解。具體地，對于一個包含N個符號的字符串X=x₁，x₂，…，x_N和一個包含M個符號的字符串Y=y₁，y₂，…，y_M，首先需要計算一個維度為N×M的動態規劃矩陣，表示為：

    得到該矩陣之后，矩陣的最后一項D_N-1，M-1即為將輸入的字符串X=x₁，x₂，…，x_N轉換為輸出字符串Y=y₁，y₂，…，y_M的最小代價，也即字符串X與Y之間的編輯距離。

    3個編輯操作可以將任一字符串轉換為另一字符串，并測量其相似度。然而，對于不同的應用領域，這些編輯操作的代價的計算方式不同。對于本文所關注的圖像分類領域，字符串中的各個符號是圖像整體或局部的一個特征描述，因此，本文采用特征向量之間的歐氏距離來描述兩個特征向量所對應的符號的替換操作的代價，表示為：

    這樣，兩個特征向量越相似，其歐氏距離越小，從而得到的替換操作的代價也越小。考慮到不同圖像以及圖像的不同子塊的尺度不一，為了便于比較編輯操作的代價，需要將特征向量進行歸一化，這樣，替換操作的代價可以修正為：

    插入和刪除操作可以看作是對不匹配的兩個符號之間的不相似度的建模。對于圖像特征向量所對應的符號而言，如果兩個符號需要進行插入或者刪除編輯操作，那說明這兩個符號是不相似的，因此可以定義一個懲罰因子c，該因子為常量，將其作為插入和編輯操作的固定代價，表示為：

    特別地，當特征向量歸一化之后，這一固定代價可以看作是兩個空向量之間的距離。如果兩個特征向量之間的距離低于固定代價，則認為兩個特征向量相似。因為當兩個特征向量不匹配時，在計算距離時會受到懲罰。基于這一思路，可以采用編輯操作來測量兩幅圖像是否相似。

    對于圖像而言，由于可能存在尺度或者平移等幾何變換，這樣，一幅圖像中的某個圖像子塊可能與另一幅圖像中任一圖像子塊都不相似，而是與另一幅圖像中幾個相鄰圖像子塊的并集相似。類似地，也可以是一幅圖像中的某幾個圖像子塊的并集與另一幅圖像中的一個或幾個圖像子塊的并集相似。這種情況下，采用現有的3種編輯操作難以準確測量兩幅圖像之間的相似度。為此，本文提出一種融合編輯操作，該操作可以對圖像區域的融合和分裂操作進行建模，目標是更好地匹配兩幅圖像。

    融合操作在字符串上的兩個相鄰符號上進行，可以用于將輸入字符串中的一個符號對{x_i，x_i+1}與輸出字符串中的符號y_j相匹配。或者相反，將輸出字符串中的一個符號對{y_j，y_j+1}與輸入字符串中的符號x_i相匹配。因為相鄰的融合操作既可以作用于輸入字符串，也可以作用于輸出字符串，因此，符號序列{x_i，x_i+1，…，x_i+k}可以與符號序列{y_j，y_j+1，…，x_j+l}相匹配。可見，融合操作包含了插入和刪除操作。從圖像的角度來看，融合操作允許一個圖像中的一組連續的圖像子塊與另一幅圖像中的一組圖像子塊相匹配。這意味著如果一個目標被分為許多區域，對應的局部特征可能組合在一起去與另一幅圖像中的一個或者多個區域的相同組合的目標特征相匹配。

    具體地，給定一個特征向量序列{x_i，x_i+1，…，x_i+k}，融合操作在于創建一個新的特征向量，表示為：

1.3 改進的SVM分類

    本文通過對字符串進行分類來實現圖像的分類，采用基于編輯距離改進的SVM分類器。具體地，采用編輯距離修改SVM的徑向基函數，表示為：

其中，I_X和I_Y分別表示待匹配的兩幅圖像。依據前面介紹，每一幅圖像都可以用33個字符串來表示。

    SVM分類器的基本原理和訓練過程這里不再贅述，可參考文獻[9]。

2 仿真試驗

    為了定量評價本文方法的性能，下面將本文方法與文獻[6]、[7]、[9]所述的圖像分類方法進行對比仿真試驗，在圖像分類領域公開的數據集和相同的計算機平臺上測量不同方法的性能指標，給出本文方法的定量評價結果。下面首先介紹本文方法所涉及的數據集，然后介紹本文選用的定量評價指標，接著介紹本文方法的一些參數配置，最后給出性能對比分析結果，詳細介紹如下。

2.1 數據集

    圖像分類領域所用的公開數據集主要有兩個：COIL-100和PVOC 2007，簡要介紹如下：

    (1)COIL-100數據集：該數據集包含圖像數量為7 200幅，目標類別數為100。可以分為測試和訓練兩個子集，其中，訓練樣本子集包含800圖像，測試樣本子集包含6 400幅圖像。圖像的尺寸都是128×128。

    (2)PVOC 2007數據集：該數據集包含圖像數量為9 963幅，類別數為20。目標包含不同的尺度、視角和光照變化。也可以分為測試和訓練兩個數據子集，其中，訓練樣本子集包含5 011圖像，測試樣本子集包含4 592幅圖像。圖像的尺寸都是192×192。

    本文選用這兩個數據集進行圖像分類實驗，測試4種對比方法的性能。其中，4種方法所用的訓練數據集和測試數據集是相同的。對于兩類數據集，分別進行訓練和測試，計算性能指標。

2.2 評價指標

    圖像分類主要關注兩個方面：(1)分類結果是否正確，(2)分類速度是否夠快。這兩個方面可以采用兩個指標來進行定量測試：

    正確率指標定義為：

    值得說明的是，分類耗時的測量與所用的計算機硬件平臺以及軟件環境都密切相關。為保證測量結果的可對比性，本文在同一計算機軟硬件平臺上測試4種方法的性能指標。具體地，計算機的硬件平臺參數為：CPU：Intel I5四核3.2 GHz；內存：16G DDR3；軟件環境參數為：Windows 7 64位操作系統，Visual Studio 2013開發環境，OpenCV 2.4.11視覺庫。

2.3 參數設置

    本文在提取圖像的HOG特征時，單元格和塊的尺寸不同，得到的圖像分類正確率也有差異。在試驗過程中，本文設置了8×8和4×4兩種單元格尺寸，以及4×4和2×2兩種塊尺寸，測試不同單元格和塊尺寸條件下本文方法在兩個數據集下的圖像分類正確率，如圖3所示。其中，直方圖的方向數量設為8。

    由圖3可見，當單元格尺寸為4×4、塊尺寸為2×2時，兩個數據集下圖像的分類正確率都是最高的。因此，本文設置單元格尺寸為4×4，塊尺寸為2×2，直方圖方向數量為8。如1.1節所述，多尺度圖像塊的尺寸都歸一化為32×32，因此，在本文的HOG特征參數設置的條件下，每一個圖像子塊提取的HOG特征向量的維數為（32/8×32/8×2×2×8=512）。

2.4 性能對比

    本文采用以上參數匹配進行圖像分類實驗，并與文獻[6]、[7]、[9]所述的圖像分類方法進行對比，在COIL-100和PVOC 2007兩個數據集下對比測試圖像分類性能。其中，圖像分類正確率指標的對比結果如圖4所示，平均分類耗時的對比結果如表1所示。

    由圖4可見，本文方法在COIL-100和PVOC 2007兩個數據集下的分類正確率指標都高于其他3種方法，尤其是在PVOC 2007數據集下的分類正確率指標優勢更明顯。這是因為本文方法通過多尺度分塊和融合編輯操作來適應同類目標在不同圖像上位置、尺寸和視角的變化，對于PVOC 2007數據集中具有不同尺度、視角和光照變化的目標的魯棒性更好。

    由表1可見，本文方法的平均分類耗時是4種方法中最小的，且遠小于文獻[7]和[9]所述方法。這是因為本文方法的HOG特征提取和改進的編輯距離計算耗時遠低于文獻[7]的多模式深度學習和文獻[9]的潛在語義分析過程。

3 結束語

    本文提出了一種結合圖像的多尺度字符串表示以及改進的編輯距離和SVM的圖像分類方法，主要思想是：提取圖像多個尺度的歸一化圖像子塊的HOG特征，采用多個字符串描述圖像；針對圖像分類需求，提出一種融合編輯操作，并對傳統的字符串編輯距離進行改進，將改進的編輯距離作用于徑向基函數，采用改進的SVM實現圖像分類。在公開測試數據集COIL-100和PVOC 2007上進行圖像分類實驗，結果表明本文方法的分類正確率高，而且平均分類耗時少。

參考文獻

[1] SUDHAKARAN S，JAMES A P.Sparse distributed localized gradient fused features of objects[J].Pattern Recognition，2015，48(4)：1538-1546.

[2] HUANG M，MU Z，ZENG H.Efficient image classification via sparse coding spatial pyramid matching representation of SIFT-WCS-LTP feature[J].Iet Image Processing，2016，10(1)：61-67.

[3] 呂啟，竇勇，牛新，等.基于DBN模型的遙感圖像分類[J].計算機研究與發展，2014，51(9)：1911-1918.

[4] CHEN J，LI Q，PENG Q，et al.CSIFT based locality-constrained linear coding for image classification[J].Pattern Analysis and Applications，2015，18(2)：441-450.

[5] CHAN T H，JIA K，GAO S，et al.PCANet：A simple deep learning baseline for image classification[J].IEEE Transactions on Image Processing，2014，24(12)：5017-5032.

[6] MANIVANNAN K，AGGARWAL P，DEVABHAKTUNI V，et al.Particulate matter characterization by gray level co-occurrence matrix based support vector machines[J].Journal of Hazardous Materials，2012，223-224(2)：94-103.

[7] 石祥濱，房雪鍵，張德園，等.基于深度學習混合模型遷移學習的圖像分類[J].系統仿真學報，2016，28(1)：167-173.

[8] CINBIS R G，VERBEEK J，SCHMID C.Approximate Fisher kernels of non-iid image models for image categorization[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2015，38(6)：1084-1098.

[9] 趙仲秋，季海峰，高雋，等.基于稀疏編碼多尺度空間潛在語義分析的圖像分類[J].計算機學報，2014，37(6)：1251-1260.

[10] MOHAMED B，ISSAM A，MOHAMED A，et al.ECG image classification in real time based on the Haar-like features and artificial neural networks[J].Procedia Computer Science，2015，73(5183)：32-39.

[11] NANNI L，LUMINI A，BRAHNAM S.Survey on LBP based texture descriptors for image classification[J].Expert Systems with Applications，2012，39(3)：3634-3641.

[12] BANERJI S，SINHA A，LIU C.HaarHOG：Improving the HOG descriptor for image classification[C].IEEE International Conference on Systems，Man，and Cybernetics.IEEE Computer Society，2013：4276-4281.

[13] MEDNIS M，AURICH M K.Application of string similarity ratio and edit distance in automatic metabolite recon ciliation comparing reconstructions and models[J].Biosystems & Information Technology，2012，1(1)：14-18.

作者信息：

魏艷鳴1，田建立2，郭榮幸3

(1.河南經貿職業學院 計算機工程學院，河南 鄭州450018；2.黃河科技學院 信息工程學院，河南 鄭州450019；

3.鄭州航空工業管理學院 電子通信工程學院，河南 鄭州450018）