金字塔匹配核用圖像特征集的判別分類

1、金字塔匹配核：用圖像特征集的判別分類Kristen Grauman and Trevor Darrell2005年摘要判別學(xué)習(xí)是具有挑戰(zhàn)性的，當(dāng)實(shí)例是特征集，且這些集合的基數(shù)是變化的并缺乏任何有意義的排序?；趦?nèi)核的分類方法可以學(xué)習(xí)復(fù)雜的決策邊界，但當(dāng)輸入是無序集時(shí)內(nèi)核必須以某種方式解決對應(yīng)關(guān)系通常一個(gè)計(jì)算昂貴的任務(wù)對大型數(shù)據(jù)集來說變得不切實(shí)際。我們提出了一個(gè)新的快速核函數(shù)將無序的特征集映射到多分辨率直方圖，并在這個(gè)空間計(jì)算加權(quán)直方圖交叉核。這種“金字塔匹配”的計(jì)算量與特征的數(shù)量是成線性關(guān)系的，它基于匹配首次出現(xiàn)的最精細(xì)分辨率的單元格隱式地找到對應(yīng)關(guān)系。因?yàn)閮?nèi)核并沒有penalize（懲罰，使

2、處于不利地位）額外特征的存在，它對雜波具有魯棒性。我們展示核函數(shù)是正定的，這使其在最優(yōu)解決方案只能保證Mercer內(nèi)核的學(xué)習(xí)算法中的應(yīng)用是有效的。我們在目標(biāo)識(shí)別任務(wù)中驗(yàn)證了我們的算法，并證明它是準(zhǔn)確的比當(dāng)前的一些方法更快。1. 引言用于計(jì)算機(jī)視覺的各種表示包括無序的特征集或部分集，其中每個(gè)集合有不同的基數(shù)，并在每個(gè)集合中的特征之間的對應(yīng)關(guān)系是未知的。例如，一個(gè)圖像可能由一組檢測到的局部仿射不變區(qū)域描述，一個(gè)形狀可以由一組定義在每個(gè)邊緣點(diǎn)的局部描述符描述，或一個(gè)人的臉可以由一組不同的面部部分塊表示。在這種情況下，特征向量集代表一個(gè)特定感興趣類別（對象，場景，形狀，人臉等）的單一實(shí)例，并且人們期望

3、特征的數(shù)目在不同的例子由于視點(diǎn)變化，閉塞，或由興趣算子的不一致檢測中是不同的。用這種表示來執(zhí)行如分類或識(shí)別這樣的學(xué)習(xí)任務(wù)是具有挑戰(zhàn)性的。雖然生成方法已經(jīng)取得了一些成功，但基于內(nèi)核的識(shí)別方法以有效地表示復(fù)雜的決策邊界和概括（generalize well）未知數(shù)據(jù) 24，21 而著稱。例如，支持向量機(jī)（SVM）是一種廣泛使用的找出兩類之間的最佳分離超平面的判別分類方法。核函數(shù)，衡量輸入數(shù)據(jù)的相似性，向決策功能引入了非線性；內(nèi)核非線性地將輸入空間的兩個(gè)實(shí)例映射到特征空間中的內(nèi)積。然而，傳統(tǒng)的基于核的算法被設(shè)計(jì)為固定長度的向量輸入操作，其中每個(gè)輸入向量對應(yīng)于該實(shí)例的一個(gè)特定的全局屬性；定義在的常用的

4、通用內(nèi)核（例如，高斯RBF，polynomial(多項(xiàng)式)）不適用于向量空間。圖1.金字塔匹配核交叉直方圖成金字塔狀形成的局部特征，近似于特征集之間的最佳匹配。在這項(xiàng)工作中，我們提出了一個(gè)金字塔匹配核定義在無序特征集合上的允許它們被有效并高效地應(yīng)用在基于核的學(xué)習(xí)方法中的新的核函數(shù)。每一個(gè)特征集被映射到一個(gè)在最精細(xì)水平保留單個(gè)特征的特性的多分辨率直方圖上。然后使用加權(quán)直方圖相交計(jì)算來比較直方圖金字塔，我們顯示了在匹配對第一次出現(xiàn)的最精細(xì)分辨率的直方圖單元里定義的隱式的對應(yīng)關(guān)系（見圖1）。通過金字塔匹配度量的相似性近似于不平等基數(shù)（unequal cardinality）的特征集之間的最佳對應(yīng)度量

5、的相似性（即，在較低的基數(shù)集合中的最佳匹配點(diǎn)的部分匹配近似于較大的基數(shù)集合中的點(diǎn)的一些子集，這樣匹配點(diǎn)之間的總的相似性是最大的）。我們的核是非常有效的并且可以在與集合的基數(shù)成線性的時(shí)間內(nèi)被計(jì)算。我們證明了我們的核函數(shù)是正定的，這意味著它適合于與保證只為正定核收斂到一種獨(dú)特的優(yōu)化（例如，支持向量機(jī)）的學(xué)習(xí)方法一起使用。因?yàn)樗籶enalize多余數(shù)據(jù)點(diǎn)的存在，我們所提出的核對雜波是魯棒的。我們將表明，這轉(zhuǎn)化為用不同背景或遮擋來處理未分割圖像的能力。核還respect輸入集所固有的共生關(guān)系：代替單獨(dú)的集合中的匹配功能，忽略一個(gè)集合中由特征所傳達(dá)的潛在的依賴關(guān)系，我們的相似性度量捕捉特征的聯(lián)合統(tǒng)計(jì)。

6、解決這個(gè)問題的其他方法已被提出25，3，12，27，16，20，14，但不幸的是，這些方法中的每一個(gè)都有以下缺點(diǎn)中的某一些：計(jì)算復(fù)雜度使大型特征集不可行；參數(shù)分布的限制可能無法充分描述數(shù)據(jù)；非正定（不保證對支持向量機(jī)唯一的解決方案）的內(nèi)核；相同大小集合的限制；和不考慮特征集內(nèi)的依賴關(guān)系。我們的方法解決了所有這些問題，產(chǎn)生了適用于在已經(jīng)存在的任何基于核的學(xué)習(xí)范式中比較無序的，長度可變的特征集合的核。我們用目標(biāo)識(shí)別任務(wù)證明了我們的算法，并顯示其準(zhǔn)確性比得上當(dāng)前的方法，然而需要顯著較少的計(jì)算時(shí)間。2.相關(guān)工作 在本節(jié)中，我們將回顧基于特征集合的判別式分類的相關(guān)工作，采用內(nèi)核和支持向量機(jī)進(jìn)行識(shí)別及多分

7、辨率圖像表示。 目標(biāo)識(shí)別是一個(gè)具有挑戰(zhàn)性的問題，需要來自一個(gè)分類器的強(qiáng)大的推廣能力，以應(yīng)對同一對象或?qū)ο箢惖膱D片的各種各樣的光照，視角，閉塞，雜亂，類內(nèi)外形和變形的發(fā)生。雖然研究者已顯示出將支持向量機(jī)用于目標(biāo)識(shí)別的有希望的結(jié)果，但他們通常使用全局圖像特征 將圖像作為一個(gè)整體的長度相等的特征，例如顏色或灰度直方圖或原始像素?cái)?shù)據(jù)的向量5,1,17。眾所周知，這種全局表示對真實(shí)世界的成像條件，如閉塞，姿勢的變化或圖像的噪聲是敏感的。 最近的工作已經(jīng)表明，局部特征不變的普通圖像變換（例如，SIFT 13）是用于識(shí)別的一個(gè)強(qiáng)大的表示，因?yàn)樵撎卣骺梢栽诓煌囊暯?，姿勢，或照明條件下的同一對象或場景的實(shí)例中

8、被可靠地檢測和匹配。然而，大多數(shù)方法使用最近鄰（例如，1,8，22，2）或基于投票分類器及隨后的對準(zhǔn)步驟（例如，13，15）的局部特征表示來進(jìn)行識(shí)別；這兩種方法可能對大型訓(xùn)練集來說是不切實(shí)際的，因?yàn)槠浞诸悤r(shí)間隨著訓(xùn)練實(shí)例數(shù)的增加而增加。另一方面，一個(gè)支持向量機(jī)確定訓(xùn)練示例的稀疏子集（支持向量）以描繪一個(gè)決策邊界。 基于核的學(xué)習(xí)算法，其中包括支持向量機(jī)，核PCA，或高斯處理已經(jīng)成為可用于包括判別性分類，回歸，密度估計(jì)，和聚類21的多種情況下完善的工具。最近，注意力已集中于開發(fā)專門的內(nèi)核，它們可以在數(shù)據(jù)不能由歐幾里得向量空間（如圖，字符串或樹）自然地表示時(shí)更充分地利用這些工具。一些研究人員已經(jīng)設(shè)計(jì)

9、了操作在無序特征集上的相似性度量。見表1對方法的簡要比較。25的作者提出了在其他集合的每個(gè)特征最佳匹配特征的相似性中求平均值的核。在該核內(nèi)的“最大”操作符的使用使它成為非默瑟核（即，不正定 - 見第3部分），因此在用于SVM時(shí)它缺乏收斂保證。14中給出的類似的核也考慮了所有可能的特征的匹配，但沒有提出每對特征之間的相似性。25和14都有一個(gè)計(jì)算復(fù)雜性是在特征的數(shù)量二次。此外，無論是獨(dú)立地匹配一組中的每個(gè)特征，忽略可能有用的同現(xiàn)信息。相比之下，我們的內(nèi)核由它們同時(shí)匹配作為一組捕獲的共現(xiàn)的功能的聯(lián)合統(tǒng)計(jì)信息。表1：比較匹配無序集合的內(nèi)核方法。每列展示每個(gè)方法的計(jì)算代價(jià)及是否內(nèi)核可以捕獲共現(xiàn)（C），

10、是否正定（P），不假定一個(gè)參數(shù)模型（M），能否處理不相等基數(shù)的集合（U）。d是向量的維數(shù)，m是最大的集合基數(shù)，D是向量空間的直徑。“金字塔”指的是所提出的內(nèi)核。在3是根據(jù)給定的上找到使用貪婪啟發(fā)式兩組之間的次優(yōu)匹配的方法;盡管這導(dǎo)致在非Mercer核，作者提供調(diào)整內(nèi)核超參數(shù)以便限制給定的內(nèi)核矩陣不是正定的概率的裝置。 27措施相似的作者在由兩組矢量元素跨越的兩個(gè)線性子空間之間的主要角度而言。這個(gè)內(nèi)核是僅正定為集相等的基數(shù)，并且其復(fù)雜性是在特征的數(shù)量的立方。在20，代數(shù)內(nèi)核被用于通過基于矢量的內(nèi)核給出相似性結(jié)合，與加權(quán)選擇以反映功能是否在對準(zhǔn)（訂購）。當(dāng)設(shè)置基數(shù)發(fā)生變化，輸入被用零填充，以便形成

11、大小相等的矩陣。在12，高斯擬合到每個(gè)組向量，然后兩組之間的核心價(jià)值是其高斯分布之間的巴氏親和力。正如作者指出，該方法被約束為以具有閉合形式解使用高斯模型。在實(shí)踐中，在12的方法也限于套小基數(shù)，因?yàn)樗膹?fù)雜性是在特征的數(shù)量的立方。同樣的，16的作者適合高斯到功能設(shè)置，然后使用KL散度作為距離度量比較集。不像12和16的核，這是基于該假定的輸入將適合某種形式的參數(shù)模型，我們的方法是無模型，并在表示保持不同的數(shù)據(jù)點(diǎn)。與無序集合數(shù)據(jù)處理時(shí)的另一種方法是，從每個(gè)類指定原型的例子，然后表示在它們的距離為每個(gè)原型的條款的示例;在歐氏空間向量處理標(biāo)準(zhǔn)算法是那么適用。28的作者建立手寫數(shù)字這樣的分類，并使用1

12、作為相似的措施的形狀內(nèi)容的距離。面對這樣一個(gè)基于原型的方法，這些問題是確定哪些例子將作為原型，選擇多少應(yīng)該有，并適當(dāng)更新原型遇到新的數(shù)據(jù)類型時(shí)。我們的特征表示基于多分辨率直方圖或“金字塔”，這是由分箱的數(shù)據(jù)點(diǎn)到越來越大尺寸的離散區(qū)域來計(jì)算。單級(jí)直方圖已在各種視覺識(shí)別系統(tǒng)被使用，其中第一個(gè)是該23，其中，使用全球顏色直方圖的相交進(jìn)行比較的圖像。金字塔已被證明是在各種各樣的圖像處理任務(wù)的有用表示 - 見摘要9。在10，多分辨率直方圖與距離L1相比近似相等質(zhì)量全局顏色直方圖的對最近鄰圖像檢索的最小代價(jià)匹配。這啟發(fā)我們使用了點(diǎn)將臺(tái)類似的表示。然而，與10，我們的方法生成一個(gè)判別分類器，并將其與加權(quán)相交

13、，而不是L1比較直方圖。我們的方法允許輸入到具有不等基數(shù)并因此使部分的匹配，這是用于處理雜波和未分割的圖像在實(shí)踐中重要的。我們相信，我們的是提倡使用直方圖金字塔作為形成在套明確判別功能，并且所述第一與分層加權(quán)直方圖交集相似性測量使用時(shí)，以顯示其為最佳局部匹配連接所述第一工作。3 方法 基于內(nèi)核的學(xué)習(xí)算法 24，21 是建立在將數(shù)據(jù)嵌入到歐氏空間（n維空間）中的思想，然后在嵌入的數(shù)據(jù)中尋找線性關(guān)系。例如，一個(gè)SVM找到嵌入式空間（也被稱為特征空間）中兩個(gè)類之間的最優(yōu)分類超平面。核函數(shù)K：用于在輸入空間X中將數(shù)據(jù)點(diǎn)對的內(nèi)積映射到嵌入空間F中，從而評(píng)估所有點(diǎn)之間的相似性并確定它們的相對位置。在嵌入式

14、空間中尋求線性關(guān)系，但在輸入空間中的決策邊界仍然可能是非線性的，這取決于特征映射函數(shù)：XF的選擇。 這項(xiàng)工作的主要貢獻(xiàn)是一種新的基于隱式對應(yīng)的核函數(shù)，它能對無序、可變長度的向量集合判定類別?？梢宰C明內(nèi)核是正定。我們的算法的主要優(yōu)點(diǎn)是它的效率，其使用遵守共同特征的聯(lián)合統(tǒng)計(jì)的隱式對應(yīng)關(guān)系，并對雜波或“多余的”數(shù)據(jù)點(diǎn)有抵抗性。 我們的方法的基本思想是將特征集合映射到多分辨率直方圖，然后將該直方圖與加權(quán)直方圖相交的措施以近似特征集合之間最佳局部匹配的相似性。我們稱之為“金字塔匹配核”，因?yàn)檩斎爰晦D(zhuǎn)換為多分辨率直方圖。3.1 金字塔匹配核我們考慮一個(gè)包含d維特征向量集合的輸入空間X，其邊界是一個(gè)直徑為

15、D的球，其最小矢量間距離是：， （1）這里在X中的不同實(shí)例下mx是變化的。特征提取函數(shù)被定義為：， （2）這里是一個(gè)直方圖向量用長度為的d維bins在數(shù)據(jù)x上形成的，的維度為。換句話說，是一個(gè)級(jí)聯(lián)直方圖向量，并且結(jié)果中每個(gè)分量直方圖的bin是前一個(gè)的兩倍。最精細(xì)直方圖中的bin是足夠小的使得來自集合X的每個(gè)d維數(shù)據(jù)點(diǎn)落入自己的bin中，然后bin的長度增加直到集合x中所有的數(shù)據(jù)點(diǎn)在L層落入單一的bin中。金字塔匹配核基于隱式對應(yīng)關(guān)系在多分辨率直方圖空間中測量點(diǎn)集之間的相似性。兩個(gè)輸入集之間的相似性被定義為每級(jí)金字塔的特征匹配數(shù)的加權(quán)總和，匹配數(shù)由計(jì)算： （3）這里表示在i層新的匹配對的數(shù)量。一

16、個(gè)新的匹配被定義為在任何更精細(xì)分辨率水平下不匹配的一對特征。內(nèi)核隱式地找到點(diǎn)集之間的對應(yīng)關(guān)系，如果我們考慮一旦兩個(gè)點(diǎn)落入同一bin里（從最精細(xì)的分辨率級(jí)別，其中每一點(diǎn)被保證有自己的bin）則認(rèn)為這兩個(gè)點(diǎn)匹配。匹配等價(jià)于一個(gè)層次化過程：在較高分辨率下不能對應(yīng)的向量有可能在較低分辨率下是匹配的。例如，在圖2中，在最精細(xì)分辨率下有兩個(gè)點(diǎn)是匹配的，在中等規(guī)模分辨率下增加了兩個(gè)新的匹配，在最粗略分辨率下又有一個(gè)新的匹配。的輸出值反映了匹配的整體相似性：在層每一個(gè)新的匹配對貢獻(xiàn)，正比于在該層兩個(gè)點(diǎn)的相似程度，由bin的大小確定。注意，公式（3）中的和從指數(shù)開始，因?yàn)榈亩x確保在層級(jí)處沒有點(diǎn)的匹配。 為了計(jì)

17、算，內(nèi)核用直方圖交函數(shù)，來衡量兩個(gè)直方圖bin之間的相交部分： （4）這里A和B是含有r個(gè)bin的直方圖，表示直方圖A第j個(gè)bin的計(jì)數(shù)。注：這里第0層分辨率最高（精細(xì)）直方圖交集有效地計(jì)算了兩個(gè)集合在給定量化層級(jí)的匹配數(shù)量，即落入相同bin的點(diǎn)的數(shù)目。為了計(jì)算在第層產(chǎn)生的新的配對數(shù)量，計(jì)算連續(xù)直方圖層級(jí)的交叉核之間的差值是足夠的： （5）這里指的是公式（2）中由生成的第個(gè)分量直方圖。注意內(nèi)核沒有明確地搜索相似的點(diǎn)它從不計(jì)算每個(gè)集合中的向量之間的距離。相反，它只是使用每個(gè)直方圖層級(jí)的交叉值的變化來計(jì)算匹配數(shù)。在金字塔每個(gè)層級(jí)上發(fā)現(xiàn)的新的匹配的數(shù)量根據(jù)直方圖bin的大小進(jìn)行加權(quán)：在較大bin里的

18、匹配的權(quán)值小于在較小bin的匹配的權(quán)值。由于長度為的d維超立方體bin的最大對角線是，金字塔中一個(gè)bin里任意兩點(diǎn)間的最大距離在每個(gè)逐漸粗糙的直方圖里是加倍的。因此，第i層產(chǎn)生的新匹配的數(shù)量的權(quán)值設(shè)為以反映該層所匹配點(diǎn)的相似性（最壞情況下）。直觀地說，這意味著在高分辨率特征最明顯下向量（集合y和z）之間的相似性被獎(jiǎng)勵(lì)更多比低分辨率下向量的相似性。在公式（3），（4）和（5）中，我們定義了（非歸一化）金字塔匹配核函數(shù)：（6）這里，并且是中的第i個(gè)直方圖。我們用每個(gè)輸入集合的自相似性的內(nèi)積來標(biāo)準(zhǔn)化這個(gè)值以避免有利于更大的輸入集合，最終的內(nèi)核值，這里。為了減輕由離散的直方圖bin可能引起的量化效果，我們可以用隨機(jī)轉(zhuǎn)換bin的方式將在不同的多分辨率直方圖下形成的多（T）層金字塔匹配數(shù)量得出的內(nèi)核值結(jié)合起來。每個(gè)T層金字塔的各維度轉(zhuǎn)換至在0至D之間隨機(jī)選擇的數(shù)的維度。公式2中應(yīng)用的T個(gè)特