一種基于最優(yōu)路徑搜索的圖像分類方法

陳潔萍，甘 泉，張 慧

(1.廣西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與電子信息工程技術(shù)系，廣西南寧530226; 2.平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南平頂山467002;3.清華大學(xué)軟件學(xué)院，北京100083)

一種基于最優(yōu)路徑搜索的圖像分類方法

陳潔萍1，甘 泉2，張 慧3

(1.廣西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與電子信息工程技術(shù)系，廣西南寧530226; 2.平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南平頂山467002;3.清華大學(xué)軟件學(xué)院，北京100083)

目前已經(jīng)有多種基于樹的算法來解決多類別圖像分類問題，然而由于選擇的學(xué)習(xí)和貪婪預(yù)測(cè)策略不當(dāng)，這些算法在分類精度和測(cè)試時(shí)間效率間不能實(shí)現(xiàn)很好的均衡。提出一種新的分類器，當(dāng)樹形架構(gòu)已知時(shí)能在效率和精度間實(shí)現(xiàn)很好的折中。首先，將圖像分類問題轉(zhuǎn)化為樹結(jié)構(gòu)中最優(yōu)路徑的搜索問題，提出新的類似于分支界定的算法來實(shí)現(xiàn)最優(yōu)路徑的高效搜索。其次，使用結(jié)構(gòu)化支持向量機(jī)(SSVM)在多種邊界約束下聯(lián)合訓(xùn)練分類器。仿真實(shí)驗(yàn)結(jié)果表明，相對(duì)于當(dāng)前最新“基于樹”的貪婪算法，當(dāng)應(yīng)用于Caltech-256、SUN和ImageNet1K等數(shù)據(jù)集時(shí)，該算法在效率較高時(shí)的精度分別上升了4.65%，5.43%和4.07%。

圖像分類;分支界定;最優(yōu)路徑;貪婪算法;效率;精度

1 算法簡(jiǎn)介

大規(guī)模視覺分類是計(jì)算機(jī)視覺的核心問題。隨著ImageNet［1］和SUN數(shù)據(jù)集［2］等大規(guī)模數(shù)據(jù)集的采集工作不斷推進(jìn)，研究人員正努力研究可以處理大量類別的新算法。其中，基于樹的算法［3-4］由于分類精度較高得到了廣泛關(guān)注。這些算法將大量圖像類別組織為樹形結(jié)構(gòu)。在每個(gè)內(nèi)部節(jié)點(diǎn)，分類器將類別分為低層節(jié)點(diǎn)的較小子集。圖1為圖像分類器工作過程示例(原圖為彩色圖片)。其中，圖1a給出了樹形結(jié)構(gòu)的示例，其中數(shù)字表示對(duì)象類別;圖1b給出了貪婪算法給出錯(cuò)誤預(yù)測(cè)的一個(gè)示例(帶有“x”標(biāo)記的節(jié)點(diǎn))，此時(shí)該算法在高層次上發(fā)生錯(cuò)誤。本文BB類似算法給出正確預(yù)測(cè)(帶有笑臉的節(jié)點(diǎn))，且沒有評(píng)估整個(gè)樹(綠盤中的節(jié)點(diǎn)被修剪)。紅色節(jié)點(diǎn)和邊緣表示已經(jīng)被評(píng)估過。圖1c闡述了基于樹模型的內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)標(biāo)記法。圖1d給出了分段(紅色邊緣)、路徑(從根到葉的綠線)和分支(路徑集合)的定義。

為了提高測(cè)試時(shí)間效率，從結(jié)構(gòu)最頂層到最底層運(yùn)行分類器使用貪婪預(yù)測(cè)算法來逐漸降低類別數(shù)量。因此，算法在測(cè)試期間獲得了預(yù)期中的“準(zhǔn)線性復(fù)雜度”(相對(duì)于類別數(shù)量)。

另外，這些算法采取的主要方法是學(xué)習(xí)樹形架構(gòu)及對(duì)應(yīng)的分類器集合，在分類精度和測(cè)試時(shí)間效率間只能實(shí)現(xiàn)次優(yōu)平衡效果，這主要是因?yàn)?1)采用的預(yù)測(cè)算法只利用了樹形架構(gòu)中的一條路徑;根據(jù)使用的分類器次序，貪婪選擇路徑(見圖1b左)。這表明結(jié)構(gòu)中更高層次生成的誤差無法在以后糾正;2)大多數(shù)基于樹的算法沒有聯(lián)合學(xué)習(xí)所有分類器，而是從最頂層到最底層一次學(xué)習(xí)一個(gè)分類器，使用對(duì)應(yīng)于類別子集的圖像數(shù)量也變少。因此，底層分類器訓(xùn)練時(shí)使用的數(shù)據(jù)要少于高層訓(xùn)練時(shí)。本文提出一種高效準(zhǔn)確的圖像層次分類器，當(dāng)樹形結(jié)構(gòu)已知時(shí)在精度和效率間實(shí)現(xiàn)更好的均衡。本文的主要貢獻(xiàn)如下:

圖1 圖像分類器工作過程示例(截圖)

1)將圖像分類問題建模為樹結(jié)構(gòu)中的最優(yōu)路徑搜索問題，提出一種類似于分支界定的搜索方法，在既不利用整個(gè)樹也不貪婪修剪類別的情況下實(shí)現(xiàn)最優(yōu)路徑的高效搜索(見圖1b右)。

2)使用拓展SSVM在更多的邊界約束下對(duì)邊界和模型參數(shù)展開聯(lián)合學(xué)習(xí)，使得可以在精度和效率間實(shí)現(xiàn)更好折中。

3)本文方法的最優(yōu)精度優(yōu)于一對(duì)多算法的精度;本文方法在精度和效率間的平衡效果要優(yōu)于當(dāng)前最新的基于樹的貪婪算法。更重要的是，當(dāng)使用Caltech-256、SUN和ImageNet1K數(shù)據(jù)集時(shí)，與文獻(xiàn)［4］算法相比，本文方法在效率較高時(shí)的精度分別提升了4.65%，5.43%和4.07%。

2 相關(guān)工作

圖像分類問題是計(jì)算機(jī)視覺領(lǐng)域的研究熱點(diǎn)問題之一，相繼有眾多研究者提出了一系列有代表性的方法，陳榮等［5］提出了一種新的圖像分類方法。通過基于最優(yōu)標(biāo)號(hào)和次優(yōu)標(biāo)號(hào)的主動(dòng)學(xué)習(xí)去挖掘那些對(duì)當(dāng)前分類器模型最有價(jià)值的樣本進(jìn)行人工標(biāo)注，并借助CST半監(jiān)督學(xué)習(xí)進(jìn)一步利用樣本集中大量的未標(biāo)注樣本，使得在花費(fèi)較不標(biāo)注代價(jià)的情況下，能夠獲得良好的分類性能。張淳杰等［6］綜合考慮局部特征之間的上下文信息，提出一種基于有判別力仿射局部特征上下文的圖像分類方法。對(duì)于一幅圖像上的某一位置，采用該區(qū)域的局部特征，及其周邊一定距離、角度內(nèi)的局部特征來進(jìn)行描述;然后對(duì)這些局部特征上下文進(jìn)行仿射變換，并通過最小化編碼損失的策略來進(jìn)行有判別力的仿射局部特征上下文的選擇，得到更有判別力的特征。最后通過實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的有效性。徐杰等［7］提出一種基于超邊相關(guān)性的圖像分類方法，有效地將圖像相關(guān)的標(biāo)注信息作為判定圖像類別的指標(biāo)引入到圖像分類中，進(jìn)而對(duì)圖像進(jìn)行更準(zhǔn)確的分類。在LabelMe和UIUC數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證該方法的有效性。

另外，文獻(xiàn)［8-9］提出基于一對(duì)多策略的算法和基于一對(duì)一策略的圖像分類算法，這些算法的分類精度往往較高。然而，評(píng)估分類器性能的時(shí)間復(fù)雜度與類別數(shù)量呈“線性”關(guān)系。文獻(xiàn)［10-11］通過利用類別的分層結(jié)構(gòu)來降低時(shí)間復(fù)雜度，提出了不同的方法來自動(dòng)構(gòu)建圖像類別結(jié)構(gòu)。其中，大多數(shù)方法均依賴貪婪算法來利用結(jié)構(gòu)中的一條路徑進(jìn)行類別預(yù)測(cè)并分別在結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)上訓(xùn)練分類器。因此，往往是犧牲精度來實(shí)現(xiàn)“準(zhǔn)線性”時(shí)間復(fù)雜性。鑒于此，本文將圖像分類問題轉(zhuǎn)化為樹結(jié)構(gòu)中最優(yōu)路徑的搜索問題，提出了一種新的類似于分支界定的算法來實(shí)現(xiàn)最優(yōu)路徑的高效搜索，最后通過仿真實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

3 本文模型

本文的目標(biāo)是設(shè)計(jì)一種圖像結(jié)構(gòu)分類器，更好地在精度和效率間實(shí)現(xiàn)平衡。在本節(jié)中，首先定義了“基于樹”的模型，然后給出如何將模型轉(zhuǎn)換為“最優(yōu)路徑模型”。

3.1 基于樹的模型

模型已知后，往往使用貪婪算法來預(yù)測(cè)輸入x∈RD的類別。算法從根節(jié)點(diǎn)開始探索樹的單條路徑直到葉節(jié)點(diǎn)，具體過程如下:從根節(jié)點(diǎn)開始(索引v=1)，選擇與最大分類器得分相對(duì)應(yīng)的邊緣e(即e=argmaxj(x))，然后算法推進(jìn)至子節(jié)點(diǎn)。對(duì)所訪問的所有子節(jié)點(diǎn)重復(fù)相同的選擇步驟，直到到達(dá)葉節(jié)點(diǎn)。因此，可以使用開始節(jié)點(diǎn)v=1串聯(lián)上被選邊緣 [e1，e2，…，eL]來表示預(yù)測(cè)路徑P(即P=［v;e1，e2，…，eL］)，其中L是路徑的長度。顯然，算法具有準(zhǔn)線性復(fù)雜度，因?yàn)樵谧顑?yōu)情況下，L=log K。

另外，大多數(shù)基于樹的方法不是聯(lián)合學(xué)習(xí)所有分類器，而是從最頂層到最下層緩慢地一次學(xué)習(xí)一個(gè)分類器，使用與類別子集相對(duì)應(yīng)的圖像也較少。因此，低層分類器訓(xùn)練時(shí)用到的數(shù)據(jù)集低于高層訓(xùn)練。為了解決上述兩個(gè)問題，大多數(shù)基于樹的算法［3-4］通過學(xué)習(xí)類別結(jié)構(gòu)，以便:1)避免貪婪算法出錯(cuò);2)通過約束結(jié)構(gòu)的深度來避免用較少數(shù)據(jù)訓(xùn)練分類器。本文方法的重點(diǎn)不是學(xué)習(xí)結(jié)構(gòu)，而是在結(jié)構(gòu)已知時(shí)解決這兩個(gè)問題，同時(shí)保證圖像分類預(yù)測(cè)的效率。

3.2 最優(yōu)路徑模型

式中:P1是樹中從根節(jié)點(diǎn)υ=1開始到達(dá)葉節(jié)點(diǎn)的所有路徑的集合。最優(yōu)路徑模型可以看成是一對(duì)多支持向量機(jī)的特殊情況，因?yàn)檠刂織l路徑的分類器參數(shù)的累積和可以看成是一對(duì)多支持向量機(jī)中一個(gè)類別的所有分類器參數(shù)。關(guān)鍵差別在于，樹結(jié)構(gòu)要求2條路徑的參數(shù)根據(jù)路徑的重疊情況部分共享。換句話說，本文模型利用結(jié)構(gòu)知識(shí)在類別間共享參數(shù)，以便結(jié)構(gòu)中距離更近的類別有更為相似的參數(shù)，這一屬性有助于提升相對(duì)一對(duì)多支持向量機(jī)的精度。

4 分支界定預(yù)測(cè)算法

本節(jié)提出了一種新的類似于分支界定的算法來實(shí)現(xiàn)最優(yōu)路徑的高效搜索。該算法不是搜索樹中的所有路徑，而是只搜索樹中的部分路徑，且一般情況下可以在“準(zhǔn)線性”時(shí)間內(nèi)結(jié)束。算法的偽代碼描述如下:

算法1:高效的分支界定預(yù)測(cè)

要求:輸入x∈RD，樹T，得分函數(shù)S，各節(jié)點(diǎn)的上界{Uυ}υ。

目的:見式(1)。

1)將Q初始化為空優(yōu)先級(jí)隊(duì)列;

5)for e=1:N do;

9)end for;

進(jìn)行常規(guī)健康教育，健康教育6 個(gè)月后，對(duì)病人集體進(jìn)行1次 60 min的骨質(zhì)疏松預(yù)防知識(shí)講解，同時(shí)為每例病人免費(fèi)提供1本 2 型糖尿病病人骨質(zhì)疏松預(yù)防小冊(cè)。

12)設(shè)置P*=［］。

4.1 分支界定類似搜索(BB)

對(duì)每個(gè)分支，計(jì)算分支中路徑對(duì)于輸入x能夠取得的最大得分的上限(x)。在搜索開始時(shí)，從與整個(gè)樹p1=［1;)的路徑集合相應(yīng)對(duì)的分支開始(見算法1的第2行)。然后，將工作分支不斷分割為N個(gè)子分支見算法1的第4行)，然后更新(x)的上限(算法1的第7行)。［［v;e1，…，eF)e)=［v;e1，…，eF，e)表示串聯(lián)。BB算法按照最佳優(yōu)先策略對(duì)候選分支組織搜索。因此，工作分支始終對(duì)應(yīng)于上限最大的一個(gè)(見算法1第10行)。當(dāng)已經(jīng)找到由單個(gè)路徑構(gòu)成的分支(即==1)，且分值至少與所有剩余候選分支的上界相等(見算法1第11行)。最佳優(yōu)先策略可以保證尋找到最優(yōu)路徑。算法的效率主要取決于邊界的緊湊度。在本文實(shí)驗(yàn)中，本文高效預(yù)測(cè)算法的速度要遠(yuǎn)快于最差情況下的復(fù)雜度。

4.2 邊界計(jì)算

假設(shè)每個(gè)節(jié)點(diǎn)υ緩存分支Pυ中從節(jié)點(diǎn)υ開始到達(dá)葉節(jié)點(diǎn)的路徑的上界Uυ。因此，分支［1;e1，…，eF)的上界(x)等于分段 [1;e1，…，eF]累積得分(x)及分段[1;e1，…，eF]最后一個(gè)節(jié)點(diǎn)緩存的上界Uυ之和(見算法1第7行)。

每個(gè)節(jié)點(diǎn)緩存的最緊湊上界是與輸入有關(guān)的Uυ(x)，當(dāng)已知輸入x時(shí)通過評(píng)估樹中的所有分類器可以確定最緊湊上界。然而，確定邊界的成本與最優(yōu)路徑蠻力搜索算法的成本相同。此外，對(duì)每個(gè)輸入均需計(jì)算一次。另一方面，提出利用訓(xùn)練輸入X來估計(jì)與輸入無關(guān)的上界Uυ，且模型訓(xùn)練后上界只需估計(jì)一次。請(qǐng)注意，Uυ邊界未必一定合理，因?yàn)閁υ可能小于未知測(cè)試輸入x∧的上界Uυ(x∧)。然而，筆者發(fā)現(xiàn)在實(shí)踐中估計(jì)的可靠性較高，因?yàn)榉诸惥纫话銢]有被犧牲，如圖2所示(其中，節(jié)點(diǎn)表示沒有邊界下降率約束條件下且松馳度(ρ)不同時(shí)進(jìn)行訓(xùn)練獲得的模型)。于是，將其稱為分支界定類似算法。

圖2 分支界定類似算法對(duì)Caltech-256數(shù)據(jù)集的有效性

雖然BB算法在找到了最優(yōu)路徑時(shí)才會(huì)終止，但是有更多信息存儲(chǔ)于可對(duì)評(píng)估過的分支進(jìn)行分級(jí)的隊(duì)列Q中(算法1)。分級(jí)可以保存豐富的預(yù)測(cè)結(jié)果集合，而且這一集合既包括共享類似路徑段的分支(比如貓和狗)，也包括路徑段非常不同的分支(比如工具和動(dòng)物)，這一特點(diǎn)可用于人機(jī)交互。例如，用戶更希望看到一組多樣化預(yù)測(cè)，然后選擇最合適的一個(gè)，而不是看到一組互相類似但可能所有都不適用的預(yù)測(cè)。

5 結(jié)構(gòu)化SVM學(xué)習(xí)

可以使用結(jié)構(gòu)化SVM(SSVM)來學(xué)習(xí)得分函數(shù)，并采用結(jié)構(gòu)化輸出P對(duì)樹形結(jié)構(gòu)中的路徑進(jìn)行編碼?？紤]到有一組訓(xùn)練輸入及樹的真實(shí)路徑{xm，Pm}m=1～M，求解如下SSVM問題

式中:W={Wυ}υ∈v是邊緣模型參數(shù)的向量串聯(lián)而成，Δ(P;Pm)是衡量估計(jì)路徑P誤差度的損耗函數(shù)，λ控制擾亂項(xiàng)之和(∑mξm)相對(duì)正則化項(xiàng)(WTW)的權(quán)重。在本文部署中，使用簡(jiǎn)單的0-1損失(即當(dāng)P≠Pm時(shí)Δ(P;Pm)=0，否則Δ(P;Pm)=1)。使用文獻(xiàn)［13］的雙坐標(biāo)下降求解方法來解決上述問題，以實(shí)現(xiàn)快速收斂并減少內(nèi)存使用。

通過避免學(xué)習(xí)模型參數(shù)然后估計(jì)各節(jié)點(diǎn)的上界U={Uυ}υ，可以把式(3)的SSVM問題進(jìn)行拓展，以聯(lián)合學(xué)習(xí)模型參數(shù)W和各節(jié)點(diǎn)的上界U

式中:γ是邊界Uυ的減少率;合理邊界是以v為起點(diǎn)的路徑∈Pυ的得分(xm;W)必須小于各節(jié)點(diǎn)的上界Uυ;減少率是指子節(jié)點(diǎn)的上界的γ倍應(yīng)該小于母節(jié)點(diǎn)的邊界Uυ。

與求解式(3)類似，只添加了式(1)和式(2)中的擾亂約束，并用文獻(xiàn)［14］中的雙坐標(biāo)下降求解方法求解式(4)。在圖3中，證明通過更改γ數(shù)值，可以調(diào)整精度和效率間的平衡。

6 實(shí)驗(yàn)

本文基于3個(gè)公開數(shù)據(jù)集(Caltech-256，SUN-397和ImageNet1K)來評(píng)估本文算法性能。目標(biāo)是:1)驗(yàn)證本文方法的精度高于一對(duì)多算法;2)與當(dāng)前最新基于樹的算法［4］相比，更好地實(shí)現(xiàn)精度和效率間的平衡。

圖3 針對(duì)Caltech-256數(shù)據(jù)集，在γ={1(無下降率約束)，2，3}且ρ=0.8的學(xué)習(xí)邊界條件下，相對(duì)復(fù)雜度和精度間的平衡結(jié)果

6.1 基本設(shè)置

對(duì)于精度，采用文獻(xiàn)［4］的方法，給出每個(gè)類別的精度均值。對(duì)于效率測(cè)試，因?yàn)闃淠Ｐ椭忻總€(gè)節(jié)點(diǎn)是線性分類器且復(fù)雜度相同，所以總體測(cè)試效率取決于分類器評(píng)估的次數(shù)。計(jì)算每個(gè)實(shí)例的分類器評(píng)估次數(shù)均值，并給出“相對(duì)復(fù)雜度”(即用一對(duì)多算法分類器評(píng)估次數(shù)進(jìn)行正規(guī)化后的均值)。將本文算法與當(dāng)前最新基于樹算法［4］和一對(duì)多SVM算法做比較。所有算法使用相同的SVM部署和局部限制線性編碼特征(LLC)。利用訓(xùn)練集4重交叉驗(yàn)證來選擇每種方法的參數(shù)λ(式(4))。為了訓(xùn)練樹形結(jié)構(gòu)，使用文獻(xiàn)［4］公布的代碼，并允許樹最多有8層結(jié)構(gòu)。已知樹形結(jié)構(gòu)后，使用第5節(jié)的SSVM來訓(xùn)練模型，以更好實(shí)現(xiàn)精度和效率的平衡。用MATLAB進(jìn)行SSVM訓(xùn)練時(shí)，Caltech和Sun數(shù)據(jù)集需要2 h左右，ImageNet數(shù)據(jù)集需要6 h左右。

6.2 Caltech-256

Caltech-256數(shù)據(jù)集包括256個(gè)對(duì)象類別。對(duì)每個(gè)對(duì)象類別，與文獻(xiàn)［4］類似，隨機(jī)提取40個(gè)圖像作為訓(xùn)練數(shù)據(jù)，40個(gè)圖像作為測(cè)試數(shù)據(jù)。使用帶有21K維度的LLC特征來重現(xiàn)文獻(xiàn)［4］給出的一對(duì)多精度。與松弛度ρ={0.5，0.6，0.7，0.8，0.9}相對(duì)應(yīng)的5種結(jié)構(gòu)接受訓(xùn)練以便進(jìn)行比較。

首先證明了分支界定類似算法在已知模型訓(xùn)練沒有使用邊界約束(式(3))條件下，沒有過多損失精度(見圖2)的同時(shí)實(shí)現(xiàn)效率提升。然而，如果沒有強(qiáng)迫結(jié)構(gòu)中的邊界按照一定速率下降，則實(shí)現(xiàn)的效率提升非常有限。在圖3中，證明了通過利用與γ={1，2，3}且ρ= 0.8相對(duì)應(yīng)的約束來訓(xùn)練本文模型，可以實(shí)現(xiàn)不同的精度和效率平衡效果(式(4))。下面進(jìn)一步嘗試不同的ρ (松馳度)和γ(邊界緊湊度)組合，并選擇對(duì)于驗(yàn)證集合可以實(shí)現(xiàn)最優(yōu)精度和效率平衡效果的模型(1/4的訓(xùn)練圖像用于模型選擇)。圖4給出了測(cè)試集的效率和精度性能。可以看到，本文方法以更低的復(fù)雜度實(shí)現(xiàn)了更高的精度。以9%左右的相對(duì)復(fù)雜度，實(shí)現(xiàn)了4.65%(相對(duì)值24.82%)的顯著性能提升。本文的最優(yōu)精度(35.44%)優(yōu)于一對(duì)多算法(34.78%)。另外，圖5表明了第1分級(jí)到第5分級(jí)的預(yù)測(cè)精度提升了10%，而復(fù)雜度只有準(zhǔn)線性上升。

圖4 針對(duì)Caltech-256數(shù)據(jù)集，本文方法、松弛結(jié)構(gòu)［4］和一對(duì)多SVM算法的精度和相對(duì)復(fù)雜度平衡結(jié)果

圖5 針對(duì)Caltech-256數(shù)據(jù)集使用ρ=0.9模型時(shí)，分類精度相對(duì)第1分級(jí)至第5分級(jí)預(yù)測(cè)相對(duì)復(fù)雜度的變化情況

6.3 Sun-397

基于SUN數(shù)據(jù)集來評(píng)估場(chǎng)景分類任務(wù)的性能。與文獻(xiàn)［2］的設(shè)置類似，使用397個(gè)經(jīng)過適當(dāng)采樣的類別來評(píng)估本文算法。對(duì)每一種類別，隨機(jī)采樣50個(gè)圖像作為訓(xùn)練數(shù)據(jù)，另外50個(gè)圖像作為測(cè)試數(shù)據(jù)。使用具有16K維度的LLC特征，以重建文獻(xiàn)［15］給出的一對(duì)多精度。與松弛度ρ= {0.6，0.7，0.8，0.9，1.0}相對(duì)應(yīng)的5處結(jié)構(gòu)接受訓(xùn)練以便進(jìn)行比較。本文算法的精度為25.69%，優(yōu)于一對(duì)多SVM的24.08%，且精度和效率平衡效果優(yōu)于文獻(xiàn)［4］，如圖6所示。與Caltech 256數(shù)據(jù)集類似，本文算法的復(fù)雜度更低，但精度更高。本文算法的復(fù)雜度相對(duì)只有5%，但是其精度實(shí)現(xiàn)了5.43% (相對(duì)值41.64%)的顯著提升。

圖6 針對(duì)Sun-397數(shù)據(jù)集，本文方法、松弛結(jié)構(gòu)［4］算法和一對(duì)多SVM算法的精度和相對(duì)復(fù)雜度平衡結(jié)果

6.4 ImageNet數(shù)據(jù)集

該數(shù)據(jù)集包括1K對(duì)象類別和120萬個(gè)圖像。使用與文獻(xiàn)［15］相同的訓(xùn)練和測(cè)試圖像分配方法。使用帶有10K維度的LLC特征來重建文獻(xiàn)［8］給出的一對(duì)多基準(zhǔn)精度。與松弛度ρ={0.9，0.75，0.6，0.45}相對(duì)應(yīng)的4處結(jié)構(gòu)接受訓(xùn)練以便進(jìn)行比較。已知樹形結(jié)構(gòu)后，基于SSVM訓(xùn)練本文模型(第5節(jié))。本文算法的精度為22.99%，優(yōu)于一對(duì)多SVM的21.2%，且精度和效率平衡效果優(yōu)于文獻(xiàn)［4］，如圖7所示。與Caltech 256數(shù)據(jù)集類似，本文算法的復(fù)雜度更低，但精度更高。本文算法的復(fù)雜度相對(duì)只有5%，但是其精度實(shí)現(xiàn)了4.07% (相對(duì)值109.79%)的顯著提升。此外，在邊界約束條件下學(xué)習(xí)而得的模型，其性能要優(yōu)于未在邊界約束下學(xué)習(xí)而得的模型性能。

圖7 針對(duì)ImageNet數(shù)據(jù)集，帶有邊界約束的本文方法、不帶有邊界約束的本文方法、松弛結(jié)構(gòu)［4］算法和一對(duì)多SVM算法的精度和相對(duì)復(fù)雜度平衡結(jié)果

7 結(jié)論

本文提出一種圖像結(jié)構(gòu)快速準(zhǔn)確分類算法，在精度和效率間實(shí)現(xiàn)更好的平衡。本文貢獻(xiàn)如下:1)提出一種基于樹結(jié)構(gòu)的新的高效預(yù)測(cè)BB類似算法;2)提出經(jīng)過拓展的SSVM，使得可以在精度和效率間實(shí)現(xiàn)更好的平衡。利用Caltech-256、SUN和ImageNet1K數(shù)據(jù)集進(jìn)行仿真，證明了本文方法的精度優(yōu)于一對(duì)多算法，且相對(duì)文獻(xiàn)［4］當(dāng)前最新的基于樹的算法，可以實(shí)現(xiàn)更好的精度和效率平衡。更重要的是，與文獻(xiàn)［15］算法相比，本文算法的復(fù)雜度更低，且對(duì)3種數(shù)據(jù)集分別實(shí)現(xiàn)了4.65%，5.43%，4.07%(相對(duì)值 24.82%，41.64%，109.79%)的性能提升。在下一步工作中，將研究基于本文算法多樣性輸出(比如類別預(yù)測(cè)等級(jí))的人機(jī)交互應(yīng)用問題。

［1］DENG J，DONGW，SOCHER R，et al.ImageNet:A large-scale hierarchical image database［EB/OL］.［2014-05-15］.http:// www.researchgate.net/publication/221361415_ImageNet_A_largescale_hierarchical_image_database.

［2］XIAO J，HAYSJ，EHINGER K，et al.Sun database:Large-scale scene recognition from abbey to zoo［EB/OL］.［2014-05-15］.http:// www.researchgate.net/publication/221362554_SUN_database_Largescale_scene_recognition_from_abbey_to_zoo.

［3］ BENGIO S，WESTON J，GRANGIER D.Label embedding trees for largemulti-class tasks［EB/OL］.［2014-05-15］.http:// www.researchgate.net/publication/221618910_Label_Embedding_ Trees_for_Large_Multi-Class_Tasks?ev=auth_pub.

［4］ GAO T，KOLLER D.Discriminative learning of relaxed hierarchy for large-scale visual recognition［EB/OL］.［2014-05-15］.http:// www.sciweavers.org/publications/discriminative-learning-relaxedhierarchy-large-scale-visual-recognition.

［5］陳榮，曹永鋒，孫洪.基于主動(dòng)學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的多類圖像分類［J］.自動(dòng)化學(xué)報(bào)，2011，37(8):3601-3605.

［6］張淳杰，熊威，張一帆，等.融合有判別力仿射局部特征上下文的圖像分類［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26(5):762-766.

［7］徐杰，景麗萍，于劍.基于超邊相關(guān)性的圖像分類方法［J］.模式識(shí)別與人工智能，2014，27(2):120-126.

［8］LIL.Multiclass boosting with repartitioning［EB/OL］.［2014-05-15］. http://www.researchgate.net/publication/221345684_Multiclass_boosting_ with_repartitioning.

［9］ALLWEIN E L，SCHAPIRE R E，SINGER Y.Reducing multiclass to binary:a unifying approach formargin classifiers［J］.J.Mach.Learn. Res.，2011，2(1):113-141.

［10］BEYGELZIMER A，LANGFORD J，LIFSHITS Y，et al.Conditional probability tree estimation analysis and algorithms［EB/OL］.［2014-05-15］.http://www.researchgate.net/publication/24166858_Conditional_Probability_Tree_Estimation_Analysis_and_Algorithms.

［11］BEYGELZIMER A，LANGFORD J，RAVIKUMAR P.Error-correcting tournaments［EB/OL］.［2014-05-15］.http://www.researchgate.net/ publication/24013513_Error-Correcting_Tournaments.

［12］LAND A H，DOIG A G.An automaticmethod for solving discrete programming problems［M］.［S.l.］:Springer Berlin Heidelberg，2010: 105-132.

［13］ YANG Y，RAMANAN D.Articulated pose estimation with flexible mixtures of parts［EB/OL］.［2014-05 -15］.http:// www.ics.uci.edu/～dramanan/software/pose/.

［14］ DENG J，BERG A，LI K，et al.What does classifying more than 10，000 image categories tell us?［EB/OL］.［2014-05-15］.http://www.docin.com/p-388937151.html.

［15］KRIZHEVSKY A，SUTSKEVER I，HINTON G E.Imagenet classification with deep convolutional neural networks［EB/OL］.［2014-05-15］.http://papers.nips.cc/paper/4824-imagenet-classificationwith-deep-convolutional-neural-networks.

Image Classification Algorithm Based on Optimal Path Search

CHEN Jieping1，GAN Quan2，ZHANG Hui3
(1.Department of Computer and Electronic Information Engineering，Guangxi Vocational and Technical College，Nanning 530226，China; 2.College of Computer Science and Technology，Pingdingshan University，Henan Pingdingshan 467002，China; 3.School of Software，Tsinghua University，Beijing 100083，China)

Many algorithms based on tree are proposed to solve the image classification problem for a large number of categories.Due to learning and greedy prediction strategy choice ofundeserved，methods based on tree-based representations cannotachieve good trade-off between accuracy and test time efficiency.In this paper，a classifier is proposed which achievesa better trade-offbetween efficiency and accuracywith a given tree-shaped hierarchy.Firstly，the image classification problem is converted as finding the best path in the tree hierarchy，and a novel branch and bound-like algorithm is introduced to efficiently search for the best path.Secondly，the classifiers are trained using a Structured SVM(SSVM)formulation with various bound constraints.Simulation results show that，thismethod achieves a significant 4.65%，5.43%，and 4.07%improvement in accuracy at high efficiency compared to state-of-the-art greedy“tree-based”methods on Caltech-256，SUN and ImageNet1K dataset，respectively.

image classification;branch and bound;optimal path;greedy algorithm;efficiency;accuracy

TP393

A

陳潔萍(1980—)，女，碩士，講師，主要研究方向?yàn)閳D像處理、云計(jì)算;

??健男

2014-07-17

【本文獻(xiàn)信息】陳潔萍，甘泉，張慧.一種基于最優(yōu)路徑搜索的圖像分類方法［J］.電視技術(shù)，2014，38(23).

國家自然科學(xué)基金項(xiàng)目(61373070/F020501)

甘 泉(1980—)，碩士，講師，研究方向?yàn)閳D像處理、數(shù)據(jù)挖掘;

張 慧(1978—)，女，博士，副教授，碩士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助幾何設(shè)計(jì)。