一種基于最優路徑搜索的圖像分類方法

陳潔萍，甘 泉，張 慧

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

一種基于最優路徑搜索的圖像分類方法

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

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

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

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

1 算法簡介

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

為了提高測試時間效率，從結構最頂層到最底層運行分類器使用貪婪預測算法來逐漸降低類別數量。因此，算法在測試期間獲得了預期中的“準線性復雜度”(相對于類別數量)。

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

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

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

2)使用拓展SSVM在更多的邊界約束下對邊界和模型參數展開聯合學習，使得可以在精度和效率間實現更好折中。

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

2 相關工作

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

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

3 本文模型

本文的目標是設計一種圖像結構分類器，更好地在精度和效率間實現平衡。在本節中，首先定義了“基于樹”的模型，然后給出如何將模型轉換為“最優路徑模型”。

3.1 基于樹的模型

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

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

3.2 最優路徑模型

式中:P1是樹中從根節點υ=1開始到達葉節點的所有路徑的集合。最優路徑模型可以看成是一對多支持向量機的特殊情況，因為沿著每條路徑的分類器參數的累積和可以看成是一對多支持向量機中一個類別的所有分類器參數。關鍵差別在于，樹結構要求2條路徑的參數根據路徑的重疊情況部分共享。換句話說，本文模型利用結構知識在類別間共享參數，以便結構中距離更近的類別有更為相似的參數，這一屬性有助于提升相對一對多支持向量機的精度。

4 分支界定預測算法

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

算法1:高效的分支界定預測

要求:輸入x∈RD，樹T，得分函數S，各節點的上界{Uυ}υ。

目的:見式(1)。

1)將Q初始化為空優先級隊列;

5)for e=1:N do;

9)end for;

進行常規健康教育，健康教育6 個月后，對病人集體進行1次 60 min的骨質疏松預防知識講解，同時為每例病人免費提供1本 2 型糖尿病病人骨質疏松預防小冊。

12)設置P*=［］。

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

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

4.2 邊界計算

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

每個節點緩存的最緊湊上界是與輸入有關的Uυ(x)，當已知輸入x時通過評估樹中的所有分類器可以確定最緊湊上界。然而，確定邊界的成本與最優路徑蠻力搜索算法的成本相同。此外，對每個輸入均需計算一次。另一方面，提出利用訓練輸入X來估計與輸入無關的上界Uυ，且模型訓練后上界只需估計一次。請注意，Uυ邊界未必一定合理，因為Uυ可能小于未知測試輸入x∧的上界Uυ(x∧)。然而，筆者發現在實踐中估計的可靠性較高，因為分類精度一般沒有被犧牲，如圖2所示(其中，節點表示沒有邊界下降率約束條件下且松馳度(ρ)不同時進行訓練獲得的模型)。于是，將其稱為分支界定類似算法。

圖2 分支界定類似算法對Caltech-256數據集的有效性

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

5 結構化SVM學習

可以使用結構化SVM(SSVM)來學習得分函數，并采用結構化輸出P對樹形結構中的路徑進行編碼。考慮到有一組訓練輸入及樹的真實路徑{xm，Pm}m=1～M，求解如下SSVM問題

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

通過避免學習模型參數然后估計各節點的上界U={Uυ}υ，可以把式(3)的SSVM問題進行拓展，以聯合學習模型參數W和各節點的上界U

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

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

6 實驗

本文基于3個公開數據集(Caltech-256，SUN-397和ImageNet1K)來評估本文算法性能。目標是:1)驗證本文方法的精度高于一對多算法;2)與當前最新基于樹的算法［4］相比，更好地實現精度和效率間的平衡。

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

6.1 基本設置

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

6.2 Caltech-256

Caltech-256數據集包括256個對象類別。對每個對象類別，與文獻［4］類似，隨機提取40個圖像作為訓練數據，40個圖像作為測試數據。使用帶有21K維度的LLC特征來重現文獻［4］給出的一對多精度。與松弛度ρ={0.5，0.6，0.7，0.8，0.9}相對應的5種結構接受訓練以便進行比較。

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

圖4 針對Caltech-256數據集，本文方法、松弛結構［4］和一對多SVM算法的精度和相對復雜度平衡結果

圖5 針對Caltech-256數據集使用ρ=0.9模型時，分類精度相對第1分級至第5分級預測相對復雜度的變化情況

6.3 Sun-397

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

圖6 針對Sun-397數據集，本文方法、松弛結構［4］算法和一對多SVM算法的精度和相對復雜度平衡結果

6.4 ImageNet數據集

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

圖7 針對ImageNet數據集，帶有邊界約束的本文方法、不帶有邊界約束的本文方法、松弛結構［4］算法和一對多SVM算法的精度和相對復雜度平衡結果

7 結論

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

［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］陳榮，曹永鋒，孫洪.基于主動學習和半監督學習的多類圖像分類［J］.自動化學報，2011，37(8):3601-3605.

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

［7］徐杰，景麗萍，于劍.基于超邊相關性的圖像分類方法［J］.模式識別與人工智能，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—)，女，碩士，講師，主要研究方向為圖像處理、云計算;

??健男

2014-07-17

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

國家自然科學基金項目(61373070/F020501)

甘 泉(1980—)，碩士，講師，研究方向為圖像處理、數據挖掘;

張 慧(1978—)，女，博士，副教授，碩士生導師，主要研究方向為計算機圖形學、計算機輔助幾何設計。