【文章內(nèi)容簡(jiǎn)介】 兩種基本方法進(jìn)行簡(jiǎn)單的比較 。 圖像匹配技術(shù) 應(yīng)用領(lǐng)域 圖像匹配技術(shù) [1,5]廣泛的應(yīng)用于 日常生活中的諸多領(lǐng)域，如目標(biāo)識(shí)別與跟蹤、立體視覺、變化檢測(cè)、車場(chǎng)車牌識(shí)別、人臉識(shí)別、機(jī)器人導(dǎo)航、測(cè)繪等。 圖像匹配技術(shù) [5]主要是指通過計(jì)算機(jī)，采用數(shù)學(xué)技術(shù)方法，對(duì)獲取的圖像按照特定目的進(jìn)行相應(yīng)的處理。圖像匹配技術(shù)是人工智能的一個(gè)重要分支和應(yīng)用。隨著計(jì)算機(jī)技術(shù)和人工智能技術(shù)的發(fā)展，圖像識(shí)別技術(shù)逐漸成為人工智能的基礎(chǔ)技術(shù)之一。它涉及的技術(shù)領(lǐng)域相當(dāng)?shù)膹V泛，也越來越深入，其基本方法也隨著數(shù)學(xué)工具的不斷進(jìn)步而不斷發(fā)展?，F(xiàn)在，圖像識(shí)別技術(shù)的應(yīng)用范圍已經(jīng)不僅局限于視覺的范圍，也體現(xiàn)在機(jī)器智能和數(shù)字技術(shù)等方面。 圖像匹配算法分類 圖像匹配是圖像信息處理領(lǐng)域中的一項(xiàng)非常重要的技術(shù)，人們對(duì)圖像匹配技術(shù)已進(jìn)行了較為深入的研究，并提出了許多有效的圖像匹配算法。然而數(shù)字圖像匹配都是計(jì)算密集型的，任何一種匹配算法，總的計(jì)算量是由所采用的相關(guān)算法的計(jì)算量和搜索位置(實(shí)驗(yàn)位置 )數(shù)之積決定的，即： 總的計(jì)算量 =相關(guān)算法的計(jì)算量搜索位置數(shù) 因此為了減少總的計(jì)算量，即為了提高處理的速度，采取的措施一方面是設(shè)法減少相關(guān)算法的計(jì)算量，例如采用簡(jiǎn)單的算法，一般只涉及加減運(yùn)算，同時(shí)使用一些簡(jiǎn)單的準(zhǔn)則函數(shù)：另一方面是減少搜索位置的數(shù)目，例如采用 數(shù)據(jù)壓縮的預(yù)處理方法或者利用像素相關(guān)性減少匹配點(diǎn)數(shù)；或者二者兼而有之。 圖像匹配算法 [4]的選取對(duì)圖像匹配結(jié)果影響很大。使用的匹配算法不僅僅要求計(jì)算量小，還必須具有良好的抗噪能力和抗幾何形變的能力。通常情況下，圖像匹配算法可分為以下兩大類：基于灰度相關(guān)的匹配算法和基于特征的圖像匹配算法。 基于灰度相關(guān)的匹配算法 7 基于灰度的匹配的方法已經(jīng)研究了近 20 年，算法相對(duì)來講已經(jīng)比較成熟，這是一種將共軛圖像以一定大小的窗口灰度陣列，按某種或幾種相似性測(cè)度來逐像素地順序進(jìn)行搜索匹配的方法。 灰度匹配的基本思想 ： 以統(tǒng)計(jì)的觀點(diǎn)將圖像看成是二維信號(hào)，采用統(tǒng)計(jì)相關(guān)的方法尋找信號(hào)間的相關(guān)匹配。利用兩個(gè)信號(hào)的相關(guān)函數(shù)，評(píng)價(jià)它們的相似性以確定同名點(diǎn)。 灰度匹配通過利用某種相似性度量，如相關(guān)函數(shù)、協(xié)方差函數(shù)、差平方和、差絕對(duì)值和等測(cè)度極值，判定兩幅圖像中的對(duì)應(yīng)關(guān)系。 最經(jīng)典的灰度匹配法是歸一化的灰度匹配法，其基本原理是逐像素 地 把一個(gè)以一定大小的實(shí)時(shí)圖像窗口的灰度矩陣，與參考圖像的所有可能的窗口灰度陣列，按某種相似性度量方法進(jìn)行搜索比較的匹配方法，從理論上說就是采用圖像相關(guān)技術(shù)。 利用灰度信息匹配方法的主要缺陷是計(jì)算量太大，因?yàn)?使用場(chǎng)合一般都有一定的速度要求，所以這些方法很少被使用?，F(xiàn)在已經(jīng)提出了一些相關(guān)的快速算法，如幅度排序相關(guān)算法， FFT 相關(guān)算法和分層搜索的序列判斷算法等。 基于特征的圖像匹配算法 特征匹配是指通過分別提取兩個(gè)或多個(gè)圖像的特征（點(diǎn)、線、面等特征），對(duì)特征進(jìn)行參數(shù)描述，然后運(yùn)用所描述的參數(shù)來進(jìn)行匹配的一種算法?；谔卣鞯钠ヅ渌幚淼膱D像一般包含的特征有顏色特征、紋理特征、形狀特征、空間位置特征等。 特征匹配首先對(duì)圖像進(jìn)行預(yù)處理來提取其高層次的特征，然后建立兩幅圖像之間特征的匹配對(duì)應(yīng)關(guān)系，通常使用的特征 基元有點(diǎn)特征、邊緣特征和區(qū)域特征。特征匹配需要用到許多諸如矩陣的運(yùn)算、梯度的求解、還有傅立葉變換和泰勒展開等數(shù)學(xué)運(yùn)算。 常用的特征提取與匹配方法有：統(tǒng)計(jì)方法、幾何法、模型法、信號(hào)處理法、邊界特征法、傅氏形狀描述法、幾何參數(shù)法、形狀不變矩法等。 基于 圖像 特征的匹配方法可以克服利用 圖像 灰度信息進(jìn)行匹配的缺點(diǎn)，由于 圖像 的特征點(diǎn)比 較像素 點(diǎn)要少很多，大大減少了匹配過程的計(jì)算量 ； 同時(shí)，特征點(diǎn)的匹配度量值對(duì)位置的變化比較敏感，可以大大提高匹配的精確程度 ； 而且，特征點(diǎn)的提取過程可以減少噪聲的影響，對(duì)灰度變化 、圖像 形變以及 旋 轉(zhuǎn) 等都有較好的適應(yīng)能力 ， 所以基于圖像 特征的匹配在實(shí)際中的應(yīng)用越來越廣泛。所使用的特征基元有點(diǎn)特征 (明顯點(diǎn)，角點(diǎn)，邊緣點(diǎn)等 )，邊緣線段等。 兩類匹配算法的 比較 特征匹配與灰度匹配的區(qū)別：灰度匹配是基于像素的，特征匹配則是基于區(qū)域的， 8 特征匹配在考慮像素灰度的同時(shí)還應(yīng)考慮諸如空間整體特征、空間關(guān)系等因素。 特征是 圖像 內(nèi)容最抽象的描述，與基于灰度的匹配方法相比，特征相對(duì)于幾何 圖像和輻射度影響來說更不易變化，但特征提取方法的計(jì)算代價(jià)通常較大，并且需要一些自由參數(shù)和事先按照經(jīng)驗(yàn)選取的閾值，因而不便于實(shí)時(shí)應(yīng)用 。同時(shí)，在紋理較少的 圖像 區(qū)域提取的特征的密度通常比較稀少，使局部特征的提取比較困難。 本章小結(jié) 本章簡(jiǎn)要介紹了圖像匹配的基本概念以及兩種基本圖像匹配方法即基于灰度相關(guān)的匹配算法和基于特征的圖像匹配算法，并且簡(jiǎn)單進(jìn)行了比較。為后面將要描述的匹配算法做了鋪墊。圖 21 是圖像匹配流程圖。 圖 21 圖像匹配流程圖 9 第 3 章 基于灰度的圖像匹配 圖像的像素灰度值信息包含了圖像記錄的所有信息 。 基于圖像像素灰度值的匹配是最基本的匹配算法思想 。 通常直接利用整幅圖像的灰度信息建立兩幅圖像之間的相似性度量，然后采 用某種搜索方法尋找使相似性度量值最大或最小的變換模型的參數(shù)值 。 常用的相似性度量有 ： ① 兩幅圖像灰度的平方差之和 ② 互相關(guān) ③ 相位相關(guān) 基于圖像灰度的 匹配 方法不需要對(duì)圖像做特征提取而是直接利用全部可用的圖像灰度信息因此能提高估計(jì)的精度和魯棒性。但由于在基于圖像灰度的算法 (如互相關(guān)算法 )中把匹配點(diǎn)周圍區(qū)域的點(diǎn)的灰度都考慮進(jìn)來進(jìn)行 計(jì)算因此其計(jì)算量很大速度較慢。 MAD 算法 MAD 算法 [6]即平均絕對(duì)差算法，是 Leese 最早提出來的一種匹配算法。設(shè)搜索圖 S為 M M，模板圖 T 為 N N，如圖 31[6]所示 ： (a)搜索圖 S (b)模板圖 T 圖 31 搜索圖 S 和模板圖 T 則 MAD 算法可定義為 公式（ 31）： ? ?? ????? MiNjjiTyjxiSMNyxd1 1),(),(1),( (31) 其中 d(x， y)為相似性度量函數(shù)在偏移量為 (x， y)時(shí)的匹配度量值，當(dāng) d(x， y)取值最小時(shí)認(rèn)為 (x， y)是最佳匹配位置。 10 很顯然，這種方法計(jì)算過程非常簡(jiǎn)單，無需復(fù)雜的乘除法運(yùn)算，但是對(duì)噪聲比較敏感，在加噪聲的情況下，匹配準(zhǔn)確率隨著信噪比的增加而減少。 序貫性檢測(cè)匹配算法 (SSDA) 序貫相似性檢測(cè)算法 (SSDA)是針對(duì)傳統(tǒng)模板匹配算法提出的一種高效的圖像匹配算法 ， 在該算法中引進(jìn)了閾值 ， 即模板與其覆蓋下的搜索子圖的像素差值的上限值 。 提出的基于 SSDA 的加速算法 ， 是在此基礎(chǔ)上 ， 引入了 模板與其覆蓋下的搜索子圖的像素差值的最低門限值 ， 如果該最低門限值超過了閾值 ， 則可以跳過該搜索子圖 。 實(shí)驗(yàn)證明 ：該算法比傳統(tǒng)的 SSDA 算法在速度上有所提高 [7]。 序貫性相似檢測(cè)匹配算法描述 傳統(tǒng)模板匹配算法在每個(gè)待匹配位置上都要做 N2(N 為模板的大小 ， 如圖 31 所示 )次相關(guān)計(jì)算 ， 計(jì)算量很大 。為 了減少在每個(gè)待匹配位置上的計(jì)算量 ， 人們提出了序貫相似性檢測(cè)算法 。 序貫相似性檢測(cè)算法是對(duì)傳統(tǒng)模板匹配算法的改進(jìn) ， 其要點(diǎn)如下 ： 設(shè)模板 T 疊放在搜索圖 S 上平移 ， 模板覆蓋下的那塊搜索圖設(shè)為子圖 jiS, ， i、 j 為這塊子圖的左上角像點(diǎn)在 S 圖中的坐標(biāo) ， 則 i 和 j 的取值范圍為 1≤i、 j≤MN+1， 如圖31 所示 。 ① 定義絕對(duì)誤差值 公式（ 32）： TmnTjiSmnSmnji kkjikk ???? ),(),(),(),( ,? （ 32） 其中 ： ),(, jiS ji 為模板覆蓋下 的搜索子圖的像素平均值 ， T 為模板位圖像素的平均值 。 ? ?? ?? ?? ???NnNmNnNmjimntNTmnsNjiS1 121 1,2),(1),(1),( ② 取一個(gè)不變的閾值 kT ③ 在子圖中 ),(, mnS ji 隨機(jī)選 取像素點(diǎn) ， 計(jì)算它同 T 中對(duì)應(yīng)點(diǎn)的誤差值 ? ， 然后把這點(diǎn)的差值同其他點(diǎn)對(duì)的差值累加起來 ， 當(dāng)累加 R 次誤差超過 kT ， 則停止累加 ， 并記下累加次數(shù) R， 定義 SSDA 的檢測(cè)曲面為 公式（ 33）： ?????? ?????? ?? ???? krk kknRTmnjiRjiI11),(m i n),( 2 ? （ 33） ④ 把 I(i， j)值最大的點(diǎn)定為匹配點(diǎn) ， 因?yàn)樵谶@一點(diǎn)上需要很多次累加才能使總誤 11 差 ?? 超過 kT 如圖 32[7]所示 ： 圖 32 累計(jì)誤差增長(zhǎng)曲線 圖 32 中給出了在 A、 B、 C 三個(gè)參考點(diǎn)上得到的誤差累計(jì)增長(zhǎng)曲線 .A、 B 反映模板 T 不在匹配點(diǎn)上 ， 這時(shí) ?? 隨累加次數(shù)的增加 ， 增長(zhǎng)很快 ， 很快超出閾值 kT 。而曲線 C 中 ?? 隨累加次數(shù)的增加 ， 增長(zhǎng)較慢 ， 很可能是一套準(zhǔn)候選點(diǎn) 。 序貫性相似檢測(cè)匹配步驟 ① 獲得待匹配圖像、模板圖像數(shù)據(jù)的地址、存儲(chǔ)的高度和寬度。 ② 建立一個(gè)目標(biāo)圖像指針，并分配內(nèi)存，以保存匹配完成后的圖像，將待匹配圖像復(fù)制到目標(biāo)圖像中。 ③ 逐個(gè)掃描原圖像中的像素點(diǎn)對(duì)應(yīng)的模板子圖，根據(jù)上面公式求出每一個(gè)像素點(diǎn)位置絕對(duì)誤差值，當(dāng)絕對(duì)誤差值超過閾值時(shí)，停止累加，記錄像素點(diǎn)的位置和累加的次數(shù)。 ④ 循環(huán)步驟 ③ ，知道處理完源圖像的全部像素點(diǎn)，累加次數(shù)最少的像素點(diǎn)為最佳匹配點(diǎn) 。 ⑤ 將目標(biāo)圖像所有像素值減半以便和原圖區(qū)別，把模板圖像復(fù)制到目標(biāo)圖中步驟④ 中記錄的像素點(diǎn)位置。 歸一化積匹配算法 歸一化互相關(guān)匹配算法 [6]是一種經(jīng)典的統(tǒng)計(jì)匹配算法，經(jīng)常寫為 NC(Normalized 12 Correlation)算法。 歸一化積匹配就是根據(jù)已知的模板圖像到另一幅圖像中尋找相應(yīng)位置的處理方法。簡(jiǎn)單而言，模板就是事先給定的一幅小圖像，歸一化積匹配就是在一幅大圖像中尋找 該模板圖像，也即已知該大圖像中有要查找的目標(biāo)，且該目標(biāo)與模板具有相同的方向或者存在較小角度的旋轉(zhuǎn)，我們可以通過一定的算法在圖中找到該目標(biāo)，并確定其坐標(biāo)位置。 歸一化積匹配原理 誤差平方和是灰度匹配經(jīng)常用到的一個(gè)相似性測(cè)度，即基準(zhǔn)圖與模板圖對(duì)應(yīng)區(qū)域的誤差平方和。設(shè) f(x， y)為 NM? 的基準(zhǔn)圖， t(j， k)為 ),( NKMJKJ ??? 的模板圖像 ，則誤差平方和測(cè)度定義 為 公式（ 34）： ? ?? ????????? 10102),(),(),( jjkkkjtkyjxfyxD （ 34） 展開得 公式（ 35）： ? ? ? ?? ? ? ?? ? ??????????????????? 10101010210102 ),(),().,(2),(),( jjkkjjkkjjkkkjtkjtkyjxfkyjxfyxD （ 35） 令 ： ? ?? ?? ????????????????????10102101010102)],([),()],().,([2),()],([),(jjkkjjkkjjkkkjtyxDTkjtkyjxfyxDS TkyjxfyxDS DS(x， y)與像素位置 (x， y)有關(guān)，但隨像素位置 (x， y)的變化， DS(x， y)變化緩慢。DST(x， y)隨像素位置 (x， y)的變化而變化，當(dāng)模板 t(j， k)和基準(zhǔn)圖中對(duì)應(yīng)區(qū)域相匹配時(shí)取最大值。 DT(x， y)與圖像像素位置 (x， y)無關(guān)只用一次計(jì)算便可。顯然，計(jì)算誤差平方和測(cè)度可以減少計(jì)算量。 基于上述分析，若設(shè) DS(x， y)也為常數(shù)，則用 DST(x， y)便可進(jìn)行圖像匹配，當(dāng)DST(x， y)取最大值時(shí)，便可認(rèn)為模板與圖像是匹配的。但假設(shè) DS(x， y)為常數(shù)會(huì)產(chǎn)生誤差，嚴(yán)重時(shí)將無法下確匹配，因此可用去均值歸一化互相關(guān)作為誤差平方和測(cè)度，其定義為 公式（ 36）： 基于灰度互相關(guān)算法的匹配示意圖中假設(shè)基準(zhǔn)圖 f (x， y)和模板圖像 t(j， k)的原點(diǎn) 13 都在左上角。對(duì)任何一個(gè) f(x， y)中的