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