基于圖像邊緣摘要的快速模板匹配

（重慶大學計算機學院，重慶 400044）



摘 要：

基于多邊形逼近和形狀簽名的思想，提取圖像邊緣摘要，并利用其進行圖像模板匹配。首先對原始圖像邊緣上的大量像素點進行統計，然后將其轉換為少量帶有權重和方向的錨點，這些錨點即組成了圖像邊緣摘要。圖像邊緣摘要具有縮放、旋轉、位移不變性，利用其進行模板匹配能夠降低噪聲的影響并減少計算時間。通過實驗驗證了該算法的有效性。

關鍵詞：圖像邊緣摘要； 錨點； 模板匹配

中圖分類號：TP391.41 文獻標志碼：A

文章編號：1001-3695(2009)02-0792-03



Image edge abstract-based fast template matching



ZHU Qing-sheng， YANG Shi-quan， LIU Feng

(College of Computer Science， Chongqing University， Chongqing 400044， China)



Abstract:Base on shape signature and polygon approximation， this paper presented a fast template matching approach-template matching based on image edge abstract (TMIEA). TEIEA was implemented as following three steps: adopted polygon to approximate continuous edges of original image; transformed each edge of polygon to AP with weight and direction， then IEA， which was invariant to resize， rotate and translate，was built on the set of anchor points; ran template matching withIEA. Several tests were performed and the results proved that the presented approach has lower computation cost and less sensitivity to noise.

Key words：image edge abstract(IEA); anchor point(AP); template matching



目標識別是機器視覺研究中的一個重要內容。在現有的目標識別方法中，圖像模板匹配是一項廣泛采用的技術。圖像模板可以是剛性模板（rigid template）或變形模板（deformable template），而變形模板又可以分為基于參數的和基于模型的。基于模型的變形模板就是使用現有的圖像作為模板[1]或從現有的圖像中學習一個模板[2]，這種方法因其具有較強的適應性得到了很多研究者的青睞，本文即使用現有圖像作為圖像模板。

現有的圖像匹配算法大多采用點匹配（point matching）的模式，采用像素點之間的距離作為模板與原始圖像的相似度。其中文獻[1]在計算相似度時考慮了距離像素點最近的邊緣切線方向，而文獻[3]則使用了窗口邊緣能量函數（window edge potential function）來計算相似度，這些方法減少了噪聲在匹配過程中的影響，提高了識別能力，但其本質仍然是基于點匹配的。本文基于多邊形逼近（polygon approximation）和形狀簽名[4]（shape signature）的思想，利用鏈碼表達圖像邊緣，進而生成圖像邊緣摘要（IEA）；最后使用圖像摘要代替原始圖像進行模板匹配，在一定程度上減少了計算量并提高了系統對噪聲的魯棒性。系統框架如圖1所示。

1 圖像邊緣摘要

圖像邊緣摘要的核心思想是多邊形對曲線邊緣具有良好的描述能力，通過調整多邊形的相鄰邊長之間的轉向角等參數，多邊形可以任意精度逼近一條曲線[5]。

本文將使用八方向鏈碼來描述圖像邊緣，八個方向C={1，2，3，4，5，6，7，8}。下文如無特殊說明，斜率即表示鏈碼方向。本文約定像素點表達方式如下：P=(x，y，s)。其中：(x，y)為該像素點的行標和列標；s為該像素點到相鄰像素點的斜率，s∈C。

1.1 圖像邊緣摘要的提取算法

圖像邊緣摘要的提取算法可以描述為：

a)使用多邊形L逼近連續邊緣E[4]；

b)將多邊形L的每條邊Lh(0＜h≤H)轉換成帶有權重和方向的錨點MPh(Xh，Yh，Wh，Sh)，計算方法見式（1）;

c)錨點序列SM={MP0，MP1，…，MPH}組成了邊緣E的摘要；

d)對圖像中每條邊緣提取摘要，則得到整幅圖像的邊緣摘要。

Wh=Jh-Jh-1

Xh=1/（Jh-Jh-1）∑Jhi=Jh-1xi

Yh=1/（Jh-Jh-1）∑Jhi=Jh-1yi

Sh=1/（Jh-Jh-1）∑Jhi=Jh-1si=sh(h∈{Jh-1，…，Jh})

(1)



其中：Jh表示多邊形Lh第h條邊的終節點在邊緣E上的位置索引；(xi，yi)表示邊緣E上的像素行列索引。

錨點MPh的各個屬性含義為(Xh，Yh)是Lh中所有像素的行列索引均值；Wh是錨點的權重，即Lh的長度，離散化表示就是Lh上像素點的個數；Sh代表是錨點的方向，即位于Lh上的所有像素點斜率的均值，因為多邊形每條邊都是直線，所以該條邊上的所有像素點斜率是一樣的，Sh=sh。該屬性能夠描述邊緣的形狀變化。

現在任何一條邊緣E可以使用錨點序列SM來表示，E≈SM={MP0，MP1，…，MPH}。提取圖像邊緣摘要的具體示例如圖2所示。首先使用多邊形逼近原圖，然后根據式（1）將多邊形每條邊轉換為錨點，圖像任意一條邊緣的錨點的集合即該邊緣的邊緣摘要。

2. 2 位移、縮放、旋轉不變性證明

下面考察當圖像發生位移、縮放、旋轉時，錨點MPh的各個屬性發生的變化。當邊緣E發生位移(a，b)、縮放ξ、旋轉θ時，E上任意一像素點(xi，yi)的坐標將變化為

[xi，yi 1]×

ξcom(θ)sin(θ)

-sin(θ)ξcos(θ)

ab=

[x′i y′i]

(2)



該像素點所在的邊緣片段形成的錨點MPh將變化為

W′h=J′h-J′h-1=ξJh-ξJh-1=ξWh

X′h=1/(J′h-J′h-1)∑J′hi=Jh-1x′i

Y′h=1/(J′h-J′h-1)∑J′hi=Jh-1y′i

S′h=1/(J′h-J′h-1)∑J′hi=Jh-1s′i=s′h=sh+θ=Sh+θ



從上面的變化看出，如果使用Sh的差分，即SC={S1-S0，S2-S1，…，SH-SH-1}來表示圖像形狀信息，則當邊緣發生位移、縮放、旋轉時，其差分將保持不變，證明見下。

因為邊緣發生位移、縮放時，錨點方向S′h保持不變，錨點方向的差分SC也會保持不變，只需考察邊緣發生旋轉時其錨點方向的差分變化情況即可。

SC′={S′1-S′0， S′2-S′1，…，S′H-S′H-1}=

{(S1+θ)-(S0+θ)，…，(SH+θ)-(SH-1+θ)}=

{S1-S0，S2-S1，…，SH-SH-1}=SC



從而在理論上證明了錨點序列SM的差分SC具備位移不變性、縮放不變性、旋轉不變性。

2 相似度計算

將上文描述的方法分別應用在模板T和原始圖像I上，就得到了各自的邊緣摘要。下面公式中相應的屬性前加I表示原始圖像，加T表示模板。原始圖像上有K條邊緣，得到K條錨點序列，ISM={SM0，SM1，…，SMK}，模板上有一條邊緣（適用于大部分模板匹配應用），得到一條錨點序列TSM={TM0}。原始圖像上任意一個錨點IMPh=(IXIh， IYIh， IWIh， ISIh)與模板上任意一個錨點TMPh=(TXIh，TYIh，TWIh，TSIh)的相似度定義[1，3]為

sim(IMPIh，TMPTh)=

[c1×e-|IWIh-TWTh|+c2×cos(|ISCIh-TSCTh|)]/

c3×(LXIh-TXTh)2+(IYIh-TYTh)2



其中：c1、c2、c3表示位移、縮放、旋轉各自的權重，0≤c1，c2，c3≤1；sim(IMPh，TMPh′)的取值范圍在(0，+∞)，為了計算方便，定義相似度的目標函數為

F(IMPIh，TMPTh)=e-1×sim(IMPIh，TMPTh)(5)

F(IMPIh， TMPTh)的取值范圍為(0，1)，只需求目標函數的最小值即可。

以式(5)為前提，原始圖像上任意一條邊緣IEk與模板上的邊緣TE0之間的目標函數定義為

sim(IEk，TE0)=∑IH，THIh=0，Th=0F(IMPIh，TMPTh)(6)



則原始圖像與圖像模板之間的目標函數定義為

sim(I，T)=min(sim(IEk，TE0));0≤k≤K

(7)



通過生成圖像的邊緣摘要，將圖像匹配的問題轉換為序列匹配的問題，只需在原始圖像形成的序列集合中尋找與模板序列的目標函數最小值即可。

3 實驗結果及分析

基于圖像邊緣摘要的匹配方法在計算過程中沒有直接利用像素點信息，而是利用其統計信息將斜率相似的像素點轉換為帶有方向的錨點進行模板匹配，這樣做的優點有兩個，即快速和對噪聲有較強的抵抗能力。下面將從邊緣摘要的描述能力、匹配效果、匹配速度三個方面驗證基于圖像邊緣摘要匹配算法的有效性。實驗圖像如圖3、4所示。

3. 1 IEA的描述能力

本文采用逐像素的窮舉搜索策略來驗證IEA的描述能力。圖4展示了在加入噪聲前后圖像模板與原始圖像在不同位置下的相似度的大小，圖5為圖3加入椒鹽噪聲后的結果。從圖6(a)中可以觀察到，在加入噪聲前出現兩個峰值，分別代表圖3(b)中兩個與模板相似的圖形。其中一個峰值明顯高于另外一個，表示該算法能夠識別出與模板最為相似的圖形。加入噪聲之后，從圖6(b)中仍然可以觀察到兩個峰值，且兩個峰值很容易進行區分，說明圖像邊緣摘要算法對噪聲具有較強的抵抗能力。基于邊緣摘要算法對噪聲不敏感的主要原因在于兩點：a）多邊形逼近過程中可以消除絕大部分獨立的噪聲點和幾個噪聲點連接而成的微小噪聲區域；b）生成錨點（AP）序列的過程中大量利用了邊緣像素點的統計信息，這在很大程度上減少了不光滑邊緣對后續匹配過程的影響。

3. 2 匹配效果

圖3的基于IEA的匹配過程如圖7所示。

根據上文描述的理論，匹配過程描述如下：圖7（a）首先根據原始圖像中相似邊緣（目標邊緣）的方向調整角度為（b），需要旋轉的角度θ即模板邊緣與目標邊緣錨點序列的斜率差；然后縮放到與目標邊緣大小一致（c），縮放的比例即模板邊緣與目標邊緣模板序列的權重比值；最后，（d）通過位移定位目標，位移量即模板邊緣與目標邊緣錨點序列的距離。圖8展示了采用點匹配的方式[3]對圖3的匹配結果，可以看出，基于邊緣摘要的匹配效果不比傳統基于點匹配的效果差。

3. 3 匹配速度

基于IEA的匹配算法耗費時間包括兩個部分，即生成圖像邊緣摘要和計算相似度來完成匹配。表1展示了單目標和多目標圖像匹配的實驗結果。實驗一針對類似圖3的10幅圖像，在原始圖像中搜索單個目標；實驗二針對類似圖4的10幅圖像，在原始圖像中搜索多個目標。顯然，基于圖像邊緣摘要的匹配效果（以查準率和查全率計算）與基于像素點的匹配效果非常接近，但是大大減少了計算時間。

基于IEA的匹配算法計算時間大大減少的原因有兩點：a)組成IEA的錨點個數遠遠小于組成圖像邊緣的像素個數（一般會相差一個數量級），如圖3(a)邊緣的像素個數380，而組成邊緣摘要的錨點個數為15，因此使用IEA代替圖像邊緣進行匹配減少了匹配過程的計算量；b)基于像素點（Pixel）的匹配過程采用啟發式的方法搜索目標可能發生的位移、縮放、旋轉、變形，而基于IEA的匹配算法具有位移、縮放、旋轉不變性，僅僅需要考慮模板變形即可，將搜索空間從四維降低到一維，減少了搜索時間。另外，原始圖像的邊緣摘要IEA還可以事先計算好存儲在數據庫中以便后續計算，這樣在匹配過程中又可以進一步節省計算時間。

表1 基于IEA和基于Pixel匹配的計算時間比較

匹配算法匹配時間/s查準率/%查全率/%

IEA0.94+0.269690

Pixel 8.429790

IEA0.42+0.149785

Pixel 7.319688

４ 結束語

本文敘述了如何使用IEA代替圖像邊緣進行模板匹配的

方法，并給出了模板與原始圖像之間相似度計算的公式。IEA是圖像邊緣的近似表達，能夠使用很少的信息描述一幅圖像

中所有連續邊緣的位置、長度、方向信息。基于IEA的匹配與傳統基于像素點的匹配過程比較主要有兩個優點：a)利用了像素點的統計信息，一定程度上減少了噪聲的影響；b)組成IEA的錨點數量大大小于圖像邊緣上的像素數量，減少了計算時間。實驗證明，基于IEA的匹配方法在保證匹配效果的前提下，能夠減少計算時間并增強對噪聲的魯棒性。本文提出的方法對邊緣比較規則的圖像具有較好的匹配結果，而對于邊緣復雜的圖像，生成的錨點數量與圖像本身的像素個數相差極少。因此，本算法的計算效率將降低到傳統基于像素點的匹配算法。理論上，本文敘述的方法同樣適應于灰度圖像和彩色圖像，只需要對錨點的屬性進行擴充，即加入相應的亮度、紋理信息等即可，這也是筆者未來研究的方向。

參考文獻：

[1]JAIN A K， ZHONG Y， LAKSHMANAN S. Object matching using deformable template[J]. IEEE Pattern Analysis and Machine Intelligence，1996，18(3):267.

[2]FELZENZWALB P.Representation and detection of deformable shapes[J]. IEEE Pattern Analysis and Machine Intelligence， 2005，27(2):208.

[3]DAO M S， NATALE F D， MASSA A. Edge potential function (EPF) and genetic algorithms(GA) for edge-based matching of visual object[J]. IEEE MultimediaMagazine， 2007，9(1):120.

[4]SCHRODER K， LAURENT P. Efficient polygon approximations for shape signatures[J]. IEEE Image Processing，1999，2(1):811-814.

[5]ZIMMER Y， TEPPER R， AKSELROD S. An improved method to compute the convex hull of a share in a binary image[J]. Elsevier Pattern Recognition，1997，30(2):397-402.

[6]WOLFSON H J.On curve matching[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，1990，12(5):483-489.