视频中目标快速检测算法

刘 松，王紫一文，魏 东，杨洪臣

（1. 四川警察学院,四川 泸州646000；2.深圳市公安局，广东 深圳 518000；3.中国刑事警察学院，沈阳 110035）

随着经济社会的发展及科学技术的进步，传统的侦查手段及模式逐渐被多警种合成作战的大侦查模式所取代。要实现多警种的有力配合、相互支撑，就需要利用好现有科技成果，并创造性地将这些科技成果移植应用到公安科技创新改革中来。以技术作为支撑和保障，才能更好地发挥不同侦查手段在合成作战中的作用，激发大侦查合成作战的真正威力。

作为合成作战中的关键一环，视频侦查在一定程度上直接关系到大侦查合成作战的效果。以人工观看分析监控视频为主的传统视频侦查方式完全不能适应大侦查合成作战模式下对视频侦查快速高效的要求，将现有技术成果加以创新改进，应用于公安工作中解决公安工作实际需求，这就是本算法探究的出发点和背景。

1 算法介绍

本算法主要通过固定摄像头下监控视频变化背景的自适应、视频中多目标定位及图像匹配等算法实现视频目标快速检测，帮助侦查人员快速高效地发现海量视频信息中与案件目标相关的信息。

2 背景提取算法

通过算法提取视频实时背景的目的在于提取视频运动目标。视频中运动目标提取算法主要包括光流法、相邻帧差法及背景差值法。其中光流法算法较为复杂，且硬件依赖性较高；相邻帧差法算法简单，实时性强，但是容易在运动目标提取中产生残影现象；背景差值法与光流法相比有算法更为简单、硬件依赖小、实时性较高的优点，较之相邻帧差法又不会产生残影现象，故在运动目标提取上采用了背景差值法。背景差值法实现的关键在于背景的提取。为适应固定监控设备不同环境下监控视频目标快速检测的要求，采用背景自适应算法实现背景提取。背景自适应算法大致可以分为两类：1）基于背景建模的背景自适应算法；2）基于像素灰度统计的背景自适应算法。

基于背景建模的背景自适应算法主要以高斯建模为主，可分为单高斯模型和混合高斯模型，其中单高斯模型较为简单，但是需要多次迭代才能实现对简单背景的刻画；而混合高斯模型利用多个不同参数高斯模型对背景加以刻画，具有算法复杂，运算量较大的特点。基于像素灰度统计的背景自适应算法是通过随机抽取一段时间内视频帧，并对不同像素位置灰度值变化进行统计，选取出现频次较高的灰度值作为该像素灰度。该方法算法简单实时性较强，故本研究在该类算法基础上加以改进实现不同环境下的视频背景自适应。

采用的基于灰度统计的背景自适应算法主要包括背景重构和背景自适应两个部分。背景重构是在t0时刻随机选择视频中n帧图像，并将像素点(x,y)每ξ灰度分为一类进行背景重构，有：

其中，f0i (x, y)为t0时刻i帧图像在(x,y)处的灰度值，grayi( x, y)为t0时刻i帧图像在(x,y)处经过灰度分类后的灰度值。(经试验确定ξ=25时重构效果较为理想)。灰度分类后将n帧(x,y)像素的灰度值保存在数组GRAY中，有：

然后将数组GRAY中出现频次最高的灰度级grayi( x, y)定义为(x,y)处的灰度值。对较短且背景变化小的视频，做到背景重构就已经足够了，但针对背景变化复杂的视频，提取视频背景就需要实现视频背景自适应，用到的方法可以参看笔者相关文章[1]，在此不再赘述。

3 多目标定位算法

多目标定位算法实现主要分为图像优化处理及多目标定位两个步骤。算法流程图如图1所示。

多目标定位算法具体实现步骤如下：步骤1：图像优化处理

多目标定位算法[2]是在背景自适应算法取得较好视频的背景bg(x,y)的基础上，运用背景差值法得到每帧视频frame(x,y)差分图像diff(x,y)，有：

图1 多目标定位流程图Fig.1 Flow chart for multi-target location

再对差分图像diff(x,y)设定阈值threshold进行二值化处理得到binary(x,y)，有：

步骤2：多目标定位

二值化处理后运用形态学处理优化二值图像binary(x,y)得到rows*cols数组mat(x,y)。再用matlab边缘查找算法bwtraceboundary对mat(x,y)进行遍历得到边缘像素(x,y)集合T，有：

根据边缘像素索引T刻画的目标边缘查找当前目标的最小外接矩阵，有：

其中[x1 y1 x2 y2]刻画了当前目标的最小外接矩阵。根据[x1 y1 x2 y2]定义rows*cols的矩阵m，有：

如式（7），将矩阵m与mat进行与运算后，消除mat中已被检测目标区域，重复步骤2进行目标定位，直到遍历结束。

4 图像匹配算法

视频中运动目标主要通过目标的纹理和颜色特征进行匹配。朱英丽等[4]提出利用运动目标颜色布局和边缘直方图等特征进行匹配实现视频中目标的检索。颜色布局能很好表现视觉信号的颜色空间分布。通过将RGB图像映射到YCrCb空间并将图像分割为64块，并计算每一块中像素在（Y,Cr,Cb）三颜色分量的均值，作为该块的颜色。再进一步对64块均值颜色进行DCT变换，选取DCT变换后三组颜色的低频分量作为图像的颜色布局描述子。边缘直方图是一种对图像边缘像素梯度方向进行统计而得到的描述图像边缘空间分布的直方图。边缘直方图能较好反映图像的纹理信息，可以用于图像间的匹配。

本研究将图像划分为16个不重叠的矩形区域。对各个区域中0°、45°、90°、135°及无方向信息五类边缘信息进行统计，得出各区域边缘直方图。通过将颜色布局和边缘直方图等图像特征作为图像匹配的描述子，利用欧式距离进行图像匹配，能够实现视频中运动目标的检索，且结果较为准确。感知哈希匹配算法在图像匹配中运用广泛，效果显著，常运用在图片搜索应用中。感知哈希算法可以分为感知哈希均值算法和pHash算法。这两种哈希算法的实现原理都是通过对图片进行处理，去除图片高频细节信息，通过低频轮廓信息生成图片hash值，通过图片间hash值汉明距离来刻画图片相似程度。感知哈希均值算法实现主要包括三步：

步骤1：尺度归一化

将待对比的两幅图片都归一化为8×8大小的图片，既方便了不同大小图片的比对又去除了图像高频信息。

步骤2：图像二值化

通过计算8×8图片image(x,y) 64位像素均值并以之为二值化阈值对图片进行二值化处理得到二值化图像binary(x,y)，有：

步骤3：计算图片hash值和图片间汉明距离

将步骤2得到的64位二值信息组合在一起就构成了图片的hash值；通过计算两张图片hash值不同位个数得到两张8×8图片的汉明距离，一般汉明距离小于5可以断定两张图片高度相似，而汉明距离大于10可以断定两张图片完全不同。两张图片的二值化图像如果分别用binary1(x,y)和binary2(x,y)来表示，两张图片的汉明距离hammin_distance可用公式(9)加以计算：

可以看到哈希均值算法是十分简单的，所以其运算速度非常快，同时图片匹配也比较准确，不失为一种十分有效且好用的图像匹配算法。当然哈希均值算法也存在一些问题，其在图片匹配上比较死板、僵硬。比如在对图像进行伽马校正后，图片的均值发生改变就会使图片hash信息发生较大变化，导致匹配时汉明距离变大，使相似图片不能被匹配，发生漏检现象。故有了基于DCT处理的pHash算法，pHash算法较哈希均值算法更为健壮，匹配结果更为精准，能在一定程度上消除图片微弱变化的影响。在图片变化幅度小于25%时pHash算法效果显著。pHash算法是在哈希均值算法步骤1之前先将图片缩小为32×32大小并进行DCT处理，选取DCT变换后左上角8×8区域低频信息作为处理对象，之后运用哈希均值算法步骤2、步骤3对DCT得到的图像低频信息进行处理。

5 算法实现及性能分析

5.1 算法实现

通过背景自适应算法实时提取视频背景，通过多目标定位算法锁定背景差值法二值化后提取的运动目标位置，最后通过图像匹配算法实现待检测目标和视频中运动目标比对[3]，最终实现基于背景自适应的视频多目标快速检测。算法具体流程图见图2：

在图像匹配模块，分别对1.3节介绍的各类匹配算法加以实现，并对各个算法性能做了简要分析。

5.2 算法性能比较及分析

图2 算法流程图Fig.2 Flow chart for veri fi cation of algorithm performance

性能测试实验是在一台配置2.3GHz i5处理器，4G内存并装载window7 64位系统和matlab2015a+软件的笔记本电脑上分别利用不同算法对时长为15 min 3s的视频中三个不同目标进行检索，最终得到反映不同算法在匹配精度及运行效率上的实验数据。

实验一 基于颜色布局和边缘直方图描述子匹配算法的目标检索实验（结果见表1）。实验表明基于颜色布局和边缘直方图描述子特征匹配实现的目标检索算法能够匹配并命中检索目标，但该类匹配算法因为匹配过程中对图像的多色彩通道进行了复杂的运算，导致其检索时间都超过了1200 s，效率欠佳；同时，该类匹配算法的匹配精准度（命中/匹配）在各检测目标的检测测试上也不是十分理想。

实验二 基于哈希均值和增强哈希算法的目标检索实验。从表2可以看出在实验中，哈希均值算法的命中、匹配及运行时间都较增强哈希算法好。但是在匹配精准度（命中/匹配）上哈希均值算法不如增强哈希算法。总体来说两类哈希算法在图像匹配上性能差距不大。

表1 实验一性能测试分析表Table 1 Result of experiment 1 by performing one algorithm

表 2 实验二性能测试分析表Table 2 Result of experiment 2 by performing a/pHash

实验三 对比表1和表2中的参数，不难发现利用哈希算法进行图像匹配时，无论在执行效率还是匹配效果上都较基于颜色布局和边缘直方图描述子实现的匹配算法有较大优势。但哈希算法在图像匹配精准度（命中/匹配）上依然有提升的空间。考虑到基于颜色布局和边缘直方图描述子的匹配算法在匹配中利用到了图像更多的色彩信息，如果在哈希算法初步判定图像相似后，再利用基于颜色布局和边缘直方图描述子的匹配算法进一步对匹配目标进行相似度度量，可能会提升算法的图像匹配精准度（命中/匹配）。为验证这一点，进行了实验三，结合颜色布局、边缘直方图描述子的哈希匹配算法目标检索实验，匹配算法的流程图见图3，结果见表3。

图3 实验三匹配算法流程图Fig.3 Flow chart of experiment 3 from new matching algorithm

表3 实验三性能测试分析表Table 3 Result of experiment 3 from new matching algorithm

可以看到表3中对不同目标匹配耗时均在200 s左右，匹配效率较高，较哈希匹配算法无较大劣势；但改进后的算法对不同匹配目标匹配精准度（命中/匹配）均提升到了100%，较传统的图像匹配算法有了较大的提升。

6 总结

通过对视频中多目标快速检测算法探究，本文发现将哈希图像匹配算法和基于颜色布局、边缘直方图描述子的匹配算法相结合后用于视频中目标检测，无论在运行效率还是在检测精准度上都有较好的效果，较传统的图像匹配算法有了较大的性能提升。