【正文】 算法一個特性： Meanshift 向量會一直指向密度增長最快的方向。式中的第一項(xiàng)和 (11)式形式十分近似，因此可以將算子 G 代替 (12)中的 K 算子，便得到 (15)中的第一個乘項(xiàng) 2, 1( ) ( )ngd ihG d ic XXf X gn h h???? ? (16) 第二項(xiàng)便是 meanshift 向量 1,1()()()niiihG niiXXXghm X XXXgh???????? (17) 這也就是表示， meanshift 向量是用核函數(shù)加權(quán)的樣本均值和 X 的差。這個條件在實(shí)際應(yīng)用中不難做到。假設(shè)對 一切 X，核函數(shù)的導(dǎo)數(shù)都存在。很容易想到，密度最密集的部分，其梯度 ( ) 0fx??， Meanshift 方法就是找到該點(diǎn)位置的一個快捷算法。這些核函數(shù)可以滿足實(shí)際應(yīng)用中的大多數(shù)需求。在兩種由一元變量的方程來產(chǎn)生多元核函數(shù)方程的公式中，人們測出武漢理工大學(xué)畢業(yè)設(shè)計 (論文 ) 8 （同時也證明了）最好的估計質(zhì)量的核函數(shù) 方程為 [33,] 1()0Exkx ??? ?? 011xx??? (7) 同時，它在 d 維空間中，按照半徑對稱的形式進(jìn)行擴(kuò)展可以得到 211 ( 2) (1 )() 20dEc d XKX ?? ???? ??? 1Xotherwise? (8) 需要注意的是， 該形式的核函數(shù)在邊界出不存在導(dǎo)數(shù)。在將核函數(shù)方程帶到 (1)中，就可以得到十分著名的密度估計方程 11( ) ( )n idiXXf X Kn h h???? ? (6) 該方程的估計質(zhì)量，可以用實(shí)際密度與估計值之間誤差的平均值和方差值來表示。后者明顯好處是讓參數(shù)變成了一個值 0h? ，又一次降低了問題的復(fù)雜程度。歸一化常數(shù) ,kdc 確保了核函數(shù)的積分值為 1，是個嚴(yán)格正實(shí)數(shù)。以上討論的兩種函數(shù)都可以滿足公式 (3)的條件，但根據(jù)我們的目的，一般選擇關(guān)于半徑對稱的方程作為核函數(shù)更加合適。多元核函數(shù)可以通過單變量核函數(shù) 1()Kx用以下不同的方式產(chǎn)生 11( ) ( )dPiK x K x??? ,1( ) ( )S kdK x a K x? (4) 其中 ()PKx是通過單變量核函數(shù)的累積而獲得的，核函數(shù) ()SKx是通過對單變量核函數(shù)在 d 維空間內(nèi)的旋轉(zhuǎn)而產(chǎn)生的，對與固定的半徑，該函數(shù)的值都是相同的（即該函數(shù)關(guān)于半徑對稱）。 Meanshift 算法定義以及效率分析 Meanshift 算法核函數(shù)概述 [1] 核函數(shù)密度估計是最常見的密度估計函數(shù)之一。在第三節(jié)，將直方圖作為目標(biāo)的主要模型，通過對直方圖的對比來提取圖像中與目標(biāo)相近的點(diǎn)，然后 Meanshift 方法用于目標(biāo)跟蹤，并對其方法進(jìn)行詳細(xì)介紹和跟蹤效率進(jìn)行分析。 本論文成功的進(jìn)行了很多跟蹤方法，處理了許多復(fù)雜的跟蹤問題。在跟蹤這方面， Bhattacharyya 相關(guān)系數(shù)的實(shí)際意義就是對候選目標(biāo)進(jìn)行打分。由于建立的相關(guān)度摸型是個連續(xù)函數(shù)，因此，基于梯度的方法便可以使用，使得該優(yōu)化方法會比優(yōu)化的搜索方法要快速許多。本文的主要介紹 的是 Meanshift 在跟蹤問題上的應(yīng)用。一本書 [32]討論了用 Meanshift 做密度檢測的優(yōu)點(diǎn)時，這個算法才被統(tǒng)計領(lǐng)域所發(fā)現(xiàn)并廣泛使用。 武漢理工大學(xué)畢業(yè)設(shè)計 (論文 ) 6 2 Mean Shift 跟蹤器設(shè)計 引言 Mean Shift 算法，在 1975 年就已經(jīng)被 Fukunaga 和 Hostetler [1]等人提出，當(dāng)時幾乎快被人們遺忘，直到 Cheng 的一篇論文 [31]才點(diǎn)燃了人們對該算法的興趣。最后，利用 Meanshift算法對其進(jìn)行跟蹤并且分析其算法復(fù)雜度和該算法的優(yōu)勢； 3) 在 Meanshift 的基礎(chǔ)之上，建立一個能夠自適應(yīng)目標(biāo)大小的 camshift 算法，同時將全局運(yùn)算改為對圖像的局部進(jìn)行運(yùn)算，從而可以大大節(jié)省運(yùn)算量。其內(nèi)容可以大致分為三個部分： 1) 推出了一種基于目標(biāo)建模和定位的跟蹤算法，該算法為跟蹤非剛性物體提供武漢理工大學(xué)畢業(yè)設(shè)計 (論文 ) 5 了新的框架。與此同時人的直接跟蹤法 [28]時間復(fù)雜度高，而且經(jīng)常會用上一些其它的模型 [29][30]。跟蹤人的時候，會產(chǎn)生很多問題，這些問題大部 分都是由人們的三維移動的無規(guī)律性而產(chǎn)生的。對模型的訓(xùn)練學(xué)習(xí)是建立在一些穩(wěn)定的圖像結(jié)構(gòu)，運(yùn)動信息和一些異常過程 [24]的基礎(chǔ)之上的。目前有許多學(xué)者根據(jù)這點(diǎn)特性做了許多算法，基于梯度的算法 [21]是根據(jù)歸一化的相關(guān)度來進(jìn)行跟蹤，然后相關(guān)度有所缺點(diǎn)，就是對光照特別敏感。目標(biāo)定位和配準(zhǔn)方法都是最大化似然函數(shù)。 基于目標(biāo)建模和定位的跟蹤算法研究現(xiàn)狀 在另一方面，目標(biāo)跟蹤算法的第二派系：基于目標(biāo)的建模與定位的跟蹤。在文獻(xiàn) [16]中，概率排除的多目標(biāo)算法被提出。 以上討論的濾波和數(shù)據(jù)關(guān)聯(lián)的方法都用于計算機(jī)視覺領(lǐng)域中多目標(biāo)的跟蹤情形。連接數(shù)據(jù)關(guān)聯(lián)度濾波 (Joint Data Association Filter(JPDAF)[8, ], 于此同時，計算了方法和目標(biāo)的關(guān)聯(lián)度概率把所有目標(biāo)都聯(lián)系起來。這些做法的假設(shè)是，對于一個給定武漢理工大學(xué)畢業(yè)設(shè)計 (論文 ) 4 的目標(biāo)來說，只有一種方法是有效的，其余的方法都是隨機(jī)的干擾。 當(dāng)跟蹤于一個多目標(biāo)的混亂環(huán)境下，一些跟蹤方法的有效性和關(guān)聯(lián)性就產(chǎn)生了。當(dāng)狀態(tài)空間是離散而且由有限個狀態(tài)組成的時候，隱馬爾科夫 (Hidden Markov Models, HMM)濾波 [10]可以用來做跟蹤。 當(dāng)噪聲向量是屬于高斯分布， kf ， kh 都是線型算子的時候，最好的方法是用卡爾曼濾波法 (Kalman Filter)[8, ]，當(dāng) kf ， kh 都是非線性算子的時候，進(jìn)行線型化就得到了擴(kuò)展的卡爾曼濾波法 (Extended Kalman Filter, EKF)[8]，兩種方法的后驗(yàn)概率分布都是高 斯型?？梢岳玫姆椒?1,...{}kkz ? 和相應(yīng)的狀態(tài)方程( , )k k k kz h x n? 相關(guān)。 研究現(xiàn)狀 基于濾波和數(shù)據(jù)關(guān)聯(lián)度的跟蹤算法 研究現(xiàn)狀 基于濾波和數(shù)據(jù)關(guān)聯(lián)度的目標(biāo)跟蹤，可以歸納為對離散時間動態(tài)系統(tǒng)的狀態(tài)空間建模方法。例如，人群中的人臉更多的依靠目標(biāo)的表 現(xiàn)形式，而不是目標(biāo)動態(tài) [6]，而在現(xiàn)場的目標(biāo)監(jiān)控系統(tǒng)里 [7]，目標(biāo)的移動和攝像機(jī)的自我移動是更關(guān)鍵的部分。 另一種 濾波和數(shù)據(jù)關(guān)聯(lián)度 是一個處理目標(biāo)動態(tài)變化，先驗(yàn)學(xué)習(xí)的由上至下的過程。同時 Comaniciu 等人 [4] 還把跟蹤問題近似為一個 meanshift 最優(yōu)化問題，使得跟蹤可以實(shí)時的進(jìn)行。 Meanshift 算法 [1]是該派別的主力算法之一，該算法是一種在一組數(shù)據(jù)的密度分布中尋找局部極值的穩(wěn)定 [2]的方法。 1 緒論 背景分析 實(shí)時跟蹤算法一直在很多計算機(jī)視覺領(lǐng)域里是個難題，例如在監(jiān)控系統(tǒng)，感知用戶界面，基于目標(biāo)的視頻壓縮算法，汽車駕駛輔助系統(tǒng)等等尖端領(lǐng)域里，武漢理工大學(xué)畢業(yè)設(shè)計 (論文 ) 3 都是一個沒有被解決的難題。 object tracking。s utility in the object tracking and analysis the advantage and efficiency in the object tracking. Finally use the mean shift to find the maximum portion in the distribution. (3) Introduce the modification of the mean shiftcamshift, and use it into the object tracking. At last, use the CAMSHIFT to find the local maximum in the feature distribution. Then achieve the realtime tracking. Also, we use a great number of examples to show the effect of the tracking. Keywords: MEANSHIFT。并用大量的實(shí)例演示其跟蹤效果。 (2) 介紹了 meanshift 算法在目標(biāo)跟蹤領(lǐng)域里的應(yīng)用 ， 講述了該過程中 圖像的特征提取，直方圖之間進(jìn)行對比（反向投影）運(yùn)算的方法從而提取出離散數(shù)據(jù)點(diǎn)的分布，最后利用 meanshift 找出該分布的最密集位置，從而實(shí)現(xiàn)跟蹤效果。在分析一些傳統(tǒng)的跟蹤算法優(yōu)缺點(diǎn)后，提出了局部的 CamShift 算法，后經(jīng)分析得知，該算法在保證了 MeanShift 的快速優(yōu)點(diǎn)的前提下，改進(jìn)了該算法的多種缺點(diǎn)，從而能夠在目標(biāo)距離發(fā)生變化，室內(nèi)環(huán)境光線昏暗，目標(biāo)物體遭到干擾的情況下依然能夠有效地追蹤物體。 武漢理工大學(xué)畢業(yè)設(shè)計 (論文 ) 目 錄 摘 要 .................................................................................................................................................................................... I ABSTRACT .........................................................................................................................................................................2 1 緒論 ....................................................................................................................................................................................2 背景分析 ....................................................................................................................................................................2 研究現(xiàn)狀 ....................................................................................................................................................................3 ..............................................................................................3 基于目標(biāo)建模和定位的跟蹤算法研究現(xiàn)狀 .................................................................................................4 主要研究內(nèi)容 ...........................................................................................................................................................4 2 MEAN SHIFT跟蹤器設(shè)計 .............................................................................................................................................6 引言 ............................................................................................................