雷茜茜，黃文明，鄧珍榮，冷金強

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

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

1 最近鄰算法改進的運動相似性模型

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

1.1 最近鄰算法

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

在圖像處理中應用最近鄰算法，計算量小、簡單、易于實現(xiàn)。通過計算下一幀圖像中所有目標與上一幀圖像中被跟蹤目標的距離，取距離最近者為被跟蹤目標在下一幀圖像中的位置來實現(xiàn)跟蹤［1］。

1.2 Hankel總體最小二乘法

設一個軌跡片段α由一個有序測量值yk組成，

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

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

于是，2個軌跡片段αi、αj之間的運動相似度Pij可定義為［3］:

對于軌跡片段α的長度l，有運動復雜性n＜l，設分別為無噪聲坐標序列和噪聲。為了便于表示，使Hankel矩陣［A|b］=［］，［E|f］=［］，其中:

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

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

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

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

結合約束條件和最小化問題［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)寫為:

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

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

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

1.4 改進的軌跡片段運動相似度模型

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

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

2 實驗結果與分析

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

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

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

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

表1 算法運行時間與準確率Tab.1 Time and accuracy of three algorithms

3 結束語

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

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

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

［2］汪傳忠，任明響，武海燕.最大距離預測法在超長時間精子序列圖像跟蹤中的應用［J］.測試技術學報，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.