簡(jiǎn)單看了幾篇模板匹配相關(guān)的論文厘熟，總結(jié)了一下，后期待修改
模板匹配介紹
模板匹配是計(jì)算機(jī)視覺(jué)應(yīng)用中最常用的技術(shù)之一维哈，可以應(yīng)用在視頻跟蹤绳姨，圖像拼接，目標(biāo)檢測(cè)笨农，字符識(shí)別和3D重建等方向上就缆。
模板和目標(biāo)圖像的子窗口之間的相似性度量是模板匹配的核心部分。
傳統(tǒng)的模板匹配相似性度量
傳統(tǒng)的模板匹配方法通常使用平方差和（SSD谒亦，sum-of-squared-differences）或歸一化積相關(guān)（NCC竭宰，normalized cross-correlation）等來(lái)計(jì)算模板與基礎(chǔ)圖像之間的相似度得分。
在搜索圖S中份招，以(i,j)為左上角切揭，取MxN大小的子圖，計(jì)算其與模板的相似度锁摔；遍歷整個(gè)搜索圖廓旬，在所有能夠取到的子圖中，找到與模板圖最相似的子圖作為最終匹配結(jié)果谐腰。
SSD
平方差和孕豹，數(shù)值越大相似度越小。
NCC
利用子圖與模板圖的灰度十气，通過(guò)歸一化的相關(guān)性度量公式來(lái)計(jì)算二者之間的匹配程度励背。
傳統(tǒng)算法評(píng)價(jià)：
優(yōu)點(diǎn)：
①思路簡(jiǎn)單，容易理解砸西。②運(yùn)算過(guò)程簡(jiǎn)單叶眉，匹配精度高。
缺點(diǎn)：
①運(yùn)算量偏大芹枷。②對(duì)噪聲非常敏感衅疙。
總結(jié)：
當(dāng)模板和目標(biāo)搜索圖像之間的轉(zhuǎn)換很簡(jiǎn)單時(shí)，這些方法效果很好鸳慈。但是饱溢，當(dāng)轉(zhuǎn)換復(fù)雜或非剛性時(shí)（stretching or shrinking），這些方法的成功率會(huì)大幅下降走芋。 另外理朋，其他因素（例如遮擋和顏色偏移）也會(huì)對(duì)這些方法造成很大影響絮识。
并且，這種方法測(cè)量相似性時(shí)考慮模板和目標(biāo)圖像中的候選窗口中的所有像素（特征點(diǎn)）嗽上。當(dāng)目標(biāo)背后的背景改變時(shí)次舌，這種方法是不可取的。
BBS（Best-Buddies-Similarity）
Introduction
CVPR2015 論文地址
本質(zhì)是Best-Buddies Similarity（BBS算法）兽愤。這是一種在兩個(gè)點(diǎn)集之間的無(wú)參魯棒相似性測(cè)量彼念，核心是計(jì)算Best-Buddies Pairs（BBPs）的數(shù)量。
Method
用傳統(tǒng)的滑動(dòng)窗口方法浅萧，在模板和圖像中每個(gè)可能的窗口（模板大兄鹕场）之間同樣計(jì)算出BBS。
BBS
首先需要將每個(gè)圖像塊轉(zhuǎn)換為中的一個(gè)點(diǎn)集洼畅。為此吩案，把圖像分成若干個(gè)的k x k圖像塊。每個(gè)圖像塊由其RGB值組成的
個(gè)矢量和中心像素相對(duì)于坐標(biāo)系的xy坐標(biāo)表示帝簇。
BBS測(cè)量了兩個(gè)點(diǎn)集P和Q之間的相似性徘郭，當(dāng)和
互為最近鄰時(shí)，他們?yōu)橐唤MBBP（原集和目標(biāo)集中的點(diǎn)對(duì)丧肴，每個(gè)點(diǎn)都是另一個(gè)點(diǎn)的最近鄰）残揉。
BBS隨兩點(diǎn)集的分布區(qū)別增大而減小纸巷，兩個(gè)分布相同時(shí)取得最大值镇草。如果兩個(gè)點(diǎn)是BBP，它們很可能是從相同的分布中提取的瘤旨。
BBS的主要特性為
- 只依賴于匹配點(diǎn)（BBPs）的子集（通常很刑萜 ），其余的被視為外點(diǎn)裆站，對(duì)于大部分異常點(diǎn)具有魯棒性
- BBS可以找出數(shù)據(jù)中的雙向匹配點(diǎn)而不需要任何先驗(yàn)知識(shí)或者潛在變形
- BBP通過(guò)計(jì)算BBP的數(shù)量進(jìn)行排名，而不是使用實(shí)際的距離值
CONCLUSION
在存在高水平的異常值（即背景噪聲黔夭、遮擋）和目標(biāo)的非剛性變形的情況下宏胯，將模板與給定圖像匹配”纠眩可以抵抗復(fù)雜的幾何變形和高度異常的點(diǎn)（背景噪聲和遮擋）肩袍。
BBS可以在存在異常值的情況下可靠地匹配來(lái)自同一分布的特征，在視角變換和集合變形下依然可以進(jìn)行穩(wěn)健的模板匹配婚惫。
缺點(diǎn)是當(dāng)模板與目標(biāo)圖像相比很小時(shí)氛赐，或者離群值（遮擋對(duì)象或背景雜波）覆蓋了大多數(shù)模板時(shí)魂爪，成功率會(huì)降低。
DDIS （Deformable Diversity Similarity）
Introduction
——CVPR2017 論文地址
DDIS明確考慮了可能的模板變形艰管，并使用了模板和搜索圖像中潛在匹配區(qū)域之間的NN特征匹配的多樣性滓侍。
采用了基于特征的BBS無(wú)參數(shù)方法∩螅基于目標(biāo)圖像窗口和模板之間特征匹配的多樣性撩笆，它對(duì)復(fù)雜的變形，明顯的背景雜波和遮擋具有魯棒性缸浦。
Method
Diversity
我們的關(guān)鍵思想是通過(guò)最近鄰域（NN field）的兩個(gè)屬性來(lái)得到目標(biāo)和模板之間的相似性夕冲。
首先，如圖2d所示裂逐，當(dāng)目標(biāo)和模板對(duì)應(yīng)時(shí)歹鱼，大多數(shù)目標(biāo)patch在模板中具有唯一的NN匹配。這意味著最近鄰域高度多樣化卜高，指向模板中的許多不同的patch弥姻。
相反，如圖2e所示篙悯，對(duì)于任意目標(biāo)蚁阳，大多數(shù)patch都沒(méi)有很好的匹配，并且NN收斂到恰好與目標(biāo)patch相似的少量模板點(diǎn)鸽照。第二螺捐，不佳匹配往往意味著較大的變形，如圖2e中的長(zhǎng)箭頭所示矮燎。
DIS & BBP
對(duì)每個(gè)q定血，都有一條紅箭頭指向它的NN p，如果p q為BBP诞外，將兩點(diǎn)之間的紅箭頭改為綠線澜沟。
DIS計(jì)算由紅色箭頭或綠線指向的藍(lán)色三角形數(shù)量。BBS計(jì)算綠線數(shù)量峡谊。
（a）P和Q的分布相似茫虽，因此，許多p是某些q的NN既们，并且有很多BBP濒析。這里DIS = BBS =8。
（b）P和Q具有不同的分布啥纸。密集p中的單個(gè)q或密集q中的單個(gè)p對(duì)DIS和BBS均貢獻(xiàn)1号杏。有時(shí)，Q和P之間存在唯一的NN匹配斯棒，而不是BBP盾致。由于P和Q的分布不同主经，DIS和BBS都相對(duì)較低，因此DIS = 3和BBS = 2庭惜。
DDIS
為了整合對(duì)大變形的懲罰罩驻，對(duì)DIS進(jìn)行了兩種修改：
首先，為了獲得變形場(chǎng)的顯式表示蜈块，區(qū)分每個(gè)patch的外觀和位置并將它們分別對(duì)待鉴腻。
其次，提出了另一種測(cè)量多樣性的方法百揭，該方法可以考慮變形量爽哎。
令表示外觀，而
表示patch p的位置（q同理）器一。我們?yōu)槊總€(gè)點(diǎn)
尋找基于appearance的
（d為距離函數(shù))
和它的的location距離由表示
定義作為為的patch q的數(shù)量课锌，
定義DDIS：其中歸一化因子c = 1 / min {M，N}
該定義可以看作是點(diǎn)上的contribution之和祈秕。 每個(gè)點(diǎn)的貢獻(xiàn)由其隱含變形矢量的長(zhǎng)度反向加權(quán)渺贤。
當(dāng)點(diǎn)具有唯一的NN時(shí)，則
志鞍，指數(shù)達(dá)到最大值1。
當(dāng)q_j的NN被許多其他點(diǎn)共享時(shí)方仿，則大，指數(shù)值低仙蚜，并且q_j對(duì)相似度的總體貢獻(xiàn)低此洲。
DDIS具有使其具有吸引力的幾個(gè)屬性：
（1）它主要依賴于具有不同NN的點(diǎn)。 共享NN的點(diǎn)的分?jǐn)?shù)對(duì)分?jǐn)?shù)的影響較小委粉。
（2）DDIS不需要任何有關(guān)數(shù)據(jù)或其潛在變形的先驗(yàn)知識(shí)呜师。
（3）DDIS分析NN field，而不是使用實(shí)際距離值贾节。
CONCLUSION
DDIS與BBS極為相似汁汗，他們都依賴于兩組點(diǎn)之間的NN匹配。 但是有兩個(gè)主要區(qū)別：
（i）兩組之間相似性的測(cè)量方式 →（i）計(jì)算復(fù)雜度降低栗涂，運(yùn)行時(shí)間縮短
（ii）空間變形量的計(jì)算知牌。→（ii）檢測(cè)精度更高
而DDIS對(duì)外觀和位置之間的分隔也可以使模板定位更加準(zhǔn)確戴差。具有非常相似外觀的目標(biāo)窗口重疊可能導(dǎo)致非常相似的得分送爸。 DDIS選擇隱含變形較少的窗口铛嘱，可以提高定位精度暖释。
DDIS可以克服諸如背景雜波袭厂，遮擋和非剛性變形等。缺點(diǎn)是不能處理物體的明顯尺度變化球匕。
CoTM （Co-occurrence based template matching）
Introduction
CVPR2018 論文地址
CoTM提出了一種基于共現(xiàn)統(tǒng)計(jì)（co-occurrence statistics）來(lái)匹配像素的新度量纹磺，以量化模板和搜索圖像中潛在匹配區(qū)域之間的差異，在整個(gè)圖像平面上收集共現(xiàn)統(tǒng)計(jì)信息亮曹，測(cè)量一對(duì)像素值在小窗口內(nèi)共現(xiàn)的概率橄杨。該度量依賴于一個(gè)共現(xiàn)矩陣（co-occurrence matrix），該矩陣對(duì)一個(gè)窗口內(nèi)某個(gè)像素值對(duì)共同出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)照卦。
共現(xiàn)統(tǒng)計(jì)與前面提到的基于補(bǔ)丁的表示形式不同式矫。基于補(bǔ)丁的方法收集本地統(tǒng)計(jì)信息役耕，而共現(xiàn)方法則收集全局統(tǒng)計(jì)信息采转。圖像中經(jīng)常出現(xiàn)的像素值可能是紋理區(qū)域的一部分，因此就隱式捕獲了紋理相似性的一些概念瞬痘。CoTM與實(shí)際像素值無(wú)關(guān)故慈，僅與它們的共現(xiàn)統(tǒng)計(jì)有關(guān)。
Method
基于SSD的模板匹配最小化框全，其中察绷，T是模板，R是圖像I中與T大小相同的區(qū)域津辩，p是像素位置拆撼。
而CoTM最大化，其中M是從圖像數(shù)據(jù)中學(xué)習(xí)的（規(guī)范化）共現(xiàn)矩陣丹泉，可以使用它來(lái)給出將像素值
與像素值
匹配的cost情萤。
對(duì)于多通道圖像（即彩色或深層特征），我們使用k-means將圖像量化為固定數(shù)量的k簇摹恨。
Co-occurrence Matrix
共現(xiàn)矩陣C（a筋岛，b）對(duì)兩個(gè)像素值a和b一起出現(xiàn)在圖像中的次數(shù)進(jìn)行計(jì)數(shù)。值為其在像平面中的距離晒哄。
其中p和q是像素位置睁宰，I_p是圖像I中像素p的值，Z是歸一化因子寝凌。 σ是用戶指定的參數(shù)（僅考慮與σ成比例的窗口內(nèi)的像素）柒傻，如果括號(hào)內(nèi)的值為true，則[·]等于1较木，否則為0红符。
為了保留圖像中很少出現(xiàn)的像素值，將C除以它們的先驗(yàn)概率，以獲得點(diǎn)向互信息（Pointwise Mutual Information PMI）矩陣：
其中h（a）是圖像中像素值a出現(xiàn)的概率预侯。
M（A）：棕色和藍(lán)色很少同時(shí)出現(xiàn)，PMI較低糜芳。
M（B）：橙色和白色同時(shí)出現(xiàn)飒货，PMI高。
M（C）：淺綠色和深綠色峭竣， 即使頻繁共現(xiàn)塘辅，PMI值也很低，因?yàn)樗麄兊南闰?yàn)概率很高皆撩。
Algorithm
CONCLUSION
CoTM對(duì)失準(zhǔn)和變形（misalignment and deformations）具有魯棒性蟆融，可以快速計(jì)算，并且可以處理不同的像素值守呜，例如RGB顏色或深色特征型酥。
但CoTM受到許多限制：
- 首先，灰色像素值的共現(xiàn)效果不好查乒。
- 其次弥喉，當(dāng)模板的像素值頻繁出現(xiàn)在背景中時(shí)，性能會(huì)下降玛迄。（在這種情況下由境，背景像素不會(huì)降低權(quán)重。）
-
最后蓖议，尚未解決照明方面的變化虏杰，
Ground-truth：綠色框，顏色特征搜索：黃色框勒虾，深層特征搜索：紅色框
CONCLUSION
以上三種方法：
- BBS纺阔，側(cè)重于nearest-neighbor（NN）匹配，以排除由背景像素引起的潛在和不良匹配修然。
- DDIS笛钝，考慮了可能的模板變形质况，使用了模板和搜索圖像中潛在匹配區(qū)域之間的NN特征匹配的多樣性度量。
- CoTM玻靡，量化模板和搜索圖像中潛在匹配區(qū)域之間的差異拯杠。
這些方法確實(shí)提高了模板匹配的性能。但是啃奴，由于兩個(gè)局限性，這些方法無(wú)法用于深度神經(jīng)網(wǎng)絡(luò)（DNN）中：
- 使用不可微分的運(yùn)算（例如閾值雄妥，計(jì)數(shù)等）
- 使用對(duì)DNN無(wú)效的運(yùn)算最蕾，例如作為循環(huán)和其他非批處理操作。
