1 WANG Hongyuan,et al:Efficient tracker based on sparse coding with Euclidean local structure-based constraint ·137. trade-off occurs between sparsity and stability when de- 1 Related works signing a learning algorithm.In addition,instability in the I,-optimization problem affects the performance of 1.1 Sparse coding and the I,-tracker the 1-tracker. Sparse coding is an attractive signal reconstruction Lu developed a NLSSS-tracker NLSSST)based method proposed by Candes that reconstructs a sig- on SC applying a non-local self-similarity constraint by nal y R"x with an over-complete dictionary D introducing the geometrical information of the set of R)with a sparse coefficient vectoreR.The candidates as a smoothing term to alleviate the instabil- SC formulation can be written as the lo-norm-constrain- ity of the -tracker However,its low efficiency (e- ed optimization problem as follows: ven slower than the original l-tracker,Table 4)re- min,lly-Dcli+all cllo (1) which is NP-hard,where‖·‖edenotes the vector's stricts its applicability in real-time tracking.In this Frobenius norm(i.e.,l2-nom),and‖·‖locounts study,motivated by the robustness of the I-tracker and the number of non-zero elements of the vector.Candes stability of NISSST,we propose a novel tracker, proved that the I-norm Il is the tightest upper called ELSS-tracker (ELSST),that is both robust and bound of the lo-nom‖·Io,and thus,Eq.(1)can efficient.The main contributions of this study are as be rewritten as the following I-optimization prob- follows: lem[67]: 1)An efficient tracker,i.e.,ELSST,is developed min,lly-Dcl+a‖lcli (2) by considering the local structure of the set of target Based on SC,Mei presented a nice I-tracker for candidates.In contrast to the Lu5s and Mei5s-track- robust trackingFig.1).Considering that the target e our tracker is more stable and sparse. is located in the latest frame,the I-tracker is initial- ized in the new arrival frame and N candidate regions 2)The proposed tracker shows excellent perform- are generated with Bayesian inference (Fig.la,b). ance in tracking different video sequences with regard With n templates learned from previous tracking and to scale,occlusion,pose variations,background clut- 2m trivial templates (m positive ones and m negative ter,and illumination changes. ones,where m is the dimension of 1D stretched image, The rest of this study is organized as follows:I- Fig.Ic),Eq.(2)can be solved Fig.1d,e,f).With and NLSSS-tracker are introduced in section 2:in sec- positive and negative trivial templates,Mei added a tion 3,we analyze the disadvantages of these two track- non-negative constraint c0 in Eq.(2),with which ers and propose our tracker;experimental results with the reconstruction errors of all candidate regions with our tracker and four comparison algorithms are reported SC coefficients can be used to determine the weights for each candidate,and the object in the new arrival frame in section 4;the conclusion and future work are sum- can be located with the sum of the weighted candidates. marized in section 5. The dictionaries updating strategies can be seen in target template T Trival Template/ (a)New arrival frame (b)N candidate (c)Over-complete regions dictionary Cr∈RW1 C∈RW C∈RmN cwith sparity constraint minllcll (d)Sample (e)Dictionaries (f)Coefficient of represention Fig.1 Original I-tracker algorithmｔｒａｄｅ⁃ｏｆｆ ｏｃｃｕｒｓ ｂｅｔｗｅｅｎ ｓｐａｒｓｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｗｈｅｎ ｄｅ⁃ ｓｉｇｎｉｎｇ ａ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｉｎ ａｄｄｉｔｉｏｎ， ｉｎｓｔａｂｉｌｉｔｙ ｉｎ ｔｈｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ａｆｆｅｃｔｓ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ． Ｌｕ ｄｅｖｅｌｏｐｅｄ ａ ＮＬＳＳＳ⁃ｔｒａｃｋｅｒ （ＮＬＳＳＳＴ） ｂａｓｅｄ ｏｎ ＳＣ ａｐｐｌｙｉｎｇ ａ ｎｏｎ⁃ｌｏｃａｌ ｓｅｌｆ⁃ｓｉｍｉｌａｒｉｔｙ ｃｏｎｓｔｒａｉｎｔ ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ｇｅｏｍｅｔｒｉｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｓｅｔ ｏｆ ｃａｎｄｉｄａｔｅｓ ａｓ ａ ｓｍｏｏｔｈｉｎｇ ｔｅｒｍ ｔｏ ａｌｌｅｖｉａｔｅ ｔｈｅ ｉｎｓｔａｂｉｌ⁃ ｉｔｙ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ［１１］ ． Ｈｏｗｅｖｅｒ， ｉｔｓ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ （ｅ⁃ ｖｅｎ ｓｌｏｗｅｒ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ， Ｔａｂｌｅ ４） ｒｅ⁃ ｓｔｒｉｃｔｓ ｉｔｓ ａｐｐｌｉｃａｂｉｌｉｔｙ ｉｎ ｒｅａｌ⁃ｔｉｍｅ ｔｒａｃｋｉｎｇ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｍｏｔｉｖａｔｅｄ ｂｙ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ｓｔａｂｉｌｉｔｙ ｏｆ ＮＬＳＳＳＴ， ｗｅ ｐｒｏｐｏｓｅ ａ ｎｏｖｅｌ ｔｒａｃｋｅｒ， ｃａｌｌｅｄ ＥＬＳＳ⁃ｔｒａｃｋｅｒ （ＥＬＳＳＴ）， ｔｈａｔ ｉｓ ｂｏｔｈ ｒｏｂｕｓｔ ａｎｄ ｅｆｆｉｃｉｅｎｔ． Ｔｈｅ ｍａｉｎ ｃｏｎｔｒｉｂｕｔｉｏｎｓ ｏｆ ｔｈｉｓ ｓｔｕｄｙ ａｒｅ ａｓ ｆｏｌｌｏｗｓ： １）Ａｎ ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ， ｉ．ｅ．， ＥＬＳＳＴ， ｉｓ ｄｅｖｅｌｏｐｅｄ ｂｙ ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ ｓｅｔ ｏｆ ｔａｒｇｅｔ ｃａｎｄｉｄａｔｅｓ． Ｉｎ ｃｏｎｔｒａｓｔ ｔｏ ｔｈｅ Ｌｕ５ｓ ［１１］ ａｎｄ Ｍｅｉ５ｓ⁃ｔｒａｃｋ⁃ ｅｒ ［８⁃９］ ， ｏｕｒ ｔｒａｃｋｅｒ ｉｓ ｍｏｒｅ ｓｔａｂｌｅ ａｎｄ ｓｐａｒｓｅ． ２） Ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｒａｃｋｅｒ ｓｈｏｗｓ ｅｘｃｅｌｌｅｎｔ ｐｅｒｆｏｒｍ⁃ ａｎｃｅ ｉｎ ｔｒａｃｋｉｎｇ ｄｉｆｆｅｒｅｎｔ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｒｅｇａｒｄ ｔｏ ｓｃａｌｅ， ｏｃｃｌｕｓｉｏｎ， ｐｏｓｅ ｖａｒｉａｔｉｏｎｓ， ｂａｃｋｇｒｏｕｎｄ ｃｌｕｔ⁃ ｔｅｒ， ａｎｄ ｉｌｌｕｍｉｎａｔｉｏｎ ｃｈａｎｇｅｓ． Ｔｈｅ ｒｅｓｔ ｏｆ ｔｈｉｓ ｓｔｕｄｙ ｉｓ ｏｒｇａｎｉｚｅｄ ａｓ ｆｏｌｌｏｗｓ： ｌ １ ⁃ ａｎｄ ＮＬＳＳＳ⁃ｔｒａｃｋｅｒ ａｒｅ ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｓｅｃｔｉｏｎ ２； ｉｎ ｓｅｃ⁃ ｔｉｏｎ ３， ｗｅ ａｎａｌｙｚｅ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅｓｅ ｔｗｏ ｔｒａｃｋ⁃ ｅｒｓ ａｎｄ ｐｒｏｐｏｓｅ ｏｕｒ ｔｒａｃｋｅｒ； ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｗｉｔｈ ｏｕｒ ｔｒａｃｋｅｒ ａｎｄ ｆｏｕｒ ｃｏｍｐａｒｉｓｏｎ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｒｅｐｏｒｔｅｄ ｉｎ ｓｅｃｔｉｏｎ ４； ｔｈｅ ｃｏｎｃｌｕｓｉｏｎ ａｎｄ ｆｕｔｕｒｅ ｗｏｒｋ ａｒｅ ｓｕｍ⁃ ｍａｒｉｚｅｄ ｉｎ ｓｅｃｔｉｏｎ ５． １ Ｒｅｌａｔｅｄ ｗｏｒｋｓ １．１ Ｓｐａｒｓｅ ｃｏｄｉｎｇ ａｎｄ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ Ｓｐａｒｓｅ ｃｏｄｉｎｇ ｉｓ ａｎ ａｔｔｒａｃｔｉｖｅ ｓｉｇｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄ ｐｒｏｐｏｓｅｄ ｂｙ Ｃａｎｄｅｓ ［６⁃７］ ｔｈａｔ ｒｅｃｏｎｓｔｒｕｃｔｓ ａ ｓｉｇ⁃ ｎａｌ ｙ ∈ Ｒ ｍ×１ ｗｉｔｈ ａｎ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ ∈ Ｒ ｍ×（ｎ＋２ｍ） ｗｉｔｈ ａ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔ ｖｅｃｔｏｒｃ ∈ Ｒ ｎ×１ ． Ｔｈｅ ＳＣ ｆｏｒｍｕｌａｔｉｏｎ ｃａｎ ｂｅ ｗｒｉｔｔｅｎ ａｓ ｔｈｅ ｌ ０ ⁃ｎｏｒｍ⁃ｃｏｎｓｔｒａｉｎ⁃ ｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ａｓ ｆｏｌｌｏｗｓ： ｍｉｎｃ‖ｙ － Ｄｃ‖２ Ｆ ＋ α‖ｃ‖０ （１） ｗｈｉｃｈ ｉｓ ＮＰ⁃ｈａｒｄ， ｗｈｅｒｅ ‖·‖Ｆ ｄｅｎｏｔｅｓ ｔｈｅ ｖｅｃｔｏｒ’ｓ Ｆｒｏｂｅｎｉｕｓ ｎｏｒｍ （ ｉ． ｅ．， ｌ ２ ⁃ｎｏｒｍ）， ａｎｄ ‖·‖０ ｃｏｕｎｔｓ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｎｏｎ⁃ｚｅｒｏ ｅｌｅｍｅｎｔｓ ｏｆ ｔｈｅ ｖｅｃｔｏｒ． Ｃａｎｄｅｓ ｐｒｏｖｅｄ ｔｈａｔ ｔｈｅ ｌ １ ⁃ｎｏｒｍ ‖·‖１ ｉｓ ｔｈｅ ｔｉｇｈｔｅｓｔ ｕｐｐｅｒ ｂｏｕｎｄ ｏｆ ｔｈｅ ｌ ０ ⁃ｎｏｒｍ ‖·‖０ ， ａｎｄ ｔｈｕｓ， Ｅｑ．（１） ｃａｎ ｂｅ ｒｅｗｒｉｔｔｅｎ ａｓ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍ ［６⁃７］ ： ｍｉｎｃ ‖ｙ － Ｄｃ‖２ Ｆ ＋ α ‖ｃ‖１ （２） Ｂａｓｅｄ ｏｎ ＳＣ， Ｍｅｉ ｐｒｅｓｅｎｔｅｄ ａ ｎｉｃｅ ｌ １ ⁃ｔｒａｃｋｅｒ ｆｏｒ ｒｏｂｕｓｔ ｔｒａｃｋｉｎｇ ［８⁃９］ （Ｆｉｇ． １）． Ｃｏｎｓｉｄｅｒｉｎｇ ｔｈａｔ ｔｈｅ ｔａｒｇｅｔ ｉｓ ｌｏｃａｔｅｄ ｉｎ ｔｈｅ ｌａｔｅｓｔ ｆｒａｍｅ， ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ｉｓ ｉｎｉｔｉａｌ⁃ ｉｚｅｄ ｉｎ ｔｈｅ ｎｅｗ ａｒｒｉｖａｌ ｆｒａｍｅ ａｎｄ Ｎ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ａｒｅ ｇｅｎｅｒａｔｅｄ ｗｉｔｈ Ｂａｙｅｓｉａｎ ｉｎｆｅｒｅｎｃｅ （ Ｆｉｇ． １ａ， ｂ）． Ｗｉｔｈ ｎ ｔｅｍｐｌａｔｅｓ ｌｅａｒｎｅｄ ｆｒｏｍ ｐｒｅｖｉｏｕｓ ｔｒａｃｋｉｎｇ ａｎｄ ２ｍ ｔｒｉｖｉａｌ ｔｅｍｐｌａｔｅｓ （ｍ ｐｏｓｉｔｉｖｅ ｏｎｅｓ ａｎｄ ｍ ｎｅｇａｔｉｖｅ ｏｎｅｓ， ｗｈｅｒｅ ｍ ｉｓ ｔｈｅ ｄｉｍｅｎｓｉｏｎ ｏｆ １Ｄ ｓｔｒｅｔｃｈｅｄ ｉｍａｇｅ， Ｆｉｇ． １ｃ）， Ｅｑ．（２） ｃａｎ ｂｅ ｓｏｌｖｅｄ （Ｆｉｇ． １ｄ，ｅ，ｆ）． Ｗｉｔｈ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｔｒｉｖｉａｌ ｔｅｍｐｌａｔｅｓ， Ｍｅｉ ａｄｄｅｄ ａ ｎｏｎ⁃ｎｅｇａｔｉｖｅ ｃｏｎｓｔｒａｉｎｔ ｃ≥０ ｉｎ Ｅｑ． （２）， ｗｉｔｈ ｗｈｉｃｈ ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｅｒｒｏｒｓ ｏｆ ａｌｌ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｗｉｔｈ ＳＣ ｃｏｅｆｆｉｃｉｅｎｔｓ ｃａｎ ｂｅ ｕｓｅｄ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｗｅｉｇｈｔｓ ｆｏｒ ｅａｃｈ ｃａｎｄｉｄａｔｅ， ａｎｄ ｔｈｅ ｏｂｊｅｃｔ ｉｎ ｔｈｅ ｎｅｗ ａｒｒｉｖａｌ ｆｒａｍｅ ｃａｎ ｂｅ ｌｏｃａｔｅｄ ｗｉｔｈ ｔｈｅ ｓｕｍ ｏｆ ｔｈｅ ｗｅｉｇｈｔｅｄ ｃａｎｄｉｄａｔｅｓ． Ｔｈｅ ｄｉｃｔｉｏｎａｒｉｅｓ ｕｐｄａｔｉｎｇ ｓｔｒａｔｅｇｉｅｓ ｃａｎ ｂｅ ｓｅｅｎ ｉｎ ［８⁃９］ ． Ｆｉｇ．１ Ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ ａｌｇｏｒｉｔｈｍ 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１３７·