模板匹配問題的動態(tài)規(guī)劃算法實(shí)現(xiàn)

榮昕萌+傅博

摘要：模板匹配方法是圖像檢索、分割、拼接、檢測等圖像問題在關(guān)鍵區(qū)域匹配過程中常采用的處理方法，匹配結(jié)果的優(yōu)劣將直接影響后續(xù)算法的結(jié)果。傳統(tǒng)圖像處理方法在采用模板匹配方法時，往往面臨時間復(fù)雜度過高的問題?；趧討B(tài)規(guī)劃的程序設(shè)計策略是一種重要的算法設(shè)計策略，為存在最優(yōu)子結(jié)構(gòu)性質(zhì)的實(shí)際問題提供了一種重要的解決途徑。針對圖像處理中的模板匹配問題進(jìn)行分析，給出相應(yīng)的動態(tài)規(guī)劃解法，并對所給算法的復(fù)雜度進(jìn)行分析和討論。實(shí)驗結(jié)果驗證了所提方法的有效性。

關(guān)鍵詞：動態(tài)規(guī)劃；模板匹配；特征距離矩陣

DOIDOI：10.11907/rjdk.171142

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）06-0037-03

0 引言

在計算機(jī)領(lǐng)域，常需要將實(shí)驗數(shù)據(jù)與預(yù)先設(shè)定好的模板進(jìn)行匹配。圖像處理領(lǐng)域中的圖像檢索、圖像分割、圖像拼接、圖像檢測、視頻編碼等，就需要運(yùn)用到模板匹配技術(shù)。模板匹配技術(shù)在圖像處理領(lǐng)域的具體應(yīng)用可以簡單分為兩大類：基于特征點(diǎn)的匹配技術(shù)、基于像素灰度的匹配。基于特征點(diǎn)的匹配往往被更高級的機(jī)器視覺類任務(wù)采用，而在圖像處理中，基于特征的匹配方法由于抽取的點(diǎn)、線、特征子等特征容易受到視角變換、遮擋等問題的干擾，會影響到最終匹配結(jié)果的質(zhì)量，同時特征抽取方法的時間復(fù)雜度較高，對于實(shí)時性是一個挑戰(zhàn)?；谙袼鼗叶鹊哪０迤ヅ浞椒?，只需要設(shè)定好匹配的模板尺寸與遍歷方式，算法簡潔、穩(wěn)定性高，適合圖像處理與計算機(jī)視覺問題中的底層預(yù)處理。但其也存在一些缺點(diǎn)，如噪聲、光照引起的灰度變化，且運(yùn)算數(shù)據(jù)量大，基于像素灰度的匹配算法也無法避免圖像數(shù)據(jù)與模板匹配過程可能帶來的高復(fù)雜度問題。

迄今為止，模板匹配技術(shù)已經(jīng)被廣泛應(yīng)用到圖像處理的實(shí)際問題中，并取得了一系列成果。例如，王倩倩[1]將模板匹配問題應(yīng)用到藻類圖像的識別問題中，李厚軍[2]將模板匹配問題應(yīng)用到眉毛的識別問題中，陳瑩[3]將模板匹配方法用于增強(qiáng)微光圖像，王正等[4]將模板匹配引入到圖像編碼中的調(diào)色板更正上，提高了圖像編碼效率，王志衡，郭超等[5]將模板匹配方法應(yīng)用到了新聞圖像字母行切分之中，張盼盼[6]等將模板匹配方法應(yīng)用到了數(shù)字識別過程中，陳寧等[7]將該方法應(yīng)用到集裝箱識別與匹配的問題中。然而，采用上述方法在面臨大數(shù)據(jù)量的數(shù)據(jù)時，也存在復(fù)雜度較高的問題。因此，如何進(jìn)一步優(yōu)化模板匹配問題有待進(jìn)一步研究解決。

動態(tài)規(guī)劃方法（Dynamic Programming）早期誕生于運(yùn)籌學(xué)，是一種迭代求解最優(yōu)的方法。近年來，動態(tài)規(guī)劃方法作為算法設(shè)計策略中求解最優(yōu)子結(jié)構(gòu)的一種重要思想，被廣泛引入到計算機(jī)問題求解之中。動態(tài)規(guī)劃求解計算機(jī)問題的基本思想是，將待求解問題分解成若干個結(jié)構(gòu)相同的子問題，在求解過程中保存已求解子問題的答案并在后續(xù)求解過程中，有效利用之前求解的答案協(xié)助當(dāng)前問題求解。由于后續(xù)問題在求解過程中已經(jīng)遇到了需要之前已經(jīng)求過的子問題，因此大大提高了求解效率[8-11]?？梢院唵蔚貙討B(tài)規(guī)劃算法分為基于線性的動態(tài)規(guī)劃算法、基于樹形的動態(tài)規(guī)劃算法、基于區(qū)域的動態(tài)規(guī)劃算法、基于背包的動態(tài)規(guī)劃算法。具體采用何種動態(tài)規(guī)劃方法應(yīng)針對具體問題作具體分析，例如，有學(xué)者[12-13]在語音識別與動作識別等具體領(lǐng)域嘗試采用動態(tài)規(guī)劃算法嘗試優(yōu)化求解。但往往只是將動態(tài)規(guī)劃算法應(yīng)用到某一具體問題，尚未對圖像處理中的模板匹配問題進(jìn)行動態(tài)規(guī)劃算法實(shí)現(xiàn)。

綜上，鑒于動態(tài)規(guī)劃方法的自身特性及當(dāng)前圖像處理在解決模板匹配問題上的不足，本文提出了一種采用動態(tài)規(guī)劃解決模板匹配的方法，首先給出圖像數(shù)據(jù)與模板的匹配問題，并對該問題進(jìn)行符號化和相應(yīng)的理論分析，此后采用動態(tài)規(guī)劃的方法解決模板匹配問題，并對傳統(tǒng)動態(tài)規(guī)劃解決方法在時間復(fù)雜度上進(jìn)行改進(jìn)。相較于傳統(tǒng)模板匹配方法，采用本文提出的方法可以將時間復(fù)雜度減少一個數(shù)量級。

1 問題分析與解決

圖像模板匹配算法的過程可以簡單歸納為：首先采用某一尺度的模板遍歷所有數(shù)據(jù)（例如整幅圖像），此后計算模板與模板在整個圖像中所對應(yīng)區(qū)域的匹配程度，最后在數(shù)據(jù)中找到與模板匹配程度最高的區(qū)域。對于一幅圖像數(shù)據(jù)S而言，若圖像的尺寸大小為H*W，模板T的尺寸為P*P，模板匹配算法需要在圖像數(shù)據(jù)上進(jìn)行遍歷，并計算模板與模板覆蓋區(qū)域的匹配程度，將模板覆蓋到一個圖像區(qū)域并計算匹配度的過程約定為一個動作。設(shè)有一組試驗動作序列：V=（V0，V1，…，VM） 和一組模板動作序列T=（T0，T1，…，TN），（M>N），兩組序列都滿足動作的時間順序，這里試驗動作數(shù)據(jù)中的每個動作都必須出現(xiàn)在匹配路徑中，而模板動作序列不做此要求。計算模板與圖像對應(yīng)位置的匹配程度，可以根據(jù)需求采取不同的度量方式，如歐式距離、光度距離與幾何距離等。模板的移動可以采用Zigzag的方式實(shí)現(xiàn)。則上述模板匹配可以得到有效的距離矩陣，可以在該距離矩陣的基礎(chǔ)上設(shè)計動態(tài)規(guī)劃優(yōu)化解決方案。這里，假設(shè)試驗動作數(shù)為M=15，模板動作數(shù)為N=10。

1.1 問題符號化及分析

為了方便地表達(dá)該問題，采用3個矩陣進(jìn)行存儲和計算，如圖1所示。一個是矩陣A，用來存放原始數(shù)據(jù)；一個是矩陣B，用來存放計算過程的局部最優(yōu)值；一個是矩陣R，用來記錄局部最優(yōu)值所對應(yīng)的路徑。

1.2 問題解決

1.2.1 局部最優(yōu)值計算

對于上述問題，采用動態(tài)規(guī)劃思想進(jìn)行解決，其基本思路如下：首先，試驗動作從V0開始，由于它是第一個試驗動作，前面沒有其它動作，因而無論它選擇哪一個模板，都可看成是當(dāng)前的最優(yōu)值；然后，考查第二個試驗動作V1，如果V1選擇的模板動作是T0，那么試驗動作V0選擇的模板只能是T0，這時它的最小值為a0，0+a1，0，同時在矩陣R中r0，0位置記錄該局部最優(yōu)值所對應(yīng)的模板序號；如果V1選擇的模板動作為T1，那么試驗動作V0可以選擇的模板是T0或T1，顯然，只有取a0，0和a0，1中的最小值，與a1，1相加后可得V1在選擇模板動作T1時的最優(yōu)值，同時在矩陣R中r0，1位置記錄該局部最優(yōu)值所對應(yīng)的模板序號；如果V1選擇的模板動作為T2，那么試驗動作V0可以選擇的模板就可以是T0、T1或T2，這時，需要取a0，0、a0，1、a0，2中的最小值，與a1，2相加后可得V1在選擇模板動作T2時的最優(yōu)值，同時在矩陣R中r0，2位置記錄該局部最優(yōu)值所對應(yīng)的模板序號；如果V1選擇的模板動作為Tj，j=3，…9，則依次類推。

其中，k的最大值是第M層葉結(jié)點(diǎn)的個數(shù)。度為p的樹中第i層至多有pi-1個節(jié)點(diǎn)（i>1），該問題求解的樹的度p=3，則第M=15層至多有3M-1=315-1個結(jié)點(diǎn)，試驗中k的最大值為16，通過分析可以得出該問題的時間復(fù)雜度為O（16*M）。

綜上分析，文中給出的算法在求模板匹配的最優(yōu)解時，其對應(yīng)的時間復(fù)雜度為O（MN）+O（KM），即max（O（MN），O（KM））。若從p叉樹的生成角度考慮，算法的時間復(fù)雜度為O（MN）+O（nodes），即max（O（MN），O（nodes））。

3 結(jié)語

針對傳統(tǒng)模板匹配算法在應(yīng)用圖像處理問題時遇到的時間復(fù)雜度過高等問題，對數(shù)據(jù)與模板匹配的過程進(jìn)行優(yōu)化，提出了一種基于動態(tài)規(guī)劃算法加以實(shí)現(xiàn)的方法，算法的時間復(fù)雜度為max（O（MN），O（KM））。利用本算法，可以將模板匹配過程的復(fù)雜度大大減小，也不需要對數(shù)據(jù)進(jìn)行過多處理，而且程序編寫簡單，各方面比原算法和目前已有文獻(xiàn)中提到的改進(jìn)算法都有很大提高。

可以看出，未來無論是計算機(jī)處理領(lǐng)域的模板匹配問題，還是日常生活生產(chǎn)中經(jīng)常遇到的“試驗數(shù)據(jù)和事先存儲好的模板動作進(jìn)行匹配”及類似問題，本文所提出的算法都具有一定應(yīng)用前景。

參考文獻(xiàn)：

[1]王倩倩.基于聚類的模板匹配顯微細(xì)胞圖像分割算法的研究[D].重慶：重慶大學(xué)，2015.

[2]李厚軍.快速模板匹配方法及其在眉毛識別中的應(yīng)用[D].北京：北京工業(yè)大學(xué)，2015.

[3]陳瑩.基于FPGA的微光圖像增強(qiáng)和模板匹配研究[D].北京：中國科學(xué)院大學(xué)，2014.

[4]王正，陶品，馮立新，溫江濤，楊士強(qiáng).基于模板的調(diào)色板方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2016，28（7）：1146-1151.

[5]王志衡，郭超.基于模板匹配的新聞圖像字幕行切分算法[J].北京郵電大學(xué)學(xué)報，2016，39（3）：49-53.

[6]張盼盼，張穎穎.模板匹配與八鄰域分析法在數(shù)字細(xì)化預(yù)處理中的應(yīng)用及比較[J].軟件導(dǎo)刊，2016，15（5）：210-211.

[7]陳寧，王勝，黃正文.基于特征匹配的集裝箱識別與定位技術(shù)研究[J].圖學(xué)學(xué)報，2016，37（4）：530-536.

[8]THOMAS H CORMEN，CHARLES E LEISERSON.Introduction to algorithms[M].Second Edition.Massachusetts：The MIT Press，2001.

[9]王曉東.計算機(jī)算法設(shè)計與分析[M].第2版.北京：電子工業(yè)出版社，2005.

[10]徐孝凱，賀桂英.數(shù)據(jù)結(jié)構(gòu)（C語言描述）[M].北京：清華大學(xué)出版社，2004.

[11]唐策善，李龍澍，黃劉生.數(shù)據(jù)結(jié)構(gòu)——用C語言描述[M].北京：高等教育出版社，2003.

[12]魏星，周萍.改進(jìn)型蟻群算法的語音動態(tài)規(guī)劃研究[J].仿真應(yīng)用研究，2011，228（5）：402-409.

[13]傅穎，郭晶云.基于動態(tài)時間規(guī)整的人體動作識別方法[J].電子測量技術(shù)，2014，37（3）：69-72.

（責(zé)任編輯：孫 娟）