孫秀娟， 楊德運(yùn)， 侯迎坤

（1. 泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021；2. 泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021；3. 泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021）

一種改進(jìn)的菱形搜索算法

孫秀娟1， 楊德運(yùn)2， 侯迎坤3

（1. 泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021；2. 泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021；3. 泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021）

DS（Diamond Search, DS）算法曾被MPEG4標(biāo)準(zhǔn)采用，是目前公認(rèn)的一種較好的搜索算法。但當(dāng)運(yùn)動(dòng)矢量較小時(shí)，菱形搜索算法速度較慢。提出了一種改進(jìn)的菱形搜索（Improved Diamond Search, IDS）算法，加入了粗定位和強(qiáng)化的半路停止操作。大量的車輛跟蹤實(shí)驗(yàn)表明，IDS算法在保證搜索性能的基礎(chǔ)上增加了搜索速度，為模板匹配提供了更加有效的技術(shù)支持。更有對(duì)比實(shí)驗(yàn)揭示了該算法對(duì)軌跡突變的不敏感性。

改進(jìn)的菱形搜索算法；運(yùn)動(dòng)矢量；粗定位；強(qiáng)化的半路停止操作

模板匹配算法計(jì)算簡單、魯棒性強(qiáng)，已被廣泛應(yīng)用于眾多領(lǐng)域，如紙幣鑒別、行為分析、目標(biāo)跟蹤等。無論如何，簡單的模板匹配算法有以下不足：首先，計(jì)算量會(huì)隨著模板尺度或搜索范圍的增大而迅速增加；其次，對(duì)于圖像中目標(biāo)的尺度變化不能自適應(yīng)；另外，模板不能隨著目標(biāo)性狀的突變或干擾而穩(wěn)健地更新，容易導(dǎo)致模板漂移，甚至跟蹤失敗[1]。針對(duì)模板匹配的計(jì)算量問題，研究人員已經(jīng)提出了許多解決方案，特別是對(duì)搜索算法的研究。文獻(xiàn)[2]詳盡地介紹了幾種快速搜索算法，如三步搜索（TSS）、四步搜索（FSS）、新三步搜索（NTSS）和菱形搜索（DS）等。大量的實(shí)驗(yàn)表明：要想實(shí)際應(yīng)用，這些算法在搜索性能或搜索速度方面還有待改進(jìn)。

為了解決搜索算法在搜索性能和搜索速度方面的問題，論文提出了一種改進(jìn)的菱形搜索（Improved Diamond Search, IDS）算法，加入了粗定位和強(qiáng)化的半路停止操作。文章結(jié)構(gòu)如下：第一小節(jié)分析了3種典型的快速搜索算法；第二小節(jié)提出了IDS算法；IDS算法的性能在第三小節(jié)被詳細(xì)分析；第四小節(jié)展示實(shí)驗(yàn)結(jié)果；最后進(jìn)行總結(jié)和展望。

1 3種快速搜索算法

研究表明：搜索模板的尺寸和形狀不僅影響運(yùn)動(dòng)估計(jì)的速度，而且直接影響算法的性能[3]。本節(jié)將通過對(duì)TSS，NTSS和DS三種快速搜索算法的分析證明以上結(jié)論，并為IDS算法提供理論支持。

1.1 TSS算法和NTSS算法

TSS算法原理，如圖1所示，采用迭代算法，通過兩次搜索步長的折半來實(shí)現(xiàn)由粗到精的搜索過程。該算法原理簡單，收斂迅速，得到了較為廣泛的應(yīng)用。但第一步的搜索步長為4，過大，易誤導(dǎo)搜索方向，使整個(gè)算法陷入局部最優(yōu)。特別是當(dāng)運(yùn)動(dòng)矢量MV較小時(shí)，TSS算法收斂緩慢，準(zhǔn)確度低。

圖1 TSS算法原理

考慮到運(yùn)動(dòng)場是中心分布，而非平均分布的，MV發(fā)生在中心點(diǎn)附近的概率是極高的。因此NTSS算法在TSS算法的第一步加入了一個(gè)3×3的小方形搜索模板，見圖2(a)。這個(gè)小方形搜索模板實(shí)際上是增加了8個(gè)高概率的搜索位，使得NTSS算法搜索性能更高；而且當(dāng)MV較小時(shí)，收斂更快。但當(dāng)MV較大時(shí)，如圖2(b)，小方形搜索模板反而變成了整個(gè)算法的負(fù)擔(dān)，使得NTSS算法需要的搜索位數(shù)量比TSS算法還多了8個(gè)。

圖2 NTSS算法示例圖

1.2 DS算法

DS算法[3]使用了兩種搜索模板，分別是大菱形搜索模板(Large Diamond Search Pattern, LDSP和小菱形搜索模板(Small Diamond Search Pattern SDSP)。首先使用固定尺寸的LDSP進(jìn)行迭代搜索，即使某一步的搜索誤導(dǎo)了搜索方向，LDSP的迭代過程仍有可能找回正確方向；最后，采用與LDSP搜索位互補(bǔ)的SDSP精確搜索位置，使DS算法趨近于全局最優(yōu)。另外，LDSP有較強(qiáng)的相關(guān)性，在迭代時(shí)僅需要計(jì)算3或5個(gè)新的搜索位，減少了不小的計(jì)算量。但當(dāng)MV小于2時(shí)，DS算法易導(dǎo)致過搜索；另外，由于搜索模板的移動(dòng)速度為2像素/步或像素/步，當(dāng)MV較大時(shí)，DS算法的收斂速度緩慢。算法原理如圖 3所示。

圖3 DS算法原理

2 改進(jìn)的菱形搜索(IDS)算法

模板匹配總的計(jì)算量是由采用的匹配策略本身的計(jì)算量和搜索位個(gè)數(shù)共同決定的，因此，在保證匹配性能的基礎(chǔ)上，盡可能地減少搜索位個(gè)數(shù)是及其必要的。搜索算法的目標(biāo)函數(shù)如下：

DS算法之所以能夠?qū)崿F(xiàn)近似全局最優(yōu)，一方面是因?yàn)長DSP的迭代過程增加了可能的搜索位個(gè)數(shù)和搜索位的密度；另一方面也是因?yàn)榭紤]了運(yùn)動(dòng)場的中心分布特性：只有最優(yōu)解出現(xiàn)在搜索模板的中心點(diǎn)時(shí)，才從LDSP轉(zhuǎn)化到SDSP，或結(jié)束整個(gè)搜索過程。但整個(gè)算法的速度卻被菱形模板的步長所限制。我們希望借鑒TSS算法由粗到精的思想對(duì)搜索方向進(jìn)行粗定位，以此來提高DS算法的速度。為此，本文提出了IDS算法，它的基本原理如圖4所示。算法的具體描述如下：

算法1（IDS算法）

1） 搜索方向粗定位

在當(dāng)前幀中使用步長為3的方形搜索模板，找到目標(biāo)函數(shù)的最優(yōu)解：

（1） 如果最優(yōu)解發(fā)生在搜索模板的中心，選用中心點(diǎn)附近3×3的方形搜索模板，找到目標(biāo)函數(shù)的最優(yōu)解，搜索終止。（第一次強(qiáng)化的半路停止操作）；

（2） 如果最優(yōu)解發(fā)生在搜索模板的邊緣點(diǎn)，且相似度大于給定閾值，設(shè)置最優(yōu)解點(diǎn)為新的搜索模板中心，搜索中心點(diǎn)附近3×3的方形搜索模板，找到目標(biāo)函數(shù)的最優(yōu)解，終止搜索。（第二次強(qiáng)化的半路停止操作）；

（3） 否則，轉(zhuǎn)移搜索模板的中心點(diǎn)到最優(yōu)解點(diǎn)，粗定位結(jié)束，轉(zhuǎn)到（2）；

2） 搜索模板轉(zhuǎn)化為LDSP，找到目標(biāo)函數(shù)的最優(yōu)解；

（1） 如果最優(yōu)解發(fā)生在搜索模板中心或是搜索范圍的邊緣，轉(zhuǎn)到（3）；

（2） 否則，替換搜索模板中心點(diǎn)為最優(yōu)解點(diǎn)，再次使用LDSP，然后轉(zhuǎn)到（3）；

3） 變換搜索模板為 SDSP，找到目標(biāo)函數(shù)的最優(yōu)解。這個(gè)解就是要找的MV，搜索結(jié)束。

圖4 IDS 算法原理。 箭頭顯示搜索方向

DS算法近似全局最優(yōu)，因此IDS算法以DS算法為依托?？紤]到 TSS算法的快速收斂和NTSS算法的中心分布特性，本文同樣設(shè)置初始搜索模板為方形搜索模板。不同的是，此時(shí)的搜索步長縮小為3。這個(gè)模板的步長介于菱形搜索模板的2和TSS的初始搜索步長4之間，不僅能為菱形搜索進(jìn)行粗定位，而且由于考慮了運(yùn)動(dòng)場的中心分布，使得搜索方向錯(cuò)誤的可能性減小。如果最優(yōu)解發(fā)生在搜索模板的中心，運(yùn)動(dòng)矢量MV發(fā)生在這個(gè)點(diǎn)附近的可能性是極高的，因此可以實(shí)施一次強(qiáng)化的半路停止操作（即在最優(yōu)解所在點(diǎn)的八臨域內(nèi)再次計(jì)算目標(biāo)函數(shù)，得到目標(biāo)點(diǎn)）。如果最優(yōu)解發(fā)生在搜索模板的邊緣點(diǎn)，且相似度大于給定閾值（依據(jù)運(yùn)動(dòng)矢量場的中心分布特性，根據(jù)實(shí)際需要設(shè)定的較大的臨界點(diǎn)），同樣依據(jù)中心分布特性，MV發(fā)生在這個(gè)點(diǎn)附近的概率是較高的，為此實(shí)施強(qiáng)化的半路停止操作。否則，將搜索模板的中心點(diǎn)轉(zhuǎn)移到最優(yōu)解所在點(diǎn)，粗定位結(jié)束。研究表明，MV發(fā)生在搜索范圍中心5×5范圍內(nèi)的概率極高[5]，因此對(duì)應(yīng)于新的中心點(diǎn)，MV極有可能小于2。為了避免過搜索，本文至多使用兩次LDSP。最后采用搜索位互補(bǔ)的SDSP結(jié)束搜索。

綜上所述，由于整個(gè)過程考慮了運(yùn)動(dòng)場的中心分布特性，IDS算法較好地模擬了目標(biāo)的運(yùn)動(dòng)狀態(tài)，保證了搜索性能。與此同時(shí)，如果某個(gè)搜索位能夠滿足兩個(gè)條件之一：（1）別當(dāng)中心點(diǎn)附近某個(gè)搜索位相似度較高時(shí)；（2）當(dāng)前最優(yōu)解已經(jīng)處于搜索范圍的邊緣，即當(dāng)前MV≥7時(shí)，考慮到運(yùn)動(dòng)場的中心分布特性，IDS算法采用強(qiáng)化的半路停止操作，適時(shí)地停止搜索過程，提高搜索速度。另外，兩次強(qiáng)化的半路停止操作中的3×3搜索模板是在確定了MV候選區(qū)域時(shí)，為了提高運(yùn)動(dòng)估計(jì)的性能而設(shè)計(jì)的。

接下來，對(duì)比全搜索（FS）、TSS、NTSS、DS和IDS算法的計(jì)算量來證明IDS算法的搜索效率。首先，無論何種情況，F(xiàn)S都需要15×15 = 225個(gè)搜索位，TSS都需要9+8+8=25個(gè)搜索位。當(dāng)MV較小時(shí)，例如圖5(a)中的白點(diǎn)為目標(biāo)點(diǎn)時(shí)，NTSS算法需要9+8+5=22個(gè)搜索位，DS算法需要16-22個(gè)搜索位，而IDS算法僅需要9+8=17個(gè)。當(dāng)目標(biāo)靜止時(shí)，例如圖 5(a)中的黑點(diǎn)為目標(biāo)點(diǎn)時(shí)，NTSS算法需要9+8=17個(gè)搜索位，DS算法需要9+4=13個(gè)搜索位，IDS算法需要9+8=17個(gè)。當(dāng)MV較大時(shí)，例如圖5(b)中的白點(diǎn)為目標(biāo)點(diǎn)時(shí)，NTSS算法需要9+8+8+8=33個(gè)搜索位， DS算法需要9+5+5+4+4=27個(gè)搜索位，而IDS算法僅需要9+8+5+3=25個(gè)。綜上所述，IDS算法確實(shí)比其它幾種算法需要較少的搜索位。事實(shí)上，IDS算法所需的搜索位個(gè)數(shù)可以用公式（2）計(jì)算：

其中，P1表示發(fā)生強(qiáng)化的半路停止操作的概率；P2表示僅運(yùn)用一次LDSP的概率；P3是LDSP在對(duì)角線方向移動(dòng)的概率。這些概率都依賴于MV。

雖然IDS算法減少的搜索位個(gè)數(shù)有限，但它所產(chǎn)生的意義卻是巨大的。因?yàn)樵诿恳粋€(gè)點(diǎn)進(jìn)行模板匹配時(shí)所涉及的計(jì)算量本身就是很大的，所以僅僅這幾個(gè)搜索位就能使計(jì)算量大大減少。因此，IDS算法確實(shí)能夠緩解模板匹配的計(jì)算壓力。

3 實(shí) 驗(yàn)

本文提出的算法已經(jīng)經(jīng)過了大量的車輛跟蹤實(shí)驗(yàn)的驗(yàn)證，還與FS、TSS、NTSS和DS算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果證明，改進(jìn)算法是高效、魯棒的，為模板匹配提供了更加有力的支持。

本文的實(shí)驗(yàn)環(huán)境中，計(jì)算機(jī)的配置為處理器Intel Pentium CPU1.86GHz、內(nèi)存1G、操作系統(tǒng)為Microsoft Windows XP Professional，編寫環(huán)境為Matlab R2009a，視頻圖像大小為768×578像素。

文獻(xiàn)[1]中的模板匹配算法被采用來跟蹤運(yùn)動(dòng)軌跡突變的車輛，然后通過跟蹤結(jié)果對(duì)比幾種算法的準(zhǔn)確性和搜索速度。圖6顯示了實(shí)驗(yàn)結(jié)果的第2、68、95和302幀圖像。在整個(gè)跟蹤過程中，車輛發(fā)生了較大的軌跡變化，特別是在第68-95幀之間。基于NTSS和DS算法的跟蹤結(jié)果與IDS算法類似，這里被省略。實(shí)驗(yàn)結(jié)果表明，當(dāng)運(yùn)動(dòng)軌跡發(fā)生大的變化時(shí)，基于TSS算法的跟蹤是不穩(wěn)健的，容易導(dǎo)致跟蹤失敗；而基于IDS算法的跟蹤受運(yùn)動(dòng)軌跡變化影響不大。原因是因?yàn)檫\(yùn)動(dòng)軌跡的變化會(huì)導(dǎo)致目標(biāo)在圖像中 MV的變化。摩托車轉(zhuǎn)彎前，MV較大，TSS算法能夠搜索到最優(yōu)解，但當(dāng)摩托車轉(zhuǎn)彎后，運(yùn)動(dòng)方向與攝像機(jī)的光軸方向近似平行，此時(shí)MV較小，這就導(dǎo)致了TSS算法性能下降。而IDS算法對(duì)MV不敏感，始終能夠保持較好的搜索性能。圖7顯示的是實(shí)驗(yàn)的漂移情況對(duì)比。很明顯，在處理軌跡突變問題上，IDS算法較TSS算法好，它的性能與FS算法相似。

以上面的摩托車跟蹤實(shí)驗(yàn)為例，同樣采用文獻(xiàn)[1]的模板匹配算法，通過目標(biāo)跟蹤的時(shí)間消耗反映不同搜索算法的搜索效率。計(jì)算結(jié)果見表1。顯然，基于IDS算法的模板匹配是最快速的。對(duì)應(yīng)的結(jié)果就是，IDS算法確實(shí)比其他幾種搜索算法搜索效率高。

圖7 漂移情況對(duì)比圖

表1 各種搜索算法的平均消耗時(shí)間

4 結(jié) 論

本文提出了一種改進(jìn)的菱形搜索（Improved Diamond Search, IDS）算法，加入了粗定位和強(qiáng)化的半路停止操作。該算法結(jié)合了TSS的快速收斂性，NTSS的中心分布特性和DS算法的近似全局最優(yōu)。大量的車輛跟蹤實(shí)驗(yàn)表明，IDS算法能夠得到與DS算法相似的搜索性能，更好地處理運(yùn)動(dòng)矢量突變問題；更有對(duì)比實(shí)驗(yàn)數(shù)據(jù)顯示了IDS算法的高效率。

無論如何，應(yīng)用到模板匹配中時(shí)，本文提出的算法還不能達(dá)到跟蹤算法對(duì)實(shí)時(shí)性的要求；與FS算法的全局最優(yōu)也有一段距離。將來的工作將在這些方面重點(diǎn)展開。tracking based on the improved diamond search algorithm and Gaussian scale-space [C]//CPS. 2011 International Conference on Intelligence Human-Machine Systems and Cybernetics (IHMSC). Zhejing: Zhejing University Press, 2011: 65-70.

[2] Wu-Chih Hu. Adaptive template block-based block matching for object tracking [C]//Jeng-Shyang Pan, Ajith Abraham, Chin-Chen Chang. Eighth International Conference on Intelligence Systems Design and Applications. Kaohsiung, 2008: 61-64.

[3] Ni Wei, Guo Baolong, Ding Guiguang. A Hexagon-based motion estimation algorithm using motion vector field adaptive search technique [J]. Computer Engineering, 2005, 31(13):10-12.

[4] Kim J N, Choi T S. A fast three-step search algorithm with minimum checking points using unimodal error surface assumption [J]. IEEE Trans. On Consumer Electronics, 1998, 44(3): 638-648.

[5] Li Remxing, Zeng Bing, Liou Ming L. A new three-step search algorithm for block motion estimation [J]. IEEE Trans. on Circuits and Systems for Video Technology, 1994, 4(4): 438-442.

[6] 倪 偉, 郭寶龍, 丁貴廣. 基于六邊形的運(yùn)動(dòng)矢量場自適應(yīng)搜索算法[J]. 計(jì)算機(jī)工程, 2005, 31(13): 10-12.

[1] Liu Wei, Sun Xiujuan, Yuan Huai. Moving target

An improved Diamond Search Algorithm

Sun Xiujuan1, Yang Deyun2, Hou Yingkun3
( 1. Department of Information Science and Technology, Taishan University, Tai’an Shandong 271021, China; 2. Department of Information Science and Technology, Taishan University, Tai’an Shandong 271021, China; 3. Department of Information Science and Technology, Taishan University, Tai’an Shandong 271021, China )

The diamond search (DS) algorithm has been adopted by MPEG4 standard, and currently recognized as a better search algorithm. But the speed of DS algorithm is slow when the motion vector is small. The improved diamond search (IDS) algorithm is presented. Rough location and enhanced halfway-stop operation are added to it. Lots of vehicle tracking experiments show that the IDS algorithm improves the search speed on the basic of ensuring the search performance, supplying more effective technique support for template matching. Moreover, contrastive experiments prove the algorithm is insensitive to mutational trajectory.

improved diamond search algorithm; motion vector; rough location; enhanced halfway-stop operation

TP 391

A

2095-302X (2013)04-0041-05

2012-09-02；定稿日期：2013-01-08

孫秀娟（1986-），女，遼寧遼陽人，助教，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理。E-mail：juanzi_5588@126.com