·146· 智能系统学报 第11卷 sampling[J].IEEE,signal processing magazine,2008,25 4 Conclusions (2):21-30. In this study,to deal with sparsity and instability [7]CANDES E J,ROMBERG J.TAO J.Robust uncertainty in the optimization problem and the high time principles:exact signal reconstruction from highly incom- complexity of the NLSSSC-tracker [11],we propose a plete frequency information[].IEEE transactions on infor- novel efficient tracker,i.e.,the Euclidean local-struc- mation theory,2006,52(2):489-509. [8]MEI Xue,LING Haibin,WU Yi,et al.Minimum error ture constraint based sparse coding (ELSSC).Our new bounded efficient /1 tracker with occlusion detection[Cl// algorithm is a l-tracker with a reconstructed over-com- Proceedings of IEEE Conference on Computer Vision and plete dictionary,which is different from that in the o- Pattern Recognition (CVPR).Colorado,USA,2011:1257- riginal I,-tracker and NLSSSC-tracker.Moreover,we 1264. simplify the large-scale I-optimization problem in our [9]MEI Xue,LING Haibin.Robust visual tracking and vehicle tracker to a much smaller one in our improved ELSSC- classification via sparse representation[].IEEE transac- tracker. tions on pattern analysis and machine intelligence,2011,33 Compared with the original 1,-tracker,our (11):2259-2272. [10 XU Huan,CARAMANIS C,MANNOR S.Sparse algo- ELSSC-tracker introduces the structure information a- rithms are not stable:a no-free-lunch theorem].IEEE mong the candidate regions generated by the Bayesian transactions on pattern analysis and machine intelligence, inference to the I-tracker,similar to that in the 2011,34(1):187-193. NLSSSC-tracker.With our derivation,the optimization [11]LU Xiaoqiang,YUAN Yuan,LU Pingkun,et al.Robust procedure of our tracker (Eg.(10))can be solved as visual tracking with discriminative sparse learning[J].Pat- that in the I-optimization but very differently from that tern recognition,2013,46(7):1762-1771. in the NLSSSC.Furthermore,our improved tracker is [12]YANG Jian,ZHANG Lei,XU Yong,et al.Beyond sparsi- much more efficient than the I-tracker and NLSSSC- ty:the role of L-optimizer in pattern classification [J]. tracker.Our experiments demonstrate the sparsity,sta- Pattern recognition,2012,45(3):1104-1118. [13]DAUBECHIES I,DEFRISE M,DE MOL C.An iterative bility,and efficiency of our tracker. thresholding algorithm for linear inverse problems with a References sparsity constraint[J].Communications on pure and ap- plied mathematics,2004,57(11):1413-1457. [1]ZHANG Shengping,YAO Hongxun,SUN Xin,et al.Sparse [14]ROSS D A,LIM J,LIN R S,et al.Incremental learning coding based visual tracking:review and experimental com- for robust visual tracking[J.International journal of com- parison[]].Pattern recognition,2013,46(7):1772-1788. puter vision,2008,77(1-3):125-141. [2]YILMAZ A,JAVED O,SHAH M.Object tracking:a sur- [15]PORIKLI F,TUZEL O,MEER P.Covariance tracking u- vey[]].ACM computing surveys (CSUR),2006,38(4): sing model update based on lie algebra[C]//Proceedings 1-.45. of IEEE Computer Society Conference on Computer Vision [3]KALAL Z,MIKOLAJCZYK K,MATAS J.Tracking-learn- and Pattern Recognition.New York,USA,2006:728- ing-detection[].IEEE transactions on pattern analysis and 735. machine intelligence,2012,34(7):1409-1422. [16]EVERINGHAM M,VAN GOOL L,WILLIAMS C K I,et [4]AVIDAN S.Ensemble tracking[J].IEEE transactions on al.The pascal visual object classes (VOC)challenge[J]. pattern analysis and machine intelligence,2007,29(2): International journal of computer vision,2010,88(2): 261-271. 303.338. [5]BABENKO B,YANG M H,BELONGIE S.Visual tracking [17]WU Yi,LIM J,YANG M H.Online object tracking:A with online multiple instance learning[C]//Proceedings of benchmark[C]//Proceedings of IEEE Conference on Com- IEEE Conference on Computer Vision and Pattern Recogni- puter Vision and Pattern Recognition (CVPR).Portland, tion (CVPR).Miami,USA.2009:983-990. USA,2013:2411-2418 [6]CANDES EJ,WAKIN M B.An introduction to compressive [18]KRISTAN M,PAUGFELDER R,LEONARDIS A,et al.４ Ｃｏｎｃｌｕｓｉｏｎｓ Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｔｏ ｄｅａｌ ｗｉｔｈ ｓｐａｒｓｉｔｙ ａｎｄ ｉｎｓｔａｂｉｌｉｔｙ ｉｎ ｔｈｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ［１０⁃１２］ ａｎｄ ｔｈｅ ｈｉｇｈ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ＮＬＳＳＳＣ⁃ｔｒａｃｋｅｒ ［１１］， ｗｅ ｐｒｏｐｏｓｅ ａ ｎｏｖｅｌ ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ， ｉ．ｅ．， ｔｈｅ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ⁃ｓｔｒｕｃ⁃ ｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ ｂａｓｅｄ ｓｐａｒｓｅ ｃｏｄｉｎｇ （ＥＬＳＳＣ）． Ｏｕｒ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｌ １ ⁃ｔｒａｃｋｅｒ ｗｉｔｈ ａ ｒｅｃｏｎｓｔｒｕｃｔｅｄ ｏｖｅｒ⁃ｃｏｍ⁃ ｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ， ｗｈｉｃｈ ｉｓ ｄｉffｅｒｅｎｔ ｆｒｏｍ ｔｈａｔ ｉｎ ｔｈｅ ｏ⁃ ｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＣ⁃ｔｒａｃｋｅｒ． Ｍｏｒｅｏｖｅｒ， ｗｅ ｓｉｍｐｌｉｆｙ ｔｈｅ ｌａｒｇｅ⁃ｓｃａｌｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｎ ｏｕｒ ｔｒａｃｋｅｒ ｔｏ ａ ｍｕｃｈ ｓｍａｌｌｅｒ ｏｎｅ ｉｎ ｏｕｒ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ⁃ ｔｒａｃｋｅｒ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ， ｏｕｒ ＥＬＳＳＣ⁃ｔｒａｃｋｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｉｎｆｏｒｍａｔｉｏｎ ａ⁃ ｍｏｎｇ ｔｈｅ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｇｅｎｅｒａｔｅｄ ｂｙ ｔｈｅ Ｂａｙｅｓｉａｎ ｉｎｆｅｒｅｎｃｅ ｔｏ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ， ｓｉｍｉｌａｒ ｔｏ ｔｈａｔ ｉｎ ｔｈｅ ＮＬＳＳＳＣ⁃ｔｒａｃｋｅｒ． Ｗｉｔｈ ｏｕｒ ｄｅｒｉｖａｔｉｏｎ， ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｃｅｄｕｒｅ ｏｆ ｏｕｒ ｔｒａｃｋｅｒ （Ｅｑ．（１０）） ｃａｎ ｂｅ ｓｏｌｖｅｄ ａｓ ｔｈａｔ ｉｎ ｔｈｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｂｕｔ ｖｅｒｙ ｄｉffｅｒｅｎｔｌｙ ｆｒｏｍ ｔｈａｔ ｉｎ ｔｈｅ ＮＬＳＳＳＣ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｏｕｒ ｉｍｐｒｏｖｅｄ ｔｒａｃｋｅｒ ｉｓ ｍｕｃｈ ｍｏｒｅ ｅffiｃｉｅｎｔ ｔｈａｎ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＣ⁃ ｔｒａｃｋｅｒ． Ｏｕｒ ｅｘｐｅｒｉｍｅｎｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｓｐａｒｓｉｔｙ， ｓｔａ⁃ ｂｉｌｉｔｙ， ａｎｄ ｅffiｃｉｅｎｃｙ ｏｆ ｏｕｒ ｔｒａｃｋｅｒ． Ｒｅｆｅｒｅｎｃｅｓ ［１］ＺＨＡＮＧ Ｓｈｅｎｇｐｉｎｇ， ＹＡＯ Ｈｏｎｇｘｕｎ， ＳＵＮ Ｘｉｎ， ｅｔ ａｌ． Ｓｐａｒｓｅ ｃｏｄｉｎｇ ｂａｓｅｄ ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ： ｒｅｖｉｅｗ ａｎｄ ｅｘｐｅｒｉｍｅｎｔａｌ ｃｏｍ⁃ ｐａｒｉｓｏｎ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１３， ４６（７）： １７７２⁃１７８８． ［２］ＹＩＬＭＡＺ Ａ， ＪＡＶＥＤ Ｏ， ＳＨＡＨ Ｍ． Ｏｂｊｅｃｔ ｔｒａｃｋｉｎｇ： ａ ｓｕｒ⁃ ｖｅｙ［Ｊ］． ＡＣＭ ｃｏｍｐｕｔｉｎｇ ｓｕｒｖｅｙｓ （ＣＳＵＲ）， ２００６， ３８（４）： １⁃４５． ［３］ＫＡＬＡＬ Ｚ， ＭＩＫＯＬＡＪＣＺＹＫ Ｋ， ＭＡＴＡＳ Ｊ． Ｔｒａｃｋｉｎｇ⁃ｌｅａｒｎ⁃ ｉｎｇ⁃ｄｅｔｅｃｔｉｏｎ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１２， ３４（７）： １４０９⁃１４２２． ［４］ ＡＶＩＤＡＮ Ｓ． Ｅｎｓｅｍｂｌｅ ｔｒａｃｋｉｎｇ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００７， ２９（ ２）： ２６１⁃２７１． ［５］ＢＡＢＥＮＫＯ Ｂ， ＹＡＮＧ Ｍ Ｈ， ＢＥＬＯＮＧＩＥ Ｓ． Ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｉｎｓｔａｎｃｅ ｌｅａｒｎｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉ⁃ ｔｉｏｎ （ＣＶＰＲ）． Ｍｉａｍｉ， ＵＳＡ， ２００９： ９８３⁃９９０． ［６］ＣＡＮＤÈＳ Ｅ Ｊ， ＷＡＫＩＮ Ｍ Ｂ． Ａｎ ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｃｏｍｐｒｅｓｓｉｖｅ ｓａｍｐｌｉｎｇ［Ｊ］． ＩＥＥＥ， ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｍａｇａｚｉｎｅ， ２００８， ２５ （２）： ２１⁃３０． ［７］ ＣＡＮＤÈＳ Ｅ Ｊ， ＲＯＭＢＥＲＧ Ｊ， ＴＡＯ Ｊ． Ｒｏｂｕｓｔ ｕｎｃｅｒｔａｉｎｔｙ ｐｒｉｎｃｉｐｌｅｓ： ｅｘａｃｔ ｓｉｇｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｆｒｏｍ ｈｉｇｈｌｙ ｉｎｃｏｍ⁃ ｐｌｅｔｅ ｆｒｅｑｕｅｎｃｙ ｉｎｆｏｒｍａｔｉｏｎ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｔｈｅｏｒｙ， ２００６， ５２（２）： ４８９⁃５０９． ［８］ ＭＥＩ Ｘｕｅ， ＬＩＮＧ Ｈａｉｂｉｎ， ＷＵ Ｙｉ， ｅｔ ａｌ． Ｍｉｎｉｍｕｍ ｅｒｒｏｒ ｂｏｕｎｄｅｄ ｅｆfiｃｉｅｎｔ ｌ１ ｔｒａｃｋｅｒ ｗｉｔｈ ｏｃｃｌｕｓｉｏｎ ｄｅｔｅｃｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ （ＣＶＰＲ）． Ｃｏｌｏｒａｄｏ， ＵＳＡ， ２０１１：１２５７⁃ １２６４． ［９］ＭＥＩ Ｘｕｅ， ＬＩＮＧ Ｈａｉｂｉｎ． Ｒｏｂｕｓｔ ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ ａｎｄ ｖｅｈｉｃｌｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｖｉａ ｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１１， ３３ （１１）： ２２５９⁃２２７２． ［１０］ ＸＵ Ｈｕａｎ， ＣＡＲＡＭＡＮＩＳ Ｃ， ＭＡＮＮＯＲ Ｓ． Ｓｐａｒｓｅ ａｌｇｏ⁃ ｒｉｔｈｍｓ ａｒｅ ｎｏｔ ｓｔａｂｌｅ： ａ ｎｏ⁃ｆｒｅｅ⁃ｌｕｎｃｈ ｔｈｅｏｒｅｍ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１１， ３４（１）： １８７⁃１９３． ［１１］ＬＵ Ｘｉａｏｑｉａｎｇ， ＹＵＡＮ Ｙｕａｎ， ＬＵ Ｐｉｎｇｋｕｎ， ｅｔ ａｌ． Ｒｏｂｕｓｔ ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｄｉｓｃｒｉｍｉｎａｔｉｖｅ ｓｐａｒｓｅ ｌｅａｒｎｉｎｇ［Ｊ］． Ｐａｔ⁃ ｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１３， ４６（７）： １７６２⁃１７７１． ［１２］ＹＡＮＧ Ｊｉａｎ， ＺＨＡＮＧ Ｌｅｉ， ＸＵ Ｙｏｎｇ， ｅｔ ａｌ． Ｂｅｙｏｎｄ ｓｐａｒｓｉ⁃ ｔｙ： ｔｈｅ ｒｏｌｅ ｏｆ Ｌ１ ⁃ｏｐｔｉｍｉｚｅｒ ｉｎ ｐａｔｔｅｒｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１２， ４５（３）： １１０４⁃１１１８． ［１３］ＤＡＵＢＥＣＨＩＥＳ Ｉ， ＤＥＦＲＩＳＥ Ｍ， ＤＥ ＭＯＬ Ｃ． Ａｎ ｉｔｅｒａｔｉｖｅ ｔｈｒｅｓｈｏｌｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌｉｎｅａｒ ｉｎｖｅｒｓｅ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ａ ｓｐａｒｓｉｔｙ ｃｏｎｓｔｒａｉｎｔ［ Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｎ ｐｕｒｅ ａｎｄ ａｐ⁃ ｐｌｉｅｄ ｍａｔｈｅｍａｔｉｃｓ， ２００４， ５７（１１）： １４１３⁃１４５７． ［１４］ＲＯＳＳ Ｄ Ａ， ＬＩＭ Ｊ， ＬＩＮ Ｒ Ｓ， ｅｔ ａｌ． Ｉｎｃｒｅｍｅｎｔａｌ ｌｅａｒｎｉｎｇ ｆｏｒ ｒｏｂｕｓｔ ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ｖｉｓｉｏｎ， ２００８， ７７（１⁃３）： １２５⁃１４１． ［１５］ＰＯＲＩＫＬＩ Ｆ， ＴＵＺＥＬ Ｏ， ＭＥＥＲ Ｐ． Ｃｏｖａｒｉａｎｃｅ ｔｒａｃｋｉｎｇ ｕ⁃ ｓｉｎｇ ｍｏｄｅｌ ｕｐｄａｔｅ ｂａｓｅｄ ｏｎ ｌｉｅ ａｌｇｅｂｒａ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００６： ７２８⁃ ７３５． ［１６］ＥＶＥＲＩＮＧＨＡＭ Ｍ， ＶＡＮ ＧＯＯＬ Ｌ， ＷＩＬＬＩＡＭＳ Ｃ Ｋ Ｉ， ｅｔ ａｌ． Ｔｈｅ ｐａｓｃａｌ ｖｉｓｕａｌ ｏｂｊｅｃｔ ｃｌａｓｓｅｓ （ＶＯＣ） ｃｈａｌｌｅｎｇｅ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ， ２０１０， ８８ （ ２）： ３０３⁃３３８． ［１７］ＷＵ Ｙｉ， ＬＩＭ Ｊ， ＹＡＮＧ Ｍ Ｈ． Ｏｎｌｉｎｅ ｏｂｊｅｃｔ ｔｒａｃｋｉｎｇ： Ａ ｂｅｎｃｈｍａｒｋ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ⁃ ｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ （ＣＶＰＲ）． Ｐｏｒｔｌａｎｄ， ＵＳＡ， ２０１３： ２４１１⁃２４１８． ［１８］ ＫＲＩＳＴＡＮ Ｍ， ＰflＵＧＦＥＬＤＥＲ Ｒ， ＬＥＯＮＡＲＤＩＳ Ａ， ｅｔ ａｌ． ·１４６· 智 能 系 统 学 报 第 １１ 卷