0 引言

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

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

1 本文方法

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

1.1 多尺度字符串表示

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

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

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

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

    (3)計(jì)算每一個(gè)細(xì)胞單元塊的梯度；

    (4)統(tǒng)計(jì)每一個(gè)細(xì)胞單元的塊的方向梯度直方圖,，形成HOG描述子,。

    HOG特征對幾何和光學(xué)形變具有魯棒性，但對尺度的魯棒性不強(qiáng),。因此,，本文在進(jìn)行圖像分類前，先將圖像劃分為不同尺度的圖像子塊,，然后再提取HOG特征,。通過分析同一類別圖像中目標(biāo)出現(xiàn)的位置規(guī)律，本文將圖像分為如圖2所示的33個(gè)尺度的圖像子塊,。然后將每一個(gè)圖像子塊都?xì)w一化到32×32的尺寸,，提取HOG特征向量。其中,，HOG特征提取所用的單元格和塊尺寸在實(shí)驗(yàn)部分討論,。本文將每一個(gè)圖像子塊的HOG特征向量看作一個(gè)字符串。那么,，一幅圖像可以用33個(gè)字符串表示,。后續(xù)通過對字符串進(jìn)行匹配來實(shí)現(xiàn)圖像的分類。

1.2 改進(jìn)的編輯距離計(jì)算

    傳統(tǒng)的編輯距離用于計(jì)算兩個(gè)字符串所對應(yīng)的符號的最優(yōu)排列,，具體是通過一系列的編輯操作,，將輸入的字符串X=x₁，x₂,，…,，x_N轉(zhuǎn)換為輸出字符串Y=y₁，y₂，…,，y_M,。

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

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

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

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

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

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

    編輯距離的計(jì)算可以看作是一個(gè)最優(yōu)化問題,，采用動(dòng)態(tài)規(guī)劃算法來進(jìn)行求解。具體地,，對于一個(gè)包含N個(gè)符號的字符串X=x₁,，x₂，…,，x_N和一個(gè)包含M個(gè)符號的字符串Y=y₁,，y₂，…,，y_M,，首先需要計(jì)算一個(gè)維度為N×M的動(dòng)態(tài)規(guī)劃矩陣，表示為：

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

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

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

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

    特別地，當(dāng)特征向量歸一化之后,，這一固定代價(jià)可以看作是兩個(gè)空向量之間的距離,。如果兩個(gè)特征向量之間的距離低于固定代價(jià)，則認(rèn)為兩個(gè)特征向量相似,。因?yàn)楫?dāng)兩個(gè)特征向量不匹配時(shí),，在計(jì)算距離時(shí)會受到懲罰?；谶@一思路,，可以采用編輯操作來測量兩幅圖像是否相似。

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

    融合操作在字符串上的兩個(gè)相鄰符號上進(jìn)行,，可以用于將輸入字符串中的一個(gè)符號對{x_i,，x_i+1}與輸出字符串中的符號y_j相匹配?；蛘呦喾?，將輸出字符串中的一個(gè)符號對{y_j，y_j+1}與輸入字符串中的符號x_i相匹配,。因?yàn)橄噜彽娜诤喜僮骷瓤梢宰饔糜谳斎胱址?，也可以作用于輸出字符串，因此,，符號序列{x_i,，x_i+1，…,，x_i+k}可以與符號序列{y_j,，y_j+1，…,，x_j+l}相匹配,。可見,，融合操作包含了插入和刪除操作,。從圖像的角度來看，融合操作允許一個(gè)圖像中的一組連續(xù)的圖像子塊與另一幅圖像中的一組圖像子塊相匹配,。這意味著如果一個(gè)目標(biāo)被分為許多區(qū)域,，對應(yīng)的局部特征可能組合在一起去與另一幅圖像中的一個(gè)或者多個(gè)區(qū)域的相同組合的目標(biāo)特征相匹配。

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

1.3 改進(jìn)的SVM分類

    本文通過對字符串進(jìn)行分類來實(shí)現(xiàn)圖像的分類,，采用基于編輯距離改進(jìn)的SVM分類器,。具體地，采用編輯距離修改SVM的徑向基函數(shù),，表示為：

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

    SVM分類器的基本原理和訓(xùn)練過程這里不再贅述，可參考文獻(xiàn)[9],。

2 仿真試驗(yàn)

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

2.1 數(shù)據(jù)集

    圖像分類領(lǐng)域所用的公開數(shù)據(jù)集主要有兩個(gè)：COIL-100和PVOC 2007,，簡要介紹如下：

    (1)COIL-100數(shù)據(jù)集：該數(shù)據(jù)集包含圖像數(shù)量為7 200幅,，目標(biāo)類別數(shù)為100?？梢苑譃闇y試和訓(xùn)練兩個(gè)子集,，其中，訓(xùn)練樣本子集包含800圖像,，測試樣本子集包含6 400幅圖像,。圖像的尺寸都是128×128。

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

    本文選用這兩個(gè)數(shù)據(jù)集進(jìn)行圖像分類實(shí)驗(yàn)，測試4種對比方法的性能,。其中,，4種方法所用的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集是相同的。對于兩類數(shù)據(jù)集,，分別進(jìn)行訓(xùn)練和測試,，計(jì)算性能指標(biāo)。

2.2 評價(jià)指標(biāo)

    圖像分類主要關(guān)注兩個(gè)方面：(1)分類結(jié)果是否正確,，(2)分類速度是否夠快,。這兩個(gè)方面可以采用兩個(gè)指標(biāo)來進(jìn)行定量測試：

    正確率指標(biāo)定義為：

    值得說明的是，分類耗時(shí)的測量與所用的計(jì)算機(jī)硬件平臺以及軟件環(huán)境都密切相關(guān),。為保證測量結(jié)果的可對比性,，本文在同一計(jì)算機(jī)軟硬件平臺上測試4種方法的性能指標(biāo)。具體地,，計(jì)算機(jī)的硬件平臺參數(shù)為：CPU：Intel I5四核3.2 GHz,；內(nèi)存：16G DDR3；軟件環(huán)境參數(shù)為：Windows 7 64位操作系統(tǒng),，Visual Studio 2013開發(fā)環(huán)境,，OpenCV 2.4.11視覺庫。

2.3 參數(shù)設(shè)置

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

    由圖3可見,，當(dāng)單元格尺寸為4×4、塊尺寸為2×2時(shí),，兩個(gè)數(shù)據(jù)集下圖像的分類正確率都是最高的,。因此，本文設(shè)置單元格尺寸為4×4,，塊尺寸為2×2,，直方圖方向數(shù)量為8。如1.1節(jié)所述,，多尺度圖像塊的尺寸都?xì)w一化為32×32,，因此,，在本文的HOG特征參數(shù)設(shè)置的條件下，每一個(gè)圖像子塊提取的HOG特征向量的維數(shù)為（32/8×32/8×2×2×8=512）,。

2.4 性能對比

    本文采用以上參數(shù)匹配進(jìn)行圖像分類實(shí)驗(yàn),，并與文獻(xiàn)[6]、[7],、[9]所述的圖像分類方法進(jìn)行對比，在COIL-100和PVOC 2007兩個(gè)數(shù)據(jù)集下對比測試圖像分類性能,。其中,，圖像分類正確率指標(biāo)的對比結(jié)果如圖4所示，平均分類耗時(shí)的對比結(jié)果如表1所示,。

    由圖4可見,，本文方法在COIL-100和PVOC 2007兩個(gè)數(shù)據(jù)集下的分類正確率指標(biāo)都高于其他3種方法，尤其是在PVOC 2007數(shù)據(jù)集下的分類正確率指標(biāo)優(yōu)勢更明顯,。這是因?yàn)楸疚姆椒ㄍㄟ^多尺度分塊和融合編輯操作來適應(yīng)同類目標(biāo)在不同圖像上位置,、尺寸和視角的變化，對于PVOC 2007數(shù)據(jù)集中具有不同尺度,、視角和光照變化的目標(biāo)的魯棒性更好,。

    由表1可見，本文方法的平均分類耗時(shí)是4種方法中最小的,，且遠(yuǎn)小于文獻(xiàn)[7]和[9]所述方法,。這是因?yàn)楸疚姆椒ǖ腍OG特征提取和改進(jìn)的編輯距離計(jì)算耗時(shí)遠(yuǎn)低于文獻(xiàn)[7]的多模式深度學(xué)習(xí)和文獻(xiàn)[9]的潛在語義分析過程。

3 結(jié)束語

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

參考文獻(xiàn)

[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].計(jì)算機(jī)研究與發(fā)展，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] 石祥濱,，房雪鍵，張德園,，等.基于深度學(xué)習(xí)混合模型遷移學(xué)習(xí)的圖像分類[J].系統(tǒng)仿真學(xué)報(bào),，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].計(jì)算機(jī)學(xué)報(bào),，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.河南經(jīng)貿(mào)職業(yè)學(xué)院 計(jì)算機(jī)工程學(xué)院,，河南 鄭州450018；2.黃河科技學(xué)院 信息工程學(xué)院,，河南 鄭州450019,；

3.鄭州航空工業(yè)管理學(xué)院 電子通信工程學(xué)院，河南 鄭州450018）