ICCV2019 Oral論文：基於圖嵌入的深度圖匹配（已開源）

2019 年 10 月 4 日
筆記

原創技術文章，第一時間獲取

由上海交通大學研究團隊獨立完成的論文Learning CombinatorialEmbedding Networks for Deep Graph Matching已被ICCV2019會議錄用為Oral論文。

這篇論文聚焦於電腦視覺領域一項歷久彌新的問題：圖匹配問題。在電腦視覺中，圖匹配旨在利用圖結構資訊，尋找物體之間節點與節點的對應關係。已有的研究工作通常從數學優化的角度求解圖匹配的數學形式，而忽視了機器學習、尤其是深度學習在圖匹配問題上的巨大潛力。作者提出，基於嵌入（embedding）技術的深度學習方法具有高效建模圖結構的能力，它能夠降低圖匹配求解運算的複雜度，同時整個框架能夠進行端到端的訓練。

論文下載

（https://arxiv.org/abs/1904.00597）

相關程式碼

（https://github.com/rogerwwww/PCA-GM）。

概述

圖 1 論文提出的框架概覽

在這篇工作中，通過CNN網路與嵌入網路，作者高效地建模了影像與圖結構的相似度資訊。作者提出了排列損失函數以替代已有工作中的偏移損失函數，進行端到端的監督訓練。通過引入嵌入技術，圖匹配求解的複雜度大大降低，原先無法被精確求解的二階組合優化問題轉化為了能夠精確求解的一階問題。在論文中，作者採用了Sinkhorn演算法，在精確求解圖匹配問題的同時允許梯度回傳。這是圖嵌入技術被首次用於電腦視覺的圖匹配任務中。論文中提出的深度圖匹配框架如圖 1所示。在實驗中，作者提出的PCA-GM演算法以15%的相對精度超越了CVPR2018的最佳論文提名Deep Learning of Graph Matching，同時還能夠在多個類別之間進行知識遷移。

背景知識

圖匹配是電腦視覺和模式識別領域中一項重要的基礎性問題。通常，圖匹配問題的結果由一個指派矩陣（assignment matrix）X表示，其中指派矩陣的每行、每列有且僅有一個元素為1。為了同時建模圖結構之間的相似度，研究者們引入了同時包含一階和二階相似度資訊的相似度矩陣（affinity matrix）K。相似度矩陣是一個具有高階複雜度的矩陣，它的對角線元素包含了節點與節點的相似度資訊，非對角線元素包含了邊與邊的相似度資訊。基於相似度矩陣K與指派矩陣X，圖匹配問題可以被公式化為Lawler形式的二次指派問題（Lawler』s Quadratic Assignment Problem, Lawler』s QAP）：

其中，vec(X)代表對矩陣X進行列向量化。公式（1）中，一個列向量的轉置乘矩陣乘列向量，其結果是一個數值。直觀地看，公式（1）最大化了圖匹配對應關係中的一階相似度和二階相似度。在數學上，公式（1）是一個NP-難的二次指派問題。一方面，過去的圖匹配研究工作主要聚焦於如何快速、精確地求解公式（1）。在這篇工作中，作者引入了深度嵌入技術，將公式（1）中NP-難的二次指派問題轉化為可以精確求解的線性指派問題。

另一方面，圖匹配面臨的問題是如何建模相似度，即如何構建相似度矩陣K。傳統的圖匹配方法通常採用形如公式（2）的高斯核函數建模邊特徵fij與fab之間的相似度。

然而，形如公式（2）的固定參數形式並不能適應多樣化的輸入影像，建模得到的相似度資訊並不能準確地反映節點之間的匹配關係。因此，在過去的研究工作中，許多基於機器學習的圖匹配方法被提出，利用機器學習方法準確地建模圖匹配相似度。特別的，CVPR2018的最佳論文提名Deep Learning of Graph Matching首次將深度學習引入圖匹配，其中採用了VGG16網路提取特徵、譜方法求解圖匹配、像素偏移損失函數用於監督訓練（詳見公眾號對這篇論文的解讀：https://mp.weixin.qq.com/s/l1Bc5l5cr3y9jQbh-bEQeQ）。在PCA-GM中，作者採用了同樣的VGG16網路結構以進行公平的對比，同時採用了Sinkhorn演算法替代譜方法，求解匹配問題。

圖內卷積

如圖 1所示，在PCA-GM中，輸入一對含有關鍵點的圖片，我們使用CNN網路（VGG16）為每個關鍵點提取一個特徵向量。隨後，通過德洛內三角化（Delaunay triangulation），我們建立了一對包含影像特徵的圖結構。通過圖嵌入方法，我們能夠在節點的特徵向量中嵌入圖結構資訊。

圖 2 圖內卷積

在模型中，作者採用了圖卷積作為圖嵌入的方法。作者提出的圖內卷積GConv實際上與圖卷積網路GCN類似，通過在鄰接的節點之間傳遞特徵資訊，圖內卷積能夠在節點的特徵向量中嵌入圖結構的資訊，進而體現圖結構的相似度。圖內卷積的所有網路參數在所有節點之間共享。基於如圖 2所示的圖內卷積，作者提出了PIA-GM模型（圖 1中藍色箭頭所示）。

跨圖卷積

圖 3 跨圖卷積

基於圖內卷積，作者進一步提出了跨圖卷積CrossConv的形式。跨圖卷積在兩個待匹配的圖結構之間傳遞特徵，如圖 3所示。

在作者提出的跨圖卷積演算法中，首先輸入上一層（k-1層）的特徵向量

。隨後，第二行中，通過計算兩圖之間任意兩個向量的相似度，構造一個的相似度矩陣

。第三行對相似度矩陣採用Sinkhorn演算法，求解得到一個匹配關係

。這是由k-1層網路的特徵預測得到的匹配關係。這個預測得到的匹配關係作

為兩個圖結構之間跨圖更新的權重，在上一層特徵

中越相似的點對，在跨圖更新時具有越高的傳播權重。因此，直觀地看，跨圖卷積層在匹配過程中同時考慮了兩個待匹配圖結構的資訊，在嵌入層中引入了一一對應的匹配約束；與之對比，單純的圖內卷積只考慮了單個圖內部的結構資訊，沒有考慮節點一一對應的匹配約束。通過跨圖卷積更新，兩圖之間原本較為相似的特徵會更加相似。基於如圖 3所示的跨圖卷積，作者在論文中提出了PCA-GM模型（圖 1中黃色箭頭所示）。

匹配求解

在經過圖內和跨圖卷積層後，圖結構中的每個節點都擁有一個同時包含了影像特徵以及圖結構特徵的嵌入特徵向量。通過為任意兩個嵌入特徵計算相似度，我們即可構建一個相似度矩陣M。在衡量相似度時，作者額外引入了相似度權重矩陣A：

其中τ是調整公式（13）判別能力的超參數，

包含了可學習的相似度權重。需要注意的是，由於作者採用了嵌入技術，將圖結構特徵嵌入到了節點的特徵向量中，因此公式（13）得到的相似度矩陣規模是線性的，其複雜度小於公式（1）中的NP-難問題。實際上，由公式（13）組成的圖匹配問題可以被公式化為線性指派問題，可以採用如下介紹的Sinkhorn演算法在端到端的框架中精確求解。

在計算得到相似度矩陣後，作者採用了Sinkhorn演算法，從相似度矩陣求解匹配結果。Sinkhorn演算法是一種迭代演算法，它通過將輸入的矩陣交替進行行歸一化以及列歸一化，最終收斂得到一個每行、每列加和均為1的雙隨機矩陣（doubly stochastic matrix）。Sinkhorn演算法如公式（14）（15）所示

由於Sinkhorn演算法只包含了乘、除操作，Sinkhorn演算法完全可微，能夠被用於端到端的深度學習訓練中。論文作者藉助了PyTorch 的自動微分技術，高效地實現了Sinkhorn演算法及其反向傳播。

損失函數

在論文中，作者提出了基於交叉熵的損失函數：排列損失函數（Permutation loss）

作為對比，CVPR2018的工作採用了基於像素偏移的損失函數：

在實驗中，作者證明，基於交叉熵的排列損失函數能夠為模型提供更精確的監督資訊。在圖 4所示的對比中，排列損失函數的優勢被具象地闡述：圖 4中，粉紅色標註的兩個節點（馬的左耳）代表真實的匹配關係。右圖中，每個節點上方的數字代表模型預測當前節點與左圖粉紅節點匹配的概率。在這次不理想的預測中，右圖中的真值節點（右圖中的粉紅色節點）只獲得了0.05的概率。然而，基於像素偏移的損失函數為這次預測給出了一個相當低的損失值（只有0.070）；作為對比，排列損失函數能夠給出一個較高的損失值（5.139）。顯然，排列損失函數為模型訓練提供了更加準確的監督資訊。

圖 4 排列損失與偏移損失對比

直觀來看，在圖 4所示的例子中，排列損失函數能夠分清馬的左、右耳，進而讓模型學習其中的結構化差異；與之對比，由於馬的左、右耳在空間上離得太近，偏移損失函數並不能夠將它們明確地區分，因此不能為訓練提供足夠的監督資訊。從圖匹配的數學形式看，作為一個組合優化問題，圖匹配問題與影像中關鍵點實際的像素位置並無緊密聯繫，採用基於交叉熵的排列損失函數迎合了圖匹配作為組合優化問題的本質。

實驗結果

在包括了真實圖片匹配以及模擬數據集上，作者提出的PCA-GM與PIA-GM均取得了最高的匹配精度，超越了基於傳統機器學習的方法以及CVPR2018 Deep Learning of Graph Matching中提出的模型GMN。

模擬數據集：