基于團塊模型的行人陰影抑制算法*

金圣韜，孟朝暉，劉 偉

(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

金圣韜(1988),男，江蘇蘇州人，碩士生，CCF會員(E200030383G)，研究方向為模式識別和計算機視覺。E-mail:jst2009@163.com

通信地址：211100 江蘇省南京市河海大學計算機與信息學院

Address:School of Computer and Information,Hohai University,Nanjing 211100,Jiangsu,P.R.China