实时运动对象分割和检索算法

—226—实时运动对象分割和检索算法肖广1，石旭利2（1.华东师范大学计算机科学与技术系，上海200062；2.新型显示和应用系统教育部重点实验室，上海200072）摘要：提出一套实时视频对象分割检索算法，用运动矢量信息标注运动区域，利用背景检测算法检测对象区域。将检测出的对象区域和运动区域进行并操作运算，得到单帧图像的分割。利用改进的Hausdorff距离跟踪算法进行匹配跟踪和检索。实验表明了该算法的有效性。关键词：实时对象分割；检索算法；Hausdorff距离Real-timeMovingObjectSegmentationandRetrievalAlgorithmXIAOGuang1,SHIXu-li2(1.DepartmentofComputerScience&Technology,EastChinaNormalUniversity,Shanghai200062;2.KeyLaboratoryofAdvancedDisplaysandSystemApplication,MinistryofEducation,Shanghai200072)【Abstract】Thispaperproposesareal-timevideoobjectsegmentationandretrievalalgorithm.Thealgorithmmarksthemovingareas,andextractstheobjectinformationbyusingthebackgrounddetectionalgorithm.Apixelinobjectareasandmovingareasissettomovingobjectareasinaframe.MovingobjectistrackedandindexedbyusingHausdorffdistance.Thealgorithmiseffectiveandreal-time.【Keywords】real-timeobjectsegmentation;retrievalalgorithm;Hausdorffdistance计算机工程ComputerEngineering第34卷第7期Vol.34No.72008年4月April2008·人工智能及识别技术·文章编号：1000—3428(2008)07—0226—03文献标识码：A中图分类号：TP18在监控系统中，海量数据的检索需要进行对象分割，基于分割时所采用的信息将其分为：3-D分割，仅基于运动信息的分割，时空分割和联合运动估计和分割。许多学者仅基于运动信息进行场景分割[1-5]。3-D分割方法把视频序列看成是三维信号。通过增加第三维时间轴扩展经典的2-D分割方法。Hinds和Pappas把二维自适应算法扩展到视频序列的分割算法中。在这些算法中经典的方法是使用估计的稠密运动场进行分割[3-5]。分割算法虽然非常多，但在实践中，尚需完善该算法和其他较为复杂的算法，这就对硬件设施提出了更高的要求，而有些算法缺乏鲁棒性，只能对测试序列进行验证，没有考虑现实世界中真正的监控场景和光照变化等场景中的存在因素。本文提出一套完整的视频对象分割检索算法，主要从快速算法的角度进行阐述，并针对现实监控场景中拍摄的视频序列进行对象的提取和检索。1视频解析本算法编写了一个视频流的解码播放软件。压缩域内运动检测的模块是内嵌在视频流的解码中，从中截取到的宏块运动矢量作为以后分割的输入信息，快速处理后这些数据仍留给后续的解码步骤：(1)按层次复解控制信息，视频位流在输入缓冲区中聚集起来，当达到一定的充满度之后，解码器开始启动。解码器按照视频序列、图像组、图像、片、宏块、块的层次，自顶向下依次解码，每一层都有相应的开始标记和控制信息。解码器寻找到第一个序列头的开始标记sequence_header_code，紧跟其后的比特位是图像的宽度(12bit)、高度(12bit)、高宽之比(4bit)、帧率(4bit)、图像传输比特率(18bit)、解码缓冲区的大小(10bit)等初始化信息，它们都有规定的比特位数和语法说明，如此向下复解到块层。可变长度字解码VLD对宏块寻址、宏块类型、宏块图案、宏块运动矢量、块DCT系数等进行统计，制定了相应的可变长编码统计表，编、解码双方都有这些统计表。当一串二进制比特流接收到时，预先并不知道其可以分割为几部分，每部分有多少比特位。在表项比较少的情况下，用遍历方法查阅相关统计表可较快地解码，但是有些统计表表项较多，例如块DCT系数可变长编码统计表有几百项。(2)Z型定位和反量化，这一步是在块层次上执行。将顺序接收的量化DCT系数按“Z”型次序放入到每个块中，同时乘以量化尺度，完成反量化。在同一帧图像中，量化尺度也并非不变。(3)进行逆离散余弦变换IDCT，在块层上实现频域到空间域的变换。逆离散余弦变换(InverseDiscreteCosineTransformation,IDCT)的计算量大，是解码中最耗费处理时间的环节。(4)运动缓存和补偿，运动补偿是运动估计的逆过程，本算法仅利用I帧和P帧进行视频对象分割和检索，所以，上述各部分算法进行了跳过B帧的运算。首先开辟两个存储区，分别保留已解码的过去或将来的I、P图像作为参考，然后以宏块运动矢量找到参考图像中的预测宏块值，并加上可能存在的匹配误差，恢复当前宏块初始值。并且在这一步将解码的宏块运动矢量进行缓存作为分割之用。当所有的信息都获得以后，开始对所解码出来的视频序列进行运动对象分割和检索。2视频运动对象分割算法2.1背景恢复在进行对象检测的时候，对视频序列预处理，即进行背景恢复，背景恢复算法首先保证相邻两帧可能是运动的对象作者简介：肖广(1969－)，男，博士研究生，主研方向：视频分析传输，计算机网络技术；石旭利，副教授、博士收稿日期：2007-10-22E-mail：[e-mail]—227—尽可能被滤除，得到静止不变的部分，并将可靠的静止部分拷贝到背景缓存中去。具体算法如下：将解码输出的YUV序列进行处理，转换成RGB序列，对于相邻的两帧分别求R,G,B的帧差，并利用自适应门限进行二值化，值为“1”的说明该像素点发生了变化，值为“0”的点表明没有发生变化。无变化的像素帧差满足正态分布：)|(0HFDp=12σπexp)2(22σFD−(1)其中，FD是帧差；2σ为帧差的方差；H0表示当前像素没有运动的假设情况。二值化门限由下式确定：)||(|0HTHFDpa=(2)其中，a是显著性水平；TH是二值化门限。由于采用R,G,B空间进行背景检测，如果像素的灰度和色度任何分量发生变化，则该像素被认为是运动像素，这种检测算法的优点是最大限度地去处运动像素而保留静止的背静像素。在3个帧差分量中，如果一个帧差的分量取值为“1”，则认为对应的该点像素发生了变化。利用上述算法计算出静止与运动点之后，对每一点像素进行连续不变帧数计数，如果计数超过一定的值，则认为该点为背景帧，并用连续不变的所有帧中的像素值的平均值作为背景帧。得到背景帧之后，用解码出来的每一帧与背景帧相减得到一个运动对象区域，该区域作为后继算法的输入。2.2运动区域连通一般地，刚体目标在空间位置上是聚集在一起的。因此在得到I帧、P帧的MV后，把其中连通的宏块都归并为一个区域。下面是进行运动区域连通的C程序：其中mvx,mvy,bx,by分别为所要判断宏块的运动矢量和坐标。对宏块做标记再合并。以自上至下、从左到右的顺序扫描宏块，对任一一个判断为异背景的宏块A，其上侧和左侧宏块是已经扫描标记过的宏块，对A加标记的方法将由左侧宏块和上侧宏块确定，分为3种情况：(1)两个相邻宏块皆属于背景，当前宏块A加新标记；(2)两个宏块仅有一个标记过的异背景宏块，A与其同标记；(3)两个宏块皆为标记好的异背景宏块，A与左侧宏块同标记。如图1所示，第1幅图“A”表示异背景宏块，“0”表示背景宏块。在第1遍扫描完后，所有的“A”宏块都加上了数字标记，第2幅图有5个标记。由于一个物体可能有多个标记，因此进行了第2遍扫描，将连通的标记区域合并。第3幅图只存在3个独立的区域了。通过区域的合并，可以屏蔽离散的干扰噪声，即删去那些宏块数目少、孤立的区域。上述算法是基于宏块的运算，为了细化结果，可以在实际的系统中的算法是基于4×4子块的。接着进行运动和非背景块的区域连通算法，即将检测出来的背景和每一帧进行像减，按照阈值确定前景区域后，用这些前景块对上述运动连通区域进行修正，得到运动对象区域。由于噪声的影响和算法本身是基于4×4块的（为了加快计算速度），上述算法在运动对象的边界区域不能很好地精确到像素点的分割，但对于进一步的对象检索，提供了一个准确的运动对象的矩形框，仅对矩形框中的图象进行边缘提取，所用的算法是CANNY边缘提取算法，提取出来的对象边缘作为下一步对象跟踪和对象检索的输入。图1运动区域连通3基于模板的对象匹配和跟踪算法Hausdorff距离是描述两组点集之间相似程度的一种度量，是集合与集合之间距离的一种定义形式。在图像的匹配跟踪应用中，它用于度量模板中的每一点到图像中的每一点的相似性程度，因此，它可以用于度量模板与图像的相似性。它不仅适用于平移情况的运动目标跟踪，而且在目标复杂运动时也能够取得较好的跟踪效果。匹配算法分为前向和后向匹配两部分。多分辨率分析是一种由“粗”到“精”(Coarse-to-fine)的方法，它的基本思想是：先在较低分辨率图像中执行某种操作，称为“粗”阶段；然后将粗阶段的执行结果作为初始条件，到较高分辨率的图像中执行与粗阶段近乎同样的操作，称为“精”阶段。“粗”阶段的执行结果不够准确，但在该分辨率的意义上接近真实结果，经过“精”阶段的进一步加工，最后得到精确的结果。本文提出一种多分辨率分析后向匹配的改进算法。后向匹配的一般流程如下：根据前向匹配的结果点集中的每个点，扫描以此点坐标作为基准坐标时模板覆盖范围内的所有点，如果被覆盖图像范围内存在特征点，则保存此点在模板距离变换图像中的值到一个数组。最后将此数组中所有点进行排序，取出第K个点，如果小于阈值则保存此基准点及其Haudorff后向匹配值。文献[6]在扫描模板覆盖范围内的特征点时的做法是逐点扫描被模板覆盖范围内的所有点，找出其中的图像的特征点。这种做法对于模板较大时，相应的无效扫描可能就比较多，扫描的效率也就比较低了。从这一点出发，作者就尝试使用一种扫描图像特征点集的方法来代替逐点扫描模板的方法进行后向匹配。现在用边缘图像的特征点来映射成边缘图像距离变换图像中的零点，先对特征点的坐标进行坐标变换(因为距离变换图像是扩展过的)，然后根据新的坐标进行扫描。因为是前项匹配结果是按Y坐标排序的，而特征点本来就是按Y坐标排序的，也就是说只要当前特征点经过坐标变换后大于可能扫描的最大Y坐标，就可以停止继续扫描，认为不可能在扫描范围内存在更多的特征点。如果特征点纵坐标未超过最大Y坐标，但整个特征点坐标不在扫描范围内，则跳过此点转到一下个特征点进行扫描。直到找到扫描范围内的特征点，才记下它的在模板中的距离变换值。为了真正地提高后向遍历的速度，有必要设置每次扫描的起始特征点序号(startNum)避免每次扫描从第一个特征点…0000AAA00AA00AA……00AAA0AAAA0000A...…AA00AAA0AAAAAA0………000011100220033...…004440111100003……550044401111110……000011100110033……001110111100003……550011101111110…—228—开始，所以，设置了3个值来确定startNum的值，currentY是当前扫描的Y坐标，currentS是当前Y坐标这行第一个特征点的序号，isFirst是判断是否是第1个扫描范围内的特征点，在找到第1个扫描范围内的特征点前，每当Y坐标改变时更新currentY和currentS。当找到第1个特征点后，记录下当前的curren