基于团块模型的行人阴影抑制算法*

2014-09-13金圣韬孟朝晖

计算机工程与科学 2014年11期

关键词：团块直方图阴影

金圣韬，孟朝晖，刘伟

(1.河海大学计算机与信息学院，江苏南京 211100;2.63780部队，海南三亚 572000)

基于团块模型的行人阴影抑制算法*

金圣韬1，孟朝晖1，刘伟2

(1.河海大学计算机与信息学院，江苏南京 211100;2.63780部队，海南三亚 572000)

为有效解决行人阴影对行人跟踪产生的影响，提出一种基于团块模型的阴影抑制算法。该算法利用团块结构作为行人模型，通过计算团块的矩特征和团块垂直直方图，借助几何的方法获得疑似阴影区域。然后，将该疑似阴影区域的灰度、方向、中心位置作为参数对整个前景区域进行阴影建模，使得阴影区域更精确。最后，从行人模型中剔除阴影团块达到阴影抑制的效果。经过视频序列测试，本文算法对不同运动方向、不同数量的行人均有良好的阴影抑制效果，表明了该设计方案的有效性和准确性。

阴影抑制；团块直方图；阴影建模；行人跟踪

1 引言

视频监控技术就是为了防止安保人员的误判、利用自动分析技术进行视频监控的技术[1]。目前的研究方法都是假设视频序列中不存在阴影，而在光线充足的场景，移动的阴影将被错误地划分为前景对象。这将导致目标位置估计、目标行为分析和目标识别的错误。

目前，运动阴影检测与抑制的方法大致分为如下三类：基于颜色模型的方法，选择一个合适的颜色空间，利用阴影像素值在颜色空间中的色彩特性进行阴影抑制，比如HSV空间[2]、色彩特征不变量空间[3]和归一化RGB空间[4]，但这些方法易受噪声影响并且对光强变化敏感；基于物理模型的方法，通过物理的方法建模或学习阴影像素的特定外观特征，比如双光源双色反射模型BIDR(Bi-Illmuinant Dichromatic Reflection)[5]，但它无法处理目标色调与背景相同的情况；基于纹理模型的方法，通过阴影光谱特征获得候选区域，再根据这些区域纹理的相关性来区分前景和阴影，比如归一化互相关[6]、Gabor滤波[7]、正交变换[8]等，由于要对一个像素的多个邻域进行计算，故运算量较大、实时性差。

针对上述算法的不足，本文提出一种基于团块模型的行人阴影抑制方法。首先构建行人团块模型，再通过计算团块的矩特征和团块垂直直方图，借助几何的方法获得疑似阴影区域。然后，将该疑似阴影区域的灰度、方向、中心位置作为参数对整个行人和阴影进行阴影建模，使得阴影区域更精确，对不同朝向、不同数量行人的阴影具有较好的抑制效果。此外，由于本文算法简单，时间复杂度较小，视频处理速度约为7.5帧/s。

2 算法流程

团块[9]是指像素在空间上连通并且具有相似图像特征(如颜色、纹理等)的区域。基于团块模型的阴影抑制算法流程如图1所示。考虑到树叶晃动等因素，采用混合高斯动态背景建模技术[10]将行人的运动前景提取出来。利用团块建模算法对前景进行建模，使每个行人都由相应团块结构表示。对于行人的阴影抑制过程采用由粗到细的步骤，首先采用团块直方图投影获取行人与阴影的分割点，然后利用几何矩估计阴影区域的朝向，这样行人和阴影区域就可以通过一条有向直线被粗略地区分开。在细化阶段，阴影边界可以通过阴影建模算法得到进一步处理。最后，标注阴影区域并在行人团块模型中剔除阴影团块。

Figure 1 Flow chart for pedestrian shadow elimination based on blob model图1 基于团块模型的行人阴影抑制算法流程图

2.1 行人团块建模算法

行人团块建模算法分为团块提取和团块合并两个阶段。对每一帧新图像，将其分割为较小的团块并计算每个团块内的像素颜色均值；再将颜色上相近且空间上相邻的团块合并构成较大团块，表征全场景的颜色分布；然后利用混合高斯背景建模算法提取的前景模板标记运动的团块；最后以每个运动团块的形心为结点，利用模糊聚类算法再次合并团块构建行人团块模型。

本文以四叉树分割算法作为团块提取算法，按照自下向上的生长方式，通过多次将局部相邻且特征相似的团块向上逐步聚合的方式来提取团块。团块的数据结构中包括：团块矩形坐标、背景标记、阴影标记、中心团块标记、团块编号、团块重心坐标、团块颜色均值等属性。

算法步骤如下：

步骤1将图像分割为由N×N个小区域aij(N的取值由目标的尺寸决定)构成的区域矩阵AN×N，并初始化Blob结构数组B。

(1)

步骤3若dij小于阈值d0，则将这两个团块合并，修改Blob结构的中心团块标记lab，使之统一为aij的团块编号。

步骤4重复步骤3，直到结构数组B遍历完毕。这样就完成了四叉树一次由下向上的聚合过程。

步骤6返回步骤5，如此重复，直到得到一个稳定的分割结果。

这样就完成了对一帧图像颜色在空间位置上的聚类。如图2a为对第75帧视频图像进行三次聚合后的结果，图中每个方格表示一个团块区域，颜色场景复杂的部分(如人物、树木)方格分布较小较密，而颜色场景简单的部分(如天空、地面)方格分布较为稀疏，尺寸也大些。

Figure 2 Blob extraction result, and predestrain model based on blob图2 团块提取和行人团块模型效果图

经过团块提取后，为了获得运动前景以构建行人团块模型，还需进行背景建模。由于视频图像中的每个像素点，其值在序列图像中的变化可以看作是一个不断产生像素值的随机过程。因此，对于每帧新进入的像素值，可以选择混合高斯背景建模判断该像素属于运动前景还是背景，由此得到前景模板M。我们利用M标记相应团块区域，这样就能有效剔除背景团块。

(2)

其中,Ik(x,y)是第k帧图像，Bk(x,y)是第k帧的背景模板，Td是阈值。

由于同一目标的不同团块在空间上具有高度相关性，为了利用邻域信息，本文定义空间函数如下：

(3)

其中，(Δx,Δy)为团块i的重心和聚类中心j坐标之差。我们利用hij来衡量团块i属于第j个聚类的可能性大小。下面给出隶属度函数uij及聚类中心vi的迭代计算公式：

(4)

(5)

其中，zj为团块j的特征向量。α为模糊因子，控制着模糊聚类间的分享程度。公式(5)中uij作为权值，表明各样本成为聚类中心的可能性。

团块合并算法步骤如下：

(1)设n为一帧图像中所有参与聚类的团块数目，给定聚类类别数q(2≤q≤n)，参数α，迭代停止阈值ε。

(2)给出初始聚类中心集合V(0)，设置迭代计数器f=0。

(6)

(7)

(5)更新迭代计数器，重复(3)、(4)，直到距离范数‖V(f+1)-V(f)‖<ε或计数器值f达到一定次数;

(6)去模糊化。本文合并算法的最终目的是为了将空间相邻的团块合并，标记为同一团块类别。我们采用最大隶属值法去模糊化。用Lj表示第j个样本点所属类别，则有：Lj=argt{max(uij)}。

我们将面积较大且相互距离较远团块的形心作为初始聚类中心赋给V(0)，并把这种团块数量作为聚类类别数量。迭代停止阈值ε影响了聚类的精度和速度，此处取0.4。模糊因子α与样本数量有关，通常大于n/(n-2)，本文取1.65。

如图2b所示，可以明显发现阴影也被错误划分为行人团块模型的一部分，为了获得稳定的跟踪效果，必须将阴影去除。

2.2 疑似阴影检测

经过行人团块建模后，图2b中行人与阴影的夹角可以通过矩特征计算得到。给定一维的行人模型团块数组R，其中心矩定义如下：

(8)

(9)

其中，(x,y)是团块R[i]的几何中心，n是数组R的长度。如图3a所示，点PG为团块数组R的重心，夹角θR是我们要求的夹角。如图3b所示，假设将行人和阴影构成的整体区域看作一个椭圆，那么现在的问题就是在已知椭圆中心坐标PG和椭圆内所有点的坐标(即各个团块中心坐标)的情况下，求夹角θR，可以通过下式求得：

(10)

式(10)就是求使椭圆内所有点到椭圆短轴投影距离的平方之和最小的那个夹角，即椭圆主轴与x轴的倾斜角。

Figure 3 Pedestrian blob model and pedestrian shadow ellips图3 行人团块模型与阴影椭圆

对式(10)求导，并令：

(11)

得：

(12)

根据式(12)，当利用中心矩计算行人和阴影的方向后，为了获得阴影分割线，我们还需要计算人和阴影的分割点PR。

点PR可以通过计算团块垂直直方图相邻两列差值，取差值最大列所对应的横坐标获得。团块垂直直方图，如图4所示，可以通过遍历数组R自下向上沿着水平方向统计垂直方向团块的数量获得。设HR(x)为团块垂直直方图R的第x列分量，由此，我们定义团块差分直方图dHR(x)如下：

(13)

这样，点PR的横坐标x可以通过式(14)获得：

(14)

其中，XRbottom是团块差分直方图的横坐标取值范围，即整个前景区域R的宽度，当xR有多个取值时，保留距离团块直方图波峰最近的点。

Figure 4 The 75th vertical histogram of pedestrian blob图4 第75帧行人团块垂直直方图

PR的纵坐标y可以通过团块垂直直方图中对应的PR横坐标得到。

(15)

其中，CR(x)表示团块数组R的中心坐标集合。这样我们就有一条有向直线将行人与阴影粗略地分割成两部分R1和R2，直线方程如下：

(16)

由于阴影部分像素的亮度更暗并且颜色变化更小，因此阴影区域R2可以根据这个特性很容易地选择。

整个疑似阴影检测算法流程如下：

(1)根据前景团块数组R计算团块垂直直方图HR(x)和夹角θR；

(2)根据团块垂直直方图HR(x)计算团块差分直方图dHR(x)；

(3)利用公式(14)，计算PR点的横坐标；

(4)扫描团块数组R，获得中心坐标集合CR(x)；

(5)利用公式(15)，通过PR的横坐标和CR(x)，计算得yR，这样就获得了PR点；

(6)根据公式(16)，利用夹角θR和PR获得分割线，计算分割后两部分颜色均值和方差，选择均值和方差较小的区域作为疑似阴影区域R2。

2.3 阴影建模

当疑似阴影区域R2确定后，我们将构建一个合适的阴影模型使阴影区域得到进一步细化。本文将从灰度、距离、方向三个角度展开分析。

当背景像素被阴影覆盖时，该像素的亮度会变暗，饱和度通常会变小，而色度不会有较大变化。因此，最直接的方式就是考虑用像素的灰度去建立模型，公式如下：

(17)

其中，μR是疑似阴影区域R2的灰度均值，Th是阈值，Ik(x,y)为前景区域像素点(x,y)处的灰度值。这里，仅考虑灰度的缺点是当某些距离疑似阴影区域较远且灰度值接近μR的区域会被错误划分为阴影区域。

由于行人的阴影都是从脚部往外延伸且阴影的长度总是有限的，因此我们借助疑似阴影区域分割点PR来测量阴影的长度，并把一定长度范围内的像素点都认为是阴影，公式如下：

(18)

其中，(xR,yR)为PR点坐标，(x,y)为前景区域像素点坐标，Td为阈值，取行人身长的0.8倍。虽然现在考虑了距离和灰度，但不同光源会导致行人的阴影具有不同的朝向，因此为了更细致的阴影区域，必须在测算距离时考查疑似阴影方向θR。为此，本文按照式(19)将原始坐标映射到椭圆坐标：

(19)

为了提高模型的精确性和弹性，针对三种判断依据，本文采用动态加权的方式融合各种因素。阴影模型表达式如下：

(20)

其中，α是权重更新速率，此处取0.1，w1是阴影灰度值权重，w2是阴影长度权重。权值会根据各个因素的符合程度自动调整。

2.4 阴影抑制

我们利用公式(20)对当前帧的前景区域的每个像素点进行建模，如果d(x,y)小于阈值Ts，那么这个像素点会被划分为阴影像素。这里Ts取疑似阴影区域R2内所有像素点d值的均值。

(21)

整个阴影抑制算法流程如下：

(1)构建行人团块模型，使每个行人都有相应团块表示：

①获取当前帧，利用团块提取算法，对图像颜色进行聚类;

②利用混合高斯背景建模的前景模板，标记运动团块;

③利用模糊聚类算法合并团块，获得最终行人团块模型。

(2)对于每个行人团块模型，分别利用疑似阴影检测算法将行人与其阴影粗略地分割开：

①计算团块中心矩，利用公式(12)计算阴影方向;

②计算团块垂直直方图，利用公式(14)和公式(15)计算行人与阴影分割点;

③根据阴影性质，选择相应疑似阴影区域R2。

(3)阴影建模，利用公式(20)对行人和阴影进行建模，若d(x,y)

(4)更新混合高斯背景模型，返回(1)，直到视频结束。

3 实验结果与分析

本文针对校园场景进行多组实验。实验程序在Visual Studio 2008环境下编写，计算机CPU采用Intel Core i3 3.07 GHz，视频序列图像大小为480*856。

为了评估本文方法的表现，定义精准率和虚警率作为评价指标。精准率是程序正确检测出的阴影像素数量与实际存在的阴影像素数量之比。虚警率是被错误划分为阴影像素的数量与程序检测的所有阴影像素数量之比。

其中，由于每个团块所包含像素点相同，可以通过人工统计团块数量来代替统计像素数量。图5显示第73帧阴影抑制的效果图，行人阴影处在人的正下方。

图6给出了不同朝向和不同数量行人的阴影抑制效果图,并与基于色彩特征不变量的阴影抑制

Figure 5 Effect diagram of pedestrian blob model after shadow elimination in the 73rd frame图5 第73帧阴影抑制效果图

做了对比。图6a和图6b阴影在行人前方，图6c和图6d阴影在其后方。图6g和图6h为多行人阴影标记效果。图6i和图6j为基于色彩特征不变量的阴影抑制。

图6a和图6d为去除阴影后的行人团块模型；图6b和图6e为行人阴影标记;图6c和图6f为团块垂直直方图；图6g和图6h为多人阴影标记效果图；图6i为基于色彩特征不变量的阴影抑制；图6j为对图6i去噪滤波的效果。

表1给出了四段视频中，两种算法性能的评估结果。

Table 1 Accurate rate and false alarm rate表1 精准率和虚警率 %

Figure 6 Effect diagrams of shadow elimination for pedestrians of different numbers facing different directions图6 不同朝向和不同数量行人的阴影抑制效果图

根据实验效果和数据表明，本文所提的方法对不同朝向、不同数量的阴影具有理想的分割和抑制效果，并且本文算法比基于色彩特征不变量的阴影抑制效果更明显。

4 结束语

本文提出了一种有效的从动态场景中去除阴影的方法。我们按照由粗到细的步骤，首先使用行人团块建模算法获得行人模型；然后利用疑似阴影检测算法计算得到一条有向直线将行人和阴影大致分割，获得疑似阴影区域；最后在细化阶段，对前景区域进行阴影建模使阴影区域更为准确。经过实验对比分析，本文算法能有效抑制阴影对行人目标检测的影响，并具有较强的实时性。

[1] Cristani M,Delbue A. Human behavior analysis in video surveillance:A social signal processing perspective[J].Neurocomputing,2013(100):86-97.

[2] Yoneyama A, Yeh C H, Kuo C. Movingcast shadow elimination for robust vehicle extraction based on 2D joint vehicle/shadow models[C]∥Proc of IEEE Conference on Advanced Video and Signal Based Surveillance,2003:229-236.

[3] Salvador E, Cavallaro A, Ebrahimi T. Cast shadow segmentation using invariant color features[J]. Computer Vision and Image Understanding,2004,95(2):238-259.

[4] Salvador E, Cavallaro A, Ebrahimi T. Shadow-aware object-based video processing[J]. IEEE Proceedings on Vision, Image and Signal Processing,2005,152(4):398-406.

[5] Huang Jia-bin, Chen Chu-song. Moving cast shadow detection using physics-based features[C]∥Proc of IEEE Conference on Computer Vision and Pattern Recognition,2009:2310-2317.

[6] Hampapur A. Robust and efficient foreground analysis for real-time video surveillance[C]∥Proc of IEEE Conference on Computer Vision and Pattern Recognition,2005:1182-1187.

[7] Leone A,Distante D.Shadow detection for moving objects based on texture analysis [J]. Pattern Recognition,2007,40(4):1222-1233.

[8] Zhang Wei, Fang Xiang-zhong, Xu Yi. Detection of moving cast shadows using image orthogonal transform[C]∥Proc of

International Conference on Pattern Recognition, 2006:626-629.

[9] Wang Shu-peng, Ji Hong-bing. Appearance model based on blobs for object tracking [J]. Journal of Xidian University,2008,35(5):799-804.(in Chinese)

[10] Shan Yong, Wang Run-sheng, Yang Fan. An algorithm of motion detection based on multi-feature background model[J]. Computer Engineering & Science,2007,29(8):40-42.(in Chinese)

[11] Wang Xiao-ying. A novel fuzzy clustering algorithm for the analysis of axillary lymph node tissue sections [J]. Applied Intelligence,2007,27(3):237-248.

附中文参考文献：

[9] 王书朋,姬红兵.利用团块模型进行目标跟踪 [J].西安电子科技大学学报(自然版),2008 35(5):799-804.

[10] 单勇,王润生,杨凡.基于多特征背景模型的运动目标检测算法 [J].计算机工程与科学,2007,29(8):40-42.

JINSheng-tao,born in 1988,MS candidate,CCF member(E200030383G)，his research interests include pattern recognition, and computer vision.

Apedestrianshadoweliminatingalgorithmbasedonblobmodel

JIN Sheng-tao1,MENG Zhao-hui1,LIU Wei2

(1.School of Computer and Information,Hohai University,Nanjing 211100;2.Troop 63780,Sanya 572000,China)

To solve the problem of negative effect of shadows in pedestrian detection,a shadow eliminating algorithm based on blob model is proposed. We first describe the pedestrian model with blob structures,and then compute the blob’s central moments and vertical histogram. With the help of these data and the a geometric method,the suspected shadow region can be obtained.After that,the rough approximation of the shadow region can be further refined through shadow modeling with several features including the intensity,orientation and center position of the shadow region. Finally,shadow blobs can be precisely eliminated from the pedestrian blob model.Experimental results demonstrate that different shadows under different conditions can be eliminated accurately and effectively.

shadow eliminating;blob histogram;shadow modeling;pedestrian detection

1007-130X(2014)11-2203-07

2013-05-23;

：2013-09-22

TP391.41

：A

10.3969/j.issn.1007-130X.2014.11.025