基于CUDA加速的TLD算法實現(xiàn)

張旭標，盧 迪，林尤添，梁金偉

(哈爾濱理工大學電氣與電子工程學院，哈爾濱 150000)

0 引言

目標跟蹤在導航制導、醫(yī)學診斷、智能監(jiān)控等領域有著廣泛的應用，目標跟蹤算法［14］通常面臨著光照變化、外觀變形、背景相似干擾、快速移動和運動模糊等［5-7］幾大難點。Kass等人提出的主動輪廓模型 (Snake模型)［8］不僅考慮圖像的灰度信息，而且考慮了整體輪廓的幾何信息，跟蹤可靠性更強，但是Snake模型計算量較大且對于形變較大或快速移動的物體跟蹤效果不夠理想;Yizong Cheng改善的均值漂移算法 (Meanshift算法)［9］利用了梯度優(yōu)化方法實現(xiàn)快速目標定位，對目標的變形、旋轉等運動有較好的適用性，但在跟蹤過程中沒有利用目標在空間中的運動方向和運動速度信息，當周圍環(huán)境存在干擾時 (如光線、遮擋 )，容易丟失目標［10］。Zdenek Kalal提出的 TLD算法［11-16］，通過將傳統(tǒng)的跟蹤算法與檢測算法相結合，并通過在線學習機制不斷更新跟蹤模塊的顯著特征點和檢測模塊的目標模型與相關參數(shù)，從而有效的解決目標物體發(fā)生形變、光照變化、尺度變化以及遮擋等問題，使得跟蹤效果魯棒性更好。

本文對傳統(tǒng)的TLD算法進行了嵌入式設備的移植，加入了離線目標模型的初始化操作，并使用CUDA(Compute Unified Device Architecture)并行化編程方式對方差濾波器進行并行計算，縮減了原來的CPU單線程的計算時間;對通過集合分類器的樣本使用聚類算法，將遠離目標的圖像框排除，提高跟蹤魯棒性。在保證跟蹤效果的前提下，減少了資源的占有率，縮短了運行時間。

1 TLD跟蹤算法原理

TLD算法主要由追蹤、檢測和學習3個部分組成，TLD算法的運行流程圖如圖1所示。用第一幀圖像中手動圈定需要跟蹤的目標物體對跟蹤模塊、檢測模塊進行初始化操作，從第二幀圖像開始，跟蹤－檢測－學習3個模塊互相補充，不斷的對錯誤進行評估，從而實現(xiàn)目標在發(fā)生形變或被遮擋的情況下仍然能準確追蹤的效果。

跟蹤模塊采用中值流跟蹤法 (Median Flow)，該算法本質上是基于前后誤差估計 (forward－backward error)的金字塔LK光流法。其基本原理為:在上一幀的目標框中選擇若干個像素點作為特征點，利用金字塔LK光流法在下一幀中尋找上一幀的特征點在當前幀中的對應位置，然后將這若干個特征點在相鄰兩幀之間的位移變換進行排序，得到位移變化的中值，將小于中值的50%的特征點作為下一幀的特征點，并依次進行下去，從而實現(xiàn)動態(tài)更新特征點的目的。跟蹤器是用于跟蹤連續(xù)幀間的運動，只有在物體始終可見時跟蹤器才會有效，跟蹤器根據(jù)物體在前一幀已知的位置估計在當前幀的位置，同時在估計過程中產生一條目標運動的軌跡作為學習模塊的正樣本。

圖1 TLD算法流程圖

檢測模塊是將方差濾波器、集合分類器以及最近鄰分類器級聯(lián)。方差濾波器是計算圖像片像素灰度值的方差，將方差小于原始圖像片方差一半的樣本標記為負;集合分類器是利用隨機森林的形式，對圖像片中任意選取的兩點進行亮度值的比較，若A點的亮度大于B點的亮度，則特征值記為1，否則記為0，每選擇一對新位置，就是一個新的特征值，隨機森林的每個節(jié)點就是對一對像素點的比較。最近鄰分類器是通過設定閾值對新樣本進行相對相似度的計算，大于設定的閾值則認為是正樣本。通過對每一幀的圖像進行全面掃描，找到與目標物體相似的所有外觀的位置，從檢測產生的結果中生成正樣本和負樣本，傳到學習模塊。

學習模塊采用一種半監(jiān)督的機器學習算法P－N學習(P－N Learning)，根據(jù)追蹤模塊和檢測模塊產生的正負樣本，使用P專家 (P－expert)檢出漏檢 (正樣本誤分為負樣本)的正樣本，使用N專家 (N－expert)改正誤檢 (負樣本誤分為正樣本)的正樣本。由于每一幀圖像內物體最多只可能出現(xiàn)在一個位置，且相鄰幀間物體的運動是連續(xù)的，所以連續(xù)幀的位置可以構成一條較平滑的軌跡。P專家的作用是尋找數(shù)據(jù)在時間上的結構性，它利用追蹤器的結果預測物體在t+1幀的位置。如果這個位置 (包圍框)被檢測器分類為負，P專家就把這個位置改為正。也就是說P專家要保證物體在連續(xù)幀上出現(xiàn)的位置可以構成連續(xù)的軌跡;N專家的作用是尋找數(shù)據(jù)在空間上的結構性，它把檢測器產生的和P專家產生的所有正樣本進行比較，選擇出一個最可信的位置，保證物體最多只出現(xiàn)在一個位置上，把這個位置作為TLD算法的追蹤結果。同時這個位置也用來重新初始化追蹤器。

2 基于CUDA加速的TLD改進算法

將圖1所示的TLD算法移植至嵌入式設備時，由于其串行運算特點，運算時間較長，不能滿足跟蹤系統(tǒng)的實時性要求。而目前隨著GPU發(fā)展的越來越強大，其計算能力已經超越了通用的CPU，將CPU與GPU并用，進行協(xié)同處理，是計算行業(yè)發(fā)展大趨勢，基于此NVIDIA發(fā)明CUDA運算平臺。本文利用CUDA運算平臺，采用多線程方式計算大量數(shù)據(jù)，縮短運算時間，以滿足嵌入式設備運動目標跟蹤系統(tǒng)的實時性要求。此外，本文在初始化操作中加入了離線目標模型模塊，增強了TLD算法目標跟蹤的自適應性能;采用基于K均值的聚類算法對經過集合分類器后的樣本數(shù)據(jù)進行了聚類，降低最近鄰分類器的閾值，從而提高檢測率，最后將跟蹤目標傳輸?shù)紺/S服務器的上位機端進行顯示?；贑UDA加速的TLD算法框圖如圖2所示，其中虛線部分即為改進部分。

圖2 基于CUDA平臺的TLD算法框圖

2.1 離線目標模型的初始化

圖1所示TLD算法在每次啟動時都需要手動選取跟蹤目標，本文在此基礎上加入離線目標模型的初始化操作過程。對于已圈定的跟蹤目標，在第一次啟動系統(tǒng)時進行目標的選取操作后，將目標模型進行保存，下次啟動系統(tǒng)時，只需讀入目標模型即可實現(xiàn)對跟蹤模塊和檢測模塊的初始化，增強了TLD算法的自適應性能。

2.2 CUDA平臺下方差濾波器算法

在TLD算法中，檢測模塊功能是在視頻當前幀中定位與目標模型匹配的目標圖像，因此要構建掃描窗口掃描當前幀圖像，并判斷當前掃描窗口內是否存在目標圖像。對圖像使用不同尺寸的掃描窗 (scanning grid)進行逐行掃描時，就會在每一個位置產生一個包圍框 (bounding box)，包圍框中確定出的圖像區(qū)域即為圖像片 (patch)，所有圖像片的集合進入到學習部分就成為了一個樣本。經過掃描窗口產生的樣本是無標簽的樣本，需要使用分類器對無標簽的樣本進行分類，從而確定其標簽。

假設視頻的分辨率為m×n，步長為k個像素，尺度縮放系數(shù)為l，則掃描過程中會產生m×n×l/k個圖像片。圖1所示TLD算法中采用的步長為10像素、尺度縮放系數(shù)有21種的掃描窗口策略，需要計算每一個掃描窗口與輸入目標的重疊度，由此帶來了大量的樣本數(shù)據(jù)進行同樣的計算。由于采用CPU單線程依次計算，勢必導致了大量的時間損耗。

采用NVIDIA推出的CUDA運算平臺，運用多線程方式計算大量的樣本數(shù)據(jù)，具體步驟如下:

1)設置視頻分辨率為240×180，選用尺度縮放系數(shù)有{0.16151f， 0.19381f， 0.23257f， 0.27908f， 0.33490f，0.40188f，0.48225f，0.57870f，0.69444f，0.83333f，1.0f，1.20000f， 1.44000f， 1.72800f， 2.07360f， 2.48832f，2.98598f，3.58318f，4.29982f，5.15978f，6.19174f} 共 21種，步長為10像素。則產生240×180×21÷10=90720個圖像，記為N;

2)在CPU端計算幀圖像積分以及幀圖像平方的積分，分別記為I和II;

3)GPU每一個線程塊中設置256個線程，則線程網(wǎng)絡中產生 (N+255)/256個線程塊;

4)將圖像片數(shù)據(jù)量N、閾值T、幀圖像積分I、幀圖像平方的積分II傳入GPU顯存中;

5)調用核函數(shù)，每一個線程塊下的每一個線程計算一個圖像片的方差，并與閾值進行比較。大于閾值的是正樣本，相應的數(shù)組下標的值記為1，小于閾值的是負樣本，相應的數(shù)組下標的值記為0;

6)將顯存中的數(shù)組數(shù)據(jù)從顯存?zhèn)骰氐絻却嬷?，將正負樣本過濾分離，傳入集合分類器。

2.3 集合分類器的聚類

方差濾波器過濾后的圖像片傳入集合分類器中，集合分類器中采用隨機森林計算后驗概率，根據(jù)閾值判定出需要進入最近鄰分類器的正負樣本。隨機森林包含了10棵樹，每棵樹為完全二叉樹，每棵樹都包含13個節(jié)點，每個節(jié)點作為一個特征，每個節(jié)點是一個像素對的比較，每個像素對的采點位置是通過第一幀初始化隨機生成的，并且互相垂直，將13個點的值統(tǒng)計做成一個13位的二進制數(shù)字從而進行后驗概率的統(tǒng)計計算。若該圖像區(qū)域的后驗概率平均值大于設定的閾值，則判定為正樣本，否則判定為負樣本。

在實際情況中，集合分類器所表示的是目標的大概位置，能很好的表示物體的位置，最近鄰分類器利用保守相似度和相關相似度去判斷是否能通過級聯(lián)分類器，從而保證成功獲得目標。為了提高精度，提高識別度，在集合分類器后進行K均值聚類，對通過集合分類器的相關性大的圖像片進行聚合，將遠離目標的圖像片去除，降低最近鄰分類器閾值，在綜合出新的目標圖像片后傳入到最近鄰分類器中進行評估。

具體步驟如下:

1)提取出所有通過集合分類器的每個樣本的中心坐標點;

2)將當前樣本的中心坐標點與其他的樣本中心坐標點做差得到一系列的距離值;

3)對每個樣本求得的所有距離值取平均，作為該樣本的參考值;

4)將參考值由小到大進行排序，取出前1/2的樣本進行聚類，若樣本數(shù)量超過50個，則只取前50個樣本;

5)降低最近鄰分類器的閾值，對新目標進行分類。

2.4 客戶端/服務器的設計

客戶端/服務器 (C/S)部分采用socket網(wǎng)絡編程技術，通過TCP/IP協(xié)議編寫基于P2P模型的客戶端和服務器精靈進程，實時的向指定路徑寫入和讀取數(shù)據(jù)。

在實際情況中，保證系統(tǒng)服務器平臺的魯棒性，系統(tǒng)采用了如下幾種技術細節(jié)保證高效性及擴展性:

1)采用Reactor模式事件處理機制，利用主進程作為監(jiān)聽網(wǎng)絡事件，如果有事件發(fā)生，則通過主進程利用管道技術通知并分發(fā)到各個處理進程。相比于Select的I/O復用技術，為了突破網(wǎng)絡端口的監(jiān)聽上數(shù)量上的限制，采用Epoll模型的邊緣觸發(fā)的ET模式提高系統(tǒng)的魯棒性。

2)在滿足多目標跟蹤的設計下，利用單例模式創(chuàng)建進程池，提高擴張性，單例設計模式保證進程池的唯一性，進程池的維護減少了進程創(chuàng)建和銷毀所帶來的CPU負荷和內存的是使用情況。

3)系統(tǒng)在設計時，利用多進程技術和加權Round Robin算法對子線程的分發(fā)進行處理提高服務器的處理能力，完成了Reactor的主線程與Worker線程均衡分發(fā)，增加了理解性和簡化了調試。Round Robin算法可以有效的解決單進程的任務負載過重時，保證均衡負載。

4)使用管道統(tǒng)一事件源機制保證父子進程信號及信號處理函數(shù)盡可能快的被執(zhí)行完畢，有效的防止服務器的父進程程序的提前退出的情況活宕機而導致產生僵尸進程。利用統(tǒng)一事件源管理機制可以有效的解決該問題。

5)本系統(tǒng)設計了采用高性能定時器，基于時間堆的心跳定時器，在對方心跳超時或者宕機的情況下，則自動殺死該進程，重新啟動，保證了系統(tǒng)正常的運行。對于傳統(tǒng)的降序鏈表定時器，升序鏈表定時器和基于hash的時間輪來說，最小堆定時器在空間上位O(1)，相較于O(N)的hash時間輪的空間復雜度優(yōu)越的多，當系統(tǒng)連接數(shù)很大的時候，最小堆的添加時間復雜度位O(lgn)，相較于升降序鏈表定時器的O(n)時間復雜度要優(yōu)越。對于執(zhí)行效率來說，升序鏈表和最小堆定時器都是O(1)比時間輪定時器要好，為此系統(tǒng)采用最小堆位時間定時器。

6)本系統(tǒng)設計的日志系統(tǒng)，采用4級日志實時輸出系統(tǒng)日志，降低了調試難度，提高了程序的可靠性。

表1 傳統(tǒng)TLD算法與本文優(yōu)化算法各個過程時間對比(ms)

7)為了使不同讀寫格式或不同平臺能互相兼容、保證數(shù)據(jù)傳輸?shù)耐暾?、提高傳輸?shù)臏蚀_性，使用der編碼的方式，對圖像進行der格式的編碼，轉成統(tǒng)一的二進制格式?？蛻舳送ㄟ^讀取到數(shù)據(jù)后進行der編碼傳輸，服務器端接受到數(shù)據(jù)后進行der解碼并顯示。

3 實驗結果

實驗硬件平臺為NVIDIA Jetson TK1嵌入式開發(fā)板，軟件環(huán)境為Ubuntu 14.04.4+opencv 2.4.13+CUDA6.0。服務器端位于局域網(wǎng)內，配置為ubuntu 64位操作系統(tǒng)，intel core i7－4710HQ CPU@2.5 GHz，8 G內存，IP地址為192.168.92.134，網(wǎng)絡環(huán)境如圖3所示。TK1作為客戶端，采用intel7260網(wǎng)卡作為數(shù)據(jù)傳輸媒介，使用傳輸端口為8000，以二進制形式實時的將圖片傳送到服務器端，客戶端網(wǎng)絡環(huán)境如圖4所示。

圖3 服務器端網(wǎng)絡環(huán)境

圖4 客戶端網(wǎng)絡環(huán)境

實驗中選用書本作為跟蹤目標，與傳統(tǒng)TLD算法運行時間 (ms)對比如表1所示，實驗結果表明，本文優(yōu)化的TLD算法在保證了傳統(tǒng)的TLD算法跟蹤效果的情況下，大幅的縮短了時間。

4 結論

本文通過對傳統(tǒng)TLD算法進行分析理解，將其移植到NVIDIA Jetson TK1嵌入式開發(fā)板中，并分別使用CUDA平臺和距離聚類算法對方差分類器和集合分類器進行優(yōu)化。實驗結果表明，相比于傳統(tǒng)的TLD算法，本文的優(yōu)化算法的實時性更強。此外，本文設計了C/S服務器用于遠程監(jiān)控目標跟蹤效果，配合嵌入式開發(fā)板，使得整個系統(tǒng)的應用范圍更加廣泛。