结合光流法与最近邻算法的运动目标检测

鲁春，杨会成，杨文斌，朱文博

(安徽工程大学电气工程学院, 安徽芜湖241000)

结合光流法与最近邻算法的运动目标检测

鲁春，杨会成，杨文斌，朱文博

(安徽工程大学电气工程学院, 安徽芜湖241000)

运动目标检测具有广泛的理论和现实意义，光流法是检测运动目标的重要方法之一。但是用于运动目标检测的光流算法却有着计算量大、处理复杂的问题。一种聚类分析算法和改进的LK光流法相结合检测方案可以很好地解决此类问题。对基于改进的LK光流法的运动目标检测算法进行了分析和仿真，再加以聚类分析使得检测出的运动目标更加准确。首先对图像序列进行采样与预处理，并利用LK光流法计算得出相邻帧图像的光流场，然后再利用最近邻聚类算法对得到的光流场进行处理，进而检测出图像中的运动目标，最后使用Matlab软件进行算法程序验证。通过实验可知，基于金字塔LK光流法与最近邻算法的运动目标检测方案可以更加有效地检测出运动物体。

运动目标检测；LK光流法；金字塔；最近邻聚类算法

引言

计算机视觉的最终目的就是使用计算机等智能设备来代替人去对周围环境进行感知、解释及应答。近年来，对动态目标进行识别与跟踪是图像处理与计算机视觉领域中一个不可或缺的分支，对这方面的研究引起许多国内外学者的重视，并且已经有许多研究所开始了有关的基础与开发研究。

运动目标检测就是在找寻运动的区域，目的就是把静止的像素点跟运动的像素点分开。一般地，视频图像会被分为两类：一类如监控视频般，背景静止；一类如车载视频般，背景不静止。其实，在现实生活中不会存在完全静止的背景，天气、光照等环境的变化都可能使得背景变化。主要的检测算法有光流法、帧间差分法和背景差分法三种[1]。背景差分法，就是固定摄像头，利用背景与运动目标之间的差别来检测运动目标。这种方法有着精准、速度快的优势，但是易受外部环境变化的影响。结合帧间差分法可以有效地克服局部运动以及噪声等外部环境的影响[2-3]。帧间差分法，就是取相邻两帧或者三帧图像之间的像素差来提取运动目标。光流法[4-5]就是将帧图像中灰度的变化与二维速度场联系起来，用光流场反映像素点运动的方向和速度，并根据光流场的分布特征来提取运动目标。用光流法结合帧间差分法[6]、光流的改进算法等算法间的相互结合[7-10]，有效地解决了光流法计算量大，处理复杂的问题。

聚类算法作为数据分析中广泛使用的主要方法之一，已经广泛应用于模式识别、机器学习、图像处理和数据挖掘等方面[11-14]。简单来说，聚类分析就是根据数据的特征将数据进行分类，使得属于同一类别的数据间有尽可能多的相同特征，而属于不同类别数据间的特征则尽可能不同。目前，常用聚类分析算法可以分为划分法、层次法、基于密度的方法、基于网格的方法和基于模型的方法[15]。

本文提出了基于金字塔(Lucas-Kanade，LK)光流法和聚类分析算法相结合的运动目标检测方案，并以前方行驶车辆作为检测的运动目标[16-17]，使用金字塔LK光流算法，克服了传统光流法计算量大，处理复杂等问题。结合最近邻聚类分析算法，大大提高了运动目标检测的准确性。

1 运动目标检测流程

在运动目标检测过程中，第一步是对摄像机采集到的图像序列进行重采样和预处理；第二步是利用金字塔改进光流法计算出各点的光流值，得出各点的光流场；第三步是利用最近邻规则聚类算法对光流场进行分割，得到运动目标区域。

1.1光流场算法

光流法的前提假设：

(1) 假设相邻视频帧之间的亮度恒定。

(2) 假设相邻视频帧之间的取帧时间连续，或者相邻视频帧之间物体的运动变化量比较微小。

(3) 保持空间的一致性，即同一子图像的像素点具有相同的运动。

光流场的目的是找到视频帧图像中每个像素点的速度向量[6-8]。设在t时刻像素点(x,y)处的灰度值为I(x,y,t)；在t+dt时刻，该像素点更新到位置(x+dx,y+dy)，灰度值为I(x+dx,y+dy,t+dt)。根据上面的光流法前提假设可知，在给定的邻域内的速度向量场的变化是缓慢的。

I(x,y,t)=I(x+dx,y+dy,t+dt)

(1)

用泰勒公式将上式展开：

I(x+dx,y+dy,t+dt)=

(2)

忽略无穷小项ε，

(3)

Ixu+Iyu+It=0

(4)

(5)

方程(4)～(5)为光流的约束方程，包含 、两个未知变量，本文选择用Lucas-Kanade光流法解决这个问题。

1.2 LK光流法

可以利用LK光流法算法对以上的问题进行求解。若该像素点与邻域内的点运动情况相似，为了求解该像素点的运动信息，则可利用以下条件求解光流，在该点邻域空间内建立约束方程，并联立方程以求解光流矢量。

假设在(u,v)的一个小的局部邻域内亮度恒定，那么：

(6)

即：

(7)

其中：

经计算可得：

(8)

(9)

由于LK光流法有一定的缺陷，需要在设置邻域窗口后计算光流。窗口较大，光流量的计算更加鲁棒；而窗口较小时，光流量的计算更准确。但由于运动的每个部分的图像不一致，如果窗口开得太大，很容易违反第三个前提。如果窗口很小，则包含更少的像素，更精确些，但当运动相对较为剧烈的时候，无法实现光流的基本假设。

1.3光流法的改进

对于LK光流法，速度小、亮度恒定、区域一致性强，对于这些假设都不容易满足。例如，当物体移动的速度变得更快时，则假设不满足，随后的假设将具有较大的偏差，这使得考虑车辆行驶速度较大时光学流量值会具有较大的误差，这使得算法可能出现较大的误差。于是寄希望降低图像中物体的运动速度，就是缩小图像的像素。假设，初始图像的像素为400×400，物体的运动速度为[16，16]，将图像的像素缩小至200×200，那么物体的运动速度将变为[8，8]，将图像的像素缩小至100×100，那么物体的运动速度将变为[4，4]。所以对源图像进行了大量的缩放后，原算法变得适用。所以光流可以由原始图像生成的金字塔图像[6-7]逐层求解，不断精确地寻找。

首先，引入两个光流量：剩余光流量和猜测光流量。对于第层光流，通过从层的精确光流量输出的猜测光流量gL和在修整后基于该层获得的剩余光流量dL获得。获得的L层的光流量：

kL=gL+dL

(10)

根据层的精确光流量，可得层的猜测光流量，两者关系：

gL=2×kL-1=2×(gL-1+dL-1)

(11)

由于第层到第层为采样一半，那么光流量相应地也该减半，因此粗略估计不准确。为了精确地计算出第层的光流量，还需要使用基本流量方程去计算得出第层中剩余光流量。基本光流方程为：

(12)

其中，IL(x,y)为原图，JL(x,y)为参考图，(dx,dy)为在(ux,uy)处的光流向量，(wx,wy)为(ux,uy)的搜索半径。

由于先前的光流层提供的先验信息，允许光的流动跳出(wx,wy)的约束并进一步移动，从而解决了前文提到的有关窗口大小的问题。

1.4基于金字塔光流法光流场求解

光流法可以动态地分析图像，检测图像中的运动物体。如果图像中没有运动物体，则在整个图像区域中光流矢量的变化是连续的。当图像中存在运动物体时，目标与图像背景之间存在相对运动，运动目标形成的速度矢量与邻域背景速度矢量不同，以检测运动目标及其位置。光流法检测运动物体的问题主要是由于光流法运算量大、缺乏实时性和实用性。对于那些运动速度太快的对象，它们将违反路光流法假设(2)与假设(3)。本文提出了改进的金字塔光流算法[10]，首先对图像进行预处理，然后进行金字塔光流运算。这样不仅可以检测出速度较快的运动目标，而且可以减少计算量，提高系统的实时性。

具体步骤如下：

(1) 视频序列中图像预处理、去噪。

(2) 取连续两张图像I、J，在点处的灰度值为和，并且已知图像I中此点的速度为，图像J中此点速度为。

(3) 将建立金字塔模型，。初始化金字塔光流估计值，层图像上点的速度为。

(4) 初始化剩余光流量，并根据基本光流方程计算层的光流值。

(5) 计算层的光流，以此类推得到最后的光流值。图像J中对应点为。

1.5最近邻聚类算法

聚类分析是根据收集的某些或某些因素将多个类别进行分组的过程。在这个过程中，集合中的每个组件都尽可能地具有相同的特征。对于其他组件，特性尽可能不同。最近邻聚类算法是一种基本的聚类分析算法。在前车检测中，同一物体在两个连续的视频帧流中具有连续的特点。连续性是最近邻聚类算法的基础。位于同一运动物体上的点必然是距离相对较近的点。如果在两个相邻的数据点发生了巨大的变化，那么这两点可以认为是属于两个不同的对象。相反，如果两个数据点之间的距离很小，那么这两点可以认为是两个数据点属于同一个对象。

首先计算同一视频帧中相连两点的光流量差值，之后将计算得到与设定的阈值进行比较，若，则可以确定这两点属于同一类，反之则确定这两点属于不同的类。在整个算法中，聚类阈值的选取是非常关键的一步，对聚类结果有很大的影响。如果阈值选择的过小，可能会将同一个目标分割成多个部分，同时对算法实时性也有影响。而阈值选择过大，则会将两个或多个目标混为一个目标，影响算法的准确性。

1.6结合LK光流法与最近邻算法的检测方法

相对于传统光流法，本文提出一种结合改进LK光流法与最近邻算法的检测方法，该算法使用基于金字塔的LK 光流算法，将可能存在运动目标的区域提取出来，通过最近邻算法在该区域内外选取各自不同的阈值来进行提取目标，这样便将阈值分割与区域分割结合起来，完成运动目标的检测提取。具体步骤为：

(1) 计算同一视频帧中相连两点的光流量差值。

(2) 将计算得到与设定的阈值进行比较，若，则可以确定这两点属于同一类，反之则确定这两点属于不同的类。

通过上述流程，就可以确定出视频帧中最可能存在运动目标的大致区域。

2 实验结果与分析

本文选用一段视频中的1260帧图像作为实验数据库，将图像中前方行驶车辆作为检测目标对本文方案进行检测，并进行传统方法与结合聚类分析的检测方案相比较。使用Matlab软件对于金字塔LK光流法的汽车前方车辆检测方法进行了分析和仿真，通过计算得出相邻帧图像的光流，然后用最近邻聚类算法对图像的光流进行检测。

为了更好地检测到运动目标，本文将在视频序列中随机选取相邻两帧图像，图像大小为175×120，如图1所示的前两张前车图像，根据本文算法计算得出其光流场，并与相邻两帧图像中的后者叠加，以判断是否检测出前方行驶车辆的大致位置。判定金字塔LK光流法是否可以确定视频帧中移动目标的大致区域。

图1 金字塔LK光流法

图1运用金字塔LK光流算法对视频中相邻两帧图像进行初步的光流处理，并根据得出的光流差值图大致判断出前方是否有行驶车辆，给出了大致位置。由表1可知，改进的金字塔光流算法的运算速度可达到0.153秒/次，相比较于传统的光流算法提高了0.564秒，大大地减小了运算量，达到减小运算时间的目的，提高了检测效率。

表1 两种算法的平均计算时间

本文通过实验确定阈值。首先设定最近邻聚类个数k, 初始化k=1开始，使用检验集估计分类的错误率。每次k增加1，当产生最小错误率最小时，选择其中最大光流差值设为阈值，本文的设定阈值mth=0.24。

图2在金字塔LK光流算法的初步处理所得到的光流值的基础上，根据最近邻聚类算法并由实验得出光流阈值。利用值对光流场进行分类处理，以更加具体的框出前方行驶车辆，并与传统的运动物体检测方法比较。

图2 两种方法的比较

相比较传统方法与结合最近邻聚类分析算法的运动目标检测方法，后者可以更加具体、准确地检测出前方行驶车辆。本文采用 CVPR 2013 Benchmark 提出的评价标准[18]，根据空间鲁棒性对检测的精确性进行评估，给出在中心位置误差阈值为40个像素点时的结果，其评估结果如图3所示。

图3 SRE精确度图

根据图3可知，本文方案的精确度可达到0.8409。与传统方案的精确度相比较提升了0.0454。在对前方车辆检测与跟踪中，使用此方法检测出前方行驶车辆，对其进行训练生成检测器，进而可以更加有效地进行检测与跟踪。

3 结束语

本文提出了基于金字塔LK光流法检测前方行驶车辆，结合最近邻聚类算法，可以更加有效地检测出前方行驶车辆。本文使用Matlab软件对提出的组合算法进行了分析和仿真。通过实验，组合金字塔LK光流法与最近邻聚类算法可以更准确地检测前车。

[1] 程爱灵,黄昶,李小雨.运动目标检测算法研究综述[J].信息通信,2017(1):12-14.

[2] 刘仲民,何胜皎,胡文瑾,等.基于背景减除法的视频序列运动目标检测[J].计算机应用,2017,37(6):1777-1781.

[3] 孙挺,齐迎春,耿国华.基于帧间差分和背景差分的运动目标检测算法[J].吉林大学学报:工学版,2016,46(4):1325-1329.

[4] 关兴来,谢晓竹.基于光流的运动目标检测跟踪快速算法[J].微计算机信息,2012,28(10):421-423.

[5] 张利平,赵俊梅.基于光流的运动车辆检测和跟踪技术的研究[J].车辆与动力技术,2014(2):61-64.

[6] 袁国武,陈志强,龚健,等.一种结合光流法与三帧差分法的运动目标检测算法[J].小型微型计算机系统,2013,34(3):668-671.

[7] 张忠义.基于改进LK光流的目标跟踪算法研究[J].信息技术,2015(10):127-130.

[8] 朱俊杰,李胜,侯保林,等.基于金字塔LK算法的运动目标的检测[J].工业控制计算机,2015,28(9):13-15.

[9] 郝慧琴,王耀力.基于帧间差分和金字塔光流法的运动目标检测[J].电视技术,2016,40(7):134-138.

[10] 陈添丁,胡鉴,吴涤,等.稀疏光流快速计算的动态目标检测与跟踪[J].中国图象图形学报,2013,18(12):1593-1600.

[11] 冯柳伟,常冬霞,邓勇,等.最近最远得分的聚类性能评价指标[J].智能系统学报,2017,12(1):67-74.

[12] 秦亚辉,何利力.基于分块后重叠K-means聚类的KNN分类算法[J].工业控制计算机,2017,30(2):103-104.

[13] 孙水辉.聚类分析在学生成绩分析中的应用[J].中国管理信息化,2016(6): 229-230.

[14] 许进文.数据挖掘中聚类分析算法及应用研究[J].计算机光盘软件与应用,2013(6):176-177.

[15] 张静.数据挖掘中聚类分析综述[J].价值工程,2014,33(15):226-227.

[16] SHUKLA D,PATEL E.Speed determination of moving vehicles using Lucas-Kanade algorithm[J].International Journal of Computer Applications Technology & Research,2013,2(1):32-36.

[17] INDU S,GUPTA M,BHATTACHARYYA A.Vehicle tracking and speed estimation using optical flow method[J].International Journal of Engineering Science and Technology,2011,3(1):429-434.

[18] WU Y,LIM J,YANG M H.Online object tracking:a benchmark[C]//Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition,Portland,OR,USA,June 23-28,2013:2411-2418.

MovingObjectDetectionMethodCombinedOpticalFlowandK-NearestNeighborAlgorithm

LUChun,YANGHuicheng,YANGWenbin,ZHUWenbo

(College of Electrical Engineering, Anhui Polytechnic University, Wuhu 241000,China)

Moving object detection has great significance in theory and practice, and optical flow is one of the important moving object detection methods. A method to detect moving objects combined K-Nearest neighbor algorithm and pyramid LK optical flow is proposed to solve such problems，as the optical flow algorithm for moving target detection has a large computational complexity and a complex problem. Analysis and simulation of moving target detection based on the improved Lucas-Kanade optical flow algorithm are given, and then the clustering analysis is made to make the moving object more accurate．Firstly, the image sequences of moving target are sampled and processed. Then Lucas-Kanade optical flow method is used to calculated the adjacent frames of light flow to get the optical flow field. Lastly, the K-Nearest neighbor algorithm is used to detect the moving object. The experiments prove that the object detection algorithm combined Lucas-Kanade algorithm and K-Nearest neighbor algorithm is an efficient moving target detection method.

moving object detection; Lucas-Kanade optical flow; pyramid; K-Nearest neighbor algorithm

TP391

A

2017-08-20

安徽省高校自然科学研究重大项目(KJ2014ZD04)

鲁 春(1993-),女,安徽滁州人,硕士生,主要从事图像处理方面的研究,(E-mail)1114510762@qq.com

1673-1549(2017)05-0063-06

10.11863/j.suse.2017.05.11