基于谱聚类和增量学习的运动目标物体检测算法研究
黄伟1, 杨文姬2, 曾璟1, 曾舒如3, 陈光4     
1. 南昌大学 信息工程学院, 江西 南昌 330031;
2. 江西农业大学 软件学院, 江西 南昌 330045;
3. 华中光电技术研究所, 湖北 武汉 430223;
4. 西安通信学院, 陕西 西安 710072
摘要: 运动目标物体检测是计算机视觉领域的热门研究方向之一。该方向的一些复杂问题,例如:环境光照变化、目标物体部分/全遮挡、目标物体刚性/非刚性形变等,仍极具挑战性,并制约检测算法效果的进一步提高。为此,提出了一种新颖的运动目标物体检测算法。该算法采用了增量学习技术,融合了视频相邻帧在空间和时间上的高相关性,在每个测试帧上都利用其相邻帧的训练数据进行模型的自学习与更新,从而保证了模型在不同环境或复杂背景下能自动调整。为了实现模型学习,还提出并采用了一种新颖的谱聚类技术。该算法通过一个由1 000多帧的视频数据库验证,采用统计学中的方差分析和多重对比等实验手段,综合分析了该算法与其他同类经典算法的效果。通过大量统计分析,结果表明,该新颖检测算法比传统算法在运动目标物体检测的准确性和鲁棒性上都有明显提高。
关键词: 算法     谱聚类     增量学习     运动目标物体     检测    

运动目标物体检测是指在视频或图像序列中, 把感兴趣的运动目标前景物体与背景或其他非关注的前景物体, 在该视频或图像序列中的每一帧中, 都进行区分的过程。一般来说, 运动目标物体检测可视为在视频或图像序列上, 具有时间和空间高相关性的一类广义图像分割问题。现代运动目标物体检测研究, 融合了数字图像处理、模式识别、机器学习、人工智能等多学科领域的先进技术和研究成果, 是计算机视觉领域的重要研究方向之一。

近年来, 运动目标物体检测获得了不少国内外知名研究者的关注[1-7]。例如:悉尼科技大学的陶大程教授研究团队通过剖析传统单视角学习策略, 提出了一种基于无损空间学习机制的多视角学习策略;并将互补编码信息引入运动目标物体的潜在特征表征中, 用于实现物体在检测过程中的多视角学习[3]。在该团队的另一项近期工作中, 将认知心理学理论融入运动目标物体的视觉特征构造中;提出了一种可以保留目标物体形状信息的多重跟踪算子[4]。在国内, 西北工业大学张蓬教授研究团队也进行了很多深入研究, 其中包括将基于马尔可夫链的多重状态学习和更新运用在行人的跟踪问题等特定运动目标物体的检测研究[5-7]。从上述研究工作可以看出, 学习机制在运动目标物体检测研究中不可或缺。这种在模式识别领域流行的“训练(学习)-验证-测试”思想可有效地帮助实现基于视频数据的模型参数自动调整和定参, 从而避免繁重的人为调参负担。此外, 还可看出:在设计运动目标物体检测算法时还须考虑视频相邻帧在时间上的高相关性, 以及视频每一帧目标物体在空间上高相关性。

本文提出了一种基于谱聚类和增量学习思想的运动目标物体检测新算法, 此算法能满足上述时间、空间高相关性和学习机制等所有要求。其中, 增量学习用于实现其学习机制。对于第N帧视频, 由于它的时间、空间高相关性, 其相邻视频帧:(N-2)、(N-1)、(N+1)、(N+2)等, 都会对其模型学习与模型参数的确定产生直接影响。因此, 采用增量学习可以实现本文算法中模型学习伴随视频帧推演而自行更新, 进而能达到良好应对运动目标物体检测视频中复杂问题(例如:环境光照突变、待检测目标物体被部分甚至全部遮挡、待检测目标物体发生刚性或非刚性形变等)的目的。此外, 本算法的像素间相似度函数构造采用了基于空间信息特征的高斯径向基函数和基于视觉信息特征的马式距离相结合的方式;但学习该相似度函数的待定参数采用了基于增量学习思想的一类新颖的谱聚类算法, 使得本文算法在理论上与其他同类研究算法大不相同, 具备理论创新性。

1 人机交互及抽样策略

本文的算法是一种半自动的方法, 可以由终端用户采取人机交互的方式, 将其具备的先验知识作为算法的输入量传递进来。在具体实现过程中, 终端用户可以通过鼠标或者触摸屏等传统人机交互的方式, 在视频的第一帧上通过勾勒一个感兴趣区域(region-of-interest, ROI)的方法将待检测的目标物体在第一帧中确定。该ROI的勾勒不需要紧贴目标物体轮框, 只需要包括物体本身即可。这样做的目的可以使终端用户对物体在该视频第一帧上的空间先验知识通过ROI勾勒的方式传递给算法, 从而算法将在该ROI区域内自动抽取表征目标物体的正样本点和在ROI区域外自动抽取表征背景的副样本点。

图 1 检测算法增量学习的实现思想

对于正样本来说, 理论上它们都来自目标物体本身。由于物体本身的视觉统一性和组成物体的像素在空间上的高相关性, 正样本可以在勾勒的ROI中心区域中直接抽取。而对于负样本来说, 抽取过程就复杂得多, 大多数工作采取了随机取样的思想。但由于视频数据在颜色、边缘等初等视觉特征在描述上一般存在复杂的分布, 所以对负样本点随机抽样并不能准确地反映所有背景像素点的真实特性和分布, 从而不可避免地给模型学习结果带来偏置。因此, 本算法在负样本抽取中, 采取了一种分层抽取的新策略。该策略通过下列2个公式执行内曼分配法则来实现。

(1)
(2)

式中, n表示需要抽样的负样本总数;L表示全体负样本点的分层数;σl表示第l层全体负样本视觉特征的标准差;Rl表示第l层全体负样本(Nl)占该帧全体负样本的百分比;nl描述按照内曼分配法则从第l层须抽取的负样本个数。由公式(1)和(2)可知, 如果某一层负样本占该帧全体负样本的比重高(Rl值大)且具备丰富的视觉特征差异(σl值大), 则该层负样本所具备的信息量就越大, 需要从该层抽取的负样本数量就越多(nl值大)。这种分层抽样的策略能有效地避免随机抽样本身鲁棒性不足等缺点, 增强样本点抽样的可信度, 有助于模型学习效果的提高。

2 相似度及谱聚类学习

一般而言, 聚类是将具体或抽象的对象集合分成由类似对象所组成的多个类的过程。由此可知, 合理构造一个相似度函数, 使它能客观、准确地定量反映2个对象之间的相似程度是影响聚类算法效果好坏的直接因素之一。本文算法引入了一种融合空间信息和视觉特征信息的相似度函数, 并用来定量计算视频每一帧中2个像素点之间的相似程度。该相似度函数中的未知参数, 将通过一类新颖的谱聚类方法来学习。

对于视频每一帧中的任意2个像素点xixj, 可以构造如下的相似度函数:

(3)

式中, σp2是一个标量;A是一个全矩阵;以上2个参数都是公式(3)的待定参数。pi表示像素点i的归一化空间坐标, 而si是从像素点i中提取的视觉特征信息。显然, 公式(3)等式右边第一项是指数形式的高斯径向基函数, 它定量带入了2个像素点的空间信息, 右边第二项是指数形式的马式距离, 它着重关注了2个像素点的视觉特征信息。在著名的Normalized Cut算法中, 只有公式(3)等式右边第二项被显式代入到相似度计算中, 且该算法的待定系数A是一个对角阵, 非全矩阵[8]。因此, normalized cut算法的相似度构造, 实际上忽略了不同维度特征向量之间的相关性, 仅存在每个向量维度内的放缩关系。在另一个流行的Ng-Jordan-Weiss算法中, 也只有公式(3)等式右边第一项被显式采用[9]。因此, 本算法中相似度函数公式(3)与国际上其他基于图论算法中的相似度函数定义都不相同。

为了确定公式(3)的未定参数σp2A, 本算法根据谱聚类技术进行了相似度学习。谱聚类是一类基于图论的特殊聚类方法, 它将传统聚类问题转化成图的最优化分割问题:即分割后的子图内部边权重最高, 不同子图间的边权重最低。本算法中的谱聚类方法的输入是此前经过人机交互和分层采样策略获得的n个像素点(即训练集)。谱聚类学习相似度函数的主要步骤如下:

1) 初始化未定参数σp2A

2) 对训练集中所有n个像素点, 通过公式(3)计算每2个像素之间的相似度, 并将其作为元素组成一个关联矩阵DRn×n

3) 定义一个对角矩阵C, 其主对角线元素是矩阵D中对应行中所有元素相加之和。

4) 定义一个graph Laplacian矩阵:

(4)

并利用特征分解的方式找出Lk个最大特征值和特征向量。在本文中, 设k=2, 对应于每一帧图像中的像素, 都可以被聚类为运动目标物体和背景2个类别。

5) 通过列堆叠的方式, 根据这k个最大特征值所对应的特征向量来定义一个新矩阵XRn×k

6) 通过构造一个Frobenius范数的最优化问题, 利用梯度下降法求解未定参数σp2A的最优解:

(5)
(6)

式中, E代表矩阵数据集的分区;B是一个任意的正交矩阵;A≥0是该最优化问题的约束条件, 描述矩阵A的半正定性。

以上步骤在一段视频的头一帧上采用, 得到该帧的模型, 学习结果后, 将该结果用于该帧的目标物体检测(测试集数据聚类)。在本算法的增量学习框架中, 第N帧之前的若干帧和其后的若干帧, 都可以提供第N帧模型的训练集;这些训练数据中, 正负样本的选取是根据在线学习模型产生的每一帧初步目标物体检测结果。其中, 从被检测物体上抽取正样本、从其他背景中分层抽取负样本。由此, 本算法的离线增量学习算法可以在视频每一帧上学习和更新模型, 而模型本身对于视频中出现的光照突变、遮挡、形变问题等也可以自动调整。

3 实验分析 3.1 实验数据和比较方法

本文进行实验所用的视频数据, 主要由国际上运动目标物体检测研究领域中的标准视频数据和为了研究光照突变、遮挡、形变等突发问题自行采集的数据两部分组成。视频包括“自行车”、“鱼”、“摩托车”、“蓝衣服行人”、“棕色车”、“黄衣服行人”等10多个主题, 总帧数为1 412帧。所有视频都经过高斯去噪进行了预处理(采用均值为0.1、方差为0.01的高斯函数构成的滤波器)。将每帧视频的每个像素点上的归一化HSI分量和RGB空间的归一化B分量提取出来, 组成该像素点的4维视觉特征列向量(即公式(3)中的), 每个像素点的归一化二维坐标组成该像素点的二维空间特征列向量(即公式(3)中的A)。

包括本论文提出算法在内的一共7种算法, 在上述数据组成的数据库中进行了实验比较和分析。这7种方法包括:“谱聚类+在线增量学习”、“谱聚类+离线增量学习”、“SVM+在线增量学习”、“SVM+离线增量学习”、“SVM+普通学习”、“谱聚类+普通学习”、“k-means无学习模型”等。其中, “谱聚类+离线增量学习”是本文介绍的算法;SVM指支持向量机。采用其他比较方法的原因详述如下:“谱聚类+在线增量学习”是按照本文算法实现框架, 但仅考虑采用第N帧之前的数据作为采用第N帧模型的训练集, 这样比较可以验证更多时间高相关性数据对模型训练效果的影响;“SVM+在线增量学习”和“SVM+离线增量学习”都按照本算法中的增量学习思想, 但采用SVM分类模型进行目标检测, 目的是验证谱聚类模型的效果;“SVM+普通学习”和“谱聚类+普通学习”都是根据传统模式识别中采用头几帧数据进行模型训练后, 将学习模型运用到视频所有帧的普通学习思想, 比较的目的是为了说明增量学习思想的优势;“k-means无学习模型”是不带有学习机制的算法, 用来说明引入学习思想能提高效果。

3.2 实验分析

在每一帧视频中, 共有8个框表示7种算法的检测结果和标准结果。其中, “谱聚类+在线增量学习”用灰度68表示、“谱聚类+离线增量学习”用灰度77表示、“SVM+在线增量学习” 用灰度104表示、“SVM+离线增量学习” 用灰度29表示、“SVM+普通学习” 用灰度174表示、“谱聚类+普通学习” 用灰度159表示、“k-means无学习模型” 用灰度142表示。标准结果用灰度227表示。

图 2是检测视频中一辆棕色轿车的结果。这段视频的跟踪难点, 在于目标物体被视频中的其他不同物体(例如同向移动的行人、相向移动的车辆、自行车等)部分甚至完全遮挡;伴随着视频的推演, 该场景也产生了明显的光照变化, 同时目标物运动速度较快。其中每一组左侧图中唯一的灰度227框表示标准检测结果;右侧图展示了包括标准框在内, 由7种不同方法共计产生的8个不同灰度检测框。由图中的检测结果可知, “谱聚类+离线增量学习”算法在所展示的8帧图像中的大部分都非常接近标准框。具体说来:在a)~d) 4帧图像中, 产生灰度68预测框的“谱聚类+离线增量学习”算法, 比产生灰度77预测框的“谱聚类+在线增量学习”算法更接近标准框;这是因为离线增量学习模型的训练数据来自测试帧之前和之后的数据, 这比在线增量学习模型的训练数据仅仅来自于测试帧之前具有更多时间相关性和数据代表性。因此, 运用离线增量学习的机制所学习的模型检测性能更加稳定。同样的结论也可以从在图 2a)~d)4帧图像中产生灰度29预测框的“SVM+离线增量学习”算法和产生灰度174预测框的“SVM+普通学习”算法、产生灰度104预测框的“SVM+在线增量学习”算法的对比得出。

图 2 运动目标物体检测实例

以上带有增量学习的方法检测结果, 都强于采用普通学习的方法和无学习方法。这说明本文提出的新算法在图 1的视频中, 可以获得比其他方法更好的定性检测效果。

为了对检测结果进行定量分析, 本文对每种方法所产生结果, 与标准框的差异进行2种定量方式的计算和统计, 这2种定量方式是覆盖率和质心差。覆盖率是指采用算法得到的检测框与标准框重叠区域的百分比;而质心差则是采用算法得到的检测框的中心与标准框中心之间的直线距离。因此, 覆盖率越大, 检测准确率越高;质心差越小, 检测准确率越高。

图 3图 4的统计箱图是根据所有视频数据的检测结果。方法1到方法7依次为:“SVM+离线增量学习”、“SVM+在线增量学习”、“SVM+普通学习”、“k-means+无学习”、“谱聚类+普通学习”、“谱聚类+在线增量学习”、“谱聚类+离线增量学习”。在每个统计箱图中, 水平中线表示不同方法相对于标准框覆盖率/质心差的中位数, 而每个统计箱的上下边缘由2条水平直线表示, 代表覆盖率/质心差的上四分位数和下四分位数。每个统计箱的四分位数外都有一条垂直虚线, 虚线的范围是1.5倍的四分位数间距, 超过1.5倍四分位数间距的覆盖率/质心差数值由离散的加号表示。从图 23可以看出:k-means覆盖率最低、质心差最大, 并且k-means统计箱的范围也最大;这说明k-means方法不经过学习, 在检测的准确率测量上起伏变化很大。“SVM+普通学习”模型以及“谱聚类+普通学习”模型结果会优于没有经过学习的k-means。其中, “谱聚类+离线增量学习”模型在所有方法中覆盖率最高、质心差最小, 故准确性最高。“谱聚类+在线增量学习”模型比“谱聚类+普通学习”模型, 因其统计箱更短, 能展现更好的鲁棒性。“SVM+离线/在线增量学习”比“SVM+普通学习”模型覆盖率更高、质心差更小并且箱型更短, 说明其准确性更好、鲁棒性更优。同时, 从上述统计箱图中可以看出, “谱聚类+离线增量学习”比“SVM+离线增量学习”准确性更好, 而“SVM+在线增量学习”比“谱聚类+在线增量学习”鲁棒性更优。这说明对于离线增量学习, 谱聚类模型更佳适用;而对于在线增量学习, SVM模型能获得更满意的结果。

图 3 覆盖率统计箱图结果
图 4 质心差统计箱图结果

表 1表 2分别描述了多重比较实验对于覆盖率和质心差2个定量标准的统计分析结果。在表中, 每一行分别代表了2种方法之间的定量比较结果, 用2种方式来表示。其一是单值估计, 用以描述方法1与方法2覆盖率或质心差的差异(采用方法1与方法2的直接相减), 其二是区间估计, 用以描述方法1与方法2计算覆盖率或质心差的差异具备95% 置信概率时估值的区间。对于覆盖率, 当计算结果为正值时, 表明方法1比方法2覆盖率高, 方法1的运动目标检测准确率就更优;对于质心差, 当计算结果为负值时, 表明方法1比方法2质心差小, 方法1的运动目标检测准确率更优。从表 1覆盖率对比实验结果可知, 单值估计和绝大多数区间估计的上下限均为正数, 这说明本文提出的新算法(即方法1)覆盖率更高。由表 2可知, 单值估计和所有区间估计的上下限计算结果均为负数, 这说明本文提出的新算法 (即方法1)质心差更小。以上分析结果从统计的角度定量说明了采用本文提出的新算法在运动目标检测运用中, 准确性和鲁棒性的突出效果。

表 1 覆盖率对比试验结果
方法1方法2单值估计区间估计
谱聚类+离线增量学习SVM+离线增量学习0.018 6[-0.001 2, 0.038 3]
谱聚类+离线增量学习SVM+在线增量学习0.032 0[0.012 2, 0.051 7]
谱聚类+离线增量学习SVM+普通学习0.106 4[0.086 7, 0.126 2]
谱聚类+离线增量学习k-means+无学习0.318 0[0.298 2, 0.337 7]
谱聚类+离线增量学习谱聚类+普通学习0.100 4[0.080 6, 0.120 1]
谱聚类+离线增量学习谱聚类+在线增量学习0.079 4[0.059 6, 0.099 1]
表 2 质心差对比试验结果
方法1方法2单值估计区间估计
谱聚类+离线增量学习SVM+离线增量学习-3.9026[-6.8898, -0.9155]
谱聚类+离线增量学习SVM+在线增量学习-5.5064[-8.0435, -2.0692]
谱聚类+离线增量学习SVM+普通学习-12.8192[-15.8063, -9.8320]
谱聚类+离线增量学习k-means+无学习-30.2417[-33.2289, -27.2546]
谱聚类+离线增量学习谱聚类+普通学习-22.3643[-25.3515, -19.3772]
谱聚类+离线增量学习谱聚类+在线增量学习-9.0417[-12.0288, -6.0545]
4 结论

在运动目标物体检测过程中, 出现各种复杂情况(包括:环境光照的突然变化、目标物体部分/完全遮挡、目标物体的刚性/非刚性形变等)是目前运动目标物体检测研究中极具挑战性的研究问题。本文提出了一种新颖的算法, 通过在相似度函数中引入空间信息度量和在相似度函数学习中引入增量学习思想, 实现了对空间和时间高相关性的考量。同时, 本算法也创新的将谱聚类技术运用在相似度函数学习中。统计分析表明, 新算法能有效提高运动目标检测准确率和鲁棒性。在今后的研究中, 本文的增量学习框架还将继续被研究和扩充。同时, 深度学习技术也将被运用在本文的后续相关研究中。

参考文献
[1] Yimaz A, Javed O, Shah M. Object Tracking:A Survey[J]. ACM Computing Surveys, 2006, 38(4): 1–45.
[2] Luo W, Xing J, Zhang X, Zhao X, Kim T. Multiple Object Tracking:A Liturature Review[EB/OL]. (2015-09-21)[2016-04-19]. http://arxiv.org/abs/1409.7618
[3] Xu C, Tao D, Xu C. Multiview Intact Space Learning[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2015, 37(12): 2531–2544. DOI:10.1109/TPAMI.2015.2417578
[4] Hong Z, Chen Z, Wang C, Mei X, Prokhorov D, Tao D. Multi-Store Tracker (MUSTer):A Cognitive Psychology Inspired Approach to Object localization[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2015:749-758
[5] Zhang P, Wang L, Huang W, Xie L, Chen G. Multiple Pedestrian Localization Based on Couple-States Markov Chain with Semantic Topic Learning for Video Surveillance[J]. Soft Computing, 2015, 19(1): 85–97. DOI:10.1007/s00500-014-1375-9
[6] Zhuo T, Zhang P, Zhang Y, Huang W, Sahli H. Object Localization Using Reformative Transductive Learning with Sample Variational Correspondence[C]//ACM International Conference on Multimedia, 2014:941-944
[7] Zhuo T, Zhang Y, Zhang P, Huang W, Sahli H. Non-Rigid Target Localization Based on Flow-Cut in Pair-Wise Frames with Online Hough Forests[C]//ACM International Conference on Multimedia, 2013:489-492
[8] Shi J, Malik J. Normalized Cuts and Image Segmentation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2000, 22: 888–905. DOI:10.1109/34.868688
[9] Ng A, Jordan M, Weiss Y. On Spectral Clustering:Analysis and Algorithm[C]//Advance in Neural Information Processing Systems, 2002:64-72
[10] 邓力, 俞栋, 谢磊. 深度学习:方法及应用[M]. 北京: 机械工业出版社, 2016: 32-64.
Deng Li, Yu Dong, Xie Lei. Deep Learning:Methods and Applications[M]. Beijing: China Machine Press, 2016: 32-64. (in Chinese)
A Novel Algorithm of Moving Object Detection via Spectral Clustering and Incremental Learning
Huang Wei1, Yang Wenji2, Zeng Jing1, Zeng Shuru3, Chen Guang4     
1. School of Information Engineering, Nanchang University, Nanchang 330031, China;
2. School of Software Engineering, Jiangxi Agriculture University, Nanchang 330045, China;
3. Huazhong Institute of Electro-Opticis, Wuhan 430223, China;
4. Xi'an Communication Institute, Xi'an 710072, China
Abstract: Moving object detection receives much research interest in contemporary computer vision studies. It is also widely acknowledged that many problems, including illumination changes, partial or full occlusions, rigid or non-rigid shape transformation, are still challenging and hinder the detection performance from being further improved. In this paper, a novel algorithm of moving object detection is introduced. The incremental learning technique is employed in this algorithm; whose main purpose is to incorporate high spatial correlation within individual frames as well as high temporary correlation between consecutive frames for automatic updating of the detection model. Also, the model learning is realized via spectral clustering. A databased composed of over 1000 video frames is utilized for experimental evaluation. A series of statistical analysis, including ANOVA and post-hoc multiple comparison tests, are implemented to evaluate the new algorithm and other compared methods. It turns out that the novel algorithm can outperform others in terms of detection accuracy and robustness from the statistical perspective.
Key words: algorithms     spectral clustering     incremental learning     moving targets     detection    
analysis of variance (ANOVA)     clustering     constrained optimization     pixels     support vector machines     target tracking    
西北工业大学主办。
0

文章信息

黄伟, 杨文姬, 曾璟, 曾舒如, 陈光
Huang Wei, Yang Wenji, Zeng Jing, Zeng Shuru, Chen Guang
基于谱聚类和增量学习的运动目标物体检测算法研究
A Novel Algorithm of Moving Object Detection via Spectral Clustering and Incremental Learning
西北工业大学学报, 2017, 35(1): 170-176.
Journal of Northwestern Polytechnical University, 2017, 35(1): 170-176.

文章历史

收稿日期: 2016-09-19

相关文章

工作空间