模板匹配綜述-SSD，BBS，DDIS，CoTM，QATM

簡單看了幾篇模板匹配相關(guān)的論文，總結(jié)了一下，后期待修改

模板匹配介紹

模板匹配是計算機(jī)視覺應(yīng)用中最常用的技術(shù)之一，可以應(yīng)用在視頻跟蹤，圖像拼接，目標(biāo)檢測，字符識別和3D重建等方向上。
模板和目標(biāo)圖像的子窗口之間的相似性度量是模板匹配的核心部分。

傳統(tǒng)的模板匹配相似性度量

傳統(tǒng)的模板匹配方法通常使用平方差和（SSD，sum-of-squared-differences）或歸一化積相關(guān)（NCC，normalized cross-correlation）等來計算模板與基礎(chǔ)圖像之間的相似度得分。
在搜索圖S中，以(i,j)為左上角，取MxN大小的子圖，計算其與模板的相似度；遍歷整個搜索圖，在所有能夠取到的子圖中，找到與模板圖最相似的子圖作為最終匹配結(jié)果。

SSD

平方差和，數(shù)值越大相似度越小。

NCC

利用子圖與模板圖的灰度，通過歸一化的相關(guān)性度量公式來計算二者之間的匹配程度。

傳統(tǒng)算法評價：

優(yōu)點(diǎn)：

①思路簡單，容易理解。②運(yùn)算過程簡單，匹配精度高。

缺點(diǎn)：

①運(yùn)算量偏大。②對噪聲非常敏感。

總結(jié)：

當(dāng)模板和目標(biāo)搜索圖像之間的轉(zhuǎn)換很簡單時，這些方法效果很好。但是，當(dāng)轉(zhuǎn)換復(fù)雜或非剛性時（stretching or shrinking），這些方法的成功率會大幅下降。 另外，其他因素（例如遮擋和顏色偏移）也會對這些方法造成很大影響。
并且，這種方法測量相似性時考慮模板和目標(biāo)圖像中的候選窗口中的所有像素（特征點(diǎn)）。當(dāng)目標(biāo)背后的背景改變時，這種方法是不可取的。

BBS（Best-Buddies-Similarity）

Introduction

CVPR2015 論文地址

本質(zhì)是Best-Buddies Similarity（BBS算法）。這是一種在兩個點(diǎn)集之間的無參魯棒相似性測量，核心是計算Best-Buddies Pairs（BBPs）的數(shù)量。

Method

用傳統(tǒng)的滑動窗口方法，在模板和圖像中每個可能的窗口（模板大?。┲g同樣計算出BBS。

BBS

首先需要將每個圖像塊轉(zhuǎn)換為\mathbb{R}^u0z1t8os中的一個點(diǎn)集。為此，把圖像分成若干個的k x k圖像塊。每個圖像塊由其RGB值組成的k^{2}個矢量和中心像素相對于坐標(biāo)系的xy坐標(biāo)表示。

BBS測量了兩個點(diǎn)集P和Q之間的相似性，當(dāng)p_{i}和q_{j}互為最近鄰時，他們?yōu)橐唤MBBP（原集和目標(biāo)集中的點(diǎn)對，每個點(diǎn)都是另一個點(diǎn)的最近鄰）。

點(diǎn)集P和點(diǎn)集Q之間的BBS定義為：（d（）為距離函數(shù)）
上標(biāo)A表示像素外觀（例如RGB），上標(biāo)L表示像素位置（標(biāo)準(zhǔn)化為[0，1]的色塊內(nèi)的x，y），λ= 2

BBS隨兩點(diǎn)集的分布區(qū)別增大而減小，兩個分布相同時取得最大值。如果兩個點(diǎn)是BBP，它們很可能是從相同的分布中提取的。
BBS的主要特性為

  • 只依賴于匹配點(diǎn)（BBPs）的子集（通常很小），其余的被視為外點(diǎn)，對于大部分異常點(diǎn)具有魯棒性
  • BBS可以找出數(shù)據(jù)中的雙向匹配點(diǎn)而不需要任何先驗(yàn)知識或者潛在變形
  • BBP通過計算BBP的數(shù)量進(jìn)行排名，而不是使用實(shí)際的距離值

CONCLUSION

在存在高水平的異常值（即背景噪聲、遮擋）和目標(biāo)的非剛性變形的情況下，將模板與給定圖像匹配?？梢缘挚箯?fù)雜的幾何變形和高度異常的點(diǎn)（背景噪聲和遮擋）。
BBS可以在存在異常值的情況下可靠地匹配來自同一分布的特征，在視角變換和集合變形下依然可以進(jìn)行穩(wěn)健的模板匹配。
缺點(diǎn)是當(dāng)模板與目標(biāo)圖像相比很小時，或者離群值（遮擋對象或背景雜波）覆蓋了大多數(shù)模板時，成功率會降低。

DDIS （Deformable Diversity Similarity）

Introduction

——CVPR2017 論文地址

DDIS明確考慮了可能的模板變形，并使用了模板和搜索圖像中潛在匹配區(qū)域之間的NN特征匹配的多樣性。

采用了基于特征的BBS無參數(shù)方法。基于目標(biāo)圖像窗口和模板之間特征匹配的多樣性，它對復(fù)雜的變形，明顯的背景雜波和遮擋具有魯棒性。

Method

Diversity

我們的關(guān)鍵思想是通過最近鄰域（NN field）的兩個屬性來得到目標(biāo)和模板之間的相似性。

首先，如圖2d所示，當(dāng)目標(biāo)和模板對應(yīng)時，大多數(shù)目標(biāo)patch在模板中具有唯一的NN匹配。這意味著最近鄰域高度多樣化，指向模板中的許多不同的patch。

相反，如圖2e所示，對于任意目標(biāo)，大多數(shù)patch都沒有很好的匹配，并且NN收斂到恰好與目標(biāo)patch相似的少量模板點(diǎn)。第二，不佳匹配往往意味著較大的變形，如圖2e中的長箭頭所示。


DIS & BBP


對每個q，都有一條紅箭頭指向它的NN p，如果p q為BBP，將兩點(diǎn)之間的紅箭頭改為綠線。
DIS計算由紅色箭頭或綠線指向的藍(lán)色三角形數(shù)量。BBS計算綠線數(shù)量。
（a）P和Q的分布相似，因此，許多p是某些q的NN，并且有很多BBP。這里DIS = BBS =8。
（b）P和Q具有不同的分布。密集p中的單個q或密集q中的單個p對DIS和BBS均貢獻(xiàn)1。有時，Q和P之間存在唯一的NN匹配，而不是BBP。由于P和Q的分布不同，DIS和BBS都相對較低，因此DIS = 3和BBS = 2。

DDIS

為了整合對大變形的懲罰，對DIS進(jìn)行了兩種修改：
首先，為了獲得變形場的顯式表示，區(qū)分每個patch的外觀和位置并將它們分別對待。
其次，提出了另一種測量多樣性的方法，該方法可以考慮變形量。
令p^a表示外觀，而p^l表示patch p的位置（q同理）。我們?yōu)槊總€點(diǎn)q_j尋找基于appearance的NN^a p_i（d為距離函數(shù))


和它的的location距離由表示

定義作為為的patch q的數(shù)量，

定義DDIS：其中歸一化因子c = 1 / min {M，N}

該定義可以看作是點(diǎn)上的contribution之和。 每個點(diǎn)的貢獻(xiàn)由其隱含變形矢量的長度反向加權(quán)。

當(dāng)點(diǎn)q_j具有唯一的NN時，則κ(NN^a(q_j，P))= 1，指數(shù)達(dá)到最大值1。
當(dāng)q_j的NN被許多其他點(diǎn)共享時，則κ(NN^a(q_j，P))大，指數(shù)值低，并且q_j對相似度的總體貢獻(xiàn)低。

DDIS具有使其具有吸引力的幾個屬性：
（1）它主要依賴于具有不同NN的點(diǎn)。 共享NN的點(diǎn)的分?jǐn)?shù)對分?jǐn)?shù)的影響較小。
（2）DDIS不需要任何有關(guān)數(shù)據(jù)或其潛在變形的先驗(yàn)知識。
（3）DDIS分析NN field，而不是使用實(shí)際距離值。

CONCLUSION

DDIS與BBS極為相似，他們都依賴于兩組點(diǎn)之間的NN匹配。 但是有兩個主要區(qū)別：
（i）兩組之間相似性的測量方式 →（i）計算復(fù)雜度降低，運(yùn)行時間縮短
（ii）空間變形量的計算?！╥i）檢測精度更高

而DDIS對外觀和位置之間的分隔也可以使模板定位更加準(zhǔn)確。具有非常相似外觀的目標(biāo)窗口重疊可能導(dǎo)致非常相似的得分。 DDIS選擇隱含變形較少的窗口，可以提高定位精度。

DDIS可以克服諸如背景雜波，遮擋和非剛性變形等。缺點(diǎn)是不能處理物體的明顯尺度變化。

CoTM （Co-occurrence based template matching）

Introduction

CVPR2018 論文地址

CoTM提出了一種基于共現(xiàn)統(tǒng)計（co-occurrence statistics）來匹配像素的新度量，以量化模板和搜索圖像中潛在匹配區(qū)域之間的差異，在整個圖像平面上收集共現(xiàn)統(tǒng)計信息，測量一對像素值在小窗口內(nèi)共現(xiàn)的概率。該度量依賴于一個共現(xiàn)矩陣（co-occurrence matrix），該矩陣對一個窗口內(nèi)某個像素值對共同出現(xiàn)的次數(shù)進(jìn)行計數(shù)。

共現(xiàn)統(tǒng)計與前面提到的基于補(bǔ)丁的表示形式不同?；谘a(bǔ)丁的方法收集本地統(tǒng)計信息，而共現(xiàn)方法則收集全局統(tǒng)計信息。圖像中經(jīng)常出現(xiàn)的像素值可能是紋理區(qū)域的一部分，因此就隱式捕獲了紋理相似性的一些概念。CoTM與實(shí)際像素值無關(guān)，僅與它們的共現(xiàn)統(tǒng)計有關(guān)。

Method

基于SSD的模板匹配最小化∑_p(T_p-R_p)^2，其中，T是模板，R是圖像I中與T大小相同的區(qū)域，p是像素位置。

而CoTM最大化∑_p M(T_p,R_p)，其中M是從圖像數(shù)據(jù)中學(xué)習(xí)的（規(guī)范化）共現(xiàn)矩陣，可以使用它來給出將像素值T_p與像素值 R_p匹配的cost。

對于多通道圖像（即彩色或深層特征），我們使用k-means將圖像量化為固定數(shù)量的k簇。

Co-occurrence Matrix

共現(xiàn)矩陣C（a，b）對兩個像素值a和b一起出現(xiàn)在圖像中的次數(shù)進(jìn)行計數(shù)。值為其在像平面中的距離。

其中p和q是像素位置，I_p是圖像I中像素p的值，Z是歸一化因子。 σ是用戶指定的參數(shù)（僅考慮與σ成比例的窗口內(nèi)的像素），如果括號內(nèi)的值為true，則[·]等于1，否則為0。

為了保留圖像中很少出現(xiàn)的像素值，將C除以它們的先驗(yàn)概率，以獲得點(diǎn)向互信息（Pointwise Mutual Information PMI）矩陣：



其中h（a）是圖像中像素值a出現(xiàn)的概率。


共現(xiàn)統(tǒng)計：（左）查詢圖像。 （右）PMI矩陣M。（亮色為低分，深色為高分。）

M（A）：棕色和藍(lán)色很少同時出現(xiàn)，PMI較低。
M（B）：橙色和白色同時出現(xiàn)，PMI高。

M（C）：淺綠色和深綠色， 即使頻繁共現(xiàn)，PMI值也很低，因?yàn)樗麄兊南闰?yàn)概率很高。

將具有不同大小的兩個模板匹配到同一張圖像，僅屬于對象的像素具有較高的權(quán)重，并且匹配結(jié)果幾乎相同。
背景影響：（c）每像素分?jǐn)?shù)M（Tp，Qp）。添加更多背景像素并不會明顯改變整體得分。

Algorithm

CONCLUSION

CoTM對失準(zhǔn)和變形（misalignment and deformations）具有魯棒性，可以快速計算，并且可以處理不同的像素值，例如RGB顏色或深色特征。
但CoTM受到許多限制：

  • 首先，灰色像素值的共現(xiàn)效果不好。
  • 其次，當(dāng)模板的像素值頻繁出現(xiàn)在背景中時，性能會下降。（在這種情況下，背景像素不會降低權(quán)重。）

  • 最后，尚未解決照明方面的變化，


    Ground-truth：綠色框，顏色特征搜索：黃色框，深層特征搜索：紅色框

CONCLUSION

以上三種方法：

  • BBS，側(cè)重于nearest-neighbor（NN）匹配，以排除由背景像素引起的潛在和不良匹配。
  • DDIS，考慮了可能的模板變形，使用了模板和搜索圖像中潛在匹配區(qū)域之間的NN特征匹配的多樣性度量。
  • CoTM，量化模板和搜索圖像中潛在匹配區(qū)域之間的差異。

這些方法確實(shí)提高了模板匹配的性能。但是，由于兩個局限性，這些方法無法用于深度神經(jīng)網(wǎng)絡(luò)（DNN）中：

  1. 使用不可微分的運(yùn)算（例如閾值，計數(shù)等）
  2. 使用對DNN無效的運(yùn)算，例如作為循環(huán)和其他非批處理操作。

QATM

QATM

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容