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

金圣韜，孟朝暉，劉 偉

(1.河海大學(xué)計算機與信息學(xué)院，江蘇 南京 211100;2.63780部隊，海南 三亞 572000)

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

金圣韜1，孟朝暉1，劉 偉2

(1.河海大學(xué)計算機與信息學(xué)院，江蘇 南京 211100;2.63780部隊，海南 三亞 572000)

為有效解決行人陰影對行人跟蹤產(chǎn)生的影響，提出一種基于團塊模型的陰影抑制算法。該算法利用團塊結(jié)構(gòu)作為行人模型，通過計算團塊的矩特征和團塊垂直直方圖，借助幾何的方法獲得疑似陰影區(qū)域。然后，將該疑似陰影區(qū)域的灰度、方向、中心位置作為參數(shù)對整個前景區(qū)域進行陰影建模，使得陰影區(qū)域更精確。最后，從行人模型中剔除陰影團塊達到陰影抑制的效果。經(jīng)過視頻序列測試，本文算法對不同運動方向、不同數(shù)量的行人均有良好的陰影抑制效果，表明了該設(shè)計方案的有效性和準確性。

陰影抑制；團塊直方圖；陰影建模；行人跟蹤

1 引言

視頻監(jiān)控技術(shù)就是為了防止安保人員的誤判、利用自動分析技術(shù)進行視頻監(jiān)控的技術(shù)[1]。目前的研究方法都是假設(shè)視頻序列中不存在陰影，而在光線充足的場景，移動的陰影將被錯誤地劃分為前景對象。這將導(dǎo)致目標位置估計、目標行為分析和目標識別的錯誤。

目前，運動陰影檢測與抑制的方法大致分為如下三類：基于顏色模型的方法，選擇一個合適的顏色空間，利用陰影像素值在顏色空間中的色彩特性進行陰影抑制，比如HSV空間[2]、色彩特征不變量空間[3]和歸一化RGB空間[4]，但這些方法易受噪聲影響并且對光強變化敏感；基于物理模型的方法，通過物理的方法建模或?qū)W習(xí)陰影像素的特定外觀特征，比如雙光源雙色反射模型BIDR(Bi-Illmuinant Dichromatic Reflection)[5]，但它無法處理目標色調(diào)與背景相同的情況；基于紋理模型的方法，通過陰影光譜特征獲得候選區(qū)域，再根據(jù)這些區(qū)域紋理的相關(guān)性來區(qū)分前景和陰影，比如歸一化互相關(guān)[6]、Gabor濾波[7]、正交變換[8]等，由于要對一個像素的多個鄰域進行計算，故運算量較大、實時性差。

針對上述算法的不足，本文提出一種基于團塊模型的行人陰影抑制方法。首先構(gòu)建行人團塊模型，再通過計算團塊的矩特征和團塊垂直直方圖，借助幾何的方法獲得疑似陰影區(qū)域。然后，將該疑似陰影區(qū)域的灰度、方向、中心位置作為參數(shù)對整個行人和陰影進行陰影建模，使得陰影區(qū)域更精確，對不同朝向、不同數(shù)量行人的陰影具有較好的抑制效果。此外，由于本文算法簡單，時間復(fù)雜度較小，視頻處理速度約為7.5幀/s。

2 算法流程

團塊[9]是指像素在空間上連通并且具有相似圖像特征(如顏色、紋理等)的區(qū)域。基于團塊模型的陰影抑制算法流程如圖1所示?？紤]到樹葉晃動等因素，采用混合高斯動態(tài)背景建模技術(shù)[10]將行人的運動前景提取出來。利用團塊建模算法對前景進行建模，使每個行人都由相應(yīng)團塊結(jié)構(gòu)表示。對于行人的陰影抑制過程采用由粗到細的步驟，首先采用團塊直方圖投影獲取行人與陰影的分割點，然后利用幾何矩估計陰影區(qū)域的朝向，這樣行人和陰影區(qū)域就可以通過一條有向直線被粗略地區(qū)分開。在細化階段，陰影邊界可以通過陰影建模算法得到進一步處理。最后，標注陰影區(qū)域并在行人團塊模型中剔除陰影團塊。

Figure 1 Flow chart for pedestrian shadow elimination based on blob model圖1 基于團塊模型的行人陰影抑制算法流程圖

2.1 行人團塊建模算法

行人團塊建模算法分為團塊提取和團塊合并兩個階段。對每一幀新圖像，將其分割為較小的團塊并計算每個團塊內(nèi)的像素顏色均值；再將顏色上相近且空間上相鄰的團塊合并構(gòu)成較大團塊，表征全場景的顏色分布；然后利用混合高斯背景建模算法提取的前景模板標記運動的團塊；最后以每個運動團塊的形心為結(jié)點，利用模糊聚類算法再次合并團塊構(gòu)建行人團塊模型。

本文以四叉樹分割算法作為團塊提取算法，按照自下向上的生長方式，通過多次將局部相鄰且特征相似的團塊向上逐步聚合的方式來提取團塊。團塊的數(shù)據(jù)結(jié)構(gòu)中包括：團塊矩形坐標、背景標記、陰影標記、中心團塊標記、團塊編號、團塊重心坐標、團塊顏色均值等屬性。

算法步驟如下：

步驟1將圖像分割為由N×N個小區(qū)域aij(N的取值由目標的尺寸決定)構(gòu)成的區(qū)域矩陣AN×N，并初始化Blob結(jié)構(gòu)數(shù)組B。

(1)

步驟3若dij小于閾值d0，則將這兩個團塊合并，修改Blob結(jié)構(gòu)的中心團塊標記lab，使之統(tǒng)一為aij的團塊編號。

步驟4重復(fù)步驟3，直到結(jié)構(gòu)數(shù)組B遍歷完畢。這樣就完成了四叉樹一次由下向上的聚合過程。

步驟6返回步驟5，如此重復(fù)，直到得到一個穩(wěn)定的分割結(jié)果。

這樣就完成了對一幀圖像顏色在空間位置上的聚類。如圖2a為對第75幀視頻圖像進行三次聚合后的結(jié)果，圖中每個方格表示一個團塊區(qū)域，顏色場景復(fù)雜的部分(如人物、樹木)方格分布較小較密，而顏色場景簡單的部分(如天空、地面)方格分布較為稀疏，尺寸也大些。

Figure 2 Blob extraction result, and predestrain model based on blob圖2 團塊提取和行人團塊模型效果圖

經(jīng)過團塊提取后，為了獲得運動前景以構(gòu)建行人團塊模型，還需進行背景建模。由于視頻圖像中的每個像素點，其值在序列圖像中的變化可以看作是一個不斷產(chǎn)生像素值的隨機過程。因此，對于每幀新進入的像素值，可以選擇混合高斯背景建模判斷該像素屬于運動前景還是背景，由此得到前景模板M。我們利用M標記相應(yīng)團塊區(qū)域，這樣就能有效剔除背景團塊。

(2)

其中,Ik(x,y)是第k幀圖像，Bk(x,y)是第k幀的背景模板，Td是閾值。

由于同一目標的不同團塊在空間上具有高度相關(guān)性，為了利用鄰域信息，本文定義空間函數(shù)如下：

(3)

其中，(Δx,Δy)為團塊i的重心和聚類中心j坐標之差。我們利用hij來衡量團塊i屬于第j個聚類的可能性大小。下面給出隸屬度函數(shù)uij及聚類中心vi的迭代計算公式：

(4)

(5)

其中，zj為團塊j的特征向量。α為模糊因子，控制著模糊聚類間的分享程度。公式(5)中uij作為權(quán)值，表明各樣本成為聚類中心的可能性。

團塊合并算法步驟如下：

(1)設(shè)n為一幀圖像中所有參與聚類的團塊數(shù)目，給定聚類類別數(shù)q(2≤q≤n)，參數(shù)α，迭代停止閾值ε。

(2)給出初始聚類中心集合V(0)，設(shè)置迭代計數(shù)器f=0。

(6)

(7)

(5)更新迭代計數(shù)器，重復(fù)(3)、(4)，直到距離范數(shù)‖V(f+1)-V(f)‖<ε或計數(shù)器值f達到一定次數(shù);

(6)去模糊化。本文合并算法的最終目的是為了將空間相鄰的團塊合并，標記為同一團塊類別。我們采用最大隸屬值法去模糊化。用Lj表示第j個樣本點所屬類別，則有：Lj=argt{max(uij)}。

我們將面積較大且相互距離較遠團塊的形心作為初始聚類中心賦給V(0)，并把這種團塊數(shù)量作為聚類類別數(shù)量。迭代停止閾值ε影響了聚類的精度和速度，此處取0.4。模糊因子α與樣本數(shù)量有關(guān)，通常大于n/(n-2)，本文取1.65。

如圖2b所示，可以明顯發(fā)現(xiàn)陰影也被錯誤劃分為行人團塊模型的一部分，為了獲得穩(wěn)定的跟蹤效果，必須將陰影去除。

2.2 疑似陰影檢測

經(jīng)過行人團塊建模后，圖2b中行人與陰影的夾角可以通過矩特征計算得到。給定一維的行人模型團塊數(shù)組R，其中心矩定義如下：

(8)

(9)

其中，(x,y)是團塊R[i]的幾何中心，n是數(shù)組R的長度。如圖3a所示，點PG為團塊數(shù)組R的重心，夾角θR是我們要求的夾角。如圖3b所示，假設(shè)將行人和陰影構(gòu)成的整體區(qū)域看作一個橢圓，那么現(xiàn)在的問題就是在已知橢圓中心坐標PG和橢圓內(nèi)所有點的坐標(即各個團塊中心坐標)的情況下，求夾角θR，可以通過下式求得：

(10)

式(10)就是求使橢圓內(nèi)所有點到橢圓短軸投影距離的平方之和最小的那個夾角，即橢圓主軸與x軸的傾斜角。

Figure 3 Pedestrian blob model and pedestrian shadow ellips圖3 行人團塊模型與陰影橢圓

對式(10)求導(dǎo)，并令：

(11)

得：

(12)

根據(jù)式(12)，當(dāng)利用中心矩計算行人和陰影的方向后，為了獲得陰影分割線，我們還需要計算人和陰影的分割點PR。

點PR可以通過計算團塊垂直直方圖相鄰兩列差值，取差值最大列所對應(yīng)的橫坐標獲得。團塊垂直直方圖，如圖4所示，可以通過遍歷數(shù)組R自下向上沿著水平方向統(tǒng)計垂直方向團塊的數(shù)量獲得。設(shè)HR(x)為團塊垂直直方圖R的第x列分量，由此，我們定義團塊差分直方圖dHR(x)如下：

(13)

這樣，點PR的橫坐標x可以通過式(14)獲得：

(14)

其中，XRbottom是團塊差分直方圖的橫坐標取值范圍，即整個前景區(qū)域R的寬度，當(dāng)xR有多個取值時，保留距離團塊直方圖波峰最近的點。

Figure 4 The 75th vertical histogram of pedestrian blob圖4 第75幀行人團塊垂直直方圖

PR的縱坐標y可以通過團塊垂直直方圖中對應(yīng)的PR橫坐標得到。

(15)

其中，CR(x)表示團塊數(shù)組R的中心坐標集合。這樣我們就有一條有向直線將行人與陰影粗略地分割成兩部分R1和R2，直線方程如下：

(16)

由于陰影部分像素的亮度更暗并且顏色變化更小，因此陰影區(qū)域R2可以根據(jù)這個特性很容易地選擇。

整個疑似陰影檢測算法流程如下：

(1)根據(jù)前景團塊數(shù)組R計算團塊垂直直方圖HR(x)和夾角θR；

(2)根據(jù)團塊垂直直方圖HR(x)計算團塊差分直方圖dHR(x)；

(3)利用公式(14)，計算PR點的橫坐標；

(4)掃描團塊數(shù)組R，獲得中心坐標集合CR(x)；

(5)利用公式(15)，通過PR的橫坐標和CR(x)，計算得yR，這樣就獲得了PR點；

(6)根據(jù)公式(16)，利用夾角θR和PR獲得分割線，計算分割后兩部分顏色均值和方差，選擇均值和方差較小的區(qū)域作為疑似陰影區(qū)域R2。

2.3 陰影建模

當(dāng)疑似陰影區(qū)域R2確定后，我們將構(gòu)建一個合適的陰影模型使陰影區(qū)域得到進一步細化。本文將從灰度、距離、方向三個角度展開分析。

當(dāng)背景像素被陰影覆蓋時，該像素的亮度會變暗，飽和度通常會變小，而色度不會有較大變化。因此，最直接的方式就是考慮用像素的灰度去建立模型，公式如下：

(17)

其中，μR是疑似陰影區(qū)域R2的灰度均值，Th是閾值，Ik(x,y)為前景區(qū)域像素點(x,y)處的灰度值。這里，僅考慮灰度的缺點是當(dāng)某些距離疑似陰影區(qū)域較遠且灰度值接近μR的區(qū)域會被錯誤劃分為陰影區(qū)域。

由于行人的陰影都是從腳部往外延伸且陰影的長度總是有限的，因此我們借助疑似陰影區(qū)域分割點PR來測量陰影的長度，并把一定長度范圍內(nèi)的像素點都認為是陰影，公式如下：

(18)

其中，(xR,yR)為PR點坐標，(x,y)為前景區(qū)域像素點坐標，Td為閾值，取行人身長的0.8倍。雖然現(xiàn)在考慮了距離和灰度，但不同光源會導(dǎo)致行人的陰影具有不同的朝向，因此為了更細致的陰影區(qū)域，必須在測算距離時考查疑似陰影方向θR。為此，本文按照式(19)將原始坐標映射到橢圓坐標：

(19)

為了提高模型的精確性和彈性，針對三種判斷依據(jù)，本文采用動態(tài)加權(quán)的方式融合各種因素。陰影模型表達式如下：

(20)

其中，α是權(quán)重更新速率，此處取0.1，w1是陰影灰度值權(quán)重，w2是陰影長度權(quán)重。權(quán)值會根據(jù)各個因素的符合程度自動調(diào)整。

2.4 陰影抑制

我們利用公式(20)對當(dāng)前幀的前景區(qū)域的每個像素點進行建模，如果d(x,y)小于閾值Ts，那么這個像素點會被劃分為陰影像素。這里Ts取疑似陰影區(qū)域R2內(nèi)所有像素點d值的均值。

(21)

整個陰影抑制算法流程如下：

(1)構(gòu)建行人團塊模型，使每個行人都有相應(yīng)團塊表示：

①獲取當(dāng)前幀，利用團塊提取算法，對圖像顏色進行聚類;

②利用混合高斯背景建模的前景模板，標記運動團塊;

③利用模糊聚類算法合并團塊，獲得最終行人團塊模型。

(2)對于每個行人團塊模型，分別利用疑似陰影檢測算法將行人與其陰影粗略地分割開：

①計算團塊中心矩，利用公式(12)計算陰影方向;

②計算團塊垂直直方圖，利用公式(14)和公式(15)計算行人與陰影分割點;

③根據(jù)陰影性質(zhì)，選擇相應(yīng)疑似陰影區(qū)域R2。

(3)陰影建模，利用公式(20)對行人和陰影進行建模，若d(x,y)

(4)更新混合高斯背景模型，返回(1)，直到視頻結(jié)束。

3 實驗結(jié)果與分析

本文針對校園場景進行多組實驗。實驗程序在Visual Studio 2008環(huán)境下編寫，計算機CPU采用Intel Core i3 3.07 GHz，視頻序列圖像大小為480*856。

為了評估本文方法的表現(xiàn)，定義精準率和虛警率作為評價指標。精準率是程序正確檢測出的陰影像素數(shù)量與實際存在的陰影像素數(shù)量之比。虛警率是被錯誤劃分為陰影像素的數(shù)量與程序檢測的所有陰影像素數(shù)量之比。

其中，由于每個團塊所包含像素點相同，可以通過人工統(tǒng)計團塊數(shù)量來代替統(tǒng)計像素數(shù)量。圖5顯示第73幀陰影抑制的效果圖，行人陰影處在人的正下方。

圖6給出了不同朝向和不同數(shù)量行人的陰影抑制效果圖,并與基于色彩特征不變量的陰影抑制

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給出了四段視頻中，兩種算法性能的評估結(jié)果。

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 不同朝向和不同數(shù)量行人的陰影抑制效果圖

根據(jù)實驗效果和數(shù)據(jù)表明，本文所提的方法對不同朝向、不同數(shù)量的陰影具有理想的分割和抑制效果，并且本文算法比基于色彩特征不變量的陰影抑制效果更明顯。

4 結(jié)束語

本文提出了一種有效的從動態(tài)場景中去除陰影的方法。我們按照由粗到細的步驟，首先使用行人團塊建模算法獲得行人模型；然后利用疑似陰影檢測算法計算得到一條有向直線將行人和陰影大致分割，獲得疑似陰影區(qū)域；最后在細化階段，對前景區(qū)域進行陰影建模使陰影區(qū)域更為準確。經(jīng)過實驗對比分析，本文算法能有效抑制陰影對行人目標檢測的影響，并具有較強的實時性。

[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].西安電子科技大學(xué)學(xué)報(自然版),2008 35(5):799-804.

[10] 單勇,王潤生,楊凡.基于多特征背景模型的運動目標檢測算法 [J].計算機工程與科學(xué),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 江蘇省南京市河海大學(xué)計算機與信息學(xué)院

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