数字视频分析中快速边缘检测和运动估计研究

徐济惠，祝晓东，刘翠娟，郭国文

（1.宁波城市职业技术学院，宁波　315100；2.浙江万里学院智能控制研究所，宁波　315100；3.宁波大学信息科学与工程学院，宁波　315100）

数字视频分析中快速边缘检测和运动估计研究

徐济惠1，祝晓东1，刘翠娟2，3，郭国文2

（1.宁波城市职业技术学院，宁波315100；2.浙江万里学院智能控制研究所，宁波315100；3.宁波大学信息科学与工程学院，宁波315100）

研究了将粒子群优化算法同万有引力算法相结合进行边缘检测，利用万有引力原理进行启发函数的计算，指导蚁群运动趋向，快速检测出边缘线，作为图像分析的预处理结果；另外根据视频图像中局部运动集中在图像中部概率较大的特性，提出对图像的几个小区域数据进行全局运动估计，这样大幅度减少了运算量，实验中通过采样4个六分之一原图边长的矩形区域进行全局估计，实验证实了在精度相同的情况下，运算速度提高了九倍左右。

视频；粒子群优化算法；全局运动估计；边缘检测；估计误差

0　前言

一般来说，随着图像特征层次的提高，将更有利于进行图像处理和分析，而且直线特征比点特征更容易检测，算法的稳定性受限于参数特征提取的稳定性和精确性。使用摄像机进行视频采样时肯定会遇到尺寸压缩、变焦和信号数字化处理等情况。为了能够更好地进行运动估计，必须对尺寸压缩和变焦等情况采用图像稳定系统进行处理（DIS，digital image stabilization），信号的数字化处理为图像边缘T稳定提取提供了可能。这种数字图像处理系统包括三部分：基于边缘检测的预处理部分；为减少运算量，在运动估计中运用相关逻辑运算代替算术减运算；在变焦处理中使用估计双线性插值技术。

边缘检测是在图像处理中经常使用的技术，是为从图像中提取信息的预处理工作。由于图像密度是与场景辐射成比例的，所以物理边缘可以表示为图像中密度变换的函数［1］。在数字图像处理的发展的几十年中，目前已经存在许多种边缘检测的算法和方法，例如比较经典的边缘检测算法：Sobel，Prewitt，Canny等等。

近期又出现了多种新颖的算法，2007年，吴金波等提出了快速多级模糊边缘检测算法［2］，对模糊图像实现快速准确地边缘检测。同年，孙耕耘提出了基于万有引力的边缘检测法［3］，但是这种方法对内存和时间的消耗都是巨大的，如果直接应用这种方法处理尺寸为800*600的图像，所需要的解内存空间为2 800*600。2009年，Hanmandlu等提出了一种基于模糊逻辑的边缘和角点的监测方法［4］。2009年，Setayesh等提出了一种新的利用粒子群优化算法原理对同质基边缘进行检测的方法［5］。2011年，Verma等人提出了利用蚁群觅食原理进行边缘监测算法［6］，核心思想是根据一个蚁群优化算法可以导出方向概率矩阵，蚁群觅食的运动方向就可以根据这个矩阵推动出来。2011年付文龙等提出了基于遗传规划的全局边缘检测算法［7］，该算法的思想就是直接将整个图像作为输入数据，不经过任何预处理和后处理，直接将图像中的所有像素点归类为边缘点或非边缘点。

1　利用蚁群优化边缘检测方法

蚁群优化简称ACO（ant colony optimization），是Dorigo等在1996年最早提出了，算法的优点是充分利用群的感知能力，同时避免由于分布式计算引起的不成熟的收敛。缺点是由于收敛速度慢，不太适合处理规模比较大的问题。

在蚁群优化过程中，利用几个人工蚂蚁来寻求一个优化问题的解，这些蚂蚁群是通过特点通信机制按质交换信息，这点同现实世界中的蚂蚁行为非常接近。单独一个蚂蚁由于记忆能力是有限的，只能执行简单的动作，然而，蚁群的集体合作可以提高完成智能解决问题的能力，例如可以发现从巢穴到食物源的最短路径。蚁群觅食时留下挥发性物质，标志它们觅食路线的信息索。蚁群就是这样通过这些信息索来实现间接通信，这些信息索既是累加的，同时又是挥发的，这些信息可以协助蚁群完成寻找目标的任务。

蚁群优化算法要解决的问题是，让K个蚂蚁在由M×N个节点组成的解空间χ中寻求优化解决方案［8］。

算法实现可以描述为：

1）首先初始化所有参加运算的K个蚂蚁的坐标位置，也就是对信息索矩阵进行初始化，得到初始信息索矩阵τ（0）。

2）构造蚁群的移动步骤，对于各个蚂蚁（k=1，2，…K）的每个步骤（n=1，2，…N）进行循环计算，第k个蚂蚁的第L步的移动是按照蜕变概率矩阵Pi，j（n）计算得到的。

其中：τi，jn是连接节点i和节点j之间的弧的信息索的值，Ωi表示的是蚂蚁k在位置i节点时所对应的所有相邻节点的集合，ηi，j表示从节点i到节点j的启发信息，α表示受信息索的影响因子，β表示受启发信息影响的因子。

3）当每一步蚂蚁按照上式（1）移动后，该算法就立即对信息索矩阵τi，jn进行一次更新操作，为后续的算法执行步骤做好准备。

其中：当节点（i，j）正好处在最佳路径上，就不需要在继续进行迭代计算了。公式中ρ表示信息的挥发速度，Δki，j表示第k个蚂蚁存留的信息总量。这里最佳路径是要根据用户定义的标准，这个最佳路径既可以是同当前构建路径的最佳吻合，也可以是从算法开始点到当前的最佳路径，也可以是二者的综合加权最佳。通常可以根据下式再进行选择：τn=（1-ψ）.τ（n-1）+ψτ（0）（3）

式中的τn是代表所有蚂蚁都已经按照前面的步骤移到相应的节点，并且信息索矩阵也都按公式（3）进行了更新后的最终信息索矩阵。式中ψ代表信息索衰减的系数。

2　万有引力边缘检测方法

利用万有引力原理进行边缘检测算法的核心思想是假设图像中的每个像素被表示为不同灰度强度的“天体”。设想每个像素点向周围相邻的点施加引力，同样周围相邻的点也向这个像素点施加引力，见图1所示。这种情况下边缘的特征就是大多数像素点存在有沿着一个特定方向的引力，所以可以利用这个特性检测边缘的存在。

对于图像中的每个像素点（I，j），其邻域可以设为是一个k×l像素点组成的域Ω，所有的邻域像素点满足条件（m，n）∈Ω&（m，n）≠（i，j）。每个像素点向周围相邻点施加的引力按下式计算：式中，→fi，j；m，n是表示点 （m，n）和点（i，j）之间的相互引力，mi，j和mm，n表示这两个点的灰度值，灰度值差别可以设想成万有引力对象的质量不同，→r表示两点之间的矢量距离。

图1　基本边缘结构及相互之间作用力示意

对于矢量→fi，j；m，n也可以通过x和y方向的作用力来表示。

相邻的各个点作用于点（i，j）的力总和为：→Fi，j=∑→fi，j；m，n=Fx^x+Fy^y（7）

其中：（m，n）∈Ω&（m，n）≠（i，j）

像素点（i，j）的边缘强度由矢量→Fi，j的值决定的，其方向也是由矢量→Fi，j的方向所决定的。

只要选择一个比较合适的阈值，就可以对原图像产生一个边缘图像。

3　算法改进

为了减少算法的计算机复杂度和内存过高的需求，采取的方法是将蚁群优化算法同万有引力原理相结合，处理边缘检测的问题，利用万有引力原理进行启发函数计算，这个函数用来指导蚁群的趋向。

这是利用一种改进的蚁群优化算法来实现对边缘的检测。改进的边缘算法的核心思想是，利用一定数量的蚂蚁在二维图像上移动，构建一个信息矩阵，表示了图像上一个个像素点的边缘信息。先初始化所有蚂蚁的位置，将蚂蚁随机分配到尺寸为M×N的图像I中，用一个常数初始值将信息矩阵初始化为τ（0）。当构造第n步蚂蚁移动时，从K个蚂蚁中任意选择一个蚂蚁，使这个蚂蚁在图像中连续移动L个步长，即这个改进的蚂蚁信息蜕变概率公式：

从节点（i，j）经过若干步移动到相邻节点（i，j），τ，（n-1）

00ij是节点（i，j）的信息索的值。Ω（i0，j0）是与节点（i0，j0）相邻节点的集合，ηi，j表示在节点（i，j）的启发信息，α和β这两个常数，分别代表对于信息索矩阵和启发矩阵的影响系数。

各个节点的启发函数值，是评估这个节点是否为期望的路径上节点的重要依据。启发函数的功能就是在多条可行的路径上选择最佳的路径方案，启发函数是通过运用万有引力原理来进行计算的。在启发函数中周围相邻点施加给中心节点的作用力定义为：

如图2所示，分别利用Canny算法和改进的算法，对两幅图像进行边缘检测的结果，从实验结果可以看出传统算法比本算法能检测到更多的边缘数目，但本算法可以减少计算时间和减少对内存的消耗，对于实时性要求比较高的场合有非常重要的价值。

图2　对Lena图像和遥感地图进行边缘检测结果比较

其中本算法进行边缘检测时需要设定的参数比较多，蚂蚁数量同图像尺寸有密切的关系，一般情况下不妨取：K=，对信息索矩阵的每一项进行初始化为0.000 1，信息索矩阵的权重因子α设为2，启发信息的权重β设为1，每个节点的相邻节点集合数设为8，衰减率ρ设为0.05，每个构造步中蚂蚁的移动次数L设为40，信息索的衰减率ψ设为1.5。

4　基于边缘的全局运动估计

当对视频图像的预处理完成后，即完成对边缘的检测，将图像所有图像处理产生边缘像素和非边缘像素两类，通过对相邻连续的图像的帧序列进行计算匹配，估计出运动矢量。对于视频运动估计可以通过对像素点的处理，也可以对边缘线的处理：

图3　视频图像运动的光流场计算处理结果

对于图像稳定系统中运动估计目的同其他应用环境中的目的是有所不同的，只需要估计出一个全局运动矢量。为了能够比较准确估计出一帧的全局运动矢量，一种行之有效的方法是对一帧图像的不同区域分别进行运动估计，通过图3也可以看出，视频图像的中央部分的局部运动比较明显，为了准确获取全局运动矢量，要尽可能避免这些局部运动的干扰。一般是取接近边缘的4个边角的位置的区域，如图4所示。由于摄像时，通常是将运动对象置为在画面的中央区域，因此在画面边缘区域由于对象运动引起的局部运动的概率比较小，相反在画面的中央区域出现局部运动的概率比较大，这种由先验经验指导的选择估计区域的方法可以保证比较准确地估计出图像帧的全局运动矢量。

图4　对图像帧进行全局运动估计的区域选择

通常情况下在连续的两帧图像中，第一帧图像的运动场称为参考场，连续的下一帧图像的运动场称为比较场。运用块匹配方法来估计4个区域相应的4个运动场，首先利用移位寄存器将前一帧的运动估计区域锁存到当前参考运动场块里，然后将当前图像场中相应的区域锁存到比较场块中，经过图像预处理后，图像中只包括边缘点和非边缘点两大类，可以用0和1表示。

通过统计参照运动场块中同比较场块中所有像素的绝对误差，进行块匹配运算。在对每个运动估计区域的边缘预处理过程中，可以将参考场中边缘图像及比较场的边缘图像都转换成了二进制边缘图像，所以就不需要进行减运算，而可以采用更加快速的逻辑异或运算［9］。

所以对参考运动场块同比较场块进行比较时，只需要比较对应点是否同时为1或0值。利用公式（11）进行匹配比较，当比较场块移动到某个位置时，出现比较场块中同参考运动场块中对应点的值相同的数目达到最多的情况时，也就是当Cmax（m，n）为最大值时，就称为最佳匹配，此时所对应的位移s（i，j）就是当前区域的运动矢量。

式中的gt0，gt1分别代表参考场块及当前场块，M×N为运动估计区域的尺寸，其中（i，j）对应当前比较场块的相对平移量，p是指在搜索窗口的最大位移量。

假设s（xi，yi）代表利用上述方法获得的4个运动估计区域的运动矢量，其中i表示4个区域中的编号。这里的s′（xi，yi）通常表示理想状态环境中检测到的运动矢量，但实际情况由于存在对比度不足、采集图像中的噪声、变焦和摇摄和运动估计区域中存在其他运动对象等原因，估算出的运动矢量，与在理想状态估计出的矢量必然会存在误差。为了尽量减少这些干扰，根据不同的环境和运动对象特点需要采集不同的策略，例如对于对比度不足和噪音等情况，这两种情况属于不可预知影响因素，可以通过在图像预处理阶段──边缘检测时利用三态匹配技术进行处理；而对于可以预知的干扰因素，例如变焦和摇摄等所引起的干扰可以通过一些传统的运动补偿技术进行预处理。

由于当整个图像帧中，存在有一个或数个运动对象，引起局部运动而造成噪声干扰的问题往往要专门处理，这里重点研究由于变焦、摇摄和运动对象引起可预知干扰的情况下如何获得理想的全局运动估计结果。首先计算独立变量：Ix（i）和Iy（i）

其中：i=1，...，4

再计算两个独立的权αx（i）和αy（i）：

其中：k1和k2分别是两个独立的常量系数。再进一步计算稳定权重sx（i）和sy（i）：

式中的（x′i，y′i）表示前一次估计出的运动矢量。

利用计算获得的独立权重αx（i），αy（i）和稳定权重sx（i）和sy（i），可以按式（15）整合得到比较准确的运动矢量，更具有鲁棒性。

从公式（13）和 （14）容易知道，随着Ix（i）和Iy（i）增加，αx（i），αy（i）成比例减少，当Ix（i）和Iy（i）增加都超过一个阈值时αx（i），αy（i）都为零。独立权重αx（i），αy（i）可以理解为是各个小的运动估计区域的运动矢量同全局运动矢量的相似度，当4个小区域估计出的运动矢量越接近，每个独立权重就越大。

当完成对图像帧的运动矢量估计后，为了对运动的比较帧的图像进行运动补偿，就要将这图像沿着这个运动矢量相反的方向进行移动。这种移动必然要扩大图像的范围，在没有任何图像边界以外信息的情况下，就需要通过数字图像插值法对参考图像和比较图像的边界进行扩充。对数字图像进行插值的方法有许多，其中最经典的同时也是最简单的一种插值方法就是最近邻居复制插值法，即需要插值点就复制最近邻居的像素点的值。这种方法的优点是比较容易通过硬件直接执行，实时性比较高，缺点是在斜线边缘容易产生马赛克效应。当然还有一些比较精细的插值算法，比如高次多项式插值算法［10］，和级次滤波器保留边缘插值法，这些方法都能对数字图像的插值效果获得比简单的最近邻居复制插值法好很多，但缺点是由于这些方法的计算复杂，耗时很多，而且不适合利用硬件来进行实时运算。为了满足兼顾运算速度和插值精度的要求，对于一般的数字图像稳定系统中，变焦范围不能太多，否则影响精度，原则上对于变焦不超过1.5倍的情况，为了实现速度和精度的双重需求，可以使用一种逼近双线性插值法来实现有级缩放图像。一旦检测到了运动矢量，运动补偿工作就要开始执行，整个图像被按照这个矢量方向相反的方向移动。这时运动补偿和逼近双线性插值要同时协调进行。

5　实验与分析

在对标准灰度视频序列乒乓球（图5）和花园（图6）进行了仿真实验中，图像帧的分辨率为352×240，对连续的帧图像4个顶点尺寸为60×40像素的小区域进行采样计算［11］。

图5　乒乓球视频的32-34帧

图6　花园视频20-22帧

例如利用全域匹配（full search FS）方法和本算法，分别是对全图进行匹配计算和对4个小区域进行计算，对不一定数量的连续帧计算，得到的估计帧和原始实际真的平均方根错误（MSE）趋势数据如图7所示。

图7　计算不同帧数的视频序列的MSE值趋势图

对不同视频序列计算得到的估计帧和原始实际帧的平均方根错误（MSE）的平均值如表1所示。

表1　对准视频的运动估计平均MSE值比较

对全局运动进行估计的时候，每一帧图像搜索的像素点个数是352*240=84 480个。在本算法中对于每一帧搜索的是4个小区域，对应的像素点个数是60*40*4=9 600个，所以计算量减少了接近9倍（84 480/9 600=8.8）。而且本算法可以结合边缘检测的预处理结果，将一幅图像进行处理后所有的像素点都被分成缘点和非边缘点两类，可以用二进制0和1表示，如果配置专用硬件设备，这样进行全局估计匹配的时候仅仅需要进行逻辑与或计算 （公式11），能够更进一步提高匹配速度。从图7和表1可以看出本算法的运动估计误差要比对全图进行计算估计要更小一些，尤其是对乒乓球标准视频的估计准确性更高，这是由于乒乓球视频中存在由于球体和手臂等快速移动对象引起的局部运动，在全局匹配的算法中，这些干扰被累加到了全局运动估计中了，引起了估计误差，而本算法由于只对四周几个小区域进行匹配计算，能有效避开了快速运动引起局部运动的干扰，所以对精确度提高效果更加明显，花园视频的中这种局部运动引起的干扰基本不存在，所以两者全局运动估计误差基本接近。

6　总结

本文首先研究的就是利用选取图像中的典型特征边缘线作为运动估计的基本单元，比如线和拐点等，一般来说，随着图像特征层次的提高，将更有利于进行图像处理和分析。为了克服传统边缘检测方法计算量大，耗时多的缺点，通过将的粒子群优化算法原理与万有引力原理的方法想结合，利用万有引力原理进行启发函数的计算结果指导粒子群运动趋向，从而快速检测出边缘线。另外，利用视频帧图像中，快速移动对象集中在画面中央的概率比较大的特性，为了能够比较准确估计出一帧的全局运动矢量，采取对一帧图像的不同区域分别进行运动估计，一般是取接近边缘的4个边角的位置的区域，这样既可以避开画面中央局部运动数据引入全局运动估计的干扰，同时减少了运动估计匹配的计算量，通过实验表明，在保证精度的情况下，运算速度提高了接近9倍，这对于视频运动估计，编码压缩和解码都具有非常重要的意义。

［1］Ziou，Tabbone S.Edge Detection Techniques-An Overview［J］. International Journal on Pattern Recognition and Image Analysis. 1998，8：537-559.

［2］Wu J，Yin Z，Xiong Y.The Fast Multilevel Fuzzy Edge Detection of Blurry Images［J］.IEEE Signal Processing Letters.2007，14（5）：344-347.

［3］Genyun Suna，Qinhuo Liua，Qiang Liua，et al.A novel approach for edge detection based on the theory of universal gravity［J］.Pattern Recognition，2007，40（10）：2766-2775.

［4］Hanmandlu M，Verma O P，Gangwar P，et al.Fuzzy Edge and Corner Detector for Color Images［J］.in Proc.ITNG.2009：1301 1306.

［5］Setayesh M，Zang M and Jonhnton M.A new homogeneity-based approach to edge detection using PSO［J］.24th International Conference Image and Vision Computing.New Zealand （IVCNZ）. 2009：231-236.

［6］VermaO P，Hanmandlu M，KumarP，etal.A NovelBacterial ForagingTechniqueforEdge Detection ［J］.Pattern Recognition Letters.2011，（8）：1187 1196，2011.

［7］Fu W L，Johnston M，Zhang M J.Genetic Programming for Edge Detection：A Global Approach［J］.Proceeding of the 2011 IEEE Congress on Evolutionary Computation.IEEE Press.2011：254-261.

［8］Verma O P，Sharma.An Optimal Edge Detection using Universal Law of Gravity and Ant Colony Aglorithm［A］.Information and Communication Technologies（WICT），2011nWorld Congress on Date of Conference［C］.2011：507-511.

［9］祝晓东，郁松年.运用视频技术的快速三维旋转分析与计算的研究［J］.计算机科学，2013，40 （2）：289-299.

［10］Netravali A N，Haskell B G.Digital Pictures-Representation and Compression［M］.Plenum Press，1988.

［11］祝晓东，徐济惠，郁松年.视频分析中全局运动矢量快速估计的研究 ［J］.计算机工程与设计，2013，34（3）：965-970.

Research Fast Edge Detection and Motion Estimation in Digital Video Analysis

Xu Jihui1，Zhu Xiaodong1，Liu Chuijuan2，3，Guo Guowen2
（1.Ningbo City college，Ningbo200072，China；2.Institute of Intelligent Control of Zhejiang Wanly College，Ningbo315100，China；3.Department of Information Science and Engineering，Ningbo University，Ningbo315100，China）

This paper first study the edge detection based on particle swarm optimization algorithm and universal gravitation algorithm in this paper.Using the principle of universal gravitation to calculate the heuristic function，guide the ant colony movement trend，and quickly detect the edge of the line.The detection results can be used as the preprocessing results of image analysis.We propose a global motion estimation based on several small domain data of the image according to the video of the local image motion is concentrated in the central part of the image of greater probability characteristics.In this way the amount of computation can be greatly reduced.We sampled four of 1/6 rectangular area original length in the experiment of global estimation.The experiment proves that the operation speed is increased by about nine times in the same accuracy.

video；particle swarm optimization algorithm；global motion estimation；edge detection；estimation error

1671-4598（2016）05-0242-04

10.16526/j.cnki.11-4762/tp.2016.05.068

TP306

A

2016-03-09；

2016-03-30。

国家自然科学基金项目（61103054）；浙江省科技厅/公益项目（2012C21032）；宁波市科技计划项目（2014C50018，2015C50053）；浙江省教育厅科研项目（Y201329047）。

徐济惠（1964-），男，浙江宁波人，副教授，主要从事图像处理，视频图像分析等方向的研究。