武漢大學(xué)和上海交通大學(xué)近日聯(lián)合發(fā)布了首篇圖像匹配大領(lǐng)域綜述：《Image Matching from Handcrafted to Deep Features: A Survey》，引用文獻(xiàn)500+，涵蓋特征匹配、圖匹配、點(diǎn)集配準(zhǔn)等8個(gè)子領(lǐng)域，是一篇非常全面的大框架圖像匹配綜述。論文現(xiàn)已被IJCV2020接收。

論文鏈接：
https://link.springer.com/article/10.1007/s11263-020-01359-2本文涵蓋特征提?。╢eature detection）、特征描述（feature description）、特征匹配（feature matching）、圖像配準(zhǔn)（image registration）、立體匹配（stereo matching）、點(diǎn)集或點(diǎn)云配準(zhǔn)（point set or point cloud registration）、圖匹配（graph matching）、誤配剔除與魯棒估計(jì)（mismatch removal，如RANSAC系列）等相關(guān)子領(lǐng)域。該綜述著重介紹了近二十年來圖像匹配領(lǐng)域較為經(jīng)典的方法，以及近年來基于深度學(xué)習(xí)的方法。同時(shí)在圖像匹配大框架下分析了各子領(lǐng)域扮演的角色以及他們之間的聯(lián)系，這亦是該綜述的主要特色。此外，相關(guān)典型應(yīng)用和實(shí)驗(yàn)對比在文中也有所涉及。下面就圖像匹配中應(yīng)用極為廣泛的特征匹配進(jìn)行簡單介紹，包括問題定義分類、研究背景與意義、研究現(xiàn)狀及發(fā)展趨勢。更多細(xì)節(jié)可查看原論文。內(nèi)容整理自作者的知乎專欄：https://zhuanlan.zhihu.com/p/112071397https://zhuanlan.zhihu.com/p/112082541

一、問題定義及分類

圖像匹配 [1–6]（Image Matching）旨在將兩幅圖像中具有相同/相似屬性的內(nèi)容或結(jié)構(gòu)進(jìn)行像素上的識別與對齊。一般而言，待匹配的圖像通常取自相同或相似的場景或目標(biāo)，或者具有相同形狀或語義信息的其他類型圖像對，從而具有一定的可匹配性。從定義出發(fā)，圖像匹配主要包含匹配目標(biāo)和匹配準(zhǔn)則兩個(gè)部分，即以什么信息為目標(biāo)載體和以何種規(guī)則或策略進(jìn)行匹配。最直接的匹配目標(biāo)便是整張圖像或以截取的圖像塊（Image Patch），一般被稱為基于區(qū)域 （Area-Based）的方法，其主要分為兩種：i）直接根據(jù)圖像或圖像塊灰度信息進(jìn)行像素上的對齊，該方法主要思想是直接最小化圖像信息差異，一般包括交叉相關(guān)法（或互 相關(guān)法），相關(guān)系數(shù)度量法，互信息法等 [5,7–9]；ii）基于圖像域變換的圖像匹配，其先將圖像信息進(jìn)行域變換，然后在變換域中對圖像進(jìn)行相似性匹配，包括傅里葉變換法， 相位相關(guān)法，沃爾什變換法等 [10–12]?；趨^(qū)域的圖像匹配方法對成像條件、圖像形變（特別是要求圖像對具有極高的重疊度）以及噪聲極其敏感，同時(shí)具有較高的計(jì)算復(fù)雜度，從而限制了其應(yīng)用能力。為解決上述問題，基于特征（Feature-Based）的圖像匹配方法得到了廣泛研究 [5,13]。其首先從圖像中提取的具有物理意義的顯著結(jié)構(gòu)特征，包括特征點(diǎn)、特征線或邊緣以及具有顯著性的形態(tài)區(qū)域 [14–18]，然后對所提取的特征結(jié)構(gòu)進(jìn)行匹配并估計(jì)變換函數(shù)將其他圖像內(nèi)容進(jìn)行對齊。盡管特征的提取需要額外的算力消耗，但針對整個(gè)基于特征的匹配框架而言，由于特征可以看做整張圖像的精簡表達(dá)，減少了許多不必要的計(jì)算，同時(shí)能夠減少噪聲、畸變及其他因素對匹配性能的影響，是目前實(shí)現(xiàn)圖像匹配的主要形式，也是本文研究重點(diǎn)。對于特征而言，點(diǎn)特征通常表示圖像中具有顯著特性的關(guān)鍵點(diǎn)（Key Point）或興趣點(diǎn)（Interest Point） [19]，因而最為簡單且穩(wěn)定，同時(shí)其他特征的匹配均可轉(zhuǎn)化為基 于點(diǎn)特征來進(jìn)行，如線的端點(diǎn)、中點(diǎn)、或離散采樣形式，形態(tài)區(qū)域中心等 [18,20–22]。因 此，特征點(diǎn)匹配在圖像匹配中是一個(gè)最為基本的問題，而我們所說的特征匹配（Feature Matching）通常意義上指基于特征點(diǎn)的匹配問題，待匹配的點(diǎn)一般由圖像像素空間的坐標(biāo)點(diǎn)表示，而相應(yīng)的圖像匹配則轉(zhuǎn)化為從兩幅圖像中提取對應(yīng)的點(diǎn)集并配對的問題。本文主要研究內(nèi)容便是從特征匹配問題的本質(zhì)特性出發(fā)，結(jié)合其他領(lǐng)域技術(shù)手段，圍繞基于特征點(diǎn)的圖像匹配方法展開深入研究，克服圖像匹配問題目前面臨的諸多挑戰(zhàn)。

二、研究背景及意義

近年來，科技水平日益提高，形成了全球自動化的格局，隨之而來的人工智能技術(shù)蓬勃發(fā)展，其主要目的是令機(jī)器聯(lián)合計(jì)算機(jī)像人類一樣感知、理解與行動。視覺感知作為最主要的感知技術(shù)之一，在此次人工智能熱潮下占據(jù)著舉足輕重的地位，因而推動著計(jì)算機(jī)視覺技術(shù)迅猛發(fā)展。同時(shí)，如何理解多個(gè)視覺目標(biāo)之間的區(qū)別與聯(lián)系，并根據(jù)特定的需求對感知的信息作相應(yīng)的處理已然成為整個(gè)計(jì)算機(jī)視覺領(lǐng)域的研究熱點(diǎn)之一，而特征匹配作為其中的一個(gè)基礎(chǔ)而關(guān)鍵的過程，連接著具有相同或相似屬性的兩個(gè)圖像目標(biāo)，是低層視覺通往高層視覺的紐帶，是實(shí)現(xiàn)信息識別與整合 [23–25] 以及從低維圖像恢復(fù)高維結(jié)構(gòu) [26,27] 的有效途徑。

圖像特征匹配相關(guān)應(yīng)用特征匹配的定義和任務(wù)目標(biāo)極為簡單且明確，它是一項(xiàng)底層視覺處理技術(shù)，直接對圖像本身進(jìn)行特征提取與配對，是許多具體大型視覺任務(wù)的首要步驟。據(jù)美國自動 成像協(xié)會（Automated Imaging Association）統(tǒng)計(jì)，40% 以上的視覺感知應(yīng)用依賴于圖像匹配的精度與效率，包括計(jì)算機(jī)視覺、模式識別、遙感、軍事安防以及醫(yī)學(xué)診斷等各領(lǐng)域。具體來講，根據(jù)數(shù)據(jù)獲取條件或者成像條件的差異，特征匹配問題可以劃分 為不同時(shí)間、不同視角以及不同傳感器，或者進(jìn)行模板圖像的匹配 [3,5]，并且每一類 型的圖像獲取形式都有著對應(yīng)的應(yīng)用目的：1）基于不同成像時(shí)間的特征匹配。主要是對同一場景或目標(biāo)在不同時(shí)間拍攝的圖像進(jìn)行匹配，一般用于場景的變化檢測，安防監(jiān)控與目標(biāo)跟蹤，以及醫(yī)學(xué)診斷治療中病情跟蹤等。2）基于不同視角的特征匹配。其主要目的是匹配從不同視角拍攝的同一目標(biāo)或場景的序列圖像進(jìn)行匹配，旨在從低維的圖像內(nèi)容恢復(fù)高維結(jié)構(gòu)，如恢復(fù)相機(jī)姿態(tài)并建立相機(jī)移動軌跡，目標(biāo)或場景的三維 重建，以及遙感全景影像拼接等。3）基于不同傳感器的特征匹配。鑒于不同傳感器所獲取的圖像有著各自的優(yōu)勢且包含不同的感知信息，因而對不同的圖像信息進(jìn)行整合并得到更全面的場景或目標(biāo)表示是十分必要的，而特征匹配便是將包含多源信息的圖像進(jìn)行關(guān)鍵點(diǎn)配對并估計(jì)變換函數(shù)從而將圖像進(jìn)行逐像素對齊，便于后續(xù)的信息融合，因而又稱為多源圖像特征匹配。這類匹配常用于醫(yī)學(xué)圖像分析中多模圖像匹配，安防及軍事領(lǐng)域中如紅外可見光配準(zhǔn)，遙感圖像處理中不同分辨率且包含不同光譜信息的 影像配準(zhǔn)與融合等。4）基于模板的特征匹配。這類匹配一般給定圖像模板，然后將獲取的圖像與模板進(jìn)行比較與匹配，常用于模板識別、差異檢測或內(nèi)容檢索，如基于視覺的模式識別（字符識別，車牌識別）、圖像檢索，醫(yī)學(xué)圖像分析中病情診斷，標(biāo)本分類以及遙感圖像中航空或衛(wèi)星圖像在已知的其他地理信息地圖中的匹配與定位等。由此可見，特征匹配作為一項(xiàng)基礎(chǔ)而關(guān)鍵的技術(shù)在諸多領(lǐng)域有著重要地位，因而對其展開深入研究有著重要實(shí)際應(yīng)用價(jià)值。此外，作為許多高層視覺任務(wù)的底層輸入，基于特征點(diǎn)的圖像匹配問題也面臨著多方面的挑戰(zhàn)，其中包括準(zhǔn)確性、魯棒性（普適性）和高效性。首先，特征匹配精度在許多基于匹配的精準(zhǔn)估計(jì)應(yīng)用上有著極高的要求，匹配誤差會保留在后續(xù)處理環(huán)節(jié)中并逐漸累積從而嚴(yán)重制約最終視覺任務(wù)的有效實(shí)施。例如 根據(jù)特征點(diǎn)匹配結(jié)果求解相機(jī)運(yùn)動參數(shù)從而恢復(fù)高維結(jié)構(gòu)（Structure From Motion， SFM）的任務(wù), 錯(cuò)誤的匹配將產(chǎn)生相機(jī)姿態(tài)的錯(cuò)誤估計(jì)，使得類似于三維重建 [27] 和同 步定位與建圖 [28,29]（Simultaneous Localization and Mapping，SLAM）等任務(wù)的結(jié)果 嚴(yán)重偏離于真實(shí)情形，同時(shí)圖像融合、圖像拼接和變化檢測等 [23,25,30] 任務(wù)同樣嚴(yán)重依賴于圖像配準(zhǔn)的結(jié)果。精度問題通常來自于兩個(gè)方面——特征提取精度和特征匹配精度。特征點(diǎn)匹配一般需要對從圖像中提取出來的關(guān)鍵點(diǎn)進(jìn)行定位，即以像素坐標(biāo)的形式表示，通常該坐標(biāo)要精確到亞像素級且兩個(gè)待匹配點(diǎn)集應(yīng)具有較高的重復(fù)率，保 證所檢測的特征點(diǎn)是真正意義上可匹配的 [13]；特征匹配精度則表現(xiàn)為所配對的兩個(gè)特征點(diǎn)在真實(shí)空間中應(yīng)當(dāng)屬于精確的同名位置，或者具有相同的語義特征，同時(shí)匹配結(jié)果中需要保證盡可能多的正確匹配以及盡可能少的錯(cuò)誤匹配。其次，設(shè)計(jì)一種魯棒的特征匹配方法以滿足多方面的需求是十分必要的。待匹配圖像通常來自不同時(shí)間、不同視角和不同傳感器，成像條件多樣性不可避免地造成了圖像的匹配難度，況且圖像本身的局部形變或畸變，以及圖像之間的復(fù)雜變換等因素同樣對特征匹配問題造成了嚴(yán)重阻礙。除此之外，如何減少因噪聲、畸變、重復(fù)圖像內(nèi)容以及遮擋等問題造成的錯(cuò)誤匹配也是特征匹配中亟需解決的問題。另一方面，為了滿足大規(guī)模以及具有實(shí)時(shí)性要求的視覺任務(wù)，特征匹配方法應(yīng)當(dāng)滿足較少的時(shí)間和空間消耗。然而特征點(diǎn)的匹 配問題本質(zhì)上是一個(gè)復(fù)雜組合優(yōu)化難題 [31]，為了將 N 個(gè)特征點(diǎn)與另外 N 個(gè)特征點(diǎn)對齊，盡管這兩組點(diǎn)是完全可匹配的，同樣也需要 N! 種排列組合，況且離群點(diǎn)和噪聲的引入將大大增加問題的求解難度，因而在建模求解過程中，如何減少解的搜索空間，降低問題的計(jì)算復(fù)雜度也是特征匹配的重要難題。綜上所述，基于特征的圖像匹配技術(shù)存在多方面的難題，有待進(jìn)一步深入的研究，以滿足眾多視覺任務(wù)的應(yīng)用需求，因而開展特征匹配相關(guān)的課題具有重要的理論研究與實(shí)際應(yīng)用價(jià)值。

三、特征匹配研究現(xiàn)狀

在進(jìn)行特征匹配之前，我們首先需要從兩幅圖像中提取顯著并且具有可區(qū)分性和可匹配性的點(diǎn)結(jié)構(gòu)。常見的點(diǎn)結(jié)構(gòu)一般為圖像內(nèi)容中的角點(diǎn)、交叉點(diǎn)、閉合區(qū)域中心點(diǎn)等具有一定物理結(jié)構(gòu)的點(diǎn)，而提取點(diǎn)結(jié)構(gòu)的一般思想為構(gòu)建能夠區(qū)分其他圖像結(jié)構(gòu)的響應(yīng)函數(shù) [15,32]（Response Function）或者從特征線或輪廓中進(jìn)行稀疏采樣?[21]。為此，Morevec [19]于 1977 年首次提出了“興趣點(diǎn)”的概念，并介紹了一種基于局部像素灰度差異的特征點(diǎn)檢測方法。然而該方法存在方向、尺度、仿射和噪聲上的敏感性，以及較大的時(shí)間需求。為此，大量研究者針對該問題提出了一系列的改進(jìn)措施，其中著名 的 Harris [14] 角點(diǎn)檢測器便是運(yùn)用二階矩或自相關(guān)矩陣來加速局部極值搜索并且保證方向的不變性，為了進(jìn)一步減少導(dǎo)數(shù)的計(jì)算，一種基于局部區(qū)域像素灰度比較的快速特征提取方法被廣泛應(yīng)用于具有實(shí)時(shí)要求的視覺任務(wù)中，其中包括 SUSAN 算子 [32]， 以及采取不同像素比較方法和比較范圍的 FAST [16] 及其改進(jìn)形式如：FAST-ER [33]、 AGAST[34] 等，同時(shí)還包括在實(shí)時(shí)視覺任務(wù)中應(yīng)用極為廣泛的 ORB 特征 [28,35]?；谙袼乇容^的特征提取方法也稱為二值特征，通常具有極高的提取效率并具有一定的方向不變性以及所提取的特征點(diǎn)具有較高的重復(fù)率，對后續(xù)的匹配具有重要意義，然而這類方法受尺度和仿射變換的影響較大。針對上述問題，帶有尺度信息的斑點(diǎn)特征成為特征提取的另一種形式，其最早是由Lindeberg 等人[36] 提出的高斯拉普拉斯（Laplace of Gaussian，LoG）函數(shù)響應(yīng)來實(shí)現(xiàn)，并從中提出了尺度空間理論，其利用高斯響應(yīng)函數(shù)的圓對稱性和對局部團(tuán)結(jié)構(gòu)的極值響應(yīng)特性以及對噪聲抑制能力，通過不同高斯標(biāo)準(zhǔn)差實(shí)現(xiàn)在尺度空間上的極值搜索，從而提取對尺度、方向和噪聲魯棒的特征點(diǎn)并得到相應(yīng)的尺度信息。為了避免大量的計(jì)算，D.Lowe 等人 [37,38] 介紹了一種高斯差分（Difference-of-Gaussian，DoG） 法來近似 LoG 的計(jì)算，并提出了著名的 SIFT 特征描述子。基于相同的思想，Bay 等 人 [39] 在 Hessian 矩陣的基礎(chǔ)上結(jié)合箱式濾波以及圖像積分對梯度進(jìn)行快速計(jì)算，提出了SURF 算子，極大程度地提升了斑點(diǎn)特征的檢測速度。此外，許多基于 SIFT 和 SURF 的改進(jìn)方法也相繼被提出，其中包括減少計(jì)算量、提升仿射魯棒性等 [40–43]。為滿足精確的匹配要求，所提取的特征通常需要精確的位置信息并保證兩個(gè)點(diǎn)集具有較高的可重復(fù)性和可匹配性。因此，大多特征提取方法中均會采用非極大值抑制（NMS）來提升局部特征點(diǎn)的顯著性和穩(wěn)定性，并且通過像素空間的插值方法估計(jì)特征點(diǎn)在亞像素空間的精確極值位置，具體的特征提取相關(guān)綜述請參考 [5,13,44–47]。一旦兩個(gè)可匹配的點(diǎn)集提取完成，圖像匹配任務(wù)便轉(zhuǎn)化為對兩個(gè)特征點(diǎn)集進(jìn)行配對。對此，目前已涌現(xiàn)出了許多開創(chuàng)性的工作及其后續(xù)的改進(jìn)方案，主要從特征匹配的本質(zhì)屬性入手，從不同角度對特征匹配進(jìn)行定義與假設(shè)，并結(jié)合相關(guān)技術(shù)手段對問題建模與求解。根據(jù)現(xiàn)有文獻(xiàn)以及相關(guān)研究成果，特征匹配問題主要從直接和間接求解兩個(gè)思路進(jìn)行。直接匹配的思想主要是將特征匹配問題抽離為兩個(gè)點(diǎn)集對應(yīng)的問題，直接從中估計(jì)正確的點(diǎn)點(diǎn)對應(yīng)關(guān)系，而間接匹配一般先通過特征點(diǎn)的局部描述子的相 似程度建立初步的對應(yīng)關(guān)系，然后根據(jù)幾何約束剔除誤匹配。此外，由于深度學(xué)習(xí) [48] （Deep Learning，DL）技術(shù)在深層特征層面強(qiáng)大的學(xué)習(xí)與表達(dá)能力，基于深度卷積網(wǎng) 絡(luò)的特征匹配技術(shù)也得到了廣泛關(guān)注 [4,49,50]，為解決圖像匹配問題提供了一個(gè)新的方向。本文將對上述解決特征匹配的技術(shù)路線中主要方法進(jìn)行分析總結(jié)。

• 3.1 直接匹配策略

前面我們提到，直接匹配主要是將特征匹配問題抽離為兩個(gè)點(diǎn)集的對應(yīng)問題，也 稱為純點(diǎn)集匹配問題。首先我們假設(shè)待匹配的兩個(gè)特征點(diǎn)集為??和??, 這里??分別表示不超過 M和N的自然數(shù)，點(diǎn)集?，?分別稱為模板點(diǎn)集 和目標(biāo)點(diǎn)集。匹配的目的即是求解一個(gè)指派矩陣??, 其中??代表??和??的對應(yīng)關(guān)系，并通過一定的約束條件以及目標(biāo)函數(shù)構(gòu)建，優(yōu)化求解得到指派矩陣。一般而言，以??來表示??與??匹配與否，即??代表兩者屬于匹配關(guān)系， 反之則不匹配；較為松弛的方法便是令??，即指派變量屬于 0 到 1 之間的連 續(xù)概率值，用以表征和之間的匹配程度?；谶@一策略的特征匹配方法主要有基于對應(yīng)矩陣估計(jì)和基于圖模型的特征匹配兩種。i) 基于對應(yīng)矩陣估計(jì)的特征匹配算法。對應(yīng)矩陣的估計(jì)需要結(jié)合變換函數(shù)的建模和參數(shù)估計(jì)而同時(shí)進(jìn)行，一般用于點(diǎn)集配準(zhǔn)問題。這類算法的目標(biāo)通常是通過變換模型與對應(yīng)矩陣的估計(jì)，將目標(biāo)點(diǎn)集變換并映射到模板點(diǎn)集中，使得變換后兩個(gè)點(diǎn)集中屬于配對的點(diǎn)能夠盡可能重合，因此其最小化目標(biāo)函數(shù)一般包含目標(biāo)點(diǎn)集變換后與模板點(diǎn)集的空間距離和指派矩陣的組合形式構(gòu)成經(jīng)驗(yàn)誤差項(xiàng)，并且對應(yīng)矩陣的相關(guān)約束條件和變換函數(shù)的平滑性、復(fù)雜性等將構(gòu)成額外的懲罰項(xiàng)。為了實(shí)現(xiàn)目標(biāo)函數(shù)的優(yōu)化與求解，常用的方法是兩個(gè)待求解變量在反復(fù)迭代更新中逐漸逼近其最優(yōu)形式。因此，變換模型的選擇也成為了基于對應(yīng)矩陣估計(jì)的特征匹配方法的重點(diǎn)。對于靜態(tài)場景圖像而言，圖像對或待匹配的兩個(gè)點(diǎn)集一般滿足多視圖幾何變換，即極線幾何或單應(yīng)等約束條件，其通常由一個(gè) 3×3 的矩陣表示，矩陣中不同元素結(jié)構(gòu)和矩陣的自由度代表 著平移、尺度、旋轉(zhuǎn)、仿射等基礎(chǔ)變換，結(jié)合點(diǎn)集的齊坐標(biāo)形式，可以反映點(diǎn)集間的這種靜態(tài)幾何變換的度量與建模。然而圖像中一般存在局部形變、成像畸變或者動態(tài)目標(biāo)等非剛性變換，此時(shí)靜態(tài)場景中的全局幾何形變模型將無法適用，常用的策略則是 采用插值理論中的幾何形變模型，如徑向基函數(shù)（Radial Basis Function, RBF），其中薄板樣條（Thin-PlateSplines，TPS）和高斯徑向基函數(shù)在非剛性點(diǎn)集配準(zhǔn)中得到了廣 泛應(yīng)用 [51,52]。例如，Chui[53] 等人提出了一種基于 TPS 估計(jì)的魯棒點(diǎn)集匹配（Robust PointMatching，RPM）框架，并且為了提升對數(shù)據(jù)退化的魯棒性，Myronenko 等人 [54] 基于高斯徑向基函數(shù)提出了一致性點(diǎn)漂移算法（Coherent Point Drift，CPD）?；趯?yīng)矩陣估計(jì)的特征匹配算法框架能夠在剛性和非剛性匹配中均取得不錯(cuò)效果，但是當(dāng)點(diǎn)集中存在大量離群點(diǎn)或數(shù)據(jù)退化嚴(yán)重時(shí)，算法性能將大大降低，甚至失效。此外，該模型框架本身屬于一個(gè)復(fù)雜組合優(yōu)化問題，其求解空間極其復(fù)雜，在迭代估計(jì)的過程中需要大量的時(shí)間消耗。ii) 基于圖模型的特征匹配算法。圖模型的構(gòu)建為特征匹配問題提供了一個(gè)新穎的思路，將待匹配特征點(diǎn)看作圖的頂點(diǎn)，點(diǎn)點(diǎn)之間連接成邊，便可以通過圖論的相關(guān)理 論對特征點(diǎn)匹配問題建模與求解，因此也稱為圖匹配（Graph Matching）[55,56]。圖匹配方法主要分為精確圖匹配和非精確圖匹配，精確方法主要將圖匹配看作一個(gè)子圖同構(gòu)問題，嚴(yán)格要求圖結(jié)構(gòu)的相似性，從而導(dǎo)致其求解難度以及解決實(shí)際問題的不適用性，而非精準(zhǔn)匹配弱化了圖結(jié)構(gòu)的相似度量，在實(shí)際問題中更加靈活，目前圖匹配的研究重點(diǎn)主要圍繞非精確匹配進(jìn)行。另一方面，圖匹配的本質(zhì)目標(biāo)是從兩個(gè)點(diǎn)集中搜索具有相似圖結(jié)構(gòu)的最大子集，其關(guān)鍵步驟主要有圖的構(gòu)建和圖模型優(yōu)化求解。圖的構(gòu)建主要在于邊的定義以及鄰接矩陣（Adjacent Matrix）和關(guān)聯(lián)矩陣（Affinity Matrix）的構(gòu)建，低階邊的定義通常只包含兩點(diǎn)之間的直接距離，而高階邊則由三個(gè)或三個(gè)以 上的頂點(diǎn)來定義，同時(shí)鄰接矩陣有全連接形式以及 ?? 近鄰、K-近鄰和三角連接等稀疏形式兩種類型，關(guān)聯(lián)矩陣則用以表征圖結(jié)構(gòu)之間的親和性，主要包含頂點(diǎn)親和（一階親和性）和邊親和（二階親和性），不同構(gòu)圖形式將影響模型的求解效率和精度。另外基于圖理論的特征匹配模型的研究重點(diǎn)一般是優(yōu)化方法的探索 [57,58]，主要將圖匹配問題看做一個(gè)二次分配的問題 [56,59]（Quadratic Assignment Problem，QAP），現(xiàn)有的求解形式通常是將模型轉(zhuǎn)化為一個(gè)能量最小化問題，主要分為基于梯度（Gradient Based）的優(yōu)化方式以及通過拉普拉斯矩陣（Graph Laplacians）在主特征的基礎(chǔ)上進(jìn)行譜方法（Spectral Based）的求解，例如譜匹配（Spectral Matching，SM） [60] 和移動圖匹配 [61]（Graph Shift，GS）、蒙特卡羅法 [62]（Monte Carlo）、隨機(jī)行走法 [63] （Random Walk）以及基于聚類的匹配方法 [64] 等?？偠灾?，基于圖理論的特征點(diǎn)匹配方法能夠從全局結(jié)合局部結(jié)構(gòu)的相似性對特征點(diǎn)集進(jìn)行結(jié)構(gòu)劃分并配對，是實(shí)現(xiàn)特征匹配的一個(gè)具有較強(qiáng)理論研究意義的途徑，然而由于其 QAP 和 NPC 屬性，因而具有較高的計(jì)算復(fù)雜度，同時(shí)噪聲和離群點(diǎn)的影響會直接制約圖匹配算法的有效性。因此，研究圖匹配算法的快速優(yōu)化求解以及針對噪聲和離群點(diǎn)的魯棒建模來提高匹配精度與效率是目前圖匹配的研究重點(diǎn)。

• 3.2 間接匹配策略

間接匹配策略一般分為兩個(gè)階段，第一個(gè)階段先根據(jù)待匹配的特征點(diǎn)構(gòu)建具有特定屬性的描述子（Feature Descriptor），從而為每個(gè)特征點(diǎn)賦予各自的特征向量，然后根據(jù)描述子的相似程度建立粗略的對應(yīng)關(guān)系。常用的特征描述方法主要分為基于局部圖像梯度統(tǒng)計(jì)的浮點(diǎn)型描述子和基于像素灰度比較的二值型描述子，前者極具代表性的便是 SIFT 描述子 [37,38]，其通過對局部像素進(jìn)行網(wǎng)格劃分并統(tǒng)計(jì) 8 個(gè)方向上的梯度 同時(shí)確定梯度主方向，隨后將其排列為一個(gè)能夠描述該特征點(diǎn)的高維向量。SIFT 能夠取得較為滿意的匹配效果，并且對光照、方向、尺度以及圖像質(zhì)量具有一定的魯棒性。為了進(jìn)一步提升 SIFT 的實(shí)現(xiàn)速度以及準(zhǔn)確性，SURF 中引入了 Haar 響應(yīng)策略，并以高斯函數(shù)進(jìn)行局部加權(quán)，統(tǒng)計(jì)扇形區(qū)域?qū)?shù)方向進(jìn)行特征描述。Yan 等人 [42] 提出了 一種基于特征降維的改進(jìn)形式 PCA-SIFT，以及其他改進(jìn)如：C-SIFT [41]、ASIFT [40]、 DSP-SIFT [65] 等?；谙袼乇容^的二值特征描述方法，主要包含不同的采樣策略和采樣范圍，比如：Michael 等人 [66] 于 2010 年在特征點(diǎn)局部矩形區(qū)域內(nèi)針對不同的采樣形式進(jìn)行了對比測試，提出了一種 BRIEF 二值描述方法；次年，Stefan 等人 [67] 提出了一種基于變尺度同心圓采樣形式的特征描述方法 BRISK，并且隨后的 Alexandre 等人 [68] 提出了一種基于視網(wǎng)膜采樣的二進(jìn)制特征描述子 FREAk。不同特征提取和不同描述方法的相互組合可以得到不同的初始匹配構(gòu)建效果，如 ORB 特征在FAST的基礎(chǔ)上根據(jù) Harris 響應(yīng)進(jìn)行前 N 個(gè)可靠特征挑選，隨后采取灰度質(zhì)心法確定其主方向， 并利用 BRIEF 特征描述方法，結(jié)合學(xué)習(xí)的策略確定二進(jìn)制編碼方式，是目前最為快速的建立初始匹配方法之一?？傊敌兔枋鲎幼罱K通過漢明距離對描述子的相似度進(jìn)行度量，相對而言具有較高的實(shí)現(xiàn)速度，而浮點(diǎn)型描述子則一般采用歐式距離進(jìn)行相似度度量，具有較高穩(wěn)定性。針對特征描述的相關(guān)綜述及其特征提取描述和匹配性能對比，同樣可以參考 [13,44–47]。此外，對于已經(jīng)存在的兩個(gè)具有物理形狀的待匹配的點(diǎn)集而言，比如從二維形狀中離散而來的特征點(diǎn)集，該點(diǎn)集一般會脫離圖像本身，因而基于圖像信息的描述方法將不再適用，此時(shí)可以通過形狀上下文 [21]（ShapeContext，SC）來構(gòu)建描述子，或者三維情況則通過自旋圖 [69]、以及二維描述子的三維改進(jìn)形式 [38,70]（MeshDOG/MeshHOG）進(jìn)行特征描述并建立初始匹配。不管怎樣，這種粗略的對應(yīng)由于僅利用了局部信息，同時(shí)噪聲、離群點(diǎn)、遮擋和重復(fù)內(nèi)容等原因，造成初始匹配中會存在大量的錯(cuò)誤匹配關(guān)系，比如現(xiàn)有的基于描述子的特征匹配方法一般錯(cuò)誤匹配比率高達(dá) 50% 以上 [17,45], 而如果設(shè)定更嚴(yán)格的閾值條件，正確比率會有很大提升，但同時(shí)也會犧牲大量的正確匹配。因此，在下一步中，則需要根據(jù)所建立的初始匹配的空間幾何約束將誤匹配剔除，同時(shí)保留盡可能多的正確匹配。間接匹配策略將特征匹配問題轉(zhuǎn)化為一個(gè)從初始匹配集??剔除誤匹配的問題，其中 N 表示具有 N 對已建立好初始對應(yīng)關(guān)系的匹配對。一類經(jīng)典的剔除 \誤匹配同時(shí)估計(jì)參數(shù)模型的方法便是隨機(jī)采樣一致性 [71]（RANdom SAmple Consensus，RANSAC），以及后續(xù)的改進(jìn)形式如 MLESAC [72]、PROSAC [73]、SCRAMSAC [74]、USAC [75] 等，統(tǒng)稱為基于重采樣的方法。這類方法旨在初始匹配中通過反復(fù)地采樣估計(jì)匹配點(diǎn)集間預(yù)定義的變換模型，來尋找滿足其估計(jì)的模型的最大內(nèi)點(diǎn)集作為正確的匹配對。該方法嚴(yán)重依賴于采樣的準(zhǔn)確性，顯然當(dāng)初始匹配中存在大量離群點(diǎn)時(shí)，所需采樣次數(shù)顯著提升，從而使得該方法的效率大大降低，同時(shí)變換模型一般無法預(yù)先定義，甚至一些非剛性情況無法建模，從而導(dǎo)致這類方法不再適用。另一類用于解決非剛性變換圖像匹配的方法則是基于非參數(shù)插值或擬合的方法，其主要基于先驗(yàn)條件插值或回歸學(xué)習(xí)出定義的非參數(shù)函數(shù)，將一幅圖像中的特征點(diǎn)映射到另一幅圖像中，然后通過核查初始點(diǎn)匹配集中每個(gè)匹配對是否與估計(jì)出的對應(yīng)函數(shù)一致來剔除 錯(cuò)誤匹配。例如通過魯棒估計(jì)對應(yīng)函數(shù)用于離群點(diǎn)剔除的 ICF 算法 [76]，以及利用非剛性變換模型在再生核希爾伯特空間 (Reproducing kernel Hilbert spaces, RKHS) 中的 泛函表達(dá)形式及其稀疏近似形式，結(jié)合高斯混合模型 (Gaussian mixed model, GMM) 與正則化理論在這一匹配框架中取得了卓越的成效 [77–86]，較為代表性的算法有基于向量場一致性點(diǎn)集匹配算法 VFC[81]、基于流形正則化點(diǎn)集匹配算法 MR-RPM [87]、基于局部線性遷移匹配算法 LLT[88] 等。該類方法在離群點(diǎn)較多或者點(diǎn)集中存在獨(dú)立的運(yùn)動結(jié)構(gòu)以及其他具有極為復(fù)雜的變換時(shí)匹配精度會急劇下降。此外，一些松弛的方法，例如在建立初始匹配后利用圖匹配相關(guān)的約束條件，通過局部結(jié)構(gòu)一致性以及分段一 致性的假設(shè)，對正確匹配進(jìn)行魯棒估計(jì)。比如基于局部保留的特征匹配方法 LPM [89]、 GLPM [90]，基于網(wǎng)格劃分運(yùn)動一致性算法 [91]（GMS），基于分層運(yùn)動一致性的特征匹配方法 [92,93] 等。由于建立初始匹配通過描述子的相似度量構(gòu)建，然后根據(jù)幾何約束剔除誤匹配，相比于直接匹配策略，這類方法能夠使特征匹配問題得到高效解決。然而，如何快速建立包含正確對應(yīng)的初始匹配，對匹配問題定義以及挖掘正誤匹配之間的分布差異和特點(diǎn)，設(shè)計(jì)一種快速精確的誤配剔除策略也是許多學(xué)者關(guān)注的重點(diǎn)。

• 3.3深度學(xué)習(xí)策略

目前，深度學(xué)習(xí)方法因其對深層特征有著優(yōu)越的學(xué)習(xí)和表達(dá)能力，以火爆的方式應(yīng)用于計(jì)算機(jī)視覺的各個(gè)領(lǐng)域，其同樣在圖像匹配問題上嶄露頭角并取得了初步成效。深度學(xué)習(xí)在圖像匹配中最合理的應(yīng)用便是直接從包含相同或相似結(jié)構(gòu)內(nèi)容的圖像對中學(xué)習(xí)到像素級別的匹配關(guān)系，其主要形式有以下幾種：1）以深度學(xué)習(xí)方法解決傳統(tǒng)類似于 SIFT [37,38] 建立初始匹配中的一個(gè)或多個(gè)環(huán)節(jié)，又或者直接設(shè)計(jì)一個(gè)端到端的匹配網(wǎng)絡(luò)，例如學(xué)習(xí)從圖像中檢測更精確可靠的特征點(diǎn)集、學(xué)習(xí)每個(gè)特征點(diǎn)的主要 方向或主要尺度及其更具有區(qū)分性和可匹配能力的特征描述子 [94–96]，一些代表方法如 LIFT [17]、NCN [50]、LF-Net [97]、SuperPoint [98] 等；又或者學(xué)習(xí)描述子之間更可靠的相似性度量準(zhǔn)則等 [99,100]。這一系列的策略在某些方面已經(jīng)證明了其相對于傳統(tǒng)方 法的優(yōu)越性 [101,102]，然而其中同樣存在大量的錯(cuò)誤匹配，依舊需要誤匹配剔除策略進(jìn) 行后處理。2）在雙目立體匹配（Stereo Matching）中，直接從圖像對中學(xué)習(xí)得到深度 圖 [103,104]，這種方法已在公共數(shù)據(jù)集 KITTI [105] 和 Middlebury [106] 中取得了統(tǒng)治性的結(jié)果，然而其一般依賴于兩張圖像具有較高的重合度并且經(jīng)過校正與對齊，因而具有 一定的局限性。3）基于深度學(xué)習(xí)的圖像塊匹配 [99,107,108]（Patch Matching）涌現(xiàn)出了大量的研究成果，其主要通過深度學(xué)習(xí)方法獲取圖像塊之間的深層特征，并度量特征之間相似性來建立對應(yīng)關(guān)系，這類方法一般用于提取好的特征點(diǎn)的描述子構(gòu)建、圖像 檢索、寬基線立體匹配 [103]（Wide-Baseline Stereo Matching）以及圖像配準(zhǔn) [99,109,110] 等方面。深度學(xué)習(xí)在匹配中的另外的一種應(yīng)用便是從兩個(gè)點(diǎn)集中學(xué)習(xí)其局部和全局特征并建立可靠的點(diǎn)對應(yīng)關(guān)系。由于三維點(diǎn)云數(shù)據(jù)的稠密特性是的其具有類似于圖像的紋理細(xì)節(jié)信息，可以方便地通過深度卷積方式進(jìn)行學(xué)習(xí)，因而應(yīng)用較廣 [111,112]。然而三維點(diǎn)云中的深度學(xué)習(xí)策略，并不適用于稀疏的特征點(diǎn)集匹配任務(wù)，為了解決這一問題，通過深度學(xué)習(xí)方法學(xué)習(xí)點(diǎn)集之間的幾何拓?fù)浣Y(jié)構(gòu)也成為當(dāng)前研究熱點(diǎn)之一。其主要目的是學(xué)習(xí)兩個(gè)圖結(jié)構(gòu)之間的相似性，或者通過局部鄰域結(jié)構(gòu)一致性學(xué)習(xí)來建立點(diǎn)集之間的配對關(guān)系 [49,50]，又或者通過點(diǎn)集間的幾何變換模型進(jìn)行約束，即在建立匹配的過程中同時(shí)學(xué)習(xí)變換模型的參數(shù) [113,114]，如基于學(xué)習(xí)的可靠匹配搜索 [113]（Learning to Find Good Correspondences，LFGC），其旨在從稀疏初始匹配集結(jié)合相機(jī)本征矩陣學(xué)習(xí)一個(gè)多層深度感知機(jī)，結(jié)合參數(shù)幾何變換模型構(gòu)建損失函數(shù)，實(shí)現(xiàn)模型估計(jì)同時(shí)剔除誤 匹配，或者基于局部結(jié)構(gòu)一致性的圖學(xué)習(xí)網(wǎng)絡(luò)來挖掘潛在的正確對應(yīng)關(guān)系 [50,115]。除此之外，國內(nèi)學(xué)者針對特征匹配問題也進(jìn)行了較為系統(tǒng)的研究，例如國防科學(xué)技術(shù)大學(xué)趙鍵 [116] 和復(fù)旦大學(xué)宋智禮[2] 在他們各自的博士課題中分別針對點(diǎn)模式的匹配問題和圖像配準(zhǔn)技術(shù)及其應(yīng)用進(jìn)行了專門研究，華中科技大學(xué)馬佳義 [3] 的博士課題研究了基于非參數(shù)模型的點(diǎn)集匹配模型框架，并提出了一系列的基于正則化理論的非參數(shù)建模和快速求解形式，哈爾濱工業(yè)大學(xué)于偉 [4] 的博士課題則研究了基于深度神經(jīng)網(wǎng)絡(luò)特征的圖像匹配方法，主要解決深度學(xué)習(xí)框架下的深層特征表達(dá)與語義匹配問題，此外華中科技大學(xué)柳成蔭 [117] 在其博士課題中，針對不同領(lǐng)域的應(yīng)用需求，從多模與多視角非剛性圖像配準(zhǔn)問題展開了專門的研究。綜上所述，特征匹配方法的研究根據(jù)問題的定義以及求解策略有著大量的研究成果，然而由于應(yīng)用場景的復(fù)雜性，造成目前的特征匹配方法存在多方面的局限，主要包括處理速度，匹配精度以及針對噪聲和非剛性形變的魯棒性。因此，本文的主旨便是對特征匹配問題進(jìn)行系統(tǒng)與深入的研究，從不同的角度定義特征匹配問題，并采用有效的技術(shù)解決當(dāng)前匹配算法的應(yīng)用局限性。

四、特征匹配發(fā)展趨勢

特征匹配問題由來已久，理論上的突破使得現(xiàn)有的方法具有一定的實(shí)際應(yīng)用能力，然而面對諸多方面的應(yīng)用需求，以及特征匹配問題本身的復(fù)雜特性，其依然是一個(gè)具有理論研究意義和實(shí)際應(yīng)用價(jià)值的開放性話題，因此需要進(jìn)一步地深入研究，同時(shí)深度學(xué)習(xí)技術(shù)的強(qiáng)大能力也使得特征匹配問題面臨著進(jìn)一步的突破。接下來，綜合當(dāng)前研究現(xiàn)狀以及相關(guān)難題，特征匹配技術(shù)的發(fā)展趨勢主要涉及以下幾個(gè)方面：

• 傳統(tǒng)方法的進(jìn)一步推進(jìn)

根據(jù)圖像匹配的概念可知，圖像匹配技術(shù)可以應(yīng)用于任何含有對相似或相同結(jié)構(gòu)及內(nèi)容信息的識別、檢測、整合與應(yīng)用的視覺任務(wù)中，盡管現(xiàn)階段深度學(xué)習(xí)方法在許多視覺任務(wù)中逐漸取代了傳統(tǒng)的基于圖像匹配的思路，并取得了突出的成果，但圖像匹配因其高魯棒性、可擴(kuò)展性、可解釋性依舊是眾多領(lǐng)域的主流方法。前面提到，匹配誤差會保留在后續(xù)處理環(huán)節(jié)中并逐漸累積從而嚴(yán)重制約最終視覺任務(wù)的有效實(shí)施，錯(cuò)誤的匹配將產(chǎn)生某些精確估計(jì)的錯(cuò)誤計(jì)算會使得一些視覺任務(wù)結(jié)果嚴(yán)重偏離于真實(shí)情形。因而設(shè)計(jì)一種高精度和高效率的匹配方法，以滿足當(dāng)前具有實(shí)性或大規(guī)模的實(shí)際應(yīng)用需求，是特征匹配后續(xù)發(fā)展的主要趨勢。另外，一定程度上提升特征點(diǎn)的提取與描述能力，如提取更精確更具有重復(fù)性和可匹配能力的特征，更顯著和可區(qū)分性的特征描述子，獲取具有高內(nèi)點(diǎn)比率和內(nèi)點(diǎn)數(shù)量的初始匹配對，實(shí)現(xiàn)實(shí)時(shí)性的特征提取與匹配方法，以及研究更高效魯棒的特征點(diǎn)匹配模型及其求解形式都會為特征匹配技術(shù)在實(shí)際應(yīng)用中帶來實(shí)質(zhì)性的突破。

• 深度學(xué)習(xí)方法的引入

實(shí)現(xiàn)圖像匹配方法的多樣性，脫離傳統(tǒng)的匹配方法，基于深度學(xué)習(xí)方法的圖像匹配將會成為今后研究熱點(diǎn)之一。通過深度學(xué)習(xí)方法解決圖像匹配中特征檢測、主方向或主尺度檢測、特征描述、相似性度量與配對、誤匹配剔除、變換模型估計(jì)等傳統(tǒng)匹配步驟中的一個(gè)或多個(gè)環(huán)節(jié)，又或者直接設(shè)計(jì)一個(gè)端到端的匹配網(wǎng)絡(luò)，從而進(jìn)一步改善傳統(tǒng)圖像特征提取、特征描述以及特征匹配中存在的缺陷，比如：提取出更具有表現(xiàn)力和可精確匹配的特征結(jié)構(gòu)，或者傳統(tǒng)的特征描述方法僅基于直觀的圖像梯度或灰度信息統(tǒng)計(jì)而得到，因而需要學(xué)習(xí)一種更為深層且更具有區(qū)分力的特征描述方法，又或者基于歐氏距離的浮點(diǎn)型描述子和基于漢明距離的二值型描述子相似度度量形式存在一定的局限，從而需要學(xué)習(xí)得到一種更合理的度量形式得到更準(zhǔn)確的匹配結(jié)果。從圖像匹配抽象出來的點(diǎn)集匹配和圖匹配問題，會進(jìn)一步啟發(fā)基于圖理論的深度網(wǎng)絡(luò)的相關(guān)研究?；谙∈椟c(diǎn)集的深度學(xué)習(xí)方法目前存在著兩個(gè)方面的挑戰(zhàn)，首先是 如何將幾何數(shù)據(jù)（稀疏點(diǎn)集）建立成圖，此圖為 image 而非 graph，或者構(gòu)建能夠處理 幾何數(shù)據(jù)的網(wǎng)絡(luò)結(jié)構(gòu)。原因在于現(xiàn)有卷積神經(jīng)網(wǎng)絡(luò)主要依托于 image 而進(jìn)行，改變圖像內(nèi)容順序?qū)⒑艽蟪潭雀淖冋麖垐D像的結(jié)構(gòu)信息，對網(wǎng)絡(luò)輸出結(jié)果造成極大影響，而幾何數(shù)據(jù)本身具有無序性，即改變幾何數(shù)據(jù)的排列順序（如端點(diǎn)順序），不會影響幾何問題本身的任何屬性。同時(shí)更高維的幾何數(shù)據(jù)是幾何問題中常見的數(shù)據(jù)類型，從高維數(shù)據(jù)到低維建圖也存在嚴(yán)峻挑戰(zhàn)。其次，現(xiàn)有深度理論在模式識別中具有顯著成效。如何去尋找?guī)缀螖?shù)據(jù)的或者空間點(diǎn)的近鄰關(guān)系，判斷其相對位置，識別多點(diǎn)之間的邊、角等幾何信息，是聯(lián)合深度卷積理論解決傳統(tǒng)幾何問題的重要挑戰(zhàn)。

• 協(xié)同匹配與增量匹配

近年來，多圖像協(xié)同匹配和增量匹配相關(guān)成果初露鋒芒 [118–120]。這類匹配在聯(lián)合多張圖像匹配信息，互相監(jiān)督引導(dǎo)的概念上一定程度地提高了匹配的精度，為了滿足這一特性，傳統(tǒng)的匹配優(yōu)化模型需要進(jìn)一步地?cái)U(kuò)展，極大程度地增加了求解復(fù)雜度。盡管協(xié)同匹配與增量匹配在匹配精度和效率上難以取得合理的權(quán)衡，然而這一概念在解決多序列圖像匹配應(yīng)用方面依舊具有較大的研究價(jià)值。首先如何對協(xié)同匹配問題進(jìn)行有效建模和高效求解本身是一個(gè)極具有理論研究意義的問題，其次，這一理念契合人類視覺對多目標(biāo)信息的聯(lián)合挖掘與利用這一特性，同時(shí)多圖像協(xié)同檢測、分割、超分等視覺任務(wù)目前已取得了不錯(cuò)成效，證明這一理念是可行且有意義的。另外，以多序列圖像和增量式為基礎(chǔ)的視覺任務(wù)，如三維重建、SLAM、機(jī)器人導(dǎo)航定位等，目前依舊依賴于傳統(tǒng)的兩兩圖像對之間的單一匹配，協(xié)同匹配的引入可以簡化這些任務(wù)中的匹配環(huán)節(jié)，同時(shí)提高匹配精度。同時(shí)，多圖像的協(xié)同匹配保證了充足的數(shù)據(jù)量以及引入了更豐富的圖像間的協(xié)同信息，而傳統(tǒng)的手工方法難以挖掘其中深層且復(fù)雜的匹配信息，基于這一特性，運(yùn)用深度學(xué)習(xí)方法解決多圖像協(xié)同匹配與增量匹配則具有極為廣闊的前景。