一種改進(jìn)的基于Hankel總體最小二乘法的精子多目標(biāo)跟蹤方法

雷茜茜，黃文明，鄧珍榮，冷金強(qiáng)

(桂林電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林541004)

檢測(cè)跟蹤運(yùn)動(dòng)目標(biāo)是圖像處理和計(jì)算機(jī)視覺(jué)的重要研究?jī)?nèi)容，它在軍事、視頻監(jiān)控和醫(yī)療診斷方面都有廣泛的應(yīng)用。多目標(biāo)跟蹤主要有特征建模、貝葉斯估計(jì)、光流場(chǎng)與運(yùn)動(dòng)場(chǎng)、概率關(guān)聯(lián)匹配等方法。余東等［1］提出了改進(jìn)的最鄰近搜索法，通過(guò)計(jì)算幀間精子的運(yùn)動(dòng)距離和方向預(yù)測(cè)其在下一幀圖像序列中可能出現(xiàn)的位置，并利用跟蹤丟失補(bǔ)償和預(yù)測(cè)范圍最小原則，與傳統(tǒng)最近鄰算法相比，提高了跟蹤的精度，但對(duì)于密度大、運(yùn)動(dòng)無(wú)規(guī)律的精子無(wú)法進(jìn)行有效跟蹤。汪忠傳等［2］提出了一種基于小窗口的應(yīng)用于超長(zhǎng)時(shí)間精子序列圖像跟蹤的最大距離預(yù)測(cè)法，通過(guò)結(jié)合最大距離預(yù)測(cè)法和最近鄰搜索算法對(duì)精子進(jìn)行實(shí)時(shí)跟蹤，但該算法和卡爾曼濾波、粒子濾波算法一樣，需要假設(shè)先驗(yàn)?zāi)Ｐ皖A(yù)測(cè)下一幀目標(biāo)所在位置。Ding等［3］提出了一種Hankel矩陣低秩逼近求運(yùn)動(dòng)相似度的多目標(biāo)跟蹤算法，在未假設(shè)運(yùn)動(dòng)先驗(yàn)?zāi)Ｐ秃湍繕?biāo)外觀信息的條件下實(shí)現(xiàn)了多目標(biāo)跟蹤，但該算法采用凸松弛和一般內(nèi)點(diǎn)(generic interior point)法求解Hankel矩陣的秩，計(jì)算復(fù)雜度和空間復(fù)雜度高，不易于實(shí)現(xiàn)。Collins［4］和Andriyenko等［5］提出了高階運(yùn)動(dòng)模型算法，通過(guò)利用高階運(yùn)動(dòng)模型實(shí)現(xiàn)跟蹤外觀相似的目標(biāo)，且未假設(shè)先驗(yàn)?zāi)Ｐ?。但這些方法仍有限制，文獻(xiàn)［4］的時(shí)間復(fù)雜度高達(dá)O(d2.5)，d為檢測(cè)區(qū)的個(gè)數(shù);文獻(xiàn)［5］的算法需要調(diào)試大量的參數(shù)。Dicle等［6］提出了Hankel總體最小二乘法(Hankel total least square，簡(jiǎn)稱HTLS)、廣義線性分配法(generalized linear assignment，簡(jiǎn)稱GLA)進(jìn)行關(guān)聯(lián)的多目標(biāo)跟蹤算法，此算法跟蹤準(zhǔn)確率較高，不需要目標(biāo)的外觀信息和運(yùn)動(dòng)的先驗(yàn)?zāi)Ｐ停商幚砣我飧唠A運(yùn)動(dòng)，且只需2個(gè)參數(shù)，但該算法漏跟蹤率較高，處理時(shí)間較長(zhǎng)，特別是目標(biāo)密集的圖像序列。鑒于此，提出一種改進(jìn)的Hankel總體最小二乘法。

1 最近鄰算法改進(jìn)的運(yùn)動(dòng)相似性模型

在一組精子圖像序列中，精子外觀都很相似，且軌跡長(zhǎng)度不一，故在進(jìn)行精子軌跡片段關(guān)聯(lián)的過(guò)程中面臨沒(méi)有外觀信息、目標(biāo)遮擋、運(yùn)動(dòng)軌跡交叉、運(yùn)動(dòng)無(wú)規(guī)律等，造成了跟蹤的困難。為解決此問(wèn)題，結(jié)合最近鄰算法和Hankel總體最小二乘法對(duì)運(yùn)動(dòng)精子進(jìn)行跟蹤。

1.1 最近鄰算法

最近鄰算法是提出最早、最簡(jiǎn)單的目標(biāo)跟蹤方法，在某些特定情況下是最有效的。該方法首先設(shè)置一個(gè)關(guān)聯(lián)門(mén)用來(lái)限制潛在的決策數(shù)目，經(jīng)關(guān)聯(lián)門(mén)將所有回波進(jìn)行初步篩選得到候選回波。關(guān)聯(lián)門(mén)是整個(gè)跟蹤區(qū)域中的一個(gè)子區(qū)域，其中心位于被跟蹤目標(biāo)的預(yù)測(cè)位置，范圍根據(jù)在一定的概率上能收到正確回波而設(shè)計(jì)。最近鄰算法是對(duì)落在關(guān)聯(lián)門(mén)中的點(diǎn)進(jìn)行選擇，根據(jù)距離進(jìn)行判斷，選擇距離被跟蹤目標(biāo)預(yù)測(cè)點(diǎn)最近的點(diǎn)。

在圖像處理中應(yīng)用最近鄰算法，計(jì)算量小、簡(jiǎn)單、易于實(shí)現(xiàn)。通過(guò)計(jì)算下一幀圖像中所有目標(biāo)與上一幀圖像中被跟蹤目標(biāo)的距離，取距離最近者為被跟蹤目標(biāo)在下一幀圖像中的位置來(lái)實(shí)現(xiàn)跟蹤［1］。

1.2 Hankel總體最小二乘法

設(shè)一個(gè)軌跡片段α由一個(gè)有序測(cè)量值yk組成，

其中，s≤k≤s+l－1，s為開(kāi)始幀，l為軌跡片段α的長(zhǎng)度。對(duì)于足夠大的n，線性回歸器是通用的近似器［7］，可將軌跡片段α的基本運(yùn)動(dòng)模型用線性回歸器表示為:

回歸器的順序n為運(yùn)動(dòng)的復(fù)雜度。在沒(méi)有噪聲的情況下，n=rank()，其中為m(m≥n)列的Hankel矩陣:

于是，2個(gè)軌跡片段αi、αj之間的運(yùn)動(dòng)相似度Pij可定義為［3］:

對(duì)于軌跡片段α的長(zhǎng)度l，有運(yùn)動(dòng)復(fù)雜性n＜l，設(shè)分別為無(wú)噪聲坐標(biāo)序列和噪聲。為了便于表示，使Hankel矩陣［A|b］=［］，［E|f］=［］，其中:

E、f為A與b的誤差矩陣。由式(1)、(2)可得，(A+E)x=(b+f)。根據(jù)TLS通過(guò)最小化誤差矩陣E、f可以求解x的思想，可求解總體最小二乘(TLS)問(wèn)題［8］求出α:

其中:○為Hadamard乘，(A+E)x=(b+f)，［A|b］，［E|f］∈SH。引入Ω恢復(fù)丟失的數(shù)據(jù)。

由于［E|f］和［A|b］是對(duì)角線元素相等的Hankel矩陣，可將式(4)改寫(xiě)為:

其中:r(η，x)=b+f－(A+E)x=0;D為對(duì)角矩陣，其組成元素包含Hankel矩陣中ηi出現(xiàn)的次數(shù)。

結(jié)合約束條件和最小化問(wèn)題［8］，得

其中:π為處罰常量;r(η，x)為

p1=［Om×nIm×m］，m=l－n。線性化r(η，x)可得:

于是，存在矩陣X∈Rm×(m+n－1)滿足:

其中，p0=［I(m+n－1)×(m+n－1)O(m+n－1)×1］。因此，最終可將式(6)寫(xiě)為:

此式可通過(guò)Hankel最小二乘法求解［9］。

1.3 廣義線性分配(GLA)關(guān)聯(lián)

假設(shè)已知N條軌跡片段{α1，α2，…，αN}，GLA問(wèn)題可表述為最優(yōu)化問(wèn)題［10-11］:

1.4 改進(jìn)的軌跡片段運(yùn)動(dòng)相似度模型

針對(duì)Hankel算法計(jì)算復(fù)雜問(wèn)題，結(jié)合最近鄰算法，提出最近鄰算法改進(jìn)的Hankel總體最小二乘運(yùn)動(dòng)相似性計(jì)算方法。首先計(jì)算相鄰幀間所有軌跡片段αi和αj(i，j=1，2，…，N)的歐式距離Di，Di為αi與下一幀所有軌跡片段的距離向量。對(duì)Di按從小至大順序進(jìn)行排序，并記錄對(duì)應(yīng)索引Ii:

然后采用式(3)計(jì)算距離最近的軌跡片段αi與αIi(1)的相似度，若相似度為零，則計(jì)算αi與距離次近的軌跡片段αIi(2)的相似度，以此類(lèi)推，直至相似度P為1停止計(jì)算。最后利用式(10)對(duì)相似度為1的軌跡片段進(jìn)行關(guān)聯(lián)，實(shí)現(xiàn)對(duì)動(dòng)物精子的多目標(biāo)跟蹤。

2 實(shí)驗(yàn)結(jié)果與分析

算法實(shí)驗(yàn)在配有Pentium IV 2.93 GHz和2 GB內(nèi)存的計(jì)算機(jī)上使用Matlab仿真實(shí)現(xiàn)，以采樣頻率為25幀每秒、經(jīng)分割識(shí)別后的動(dòng)物精子圖像序列為實(shí)驗(yàn)對(duì)象，其初始圖像如圖1(精子已編號(hào))［1］。

圖1 首幀精子圖像Fig.1 The first picture of sperm

為進(jìn)行有效對(duì)比，實(shí)驗(yàn)分別運(yùn)行最近鄰算法、文獻(xiàn)［6］算法和本算法對(duì)25幀動(dòng)物精子圖像序列進(jìn)行多目標(biāo)跟蹤，獲得的精子運(yùn)動(dòng)軌跡如圖2所示，其中圖2(a)、(b)和(c)分別為最近鄰算法、文獻(xiàn)［6］算法及本算法的跟蹤軌跡圖，圖2(d)為動(dòng)物精子的實(shí)際運(yùn)動(dòng)軌跡圖。對(duì)比分析圖2的跟蹤軌跡可看出，最近鄰算法與精子實(shí)際運(yùn)動(dòng)軌跡的差別最大，改進(jìn)算法與精子實(shí)際運(yùn)動(dòng)軌跡最接近。

各算法的處理時(shí)間和準(zhǔn)確率結(jié)果如表1所示。從表1可見(jiàn)，3種算法中，最近鄰算法僅需計(jì)算精子質(zhì)心間的距離，快速簡(jiǎn)單，跟蹤速度最快，僅為3.59 s，但對(duì)于精子密集度較高、目標(biāo)遮擋、運(yùn)動(dòng)發(fā)生突變的情況無(wú)法進(jìn)行有效處理，使得準(zhǔn)確率為90.60%最低。文獻(xiàn)［6］算法的跟蹤線索為運(yùn)動(dòng)狀態(tài)，不依賴目標(biāo)外觀，也不受外界因素的干擾，準(zhǔn)確率較高，達(dá)95.58%，但該計(jì)算相似度的過(guò)程很復(fù)雜，算法運(yùn)行時(shí)間較長(zhǎng)。本算法結(jié)合兩者的優(yōu)點(diǎn)，取距離最近的待跟蹤目標(biāo)與跟蹤目標(biāo)進(jìn)行相似性匹配，跟蹤時(shí)間縮短至3.94 s，降低了11.06%，且精子漏跟蹤率下降了一定幅度，更快速準(zhǔn)確地實(shí)現(xiàn)了精子多目標(biāo)跟蹤。

表1 算法運(yùn)行時(shí)間與準(zhǔn)確率Tab.1 Time and accuracy of three algorithms

3 結(jié)束語(yǔ)

Hankel總體最小二乘法為相似外觀的多目標(biāo)跟蹤提供了可靠的跟蹤線索。鑒于動(dòng)物精子外觀的相似性，利用文獻(xiàn)［6］算法，并在進(jìn)行運(yùn)動(dòng)相似性匹配的同時(shí)結(jié)合最近鄰算法縮小匹配范圍，提高跟蹤速度。實(shí)驗(yàn)結(jié)果表明，本算法能穩(wěn)定、準(zhǔn)確且快速地跟蹤動(dòng)物精子的運(yùn)動(dòng)，為后續(xù)精子質(zhì)量參數(shù)分析的準(zhǔn)確性提供了可靠保證。但本算法在進(jìn)行軌跡跟蹤的過(guò)程中未解決精子彈性碰撞問(wèn)題。為滿足實(shí)際應(yīng)用的要求，進(jìn)一步提高準(zhǔn)確率仍需今后更深入研究。

圖2 3種算法跟蹤及實(shí)際軌跡Fig.2 Tracked trajectories of three algorithms and real trajectories

［1］余東.豬精子質(zhì)量自動(dòng)分析系統(tǒng)應(yīng)用研究［D］.桂林:桂林電子科技大學(xué)，2012:27-39.

［2］汪傳忠，任明響，武海燕.最大距離預(yù)測(cè)法在超長(zhǎng)時(shí)間精子序列圖像跟蹤中的應(yīng)用［J］.測(cè)試技術(shù)學(xué)報(bào)，2014，28(2):132-136.

［3］Ding T，Sznaier M，Camps O.Fast track matching and event detection［C］//Anchorage:the IEEE Conference on Computer Vision and Pattern Recognition，2008:1-8.

［4］Collins R.Multi-target data association with higher-order motion models［C］//Providence:the IEEE Conference on Computer Vision and Pattern Recognition，2012:1744-1751.

［5］Andriyenko A，Schindler K，Roth S.Discrete-continuous optimization for multi-target tracking［C］//Providence:the IEEE Conference on Computer Vision and Pattern Recognition，2012:1926-1933.

［6］Caglayan D，Mario S，Octavia C.The way they move:tracking multiple targets with similar appearance［C］//IEEE International Conference on Computer Vision，2013:2304-2311.

［7］Ross G，Soland R.A branch and bound algorithm for the generalized assignment problem［J］.Mathematical Programming，1975，8(1):91-103.

［8］Shmoys D，Tardos E.An approximation algorithm for the generalized assignment problem［J］.Mathematical Programming，1993，62(1):461-474.

［9］Gold S，Rangarajan A.Softmax to softassign:neural network algorithms for combinatorial optimization［J］.Journal of Artificial Neural Networks，1995，2(4):381-399.

［10］Breiman L.Hinging hyperplanes for regression，classification and function approximation［C］//IEEE Transaction on Information Theory，1993:999-1011.

［11］Park H，Zhang L，Rosen J B.Low rank approximation of a Hankel matrix by structured total least norm［J］.BIT Numerical Mathematics，1999，39(4):757-779.

［12］Markovsky I，Huffel S V.Overview of total least squares methods［J］.Signal Processing，2007，87(10):2283-2302.