本文主要內容
1.模版匹配
2.特徵匹配
3.深度學習去找目標
圖像匹配是指通過一定的匹配算法在兩幅或多幅圖像之間識別同名點。
應用：遙感（製圖更新），計算機視覺應用程式，醫療用圖像註冊。
圖像匹配主要可分為以灰度為基礎的匹配和以特徵為基礎的匹配。
模板匹配是基於像素的匹配，用來在一副大圖中搜尋查找模版圖像位置的方法。和 2D 卷積一樣，它也是用模板圖像在輸入圖像（大圖）上滑動，並在每一個位置對模板圖像和與其對應的輸入圖像的子區域進行比較。OpenCV 提供了幾種不同的比較方法。返回的結果是一個灰度圖像，每一個像素值表示了此區域與模板的匹配程度。
當你得到這幅圖之後，就可以使用函數cv2.minMaxLoc() 來找到其中的最小值和最大值的位置了。
第一個值為矩形左上角的點（位置），（w，h）為模板矩形的寬和高。這個矩形就是找到的模板區域了。注意：如果你使用的比較方法是 cv2.TM_SQDIFF，最小值對應的位置才是匹配的區域。CV_TM_SQDIFF 平方差匹配法：該方法採用平方差來進行匹配；最好的匹配值為0；匹配越差，匹配值越大。
CV_TM_CCORR?相關匹配法：該方法採用乘法操作；數值越大表明匹配程度越好。
CV_TM_CCOEFF?相關係數匹配法：1表示完美的匹配；-1表示最差的匹配。
CV_TM_SQDIFF_NORMED?歸一化平方差匹配法
CV_TM_CCORR_NORMED?歸一化相關匹配法
CV_TM_CCOEFF_NORMED?歸一化相關係數匹配法
假如你的模板圖像在目標圖像中出現了很多次怎麼辦呢？
如果你想匹配一次，就找最大匹配的點，如果你想匹配多個物體，就可以自己來設置一個匹配閾值，根據你的需求來
模板匹配具有自身的局限性，主要表現在它只能進行平行移動，若原圖像中的匹配目標發生旋轉或大小變化，該算法無效。
1.SIFT特徵提取
2.FLANN匹配器
圖像特徵
特徵描述，計算機對特徵周圍的區域進行描述，這樣它才能在其他圖像中找到相同的特徵
SIFT: 是一種檢測局部特徵的算法，該算法通過求一幅圖中的特徵點（interest points, or corner points）及其有關scale 和 orientation 的描述子得到特徵並進行圖像特徵點匹配
SIFT特徵不只具有尺度不變性，即使改變旋轉角度，圖像亮度或拍攝視角，仍然能夠得到好的檢測效果。
1.尺度空間極值檢測:這是一個初始化操作，尺度空間理論目的是模擬圖像數據的多尺度特徵。
2.關鍵點（極值點）定位
3.為關鍵點（極值點）指定方向參數
4.關鍵點描述符的生成
1.構建尺度空間
不同的尺度空間不能使用相同的窗口檢測極值點。對小的角點要用小的窗口，對大的角點只能使用大的窗口。為了達到這個目的我們要使用尺度空間濾波器
這是一個初始化操作，尺度空間理論目的是模擬圖像數據的多尺度特徵。使用具有不同方差值 σ 的高斯拉普拉斯算子（LoG）對圖像進行卷積。
LoG 的計算量非常大，為了有效的在尺度空間檢測到穩定的關鍵點，所以 SIFT 算法使用高斯差分算子（DoG）來對 LoG 做近似。利用不同尺度的高斯差分核與圖像卷積生成。具體到圖像處理來講，就是將兩幅圖像在不同參數下的高斯濾波結果相減，得到DoG圖
圖像金字塔：我們可以通過降採樣（如只取奇數行或奇數列）來構成一組圖像尺寸（1，0.5，0.25 等）不同的金字塔，然後對這一組圖像中的每一張圖像使用具有不同方差 σ 的高斯卷積核構建出具有不同解析度的圖像金字塔（不同的尺度空間）。DoG 就是這組具有不同解析度的圖像金字塔中相鄰的兩層之間的差值。如下圖所示：
i為塔數（第幾個塔），s為每塔層數由圖片size決定建幾個塔，每塔幾層圖像(S一般為3-5層)。0塔的第0層是原始圖像(或你double後的圖像)，直觀上看來越往上圖片越模糊。
2.檢測DOG尺度空間極值點
高斯尺度空間金字塔中每組有五層不同尺度圖像，相鄰兩層相減得到四層DoG結果。關鍵點搜索就在這四層DoG圖像上尋找局部極值點。尋找DoG極值點時，每一個像素點和它所有的相鄰點比較，當其大於（或小於）它的圖像域和尺度域的所有相鄰點時，即為極值點。則在比較時犧牲了-1組的第0層和第N組的最高層
除去不好的特徵點
以上極值點的搜索是在離散空間進行搜索的，由下圖可以看到，在離散空間找到的極值點不一定是真正意義上的極值點。使用尺度空間的泰勒級數展開來獲得極值的準確位置，如果極值點的灰度值小於閾值（0.03）就會被忽略掉。DoG 算法對邊界非常敏感，會產生較強的邊緣響應，所以我們必須要把邊界去除，使用近似Harris Corner檢測器。
通過擬和三維二次函數以精確確定關鍵點的位置和尺度（達到亞像素精度），同時去除低對比度的關鍵點和不穩定的邊緣響應點，以增強匹配穩定性、提高抗噪聲能力。
3.為關鍵點（極值點）指定方向參數
上一步中確定了每幅圖中的特徵點，為每個特徵點計算一個方向，這樣它才會具有旋轉不變性。獲取關鍵點（所在尺度空間）的鄰域，然後計算這個區域的梯度級和方向。根據計算得到的結果創建一個含有 36 個 bins（每 10度一個 bin）的方向直方圖。直方圖中的峰值為主方向參數，如果其他的任何柱子的高度高於峰值的80% 被認為是輔方向。這就會在相同的尺度空間相同的位置構建出具有不同方向的關鍵點。這對於匹配的穩定性會有所幫助。
每個關鍵點有三個信息：位置，所處尺度、方向，由此可以確定一個SIFT特徵區域。
4. 關鍵點描述子的生成
該步中將建立所有scale中特徵點的描述子（128維）
通過對關鍵點周圍圖像區域分塊，計算塊內梯度直方圖，生成具有獨特性的向量，這個向量是該區域圖像信息的一種抽象，具有唯一性。
為了保證特徵矢量具有旋轉不變性，要以特徵點為中心，在附近鄰域內旋轉θ角，即旋轉為特徵點的方向。
選取與關鍵點周圍一個 16x16 的鄰域，把它分成 16 個 4x4 的小方塊，為每個小方塊創建一個具有 8 個 bin 的方向直方圖。繪製每個梯度方向的累加值，即可形成一個種子點，這樣就可以對每個特徵形成一個4*4*8=128維的描述子，每一維都可以表示4*4個格子中一個的scale/orientation.?將這個向量歸一化之後，就進一步去除了光照的影響。
生成了A、B兩幅圖的描述子（分別是k1*128維和k2*128維）。
將兩圖中各個scale（所有scale）的描述子進行匹配，匹配上128維即可表示兩個特徵點match上了。
可以採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取第一個圖的某個關鍵點，通過遍歷找到第二幅圖像中的距離最近的那個關鍵點。但有些情況下，第二個距離最近的關鍵點與第一個距離最近的關鍵點靠的太近。這可能是由於噪聲等引起的。此時要計算最近距離與第二近距離的比值。如果比值大於 0.8，就忽略掉。這會去除 90% 的錯誤匹配，同時只去除 5% 的正確匹配。
FLANN 是快速最近鄰搜索包（Fast_Library_for_Approximate_Nearest_Neighbors）的簡稱。它是一個對大數據集和高維特徵進行最近鄰搜索的算法的集合，而且這些算法都已經被優化過了。
使用 FLANN 匹配，我們需要傳入兩個字典作為參數。這兩個用來確定要使用的算法和其他相關參數等，第一個是 IndexParams，第二個字典是 SearchParams。用它來指定遞歸遍歷的次數。值越高結果越準確，但是消耗的時間也越多。
indexparams = dict(algorithm =FLANN_INDEX_KDTREE, trees = 5)
searchparams = dict(checks = 100)
flann = cv2.FlannBasedMatcher(indexParams,searchParams)
matches = flann.knnMatch(des1,des2,k=2)
檢測出的匹配點可能有一些是錯誤正例（false positives）。因為這裡使用過的kNN匹配的k值為2（在訓練集中找兩個點），第一個匹配的是最近鄰，第二個匹配的是次近鄰。直覺上，一個正確的匹配會更接近第一個鄰居。換句話說，一個不正確的匹配，兩個鄰居的距離是相似的。因此，我們可以通過查看二者距離的不同來評判匹配程度的好壞。並且捨去那些不好的匹配點，保留好的匹配點。
我們在一張雜亂的圖像中找到了一個對象（的某些部分）的位置。這些信息足以幫助我們在目標圖像中準確的找到（模板圖像）對象。
我們可以使用cv2.findHomography()函數如果將這兩幅圖像中的特徵點集傳給這個函數，他就會找到這個對象的透視圖變換。
透視變換(Perspective Transformation)是將成像投影到一個新的視平面(Viewing Plane)，也稱作投影映射(Projective Mapping)。
然後我們就可以使用函數 cv2.perspectiveTransform() 找到模板圖像的4個坐標點變換到目標圖像中的新的坐標了。
一個平面到另一個平面的映射關係。兩張圖分別有四個相對位置相同的點，Homography就是一個變換（3*3矩陣），將一張圖中的點映射到另一張圖中對應的點
用網絡去訓練的模型，能夠識別出目標，但是對訓練數據的構造要求比較高。遷移性很難得到保證。
a.先將要訓練的圖像進行標記，可以把你要識別的每個模板標為一類
b.訓練的圖儘可能的豐富，這樣可以增強模型的遷移性
c.用訓練好的模型去測試，識別出目標圖片上的類
特徵匹配與模板匹配的區別:模板匹配是基於像素的，特徵匹配則是基於區域的，特徵匹配在考慮像素灰度的同時還應考慮諸如空間整體特徵、空間關係等因素。
特徵是圖像內容最抽象的描述，與基於灰度的匹配方法相比，特徵相對於幾何圖像和輻射度影響來說更不易變化，但特徵提取方法的計算代價通常較大，並且需要一些自由參數和事先按照經驗選取的閥值，因而不便於實時應用。同時，在紋理較少的圖像區域提取的特徵的密度通常比較稀少，使局部特徵的提取比較困難。另外，基於特徵的匹配方法的相似性度量也比較複雜，往往要以特徵屬性、啟發式方法及閥方法的結合來確定度量方法。
深度學習的方法對數據的要求較高，需要考慮模型的遷移性，相對訓練的時間也會耗費更多，但數據集夠豐富的時候，深度學習是個很好的選擇。
在應用過程中，選擇優先使用模板匹配，再用特徵匹配，最後用深度學習的方式
第一個是indexParams。配置我們要使用的算法
1、隨機k-d樹算法（The Randomized k-d TreeAlgorithm）
a.Classick-d tree
找出數據集中方差最高的維度，利用這個維度的數值將數據劃分為兩個部分，對每個子集重複相同的過程。
b.Randomizedk-d tree
建立多棵隨機k-d樹，從具有最高方差的N_d維中隨機選取若干維度，用來做劃分。在對隨機k-d森林進行搜索時候，所有的隨機k-d樹將共享一個優先隊列。
增加樹的數量能加快搜索速度，但由於內存負載的問題，樹的數量只能控制在一定範圍內，比如20，如果超過一定範圍，那麼搜索速度不會增加甚至會減慢
2、優先搜索k-means樹算法（The Priority Search K-MeansTree Algorithm）
2.1算法描述
步驟1 建立優先搜索k-means tree:
(1)建立一個層次化的k-means 樹；
(2)每個層次的聚類中心，作為樹的節點；
(3)當某個cluster內的點數量小於K時，那麼這些數據節點將做為葉子節點。
步驟2 在優先搜索k-means tree中進行搜索：
(1)從根節點N開始檢索；
(2)如果是N葉子節點則將同層次的葉子節點都加入到搜索結果中，count += |N|；
(3)如果N不是葉子節點，則將它的子節點與query Q比較，找出最近的那個節點Cq，同層次的其他節點加入到優先隊列中；
(4)對Cq節點進行遞歸搜索；
(5)如果優先隊列不為空且 count<L，那麼從取優先隊列的第一個元素賦值給N，然後重複步驟(1)。
聚類的個數K，也稱為branching factor 是個非常主要的參數。
建樹的時間複雜度 = O( ndKI ( log(n)/log(K) ))? n為數據點的總個數，I為K-means的迭代次數。搜索的時間複雜度 = O( L/K * Kd * ( log(n)/(log(K) ) ) = O(Ld ( log(n)/(log(K) ) )。
3.層次聚類樹 （The Hierarchical ClusteringTree）
層次聚類樹採用k-medoids的聚類方法，而不是k-means。即它的聚類中心總是輸入數據的某個點，但是在本算法中，並沒有像k-medoids聚類算法那樣去最小化方差求聚類中心，而是直接從輸入數據中隨機選取聚類中心點，這樣的方法在建立樹時更加簡單有效，同時又保持多棵樹之間的獨立性。
同時建立多棵樹，在搜索階段並行地搜索它們能大大提高搜索性能（歸功於隨機地選擇聚類中心，而不需要多次迭代去獲得更好的聚類中心）。建立多棵隨機樹的方法對k-d tree也十分有效，但對於k-means tree卻不適用。
比如我們使用SIFT，我們可以傳入參數：
index_params=dict(algorithm = FLANN_INDEX_KDTREE，trees=5)