1 WANG Hongyuan,et al:Efficient tracker based on sparse coding with Euclidean local structure-based constraint ·141. Table 2 Euclidean Local Structure based Tracking ELSS-tracker) Input:Given a video stream for tracking,location of the target l in frame #1 Output:Tracking results of each frame 1:Set s=1,select 10 template regions extremely near the target in #1,then resize and stretch them to beTR 2:While not reach the end of the video sequence,ss+1 3:Pick N=200 candidate regions around the latest target location in frame #s,and stretch to be yRx 4:Construct D with T,positive and negative identity matries,likewise in Fig.I and Fig2 5:Solve ELSSC-optimization with Y and D in Tab.1,and denote the optimization result as c 6:Compute the reconstruct errors eVeand the normalized weight where exp(ea) 7:Locate the object for tracking with the weighted sum of all 200 candidate regions and in frame #s 8:Select 10 regions that extremely nearby the object as the new target templates T 9:End 3 Experiments ELSSC were verified.The experiments were designed with the Face sequence in the VOT 2013 benchmark 3.1 Experimental setting datasetis]as follows:six similar regions were repre- In order to evaluate the proposed tracker,experi- sented (CR,..,CR,their means and standard deri- ments on 12 video sequences were conducted,inclu- vations illustrate the similarity)sparsely with template ding Surfer,Dudek,Faceocc2,Animal,Girl,Stone,T=[T,To]R0xio from two regions apart Car,Cup,Face,Juice,Singer,Sunshade,Bike,Car from each other the red region and the green one). Dark,and Jumping These sequences covered al- Evidently,T is over-completed,and the entire diction- most all challenges in tracking,including occlusion ary DR is constructed likewise in Figs.1 (even heavy occlusion),motion blur,rotation,scale and 2. variation,illumination variation,and complex back- The sparse coefficients of CR,.,CR generated ground.For comparison,we used four state-of-the-art with the 1-,the NISSSC-,the original ELSSC-,and algorithms with the same initial positions and the same the improved ELSSC-optimization are plotted in Fig.3. representations of the targets.They were the incremen-In particular,six similar regions have very different tal learning-based tracker (IVT,a common discrimi- representation coefficients,when using the original I- nant tracker)[14],the covariance-based tracker (Cov- optimization problem,which ignores the structure in- Track,a generative tracker on Lie-group)(,the formation between regions.The results of the other tracker (a generative tracking method),and the three algorithms are much more stable,because of NISSST.All the experiments were run on a comput- preservation of the structural information.If two regions er with a 2.67 GHz CPU and a 2 GB memory. are similar to each other,they also have similar sparse The main parameters used in our experiments coefficients.This improves the robustness of tracking; are set as follows:the number of candidate regions otherwise,the tracker may degenerate or even fail to N=200,the number of template regions is n track.CR for example,with I-optimization,can be 10,and the candidates and targets are resized to represented by T2,Ts,T,T,and T1,and the track- 40×40. er may fail to track the top of the book.Meanwhile,ex- 3.2 Experimental results for sparsity and stability perimental results show that,NLSSSC and our two The stability and sparsity of the original sparse ELSSC are sparser than the original 1 -optimization coding,the NISSSC,and the original and improved problem.Ｔａｂｌｅ ２ Ｅｕｃｌｉｄｅａｎ Ｌｏｃａｌ Ｓｔｒｕｃｔｕｒｅ ｂａｓｅｄ Ｔｒａｃｋｉｎｇ （ＥＬＳＳ⁃ｔｒａｃｋｅｒ） Ｉｎｐｕｔ：Ｇｉｖｅｎ ａ ｖｉｄｅｏ ｓｔｒｅａｍ ｆｏｒ ｔｒａｃｋｉｎｇ，ｌｏｃａｔｉｏｎ ｏｆ ｔｈｅ ｔａｒｇｅｔ ｌ １ ｉｎ ｆｒａｍｅ ＃１ Ｏｕｔｐｕｔ：Ｔｒａｃｋｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ｅａｃｈ ｆｒａｍｅ １：Ｓｅｔ ｓ ＝ １，ｓｅｌｅｃｔ １０ ｔｅｍｐｌａｔｅ ｒｅｇｉｏｎｓ ｅｘｔｒｅｍｅｌｙ ｎｅａｒ ｔｈｅ ｔａｒｇｅｔ ｉｎ ＃１，ｔｈｅｎ ｒｅｓｉｚｅ ａｎｄ ｓｔｒｅｔｃｈ ｔｈｅｍ ｔｏ ｂｅ Ｔ ∈ Ｒ １ ６００×１０ ２：Ｗｈｉｌｅ ｎｏｔ ｒｅａｃｈ ｔｈｅ ｅｎｄ ｏｆ ｔｈｅ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅ，ｓ←ｓ＋１ ３：Ｐｉｃｋ Ｎ＝ ２００ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ａｒｏｕｎｄ ｔｈｅ ｌａｔｅｓｔ ｔａｒｇｅｔ ｌｏｃａｔｉｏｎ ｌ ｓ⁃１ ｉｎ ｆｒａｍｅ ＃ｓ，ａｎｄ ｓｔｒｅｔｃｈ ｔｏ ｂｅ Ｙ ∈ Ｒ １ ６００×２００ ４：Ｃｏｎｓｔｒｕｃｔ Ｄ ｗｉｔｈ Ｔ， ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｅｓ，ｌｉｋｅｗｉｓｅ ｉｎ Ｆｉｇ．１ ａｎｄ Ｆｉｇ２ ５：Ｓｏｌｖｅ ＥＬＳＳＣ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｗｉｔｈ Ｙ ａｎｄ Ｄ ｉｎ Ｔａｂ．１，ａｎｄ ｄｅｎｏｔｅ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｒｅｓｕｌｔ ａｓ ｃ （ｓ） ｉ ６：Ｃｏｍｐｕｔｅ ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔ ｅｒｒｏｒｓ ｅ （ｓ） ｉ ＝ ‖ｘ （ｓ） ｉ － Ｖｃ （ｓ） ｉ ‖２ ２ ａｎｄ ｔｈｅ ｎｏｒｍａｌｉｚｅｄ ｗｅｉｇｈｔ ｗ （ｓ） ｉ ＝ ｗ （ｓ） ｉ ／∑ｉ ｗ （ｓ） ｉ ， ｗｈｅｒｅ ｗ （ｓ） ｉ ＝ ｅｘｐ（ － ｅ （ｓ） ｉ ／ α） ７：Ｌｏｃａｔｅ ｔｈｅ ｏｂｊｅｃｔ ｆｏｒ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｔｈｅ ｗｅｉｇｈｔｅｄ ｓｕｍ ｏｆ ａｌｌ ２００ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ａｎｄ ｗ （ｓ） ｉ ｉｎ ｆｒａｍｅ ＃ｓ ８：Ｓｅｌｅｃｔ １０ ｒｅｇｉｏｎｓ ｔｈａｔ ｅｘｔｒｅｍｅｌｙ ｎｅａｒｂｙ ｔｈｅ ｏｂｊｅｃｔ ａｓ ｔｈｅ ｎｅｗ ｔａｒｇｅｔ ｔｅｍｐｌａｔｅｓ Ｔ ９：Ｅｎｄ ３ Ｅｘｐｅｒｉｍｅｎｔｓ ３．１ Ｅｘｐｅｒｉｍｅｎｔａｌ ｓｅｔｔｉｎｇ Ｉｎ ｏｒｄｅｒ ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｒａｃｋｅｒ， ｅｘｐｅｒｉ⁃ ｍｅｎｔｓ ｏｎ １２ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ ｗｅｒｅ ｃｏｎｄｕｃｔｅｄ， ｉｎｃｌｕ⁃ ｄｉｎｇ Ｓｕｒｆｅｒ， Ｄｕｄｅｋ， Ｆａｃｅｏｃｃ２， Ａｎｉｍａｌ， Ｇｉｒｌ， Ｓｔｏｎｅ， Ｃａｒ， Ｃｕｐ， Ｆａｃｅ， Ｊｕｉｃｅ， Ｓｉｎｇｅｒ， Ｓｕｎｓｈａｄｅ， Ｂｉｋｅ， Ｃａｒ Ｄａｒｋ， ａｎｄ Ｊｕｍｐｉｎｇ ［１７⁃１９］ ． Ｔｈｅｓｅ ｓｅｑｕｅｎｃｅｓ ｃｏｖｅｒｅｄ ａｌ⁃ ｍｏｓｔ ａｌｌ ｃｈａｌｌｅｎｇｅｓ ｉｎ ｔｒａｃｋｉｎｇ， ｉｎｃｌｕｄｉｎｇ ｏｃｃｌｕｓｉｏｎ （ｅｖｅｎ ｈｅａｖｙ ｏｃｃｌｕｓｉｏｎ）， ｍｏｔｉｏｎ ｂｌｕｒ， ｒｏｔａｔｉｏｎ， ｓｃａｌｅ ｖａｒｉａｔｉｏｎ， ｉｌｌｕｍｉｎａｔｉｏｎ ｖａｒｉａｔｉｏｎ， ａｎｄ ｃｏｍｐｌｅｘ ｂａｃｋ⁃ ｇｒｏｕｎｄ． Ｆｏｒ ｃｏｍｐａｒｉｓｏｎ， ｗｅ ｕｓｅｄ ｆｏｕｒ ｓｔａｔｅ⁃ｏｆ⁃ｔｈｅ⁃ａｒｔ ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ ｔｈｅ ｓａｍｅ ｉｎｉｔｉａｌ ｐｏｓｉｔｉｏｎｓ ａｎｄ ｔｈｅ ｓａｍｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ ｏｆ ｔｈｅ ｔａｒｇｅｔｓ． Ｔｈｅｙ ｗｅｒｅ ｔｈｅ ｉｎｃｒｅｍｅｎ⁃ ｔａｌ ｌｅａｒｎｉｎｇ⁃ｂａｓｅｄ ｔｒａｃｋｅｒ （ ＩＶＴ， ａ ｃｏｍｍｏｎ ｄｉｓｃｒｉｍｉ⁃ ｎａｎｔ ｔｒａｃｋｅｒ） ［１４］ ， ｔｈｅ ｃｏｖａｒｉａｎｃｅ⁃ｂａｓｅｄ ｔｒａｃｋｅｒ （Ｃｏｖ⁃ Ｔｒａｃｋ， ａ ｇｅｎｅｒａｔｉｖｅ ｔｒａｃｋｅｒ ｏｎ Ｌｉｅ⁃ｇｒｏｕｐ） ［１５］ ， ｔｈｅ ｌ １ ⁃ ｔｒａｃｋｅｒ （ ａ ｇｅｎｅｒａｔｉｖｅ ｔｒａｃｋｉｎｇ ｍｅｔｈｏｄ） ［８⁃９］ ， ａｎｄ ｔｈｅ ＮＬＳＳＳＴ ［１１］ ．Ａｌｌ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｒｕｎ ｏｎ ａ ｃｏｍｐｕｔ⁃ ｅｒ ｗｉｔｈ ａ ２．６７ ＧＨｚ ＣＰＵ ａｎｄ ａ ２ ＧＢ ｍｅｍｏｒｙ． Ｔｈｅ ｍａｉｎ ｐａｒａｍｅｔｅｒｓ ｕｓｅｄ ｉｎ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔｓ ａｒｅ ｓｅｔ ａｓ ｆｏｌｌｏｗｓ： ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ Ｎ ＝ ２００， ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔｅｍｐｌａｔｅ ｒｅｇｉｏｎｓ ｉｓ ｎ ＝ １０， ａｎｄ ｔｈｅ ｃａｎｄｉｄａｔｅｓ ａｎｄ ｔａｒｇｅｔｓ ａｒｅ ｒｅｓｉｚｅｄ ｔｏ ４０ × ４０． ３．２ Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｆｏｒ ｓｐａｒｓｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ Ｔｈｅ ｓｔａｂｉｌｉｔｙ ａｎｄ ｓｐａｒｓｉｔｙ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｓｐａｒｓｅ ｃｏｄｉｎｇ， ｔｈｅ ＮＬＳＳＳＣ， ａｎｄ ｔｈｅ ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ ｗｅｒｅ ｖｅｒｉｆｉｅｄ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｄｅｓｉｇｎｅｄ ｗｉｔｈ ｔｈｅ Ｆａｃｅ ｓｅｑｕｅｎｃｅ ｉｎ ｔｈｅ ＶＯＴ ２０１３ ｂｅｎｃｈｍａｒｋ ｄａｔａｓｅｔ ［１８］ ａｓ ｆｏｌｌｏｗｓ： ｓｉｘ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ ｗｅｒｅ ｒｅｐｒｅ⁃ ｓｅｎｔｅｄ （ＣＲ１ ，…，ＣＲ６ ， ｔｈｅｉｒ ｍｅａｎｓ ａｎｄ ｓｔａｎｄａｒｄ ｄｅｒｉ⁃ ｖａｔｉｏｎｓ ｉｌｌｕｓｔｒａｔｅ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ） ｓｐａｒｓｅｌｙ ｗｉｔｈ ｔｅｍｐｌａｔｅ Ｔ ＝ Ｔ１ ，…，Ｔ１０ [ ] ∈ Ｒ １ ６００×１０ ｆｒｏｍ ｔｗｏ ｒｅｇｉｏｎｓ ａｐａｒｔ ｆｒｏｍ ｅａｃｈ ｏｔｈｅｒ （ ｔｈｅ ｒｅｄ ｒｅｇｉｏｎ ａｎｄ ｔｈｅ ｇｒｅｅｎ ｏｎｅ）． Ｅｖｉｄｅｎｔｌｙ， Ｔ ｉｓ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅｄ， ａｎｄ ｔｈｅ ｅｎｔｉｒｅ ｄｉｃｔｉｏｎ⁃ ａｒｙ Ｄ ∈ Ｒ １ ６００×３ ２１０ ｉｓ ｃｏｎｓｔｒｕｃｔｅｄ ｌｉｋｅｗｉｓｅ ｉｎ Ｆｉｇｓ． １ ａｎｄ ２． Ｔｈｅ ｓｐａｒｓｅ ｃｏｅffiｃｉｅｎｔｓ ｏｆ ＣＲ１ ，…， ＣＲ６ ｇｅｎｅｒａｔｅｄ ｗｉｔｈ ｔｈｅ ｌ １ ⁃， ｔｈｅ ＮＬＳＳＳＣ⁃， ｔｈｅ ｏｒｉｇｉｎａｌ ＥＬＳＳＣ⁃， ａｎｄ ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ａｒｅ ｐｌｏｔｔｅｄ ｉｎ Ｆｉｇ． ３． Ｉｎ ｐａｒｔｉｃｕｌａｒ， ｓｉｘ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ ｈａｖｅ ｖｅｒｙ ｄｉffｅｒｅｎｔ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｃｏｅffiｃｉｅｎｔｓ， ｗｈｅｎ ｕｓｉｎｇ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ， ｗｈｉｃｈ ｉｇｎｏｒｅｓ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｂｅｔｗｅｅｎ ｒｅｇｉｏｎｓ． Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｏｔｈｅｒ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｍｕｃｈ ｍｏｒｅ ｓｔａｂｌｅ， ｂｅｃａｕｓｅ ｏｆ ｐｒｅｓｅｒｖａｔｉｏｎ ｏｆ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｉｎｆｏｒｍａｔｉｏｎ． Ｉｆ ｔｗｏ ｒｅｇｉｏｎｓ ａｒｅ ｓｉｍｉｌａｒ ｔｏ ｅａｃｈ ｏｔｈｅｒ， ｔｈｅｙ ａｌｓｏ ｈａｖｅ ｓｉｍｉｌａｒ ｓｐａｒｓｅ ｃｏｅffiｃｉｅｎｔｓ． Ｔｈｉｓ ｉｍｐｒｏｖｅｓ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｔｒａｃｋｉｎｇ； ｏｔｈｅｒｗｉｓｅ， ｔｈｅ ｔｒａｃｋｅｒ ｍａｙ ｄｅｇｅｎｅｒａｔｅ ｏｒ ｅｖｅｎ ｆａｉｌ ｔｏ ｔｒａｃｋ． ＣＲ４ ｆｏｒ ｅｘａｍｐｌｅ， ｗｉｔｈ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ， ｃａｎ ｂｅ ｒｅｐｒｅｓｅｎｔｅｄ ｂｙ Ｔ２ ， Ｔ８ ， Ｔ６ ， Ｔ７ ， ａｎｄ Ｔ１ ， ａｎｄ ｔｈｅ ｔｒａｃｋ⁃ ｅｒ ｍａｙ ｆａｉｌ ｔｏ ｔｒａｃｋ ｔｈｅ ｔｏｐ ｏｆ ｔｈｅ ｂｏｏｋ． Ｍｅａｎｗｈｉｌｅ， ｅｘ⁃ ｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ， ＮＬＳＳＳＣ ａｎｄ ｏｕｒ ｔｗｏ ＥＬＳＳＣ ａｒｅ ｓｐａｒｓｅｒ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ． 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１４１·