一种改进的菱形搜索算法

孙秀娟， 杨德运， 侯迎坤

（1. 泰山学院信息科学技术学院，山东 泰安 271021；2. 泰山学院信息科学技术学院，山东 泰安 271021；3. 泰山学院信息科学技术学院，山东 泰安 271021）

一种改进的菱形搜索算法

孙秀娟1， 杨德运2， 侯迎坤3

（1. 泰山学院信息科学技术学院，山东 泰安 271021；2. 泰山学院信息科学技术学院，山东 泰安 271021；3. 泰山学院信息科学技术学院，山东 泰安 271021）

DS（Diamond Search, DS）算法曾被MPEG4标准采用，是目前公认的一种较好的搜索算法。但当运动矢量较小时，菱形搜索算法速度较慢。提出了一种改进的菱形搜索（Improved Diamond Search, IDS）算法，加入了粗定位和强化的半路停止操作。大量的车辆跟踪实验表明，IDS算法在保证搜索性能的基础上增加了搜索速度，为模板匹配提供了更加有效的技术支持。更有对比实验揭示了该算法对轨迹突变的不敏感性。

改进的菱形搜索算法；运动矢量；粗定位；强化的半路停止操作

模板匹配算法计算简单、鲁棒性强，已被广泛应用于众多领域，如纸币鉴别、行为分析、目标跟踪等。无论如何，简单的模板匹配算法有以下不足：首先，计算量会随着模板尺度或搜索范围的增大而迅速增加；其次，对于图像中目标的尺度变化不能自适应；另外，模板不能随着目标性状的突变或干扰而稳健地更新，容易导致模板漂移，甚至跟踪失败[1]。针对模板匹配的计算量问题，研究人员已经提出了许多解决方案，特别是对搜索算法的研究。文献[2]详尽地介绍了几种快速搜索算法，如三步搜索（TSS）、四步搜索（FSS）、新三步搜索（NTSS）和菱形搜索（DS）等。大量的实验表明：要想实际应用，这些算法在搜索性能或搜索速度方面还有待改进。

为了解决搜索算法在搜索性能和搜索速度方面的问题，论文提出了一种改进的菱形搜索（Improved Diamond Search, IDS）算法，加入了粗定位和强化的半路停止操作。文章结构如下：第一小节分析了3种典型的快速搜索算法；第二小节提出了IDS算法；IDS算法的性能在第三小节被详细分析；第四小节展示实验结果；最后进行总结和展望。

1 3种快速搜索算法

研究表明：搜索模板的尺寸和形状不仅影响运动估计的速度，而且直接影响算法的性能[3]。本节将通过对TSS，NTSS和DS三种快速搜索算法的分析证明以上结论，并为IDS算法提供理论支持。

1.1 TSS算法和NTSS算法

TSS算法原理，如图1所示，采用迭代算法，通过两次搜索步长的折半来实现由粗到精的搜索过程。该算法原理简单，收敛迅速，得到了较为广泛的应用。但第一步的搜索步长为4，过大，易误导搜索方向，使整个算法陷入局部最优。特别是当运动矢量MV较小时，TSS算法收敛缓慢，准确度低。

图1 TSS算法原理

考虑到运动场是中心分布，而非平均分布的，MV发生在中心点附近的概率是极高的。因此NTSS算法在TSS算法的第一步加入了一个3×3的小方形搜索模板，见图2(a)。这个小方形搜索模板实际上是增加了8个高概率的搜索位，使得NTSS算法搜索性能更高；而且当MV较小时，收敛更快。但当MV较大时，如图2(b)，小方形搜索模板反而变成了整个算法的负担，使得NTSS算法需要的搜索位数量比TSS算法还多了8个。

图2 NTSS算法示例图

1.2 DS算法

DS算法[3]使用了两种搜索模板，分别是大菱形搜索模板(Large Diamond Search Pattern, LDSP和小菱形搜索模板(Small Diamond Search Pattern SDSP)。首先使用固定尺寸的LDSP进行迭代搜索，即使某一步的搜索误导了搜索方向，LDSP的迭代过程仍有可能找回正确方向；最后，采用与LDSP搜索位互补的SDSP精确搜索位置，使DS算法趋近于全局最优。另外，LDSP有较强的相关性，在迭代时仅需要计算3或5个新的搜索位，减少了不小的计算量。但当MV小于2时，DS算法易导致过搜索；另外，由于搜索模板的移动速度为2像素/步或像素/步，当MV较大时，DS算法的收敛速度缓慢。算法原理如图 3所示。

图3 DS算法原理

2 改进的菱形搜索(IDS)算法

模板匹配总的计算量是由采用的匹配策略本身的计算量和搜索位个数共同决定的，因此，在保证匹配性能的基础上，尽可能地减少搜索位个数是及其必要的。搜索算法的目标函数如下：

DS算法之所以能够实现近似全局最优，一方面是因为LDSP的迭代过程增加了可能的搜索位个数和搜索位的密度；另一方面也是因为考虑了运动场的中心分布特性：只有最优解出现在搜索模板的中心点时，才从LDSP转化到SDSP，或结束整个搜索过程。但整个算法的速度却被菱形模板的步长所限制。我们希望借鉴TSS算法由粗到精的思想对搜索方向进行粗定位，以此来提高DS算法的速度。为此，本文提出了IDS算法，它的基本原理如图4所示。算法的具体描述如下：

算法1（IDS算法）

1） 搜索方向粗定位

在当前帧中使用步长为3的方形搜索模板，找到目标函数的最优解：

（1） 如果最优解发生在搜索模板的中心，选用中心点附近3×3的方形搜索模板，找到目标函数的最优解，搜索终止。（第一次强化的半路停止操作）；

（2） 如果最优解发生在搜索模板的边缘点，且相似度大于给定阈值，设置最优解点为新的搜索模板中心，搜索中心点附近3×3的方形搜索模板，找到目标函数的最优解，终止搜索。（第二次强化的半路停止操作）；

（3） 否则，转移搜索模板的中心点到最优解点，粗定位结束，转到（2）；

2） 搜索模板转化为LDSP，找到目标函数的最优解；

（1） 如果最优解发生在搜索模板中心或是搜索范围的边缘，转到（3）；

（2） 否则，替换搜索模板中心点为最优解点，再次使用LDSP，然后转到（3）；

3） 变换搜索模板为 SDSP，找到目标函数的最优解。这个解就是要找的MV，搜索结束。

图4 IDS 算法原理。 箭头显示搜索方向

DS算法近似全局最优，因此IDS算法以DS算法为依托。考虑到 TSS算法的快速收敛和NTSS算法的中心分布特性，本文同样设置初始搜索模板为方形搜索模板。不同的是，此时的搜索步长缩小为3。这个模板的步长介于菱形搜索模板的2和TSS的初始搜索步长4之间，不仅能为菱形搜索进行粗定位，而且由于考虑了运动场的中心分布，使得搜索方向错误的可能性减小。如果最优解发生在搜索模板的中心，运动矢量MV发生在这个点附近的可能性是极高的，因此可以实施一次强化的半路停止操作（即在最优解所在点的八临域内再次计算目标函数，得到目标点）。如果最优解发生在搜索模板的边缘点，且相似度大于给定阈值（依据运动矢量场的中心分布特性，根据实际需要设定的较大的临界点），同样依据中心分布特性，MV发生在这个点附近的概率是较高的，为此实施强化的半路停止操作。否则，将搜索模板的中心点转移到最优解所在点，粗定位结束。研究表明，MV发生在搜索范围中心5×5范围内的概率极高[5]，因此对应于新的中心点，MV极有可能小于2。为了避免过搜索，本文至多使用两次LDSP。最后采用搜索位互补的SDSP结束搜索。

综上所述，由于整个过程考虑了运动场的中心分布特性，IDS算法较好地模拟了目标的运动状态，保证了搜索性能。与此同时，如果某个搜索位能够满足两个条件之一：（1）别当中心点附近某个搜索位相似度较高时；（2）当前最优解已经处于搜索范围的边缘，即当前MV≥7时，考虑到运动场的中心分布特性，IDS算法采用强化的半路停止操作，适时地停止搜索过程，提高搜索速度。另外，两次强化的半路停止操作中的3×3搜索模板是在确定了MV候选区域时，为了提高运动估计的性能而设计的。

接下来，对比全搜索（FS）、TSS、NTSS、DS和IDS算法的计算量来证明IDS算法的搜索效率。首先，无论何种情况，FS都需要15×15 = 225个搜索位，TSS都需要9+8+8=25个搜索位。当MV较小时，例如图5(a)中的白点为目标点时，NTSS算法需要9+8+5=22个搜索位，DS算法需要16-22个搜索位，而IDS算法仅需要9+8=17个。当目标静止时，例如图 5(a)中的黑点为目标点时，NTSS算法需要9+8=17个搜索位，DS算法需要9+4=13个搜索位，IDS算法需要9+8=17个。当MV较大时，例如图5(b)中的白点为目标点时，NTSS算法需要9+8+8+8=33个搜索位， DS算法需要9+5+5+4+4=27个搜索位，而IDS算法仅需要9+8+5+3=25个。综上所述，IDS算法确实比其它几种算法需要较少的搜索位。事实上，IDS算法所需的搜索位个数可以用公式（2）计算：

其中，P1表示发生强化的半路停止操作的概率；P2表示仅运用一次LDSP的概率；P3是LDSP在对角线方向移动的概率。这些概率都依赖于MV。

虽然IDS算法减少的搜索位个数有限，但它所产生的意义却是巨大的。因为在每一个点进行模板匹配时所涉及的计算量本身就是很大的，所以仅仅这几个搜索位就能使计算量大大减少。因此，IDS算法确实能够缓解模板匹配的计算压力。

3 实 验

本文提出的算法已经经过了大量的车辆跟踪实验的验证，还与FS、TSS、NTSS和DS算法进行了对比实验。实验结果证明，改进算法是高效、鲁棒的，为模板匹配提供了更加有力的支持。

本文的实验环境中，计算机的配置为处理器Intel Pentium CPU1.86GHz、内存1G、操作系统为Microsoft Windows XP Professional，编写环境为Matlab R2009a，视频图像大小为768×578像素。

文献[1]中的模板匹配算法被采用来跟踪运动轨迹突变的车辆，然后通过跟踪结果对比几种算法的准确性和搜索速度。图6显示了实验结果的第2、68、95和302帧图像。在整个跟踪过程中，车辆发生了较大的轨迹变化，特别是在第68-95帧之间。基于NTSS和DS算法的跟踪结果与IDS算法类似，这里被省略。实验结果表明，当运动轨迹发生大的变化时，基于TSS算法的跟踪是不稳健的，容易导致跟踪失败；而基于IDS算法的跟踪受运动轨迹变化影响不大。原因是因为运动轨迹的变化会导致目标在图像中 MV的变化。摩托车转弯前，MV较大，TSS算法能够搜索到最优解，但当摩托车转弯后，运动方向与摄像机的光轴方向近似平行，此时MV较小，这就导致了TSS算法性能下降。而IDS算法对MV不敏感，始终能够保持较好的搜索性能。图7显示的是实验的漂移情况对比。很明显，在处理轨迹突变问题上，IDS算法较TSS算法好，它的性能与FS算法相似。

以上面的摩托车跟踪实验为例，同样采用文献[1]的模板匹配算法，通过目标跟踪的时间消耗反映不同搜索算法的搜索效率。计算结果见表1。显然，基于IDS算法的模板匹配是最快速的。对应的结果就是，IDS算法确实比其他几种搜索算法搜索效率高。

图7 漂移情况对比图

表1 各种搜索算法的平均消耗时间

4 结 论

本文提出了一种改进的菱形搜索（Improved Diamond Search, IDS）算法，加入了粗定位和强化的半路停止操作。该算法结合了TSS的快速收敛性，NTSS的中心分布特性和DS算法的近似全局最优。大量的车辆跟踪实验表明，IDS算法能够得到与DS算法相似的搜索性能，更好地处理运动矢量突变问题；更有对比实验数据显示了IDS算法的高效率。

无论如何，应用到模板匹配中时，本文提出的算法还不能达到跟踪算法对实时性的要求；与FS算法的全局最优也有一段距离。将来的工作将在这些方面重点展开。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] 倪 伟, 郭宝龙, 丁贵广. 基于六边形的运动矢量场自适应搜索算法[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-），女，辽宁辽阳人，助教，硕士研究生，主要研究方向为数字图像处理。E-mail：juanzi_5588@126.com