論文|通過模板匹配方式發現結構化變體

本文為極市平台論文原創編譯，首發極市平台微信號 論文|通過模板匹配方式發現結構化變體。

本文來源自下面論文

編譯作者：晨陽

概括

如何判斷原始測量數據的變化模式仍然是形狀分析的棘手問題。 這個需求揭示了哪些元素被重複，或者元素如何能夠作為來自公共基本元素的結構變化而被發現的問題。 文中通過在建築物的3D採集的例子中對這個問題進行了調研。利用一組模板模型，作者發現了構建元素的幾何相似性，從而使每個模板都配有限定基本幾何形狀的變形模型。文中演算法的核心是同時進行模板匹配和變形分析，通過提取其匹配模板的變形模式的相似性來檢測構建元素。本文也證明了此分析方式可以成功地檢測出結構變化，並對嘈雜和不完整的數據也適用。

原理

涉及到構建數字城市的許多應用，如地圖和導航，嚴重依賴於建築物的三維（3D）模型。目前通常是使用多視圖立體重建（MVS）或3D掃描技術等來將真實場景數字化。然而，由於光照的變化，建築物的遮擋及鏡面表面等一系列問題，上述方法經常會導致模型雜訊及部分重建。本文使用了一組常見元素類型（如窗口）的模板模型，用文中的演算法對建築物的3D重建（MVS或掃描）進行操作，其中元素（窗口）構成落入其邊界框內的輸入重建的子集。 對於其中的每個元素，作者確定了最佳匹配模板並計算出此模板的最佳擬合變形，在文中稱之為模板實例。文中演算法的核心是通過檢測其匹配模板實例的變形參數中的模式，來揭示元素之間的幾何相似性。如圖1所示，對於配備i-Wires變形模型的模板T，文中給出了具有檢測到的特徵線的不同參數的各種實例（以紅色示出），並使用多維縮放投影將每個實例可視化為相應變形空間中的點。

圖1

本文模板的每個實例都被表示為k維變形空間中的點，其中附近的點表示具有類似變形參數的實例。作為基本幾何的變化的元素將映射到附近的點（參見圖2a）。這在基於變形空間中的成對元素距離計算的相似性矩陣中被揭示（參見圖2右）。作為精確複製的元素表示為紅色塊，而具有部分相似性的元素由更接近紅色的顏色表示。然而，即使是在真實數據的情況下，由於雜訊和部分數據丟失的存在，精確副本的元素也經常匹配相同模板的不同實例（參見圖2b）。因此，通過類似的元素映射到模板變形空間中的散點，難以觀察到清晰的簇。為解決這個問題，作者建議同時分析輸入元素（參見圖3）。作者通過變形一組模板來適應給定的元素。然後文中組合了來自模板變形的觀察結果，將每個元素映射到公共子空間表示。直觀地來看，類似的元素被期望映射到該子空間中的附近點。而通過使用變形空間中的成對元素距離作為約束，作者始終採用變形的模板實例來標記每個元素。

圖2：（a）在輸入完美數據的情況下，具有相同幾何的元素被映射到矩形模板的單個點具有部分相似性，即具有相同寬度或高度的元素形成鬆散的簇。 （b）由於雜訊和數據丟失的存在，這使得在變形空間中難以清楚得觀察簇。使用變形空間中的成對元素距離計算相似性矩陣可以解決這種問題。

圖3：給定建築物的3D採集（例如，MVS），文中利用一組可變形模板來匹配其元素，即窗口。本文通過子空間分析來合併來自多個模板變形的觀察，以提取元素之間的關係。 使用這些關係作為約束，文中用變形的模板實例來標記每個元素（相同的實例用相同的顏色表示）。 本文通過合併與類似模板實例匹配的元素來重複模板變形。經過分析迭代來揭示哪些元素是相同幾何的複本（在平滑權重矩陣中表示為紅色塊）或共享部分相似性（在匹配模板上以綠色突出顯示）。

效果

由於模板變形類似於適合相似的元素，每個模板有助於元素相似性的檢測。作者通過合成的房子模型來說明這一點。如圖4，兩種類型的窗口顯示高度和寬度的變化。

圖4：當使用不同數量的模板時，本文顯示合成房子模型的選定模板實例（包括38個窄三角形頂部，4個寬三角形頂部，23個長拱形和23個短拱形窗口）。 對於每種情況，文中還顯示了顏色編碼的平滑度矩陣和元素之間檢測到的部分相似性（以綠色突出顯示）。

對比

由於雜訊和部分數據丟失的存在，對每個元素的獨立分析通常導致從相同基本幾何（圖5a左）導出的元素的不同模板的選擇。 即使選擇正確的模板，複製的元素也會映射到模板變形空間中的分散點。 因此，諸如k均值的標準聚類演算法並不能識別正確的元素簇（圖5b左）。 然而，通過迭代分析逐漸整合相似元素，可以揭示不同的元素集群（圖5b右）。 對於這個數據集，與通過視覺檢查的地面實況聚類相比，文中演算法的聚類實現了具有一個錯標記的元素的0.876的相互信息得分[VEB09]，高於基於獨立分析的聚類的得分（0.468）。

圖5：（a）對於一組元素的單獨模板擬合從而選擇五個不同的模板，而文中的演算法則將元素分配到相同模板的五個不同實例。 （b）給定模板選擇，使用通過個體擬合獲得的變形參數來觀察低維度變形空間中的每個元素（複製的元素以相同的顏色示出）。 由k均值（k = 5）演算法生成的簇由不同的符號指示。

結論

本文通過使用可變形模板模型來發現圖片元素之間的相似性。通過模板匹配和變形分析識別每個元素的最佳擬合，並檢測了這些實例的變形。本文採用了半自動方法來識別建築物的元素，而自動檢測建築元素也將會是未來的發展趨勢。

推薦文章：

目標檢測相關的資源列表

2012-2016引用最多的Top100深度學習論文列表

論文|反饋網路

CVPR 2017論文：基於網格的運動統計，用於快速、超魯棒的特徵匹配