出品 | AI科技大本營（ID:rgznai100）
6月14日-19日，CVPR 2020在線上舉行，據了解，本屆大會共收到6656篇投稿，接收論文1470篇，錄用率約22%，低於ICCV 2019論文錄用率（25%），為十年以來最低錄用率。
在今年的CVPR上，AR公司亮風台提出完全可訓練的圖匹配方法，論文《Learning Combinatorial Solver for Graph Matching》入選CVPR 2020 Oral presentation（約5%比例）。據了解，在CVPR 2019上，亮風台投影AR新算法同樣入選 Oral環節，該成果為投影AR技術應用落地提供了重要的技術基礎。
在計算機視覺領域，基於學習的圖匹配方法已經有十多年的發展和探索史，近幾年發展和普及速度更迅速。然而，以往的基於學習的算法，無論有無深度學習策略，都主要集中在節點學習和/或邊緣仿射的生成上，而對組合求解器的學習關注較少。
亮風台及其合作方提出了一個完全可訓練的圖匹配框架，在該框架中，仿射學習和組合優化求解並不像以往的許多技術那樣被明確地分開。團隊首先將兩個輸入圖之間建立節點對應的問題轉化為從一個已構造的分配圖中選擇可靠節點的問題。隨後，採用圖網絡塊模塊對圖進行計算，形成各節點的結構化表示。最後為每個節點預測一個用於節點分類的標籤，並在排列差分和一對一匹配約束的正則化下進行訓練。
為了進行評估，新算法在四個公共基準上進行了測試，與包括非學習和基於學習的算法在內的八個最新基準進行了比較。該算法對噪聲和異常值具有較強的魯棒性，總體上優於所有的基線算法。
總體來說，新成果提出的圖匹配學習框架有三個方面的貢獻：
• 通過構造一個給定兩個待匹配輸入圖的賦值圖，將圖匹配學習轉化為節點選擇學習；
• 將仿射學習和組合優化求解結合到一個統一的學習框架中，並擴展了用於結構表示和關係推理的圖形網絡塊模塊；
• 設計了一個新的損失函數，其中施加一對一匹配約束來監督網絡的訓練。
基於學習的圖匹配
傳統圖匹配的研究主要依賴於手工構建的仿射關係，這些仿射關係作為組合求解器的輸入。這種預先定義的參數關聯模型會限制捕捉真實匹配任務結構的靈活性，不合適的關聯模型可能會使匹配求解器偏離真實匹配解。
針對這一問題，圖匹配的學習在提高匹配精度方面顯示了其優越的性能，這主要是通過學習圖親和力度量的參數來代替手工構建的親和力度量來提高的。大多數傳統的學習圖匹配算法都是有監督的算法，需要對每個正圖中的每個節點對應關係進行詳細的標記以進行訓練。這些算法分別使用大餘量方法、非線性逆優化和基於平滑的技術以有監督的方式訓練匹配參數。與有監督方法相比，無監督方法不需要大量的節點級標記。後來，Leordeanu等人為二階以上約束模型提供一個半監督學習公式。與這些方法不同，Cho提出為類的所有實例參數化一個圖模型，並學習其結構屬性以進行可視化對象匹配。
儘管深度學習技術在許多領域都顯示出強大的威力，但關於圖形匹配的深度學習的文獻仍然有限。為數不多的開創性研究主要是對深網絡中的參數親合函數進行編碼，以便在計算出的節點和邊緣親合下獲得正確的匹配分配。Zanfir和Sminchisescu將圖匹配作為一個二次指派問題，在使用深參數特徵層次表示的一元和成對節點仿射下進行。它採用譜匹配作為組合求解器，對反向傳播具有可微性。Wang等人使用圖卷積網絡（GCN）框架作為節點嵌入模塊，該模塊聚合圖結構信息以生成節點音調相似性。通過這種方法，圖匹配被放鬆為線性分配，並採用Sinkhorn網作為組合求解器。
我們的工作屬於深度學習算法組。與以往的方法相比，我們的方法不僅關注於親和函數的學習，而且關注於組合求解器的學習，它們被有效地組合成一個完全可訓練的圖網絡。為了提高匹配精度，我們在學習框架中引入了強結構表示和它們之間的關係歸納偏差，並通過實驗驗證了其良好的性能。
問題描述
2.1圖匹配問題
n個節點的無向圖可以用表示，其中
和分別表示節點集和邊緣集。圖通常由一個對稱鄰接矩陣表示，若且唯若Vi與Vj之間存在邊時，Aij=1。通常將非負實值權重 Aij=Wij與所有節點對相關聯，將鄰接矩陣泛化為加權圖。 這種概括對於許多應用程式捕獲節點之間的結構關係很重要。在本文的其餘部分中，除非另有說明，否則所有提及的鄰接矩陣均以實數值加權。
對於圖匹配問題，給定兩個節點為的圖，不失一般性我們假設。圖匹配問題可以表示為找到一個節點對應關係以支持如下的全局一致性：
上式表示的加權圖匹配在實踐中通常受到限制，因為每個圖的邊僅與標量屬性相關聯，並且邊緣一致性函數僅限於邊緣權重之差。在最近的研究中[6,7,9,11,19]，圖匹配問題通常描述為
其中是將節點對應關係映射到整數索引的雙射函數。
在本文中，我們主要研究上式的圖匹配算法，因為它不僅可以編碼邊權重之差，而且還可以編碼許多複雜的兼容性函數。
2.2 匹配作為節點標註問題
圖1. 分配圖構造示例
在過去的幾十年中，針對上述圖節點選擇問題已經提出了許多算法。最近的一些研究包括使用特徵向量技術在分配圖中找到主要的強連通簇，以及採用Markov隨機遊走的統計數據來選擇可靠的節點。
與這些手工設計的算法不同，本文提出了一種數據驅動的方法，該方法能夠學習如何解決整數二次程序（IQP）問題。
我們的方法：群組敏感的圖網絡框架
Battaglia等提出了一種圖網絡（GN）框架，該框架在圖結構上運行並相應地構造其計算，定義了一類用於圖結構表示的關係推理的函數。
GN框架中的主要計算單元是GN塊，它是一個圖到圖的模塊，該模塊將圖作為輸入，對結構進行計算，然後將圖作為輸出返回。在GN塊中處理的信息分為三個級別：實體由圖的節點表示，實體的關係由邊表示，系統級別的屬性由全局屬性表示。一個GN塊包含：
三個聚合函數將輸入圖的信息從邊到節點，最後到全局屬性進行聚合；三個更新函數，使用聚合的信息來更新輸出圖。
原始圖匹配問題的一對一匹配約束意味著：分配圖中的同一節點相關聯的任何節點子集都包含一個且只有一個正節點。這些一對一匹配約束通常在指導解決圖匹配問題中起關鍵作用。為了在我們的圖網絡中施加一對一的匹配約束，因此我們需要聚集分配圖中的不同節點子集的信息。但是，中提出的GN框架由於缺乏群組級屬性而不足以對節點的子集進行建模。
為解決上述問題，我們為圖匹配問題開發了一個可感知群組屬性的GN框架。我們的群組敏感的GN框架分為四個級別：實體由圖形的節點表示，實體的關係由邊表示，節點的子集屬性由群組屬性表示，系統級別的屬性由全局屬性表示。相應地，它包含5個聚合函數，和4個更新函數 ，
當將圖G作為輸入提供給群組敏感的GN塊時，計算將從邊、節點、群組、最後到全局級別進行。算法1顯示了完整的群組敏感的GN塊中的計算步驟。請注意，儘管我們在此假設了此步驟順序，但實際計算並不一定需要按該順序嚴格執行。同樣，某些計算步驟可以根據不同的任務跳過。例如，在我們的圖匹配實驗中，全局屬性是不必要的，因此將跳過步驟6、7、8和9。特別是，如果我們在某些任務中不使用群組級別的屬性，並刪除步驟4、5和8，則群組敏感的GN塊簡化為原始GN塊。
實驗4.1 模擬2D點集
4.2 CMU House數據集
CMU房屋數據集包括111個圖像序列幀，其中所有序列都包含經過變換的相同房屋對象。為了評估匹配精度，在所有幀中手動跟蹤並標記了30個標定點。
對於訓練中的每個試驗，我們通過從111幀中隨機選擇兩個示例來形成圖像對。為了評估噪聲對圖匹配算法的影響，我們使用節點設置（n1, n2）=（10, 30），其中該對的第一個示例從30個標定點中隨機選擇10個點，這意味著第二個示例包含20個離群點。我們將每個標定點建模為一個圖節點，然後通過Delaunay三角剖分建立圖的邊。每條邊(i, j)賦予權重Aij，權重Aij計算為連接節點vi和vj之間的歐式距離。節點親密度設置為0，並且計算中的邊(i,j)和中的邊(a,b)之間的邊親和度為
為了進行測試，我們匹配了所有可能的圖像對，總共560對圖像相隔10、20，...，100幀，其中增加的採樣間隔意味著變形程度的增加。節點選擇、圖形構造和親和力生成與訓練時相同。圖3示出了相對於不同圖像序列間隔的性能曲線。
4.3 Willow數據集
此數據集由Minsu Cho等人提供，他們從Caltech-256和Pascal VOC 2007收集了五類圖像，即汽車，鴨，人臉，摩托車和酒瓶。每個類至少包含40張具有不同實例的圖像，並在每個類別的所有圖像上手動繪製了10標定點標記在目標對象上。
表1顯示了我們的算法與基準算法的匹配精度（[5、15、17]的結果引自[15]）。
結論
為了提高匹配精度，提出了一種新的圖形匹配深度學習算法。我們首先將輸入圖之間建立節點對應的問題轉化為從構造的指派圖中選擇可靠節點的問題。為了解決節點分類問題，我們提出了一種完全可訓練的網絡，該網絡嵌入圖網絡塊模塊，通過對每個節點的鄰域進行卷積，形成其結構化表示。此外，還提出了一種新的損失函數來編碼一對一的匹配約束，以指導網絡的訓練。實驗結果表明，我們的圖匹配算法對噪聲和離群點具有較強的魯棒性，並優於目前最先進的算法。
原文連結：
http://openaccess.thecvf.com/content_CVPR_2020/html/Wang_Learning_Combinatorial_Solver_for_Graph_Matching_CVPR_2020_paper.html