基于自適應mean shift算法的多人頭檢測

杭朱飛，潘崢嶸（蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州　730050）

基于自適應mean shift算法的多人頭檢測

杭朱飛，潘崢嶸
（蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州730050）

基于均值偏移（mean shift）分割算法需人工進行帶寬選擇和耗時長問題，本文利用直方圖密度估計與真實密度之間局部協方差最小來進行自動帶寬計算方法。將該方法應用于彩色圖像多人頭的檢測中，可以有效克服因發色模型檢測出現的漏檢現象，該方法首先利用mean shift自動分割圖像，然后利用圖像的灰值形態學來增強發色的灰度特性后進行二值化，在此基礎上，采用二值形態學的膨脹腐蝕算法進行預處理，從而得到若干個候選區域 最后利用輪廓的幾何特征綜合判斷這些區域是否為人頭。實驗結果表明：自適應帶寬的mean shift算法可快速完成，并具有較好的分割，該方法顯示了良好的適用性，在檢測目標發色出現白發和染色情況下，不會造成漏檢，克服了發色模型檢測的缺陷。

均值偏移；直方圖密度估計；協方差；形態學；發色模型

在復雜背景下進行人頭檢測（Head Detection）是智能視覺處理系統的重要組成部分。在現實中，基于單一特征（如頭部輪廓、發色及相關統計特征等）的頭部檢測方法容易出現目標區域的誤檢測，因此基于多特征的頭部目標檢測是研究的熱點。

常用的人頭檢測算法有兩大類:一是基于先驗規則的，比如發色模型形狀［1］和膚色等［2］；另一類是基于特征和分類器的檢測方法，比如尋找人頭輪廓，然后采用支持向量機SVM（support vector machine）、AdaBoost［3］、神經網絡等分類器進行訓練。

基于先驗規則的方法，其主要思想是通過對大量的實驗數據統計，得出一個模型，然后利用提取出的模型來準確地檢測人頭；但是，先驗模型的提取容易受到光照影響，造成獲取的模型不準確，從而導致人頭檢測方法失敗。基于特征提取和分類器訓練的方法具有良好的魯棒性，人頭檢測的正確率也很高；但是分類器的訓練比較耗費時間，如果特征數目比較多還會增加空間復雜度。基于上述兩類方法的基礎上，本文提出利用mean shift的彩色圖像分割算法的人頭檢測方法，文中采用的自適應mean shift算法是一種特征空間聚類算法［4］，它的一個突出優點是不須人為地設定過多參數而可以得到較為客觀的分割結果。灰度圖像處理包括選擇式掩模平滑和灰值形態學進行處理，以提高頭部目標的灰度與背景的區別，為閾值分割的預處理和為輪廓特征進行人頭檢測提供基礎。

1　mean shift算法

1.1mean shift基本算法

Mean shift算法是一種非參數密度梯度估計過程，也是一種有效的統計迭代算法，最早由 Fukunaga和 Hostelel提出，而后由 Cheng以及Meer［5］等改進了mean shift算法中的核函數和權重函數，并將其應用于聚類和全局優化，才擴大了該算法的應用范圍，得到了進一步發展［6］。

mean shift算法的基本思想是通過沿著特征空間內樣本密度梯度方向進行反復迭代搜索，使各樣本點最終收斂于臨近的局部密度極大點。對于d維歐式空間Rd中的一個特征數據點中xi，i=1…n，假定d×d帶寬矩陣為Hi，它量化不確定的特征數據點xi，密度估計的核函數用高斯核函數，則在Rd空間中點x估計的密度概率值為：

其中，D2（x，xi，Hi）≡（x-xi）TH-1i（x-xi）表示馬氏距離從 x 到xi。

讓Hh為在每個數據加入權重得：

其中權重：

滿足則fv密度梯度估計為：

將式（4）左乘

由式（6）可得，均值平移向量與概率密度估計成反比，因此均值平移向量的方向總是指向概率密度增加最大的方向，即均值朝附近數據樣本密集區域移動。因此，n采樣點可以漂移到概率密度函數的局部極大值點［7］。

假如帶寬矩陣Hi等于固定帶寬H，則式（1）減少了Hi變量，轉化為：

而式（6）變為：

在固定帶寬下，通過迭代運算進行模點搜索，為了找到每個數據點到類中心［8］，而以模點的顏色來代替本類數據點的顏色，從而平滑圖像，也正是因為固定帶寬導致了迭代運算復雜而耗時長。在理論上，可變帶寬的分割效果會更加好，但是它要依靠帶寬矩陣Hi的選擇，下面將會討論合適估計帶寬矩陣Hi。

當給定核函數、允許誤差ε及初始點x，通過mean shift算法不停迭代，核函數的中心點將收斂到數據空間中密度最大的點，其迭代過程如下［9］：

1）計算mean shift矢量m（x）；

2）計算樣本均值與像素點之間的偏移量m（x）-x；

3）判斷如果‖m（x）-x‖＆lt;ε，結束循環，否則把m（x）賦值給采樣點x執行（1）繼續，直到滿足條件。

1．2帶寬自適應

在聚類中，帶寬h決定了核函數的影響范圍，帶寬h對核函數估計過程以及最終的聚類結果都有很大影響。如果h取值太過下，密度函數相當于n個數據點最后聚類為很多類，也就是過分分割。如果h很大，所有像素的密度接近與1且聚類成很少的類，這樣就失去分割的意義，也會導致耗時。所以，盡可能準確的密度估計結果和聚類結果來自于帶寬h的選擇。選擇窗寬h時應盡可能的使密度函數體現原始數據的分布特性。

1．2．1直方圖

文中使用直方圖密度估計對圖像的像素點的特征進行統計，直方圖是一種統計圖，對于一幅圖像來說，通過統計圖像中各個像素點的數量，從而對圖像的像素分布有一個直觀了解。這種辦法存在很多缺陷，例如估計出來的密度概率密度有很多毛刺，不是連續光滑的曲線，需要進行平滑處理，比較的直觀的表現如圖1所示。

圖1　直方圖光滑處理

對于一幅彩色圖像來說，不同與灰度圖像是單通道圖像，它是包含RGB的三通道，但是獲取步驟是相同的，計算其二維直方圖就可以［10］。對于RGB圖像，由于其處理是計算量較大，先將其轉化為LUV空間，根據文獻［11］LUV和Lab彩色空間最接近人對色彩的感官認識。基于這種原因，選用LUV作為 mean shift分割的目標彩色空間，L分量表示圖像的亮度，U、V分量表示圖像的色差。而對于一幅圖像的直方圖定義如下：

一幅圖片在范圍［0，G］內共有L個灰度級，其直方圖定義為離散函數h（rk）=nk，其中rk是區間［0，G］內的第K級亮度，nk是灰度級為rk的圖像中的像素數。

1．2．2帶寬選擇理論

有數學知識可知基本特性的標準梯度正態分布，它是估計成比例向下偏移的［12］。利用此屬性導致的直接結果是：在大樣本近似范圍之內，估計偏差值可以被取消，使得潛在分布的數據，在確定的范圍內有協方差估計。如果假設：在數據點x位置的附近，不確定的偏移值μ和協方差矩陣是服從多態正態分布的。協方差矩陣直接估計通常很難的，因為局部自適應正態分布需要一個領域大小范圍內擬合參數是估計的先驗知識。如果估計值是領域范圍內的，則需要擬合最優的規模不變測度。然而下面的理論對于這個問題提出了一個簡潔解決辦法。這個理論就是：假設數據點的真實分布f是服從正態分布N（μ，∈），固定帶寬的mean shift計算使用標準高斯核函數KH，那么當帶寬H=∈時，均值偏移向量的模值最大值，因此樣本服從正態分布時，可以自動計算出帶寬H=∈。而由數理統計的知識可知，在樣本量較大時，一般認為其服從正態分布。

文獻［7］可知因為真實分布f和協方差矩陣∈是服從多態正態分布，所以密度概率值也是服從正態分布的和協方差∈+H。同樣的，密度梯度估計是線性轉換得到可知在樣本量較大時，均值偏移的協方差相對較小，由式（8）可得：

帶寬的mean shift的規范由下式給出如下，具體的證明過程可看文獻［14］：

該理論導致一個有趣的比例選擇規范：基本分布具有局部的協方差等于帶寬最大化的歸一化mean shift矢量的幅度［13］。由于該理論是應用在求取每個模點中，一個解決方案（最小二乘法［14］）可以通過使用獲得mean shift軌跡表示多個測量所有數據點會聚到相同模點。歸納帶寬矩陣選擇的辦法如下：

假設n個數據點表示為xi，i=1…n，相應的帶寬為減少計算量區比例單位陣形式

1）在直方圖的分區級別內進行帶寬估計，對于每個帶寬Hj，i=1…k，

①用mean shift算法迭代；

②使用模點的均值和協方差組成（μju，∈ju）對每個分割得的模點u進行估計；

③關聯每個數據點xi均值和它模點的協方差；

2）在數據層進行帶寬估計，對每個數據點xi。s

①依靠估計集合（μ1，∈1）…（μk，∈k），定義相應的正態分布p1…pk；

②通過周圍分布最小的Jensen-Shannon divergence間距離來選擇最穩定的一種估計（μ，∈）。∈表示對xi選擇的帶寬。

算法的復雜度是k次，大于使用mean shift分析一個級別的數據分割復雜度。直接使用mean shift分析所有的直方圖密度級的復雜度為O（n2），其中n數據點的數量。用空間不規則密度和估計數據點的軌跡線去選擇一組q個去代表數據點，那么mean shift算法會減小復雜度O（qn），其中q＆lt;＆lt;n。這樣帶寬自適應的mean shift算法，對于運算的時間有了較大的提高，本文使用的參考軟件是Peter Meer開發的EDISON這個軟件，從分割效果和性能兩方面綜合考慮，hs=7和hr=6.5為圖像分割的最優核帶寬［15］。而本文自適應的帶寬會在執行時自適應，具體的效果如圖2所示和具體的參數如表1所示。

圖2　舉例說明EDISON和本文的mean shift

表1　EDISON和本文的mean shift時間比較

2　人頭檢測算法流程

2.1人頭檢測算法的總體框架

本研究的整體流程如圖3所示，主要包括mean shift分割、灰度處理、輪廓特征提取和特征判斷4大部分。

圖3　人頭檢測算法流程圖

2.2mean shift分割

根據mean shift算法進行分割，由上文的推倒公式（1）～（11）可知：影響mean shift算法主要性能的主要因素是帶寬H大小的選擇和K（x）核函數形式的選擇。文獻［12］表明：在實際應用中，不同形式的核函數對分割結果的影響遠沒有帶寬大小的影響大。通過mean shift算法實際物理意義的理解，帶寬H控制著影響當前數據點的影響半徑，不同的帶寬對分割效果影響很大。在帶寬比較小的時候，圖像處于過分割狀態（即過度分類），分割后的區域數最多，看不出明顯的聚類特征，使得本來應該屬于一個類別的特征點被分散成多個類別，但耗時最短。隨著帶寬的增加，耗時增加，分割區域數逐漸減小。因此，只有使用合適的帶寬，才能將數據集進行很好的分類，應用本文提出的自適應mean shift有比較好的結果，看上文。

2.3灰度處理

灰度處理包括圖像平滑和灰度形態學。平滑是一種實用的圖像處理技術，能減弱或消除圖像中高頻率分量，可是不影響低頻率分量。因為高頻率分量主要對應圖像中的區域邊緣等灰度值具有較大較快變化的部分，平滑濾波將這些分量濾去可以減少局部灰度起伏，使圖像變得比較平滑。本文使用選擇式掩模平滑，它克服了尖銳變化的邊緣或線條變得模糊的缺陷，可以保留一定的邊緣信息。灰度形態學中的膨脹即以結構元素f（x，y）為模板，搜尋圖像在結構基元大小范圍內的灰度和的極大值。腐蝕運算過程則是以結構元素f（x，y）為模板，搜尋圖像在結構基元大小范圍內的灰度差的極小值。

2.4輪廓特征提取

利用閾值分割后得到二值化處理后的圖像中存在著若干連通區域，即人頭候選區域。此時這些區域中可能存在孔洞或者邊緣存在毛刺，故首先對二值圖像使用膨脹、腐蝕算子進行形態學閉運算操作，結構元素選擇經典的3×3的模板；然后對閉運算的結果圖像進行邊緣檢測。

2.5特征判斷

對于上一步得到的輪廓序列進行逐個判斷篩選。判斷的條件為一些先驗知識，分別有離散度、占空比、面積、周長等。離散度C的定義為C=P2/AO，占空比Z的定義為Z=AO/AR其中，P是輪廓的周長，AO是輪廓包圍區域的面積，AR是輪廓的外接矩形的面積。這些先驗知識中的面積和周長需要根據實際采集的圖像中人頭的大小范圍進行設定。而離散度和占空比是一個比值，理想狀態下不會根據人頭的大小而改變。本研究對實際獲取的人頭圖像進行反復實驗，選定離散度閾值為18、占空比閾值為 0.8時效果比較好。完全符合這4個特征指標的輪廓即可判定為人頭區域。

3　實驗結果與分析

在VS2012+VC++環境下，對于垂直攝像頭下采集的視頻進行處理，進而驗證本研究的可行性和有效性。具體實驗結果見圖4。

圖4中，（a）至（e）為不同發色的多人頭處理結果。（a）為彩色原始圖像，（b）為用了Mean shift算法對圖像進行分割的結果，比較完整地分割出了頭部目標區域，但是同時也分割出了部分偽目標區域，（c）是s經過灰度化處理和閾值分割后獲得區域的結果，（d）是對（c）進行了二值形態（腐濁和膨脹）的結果，（e）為輪廓提取之后進行特征判斷的結果圖像。（f）至（j）為發色和衣服顏色類似的多人頭處理結果。（f）為彩色原始圖像，（g）為用了Mean shift算法對圖像進行分割的結果，出現了因衣服顏色和發色類似的灰度級出現了偽目標區域，（h）是經過灰度化處理和閾值分割后獲得區域的結果，（i）是對（h）進行了二值形態（腐濁和膨脹）的結果，（j）為輪廓提取之后進行特征判斷的結果圖像，特征條件的離散度是關鍵。

圖4　人頭檢測結果

4　結束語

本研究帶寬自適應mean shift分割算法同EDISON軟件使用的算法進行比較，由圖2和表s1能知道：在分割效果基本相同的情況下，執行mean shift的時間縮短明顯。本文將其應用在多人頭檢測下，能有效地去除非人頭區域的干擾，同時不會因為發色出現漏檢的現象，與利用發色模型進行頭部目標檢測存在優勢。而獲得的目標候選區域利用的是提取輪廓的特征（離散度、占空比、面積、周長等）進行判斷，與利用Hough變換建立圓存在性模型來說有更加好的實用性和適用性。

［1］Min Zhao，Dihua Sun，Hengpan He.Hair-color modeling and head detection［C］.Proceedings of the 7th World Congress on Intelligent Control and Automation，2008:7768-7772.

［2］McKenna J，Gong S，Raja Y.Modeling facial color and identity with Gaussian mixtures［J］.Pattern Recognition，1998，31（12）: 1883-1892.

［3］孫棣華，閆川，趙敏，等．結合梯度與彩色直方圖的人頭識別［J］.重慶工學院學報:自然科學版，2007，21（12）:1-5．

［4］Fukunaga K，Hostetler L D.The estimation of the gradient of a density function with applications in pattern recognition［J］. IEEE Trans on information Theory，1975，21（1）:32-40.

［5］Comaniciu D，Ramesh V，Meer P.Kernel-Based Object Tracking［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2003，25（5）:564-575.

［6］周芳芳，樊曉平，葉榛.均值漂移算法的研究與應用［J］.控制與決策，2007，22（8）:841-847.

［7］文志強，蔡自興.Mean shift算法的收斂分析［J］.Journal of Software，2007，18（2）:205-212.

［8］Comaniciu D，Meer P.Mean shift:A Robust Approach toward Feature Space Analysis［J］.Pattern Analysis Machine Intelligence，2002，24（5）:603-619.

［9］熊平，白云鵬.帶寬自適應Mean shift圖像分割算法［J］.計算機工程與應用，2013，49（23）:174-176.

［10］馬瑜，梁慧琳，張艷寧.自適應的均值漂移分割算法［J］.激光與紅外，2013，43（10）:1162-1165.

［11］賁志偉，趙勛杰.基于Mean Shift算法提取彩色圖像有意義區域［J］.激光與紅外，2009，39（9）:1004-1008.

［12］Stoker T.Smoothing Bias in Density Derivative Estimation［J］. Statistical Assoc，1993，88（423）:855-863.

［13］Comaniciu D，Ramesh V，Meer P.The Variable Bandwidth Mean Shift and Data-Driven Scale Selection［J］.International Conference on Computer Vision-ICCV，2001:438-445.

［14］Dorin Comaniciu.An algorithm for Data-Driven bandwidth selection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（2）:281-288.

［15］趙敏.單目視覺多行人目標檢測與跟蹤計算研究［D］.重慶：重慶大學，2010.

Multi head target detection based on adaptive mean shift algorithm

HANG Zhu-fei，PAN Zheng-rong
（College of Electrical and Information Engineering，Lanzhou University of Technology，Lanzhou 730050，China）

Segmentation algorithm based on mean shift（mean shift）need to manually select the bandwidth parameters timeconsuming problem，In the paper，method use the histogram density estimation between tap density and the local minimum covariance to automatic bandwidth calculation.The method is applied to a color image for detecting Multiplayer head，it Can effectively overcome undetected phenomenon for hair color model.Firstly，the mean shift algorithm to automatic image segmentation，Then use the gray value morphology image to enhance hair color gradation characteristic binarization，On this basis，the use of expansion algorithm binary morphology of corrosion pretreatment，To yield a final outline of several candidate regions use geometric features integrated to determine whether the region is to succeed.Experimental results show that: adaptive bandwidth mean shift algorithm can be done quickly.it have good applicability in the detection target appears under white hair and hair color staining，will not cause missed，hair color model to overcome the defects detected.

mean shift；histogram density estimation；covariance；morphology；hair color model

TN919.8

A

1674－6236（2016）11-0189-05

2016-02-04稿件編號：201602013

甘肅省自然科學研究基金計劃項目（1308RJZA273）

杭朱飛（1989—），男，浙江海寧人，碩士。研究方向：圖像處理，嵌入式。