均值漂移跟蹤算法

1、在無人駕駛車輛測試平臺(tái)上利用均值漂移跟蹤算法實(shí)現(xiàn)移動(dòng)圖像的實(shí)時(shí)跟蹤Benjamin Gorry, Zezhi Chen, Kevin Hammond, Andy Wallace, and Greg Michaelson摘 要：本文描述了一種用來跟蹤移動(dòng)目標(biāo)的新型計(jì)算機(jī)視覺算法，該算法是作為無人駕駛車輛長期研究的一部分而被發(fā)展的。我們將介紹在視頻序列中利用變量核進(jìn)行跟蹤的研究結(jié)果。其中，均值漂移目標(biāo)跟蹤算法是我們工作的基礎(chǔ)；對于一個(gè)移動(dòng)目標(biāo)，該算法通常用來在初始幀中確定一個(gè)矩形目標(biāo)窗口，然后利用均值漂移分離算法處理該窗口中的數(shù)據(jù)，將跟蹤目標(biāo)從背景環(huán)境中分離出來。我們并沒有使用標(biāo)準(zhǔn)的Epanech

2、nikov內(nèi)核，而是利用一個(gè)倒角距離變換加權(quán)內(nèi)核來提升目標(biāo)表示和定位的精度，利用Bhattacharyya系數(shù)使RGB色彩空間中兩個(gè)分布之間的距離最小化。實(shí)驗(yàn)結(jié)果表明，相對于標(biāo)準(zhǔn)算法，本算法在跟蹤能力和通用性上有一定的提升。這些算法已經(jīng)運(yùn)用在機(jī)器人試驗(yàn)平臺(tái)的組成部分中，并證明了這些算法的有效性。關(guān)鍵詞：Hume，函數(shù)程序設(shè)計(jì)，無人駕駛車輛，先驅(qū)者機(jī)器人，視覺I. 引言本文比較和對比了在視覺序列中跟蹤移動(dòng)目標(biāo)的三種計(jì)算機(jī)視覺算法。對于很多無人駕駛車輛（AV）來說，在復(fù)雜背景中檢測和跟隨移動(dòng)目標(biāo)的應(yīng)用是至關(guān)重要的。例如，這可以讓一個(gè)全尺寸無人駕駛車輛跟蹤行人或者移動(dòng)車輛并避免與之相撞。同時(shí)對于機(jī)器

3、人而言，這項(xiàng)技術(shù)也可以提升導(dǎo)航性能和增強(qiáng)安全性。對單個(gè)移動(dòng)目標(biāo)的良好隔離，將便于我們針對感興趣的目標(biāo)進(jìn)行應(yīng)用開發(fā)。而所有的這些應(yīng)用都要求我們能夠?qū)崟r(shí)的處理全彩色的視頻序列。我們的工作是在基于先驅(qū)者P3-AT全地形機(jī)器人的無人駕駛車輛測試平臺(tái)上進(jìn)行的，它是一個(gè)英國項(xiàng)目的一部分。這個(gè)龐大的項(xiàng)目是由國防科學(xué)技術(shù)中心（DTC）下轄的無人系統(tǒng)工程（SEAS）為了開發(fā)新型無人駕駛車輛傳感器技術(shù)而建立的。國防科學(xué)技術(shù)中心的無人系統(tǒng)工程是由英國工業(yè)聯(lián)盟操作管理，旨在通過采取系統(tǒng)工程的方法在整個(gè)系統(tǒng)和子系統(tǒng)層次上，研究有關(guān)無人系統(tǒng)的創(chuàng)新性技術(shù)，以此達(dá)到利用科學(xué)技術(shù)進(jìn)步促進(jìn)軍事能力發(fā)展的目的。本文有許多獨(dú)到之處。

4、第一，基于之前探討的均值漂移算法，我們介紹了在復(fù)雜、混亂的背景下追蹤移動(dòng)圖像的新算法。第二，我們展示了我們的算法能夠在全尺寸視頻圖像中實(shí)時(shí)地追蹤移動(dòng)目標(biāo)。第三，我們以先驅(qū)者P3-AT全地形機(jī)器人為基礎(chǔ)，介紹了如何在一個(gè)簡易無人車輛測試平臺(tái)上配置新算法。最后，我們的實(shí)現(xiàn)方式是與眾不同的，因?yàn)槲覀儾捎眯路f的Hume1,2編程語言來編寫程序。這一語言的新奇之處在于將函數(shù)式編程概念與編寫實(shí)時(shí)反應(yīng)系統(tǒng)的有限狀態(tài)自動(dòng)機(jī)有機(jī)結(jié)合起來。B. Gorry, Z. Chen, G. Michaelson來自蘇格蘭瑞卡頓的赫瑞瓦特大學(xué)計(jì)算機(jī)科學(xué)系。K. Hammond來自蘇格蘭圣安德魯斯的圣安德魯斯大學(xué)計(jì)算機(jī)科學(xué)學(xué)

5、院。A. Wallace來自蘇格蘭瑞卡頓的赫瑞瓦特大學(xué)電子與計(jì)算機(jī)工程系 II. 均值漂移視覺算法A. 均值漂移分離算法我們將介紹利用不同內(nèi)核對視頻序列中移動(dòng)目標(biāo)實(shí)時(shí)跟蹤的研究結(jié)果。這些內(nèi)核是由Comaniciu和Meer4,5,6第一次應(yīng)用于圖像分離處理，其具有如下特征，底層的、簡單的、魯棒性的以及不同的均值漂移、聚類算法3。對于在無人駕駛車輛上的應(yīng)用，我們首先通過分割及交互式的選擇確定一個(gè)感興趣的目標(biāo)，然后當(dāng)該目標(biāo)在攝像機(jī)視野范圍內(nèi)移動(dòng)時(shí)對其實(shí)施跟蹤。設(shè)計(jì)均值漂移算法是用來尋找數(shù)據(jù)的眾數(shù)（或者說數(shù)據(jù)高度集中區(qū)域的中心），而這些數(shù)據(jù)是由任意維向量表示的。該算法處理過程如下所示7。l 選擇搜索

6、窗口的半徑l 選擇窗口的初始位置（中心點(diǎn)）l 重復(fù)如下步驟計(jì)算整個(gè)窗口數(shù)據(jù)點(diǎn)的均值，然后將窗口中心點(diǎn)平移到該均值點(diǎn)l 直到中心點(diǎn)的平移距離小于預(yù)設(shè)的閥值特征空間中的高密度區(qū)域?qū)?yīng)于在圖像域中色彩/飽和度有限范圍內(nèi)擁有的足夠大數(shù)量的像素。因此，這些像素就形成了連通區(qū)域（這種情況在相對平滑圖像中是很常見的）；該算法本質(zhì)上就是為了找到在對比度/色彩上基本無變化的相對較大的連通區(qū)域（被人們理解并定義的區(qū)域）。事實(shí)上，本算法是這樣進(jìn)行處理的，每一次隨機(jī)地放置一個(gè)搜索窗口，找到相應(yīng)的眾數(shù)，然后將所有特征向量從特征空間移動(dòng)到最終窗口中。因此，人們總是希望能夠快速找到較大區(qū)域。(a) 一個(gè)320×2

7、40的彩色圖像(b) 對應(yīng)的RGB圖像(c) 對應(yīng)的Luv色彩空間圖1 圖像，RGB和Luv之間的關(guān)系在實(shí)現(xiàn)過程中，我們將通常在RGB色彩空間中呈現(xiàn)的像素映射到Luv色彩空間，Luv色彩空間有一個(gè)通過L表示的亮度分量和兩個(gè)通過u和v表示的色度分量。通常認(rèn)為后一個(gè)色彩空間等方性更好，因而更適合用在眾數(shù)尋找算法中。最后，當(dāng)我們定義了一個(gè)可變核，該可變核就會(huì)在顯示跟蹤結(jié)果時(shí)被約束在我們之前提到的矩形窗口中。圖1舉例說明了圖像和特征空間之間的關(guān)系。圖2展示了分別在RGB與Luv空間中的分離結(jié)果。至少主觀上，我們可以看到在這個(gè)實(shí)例中利用Luv參數(shù)化所帶來的提升。通過Hume編程語言將RGB映射到Luv的

8、實(shí)現(xiàn)流程圖如圖3所示。圖4是均值漂移分離算法的流程圖。(a) 在RGB色彩空間中分離結(jié)果(b) 在Luv色彩空間中分離結(jié)果圖2 分離結(jié)果圖3 RGB到Luv的流程圖（Hume）圖4 均值漂移分離算法流程圖（Hume）B. 均值漂移目標(biāo)跟蹤算法在初始幀中，首先針對目標(biāo)區(qū)域定義一個(gè)矩形窗口。然后在Luv色彩空間中運(yùn)用均值漂移算法，將跟蹤目標(biāo)從背景中分離出來。當(dāng)目標(biāo)移動(dòng)時(shí)，利用獨(dú)特的倒角距離變換加權(quán)內(nèi)核來提升目標(biāo)表示和定位的精度，同時(shí)利用Bhattacharyya系數(shù)使兩個(gè)顏色分布之間的距離最小化。在通過彩色圖像序列跟蹤目標(biāo)的過程中，假設(shè)我們能夠利用色彩空間中某一區(qū)域的樣本離散分布將目標(biāo)表示出來，并

9、利用一個(gè)能夠確定當(dāng)前位置的內(nèi)核進(jìn)行定位。因此，我們就要找到函數(shù)分布中的最大值。該函數(shù)是相對于之前的模版圖像，在候選圖像中目標(biāo)位置（漂移）的函數(shù)，用來計(jì)算加權(quán)色彩分布之間的相似度。而Bhattacharyya系數(shù)8是重疊數(shù)量的估算值。如果能夠得到相對密度p(x)和q( x)的兩組參數(shù)，則Bhattacharyya系數(shù)定義如下： （1）因此，我們在處理從彩色圖像中得到的離散采樣數(shù)據(jù)時(shí)，我們就使用在模版和候選圖像中應(yīng)用以m進(jìn)制直方圖存放的離散密度。模版圖像的離散密度定義如下： （2）同樣地，在隨后幀中的給定位置y處，候選圖像的預(yù)估直方圖是： （3）根據(jù)方程（1）的定義，Bhattacharyya系數(shù)

10、的樣本估計(jì)定義如下： （4）由色彩密度函數(shù)得到一組獨(dú)立的隨機(jī)樣本。如果K是標(biāo)準(zhǔn)的內(nèi)核函數(shù)，那么內(nèi)核密度估計(jì)由下式給出： （5）用這種方式估算色彩密度時(shí)，那么均值漂移算法就用來在目標(biāo)幀中不斷移動(dòng)位置y，以此來尋找Bhattacharyya系數(shù)分布的眾數(shù)（方程4）。圍繞()展開泰勒級數(shù)，則Bhattacharyya近似為8： （6）其中 （7）當(dāng)方程（6）的第一項(xiàng)獨(dú)立于y時(shí)，方程（6）的第二項(xiàng)取得最大值，則方程（4）取最大值。在均值漂移算法中，內(nèi)核不斷地從當(dāng)前位置移動(dòng)到新位置，到的關(guān)系如下： （8）其中，G是K的梯度函數(shù)。這等價(jià)于基于色彩直方圖的內(nèi)核過濾相似度函數(shù)梯度的階躍上升。圖5是均值漂移目標(biāo)

11、跟蹤算法的流程圖。圖5 均值漂移目標(biāo)跟蹤算法流程圖（Hume）III. 在無人駕駛車輛測試平臺(tái)上應(yīng)用跟蹤算法我們的硬件測試平臺(tái)由先驅(qū)者P3-AT全地形機(jī)器人組成，即SEBO（SEAS機(jī)器人，圖6）。我們?yōu)镾EBO配置了前陣聲納光盤，無線以太網(wǎng)，前后安全保險(xiǎn)杠以及一個(gè)安裝在表面用來收集均值漂移視覺算法數(shù)據(jù)的攝像頭。我們通過如下的標(biāo)準(zhǔn)軟件連接到先驅(qū)者機(jī)器人從而實(shí)現(xiàn)Hume程序應(yīng)用：ARIA（先進(jìn)機(jī)器人應(yīng)用程序接口）。該軟件是一個(gè)連接機(jī)器人微控制器的開源開發(fā)環(huán)境，并且提供了基本的馬達(dá)和攝像功能接口；VisLib是一個(gè)基于C語言的開源視覺處理程序庫，它提供了基本的圖像處理能力。圖6 SEBO - th

12、e Heriot-Watt/St Andrews 先鋒機(jī)器人P3-ATA. 軟件體系結(jié)構(gòu)圖7展示了在測試平臺(tái)上實(shí)現(xiàn)的軟件結(jié)構(gòu)。在機(jī)器人上實(shí)線箭頭代表本地套接字通信而虛擬箭頭表示無線套接字通信。除了在筆記本電腦上運(yùn)行的Java GUI以外，所有的代碼都是存儲(chǔ)于機(jī)器人上的。位于機(jī)器人上的圖像處理程序?qū)C(jī)器人攝像機(jī)捕獲的實(shí)時(shí)圖像以Hume語言方式記錄，然后通過無線方式發(fā)送到筆記本電腦，并在其中實(shí)時(shí)的顯示出來。每個(gè)圖像的紅色，藍(lán)色和綠色分量都能被捕獲到。由于其中被捕獲的圖像大小是240×320，因此要求有一個(gè)尺寸為3×240×320的存儲(chǔ)結(jié)構(gòu)。圖7 機(jī)器人測試平臺(tái)結(jié)構(gòu)圖8

13、 接口界面的截圖我們已經(jīng)在筆記本電腦上實(shí)現(xiàn)了一個(gè)簡單命令的接口。當(dāng)用戶決定移動(dòng)機(jī)器人時(shí)，電腦會(huì)發(fā)送一個(gè)無線信號(hào)到位于機(jī)器人上的Hume程序中。然后Hume程序與一個(gè)C+ ARIA程序通信，該程序把基本的電機(jī)命令發(fā)送到機(jī)器人。以類似控制機(jī)器人的方式控制攝像頭。圖7展示了當(dāng)用戶選擇控制相機(jī)時(shí)，控制信號(hào)就通過無線從筆記本電腦發(fā)送到機(jī)器人上的Hume程序中。然后，Hume程序就會(huì)與C+ ARIA程序通信，并讓其發(fā)送相機(jī)的控制命令。圖8左上部分顯示的是相機(jī)面板，用于控制相機(jī)的搖攝，傾斜和變焦功能。這里提供了兩套相機(jī)控制。第一組允許設(shè)定相機(jī)的最小運(yùn)動(dòng)或?qū)咕嘀?，而第二組允許設(shè)定相機(jī)的最大運(yùn)動(dòng)或?qū)怪?。B.

14、 結(jié)合視覺算法圖7中有星號(hào)標(biāo)記的Hume方框圖可以先后被替換為：1. LUV轉(zhuǎn)換算法；2. 均值漂移分離算法；3. 均值漂移目標(biāo)跟蹤算法。這些算法產(chǎn)生不同的圖像效果。從最初的實(shí)驗(yàn)中，每一個(gè)算法都可以作為測試平臺(tái)結(jié)構(gòu)的一部分，并通過簡單地更換Hume盒，將圖像從相機(jī)傳到Java界面上。這項(xiàng)工作的開始就要明確各算法間的依賴關(guān)系并在需要處建立有效的鏈接點(diǎn)。對于LUV的轉(zhuǎn)換算法，圖像被呈現(xiàn)在LUV色彩空間中。對于均值漂移分離算法，實(shí)驗(yàn)中使用多種類型和尺寸的圖像。通常情況下該算法是處理尺寸為240×320的圖像。均值漂移目標(biāo)跟蹤算法的最初工作出現(xiàn)了令人欣喜的結(jié)果。對于一個(gè)放置在相機(jī)焦點(diǎn)上的目標(biāo)

15、，當(dāng)機(jī)器人或相機(jī)以穩(wěn)定的速度移動(dòng)時(shí)，可以在屏幕上實(shí)時(shí)的跟蹤目標(biāo)。當(dāng)前的工作是引入這樣一個(gè)選項(xiàng)，它允許用戶在界面屏幕上圈出感興趣的目標(biāo)，將其突出出來。該對象的坐標(biāo)，即在屏幕上的位置，就被傳送到均值漂移跟蹤算法。這樣一來，如果目標(biāo)移動(dòng)，機(jī)器人也跟著移動(dòng)；或者機(jī)器人上的相機(jī)跟著移動(dòng)，然后使用在2.2節(jié)中討論的算法對該目標(biāo)進(jìn)行跟蹤。這些是可以在界面上觀察到的。C. 實(shí)現(xiàn)與實(shí)驗(yàn)評價(jià)圖9展示了跟蹤對象的第一幀圖和前景圖像。在這種情況下，當(dāng)目標(biāo)具有相對統(tǒng)一的亮度時(shí)，一個(gè)簡單的區(qū)域同質(zhì)標(biāo)準(zhǔn)就會(huì)被采用。圖10展示了使用NCDT內(nèi)核跟蹤一名男路人的部分結(jié)果。圖9 分離出的矩形窗口圖10 使用NCDT內(nèi)核跟蹤一名男

16、路人的部分結(jié)果D. 機(jī)器人平臺(tái)目前，圖7中展示的機(jī)器人平臺(tái)已被用來作為在Hume語言中開發(fā)的視覺算法的部署體系結(jié)構(gòu)。這些算法的使用是Hume的實(shí)現(xiàn)工作以及Hume可以和其他行業(yè)標(biāo)準(zhǔn)語言，例如C,C+,Java相結(jié)合的概念上的證明。在第二節(jié)中探討的這三種算法，可以對安裝在機(jī)器人表面上的相機(jī)捕獲的圖像進(jìn)行實(shí)時(shí)處理。機(jī)器人平臺(tái)可能的擴(kuò)展將涉及到的Hume代碼的各個(gè)部分，這些代碼與機(jī)器人的API相連接。我們通過做這些內(nèi)容，以個(gè)別方案為基礎(chǔ)來獲得一系列的性能分析?；蛘?，我們將圖7中展示的三種Hume程序結(jié)合起來。通過程序的執(zhí)行我們可以對其進(jìn)行性能分析，當(dāng)Java接口發(fā)出機(jī)器人或相機(jī)的移動(dòng)請求時(shí)，我們也可

17、以評估程序的反應(yīng)速率。均值漂移跟蹤算法的一系列實(shí)驗(yàn)將繼續(xù)進(jìn)行下去。這些實(shí)驗(yàn)涉及到不同大小，顏色，不同的背景顏色和形狀的跟蹤對象。IV. 相關(guān)工作在很多應(yīng)用領(lǐng)域都有關(guān)于實(shí)時(shí)跟蹤算法的應(yīng)用。通過實(shí)時(shí)獲取圖像，并進(jìn)行圖像分割，我們可以將圖像分為幾個(gè)不同的區(qū)域。然后，我們可以利用這個(gè)信息來跟蹤突出顯示的對象。在這個(gè)處理過程中，這些算法是采用FPGAs(現(xiàn)場可編程門陣列)而不是微處理器來實(shí)現(xiàn)。這是利用現(xiàn)場可編程門陣列的計(jì)算性和并行處理的優(yōu)勢。然而，在10中討論到的算法需要用到清晰可見的熒光標(biāo)記，在本文中討論到的均值漂移算法則不需要這種標(biāo)記。我們最初的實(shí)驗(yàn)已經(jīng)證明兩個(gè)僅在一些小地方有顏色差異的相似物體也可

18、以被識(shí)別出來。在嵌入式實(shí)時(shí)應(yīng)用程序中，獲得精確的時(shí)間和空間使用率邊界是非常有價(jià)值的11,12。如果我們能夠預(yù)測系統(tǒng)如何運(yùn)行，我們就可以為一個(gè)程序周期的期望執(zhí)行時(shí)間設(shè)定上界。使用Hume編程語言，就可以做到這些。Hume編程語言設(shè)計(jì)的關(guān)鍵是它的可計(jì)算的功能。為了提供這些計(jì)算結(jié)構(gòu)，Hume編程語言開發(fā)了一系列的重疊語言子集13。在每個(gè)重疊子集中都增加了語言的可表達(dá)性。通過選擇合適 的語言等級，程序員可以在語言的表現(xiàn)性和需要的計(jì)算等級中得到平衡。因此，我們可以確定所需要的時(shí)間和空間上界這就使我們可以確定所需要的硬件數(shù)量。在本文中提到的關(guān)于FPGAs的休姆算法的部署正是我們所感興趣的。然后我們可以利用

19、Hume編程語言的計(jì)算結(jié)果與微處理器中獲得的計(jì)算結(jié)果相比較。V. 結(jié)論及展望本文中我們探索了使用變量核來提高均值漂移分割算法。實(shí)驗(yàn)結(jié)果表明，和利用標(biāo)準(zhǔn)內(nèi)核程序計(jì)算結(jié)果相比較，已經(jīng)完成的均值漂移物體跟蹤算法在跟蹤能力和通用性上有所提高。這些算法包含在用于證明他們效率的機(jī)器人測試架構(gòu)中。每一種算法都是用Hume算法研發(fā)的。通過實(shí)時(shí)圖像的處理和機(jī)器人的無線通信，可以在復(fù)雜混亂的背景下追蹤移動(dòng)物體。目前進(jìn)行中的工作是通過以下幾項(xiàng)來擴(kuò)展試驗(yàn)平臺(tái)：1、 為無人駕駛車輛研發(fā)新圖像的處理算法；2、 通過增加一條線性后續(xù)算法來補(bǔ)充動(dòng)態(tài)跟蹤算法。這些將包括用于控制機(jī)器人和相機(jī)移動(dòng)的擴(kuò)展接口，這些擴(kuò)展功能還需要進(jìn)一

20、步的論證：1、 Hume編程語言如何用于研發(fā)執(zhí)行實(shí)時(shí)處理的算法；2、 測試平臺(tái)的靈活性；3、 跟蹤算法的準(zhǔn)確性。致 謝本論文中研究的工作是由英國國防部國防科學(xué)技術(shù)中心成立的系統(tǒng)工程自治系統(tǒng)（SEAS）資助的。這里要特別感謝我們在歐盟FP6 EmBounded工程中的合作伙伴：Christian Ferdinand、Reinhold Heckmann、Hans-Wolfgang Loidl、Robert Pointon和Steffen Jost。參 考 文 獻(xiàn)1 K. Hammond and G. Michaelson, “The Hume Report, Version 0.3”, 20062

21、 K. Hammond and G. Michaelson, “Hume: a Domain-Specific Language for Real-Time Embedded Systems”, Proc. of Int. Conf. on Generative Programming and Component Engineering, Erfurt, Germany, Sept. 2003, Springer-Verlag Lecture Notes in Comp. Sci., pp. 37-56.3 Y. Z. Cheng, “Mean shift, model seeking, an

22、d clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(8): 790 -799, 1995.4 Comaniciu, P. Meer, “Robust analysis of feature space: Color image segmentation,” In IEEE Conf. Computer vision and Pattern Recognition, 750 755, 1997.5 Comaniciu and P. Meer, “Mean shift: A robust

23、 approach toward feature space analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5), 603-619, 2002.6 Comaniciu, V. Ramesh, P. Meer, “Kernel-based object tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(5), pp564-575, 2003.7 Y. Keselman and E.

24、Micheli-Tzanakou, “Extraction and characterization of regions of interest in biomedical images,” In Proceeding of IEEE International conference on Information Technology Application in Biomedicine (ITAB 98), 87-90, 1998.8 Bhattacharyya, “On a measure of divergence between two statistical populations defined by their probability distributions,” Bulletin of the Calcutta Mathematics Society, 35, pp99-110, 1943.9 MobileRobots Inc., “Pioneer 3 Operations Manual with MobileRobots Exclusive Advanced Control & Operations Software”, MobileRob