0 引言

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

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

1 本文方法

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

1.1 多尺度字符串表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    編輯距離的計(jì)算可以看作是一個(gè)最優(yōu)化問(wèn)題，采用動(dòng)態(tài)規(guī)劃算法來(lái)進(jìn)行求解。具體地，對(duì)于一個(gè)包含N個(gè)符號(hào)的字符串X=x₁，x₂，…，x_N和一個(gè)包含M個(gè)符號(hào)的字符串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)換為另一字符串，并測(cè)量其相似度。然而，對(duì)于不同的應(yīng)用領(lǐng)域，這些編輯操作的代價(jià)的計(jì)算方式不同。對(duì)于本文所關(guān)注的圖像分類(lèi)領(lǐng)域，字符串中的各個(gè)符號(hào)是圖像整體或局部的一個(gè)特征描述，因此，本文采用特征向量之間的歐氏距離來(lái)描述兩個(gè)特征向量所對(duì)應(yīng)的符號(hào)的替換操作的代價(jià)，表示為：

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

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

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

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

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

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

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

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

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

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

2 仿真試驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

    由圖3可見(jiàn)，當(dāng)單元格尺寸為4×4、塊尺寸為2×2時(shí)，兩個(gè)數(shù)據(jù)集下圖像的分類(lèi)正確率都是最高的。因此，本文設(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 性能對(duì)比

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

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

    由表1可見(jiàn)，本文方法的平均分類(lèi)耗時(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]的潛在語(yǔ)義分析過(guò)程。

3 結(jié)束語(yǔ)

    本文提出了一種結(jié)合圖像的多尺度字符串表示以及改進(jìn)的編輯距離和SVM的圖像分類(lèi)方法，主要思想是：提取圖像多個(gè)尺度的歸一化圖像子塊的HOG特征，采用多個(gè)字符串描述圖像；針對(duì)圖像分類(lèi)需求，提出一種融合編輯操作，并對(duì)傳統(tǒng)的字符串編輯距離進(jìn)行改進(jìn)，將改進(jìn)的編輯距離作用于徑向基函數(shù)，采用改進(jìn)的SVM實(shí)現(xiàn)圖像分類(lèi)。在公開(kāi)測(cè)試數(shù)據(jù)集COIL-100和PVOC 2007上進(jìn)行圖像分類(lèi)實(shí)驗(yàn)，結(jié)果表明本文方法的分類(lèi)正確率高，而且平均分類(lèi)耗時(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模型的遙感圖像分類(lèi)[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í)的圖像分類(lèi)[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] 趙仲秋，季海峰，高雋，等.基于稀疏編碼多尺度空間潛在語(yǔ)義分析的圖像分類(lèi)[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）