基于Mean Shift算法的運動目標跟蹤方法研究

滕蓉

【摘要】研究了運動視頻圖像的非參數密度估計及目標跟蹤方法，引出了Mean Shift算法理論。將Mean Shift算法應用于跟蹤系統中，在運動目標檢測的基礎上，利用特征空間中特征值的概率密度描述目標模型與候選模型，并對目標進行定位。實驗結果證明了基于Mean Shift算法的目標跟蹤能準確跟蹤目標，該算法可收斂到局部極值點，具有良好的跟蹤效果。

引言

Mean Shift目標跟蹤算法采用核概率密度來描述目標的特征，基于Bhattacharyya系數用Mean Shift進行迭代搜索，最終收斂的位置即為目標中心。對于尺寸變化不大的目標，其跟蹤效果主要取決于用于計算Bhattacharyya系數的目標模板以及候選目標特征選取機制。目標特征的選取原則是要能夠最大限度地描述目標本身獨有的性質，它決定了Bhattacharyya系數對Mean Shift迭代的收斂速度和收斂位置。常用的方法有圖像（灰度或者彩色圖像）直方圖，也有一些國內學者采用方向直方圖，還有結合目標的其他特征，如目標中心加權距離、目標梯度圖像、標準差圖像等，在一定程度上增強了跟蹤的魯棒性。但是用這些方法得到的直方圖中，除了目標本身的灰度以外，還包含了大量的背景成分，背景發生變化將會導致候選目標區域和模板直方圖的最佳匹配位置與實際目標中心有所偏差，對跟蹤快速運動的目標，系統將會變得不穩定，最終導致目標丟失。文獻提出采用背景加權的方法計算目標模板與候選區域特征直方圖，試圖消除背景影響，但由于目標窗中的部分背景在擴大窗中可能并不存在，因此這種方法亦無法完全消除背景，實際的跟蹤效果并沒有顯著提高。

本文將Mean Shift算法用于目標跟蹤中，首先要初始化被跟蹤目標所在區域，采用運動目標檢測出來的結果作為初始目標。然后對目標區域的所有像素點計算特征空間中每個特征值的概率。利用相似性函數度量初始幀目標模型和當前幀候選模型的相似性，在計算相似函數最大值時可得到目標的運動方向，通過不斷的迭代計算，在當前幀中，目標會收斂到運動目標的真實位置，從而實現跟蹤。并將其應用到目標跟蹤實驗中，最后對實驗結果進行了分析。

一、Mean shift算法理論

在目標跟蹤過程中，常將目標的相關信息映射到特征空間中，特征值表示特征空間的隨機變量。對于參數估計來說，在特征值服從已知函數類型的概率密度函數條件下，通過目標區域中觀測到的數據對密度函數相關的參數進行估計，然后得到整個空間的概率密度分布情況。在實際應用中，數據模型往往是未知的，因此事先確定概率密度函數的表達式是不現實的，此時通常是采用非參數密度估計解決此類問題。

非參數密度估計方法無需事先知道觀測數據的函數分布形式，只需要通過對觀測數據樣本的分析就可以進行概率密度估計。非參數密度估計的方法通常有最近鄰域法、直方圖法以及核密度估計法等。其中，最近鄰域法比較容易受局部噪聲的干擾，很難準確地對模型進行估計；直方圖法只適用于維數較低的數據分布，當數據維數增高時，直方圖將面臨維數災難，且所需的存儲空間也將會隨維數的增加成指數增加；核密度方法可以很快產生漸進無偏密度估計，擁有比較不錯的概率統計性質，它是目前最常被用到的非參數估計方法。

核密度估計方法的基本原理與直方圖方法類似，首先將采樣數據的值域分成幾個相等的區間（bin），根據數據值的大小，將數據分配到各個bin中，其中每個bin的概率值就是對應的數據的個數與總體樣本數據個數的比率。核密度估計比直方圖法多一個用來進行數據平滑的核函數，核函數也叫做“窗函數”。常用的核函數有均勻核函數、三角核函數、Gauss核函數、Epanechikov核函數等，其共同特點是關于中信對稱，且是有限局部支撐的。

Mean Shift算法的本質是變步長梯度上升搜索峰值，其運算過程就是在概率空間中求解概率密度機制，也就是通過迭代計算的方法將樣本點逐漸移動到概率密度函數f（x）的局部極大值點。

關于Mean Shift算法的收斂性問題，文志強等和李鄉儒等研究并證明了該算法是收斂的。

二、基于Mean shift算法的目標跟蹤

將Mean Shift算法用于目標跟蹤中，首先要初始化被跟蹤目標所在區域，本節采用上一章中運動目標檢測出來的結果作為初始目標，即一個包含運動目標的最小外接矩形區域，該區域也是核函數作用的區域，區域的大小等于核函數的帶寬。然后對目標區域的所有像素點計算特征空間中每個特征值的概率，即描述目標模型。特征空間取穩定性較強的顏色特征，若是RGB顏色模型則將顏色子空間R、G、B各分成k個相等的區間，共m個，若是灰度模型則只需將灰度分成m個區間即可。區間對應的值稱為特征值，所有的這些區間組成了特征空間。在以后的每幀圖像中，對目標的候選區域內同樣計算特征空間中的所有特征值的概率，即候選模型描述。然后利用相似性函數度量初始幀目標模型和當前幀候選模型的相似性，在計算相似函數最大值時可得到目標運動的Mean Shift向量，也就是運動目標的運動方向，通過不斷的迭代計算Mean Shift向量，在當前幀中，最終目標會收斂到運動目標的真實位置，從而實現跟蹤。

實驗結果與分析

實驗基于SEED_DEC643開發平臺，視頻口傳入的是ITU-RBT，656格式的圖像數據流經公式轉化后得到RGB格式的圖像數據，將RGB空間分成m=8×8×8=512個特征空間來描述目標模型。

視頻場景為一個人走過，運動過程中遇到樹，目標被完全遮擋，短時間過后目標又重新出現在視野內。實驗中，運動目標模型的位置、大小等信息由運動檢測結果產生，為了避免背景因素過多的影響目標區域而導致跟蹤過程失敗，在目標區域的選擇方面，是在檢測出的包含運動目標的最小外接矩形的基礎上按比例縮小，作為目標跟蹤的初始區域，并對此區域進行目標描述。可以看出，Mean Shift算法能夠準確的跟蹤運動目標。在跟蹤過程中，通過CCS中watch window工具對變量的實時觀察可以看出算法的迭代步驟一般在3次左右，算法收斂速度快，實時性好。

四、結論

本文研究了運動圖像的非參數密度估計和跟蹤方法，引出了Mean Shift算法理論，通過Mean Shift向量的迭代，使核函數的中心點快速的收斂到數據空間中樣本分布密度最大的位置。將Mean Shift算法應用于跟蹤系統中，運動目標模型是在運動目標檢測結果的基礎上初始化的。首先利用特征空間中特征值的概率密度描述目標模型與候選模型。通過跟蹤實驗證明了基于Mean Shift算法的目標跟蹤能夠準確的跟蹤目標。