1、第7章 圖像匹配目錄7.1 基本概念7.2 圖像匹配算法分類7.3 模板匹配算法7.4 改進算法7.1 基本概念模板匹配可以分為狹義的和廣義的。狹義匹配：匹配的目標是同一樣事物。因為一個事物的自身特點總是固定的，比如顏色、大小、形狀等等，即便由于環境的不同而導致獲取的圖片有差別，只要計算機能夠分辨出這些特征就可以識別事物。廣義的匹配：匹配的是一類事物。如，某一種動物，某一類型的汽車等。相比于前一種匹配，這種方式更為復雜，需要系統具備一定的學習和推理能力。7.2 圖像匹配算法分類直接利用原始圖像的灰度進行匹配利用圖像的物理形狀特征進行匹配使用高級特征的算法進行匹配直接利用原始圖像的灰度進行匹配直

2、接利用圖像的信息區分不同對象，處理的信息量大，計算復雜度高。對圖像之間的微小差別非常敏感，一個細微的變化(比如光照條件的微小變化而導致的圖像灰度值的細微變化)就會對匹配算法的計算結果產生大的影響，甚至可能導致匹配的失敗。結論：抗噪聲、抗干擾的能力比較差，只能適用于2幅圖像具有相同外界條件的情況下作精細的匹配。使用高級特征的算法進行匹配基于約束的樹搜索，可利用深度優先搜索策略，依靠解釋樹尋找局部一致的匹配。基于多尺度特征作特征匹配，則是對圖像信息引入多種級別的抽象，遵循先輪廓后細節，先宏觀后微觀，先易于辨認部分后較為模糊部分的人類視覺匹配規律，能提高圖像匹配的可靠性7.3 模板匹配算法ABS算法

3、歸一化互相關匹配算法圖像矩匹配算法基于圖像特征點的匹配算法匹配準則3種匹配準則：實現方便，但如果待匹配圖像或是模板圖像之一的灰度值發生線性變換，就無所適從了。不同的圖像和模板有著不同的背景灰度值和不同的搜索窗口，所需的閾值也各不相同，很難事先選定閾值，因而誤匹配率很高。這種算法只適用于待匹配圖是模板圖像中部分的情況歸一化互相關匹配算法歸一化互相關匹配算法是一種經典的統計算法，通常寫為NC(Normalized Correlation)算法。這種算法通過計算模板和待匹配圖像的互相關值來確定匹配的程度。互相關值最大時的搜索窗口位置決定了模板圖像在待匹配圖像中的位置。互相關的定義一般有如下2種形式：

4、設模板為M(lw )，其中l、w是M的長和寬；搜索的基準圖為S(LW )，其中L、W是S的長和寬。將模板M在基準圖S上平移，模板覆蓋下的區域為子區域 。定義i和j是模板M的左上角像素在基準圖中的坐標，那么需要搜索的范圍，即坐標(i,j)的范圍就是：1iW-w1jL- l根據以上的描述，將模板M與子區域 進行比較，在眾多的子區域中尋求相似性最大化的那個作為匹配。定義相似性關系函數為：上式的意義并非是看二者的相似程度，相反，它是看二者相差了多少。相似程度越高， 的值反而越小。將上式展開可以得到：D(i, j) 的大小并不能體現模板與子區域的相似程度。定義相關函數：歸一化，得：當子區域與模板匹配時，

5、 有最大值。當子區域與模板完全一樣時，R0(i,j) =1；反之 R0(i,j) 1， R0(i,j)的值越大，則子區域與模板相似程度越高圖像矩匹配算法在圖像處理中，矩是一種統計特性，可采用不同階次的矩來計算模板的位置、方向和尺寸變換參數。由于高階矩對噪聲和變形非常敏感，因此在實際應用中通常選用低階來實現圖像匹配，一般采用具有平移、旋轉與尺寸不變性的矩特征參數。對于圓形窗口內的歸一化矩陣，可將平移、旋轉和尺度變化的模板匹配簡化為一般的平移模板匹配。這種不變矩在模式識別、圖像分類和目標跟蹤方面發揮著重要作用。在精確尋的中，由于實時圖和基準圖的獲取方式、時間和空間位置都不同，因此實時圖相對于基準圖

6、就會產生一定的平移、旋轉和比例變化等幾何失真。圖像矩的幾何失真不變性正好克服了這個問題對于給定的數字圖像，定義它的（p+q）階混合原點矩為相應的（p+q）階混合中心矩可表示為：其中：用零階中心矩對各階中心矩進行規格化，得：利用第二、三階矩，可導出七個不變矩組利用第二、三階矩，可導出七個不變矩組：利用上面七個式子便可求出任意一個數字地圖的七個不變矩，這些不變矩反映了地圖的固有特征。因此，精確尋的問題可用實時圖和基準子圖七個不變矩之間的相似度來解決。令實時圖和基準子圖的不變矩分別為Mi和Nj, 則它們之間的相似度為：在所有的試驗位置(u,v)上，maxR(u*,v*) 所對應的位置 即為匹配點。該

7、算法稱為圖像矩算法，這種方法對圖像噪聲敏感，而且對圖像的質量要求較高。基于圖像特征點的匹配算法圖像特征提取是圖像匹配和三維信息提取的基礎，是影像分析與圖像處理技術領域中最重要的任務之一。有效的特征提取算法是影像分析與處理的關鍵。在基于點特征的圖像配準中，特征點的提取是圖像配準的關鍵步驟。常用的點特征提取方法有：Moravec算子、Harri算子、SUSAN算子、Foratner算子等特征點提取方法多尺度小波變換法提取邊緣點SUSAN角點提取法仿射不變Harris特征提取算子Forstner興趣算子Moravec興趣算子SUSAN角點提取法角點：兩條直線邊緣的接合點。圖像的角點檢測方法：1. 先

8、將圖像分割為區域，用鏈碼表示目標邊界，然后通過方向變化確定角點。這種方法的主要缺點是角點檢測的結果依賴于前面的圖像分割的結果。2. 直接對圖像灰度級進行操作，這些方法主要利用梯度和曲率度量檢測角點。Smith等人提出的SUSAN算法為第二類方法。SUSAN算法：用圓形模板在圖像上移動，若模板內像素的灰度與模板中心像素灰度的差值小于一定閾值，則認為該點與核具有相同的灰度，由滿足這樣條件的像素組成 的局部 區域稱為“USAN”。根據 USAN的尺寸、質心和二階矩，可檢測邊緣、角點等特征。SUSAN角點提取法不涉及圖像的求導運算，具有簡單直觀、特征定位比較準確等優點仿射不變Harris特征提取算子H

9、arris算子是C.Harris和M.J.Stephens于1998年提出的基于信號強度的點特征提取算子，具體如下:1. 構造一個與自相關函數相聯系的矩陣A，A陣的特征值是自相關函數的一階曲率2. 如果兩個曲率值都高，則認為該點是特征點。Harris算子中只用到灰度的一階差分以及濾波，計算簡單。同時，由于Harris算子特征點的檢測不需設置閾值，可以滿足檢測自動化的要求。Moravec興趣算子Moravec于1977年提出利用灰度方差提取點特征的算子。Moravec算子是在四個主要方向上，選擇具有最大最小灰度方差的點作為特征點：第一步，計算各像元的興趣值IV（interest value）。第

10、二步，給定一經驗閾值，將興趣值大于該閾值的點（即興趣值計算窗口的中心點）作為候選點。閾值的選擇應以候選點中包括所需要的特征點，而又不含過多的非特征點為原則。第三步，選取候選點中的極值點作為特征點。近些年應用較多的一種方法是：首先利用邊緣提取方法提取整個圖象的邊緣輪廓，然后在此輪廓內利用以上特征點提取方法提取特征點。下面以滑動同心窗結合連通區域分析的定位方法為例，說明這種方法在車牌識別中的應用。滑動同心窗原理（SCW）目標檢測，是指在一幅或多幅圖像中檢測用戶所感興趣的區域。車牌定位也是目標檢測的一種。滑動同心窗（sliding concentric windows, SCW）是一種常用的圖像分割

11、方法，用于檢測用戶所感興趣的各種區域。用戶可根據待檢測目標的特征，定義SCW的參數，實現正確檢測。直觀上，車牌區域在整幅圖像中具有其獨自的特征。最明顯的就是其紋理的不規則，導致其統計特性的急劇變化。由于牌照的規格一致，字體的規格也一致，導致這種統計上的變化又具有某些不變的特征。SCW可以很好地描述這種“不規則”，它統計父窗口和子窗口中所有像素的均值或者標準差，并根據兩者的比值大小，反映窗口區域中像素的變化情況圖7-2 父窗體和子窗體的建立其算法步驟如下：(1) 建立兩個同心窗A和B，A嵌套在B內，稱A為子窗口，B為父窗口。A的大小為(2X1+1)(2Y1+1)個像素，B的大小為(2X2+1)(

12、2Y2+1)。將B窗體的左上角像素與圖像的左上角像素對齊，如下圖所示:(2) 計算A窗和B窗內像素的統計特性MA和MB (本書使用平均值)，然后對兩值進行比較，求其比值。如果比值超過閾值(根據待檢測目標的特性，由用戶設定，為一經驗值)，則認為窗口的中心像素是屬于目標區域(本文則認為是車牌像素點)，置為255；否則認為是非車牌像素點，置為0。判決規則如下：圖7-3 SCW處理前后對比(3) 按照如上步驟掃描全圖，判決所有像素點，并得到二值圖。SCW是對原始圖像進行處理的第一步，在得到的二值圖中，判決為車牌的點像素值為255，非車牌點像素值為0。用SCW處理后的一些結果如下圖所示：連通區域分析（C

13、CA）原始圖像經過SCW處理后，成為一幅二值圖像。其中白色像素點代表可能的車牌區域，黑色像素點代表非車牌區域。整幅圖像表現為多個子區域，例如在圖（7-3）中，包含有車牌區域，兩個車燈區域，散熱器區域，以及其他區域。接下來就需要分割區域，并分析各個區域的特點，并從中找出車牌區域。連通區域分析(connected component analysis, CCA)是一種圖像分析算法，它分析輸入圖像中各像素間的連通性，并根據這種連通性，將圖像分割為多個連通區域，同時還得到各個連通區域的幾何特征(面積，方向，重心等等)。各個區域內的像素點之間存在直接或者間接的相鄰性，不同區域內的像素點之間不存在直接或者

14、間接的相鄰性。相鄰性有4連通或者8連通等不同定義。圖7-4 歐拉數定義示意圖CCA算法可以很容易地從圖（7-3）中分析出車牌區域，車燈區域，散熱器區域，以及其他區域，并得到這些區域的特性。為了在多個區域中區分車牌區域和其他區域，長寬比和歐拉數是最關鍵的區域特征。為了簡便起見，下文將連通區域簡稱為“斑塊”。斑塊的長寬比定義為該斑塊的外接矩形的長寬比。牌照的長寬比處在23之間，根據這一特征，可排除不滿足條件的斑塊。斑塊的歐拉數定義為斑塊內部所含有的閉合曲線數，也可理解為斑塊內部含有的“空洞”的數目。如下圖所示：圖7-5 字符“空洞”斑塊“A”內部僅有一個“空洞”，其歐拉數為1；斑塊“B”內部有兩個

15、“空洞”，其歐拉數為2。可以看到，經過SCW處理后，車牌斑塊由于大量字符的存在，使其內部存在與字符相對應的“空洞”，并且這些“空洞”滿足一定的大小要求。如下圖所示：圖7-6 淺底深字情況的處理結果字符“空洞”是車牌斑塊最重要的特性，由圖7-5可見，車牌斑塊內部存在7個左右和字符大小相近的“空洞”，其歐拉數約為7；而其他斑塊或者歐拉數太少，或者雖然有足夠的歐拉數，但“空洞”太大或者太小，不符合字符特征。根據斑塊歐拉數，可以準確地確定車牌區域。問題：對于淺底深字(如藍底黑字)的情況，經過SCW步驟后，車牌不成為一個斑塊，字符互相獨立。此時經過CCA步驟后，得到的車牌數為0。如下圖所示：圖7-7 淺

16、底深字問題解決后的效果解決方法：將原圖取反，再重復SCW和CCA步驟，即可得到車牌區域，如下圖所示：多尺度小波變換的邊緣點提取在幾種特征點提取算法中，基于多尺度小波變換的邊緣點提取方法，其適應性和抗噪性強，提取的特征點能有效的實現匹配，在自動配準中能廣泛的適用。缺點：小波變換是全局的變換，無法對圖像作分塊并行處理，計算復雜度高，對于大尺寸的圖像，只能采用基于金字塔結構的方法逐層提取和映射，減少計算量，提高運算速度。Harris算子是基于信號的點特征提取算子，給出了與自相關函數相聯系的矩陣M。M矩陣的特征值是自相關函數的一階曲率，如果2個曲率值都很高，就認為該點是特征點。Harris算子的公式只

17、涉及圖像的一階導數： (7-15)角響應公式： 式中， 是gx方向的梯度， 是gy方向的梯度，G為高斯模板，det為矩陣的行列式，tr為矩陣的直跡，k為默認常數。一般做法：若I大于某個給定的閾值時,即認為相應局部窗口的中心點是一個角點。Harris特征提取算子書中方法：在實際操作中，可依次從以每個像素為中心的33的窗口中提取最大值，如中心點像素的值就是最大值，則該點就是特征點。局部極值點的數目很多，可對極值點排序，根據要求選出興趣值最大的若干點作為最后的結果。Harris算子計算簡單，提取的點特征均勻合理，且可根據需要定量地提取特征點。在圖像發生旋轉、灰度發生變化、噪聲影響和視點變換的情況下，

18、Harris算子是最穩定的點特征提取算子。SIFT算法在圖像特征提取與匹配領域中，如何提取穩定的特征，提高匹配的準確度是一個關鍵的問題。下面介紹一種基于圖像特征點提取及匹配的方法，尺度不變特征變換(SIFT，Scale Invariant Feature Transform)算法。SIFT算法主要思想是利用多尺度變換在尺度空間中尋找極值點，提取特征點位置和方向，使其對圖像縮放、旋轉、光線變化甚至仿射變換保持不變。(1)圖像的多尺度表示為了模擬人類在不同距離觀察事物的過程，形成了多尺度空間方法。經研究發現高斯函數是唯一的尺度空間內核函數。SIFT算法定義圖像尺度空間函數為L(x, y, ) ，輸

19、入圖像用I(x, y) 表示，利用高斯內核函數對輸入圖像進行卷積操作，則有：其中， G(x, y, )為尺度可變高斯函數，具體如下：這里，(x，y)為空間坐標；為尺度坐標。采用不同的對圖像進行高斯卷積，得到高斯圖像金字塔，從而增強SIFT算法對于圖形縮放的適應能力。SIFT算法分析高斯差分(DOG，Difference of Gaussian)函數為其中k為常數。Mikolajczyk通過實驗發現相對于其他的特征提取函數，通過求高斯拉普拉斯函數 的最大和最小值能得到最穩定的圖像特征點，并且由于所以用DOG函數也可以得到最穩定的圖像特征點。每一個采樣點要和它所有的相鄰像素點進行比較，看是否為其所

20、在圖像域和尺度域的檢測鄰域中的極值點。從而SIFT算法能夠獲取穩定的圖像特征點。(2)求高斯差分空間極值DOG空間極值有對噪聲敏感的低對比度點和對邊緣響應敏感的邊緣響應點，必須去除。低對比度點去除：將尺度空間函數 D(x, y, )進行2階泰勒展開，求其導數并將其值設為0，則可以得到：將其加到其樣本點上從而得到在極值位置處的插值估計值將 小于某一閾值的點視為低對比度點去除。(3)去除低對比度點和邊緣響應點邊緣響應點去除一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。由于D的主曲率和Hessian矩陣H的特征值成正比，為了檢測主曲率是否在某域值

21、(為H陣最大特征值與最小特征值的比值)下，只需檢測Hessian矩陣（2階導數矩陣）：去除低對比度點和邊緣響應點，可提高SIFT算子的抗噪聲能力。(4)賦予特征點方向信息計算特征點(x，y)處梯度的模值和方向。在以特征點為中心的鄰域窗口內采樣，并用直方圖統計鄰域像素的梯度方向。直方圖的峰值代表了該特征點處鄰域梯度的主方向，即作為該特征點的方向。保證了SIFT算法特征點提取具有旋轉不變性，同時以子區域的統計特性代替單個像素作為研究對象，提高了對圖像局部變形的適應能力。賦予特征點算子描述符向量在特征點描述符生成過程中，在處理梯度幅度時進行了類似于高斯函數的加權處理，強化了中心區域，淡化了邊緣區域的

22、影響，提高了SIFT算子對幾何變形的適應性；最后將描述符向量長度歸一化，也減小SIFT算子對光照變化的影響。SIFT算法實現SIFT算法的實現包括4個步驟：(1) 檢測尺度空間極值點。首先創建DOG金字塔多尺度空間。在DOG空間中，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的92個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。通過以上方法獲取的特征點稱為候選特征點。(2) 精確確定極值點位置。將由式(7-21)計算出所有 D(X)中小于0.008的候選特征點視為低對比度候選極值點過濾掉。取=10，如果主曲率間的比值大于10，則認為該點是位于邊緣而被過濾掉，余下的則為

23、SIFT特征點。(3) 為每個特征點指定方向參數。梯度直方圖的范圍是0-360，取每10 一個柱，總共分36個柱進行方向直方圖的統計計算，為特征點賦予方向參數。(4) 特征點描述子的生成。首先將坐標軸旋轉為特征點的方向，對任意一個特征點，在其所在的尺度空間取以特征點為中心的1616大小的鄰域，再將此鄰域均勻地分為44個子區域，對每個子區域計算梯度方向直方圖(8個方向)；然后，對44個子區域的8方向梯度直方圖根據位置。每個直方圖有8方向的梯度方向，每一個描述符包含一個位于關鍵點附近的四個直方圖數組.這就導致了SIFT的特征向量有128維.先是一個44的來計算出一個直方圖，每個直方圖有8個方向。所

24、以是448=128維將這個向量歸一化之后，就進一步去除了光照的影響。7.4 改進算法序貫相似性檢測算法基于排序的序貫相關算法FFT的相關算法分層搜索的序貫判決算法序貫相似性檢測算法模板匹配算法效率很低，實際應用價值不高。原因是模板匹配算法對基準圖S的所有子區域一視同仁，全部都要運算檢驗。多數情況下，基準圖S上與模板相似的子區域并非那么多，這樣，過多的運算用在與匹配目標無關的子區域內，做了太多的無用功。下面介紹一種快速計算方法：序貫相似性檢測算法，簡稱SSDA。SSDA算法的基本思想是首先定義一個絕對誤差值 和一個恒定閾值 。 (7-23)其中，然后在子區域 中隨機選取像素點，并計算該像素點與T

25、中對應的像素點的誤差值 ，并將該值點同其他點對的誤差值進行累加。當算術和超過 時則停止累加，并記錄累加次數r。由此定義SSDA的檢測曲面為： (7-24)接下來把 值最大的點 定為匹配點，因為在這一點上需要很多次累加才能使總誤差超過 。如圖7-2所示，圖中的三條曲線分別表示在A、B、C三個參考點上得到的誤差累加增長情況。其中A、B才考點所反映出來的累計誤差 增長的結果很快超出了閾值 ，這就恰恰反映了模板T不再匹配點上。相反，曲線C中的 增長較為緩慢，因此它很可能是要尋找的匹配點。圖7-8 累計誤差增長曲線可以對SSDA算法做一些改進以期進一步提高計算效率，具體做法如下：(1) 對多有可能的匹配

26、點不逐個進行匹配，即模板不一定對每點都平移到。而按一定的策略，例如可用粗細結合的均勻搜索，即先每隔m個點搜索一下匹配的好壞，然后在有最大匹配值的像素點的周圍的局部范圍內對各個可能的匹配位置求匹配，而略過匹配值較小的像素點的周圍像素的匹配。這樣做可以大大減少計算量，但這種策略能否不丟失真正的匹配點主要取決于誤差曲面 的平滑性和單峰性。(2) 為了盡早排除掉那些非匹配點，在某個參考點 處，對模板覆蓋下的 個點對的計算順序，可用與i，j無關的隨機方式計算誤差。另外一個備選的方式是采用適應圖像內容的方式，按模板中突出特征選取偽隨機序列，由此決定計算誤差的先后順序。不選用固定的閾值 ，而采用單調增長的閾

27、值學列。這樣做可以是非匹配點用更少的計算就達到閾值而被排除掉，真正的匹配點則需要更多此的誤差累計才能達到閾值，如圖7-9所示。 圖7-9 采用閾值序列單調增加的方式改進SSDA算法SSDA算法比FFT的相關算法快50倍，是較受人重視的一種算法。特別地，當待搜索圖像為二進制圖時，SSDA算法還可以簡化，這是模板與對應子區域中的成對像素點的差值為： (7-25)其中 表示異或運算，由此得： (7-26)上式稱作二進制的Hamming距離，同樣當D越小，則子區域同模板的相似度越大。由前面的討論可知，任何一種匹配算法的計算量都是采用的相關算法的計算量與搜索區域數目之積來決定的，也就是說：總計算量=（相

28、關算法的計算量）（搜索區域數目）因此，為了減少總的計算量，除了上面介紹的匹配方法之外，我們再介紹幾種其他的快速計算法。上式稱作二進制的Hamming距離，同樣當D越小，則子區域同模板的相似度越大。由前面的討論可知，任何一種匹配算法的計算量都是采用的相關算法的計算量與搜索區域數目之積來決定的，也就是說：總計算量=（相關算法的計算量）（搜索區域數目）因此，為了減少總的計算量，除了上面介紹的匹配方法之外，我們再介紹幾種其他的快速計算法。基于排序的序貫相關算法這種算法的設計思想并不復雜，簡單地說就是在對圖像灰度進行二進制幅度排序的基礎上進行序貫匹配處理，因此算法共分兩步。第一個步驟稱為幅度排序預處理。

29、把模板中的各個灰度值按幅度大小排成列的形式，并計算出各自的位置坐標 ，然后對它進行二進制（或三進制）編碼。編碼的具體方式是逐層掃描并將每一層一分為二，分別賦值1或0，通常選擇幅度大的一組賦值為1，幅度小的一組賦值為0，如果存在某一層的項目數是一個奇數，那么就將該層的中間幅度賦值為 ，直到當各組所剩的元素不能再分為止。最后，根據二進位排序的諸列，把模板變換成二進制陣列的一個有序的集合 ，n=1，2，N。第二步是由粗到細的相關過程。順序地將這些二進制陣列與基準圖進行由粗到細的相關，直到確定匹配點為止。下面舉例說明具體的操作方式。假設存在一個3 3的圖像，如圖XX所示。首先將圖像的幅度按大小排序填入

30、表中，并將對應的位置也順次填入。可見幅度最大值是48，它對應的像素點位置是（1，1），幅度第二的值是41，它對應的位置是（3，3）然后進行分層編碼。因為共有9個幅度值，因此中間幅度值24被賦為 。這樣剩余的幅度選取較大的賦值為1，即表中前4位被編碼為1，后4位被編碼為0，記錄層號。然后對后4位的值再進行同樣的編碼，依次遞推，最終結果如圖7-10所示。最終得到的二進制序列分為三層，分別由、III來表示。圖7-10 圖像的幅度排序預處理得到二進制序列之后，便可以由此構造二進制陣列。二進制陣列是有序的集合 ，n=1，2，N，其中N是二進制排列的分層數，在這個例子中N=3。繼續上面的步驟，幅度是48的

31、像素點的位置是（1，1），二進制編碼是111。因此，在構造的3個二進制陣列 、 、 的（1，1）位置上分別填入1、1、1三個編碼值；幅度是41的像素點的位置是（3，3），二進制編碼是110。因此，在構造的3個二進制陣列 、 、 的（3，3）位置上分別填入1、1、0三個編碼值；依次類推最終得到的結果如圖7-11所示。圖7-11 二進制陣列下面是算法的第二個步驟，序貫地將得到的二進制陣列與基準圖進行由粗到細的關聯，直到找到匹配點為止。對于此例，首先用 陣列與基準圖進行如下運算，得： (7-27)上式的意義解釋為：當 陣列放在基準圖的某一搜索位置（u，v）上時，與 陣列中的1值相對的基準圖像素值之和

32、減去與 陣列中的0值相對的基準圖的像素值之和，這一計算將忽略與 陣列中的 號對應的基準圖像素元。 實際上是一比特量化模板與基準圖的積相關函數，它反映了圖像中最粗糙的圖像結構的信息（即一種高低表示）與基準圖的相關。 被稱為基本的相關面。上式的意義解釋為：當 陣列放在基準圖的某一搜索位置（u，v）上時，與 陣列中的1值相對的基準圖像素值之和減去與 陣列中的0值相對的基準圖的像素值之和，這一計算將忽略與 陣列中的 號對應的基準圖像素元。 實際上是一比特量化模板與基準圖的積相關函數，它反映了圖像中最粗糙的圖像結構的信息（即一種高低表示）與基準圖的相關。 被稱為基本的相關面。那么，如何通過基本的相關面來

33、減少計算量呢？方法是在基準圖全區域的檢索過程中，設定一個閾值 ，舍棄那些 的點，這樣可以很大程度地減少下一輪搜索的目標數。通過這樣的操作將更多的計算時間用在更有可能接近目標的區域上，對于 的點，需要進行更加細致的相關運算：(7-28)同理，在第二次搜索時也設定一個閾值 ，并在 的點上以 為基礎進行更仔細的運算： (7-29)再設閾值 等等，依此類推，可以得到第n個相關面為： (7-30) 當設閾值為 時，若 的點只有一個，則匹配完成，即點（u，v）為最佳匹配點。顯然，通過逐次細化，閾值將變得越來越小： (7-31)這樣相關的搜索點也會變得越來越少，這樣就達到了有效減少總體計算量，并提高相關的處

34、理速度的目的。這種二進制位的幅度排序算法（即BARC算法），所需要的加法總計算量為： (7-32)其中k是一個在1和2之間的常數，而L，W和l，w分別為基準圖和模板的尺寸。FFT的相關算法由傅里葉分析中的相關定理可知兩個函數在定義域中的卷積等于他們在頻域中的乘積，而相關則是卷積的一種特定形式。因此，存在著另一種計算相關函數的方法。雖然這樣在時間上并沒有縮短，但快速傅里葉變換技術比直接的模板匹配算法速度提高了一個數量級，因此用FFT進行頻域相關計算是一種可行的方法。首先把基準圖和模板進行二級離散傅里葉變換（DFT）。對于基準圖，有 (7-33)其中u和v分別表示J和其在方向上的頻率變量，且并假定

35、基準圖的尺寸是M M維的。模板的離散傅里葉變換y（u，v）是用同樣的方式計算得到的。然后，由相關定理可以寫出離散傅里葉變換 為： (7-34)為此，對 求傅里葉反變換，就可以得出空間域中的相關函數 為： (7-35)由此可見，相關函數可以通過DFT的方法計算出來，而計算DFT最有效的方法就是采用FFT算法，這種一般在教科書上都可以找到，所以這里略去對它的討論。最后根據以上的關系式，我們可以畫出FFT的相關算法流程圖，如圖7-12所示。顯然，這種相關算法可以容易地推廣到FFT的歸一化算法。如果被測試圖像的像素和試驗位置數越大的話，那么這種算法在時間上就更加節省了。但是要注意，由于傅里葉變換是個周

36、期函數，因此匹配點會以周期的形式出現，所以在運算時，必須采取其他適當的措施。 圖7-12 FFT相關算法分層搜索的序貫判決算法這種分層搜索算法是基于人們尋找事物的習慣而形成的，人們尋找事物是先從大范圍找起，再一步步往更細的方向尋找。例如在世界地圖上找我國首都北京的位置，總要先找到中國，這叫做粗相關；在這個區域內在仔細確定北京的位置，這叫做細相關。所以由這種思想形成的分層搜索算法具有相當搞的處理速度。如BARC算法一樣，它也是由兩個步驟組成的。第一步：分層預處理。首先，對被匹配的圖像進行分層預處理。方法是將圖2 2維的鄰區域逐個網絡地進行平均處理，從而得到一個分辨率更低和維數更小的圖像。然后，將

37、此圖像再用同樣的方法處理后，得到一個分辨率更低和維數更小的圖像，依次進行下去。如果一共進行了K次分層處理，那么我們就可以得到K個處理后的圖像。加上原圖像便可構成一組分辨力由高到低，而維數由大到小的圖像序列。這種技巧稱之為分層預處理。如果將上述分層技術應用與基準圖和模板，就可以獲得兩個這樣的圖像序列：一個是基準圖的，另一個是模板的。它們分別表示為：其中k=0，1，L，且已假設基準圖是M M維的，而模板是N N維的。因為原圖的分辨力最高且維數最大，所以k=0的圖像 和 具有最高的分辨力，k=L的圖像 和 則具有最低的分辨力。如前所述，若采用先粗后細的相關方法，則可以很快地找到匹配點。所以，第一次相

38、關搜索是從分辨力最低和維數最小的一對圖像 和 （K=L）開始的。這是，由于 的像素數比較少，加上損失了一部分高頻信息，所以在粗相關的過程中，正確截獲率 將是不大的。所以，為了提高 應設法改善 和 的信噪比。例如：將具有較高分辨力的 （或 ）通過低通濾波器以后，再以二倍于它的采樣間隔進行采樣，而得到的 （或 ）比用直接分層法得到的具有更高的信噪比。因此，相對提高了 。顯然，其他各層亦作同樣的處理。這種技術稱之為分層搜索預處理。第二步：先粗后細的相關過程。如前所述，第一次相關是從 和 開始的，為了找到可能的粗匹配位置，應將 在 的所有搜索位置上進行相關，并確定出粗匹配位置 。因為這時 和 的維數最

39、小，所以搜索過程是很快的，但這時 值較小，可能產生若干個粗匹配位置。第二次相關是在較高分辨力的圖像 和 之間進行的。這時，因為已經知道了可能的粗匹配位置，所以 只需要在 的一個或若干個粗匹配位置附近進行相關搜索就可以找出一個或者少數幾個可能性更大的匹配位置 。在上述相關過程中，為了不丟失匹配點，應在粗匹配位置 附近增加幾個補充試驗位置。顯然，第三次相關與第二次相關是類似的。如此進行下去，一直到最高分辨力的模板 在基準圖 上找到匹配位置時為止。由此可見，整個搜索過程是從最低分辨力到最高分辨力逐層地進行下去的，為了進一步提高處理速度，相關運算常常采用SSDA算法，這種技術成為分層搜索的序貫判決算法

40、。7.5 其它算法介紹基于對數極坐標變換的圖像匹配算法(1)相位相關法設兩幅離散圖像 和 在空間域存在簡單的平移關系： (7-39)相應的， 和 的傅里葉變換 和 是相關的： (7-40)則它們的互功率譜為： (7-41)這里 表示F復數的共軛。位移位置是在 。相位相關法就是求上式的傅里葉反變換，然后通過找峰值的位置確定平移參數 和 。當兩幅圖像確實相關時，由于檢測結果為一個 艿函數，存在較尖銳的檢測峰值，所以能實現圖像的精確匹配。而當兩幅圖像毫不相關時，檢測結果不會有明顯的峰值。因此可以利用這一點來區別兩幅圖像是否相關。當兩幅圖像間存在某一灰度差或僅有灰度反轉時，這種差別在檢測結果中只表現為

41、在 艿函數加一恒量，并不影響檢測結果。相位相關算法流程圖如圖7-13所示：圖7-13 相位相關算法流程圖(2)基于對數極坐標變換的圖像匹配算法對數極坐標變換圖像對數極坐標變換是將笛卡爾坐標系轉換至對數極坐標系，這樣笛卡爾坐標系下的圖像匹配為對數極坐標下的圖像匹配，原坐標系下的尺度和旋轉變換，相應地轉化為平移變換，利用相位相關法可以將尺度和旋轉角度檢測出來。圖像 到 的對數極坐標變換定義為： (7-42) (7-43)式中， 分別對應對數極坐標系的極徑和極角， 為變換中心。對數極坐標變換關系如圖7-14所示。圖7-14 圖像對數極坐標變換示意圖基于對數極坐標變換的相位相關法設兩幅離散圖像 和 在

42、空間域存在以 為參數的尺度變換和旋轉角度為 的旋轉變換： (7-44)則經過對數極坐標變換后得到： (7-45)從上式中可以看出，經過對數極坐標變換后， 相對于 只存在平移關系，因此可以利用相位相關法獲得 和旋轉角度 ，從而進一步獲得縮放尺度 。基于對數極坐標變換的相位相關法流程圖如圖7-15所示：圖7-15 基于對數極坐標變換的相位相關法流程圖不同分辨率圖像的角點匹配方法(1)圖像的多尺度表示及角點檢測首先構造高分辨率圖像的高斯金字塔圖像，得到高分辨率圖像的多尺度表示。高斯金字塔是由原圖像經過連續高斯濾波和二次采樣生成的一系列不同分辨率的圖像組成。金字塔圖像從底層到頂層尺寸連續減小，分辨率連

43、續降低。圖像尺寸的迅速減小，有利于減少后續處理中的計算量。為計算簡便，高斯金字塔往往利用幾幅不同尺度的圖像來代替某個較大尺度范圍內的所有尺度圖像，在尺度量化上較為粗糙。在得到的金字塔各尺度圖像上分別提取角點。角點檢測算法中比較著名的有Harris算子和SUSAN算子，實驗研究證明，在角點檢測穩定性上Harris算子要優于SUSAN算子，這對于圖像的角點匹配非常有利，因而作者選用Harris算子進行角點檢測。對于金字塔的第l層圖像函數 ，在點 處的自相關矩陣為： (7-46)式中 ， 為H的特征值。若 大于設定閾值且為鄰域極大值，則將點 視為角點。(2)角點特征的提取為有效匹配角點，需要進一步提取角點處的局部圖像特征。一種最為簡單的方法是直接提取角點周圍一定區域內的灰度值向量，然后進行歸一化等處理，匹配時采用灰度互相關方法。這種方法要用很多像素點，導致匹配時的計算量很大，且對圖像幾何變形及灰度畸變比較敏感。文獻中都采用高斯差分不變量作為特征描述方法，這種特征雖然計算簡單，但是匹配性能不強，又容易受噪聲的影響。此外，還有利用圖像局部區域的矩不變量，像素點位置分布的直方圖等方法。Lowe等在研究尺度不變特征時提出了一種稱為SIFT(scale invariant