陳家紅

（金陵科技學院計算機工程學院，南京211169）

基于局部背景加權和能量約束的多目標檢測與跟蹤算法

陳家紅

（金陵科技學院計算機工程學院，南京211169）

針對標記點處理方法用于多目標跟蹤時效果不佳的問題，在標記點方法的基礎上，提出一種多目標聯(lián)合檢測跟蹤算法。改進的幀間差法用于目標的初步確定，通過局部背景加權進一步確定其與多個目標的標記?？紤]動態(tài)模型的軌跡一致性問題，對動態(tài)目標、長時間跟蹤和目標互斥相似等問題進行研究。針對非凸性的能量函數(shù)采用可逆跳轉馬爾可夫鏈蒙特卡洛進行優(yōu)化。實驗結果表明，在有高斯噪聲情況下，與其他跟蹤算法相比，該算法的檢測和跟蹤相似度最高，在衛(wèi)星圖像序列和自采集視頻中的精度和召回率也最高，整體性能較優(yōu)。

多目標跟蹤；局部背景加權；能量約束；非凸性；可逆跳轉馬爾可夫鏈蒙特卡洛

1 概述

目標跟蹤在交通、安防、無人機、無線傳感器網(wǎng)絡等領域應用非常廣泛［1-3］，是模式識別、機器視覺等許多交叉學科的熱門研究課題。從某種意義上說，可以將目標跟蹤定義為圖像平面中目標軌跡的評估問題［4］。因此，跟蹤器在圖像序列的不同圖像幀中為目標設置一致標簽，還可以提供目標的運動方向、外形或尺寸信息［5］，在目標跟蹤中用軌跡評估具有重要意義。目標跟蹤按跟蹤目標的數(shù)量，可以分為單目標跟蹤和多目標跟蹤，兩者雖然有相似之處，但多目標要比單目標復雜得多，要考慮的問題多而復雜，如多目標的重疊、相似區(qū)別和排序等問題［6］。本文給出一種多目標跟蹤算法，就動態(tài)目標、長時間跟蹤和目標互斥相似等問題進行研究，提出背景加權和能量約束的多目標跟蹤算法。

2 相關研究

關于目標跟蹤已經(jīng)有很多學者對其進行大量研究，本節(jié)按單目標［7-9］和多目標跟蹤［10-13］進行描述，重要討論利用序列方法［10-11］和標記點方法［12-13］的多目標跟蹤。

文獻［7］針對傳統(tǒng)的Meanshift跟蹤算法在跟蹤時的不穩(wěn)定問題，提出一種改進算法，意圖削弱目標模型中的背景特征對目標跟蹤的影響，即局部背景加權BWH，通過局部背景模型篩選目標與候選模型的顯著特征。文獻［8］的設計思想較好，但實驗效果并不好。文獻［8］用理論和實驗證明了文獻［7］的BWH并沒有起作用，算法最終退化為傳統(tǒng)的Meanshift，并對其進行糾正，提出了CBWH算法，真正實現(xiàn)了文獻［7］期望的效果。但這類算法依然是以Meanshift為基礎，在近似的顏色區(qū)域目標經(jīng)常發(fā)生漂移。

文獻［9］是著名的TLD（Tracking-Learning-Detecting）算法。在目標跟蹤領域中影響非常大，這可能是由于非常好的效果和代碼分享，TLD將跟蹤和檢測同時進行，同時利用N-P專家的學習方法對跟蹤和檢測出現(xiàn)的錯誤樣本和正確樣本同時進行分類，糾正跟蹤和檢測過程中的錯誤，而TLD算法是一種單目標跟蹤，多目標的學習很困難。文獻［9］解決了這個問題，但并未見著于學術，而是見著于他成立的公司中。

文獻［10］是一種改進的多假設跟蹤器（Multi-Hypothesis Tracker，MHT），數(shù)據(jù)校準后進行串行合并和點跡合成。屬于多目標跟蹤領域中常見的技術，該算法的主要缺點在于不能根據(jù)新數(shù)據(jù)修改過去的結果。但是，實時跟蹤并不總是一個不可獲取的約束條件，比如線下視頻處理或信息檢索等應用程序就不存在這些限制條件。文獻［11］提出了MCMC數(shù)據(jù)關聯(lián)方法，利用這種方法可以對一組離散度檢測信號進行分區(qū)用以跟蹤。為了檢索每個分區(qū)，假設目標和檢測是一對一的映射關系。但是，沒有并沒有對其進行細致的研究。

標記點處理方法（Marked Point Processes，MPP）［12］已經(jīng)成功地應用于高分辨率遙感光學圖像以檢測目標，文獻［13］中所提出的模型用以獲取所有未知目標的后驗概率，得出時空信息。因此，這種模型的主要目的在于識別和了解特定事件變化的外力，對能量中的特定因素進行優(yōu)化會使得處理過程相互依賴。

本文提出一種新的MPP算法，該算法適用于多目標跟蹤問題，并且將局部背景加權加入其中用于目標標記，能量約束用于多目標跟蹤。

3 多目標檢測

多目標的檢測是目標跟蹤的重要環(huán)節(jié)，本節(jié)介紹的多目標檢測是由改進的幀間差法進行快速目標確定，用顏色直方圖向量和背景加權對目標進行標記。

3.1 改進的幀間差法目標檢測

通過幀差法［14］找到運動目標的可能位置，不同于一般的幀間差法，只使用相鄰2幀，本文使用前后3幀，三幀差法可以獲得更多的像素間的信息，兩幀差法只考慮第k幀與前一幀或后一幀的關系，只進行一次差分運算，三幀差法考慮前后2幀關系，進行了2次差分運算，三幀差法可以獲得更多像素灰度信息關系，另外三幀差法也適合之后的相位與運算。在運算量方面，如果不考慮后續(xù)操作的不同，三幀差法增加了h×w次減法運算（h，w分別為圖像的高度和寬度）。相位與運算和簡單的閾值二值化進行目標確定。在每個像素位置上，計算隨著時間變化亮度值的平均值，并用pm表示。對于每個視頻幀f，計算f中所有的像素亮度值pf與參考幀之間的差值，以及局部的平均差值pm。最后，僅保留那些差值大于預設定閾值的像素點作為前景：

閾值處理之后進行二值處理，然后確定目標。圖1為改進的幀間差法的流程圖。

圖1 使用幀間差法的目標確定流程

3.2 目標標記

背景在目標定位中起著重要作用，對于2個相似的目標，背景是區(qū)分不同目標的重要手段，經(jīng)驗表明將目標背景信息融入到目標定位中非常必要。在文獻［8］的CBWH算法中，目標局部背景模型的權重計算公式如下：

具體定義可以參考文獻［7-8］，本文并沒有將完整的CBWH算法引入到目標檢測中，只是運用了其中直方圖向量表征及其背景加權以對多目標進行劃分和標記。由于CBWH是BWH的改正版本（CBWH的確用嚴格的理論和實驗證明了BWH的錯誤，不過BWH的背景加權思想一直廣為使用［8］）。而它們均是基于均值漂移的方法，即M eanshift方法，均是基于單目標跟蹤，本文屬于多目標跟蹤，并不是基于Meanshift，只是將CBWH的背景加權運用于多目標標記，突出背景的因素。

4 多目標跟蹤

使用能量約束進行增強跟蹤的條件約束，這些約束條件來自于實際場景中的目標約束。

4.1 動態(tài)模型

跟蹤的定義屬性（與每幀中進行獨立的檢測相反）即為：在大多數(shù)情況下目標軌跡是平滑的，運動模型表示為dgn，本文創(chuàng)建一個能量項激勵目標遵循給定的運動模型，其約束為一個目標u在時刻k存在的情況，約束情況可以改寫為：

其中，dyn0表示閾值，這個閾值描述目標偏離運動模型的程度，且目標仍然可以獲取。

能量項遵循動態(tài)模型，即所有目標的總和：

這一項有助于目標的創(chuàng)建，目標檢測過程受到削弱，但是動態(tài)模型增強了目標的存在性。

4.2 標簽一致性問題

為了對不同軌跡進行區(qū)分，在每個目標上標記一個標簽。標簽用3.2節(jié)的方法進行標注，可以看成是一個軌跡的鑒別符號，不同的標簽表示不同的軌跡。因此，在數(shù)據(jù)集合中標簽的數(shù)量與軌跡的數(shù)量要保持接近。理想情況下，大量的目標u分散在整個圖像序列中，目標的數(shù)量應該遠小于標簽的數(shù)量。本文利用labels（X）=Uu∈Xl（u）表示在配置X中所構建的標簽集合，其中l(wèi)（u）表示目標u的標簽。

其中，|labels（X）|表示集合的基數(shù)。

根據(jù)運動模型設計所用的標簽，給定的目標u集中在位置pos（u）=（ch（u），cw（u）），本文在相鄰幀上尋找目標，相鄰幀之間的關系滿足運動模型。計算目標u與其他目標之間的距離，并將計算獲取的距離與距離閾值進行比較，如果計算獲取的距離小于閾值，那么將目標u的標簽設置為先前圖像幀中目標的標簽；否則，為目標u分配一個新的大小在［0，L］/labels（Xt）。配置X中在任何實際運行時刻t都不允許含有2個或更多個具有相同標簽的目標，這意味著分配給這些配置無限的能量。

4.3 目標互斥及能量公式

當檢測和跟蹤目標時，難點是在一幅給定的圖像幀中處理目標碰撞和重疊。在本文模型中，如果配置中含有的目標發(fā)生重疊的部分超過給定的范圍，那么將這樣的配置概率置為0。目標u和v之間的重疊區(qū)域的表示如下：

針對重疊的能量項為：

跟蹤階段的能量公式為：

圖2直觀地展現(xiàn)了每個能量項如何影響輸出的結果，上一行顯示了每個獨立項含有較高能量值的配置，下一行顯示了每個獨立項含有較低能量值的配置。黑色的點表示在不同時間幀目標的位置。目標上不同的顏色表示分配到不同標簽。

圖2 能量項不同組成成分的影響

4.4 能量公式的優(yōu)化

圖3 目標時空卷的雙錐擴展

本文利用模擬退火尋找能量函數(shù)中的極小值。式（1）中的概率密度函數(shù)可以改寫為：

其中，Tempi表示溫度參數(shù)，當i趨于無窮時Tempi趨于0。如果Tempi減少對數(shù)率，那么Xi趨向于fθ，i的全局最優(yōu)。

對式（10）的求解一般采用幾何法迭代法，通過設計恰當?shù)母蓴_內核來減少計算量。本文采用了如下的干擾內核，即出生和死亡依賴于出生圖：在預處理階段創(chuàng)建2種類型的圖：

（1）出生圖：由于目標具有的輻射值應該大于背景，因此本文利用一個簡單的閾值技術在每幀圖像上確定目標可能的位置，并分配給這些位置較高的內核概率；

（2）水編碼：在對船只進行跟蹤時，首先檢測水區(qū)域，然后在水區(qū)域內進一步搜索?？梢愿鶕?jù)水區(qū)域特性的特征提取出水區(qū)域，具有低輻射值、整個區(qū)域方差較小以及相對較大的尺寸。

根據(jù)一個出生圖內核確定出生和死亡，出生圖內核首先選取概率pb和pd=1-pb，pb和pd=1-pb分別表示目標u添加（出生）到配置和從配置中刪除（死亡）的概率。如果選取出生，那么內核根據(jù)出生圖生成一個新的目標u，并且可知X′=X∪u。如果選取死亡，那么內核根據(jù)出生圖在X中選取一個目標u，可知X′=Xu。將模擬退火方案中嵌入RJMCMC采樣器可以獲取更好的結果，但是計算量的減少比較輕微。在幾次實驗中，30 000次抽樣，前5 000次左右用于“退火”，MCMC采樣20 000多次達到穩(wěn)定。

5 實驗結果和分析

仿真實驗在W in7操作系統(tǒng)，Intel酷睿雙核，2.95 GHz，4 GB RAM，所用平臺為Matlab2011b。

5.1 對比距離測度

對比距離測度用于不同方法檢測跟蹤目標的匹配程度，當感興趣的目標在黑色背景中以明亮的形式出現(xiàn)，需要計算物體內部及其邊界間的對比距離測度。文獻［16］對對比距離測度進行介紹，其定義如下：

質量函數(shù)給較好放置的橢圓（即目標u的dB（u，F(xiàn)ρ（u）））一個大于閾值d0（Y）的負值，否則分配給一個正值。

5.2 合成圖像實驗

首先在3個合成生物圖像序列上對本文提出的方法進行測試。文獻［13］中已經(jīng)生成了圖像序列，圖像序列由25幅尺寸為256×256像素的圖像組成，在每幀圖像上存在近乎20個目標，3個圖像序列上含有不同級別的高斯噪聲。圖4給出了跟蹤結果，采用的目標運動模型是布朗運動模型。

圖4 合成生物圖像序列的實驗結果

圖4 （a）表示在第1個圖像序列（無噪聲）上的跟蹤結果。圖4（b）表示在第1個圖像序列（高斯噪聲，μ=25，ρ=2.5）上的跟蹤實驗結果。圖4（c）表示在第1個圖像序列（高斯噪聲μ=50，ρ=5.0）上的跟蹤結果。將本文方法與粒子跟蹤進行比較，表1是在3個合成圖像序列上對文獻［13］中的多目標跟蹤器所獲取的實驗結果和本文提出的算法所獲取的實驗結果進行比較，根據(jù)最大距離為5個像素點計算2種方法配對的檢測和跟蹤間的相似性。這意味著如果利用文獻［13］在位置c1檢測出的目標與本文提出的方法在位置c2處檢測的目標相同，并且此時c1與c2的對比距離測度|c1-c2|≥5，那么2個檢測不匹配。

表1 3個合成圖像序列上的實驗結果比較

每個序列的計算時間在50 s左右。雖然與目前最先進的方法相比，本文算法性能有所減弱，但是運算時采用串行運算，如果利用并行計算策略可以大幅提高本文算法的性能。

5.3 衛(wèi)星圖像實驗

本文主要的目標是運用本文提出的算法處理真實的數(shù)據(jù)，利用高分辨率衛(wèi)星圖像進行目標跟蹤是遙感領域中的一個新應用［17］。在2個含有船只的圖像序列上對本文算法進行測試，每個圖像序列由低時間頻率情況下拍攝的16幅圖像組成，由于圖像拍攝的角度變化，目標的外形也發(fā)生了大幅度的變化。本文將3種跟蹤器實驗結果進行比較：文獻［12］的MPP，文獻［13］的Icy和經(jīng)典的卡爾曼跟蹤器。

5.3.1 度量

由于許多因素的影響，對不同跟蹤算法進行一個客觀的比較十分困難：（1）單個跟蹤識別的重要性與應用相關；（2）將跟蹤器的輸出分為正確和不正確十分困難，這通常需要額外的參數(shù)去評估跟蹤器的正確性和精度。

為了對多目標跟蹤的精度進行評估，計算了3種類型的錯誤：假陽性（FP），假陰性（FN）和身份轉換（ID），3種類型錯誤的權重相同。本文對真陽性（TP）的數(shù)量進行了規(guī)定并且提供了運動目標（TO）總的個數(shù)。運動目標總的個數(shù)（TO）是所有圖像幀中目標的總和，在2個連續(xù)幀上一個運動目標的位置會發(fā)生變化。另外，利用不同軌跡的總數(shù)量計算主要跟蹤（MT）和主要丟失（M L）的分數(shù)，進而測量有多少真實地面軌跡被成功跟蹤（至少跟蹤了80%）或丟失（跟蹤少于20%）（TT）。最后，確定每個算法的精度，定義為：

5.3.2 定量評價

表2顯示了所有圖像序列的定量結果。本文顯示了4個跟蹤器的實驗結果：本文算法（用BW-EC表示），卡爾曼跟蹤器（用K lman表示），MPP和Icy。圖5顯示了本文算法在2個圖像序列上的實驗結果。圖5（a）是第1個圖像序列上的跟蹤過程持續(xù)到第11幅圖像，圖5（b）是第2個圖像序列上的跟蹤過程持續(xù)到第14幀。為了進行比較，在表2中列出了實驗結果的數(shù)據(jù)形式。

表2 2個衛(wèi)星圖像序列的實驗結果

圖5 不同角度拍攝的衛(wèi)星圖像序列

圖5 （a）由大小為1 840×820像素的16幅圖像幀構成，整個圖像幀中含有恒定的8個運動目標。利用目標證據(jù)以更好地評估出目標的位置，利用恒定的距離測度獲取目標尺寸和方向的精確值。此外，在整個圖像序列中對標簽進行了保留。運行時間為48 s。圖5（b）是由尺寸為830×730像素的16幅圖像構成，在區(qū)分動態(tài)目標和靜態(tài)目標時，本文的模型與經(jīng)典跟蹤器［12-13］相比顯現(xiàn)出了更高的跟蹤性能，這是由于本文模型獲取了更好的檢測結果，保持整個圖像序列中的所有標簽。

本文算法BW-EC的性能超過卡爾曼跟蹤器，卡爾曼跟蹤器性能比較低，而且需要對時間進行初始化。目標的外形在整個圖像序列中都在發(fā)生變化，因此，跟蹤器的精度受到較大影響。本文的跟蹤器僅受到目標和目標邊界間對比度的影響。因此，外形的改變不會影響本文算法的有效性。

5.4 自采集視頻實驗

為了更好地說明本文算法的效果，筆者自行采集一段視頻進行實驗。圖6和圖7是一段交通視頻跟蹤的效果圖。

圖6 目標車輛的初始化

圖7 車輛跟蹤結果

圖6 是初始化的目標車輛，圖7是目標出現(xiàn)跟蹤和檢測的結果?？梢钥闯?，即使類似目標出現(xiàn)也沒有丟失目標或者發(fā)生擾亂，車運動軌跡也被成功標出。

表3為這段交通視頻的實驗結果，從精度和召回率看，本文算法優(yōu)于其他算法。

表3 交通視頻實驗結果

6 結束語

本文提出一種利用局部背景加權和能量約束的多目標檢測和跟蹤算法，背景加權用于檢測和標記。本文重點定義了一個新的直觀能量約束模型，利用這個能量可以檢測出圖像序列中所有的目標并將其分成不同的軌跡。另外，采用著名的RJMCMC采樣器對能量模型進行最優(yōu)化，最后在3種不同圖像序列或視頻上證明了本文算法的有效性。

下一步將就以下2個方向進行研究：（1）模型對于噪聲和并行執(zhí)行的奇異值魯棒性分析。（2）設計一個并行執(zhí)行的RJMCMC采樣器，這種執(zhí)行方式將會顯著減少采樣器的計算時間。

［1］ 丁業(yè)兵，趙 峰，郝詩海.多特征帶寬自適應Mean Shift目標跟蹤算法［J］.計算機工程，2013，39（2）：197-201.

［2］ 史志剛.視頻序列中運動目標檢測與跟蹤技術研究［D］.西安：西安電子科技大學，2014.

［3］ 劉淑英.無線傳感器網(wǎng)絡中改進的多目標定位和跟蹤算法［J］.計算機工程，2015，41（4）：7-13.

［4］ 柳培忠，阮曉虎，田 震，等.一種基于多特征融合的視頻目標跟蹤方法［J］.智能系統(tǒng)學報，2014，17（3）：1-6.

［5］ M u?icki D，Song Taek-Lyul，Lee H H，et al.Correlated Doppler-assisted Target Tracking in Clutter［J］.IET Radar Sonar&Navigation，2013，7（1）：94-100.

［6］ 才 盛.多目標監(jiān)控場景下的檢測和跟蹤技術研究［D］.廈門：廈門大學，2014.

［7］ Comanciu D，Visvanathan R，Meer P.Kernel-based Object Tracking［J］.IEEE Transactions on Pattern Analysis&Machine Intelligence，2003，40（5）：564-575.

［8］ Ning Jifeng，Zhang Lei，Zhang David，et al.Robust Meanshift Tracking with Corrected Background-weighted Histogram［J］.IET Computer Vision，2012，6（1）：62-69.

［9］ Kalal Z，Mikolajczyk K，Matas J.Tracking-learningdetection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（7）：1409-1422.

［10］ 李世忠，王國宏，白 晶，等.壓制干擾下雷達網(wǎng)點目標概率多假設跟蹤算法［J］.西安交通大學學報，2012，46（10）：101-106.

［11］ Oh S，Russell S，Sastry S.Markov Chain Monte Carlo Data Association for General Multiple-target Tracking Problems［C］//Proceedings of IEEE Conference on Decision &Control.Washington D.C.，USA：IEEE Press，2005：735-742.

［12］ van Lieshout M N M.Markov Point Processes and Their Applications［M］.London，UK：Imperial College Press，2000.

［13］ Dallongeville S，Chenouard N，HervéN.Icy：An Open Bioimage Informatics Platform for Extended Reproducible Research［J］.Nature Methods，2012，9（7）：690-696.

［14］ 彭 爽，蔣榮欣.面向高清視頻監(jiān)控系統(tǒng)的實時運動檢測算法［J］.計算機工程，2014，40（11）：288-291.

［15］ 金美娜，趙擁軍，蓋江偉.一種基于混合RJMCMC方法的寬帶信號DOA估計方法［J］.電子與信息學報，2010，32（2）：504-508.

［16］ 夏建濤，何明一.基于Bhattacharyya距離準則的核空間特征提取算法［J］.計算機學報，2004，27（5）：683-689.

［17］ 湯亞波，徐守時.基于D-S證據(jù)理論的多源遙感圖像目標數(shù)據(jù)聯(lián)合關聯(lián)算法［J］.中國科學技術大學學報，2006，36（5）：466-471.

編輯 顧逸斐

Multi-target Detection and Tracking Algorithm Based on Local Background Weighting and Energy Constraint

CHEN Jiahong
（School of Computing Engineering，Jinling Institute of Technology，Nanjing 211169，China）

As the performance of multi-target tracking based on Marked Point Process（MPP）is poor，a hybrid multitarget detection and tracking is proposed.The improved frame difference method is used to determine the preliminary of the target.Local background weighting is applied to identify further and mark the targets.The consistency of the dynamic model is considered.Energy is used to constraint target dynamics，long-term tracking and target similarity and mutual exclusion.Reversible jump Markov chain Monte Carlo is applied to optimize the nonconvex energy function.Some image sequences are added with different levels of noise.Experimental results show that in the image sequences with Gaussian noise，compared with other tracking algorithm s，the similarities of the proposed algorithm's detection and tracking are highest.In addition，the precision and recall in satellite image sequences and self-capture videos are also highest.The overall performance of the proposed algorithm is better.

multi-target tracking；local background weighting；energy constraint；nonconvex；reversible jump Markov chain Monte Carlo

陳家紅.基于局部背景加權和能量約束的多目標檢測與跟蹤算法［J］.計算機工程，2015，41（11）：267-272.

英文引用格式：Chen Jiahong.Multi-target Detection and Tracking Algorithm Based on Local Background Weighting and Energy Constraint［J］.Computer Engineering，2015，41（11）：267-272.

1000-3428（2015）11-0267-06

A

TP391

10.3969/j.issn.1000-3428.2015.11.046

江蘇省高校自然科學基金資助項目（11KJD520006）；江蘇省教育科學“十二五”規(guī)劃課題基金資助項目（D/2013/01/068）。

陳家紅（1979-），男，講師，主研方向：圖像處理，目標跟蹤。

2015-06-12

2015-07-07 E-m ail：chenjiahong-email@126.com