【知识工程】Efficient tracker based on sparse coding with Euclidean local structure-based constraint编辑部

第11卷第1期 智能系统学报 Vol.11 No.1 2016年2月 CAAI Transactions on Intelligent Systems Feh.2016 D0I:10.11992/is.201507073 网络出版地址：htp:/www.cmki.net/kcms/detail/23.1538.tp.201509030.1456.002.html Efficient tracker based on sparse coding with Euclidean local structure-based constraint WANG Hongyuan',ZHANG Ji',CHEN Fuhua2 (1.School of Information Science and Engineering,Changzhou University,Changzhou,Jiangsu,China 213164;2.Department of Nat- ural Science and Mathematics,West Liberty University,West Virginia,United States 26074) Abstract:Sparse coding (SC)based visual tracking(I-tracker)is gaining increasing attention,and many related algorithms are developed.In these algorithms,each candidate region is sparsely represented as a set of target tem- plates.However,the structure connecting these candidate regions is usually ignored.Lu proposed an NLSSC-tracker with non-local self-similarity sparse coding to address this issue,which has a high computational cost.In this study, we propose an Euclidean local-structure constraint based sparse coding tracker with a smoothed Euclidean local structure.With this tracker,the optimization procedure is transformed to a small-scale I,-optimization problem,sig- nificantly reducing the computational cost.Extensive experimental results on visual tracking demonstrate the effectiveness and efficiency of the proposed algorithm. Keywords:euclidean local-structure constraint;I,-tracker;sparse coding;target tracking CLC Number:TP18;TP301.6 Document Code:A Article ID:1673-4785(2016)01-0136-12 Citation:WANG Hongyuan,ZHANG Ji,CHEN Fuhua.Efficient tracker based on sparse coding with Euclidean local struc- ture-based constraint[J].CAAI Transactions on Intelligent Systems,2016,11(1):136-147. Recently,visual target tracking was widely used Based on sparse coding (SC;also referred to as in security surveillance,navigation,human-computer sparse sensing or compressive sensing)(7,Mei pro- interaction,and other applications(2.In a video se- posed an I-tracker for generative trackings,ad- quence,targets for tracking often change dynamically dressing occlusion,corruption,and some other chal- and uncertainly because of disturbance phenomena lenging issues.However,this tracker incurs a very such as occlusion,noisy and varying illumination,and high computational cost to achieve efficient tracking object appearance.Many tracking algorithms were pro- (see section 2.1 and Fig.1 for details),and the local posed in the last twenty years that can be divided into structures of similar regions are ignored,which may two categories:generative tracking and discriminant cause the instability and even failure of the I-tracker. tracking algorithms Generative algorithms (e.g., Indeed,the sparse coefficients,for representing six eigen tracker,mean-shift tracker,incremental tracker, similar regions (CR-CR)under ten template regions covariance tracker[2])adopt appearance models to ex- (T-To)with original l,-tracker,are diversified (Fig. press the target observations,whereas discriminant al- 3).Considering CR,and CR,for example,we can gorithms (e.g.,TLD3],ensemble tracking,and see that although the latter is almost the partial occlu- MILTrack[s])view tracking as a classification prob- sion version of the former,their sparse representations lem,thus attempting to distinguish the target from the are very different.Tracking CR(the woman's face) backgrounds.Here,we present a new generative algo- may fail,because the tracker is likely to incorrectly rithm. consider the region Ts(the book)as its target. Received Date:2015-07-31.Online Pulication:2015-09-30. Contrary to expectations,Xu proved that a sparse Foundation Item:National Natural Foundation of China under Grant (61572085,61502058). algorithm cannot be stable and that similar signals may Corresponding Author:Hongyuan Wang.E-mail:hywang@cczu.edu.cn. not exhibit similar sparse coefficients Thus,a

第 １１ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．１ ２０１６ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０７０７３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０９０３０．１４５６．００２．ｈｔｍｌ Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ＷＡＮＧ Ｈｏｎｇｙｕａｎ １ ， ＺＨＡＮＧ Ｊｉ １ ， ＣＨＥＮ Ｆｕｈｕａ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｃｈａｎｇｚｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｈａｎｇｚｈｏｕ， Ｊｉａｎｇｓｕ， Ｃｈｉｎａ ２１３１６４； ２． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｎａｔ⁃ ｕｒａｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｍａｔｈｅｍａｔｉｃｓ， Ｗｅｓｔ Ｌｉｂｅｒｔｙ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｅｓｔ Ｖｉｒｇｉｎｉａ， Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ２６０７４） Ａｂｓｔｒａｃｔ：Ｓｐａｒｓｅ ｃｏｄｉｎｇ （ＳＣ） ｂａｓｅｄ ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ （ｌ １ ⁃ｔｒａｃｋｅｒ） ｉｓ ｇａｉｎｉｎｇ ｉｎｃｒｅａｓｉｎｇ ａｔｔｅｎｔｉｏｎ， ａｎｄ ｍａｎｙ ｒｅｌａｔｅｄ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｄｅｖｅｌｏｐｅｄ． Ｉｎ ｔｈｅｓｅ ａｌｇｏｒｉｔｈｍｓ， ｅａｃｈ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎ ｉｓ ｓｐａｒｓｅｌｙ ｒｅｐｒｅｓｅｎｔｅｄ ａｓ ａ ｓｅｔ ｏｆ ｔａｒｇｅｔ ｔｅｍ⁃ ｐｌａｔｅｓ． Ｈｏｗｅｖｅｒ， ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｃｏｎｎｅｃｔｉｎｇ ｔｈｅｓｅ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｉｓ ｕｓｕａｌｌｙ ｉｇｎｏｒｅｄ． Ｌｕ ｐｒｏｐｏｓｅｄ ａｎ ＮＬＳＳＣ⁃ｔｒａｃｋｅｒ ｗｉｔｈ ｎｏｎ⁃ｌｏｃａｌ ｓｅｌｆ⁃ｓｉｍｉｌａｒｉｔｙ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｔｏ ａｄｄｒｅｓｓ ｔｈｉｓ ｉｓｓｕｅ， ｗｈｉｃｈ ｈａｓ ａ ｈｉｇｈ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｓｔ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｗｅ ｐｒｏｐｏｓｅ ａｎ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ⁃ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ ｂａｓｅｄ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｔｒａｃｋｅｒ ｗｉｔｈ ａ ｓｍｏｏｔｈｅｄ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ． Ｗｉｔｈ ｔｈｉｓ ｔｒａｃｋｅｒ， ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｃｅｄｕｒｅ ｉｓ ｔｒａｎｓｆｏｒｍｅｄ ｔｏ ａ ｓｍａｌｌ⁃ｓｃａｌｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ， ｓｉｇ⁃ ｎｉｆｉｃａｎｔｌｙ ｒｅｄｕｃｉｎｇ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｓｔ． Ｅｘｔｅｎｓｉｖｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ｖｉｓｕａｌ ｔｒａｃｋｉｎｇ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅffｅｃｔｉｖｅｎｅｓｓ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ⁃ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ； ｌ １ ⁃ｔｒａｃｋｅｒ； ｓｐａｒｓｅ ｃｏｄｉｎｇ； ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ＣＬＣ Ｎｕｍｂｅｒ：ＴＰ１８； ＴＰ３０１．６ Ｄｏｃｕｍｅｎｔ Ｃｏｄｅ：Ａ Ａｒｔｉｃｌｅ ＩＤ：１６７３⁃４７８５（２０１６）０１⁃０１３６⁃１２ Ｃｉｔａｔｉｏｎ：ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ＺＨＡＮＧ Ｊｉ， ＣＨＥＮ Ｆｕｈｕａ． Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃ⁃ ｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（１）： １３６⁃１４７． Ｒｅｃｅｉｖｅｄ Ｄａｔｅ：２０１５⁃０７⁃３１． Ｏｎｌｉｎｅ Ｐｕｌｉｃａｔｉｏｎ：２０１５⁃０９⁃３０． Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍ： Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒａｎｔ （６１５７２０８５，６１５０２０５８）． Ｃｏｒｒｅｓｐｏｎｄｉｎｇ Ａｕｔｈｏｒ：Ｈｏｎｇｙｕａｎ Ｗａｎｇ． Ｅ⁃ｍａｉｌ： ｈｙｗａｎｇ＠ ｃｃｚｕ．ｅｄｕ．ｃｎ． Ｒｅｃｅｎｔｌｙ， ｖｉｓｕａｌ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ｗａｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｓｅｃｕｒｉｔｙ ｓｕｒｖｅｉｌｌａｎｃｅ， ｎａｖｉｇａｔｉｏｎ， ｈｕｍａｎ⁃ｃｏｍｐｕｔｅｒ ｉｎｔｅｒａｃｔｉｏｎ， ａｎｄ ｏｔｈｅｒ ａｐｐｌｉｃａｔｉｏｎｓ ［１⁃２］ ． Ｉｎ ａ ｖｉｄｅｏ ｓｅ⁃ ｑｕｅｎｃｅ， ｔａｒｇｅｔｓ ｆｏｒ ｔｒａｃｋｉｎｇ ｏｆｔｅｎ ｃｈａｎｇｅ ｄｙｎａｍｉｃａｌｌｙ ａｎｄ ｕｎｃｅｒｔａｉｎｌｙ ｂｅｃａｕｓｅ ｏｆ ｄｉｓｔｕｒｂａｎｃｅ ｐｈｅｎｏｍｅｎａ ｓｕｃｈ ａｓ ｏｃｃｌｕｓｉｏｎ， ｎｏｉｓｙ ａｎｄ ｖａｒｙｉｎｇ ｉｌｌｕｍｉｎａｔｉｏｎ， ａｎｄ ｏｂｊｅｃｔ ａｐｐｅａｒａｎｃｅ． Ｍａｎｙ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｗｅｒｅ ｐｒｏ⁃ ｐｏｓｅｄ ｉｎ ｔｈｅ ｌａｓｔ ｔｗｅｎｔｙ ｙｅａｒｓ ｔｈａｔ ｃａｎ ｂｅ ｄｉｖｉｄｅｄ ｉｎｔｏ ｔｗｏ ｃａｔｅｇｏｒｉｅｓ： ｇｅｎｅｒａｔｉｖｅ ｔｒａｃｋｉｎｇ ａｎｄ ｄｉｓｃｒｉｍｉｎａｎｔ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍｓ ［１⁃２］ ． Ｇｅｎｅｒａｔｉｖｅ ａｌｇｏｒｉｔｈｍｓ （ ｅ． ｇ．， ｅｉｇｅｎ ｔｒａｃｋｅｒ， ｍｅａｎ⁃ｓｈｉｆｔ ｔｒａｃｋｅｒ， ｉｎｃｒｅｍｅｎｔａｌ ｔｒａｃｋｅｒ， ｃｏｖａｒｉａｎｃｅ ｔｒａｃｋｅｒ ［２］ ） ａｄｏｐｔ ａｐｐｅａｒａｎｃｅ ｍｏｄｅｌｓ ｔｏ ｅｘ⁃ ｐｒｅｓｓ ｔｈｅ ｔａｒｇｅｔ ｏｂｓｅｒｖａｔｉｏｎｓ， ｗｈｅｒｅａｓ ｄｉｓｃｒｉｍｉｎａｎｔ ａｌ⁃ ｇｏｒｉｔｈｍｓ （ ｅ． ｇ．， ＴＬＤ ［３］ ， ｅｎｓｅｍｂｌｅ ｔｒａｃｋｉｎｇ ［４］ ， ａｎｄ ＭＩＬＴｒａｃｋ ［５］ ） ｖｉｅｗ ｔｒａｃｋｉｎｇ ａｓ ａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍ， ｔｈｕｓ ａｔｔｅｍｐｔｉｎｇ ｔｏ ｄｉｓｔｉｎｇｕｉｓｈ ｔｈｅ ｔａｒｇｅｔ ｆｒｏｍ ｔｈｅ ｂａｃｋｇｒｏｕｎｄｓ． Ｈｅｒｅ， ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗ ｇｅｎｅｒａｔｉｖｅ ａｌｇｏ⁃ ｒｉｔｈｍ． Ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ （ ＳＣ； ａｌｓｏ ｒｅｆｅｒｒｅｄ ｔｏ ａｓ ｓｐａｒｓｅ ｓｅｎｓｉｎｇ ｏｒ ｃｏｍｐｒｅｓｓｉｖｅ ｓｅｎｓｉｎｇ） ［６⁃７］ ， Ｍｅｉ ｐｒｏ⁃ ｐｏｓｅｄ ａｎ ｌ １ ⁃ｔｒａｃｋｅｒ ｆｏｒ ｇｅｎｅｒａｔｉｖｅ ｔｒａｃｋｉｎｇ ［８⁃９］ ， ａｄ⁃ ｄｒｅｓｓｉｎｇ ｏｃｃｌｕｓｉｏｎ， ｃｏｒｒｕｐｔｉｏｎ， ａｎｄ ｓｏｍｅ ｏｔｈｅｒ ｃｈａｌ⁃ ｌｅｎｇｉｎｇ ｉｓｓｕｅｓ． Ｈｏｗｅｖｅｒ， ｔｈｉｓ ｔｒａｃｋｅｒ ｉｎｃｕｒｓ ａ ｖｅｒｙ ｈｉｇｈ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｓｔ ｔｏ ａｃｈｉｅｖｅ ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｉｎｇ （ｓｅｅ ｓｅｃｔｉｏｎ ２．１ ａｎｄ Ｆｉｇ．１ ｆｏｒ ｄｅｔａｉｌｓ）， ａｎｄ ｔｈｅ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅｓ ｏｆ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ ａｒｅ ｉｇｎｏｒｅｄ， ｗｈｉｃｈ ｍａｙ ｃａｕｓｅ ｔｈｅ ｉｎｓｔａｂｉｌｉｔｙ ａｎｄ ｅｖｅｎ ｆａｉｌｕｒｅ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ． Ｉｎｄｅｅｄ， ｔｈｅ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ， ｆｏｒ ｒｅｐｒｅｓｅｎｔｉｎｇ ｓｉｘ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ （ＣＲ１ －ＣＲ６ ） ｕｎｄｅｒ ｔｅｎ ｔｅｍｐｌａｔｅ ｒｅｇｉｏｎｓ （ Ｔ１ －Ｔ１０ ） ｗｉｔｈ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ， ａｒｅ ｄｉｖｅｒｓｉｆｉｅｄ （Ｆｉｇ． ３）． Ｃｏｎｓｉｄｅｒｉｎｇ ＣＲ１ ａｎｄ ＣＲ４ ， ｆｏｒ ｅｘａｍｐｌｅ， ｗｅ ｃａｎ ｓｅｅ ｔｈａｔ ａｌｔｈｏｕｇｈ ｔｈｅ ｌａｔｔｅｒ ｉｓ ａｌｍｏｓｔ ｔｈｅ ｐａｒｔｉａｌ ｏｃｃｌｕ⁃ ｓｉｏｎ ｖｅｒｓｉｏｎ ｏｆ ｔｈｅ ｆｏｒｍｅｒ， ｔｈｅｉｒ ｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ ａｒｅ ｖｅｒｙ ｄｉｆｆｅｒｅｎｔ． Ｔｒａｃｋｉｎｇ ＣＲ４ （ ｔｈｅ ｗｏｍａｎ􀆳ｓ ｆａｃｅ） ｍａｙ ｆａｉｌ， ｂｅｃａｕｓｅ ｔｈｅ ｔｒａｃｋｅｒ ｉｓ ｌｉｋｅｌｙ ｔｏ ｉｎｃｏｒｒｅｃｔｌｙ ｃｏｎｓｉｄｅｒ ｔｈｅ ｒｅｇｉｏｎ Ｔ８（ｔｈｅ ｂｏｏｋ） ａｓ ｉｔｓ ｔａｒｇｅｔ． Ｃｏｎｔｒａｒｙ ｔｏ ｅｘｐｅｃｔａｔｉｏｎｓ， Ｘｕ ｐｒｏｖｅｄ ｔｈａｔ ａ ｓｐａｒｓｅ ａｌｇｏｒｉｔｈｍ ｃａｎｎｏｔ ｂｅ ｓｔａｂｌｅ ａｎｄ ｔｈａｔ ｓｉｍｉｌａｒ ｓｉｇｎａｌｓ ｍａｙ ｎｏｔ ｅｘｈｉｂｉｔ ｓｉｍｉｌａｒ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ ［１０］ ． Ｔｈｕｓ， ａ

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

ｔｒａｄｅ⁃ｏｆｆ ｏｃｃｕｒｓ ｂｅｔｗｅｅｎ ｓｐａｒｓｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｗｈｅｎ ｄｅ⁃ ｓｉｇｎｉｎｇ ａ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｉｎ ａｄｄｉｔｉｏｎ， ｉｎｓｔａｂｉｌｉｔｙ ｉｎ ｔｈｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ａｆｆｅｃｔｓ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ． Ｌｕ ｄｅｖｅｌｏｐｅｄ ａ ＮＬＳＳＳ⁃ｔｒａｃｋｅｒ （ＮＬＳＳＳＴ） ｂａｓｅｄ ｏｎ ＳＣ ａｐｐｌｙｉｎｇ ａ ｎｏｎ⁃ｌｏｃａｌ ｓｅｌｆ⁃ｓｉｍｉｌａｒｉｔｙ ｃｏｎｓｔｒａｉｎｔ ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ｇｅｏｍｅｔｒｉｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｓｅｔ ｏｆ ｃａｎｄｉｄａｔｅｓ ａｓ ａ ｓｍｏｏｔｈｉｎｇ ｔｅｒｍ ｔｏ ａｌｌｅｖｉａｔｅ ｔｈｅ ｉｎｓｔａｂｉｌ⁃ ｉｔｙ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ［１１］ ． Ｈｏｗｅｖｅｒ， ｉｔｓ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ （ｅ⁃ ｖｅｎ ｓｌｏｗｅｒ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ， Ｔａｂｌｅ ４） ｒｅ⁃ ｓｔｒｉｃｔｓ ｉｔｓ ａｐｐｌｉｃａｂｉｌｉｔｙ ｉｎ ｒｅａｌ⁃ｔｉｍｅ ｔｒａｃｋｉｎｇ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｍｏｔｉｖａｔｅｄ ｂｙ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ｓｔａｂｉｌｉｔｙ ｏｆ ＮＬＳＳＳＴ， ｗｅ ｐｒｏｐｏｓｅ ａ ｎｏｖｅｌ ｔｒａｃｋｅｒ， ｃａｌｌｅｄ ＥＬＳＳ⁃ｔｒａｃｋｅｒ （ＥＬＳＳＴ）， ｔｈａｔ ｉｓ ｂｏｔｈ ｒｏｂｕｓｔ ａｎｄ ｅｆｆｉｃｉｅｎｔ． Ｔｈｅ ｍａｉｎ ｃｏｎｔｒｉｂｕｔｉｏｎｓ ｏｆ ｔｈｉｓ ｓｔｕｄｙ ａｒｅ ａｓ ｆｏｌｌｏｗｓ： １）Ａｎ ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ， ｉ．ｅ．， ＥＬＳＳＴ， ｉｓ ｄｅｖｅｌｏｐｅｄ ｂｙ ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ ｓｅｔ ｏｆ ｔａｒｇｅｔ ｃａｎｄｉｄａｔｅｓ． Ｉｎ ｃｏｎｔｒａｓｔ ｔｏ ｔｈｅ Ｌｕ５ｓ ［１１］ ａｎｄ Ｍｅｉ５ｓ⁃ｔｒａｃｋ⁃ ｅｒ ［８⁃９］ ， ｏｕｒ ｔｒａｃｋｅｒ ｉｓ ｍｏｒｅ ｓｔａｂｌｅ ａｎｄ ｓｐａｒｓｅ． ２） Ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｒａｃｋｅｒ ｓｈｏｗｓ ｅｘｃｅｌｌｅｎｔ ｐｅｒｆｏｒｍ⁃ ａｎｃｅ ｉｎ ｔｒａｃｋｉｎｇ ｄｉｆｆｅｒｅｎｔ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｒｅｇａｒｄ ｔｏ ｓｃａｌｅ， ｏｃｃｌｕｓｉｏｎ， ｐｏｓｅ ｖａｒｉａｔｉｏｎｓ， ｂａｃｋｇｒｏｕｎｄ ｃｌｕｔ⁃ ｔｅｒ， ａｎｄ ｉｌｌｕｍｉｎａｔｉｏｎ ｃｈａｎｇｅｓ． Ｔｈｅ ｒｅｓｔ ｏｆ ｔｈｉｓ ｓｔｕｄｙ ｉｓ ｏｒｇａｎｉｚｅｄ ａｓ ｆｏｌｌｏｗｓ： ｌ １ ⁃ ａｎｄ ＮＬＳＳＳ⁃ｔｒａｃｋｅｒ ａｒｅ ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｓｅｃｔｉｏｎ ２； ｉｎ ｓｅｃ⁃ ｔｉｏｎ ３， ｗｅ ａｎａｌｙｚｅ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅｓｅ ｔｗｏ ｔｒａｃｋ⁃ ｅｒｓ ａｎｄ ｐｒｏｐｏｓｅ ｏｕｒ ｔｒａｃｋｅｒ； ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｗｉｔｈ ｏｕｒ ｔｒａｃｋｅｒ ａｎｄ ｆｏｕｒ ｃｏｍｐａｒｉｓｏｎ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｒｅｐｏｒｔｅｄ ｉｎ ｓｅｃｔｉｏｎ ４； ｔｈｅ ｃｏｎｃｌｕｓｉｏｎ ａｎｄ ｆｕｔｕｒｅ ｗｏｒｋ ａｒｅ ｓｕｍ⁃ ｍａｒｉｚｅｄ ｉｎ ｓｅｃｔｉｏｎ ５． １ Ｒｅｌａｔｅｄ ｗｏｒｋｓ １．１ Ｓｐａｒｓｅ ｃｏｄｉｎｇ ａｎｄ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ Ｓｐａｒｓｅ ｃｏｄｉｎｇ ｉｓ ａｎ ａｔｔｒａｃｔｉｖｅ ｓｉｇｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄ ｐｒｏｐｏｓｅｄ ｂｙ Ｃａｎｄｅｓ ［６⁃７］ ｔｈａｔ ｒｅｃｏｎｓｔｒｕｃｔｓ ａ ｓｉｇ⁃ ｎａｌ ｙ ∈ Ｒ ｍ×１ ｗｉｔｈ ａｎ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ ∈ Ｒ ｍ×（ｎ＋２ｍ） ｗｉｔｈ ａ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔ ｖｅｃｔｏｒｃ ∈ Ｒ ｎ×１ ． Ｔｈｅ ＳＣ ｆｏｒｍｕｌａｔｉｏｎ ｃａｎ ｂｅ ｗｒｉｔｔｅｎ ａｓ ｔｈｅ ｌ ０ ⁃ｎｏｒｍ⁃ｃｏｎｓｔｒａｉｎ⁃ ｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ａｓ ｆｏｌｌｏｗｓ： ｍｉｎｃ‖ｙ － Ｄｃ‖２ Ｆ ＋ α‖ｃ‖０ （１） ｗｈｉｃｈ ｉｓ ＮＰ⁃ｈａｒｄ， ｗｈｅｒｅ ‖·‖Ｆ ｄｅｎｏｔｅｓ ｔｈｅ ｖｅｃｔｏｒ’ｓ Ｆｒｏｂｅｎｉｕｓ ｎｏｒｍ （ ｉ． ｅ．， ｌ ２ ⁃ｎｏｒｍ）， ａｎｄ ‖·‖０ ｃｏｕｎｔｓ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｎｏｎ⁃ｚｅｒｏ ｅｌｅｍｅｎｔｓ ｏｆ ｔｈｅ ｖｅｃｔｏｒ． Ｃａｎｄｅｓ ｐｒｏｖｅｄ ｔｈａｔ ｔｈｅ ｌ １ ⁃ｎｏｒｍ ‖·‖１ ｉｓ ｔｈｅ ｔｉｇｈｔｅｓｔ ｕｐｐｅｒ ｂｏｕｎｄ ｏｆ ｔｈｅ ｌ ０ ⁃ｎｏｒｍ ‖·‖０ ， ａｎｄ ｔｈｕｓ， Ｅｑ．（１） ｃａｎ ｂｅ ｒｅｗｒｉｔｔｅｎ ａｓ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍ ［６⁃７］ ： ｍｉｎｃ ‖ｙ － Ｄｃ‖２ Ｆ ＋ α ‖ｃ‖１ （２） Ｂａｓｅｄ ｏｎ ＳＣ， Ｍｅｉ ｐｒｅｓｅｎｔｅｄ ａ ｎｉｃｅ ｌ １ ⁃ｔｒａｃｋｅｒ ｆｏｒ ｒｏｂｕｓｔ ｔｒａｃｋｉｎｇ ［８⁃９］ （Ｆｉｇ． １）． Ｃｏｎｓｉｄｅｒｉｎｇ ｔｈａｔ ｔｈｅ ｔａｒｇｅｔ ｉｓ ｌｏｃａｔｅｄ ｉｎ ｔｈｅ ｌａｔｅｓｔ ｆｒａｍｅ， ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ｉｓ ｉｎｉｔｉａｌ⁃ ｉｚｅｄ ｉｎ ｔｈｅ ｎｅｗ ａｒｒｉｖａｌ ｆｒａｍｅ ａｎｄ Ｎ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ａｒｅ ｇｅｎｅｒａｔｅｄ ｗｉｔｈ Ｂａｙｅｓｉａｎ ｉｎｆｅｒｅｎｃｅ （ Ｆｉｇ． １ａ， ｂ）． Ｗｉｔｈ ｎ ｔｅｍｐｌａｔｅｓ ｌｅａｒｎｅｄ ｆｒｏｍ ｐｒｅｖｉｏｕｓ ｔｒａｃｋｉｎｇ ａｎｄ ２ｍ ｔｒｉｖｉａｌ ｔｅｍｐｌａｔｅｓ （ｍ ｐｏｓｉｔｉｖｅ ｏｎｅｓ ａｎｄ ｍ ｎｅｇａｔｉｖｅ ｏｎｅｓ， ｗｈｅｒｅ ｍ ｉｓ ｔｈｅ ｄｉｍｅｎｓｉｏｎ ｏｆ １Ｄ ｓｔｒｅｔｃｈｅｄ ｉｍａｇｅ， Ｆｉｇ． １ｃ）， Ｅｑ．（２） ｃａｎ ｂｅ ｓｏｌｖｅｄ （Ｆｉｇ． １ｄ，ｅ，ｆ）． Ｗｉｔｈ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｔｒｉｖｉａｌ ｔｅｍｐｌａｔｅｓ， Ｍｅｉ ａｄｄｅｄ ａ ｎｏｎ⁃ｎｅｇａｔｉｖｅ ｃｏｎｓｔｒａｉｎｔ ｃ≥０ ｉｎ Ｅｑ． （２）， ｗｉｔｈ ｗｈｉｃｈ ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｅｒｒｏｒｓ ｏｆ ａｌｌ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｗｉｔｈ ＳＣ ｃｏｅｆｆｉｃｉｅｎｔｓ ｃａｎ ｂｅ ｕｓｅｄ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｗｅｉｇｈｔｓ ｆｏｒ ｅａｃｈ ｃａｎｄｉｄａｔｅ， ａｎｄ ｔｈｅ ｏｂｊｅｃｔ ｉｎ ｔｈｅ ｎｅｗ ａｒｒｉｖａｌ ｆｒａｍｅ ｃａｎ ｂｅ ｌｏｃａｔｅｄ ｗｉｔｈ ｔｈｅ ｓｕｍ ｏｆ ｔｈｅ ｗｅｉｇｈｔｅｄ ｃａｎｄｉｄａｔｅｓ． Ｔｈｅ ｄｉｃｔｉｏｎａｒｉｅｓ ｕｐｄａｔｉｎｇ ｓｔｒａｔｅｇｉｅｓ ｃａｎ ｂｅ ｓｅｅｎ ｉｎ ［８⁃９］ ． Ｆｉｇ．１ Ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ ａｌｇｏｒｉｔｈｍ 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１３７·

·138. 智能系统学报 第11卷 1.2 Non-local self-similarity based sparse coding rameter enforcing similarity,and s,is the normalization for tracking (NLSSST) factor.The weight measures the similarity between Recently,Xu indicated the trade-off between the K-neighborhood of y;and y:.Lu's algorithm actual- sparsity and stability in sparse regularized algo- ly attempts to solve the following: rithms[].Moreover,Yang pointed out the same A-op- timization issue in pattern classification Based on minc I Y-DC+a cll+B II C-CWIl the fact that lots of similar regions exist in all N candi- (4) dates generated by Bayesian inference,Lu proposed Taking the solution of the I-tracker from Eq.(2) his tracker with the non-local self-similarity constraint as the initial coefficients co,Eq.(4)can be solved as 含s-含6P=1c-cw1 through iterative computations.However,the high (3) computational cost of the original I,-tracker and itera- i=1 where c;and c,are the sparse coefficients corresponding tive procedure for maintaining the neighborhood con- to the candidate regions y;and y,respectively,and w straints of sparse coefficients make NLSSST inefficient is the weight assigned to c.Given N m-dimensional in achieving real-timing tracking.In contrast to Fig.1, candidates Y=[y.yx]E RTxN,the first K-closest the schematic diagram of NLSSST presented in Fig.2, candidate point aroundy,is denoted by N(y),and includes an additional neighborhood constraint between 1_Iwy-W2☑ the weight w=一e where h is a pa- y;and N(y:). target template T trival template t 图图 (a)N Candidate regions (b)Over-complete dictionary Cr∈RxN C+∈RmxN C∈RmxN with sparity yNx()y\{y,N(y》 constraint min c (c)Sample (d)Dictionaries (e)Coefficient of representation Fig.2 Lu's NLSSST Algorithm 2 Euclidean local structure-based sparse known that the 12-norm is much more commonly used for measuring the distance between two vectors and is coding for tracking (ELSST) much easier to optimize than the I-norm.Thus,we To circumvent the heavy computation burden of take the former to measure the relationships between the 1-tracker and NISSST (Table 4),we propose an the sparse coefficient vectors,which are close to each efficient tracker,called ELSST,that considers the lo- other,i.e.,the Euclidean local-structure constraint, cal Euclidean structures of the candidates. and the latter I-norm of C to maintain the sparsity of 2.1 Original euclidean local structure constraint the optimization as follows: sparse coding Original ELSSC) It is evident from Eq.(4)that NLSSST attempts minc I Y-DC+a C+B I C-CWll to solve a double I-norm problem.However,it is well (5)

１．２ Ｎｏｎ⁃ｌｏｃａｌ ｓｅｌｆ⁃ｓｉｍｉｌａｒｉｔｙ ｂａｓｅｄ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｆｏｒ ｔｒａｃｋｉｎｇ （ＮＬＳＳＳＴ） Ｒｅｃｅｎｔｌｙ， Ｘｕ ｉｎｄｉｃａｔｅｄ ｔｈｅ ｔｒａｄｅ⁃ｏｆｆ ｂｅｔｗｅｅｎ ｓｐａｒｓｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｉｎ ｓｐａｒｓｅ ｒｅｇｕｌａｒｉｚｅｄ ａｌｇｏ⁃ ｒｉｔｈｍｓ ［１０］ ． Ｍｏｒｅｏｖｅｒ， Ｙａｎｇ ｐｏｉｎｔｅｄ ｏｕｔ ｔｈｅ ｓａｍｅ Ａ⁃ｏｐ⁃ ｔｉｍｉｚａｔｉｏｎ ｉｓｓｕｅ ｉｎ ｐａｔｔｅｒｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［１２］ ． Ｂａｓｅｄ ｏｎ ｔｈｅ ｆａｃｔ ｔｈａｔ ｌｏｔｓ ｏｆ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ ｅｘｉｓｔ ｉｎ ａｌｌ Ｎ ｃａｎｄｉ⁃ ｄａｔｅｓ ｇｅｎｅｒａｔｅｄ ｂｙ Ｂａｙｅｓｉａｎ ｉｎｆｅｒｅｎｃｅ， Ｌｕ ｐｒｏｐｏｓｅｄ ｈｉｓ ｔｒａｃｋｅｒ ｗｉｔｈ ｔｈｅ ｎｏｎ⁃ｌｏｃａｌ ｓｅｌｆ⁃ｓｉｍｉｌａｒｉｔｙ ｃｏｎｓｔｒａｉｎｔ ａｓ ∑ ｎ ｉ ＝ １ ｃｉ － ∑ Ｋ ｊ ＝ １ ｗｊｉ ｃｊ ２ ＝ ‖Ｃ － ＣＷ‖２ Ｆ （３） ｗｈｅｒｅ ｃｉ ａｎｄ ｃｊ ａｒｅ ｔｈｅ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｏ ｔｈｅ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｙｉ ａｎｄ ｙｊ， ｒｅｓｐｅｃｔｉｖｅｌｙ， ａｎｄ ｗｊｉ ｉｓ ｔｈｅ ｗｅｉｇｈｔ ａｓｓｉｇｎｅｄ ｔｏ ｃｊ ． Ｇｉｖｅｎ Ｎ ｍ⁃ｄｉｍｅｎｓｉｏｎａｌ ｃａｎｄｉｄａｔｅｓ Ｙ ＝ ｙ１ … ｙＮ [ ] ∈ Ｒ ｍ×Ｎ ， ｔｈｅ ｆｉｒｓｔ Ｋ⁃ｃｌｏｓｅｓｔ ｃａｎｄｉｄａｔｅ ｐｏｉｎｔ ａｒｏｕｎｄｙｊ ｉｓ ｄｅｎｏｔｅｄ ｂｙ ＮＫ （ ｙｊ ）， ａｎｄ ｔｈｅ ｗｅｉｇｈｔ ｗｊｉ ＝ １ ｓｊ ｅ － ‖ＮＫ （ｙ ｊ ） －ＮＫ （ｙ ｉ ）‖２ ｈ ， ｗｈｅｒｅ ｈ ｉｓ ａ ｐａ⁃ ｒａｍｅｔｅｒ ｅｎｆｏｒｃｉｎｇ ｓｉｍｉｌａｒｉｔｙ， ａｎｄ ｓｊ ｉｓ ｔｈｅ ｎｏｒｍａｌｉｚａｔｉｏｎ ｆａｃｔｏｒ． Ｔｈｅ ｗｅｉｇｈｔ ｗｊｉ ｍｅａｓｕｒｅｓ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｂｅｔｗｅｅｎ ｔｈｅ Ｋ⁃ｎｅｉｇｈｂｏｒｈｏｏｄ ｏｆ ｙｊ ａｎｄ ｙｉ ． Ｌｕ’ｓ ａｌｇｏｒｉｔｈｍ ａｃｔｕａｌ⁃ ｌｙ ａｔｔｅｍｐｔｓ ｔｏ ｓｏｌｖｅ ｔｈｅ ｆｏｌｌｏｗｉｎｇ： ｍｉｎＣ ‖Ｙ － ＤＣ‖２ Ｆ ＋ α ‖Ｃ‖１ ＋ β ‖Ｃ － ＣＷ‖１ （４） Ｔａｋｉｎｇ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ｆｒｏｍ Ｅｑ．（２） ａｓ ｔｈｅ ｉｎｉｔｉａｌ ｃｏｅｆｆｉｃｉｅｎｔｓ ｃ０ ， Ｅｑ． （ ４） ｃａｎ ｂｅ ｓｏｌｖｅｄ ｔｈｒｏｕｇｈ ｉｔｅｒａｔｉｖｅ ｃｏｍｐｕｔａｔｉｏｎｓ ［１１］ ． Ｈｏｗｅｖｅｒ， ｔｈｅ ｈｉｇｈ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｓｔ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ｉｔｅｒａ⁃ ｔｉｖｅ ｐｒｏｃｅｄｕｒｅ ｆｏｒ ｍａｉｎｔａｉｎｉｎｇ ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｃｏｎ⁃ ｓｔｒａｉｎｔｓ ｏｆ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ ｍａｋｅ ＮＬＳＳＳＴ ｉｎｅｆｆｉｃｉｅｎｔ ｉｎ ａｃｈｉｅｖｉｎｇ ｒｅａｌ⁃ｔｉｍｉｎｇ ｔｒａｃｋｉｎｇ． Ｉｎ ｃｏｎｔｒａｓｔ ｔｏ Ｆｉｇ． １， ｔｈｅ ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ＮＬＳＳＳＴ ｐｒｅｓｅｎｔｅｄ ｉｎ Ｆｉｇ． ２， ｉｎｃｌｕｄｅｓ ａｎ ａｄｄｉｔｉｏｎａｌ ｎｅｉｇｈｂｏｒｈｏｏｄ ｃｏｎｓｔｒａｉｎｔ ｂｅｔｗｅｅｎ ｙｉ ａｎｄ ＮＫ（ｙｉ）． Ｆｉｇ． ２ Ｌｕ􀆳ｓ ＮＬＳＳＳＴ Ａｌｇｏｒｉｔｈｍ ２ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｆｏｒ ｔｒａｃｋｉｎｇ （ＥＬＳＳＴ） Ｔｏ ｃｉｒｃｕｍｖｅｎｔ ｔｈｅ ｈｅａｖｙ ｃｏｍｐｕｔａｔｉｏｎ ｂｕｒｄｅｎ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＴ （Ｔａｂｌｅ ４）， ｗｅ ｐｒｏｐｏｓｅ ａｎ ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ， ｃａｌｌｅｄ ＥＬＳＳＴ， ｔｈａｔ ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｌｏ⁃ ｃａｌ Ｅｕｃｌｉｄｅａｎ ｓｔｒｕｃｔｕｒｅｓ ｏｆ ｔｈｅ ｃａｎｄｉｄａｔｅｓ． ２．１ Ｏｒｉｇｉｎａｌ ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ ｓｐａｒｓｅ ｃｏｄｉｎｇ （Ｏｒｉｇｉｎａｌ ＥＬＳＳＣ） Ｉｔ ｉｓ ｅｖｉｄｅｎｔ ｆｒｏｍ Ｅｑ． （４） ｔｈａｔ ＮＬＳＳＳＴ ａｔｔｅｍｐｔｓ ｔｏ ｓｏｌｖｅ ａ ｄｏｕｂｌｅ ｌ １ ⁃ｎｏｒｍ ｐｒｏｂｌｅｍ． Ｈｏｗｅｖｅｒ， ｉｔ ｉｓ ｗｅｌｌ ｋｎｏｗｎ ｔｈａｔ ｔｈｅ ｌ ２ ⁃ｎｏｒｍ ｉｓ ｍｕｃｈ ｍｏｒｅ ｃｏｍｍｏｎｌｙ ｕｓｅｄ ｆｏｒ ｍｅａｓｕｒｉｎｇ ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｔｗｏ ｖｅｃｔｏｒｓ ａｎｄ ｉｓ ｍｕｃｈ ｅａｓｉｅｒ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈａｎ ｔｈｅ ｌ １ ⁃ｎｏｒｍ． Ｔｈｕｓ， ｗｅ ｔａｋｅ ｔｈｅ ｆｏｒｍｅｒ ｔｏ ｍｅａｓｕｒｅ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｂｅｔｗｅｅｎ ｔｈｅ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔ ｖｅｃｔｏｒｓ， ｗｈｉｃｈ ａｒｅ ｃｌｏｓｅ ｔｏ ｅａｃｈ ｏｔｈｅｒ， ｉ． ｅ．， ｔｈｅ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ⁃ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ， ａｎｄ ｔｈｅ ｌａｔｔｅｒ ｌ １ ⁃ｎｏｒｍ ｏｆ Ｃ ｔｏ ｍａｉｎｔａｉｎ ｔｈｅ ｓｐａｒｓｉｔｙ ｏｆ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ａｓ ｆｏｌｌｏｗｓ： ｍｉｎＣ ‖Ｙ － ＤＣ‖２ Ｆ ＋ α ‖Ｃ‖１ ＋ β ‖Ｃ － ＣＷ‖２ Ｆ （５） ·１３８· 智 能 系 统 学 报 第 １１ 卷

1 WANG Hongyuan,et al:Efficient tracker based on sparse coding with Euclidean local structure-based constraint ·139. Table 1 Optimization for ELS constraint based SC(ELSSC) Input:Given N data points Y=[yY]ER,over-complete dictionary DR) Output:Sparse matrix C=[ce]R(x Parameters:Maxiumn iteration number J=10,neighborhood size K=5,all-zero vector co,a=0.01,B=0.5,y=0.001 1:For each point y,compute the nearest K neighborhoods N(y)and weights 2:Compute the SVD-decomposition of D UJVT,where VER()(2m) 3:compute ID'D‖，and set‖D'D|+2 B randomly 4:For i=1:N 5:For t=1:J 6:If lec)<,break inner iteration 7:0omie0=,6-,0=[Dy+290,-w+(y-28)c-DD,e-"],md0=VeR 8:Repesent”thparse colficient vector”,ie,optimize子l”-lke”tallo"l, 9:End 10:End Equation (5)is the objective function of our Eu- clidean local structure constraint-based SC and can be +7291a-ol-宁Ie-nl店 solved through iterative computation.In particular,at 1 lI3-6:D9〉+aIe0,-2pc9,-)+ the t-th iteration,for a single candidate y:in Y,Eq. (5)can be written as follows: 子"1-g-9e)+Y,81o+ 2 mineof(c()=min Iy:-De+ a ll e :+B lc)-0)(6) 〈De”,D〉-2ID,l3+BI-wI经= where.At the t-th iteration for the optimization of c,c,j is fixed.Therefore,we can 子1e"3-De）-29(c0,g-）- regard 1)as a constant.To solve Eq.(6),we intro- (y-2B)c.co+(Def Dco)+a llel+ duce the following surrogate function as presented in [11]: (兮%店+7291l+811》- 6o）=分1e-6l-71n0-l目 子Ic”-0+aI0,+R (7) (8) where is convex.According to Daubechies,when where AI-D'D is a strictly positive definite matrix,c,co) 1 =[D'y:+280+(y-28)c-D De-] 2 is strictly convex for any co with respect to c.Hence,in and our experiments,the constant A is set accordingly (A y-28;Table 1).Once the over-complete dictionary D is R=lxl+Y291o1-1l+ fixed,we can derive the following convex objective func- tion from Eq.(7): BIwI-子I” )lyDeare fixed at the t-th iteration.Thus,we can simplify

Ｔａｂｌｅ １ Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ＥＬＳ ｃｏｎｓｔｒａｉｎｔ ｂａｓｅｄ ＳＣ（ＥＬＳＳＣ） Ｉｎｐｕｔ：Ｇｉｖｅｎ Ｎ ｄａｔａ ｐｏｉｎｔｓ Ｙ＝ ［ ｙ１… ｙＮ ］∈Ｒ ｍ×Ｎ ，ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ∈Ｒ ｍ×（ｎ＋２ｍ） Ｏｕｔｐｕｔ：Ｓｐａｒｓｅ ｍａｔｒｉｘ Ｃ＝ ［ｃ１… ｃＮ ］∈Ｒ （ｎ＋２ｍ）×Ｎ Ｐａｒａｍｅｔｅｒｓ： Ｍａｘｉｕｍｎ ｉｔｅｒａｔｉｏｎ ｎｕｍｂｅｒ Ｊ ＝ １０，ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｉｚｅ Ｋ＝ ５，ａｌｌ⁃ｚｅｒｏ ｖｅｃｔｏｒ ｃ０ ，α＝ ０．０１，β ＝ ０．５，γ ＝ ０．００１ １：Ｆｏｒ ｅａｃｈ ｐｏｉｎｔ ｙｉ，ｃｏｍｐｕｔｅ ｔｈｅ ｎｅａｒｅｓｔ Ｋ ｎｅｉｇｈｂｏｒｈｏｏｄｓ ＮＫ（ｙｉ） ａｎｄ ｗｅｉｇｈｔｓ ｗｊｉ ２：Ｃｏｍｐｕｔｅ ｔｈｅ ＳＶＤ⁃ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｏｆ Ｄ ＝ ＵΣＶ Ｔ ，ｗｈｅｒｅ Ｖ∈Ｒ （ｎ＋２ｍ）×（ｎ＋２ｍ） ３：ｃｏｍｐｕｔｅ ‖Ｄ ＴＤ‖， ａｎｄ ｓｅｔ‖Ｄ ＴＤ‖＋２β ｒａｎｄｏｍｌｙ ４：Ｆｏｒ ｉ ＝ １：Ｎ ５： Ｆｏｒ ｔ ＝ １：Ｊ ６： Ｉｆ ‖ｃ （ｔ） ｉ － ｃ （ｔ－１） ｉ ‖２ ＜ τ ， ｂｒｅａｋ ｉｎｎｅｒ ｉｔｅｒａｔｉｏｎ ７：Ｃｏｍｐｕｔｅ θ （ｔ） ｉ ＝ ∑ｊ ｗｊｉ ｃ （ｔ－１） ｊ ，ｖ （ｔ） ｉ ＝ １ γ ［Ｄ Ｔ ｙｉ ＋ ２βθｉ （ｔ－１） ＋ （γ － ２β）ｃｉ ｔ－１ － Ｄ ＴＤｉ ｃ ｔ－１ ］ ，ａｎｄ ｘ （ｔ） ｉ ＝Ｖｖ （ｔ） ｉ ∈Ｒ （ｎ＋２ｍ）×１ ８： Ｒｅｐｒｅｓｅｎｔ ｘ （ｔ） ｉ ｗｉｔｈ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔ ｖｅｃｔｏｒ ｃ （ｔ） ｉ ，ｉ．ｅ．，ｏｐｔｉｍｉｚｅ γ ２ ‖ｘ （ｔ） ｉ －Ｖｃ （ｔ） ｉ ‖２ ２ ＋α‖ｃ （ｔ） ｉ ‖１ ９： Ｅｎｄ １０：Ｅｎｄ Ｅｑｕａｔｉｏｎ （５） ｉｓ ｔｈｅ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ ｏｆ ｏｕｒ Ｅｕ⁃ ｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ⁃ｂａｓｅｄ ＳＣ ａｎｄ ｃａｎ ｂｅ ｓｏｌｖｅｄ ｔｈｒｏｕｇｈ ｉｔｅｒａｔｉｖｅ ｃｏｍｐｕｔａｔｉｏｎ． Ｉｎ ｐａｒｔｉｃｕｌａｒ， ａｔ ｔｈｅ ｔ⁃ｔｈ ｉｔｅｒａｔｉｏｎ， ｆｏｒ ａ ｓｉｎｇｌｅ ｃａｎｄｉｄａｔｅ ｙｉ ｉｎ Ｙ， Ｅｑ． （５） ｃａｎ ｂｅ ｗｒｉｔｔｅｎ ａｓ ｆｏｌｌｏｗｓ： ｍｉｎｃｉ （ｔ） ｆ（ｃｉ （ｔ） ） ＝ ｍｉｎｃｉ （ｔ） ‖ｙｉ － Ｄｃｉ （ｔ）‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ β ‖ｃ （ｔ） ｉ － θ （ｔ－１） ｉ ‖２ ２ （６） ｗｈｅｒｅ θ （ｔ） ｉ ＝ ∑ ｊｗｊｉ ｃ （ｔ－１） ｊ ． Ａｔ ｔｈｅ ｔ⁃ｔｈ ｉｔｅｒａｔｉｏｎ ｆｏｒ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｃｉ，ｃｊ，ｉ ≠ ｊ ｉｓ fiｘｅｄ． Ｔｈｅｒｅｆｏｒｅ， ｗｅ ｃａｎ ｒｅｇａｒｄ θ （ｔ－１） ｉ ａｓ ａ ｃｏｎｓｔａｎｔ． Ｔｏ ｓｏｌｖｅ Ｅｑ． （６）， ｗｅ ｉｎｔｒｏ⁃ ｄｕｃｅ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｓｕｒｒｏｇａｔｅ ｆｕｎｃｔｉｏｎ ａｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ［１１］： ψ（ｃｉ，ｃ０） ＝ λ ２ ‖ｃ （ｔ） ｉ － ｃ０‖２ ２ － １ ２ ‖Ｄｃ （ｔ） ｉ － Ｄｃ０‖２ ２ （７） ｗｈｅｒｅ λ ｉｓ ｃｏｎｖｅｘ． Ａｃｃｏｒｄｉｎｇ ｔｏ Ｄａｕｂｅｃｈｉｅｓ ［１３］ ， ｗｈｅｎ λＩ － Ｄ ＴＤ ｉｓ ａ ｓｔｒｉｃｔｌｙ ｐｏｓｉｔｉｖｅ ｄｅfiｎｉｔｅ ｍａｔｒｉｘ， ψ（ｃｉ，ｃ０） ｉｓ ｓｔｒｉｃｔｌｙ ｃｏｎｖｅｘ ｆｏｒ ａｎｙ ｃ０ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｃｉ ． Ｈｅｎｃｅ， ｉｎ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔｓ， ｔｈｅ ｃｏｎｓｔａｎｔ λ ｉｓ ｓｅｔ ａｃｃｏｒｄｉｎｇｌｙ （ λ ＝ γ － ２β； Ｔａｂｌｅ １）． Ｏｎｃｅ ｔｈｅ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ ｉｓ ｆｉｘｅｄ， ｗｅ ｃａｎ ｄｅｒｉｖｅ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｃｏｎｖｅｘ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃ⁃ ｔｉｏｎ ｆｒｏｍ Ｅｑ． （７）： ｆ（ｃ （ｔ） ｉ ） ＝ １ ２ ‖ｙｉ － Ｄｃ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ β ‖ｃ （ｔ） ｉ － θ （ｔ－１） ｉ ‖２ ２ ＋ γ － ２β ２ ‖ｃ （ｔ） ｉ － ｃ０‖２ ２ － １ ２ ‖Ｄｃ （ｔ） ｉ － Ｄｃ０‖２ ２ ＝ １ ２ ‖ｙｉ‖２ ２ － 〈ｙｉ，Ｄｃ （ｔ） ｉ 〉 ＋ α ‖ｃ （ｔ） ｉ ‖１ － ２β〈ｃ （ｔ） ｉ ，θ （ｔ－１） ｉ 〉 ＋ γ ２ ‖ｃ （ｔ） ｉ ‖２ ２ － （γ － ２β）〈ｃ （ｔ） ｉ ，ｃ０〉 ＋ γ － ２β ２ ‖ｃ０‖２ ２ ＋ 〈Ｄｃ （ｔ） ｉ ，Ｄｃ０ 〉 － １ ２ ‖Ｄｃ０‖２ ２ ＋ β ‖θ （ｔ－１） ｉ ‖２ ２ ＝ γ ２ ‖ｃ （ｔ） ｉ ‖２ ２ － 〈ｙｉ，Ｄｃ （ｔ） ｉ 〉 － ２β〈ｃ （ｔ） ｉ ，θ （ｔ－１） ｉ 〉 － （γ － ２β）〈ｃ （ｔ） ｉ ，ｃ０〉 ＋ 〈Ｄｃ （ｔ） ｉ ，Ｄｃ０〉 ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ （ １ ２ ‖ｙｉ‖２ ２ ＋ γ － ２β ２ ‖ｃ０‖２ ２ ＋ β ‖θ （ｔ－１） ｉ ‖２ ２ ） ＝ γ ２ ‖ｃ （ｔ） ｉ － ｖ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ Ｒ （８） ｗｈｅｒｅ ｖ （ｔ） ｉ ＝ １ γ Ｄ Ｔ ｙｉ ＋ ２βθ （ｔ－１） ｉ ＋ （γ － ２β）ｃ ｔ－１ ｉ － Ｄ ＴＤｃ ｔ－１ [ ] ａｎｄ Ｒ ＝ １ ２ ‖ｙｉ‖２ ２ ＋ γ － ２β ２ ‖ｃ０‖ － １ ２ ‖Ｄｃ０‖２ ２ ＋ β ‖θ （ｔ－１） ｉ ‖２ ２ － γ ２ ‖ｖ （ｔ） ｉ ‖２ ２ ａｒｅ fiｘｅｄ ａｔ ｔｈｅ ｔ⁃ｔｈ ｉｔｅｒａｔｉｏｎ． Ｔｈｕｓ， ｗｅ ｃａｎ ｓｉｍｐｌｉｆｙ 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１３９·

·140· 智能系统学报 第11卷 Eg.(8)as follows: e)=子Ixw-reoI+alel )=+a (9) (12) To solve Eq.(9)using SVD,we decompose the over- where V"=[V'I'-I"]E R"x3,I'denotes the n-or- complete dictionary DR(asD=UV,where dered identity matrix,andx'is the first n rows of x;in U∈RmXm,∑∈Rmx(a+2m）andV∈Ra+2m)x(a+2). Eq.(10). Since V is an orthogonal matrix,Eq.(9)can be re- 2.3 Original and improved ELSSC-tracker written as fc")=子I9-e”+a1c”, Based on the above algorithm,our tracker can be obtained with the framework of the original I,-track- (10) er(Table 2).We need to iteratively solve the large- where x=Vo).Consequently,we can transform the scale l,-optimization problem in Eq.(10)twice,up to optimization problem with the Euclidean local structure three times for each candidate in the algorithm,and constraint in Eq.(6)to a pure l-optimization problem more than five times in NLSSST.The initial sparse in Eq.(10),i.e.,to represent the given signalxwith coefficients co are considered as all-zero vectors and it- sparse coefficientsc under the new dictionary V eratively solve the problem without any I,-optimization R(2m)x(+2m).The procedure of Euclidean local-struc- issues,as in Table 1 in [11].Nevertheless,we find ture constraint based sparse coding (ELSSC)is sum- that,in NLSSST,it is more effective and accurate to marized in Table 1 and is very different from the opti- initialize co as the solution of the I-optimization prob- mization procedure followed for NISSSC],even lem.Therefore,the computation complexity of our though the difference between their objective functions tracker is of the same order of magnitude as that of the seems very small (Eqs.(4)and (5),respectively).1-tracker and NLSSST.When we resize all n 10 tar- 2.2 Improved euclidean local structure constraint gets and N=200 candidate regions to 40 x 40,i.e., sparse coding (Improved ELSSC) m 1 600 Figs.1 and 2),then the over-complete If m in Eq.(10)is large,it is time-consuming to dictionary D is 1 600 x 3 210 and the orthogonal ma- obtain the optimization result c,as that in I-optimiza- trix V is 3 210 x 3 210 in Eq.(10).It is very difficult tion and NISSSC.Fortunately,in terms of SVD and to solve the corresponding I-optimization problem with the structure of D Figs.1 and 2),we have such a D in 1-tracker and NISSST)or V in our D UEV [UEV,I,-I]=[T,I,-I] ELSST). (11) With the improved ELSSC,is the first ten rows where I denotes the m-ordered identity matrix.'is the of and V'consists of the first ten rows and first ten first n rows of V'consists of the first n rows and the columns of V.Thus,each iteration of each candidate first n columns of V,and mn.As a result,when region in ELSST can be reduced from the large-scale constructing the dictionary V in Eq.(10),only the I-optimization problem to a much smaller one because first n rows and first n columns of V must be prepared,of the much smaller scale V E Rox10.To overcome whereas the remaining parts of V are not considered to the problem of occlusions in tracking,the analogous make any contribution to the target templates T.Thus,trivial templates are used to construct the new dictiona- the large scale optimization in Eq.(10)can be re-ryRx,i.e.,a ten-ordered identity matrix and duced to a much smaller one as follows: ten-ordered negative identity matrix

Ｅｑ． （８） ａｓ ｆｏｌｌｏｗｓ： ｆ（ｃ （ｔ） ｉ ） ＝ γ ２ ‖ｃ （ｔ） ｉ － ｖ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ （９） Ｔｏ ｓｏｌｖｅ Ｅｑ． （９） ｕｓｉｎｇ ＳＶＤ， ｗｅ ｄｅｃｏｍｐｏｓｅ ｔｈｅ ｏｖｅｒ⁃ ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ∈Ｒ ｍ×（ｎ＋２ｍ） ａｓ Ｄ ＝ ＵΣＶ Ｔ ，ｗｈｅｒｅ Ｕ ∈ Ｒ ｍ×ｍ ，Σ ∈ Ｒ ｍ×（ｎ＋２ｍ） ａｎｄ Ｖ ∈ Ｒ （ｎ＋２ｍ） ×（ｎ＋２ｍ） ． Ｓｉｎｃｅ Ｖ ｉｓ ａｎ ｏｒｔｈｏｇｏｎａｌ ｍａｔｒｉｘ， Ｅｑ． （９） ｃａｎ ｂｅ ｒｅ⁃ ｗｒｉｔｔｅｎ ａｓ ｆ（ｃ （ｔ） ｉ ） ＝ γ ２ ‖ｘ （ｔ） ｉ － Ｖｃ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ （１０） ｗｈｅｒｅ ｘ （ｔ） ｉ ＝ Ｖｖ （ｔ） ｉ ． Ｃｏｎｓｅｑｕｅｎｔｌｙ， ｗｅ ｃａｎ ｔｒａｎｓｆｏｒｍ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｈｅ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ ｉｎ Ｅｑ． （６） ｔｏ ａ ｐｕｒｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｎ Ｅｑ． （１０）， ｉ．ｅ．， ｔｏ ｒｅｐｒｅｓｅｎｔ ｔｈｅ ｇｉｖｅｎ ｓｉｇｎａｌｘ （ｔ） ｉ ｗｉｔｈ ｓｐａｒｓｅ ｃｏｅffiｃｉｅｎｔｓｃ （ｔ） ｉ ｕｎｄｅｒ ｔｈｅ ｎｅｗ ｄｉｃｔｉｏｎａｒｙ Ｖ ∈ Ｒ （ｎ＋２ｍ） ×（ｎ＋２ｍ） ． Ｔｈｅ ｐｒｏｃｅｄｕｒｅ ｏｆ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ⁃ｓｔｒｕｃ⁃ ｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ ｂａｓｅｄ ｓｐａｒｓｅ ｃｏｄｉｎｇ （ＥＬＳＳＣ） ｉｓ ｓｕｍ⁃ ｍａｒｉｚｅｄ ｉｎ Ｔａｂｌｅ １ ａｎｄ ｉｓ ｖｅｒｙ ｄｉffｅｒｅｎｔ ｆｒｏｍ ｔｈｅ ｏｐｔｉ⁃ ｍｉｚａｔｉｏｎ ｐｒｏｃｅｄｕｒｅ ｆｏｌｌｏｗｅｄ ｆｏｒ ＮＬＳＳＳＣ ［１１］ ， ｅｖｅｎ ｔｈｏｕｇｈ ｔｈｅ ｄｉｆｆｅｒｅｎｃｅ ｂｅｔｗｅｅｎ ｔｈｅｉｒ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎｓ ｓｅｅｍｓ ｖｅｒｙ ｓｍａｌｌ （Ｅｑｓ． （４） ａｎｄ （５）， ｒｅｓｐｅｃｔｉｖｅｌｙ）． ２．２ Ｉｍｐｒｏｖｅｄ ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ ｓｐａｒｓｅ ｃｏｄｉｎｇ （Ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ） Ｉｆ ｍ ｉｎ Ｅｑ． （１０） ｉｓ ｌａｒｇｅ， ｉｔ ｉｓ ｔｉｍｅ⁃ｃｏｎｓｕｍｉｎｇ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｒｅｓｕｌｔ ｃｉ， ａｓ ｔｈａｔ ｉｎ ｌ １ ⁃ｏｐｔｉｍｉｚａ⁃ ｔｉｏｎ ａｎｄ ＮＬＳＳＳＣ． Ｆｏｒｔｕｎａｔｅｌｙ， ｉｎ ｔｅｒｍｓ ｏｆ ＳＶＤ ａｎｄ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ Ｄ （Ｆｉｇｓ． １ ａｎｄ ２）， ｗｅ ｈａｖｅ Ｄ ＝ ＵΣＶ Ｔ ＝ ＵΣＶ′ Ｔ [ ，Ｉ， － Ｉ] ＝ [Ｔ，Ｉ， － Ｉ] （１１） ｗｈｅｒｅ Ｉ ｄｅｎｏｔｅｓ ｔｈｅ ｍ⁃ｏｒｄｅｒｅｄ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ． Σ′ ｉｓ ｔｈｅ ｆｉｒｓｔ ｎ ｒｏｗｓ ｏｆ Σ， Ｖ′ ｃｏｎｓｉｓｔｓ ｏｆ ｔｈｅ ｆｉｒｓｔ ｎ ｒｏｗｓ ａｎｄ ｔｈｅ ｆｉｒｓｔ ｎ ｃｏｌｕｍｎｓ ｏｆ Ｖ， ａｎｄ ｍ≫ｎ． Ａｓ ａ ｒｅｓｕｌｔ， ｗｈｅｎ ｃｏｎｓｔｒｕｃｔｉｎｇ ｔｈｅ ｄｉｃｔｉｏｎａｒｙ Ｖ ｉｎ Ｅｑ． （ １０）， ｏｎｌｙ ｔｈｅ ｆｉｒｓｔ ｎ ｒｏｗｓ ａｎｄ ｆｉｒｓｔ ｎ ｃｏｌｕｍｎｓ ｏｆ Ｖ ｍｕｓｔ ｂｅ ｐｒｅｐａｒｅｄ， ｗｈｅｒｅａｓ ｔｈｅ ｒｅｍａｉｎｉｎｇ ｐａｒｔｓ ｏｆ Ｖ ａｒｅ ｎｏｔ ｃｏｎｓｉｄｅｒｅｄ ｔｏ ｍａｋｅ ａｎｙ ｃｏｎｔｒｉｂｕｔｉｏｎ ｔｏ ｔｈｅ ｔａｒｇｅｔ ｔｅｍｐｌａｔｅｓ Ｔ． Ｔｈｕｓ， ｔｈｅ ｌａｒｇｅ ｓｃａｌｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎ Ｅｑ． （ １０） ｃａｎ ｂｅ ｒｅ⁃ ｄｕｃｅｄ ｔｏ ａ ｍｕｃｈ ｓｍａｌｌｅｒ ｏｎｅ ａｓ ｆｏｌｌｏｗｓ： ｆ（ｃ′ （ｔ） ｉ ） ＝ γ ２ ‖ｘ′ （ｔ） ｉ － Ｖ″ｃ′ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ′ （ｔ） ｉ ‖１ ， （１２） ｗｈｅｒｅ Ｖ″ ＝ [Ｖ′ Ｉ′ － Ｉ″] ∈ Ｒ ｎ×３ｎ ，Ｉ′ ｄｅｎｏｔｅｓ ｔｈｅ ｎ⁃ｏｒ⁃ ｄｅｒｅｄ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ， ａｎｄ ｘｉ ′ ｉｓ ｔｈｅ ｆｉｒｓｔ ｎ ｒｏｗｓ ｏｆ ｘｉ ｉｎ Ｅｑ．（１０）． ２．３ Ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ⁃ｔｒａｃｋｅｒ Ｂａｓｅｄ ｏｎ ｔｈｅ ａｂｏｖｅ ａｌｇｏｒｉｔｈｍ， ｏｕｒ ｔｒａｃｋｅｒ ｃａｎ ｂｅ ｏｂｔａｉｎｅｄ ｗｉｔｈ ｔｈｅ ｆｒａｍｅｗｏｒｋ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋ⁃ ｅｒ ［８⁃９］ （Ｔａｂｌｅ ２）． Ｗｅ ｎｅｅｄ ｔｏ ｉｔｅｒａｔｉｖｅｌｙ ｓｏｌｖｅ ｔｈｅ ｌａｒｇｅ⁃ ｓｃａｌｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｎ Ｅｑ． （１０） ｔｗｉｃｅ， ｕｐ ｔｏ ｔｈｒｅｅ ｔｉｍｅｓ ｆｏｒ ｅａｃｈ ｃａｎｄｉｄａｔｅ ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ， ａｎｄ ｍｏｒｅ ｔｈａｎ fiｖｅ ｔｉｍｅｓ ｉｎ ＮＬＳＳＳＴ． Ｔｈｅ ｉｎｉｔｉａｌ ｓｐａｒｓｅ ｃｏｅffiｃｉｅｎｔｓ ｃ０ ａｒｅ ｃｏｎｓｉｄｅｒｅｄ ａｓ ａｌｌ⁃ｚｅｒｏ ｖｅｃｔｏｒｓ ａｎｄ ｉｔ⁃ ｅｒａｔｉｖｅｌｙ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｗｉｔｈｏｕｔ ａｎｙ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｉｓｓｕｅｓ， ａｓ ｉｎ Ｔａｂｌｅ １ ｉｎ ［１１］． Ｎｅｖｅｒｔｈｅｌｅｓｓ， ｗｅ fiｎｄ ｔｈａｔ， ｉｎ ＮＬＳＳＳＴ， ｉｔ ｉｓ ｍｏｒｅ ｅffｅｃｔｉｖｅ ａｎｄ ａｃｃｕｒａｔｅ ｔｏ ｉｎｉｔｉａｌｉｚｅ ｃ０ ａｓ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｏｕｒ ｔｒａｃｋｅｒ ｉｓ ｏｆ ｔｈｅ ｓａｍｅ ｏｒｄｅｒ ｏｆ ｍａｇｎｉｔｕｄｅ ａｓ ｔｈａｔ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＴ． Ｗｈｅｎ ｗｅ ｒｅｓｉｚｅ ａｌｌ ｎ ＝ １０ ｔａｒ⁃ ｇｅｔｓ ａｎｄ Ｎ ＝ ２００ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｔｏ ４０ × ４０， ｉ．ｅ．， ｍ ＝ １ ６００ （ Ｆｉｇｓ． １ ａｎｄ ２）， ｔｈｅｎ ｔｈｅ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ ｉｓ １ ６００ × ３ ２１０ ａｎｄ ｔｈｅ ｏｒｔｈｏｇｏｎａｌ ｍａ⁃ ｔｒｉｘ Ｖ ｉｓ ３ ２１０ × ３ ２１０ ｉｎ Ｅｑ． （１０）． Ｉｔ ｉｓ ｖｅｒｙ ｄｉｆｆｉｃｕｌｔ ｔｏ ｓｏｌｖｅ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｗｉｔｈ ｓｕｃｈ ａ Ｄ （ ｉｎ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＴ） ｏｒ Ｖ （ ｉｎ ｏｕｒ ＥＬＳＳＴ）． Ｗｉｔｈ ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ， Σ′ ｉｓ ｔｈｅ ｆｉｒｓｔ ｔｅｎ ｒｏｗｓ ｏｆ Σ， ａｎｄ Ｖ′ ｃｏｎｓｉｓｔｓ ｏｆ ｔｈｅ ｆｉｒｓｔ ｔｅｎ ｒｏｗｓ ａｎｄ ｆｉｒｓｔ ｔｅｎ ｃｏｌｕｍｎｓ ｏｆ Ｖ． Ｔｈｕｓ， ｅａｃｈ ｉｔｅｒａｔｉｏｎ ｏｆ ｅａｃｈ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎ ｉｎ ＥＬＳＳＴ ｃａｎ ｂｅ ｒｅｄｕｃｅｄ ｆｒｏｍ ｔｈｅ ｌａｒｇｅ⁃ｓｃａｌｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｔｏ ａ ｍｕｃｈ ｓｍａｌｌｅｒ ｏｎｅ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｍｕｃｈ ｓｍａｌｌｅｒ ｓｃａｌｅ Ｖ′ ∈ Ｒ １０×１０ ． Ｔｏ ｏｖｅｒｃｏｍｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｏｃｃｌｕｓｉｏｎｓ ｉｎ ｔｒａｃｋｉｎｇ， ｔｈｅ ａｎａｌｏｇｏｕｓ ｔｒｉｖｉａｌ ｔｅｍｐｌａｔｅｓ ａｒｅ ｕｓｅｄ ｔｏ ｃｏｎｓｔｒｕｃｔ ｔｈｅ ｎｅｗ ｄｉｃｔｉｏｎａ⁃ ｒｙＶ″ ∈ Ｒ １０×３０ ， ｉ．ｅ．， ａ ｔｅｎ⁃ｏｒｄｅｒｅｄ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ ａｎｄ ｔｅｎ⁃ｏｒｄｅｒｅｄ ｎｅｇａｔｉｖｅ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ． ·１４０· 智 能 系 统 学 报 第 １１ 卷

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ｃｉｅｎｔｓ． Ｔｈｉｓ ｉｍｐｒｏｖｅｓ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｔｒａｃｋｉｎｇ； ｏｔｈｅｒｗｉｓｅ， ｔｈｅ ｔｒａｃｋｅｒ ｍａｙ ｄｅｇｅｎｅｒａｔｅ ｏｒ ｅｖｅｎ ｆａｉｌ ｔｏ ｔｒａｃｋ． ＣＲ４ ｆｏｒ ｅｘａｍｐｌｅ， ｗｉｔｈ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ， ｃａｎ ｂｅ ｒｅｐｒｅｓｅｎｔｅｄ ｂｙ Ｔ２ ， Ｔ８ ， Ｔ６ ， Ｔ７ ， ａｎｄ Ｔ１ ， ａｎｄ ｔｈｅ ｔｒａｃｋ⁃ ｅｒ ｍａｙ ｆａｉｌ ｔｏ ｔｒａｃｋ ｔｈｅ ｔｏｐ ｏｆ ｔｈｅ ｂｏｏｋ． Ｍｅａｎｗｈｉｌｅ， ｅｘ⁃ ｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ， ＮＬＳＳＳＣ ａｎｄ ｏｕｒ ｔｗｏ ＥＬＳＳＣ ａｒｅ ｓｐａｒｓｅｒ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ． 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１４１·

.142. 智能系统学报 第11卷 Mean:65.4463 CR2 Mean:747100 Mean:707238 CR d292313 5i25.2076 Std247166 4an22681 Mean.64.199 CR4 Men:56.3894 St30.6914 CRS Sd27.0634CR Sd318258 6 candidate regions(CR1-CR6) 10 template regions(TI-T10) L1-tracker 0.4 NLSSSC-tracke Original ELSSC-tracke 02 100.040.05 006 0.0 0.11 140.07 320100.i10 00700800的 wse co质iens withN忆SSYC'-rakr Fig.3 Comparisions of sparsity and stability with the original 1,-.NLSSSC-.and our ELSSC-optimization.The sparse coefficients only are accurated to the second decimal place. 3.3 Experimental results for visual target tracking large size of candidates based on the definition of in- We evaluate the investigated algorithms compara-tegral image,the feature extraction of these candidates tively,using the center location errors,the average is so fast,that its cost can be ignored),which makes success rates,and the average frames per second.The it robust for occlusion,scale variation,and blur. results are shown in Figs.4&5 and in Tables 3&4.The NISSST and our original and improved trackers all templates of NISSST,the original ELSST,and the im-work well,when the targets are occluded;our two proved ELSST are shown in Fig.4(g-o).Overall,our trackers work even better. original and improved trackers outperform the other For motion blur,our two trackers work better than state-of-the-art algorithms. IVT and the original l-tracker.Moreover,CovTracking For occlusion,five algorithms,except IVT,func- also reveals its ability to handle blur (e.g.,#4,#9, tion satisfactorily,especially at #206,#366 of the and #38 in Fig.4(d,o).In the former sequence,the Dudek sequence in Fig.4(b)(the head in tracking is animal runs and jumps fast (motion blur)with a lot of covered by the hand and glasses),#143,#265,#496 water splashing occlusion),while in the latter,the of the Faceocc2 sequence in Fig.4(c)(the head in man ropes skipping and the camera cannot take the tracking is covered by the book),#85,#108,#433 of clear face of the man.IVT and I,-tracker fail both from the Girl sequence in Fig.4(e)(the head in tracking #4 in Fig.4(d),and never recover after that.Our o- turns right,turns back,and blocks someone else),riginal and improved ELSS lost the target in #31 and and #56,#104,#301 of the Face sequence in Fig.4 #41,then recovered in #33 and #44 Fig.4(d)).In (i)(the head in tracking is also covered by the #12 to #21 and #44 to #71,the improved ELSST works book).After the target recovers from occlusion,these better than original ELSST,CovTracking,I-tracker, five trackers can seek it quickly.IVT works poorly,e- and NLSSST. ven loses the target in #10 of the Girl sequence Fig.5 For rotation and scale variation,our trackers also (e)),because the number of positive and negative perform robustly (Figs.4(a,c,e,g,j)and 5(a,c,e, samples is limited (considering the learning g,j).When the surfer falls forward and backward,the efficiency),and the incremental updating of the girl turns left and right,moves towards and away from classifier in IVT is less effective.CovTracking has a the camera,the man turns left and right,the car turns

Ｆｉｇ． ３ Ｃｏｍｐａｒｉｓｉｏｎｓ ｏｆ ｓｐａｒｓｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｗｉｔｈ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃， ＮＬＳＳＳＣ⁃， ａｎｄ ｏｕｒ ＥＬＳＳＣ⁃ｏｐｔｉｍｉｚａｔｉｏｎ． Ｔｈｅ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ ｏｎｌｙ ａｒｅ ａｃｃｕｒａｔｅｄ ｔｏ ｔｈｅ ｓｅｃｏｎｄ ｄｅｃｉｍａｌ ｐｌａｃｅ． ３．３ Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｆｏｒ ｖｉｓｕａｌ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ Ｗｅ ｅｖａｌｕａｔｅ ｔｈｅ ｉｎｖｅｓｔｉｇａｔｅｄ ａｌｇｏｒｉｔｈｍｓ ｃｏｍｐａｒａ⁃ ｔｉｖｅｌｙ， ｕｓｉｎｇ ｔｈｅ ｃｅｎｔｅｒ ｌｏｃａｔｉｏｎ ｅｒｒｏｒｓ， ｔｈｅ ａｖｅｒａｇｅ ｓｕｃｃｅｓｓ ｒａｔｅｓ， ａｎｄ ｔｈｅ ａｖｅｒａｇｅ ｆｒａｍｅｓ ｐｅｒ ｓｅｃｏｎｄ． Ｔｈｅ ｒｅｓｕｌｔｓ ａｒｅ ｓｈｏｗｎ ｉｎ Ｆｉｇｓ． ４＆５ ａｎｄ ｉｎ Ｔａｂｌｅｓ ３＆４． Ｔｈｅ ｔｅｍｐｌａｔｅｓ ｏｆ ＮＬＳＳＳＴ， ｔｈｅ ｏｒｉｇｉｎａｌ ＥＬＳＳＴ， ａｎｄ ｔｈｅ ｉｍ⁃ ｐｒｏｖｅｄ ＥＬＳＳＴ ａｒｅ ｓｈｏｗｎ ｉｎ Ｆｉｇ． ４（ｇ⁃ｏ）． Ｏｖｅｒａｌｌ， ｏｕｒ ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ｔｒａｃｋｅｒｓ ｏｕｔｐｅｒｆｏｒｍ ｔｈｅ ｏｔｈｅｒ ｓｔａｔｅ⁃ｏｆ⁃ｔｈｅ⁃ａｒｔ ａｌｇｏｒｉｔｈｍｓ． Ｆｏｒ ｏｃｃｌｕｓｉｏｎ， fiｖｅ ａｌｇｏｒｉｔｈｍｓ， ｅｘｃｅｐｔ ＩＶＴ， ｆｕｎｃ⁃ ｔｉｏｎ ｓａｔｉｓｆａｃｔｏｒｉｌｙ， ｅｓｐｅｃｉａｌｌｙ ａｔ ＃ ２０６， ＃ ３６６ ｏｆ ｔｈｅ Ｄｕｄｅｋ ｓｅｑｕｅｎｃｅ ｉｎ Ｆｉｇ． ４ （ｂ） （ｔｈｅ ｈｅａｄ ｉｎ ｔｒａｃｋｉｎｇ ｉｓ ｃｏｖｅｒｅｄ ｂｙ ｔｈｅ ｈａｎｄ ａｎｄ ｇｌａｓｓｅｓ）， ＃１４３， ＃２６５， ＃４９６ ｏｆ ｔｈｅ Ｆａｃｅｏｃｃ２ ｓｅｑｕｅｎｃｅ ｉｎ Ｆｉｇ． ４ （ ｃ） （ ｔｈｅ ｈｅａｄ ｉｎ ｔｒａｃｋｉｎｇ ｉｓ ｃｏｖｅｒｅｄ ｂｙ ｔｈｅ ｂｏｏｋ）， ＃８５， ＃１０８， ＃４３３ ｏｆ ｔｈｅ Ｇｉｒｌ ｓｅｑｕｅｎｃｅ ｉｎ Ｆｉｇ ．４ （ｅ） （ｔｈｅ ｈｅａｄ ｉｎ ｔｒａｃｋｉｎｇ ｔｕｒｎｓ ｒｉｇｈｔ， ｔｕｒｎｓ ｂａｃｋ， ａｎｄ ｂｌｏｃｋｓ ｓｏｍｅｏｎｅ ｅｌｓｅ）， ａｎｄ ＃５６， ＃１０４， ＃３０１ ｏｆ ｔｈｅ Ｆａｃｅ ｓｅｑｕｅｎｃｅ ｉｎ Ｆｉｇ． ４ （ ｉ ） （ ｔｈｅ ｈｅａｄ ｉｎ ｔｒａｃｋｉｎｇ ｉｓ ａｌｓｏ ｃｏｖｅｒｅｄ ｂｙ ｔｈｅ ｂｏｏｋ）． Ａｆｔｅｒ ｔｈｅ ｔａｒｇｅｔ ｒｅｃｏｖｅｒｓ ｆｒｏｍ ｏｃｃｌｕｓｉｏｎ， ｔｈｅｓｅ fiｖｅ ｔｒａｃｋｅｒｓ ｃａｎ ｓｅｅｋ ｉｔ ｑｕｉｃｋｌｙ． ＩＶＴ ｗｏｒｋｓ ｐｏｏｒｌｙ， ｅ⁃ ｖｅｎ ｌｏｓｅｓ ｔｈｅ ｔａｒｇｅｔ ｉｎ ＃１０ ｏｆ ｔｈｅ Ｇｉｒｌ ｓｅｑｕｅｎｃｅ （Ｆｉｇ． ５ （ｅ））， ｂｅｃａｕｓｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｓａｍｐｌｅｓ ｉｓ ｌｉｍｉｔｅｄ （ ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｌｅａｒｎｉｎｇ ｅffiｃｉｅｎｃｙ）， ａｎｄ ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ｕｐｄａｔｉｎｇ ｏｆ ｔｈｅ ｃｌａｓｓｉfiｅｒ ｉｎ ＩＶＴ ｉｓ ｌｅｓｓ ｅffｅｃｔｉｖｅ． ＣｏｖＴｒａｃｋｉｎｇ ｈａｓ ａ ｌａｒｇｅ ｓｉｚｅ ｏｆ ｃａｎｄｉｄａｔｅｓ （ｂａｓｅｄ ｏｎ ｔｈｅ ｄｅfiｎｉｔｉｏｎ ｏｆ ｉｎ⁃ ｔｅｇｒａｌ ｉｍａｇｅ， ｔｈｅ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ｏｆ ｔｈｅｓｅ ｃａｎｄｉｄａｔｅｓ ｉｓ ｓｏ ｆａｓｔ， ｔｈａｔ ｉｔｓ ｃｏｓｔ ｃａｎ ｂｅ ｉｇｎｏｒｅｄ）， ｗｈｉｃｈ ｍａｋｅｓ ｉｔ ｒｏｂｕｓｔ ｆｏｒ ｏｃｃｌｕｓｉｏｎ， ｓｃａｌｅ ｖａｒｉａｔｉｏｎ， ａｎｄ ｂｌｕｒ． ＮＬＳＳＳＴ ａｎｄ ｏｕｒ ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ｔｒａｃｋｅｒｓ ａｌｌ ｗｏｒｋ ｗｅｌｌ， ｗｈｅｎ ｔｈｅ ｔａｒｇｅｔｓ ａｒｅ ｏｃｃｌｕｄｅｄ； ｏｕｒ ｔｗｏ ｔｒａｃｋｅｒｓ ｗｏｒｋ ｅｖｅｎ ｂｅｔｔｅｒ． Ｆｏｒ ｍｏｔｉｏｎ ｂｌｕｒ， ｏｕｒ ｔｗｏ ｔｒａｃｋｅｒｓ ｗｏｒｋ ｂｅｔｔｅｒ ｔｈａｎ ＩＶＴ ａｎｄ ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ． Ｍｏｒｅｏｖｅｒ， ＣｏｖＴｒａｃｋｉｎｇ ａｌｓｏ ｒｅｖｅａｌｓ ｉｔｓ ａｂｉｌｉｔｙ ｔｏ ｈａｎｄｌｅ ｂｌｕｒ （ ｅ． ｇ．， ＃４， ＃９， ａｎｄ ＃３８ ｉｎ Ｆｉｇ． ４（ｄ，ｏ）． Ｉｎ ｔｈｅ ｆｏｒｍｅｒ ｓｅｑｕｅｎｃｅ， ｔｈｅ ａｎｉｍａｌ ｒｕｎｓ ａｎｄ ｊｕｍｐｓ ｆａｓｔ （ｍｏｔｉｏｎ ｂｌｕｒ） ｗｉｔｈ ａ ｌｏｔ ｏｆ ｗａｔｅｒ ｓｐｌａｓｈｉｎｇ （ ｏｃｃｌｕｓｉｏｎ）， ｗｈｉｌｅ ｉｎ ｔｈｅ ｌａｔｔｅｒ， ｔｈｅ ｍａｎ ｒｏｐｅｓ ｓｋｉｐｐｉｎｇ ａｎｄ ｔｈｅ ｃａｍｅｒａ ｃａｎｎｏｔ ｔａｋｅ ｔｈｅ ｃｌｅａｒ ｆａｃｅ ｏｆ ｔｈｅ ｍａｎ． ＩＶＴ ａｎｄ ｌ １ ⁃ｔｒａｃｋｅｒ ｆａｉｌ ｂｏｔｈ ｆｒｏｍ ＃４ ｉｎ Ｆｉｇ． ４（ｄ）， ａｎｄ ｎｅｖｅｒ ｒｅｃｏｖｅｒ ａｆｔｅｒ ｔｈａｔ． Ｏｕｒ ｏ⁃ ｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ＥＬＳＳ ｌｏｓｔ ｔｈｅ ｔａｒｇｅｔ ｉｎ ＃３１ ａｎｄ ＃４１， ｔｈｅｎ ｒｅｃｏｖｅｒｅｄ ｉｎ ＃３３ ａｎｄ ＃４４ （Ｆｉｇ． ４（ｄ））． Ｉｎ ＃１２ ｔｏ ＃２１ ａｎｄ ＃４４ ｔｏ ＃７１， ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＴ ｗｏｒｋｓ ｂｅｔｔｅｒ ｔｈａｎ ｏｒｉｇｉｎａｌ ＥＬＳＳＴ， ＣｏｖＴｒａｃｋｉｎｇ， ｌ １ ⁃ｔｒａｃｋｅｒ， ａｎｄ ＮＬＳＳＳＴ． Ｆｏｒ ｒｏｔａｔｉｏｎ ａｎｄ ｓｃａｌｅ ｖａｒｉａｔｉｏｎ， ｏｕｒ ｔｒａｃｋｅｒｓ ａｌｓｏ ｐｅｒｆｏｒｍ ｒｏｂｕｓｔｌｙ （Ｆｉｇｓ． ４（ａ，ｃ，ｅ，ｇ，ｊ） ａｎｄ ５（ ａ，ｃ，ｅ， ｇ，ｊ）． Ｗｈｅｎ ｔｈｅ ｓｕｒｆｅｒ ｆａｌｌｓ ｆｏｒｗａｒｄ ａｎｄ ｂａｃｋｗａｒｄ， ｔｈｅ ｇｉｒｌ ｔｕｒｎｓ ｌｅｆｔ ａｎｄ ｒｉｇｈｔ， ｍｏｖｅｓ ｔｏｗａｒｄｓ ａｎｄ ａｗａｙ ｆｒｏｍ ｔｈｅ ｃａｍｅｒａ， ｔｈｅ ｍａｎ ｔｕｒｎｓ ｌｅｆｔ ａｎｄ ｒｉｇｈｔ， ｔｈｅ ｃａｒ ｔｕｒｎｓ ·１４２· 智 能 系 统 学 报 第 １１ 卷

1WANG Hongyuan,et al:Efficient tracker based on sparse coding with Euclidean local structure-based constraint .143. over,and the juice bottle becomes bigger and smaller to evaluate the success rate.In general,from the above in Surfer,Girl,Faceocc2,Car,and Juice sequence, analysis,we find that our original and improved respectively,five trackers except IVT perform well,es- ELSSC-trackers perform almost the same,and the for- pecially the NLSSS-tracker and our two ELSSC-trackers. mer is slightly better,especially in the Dudek, In a complex background and with high illumina- Faceoce2,Surfer,Stone,CarDark,and Jumping se- tion variance Fig.4(f)),there are many similar quences (Fig.5(a,b,c,f,n,o).However,we also stones to track.The I,-tracker and our two trackers find from Table 4,which summarizes the average work better than other three trackers.Cov-tracker fails, frames per second,that the improved ELSST works because it extracts edge information of targets as one much faster than the original ELSST and almost all the dimension of features,and in this sequences,edge of other trackers;IVT is faster than the improved ELSST targets are ambiguous and hard to be distinct.Similar when dealing with Surfer and Dudek sequences,but its results are obtained from Fig.4(h,1,m). success rate is much worse than that of the improved Table 3 summarizes the average success rates. ELSST.It is sensitive under the phenomena of occlu- Given the tracking results R and the ground-truth Rc, sion,rotation,and target motion blur.The original I,- we use the detection criterion in the PASCAL VOC tracker performs well in most frames,but it is also challenget],i.e., time-consuming and fails to track sometimes;Cov- area(Rr∩Rc) Tracking is suitable for occlusion and rotation,but fails score area(Rr URc) when facing a complex background. #219 14 出 (a)Sequence surfer (375 frames) (b)Sequence dudek (1145 frames) (c)Sequence faceoce2 (819 frames) *2 (d)Sequence animal (71 frames) (e)Sequence girl(500 frames) (f)Sequence S tone (593 frames) 106 175 231 (g)Sequence car(374 frames) (h)Sequence cup(303 frames (i)Sequence face (415 frames) 5【年 (j)Sequence juice (404 frames) (k)Sequence singer(351 frames) (1)Sequence sunshade (172 frames)

ｏｖｅｒ， ａｎｄ ｔｈｅ ｊｕｉｃｅ ｂｏｔｔｌｅ ｂｅｃｏｍｅｓ ｂｉｇｇｅｒ ａｎｄ ｓｍａｌｌｅｒ ｉｎ Ｓｕｒｆｅｒ， Ｇｉｒｌ， Ｆａｃｅｏｃｃ２， Ｃａｒ， ａｎｄ Ｊｕｉｃｅ ｓｅｑｕｅｎｃｅ， ｒｅｓｐｅｃｔｉｖｅｌｙ， fiｖｅ ｔｒａｃｋｅｒｓ ｅｘｃｅｐｔ ＩＶＴ ｐｅｒｆｏｒｍ ｗｅｌｌ， ｅｓ⁃ ｐｅｃｉａｌｌｙ ｔｈｅ ＮＬＳＳＳ⁃ｔｒａｃｋｅｒ ａｎｄ ｏｕｒ ｔｗｏ ＥＬＳＳＣ⁃ｔｒａｃｋｅｒｓ． Ｉｎ ａ ｃｏｍｐｌｅｘ ｂａｃｋｇｒｏｕｎｄ ａｎｄ ｗｉｔｈ ｈｉｇｈ ｉｌｌｕｍｉｎａ⁃ ｔｉｏｎ ｖａｒｉａｎｃｅ （ Ｆｉｇ． ４ （ ｆ））， ｔｈｅｒｅ ａｒｅ ｍａｎｙ ｓｉｍｉｌａｒ ｓｔｏｎｅｓ ｔｏ ｔｒａｃｋ． Ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ｏｕｒ ｔｗｏ ｔｒａｃｋｅｒｓ ｗｏｒｋ ｂｅｔｔｅｒ ｔｈａｎ ｏｔｈｅｒ ｔｈｒｅｅ ｔｒａｃｋｅｒｓ． Ｃｏｖ⁃ｔｒａｃｋｅｒ ｆａｉｌｓ， ｂｅｃａｕｓｅ ｉｔ ｅｘｔｒａｃｔｓ ｅｄｇｅ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔａｒｇｅｔｓ ａｓ ｏｎｅ ｄｉｍｅｎｓｉｏｎ ｏｆ ｆｅａｔｕｒｅｓ， ａｎｄ ｉｎ ｔｈｉｓ ｓｅｑｕｅｎｃｅｓ， ｅｄｇｅ ｏｆ ｔａｒｇｅｔｓ ａｒｅ ａｍｂｉｇｕｏｕｓ ａｎｄ ｈａｒｄ ｔｏ ｂｅ ｄｉｓｔｉｎｃｔ． Ｓｉｍｉｌａｒ ｒｅｓｕｌｔｓ ａｒｅ ｏｂｔａｉｎｅｄ ｆｒｏｍ Ｆｉｇ． ４（ｈ，ｌ，ｍ）． Ｔａｂｌｅ ３ ｓｕｍｍａｒｉｚｅｓ ｔｈｅ ａｖｅｒａｇｅ ｓｕｃｃｅｓｓ ｒａｔｅｓ． Ｇｉｖｅｎ ｔｈｅ ｔｒａｃｋｉｎｇ ｒｅｓｕｌｔｓ ＲＴ ａｎｄ ｔｈｅ ｇｒｏｕｎｄ⁃ｔｒｕｔｈ ＲＧ ， ｗｅ ｕｓｅ ｔｈｅ ｄｅｔｅｃｔｉｏｎ ｃｒｉｔｅｒｉｏｎ ｉｎ ｔｈｅ ＰＡＳＣＡＬ ＶＯＣ ｃｈａｌｌｅｎｇｅ ［１６］ ，ｉ．ｅ．， ｓｃｏｒｅ ＝ ａｒｅａ（ＲＴ ∩ ＲＧ ） ａｒｅａ（ＲＴ ∪ ＲＧ ） ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｓｕｃｃｅｓｓ ｒａｔｅ． Ｉｎ ｇｅｎｅｒａｌ， ｆｒｏｍ ｔｈｅ ａｂｏｖｅ ａｎａｌｙｓｉｓ， ｗｅ fiｎｄ ｔｈａｔ ｏｕｒ ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ⁃ｔｒａｃｋｅｒｓ ｐｅｒｆｏｒｍ ａｌｍｏｓｔ ｔｈｅ ｓａｍｅ， ａｎｄ ｔｈｅ ｆｏｒ⁃ ｍｅｒ ｉｓ ｓｌｉｇｈｔｌｙ ｂｅｔｔｅｒ， ｅｓｐｅｃｉａｌｌｙ ｉｎ ｔｈｅ Ｄｕｄｅｋ， Ｆａｃｅｏｃｃ２， Ｓｕｒｆｅｒ， Ｓｔｏｎｅ， ＣａｒＤａｒｋ， ａｎｄ Ｊｕｍｐｉｎｇ ｓｅ⁃ ｑｕｅｎｃｅｓ （Ｆｉｇ． ５ （ ａ， ｂ， ｃ， ｆ， ｎ， ｏ）． Ｈｏｗｅｖｅｒ， ｗｅ ａｌｓｏ fiｎｄ ｆｒｏｍ Ｔａｂｌｅ ４， ｗｈｉｃｈ ｓｕｍｍａｒｉｚｅｓ ｔｈｅ ａｖｅｒａｇｅ ｆｒａｍｅｓ ｐｅｒ ｓｅｃｏｎｄ， ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＴ ｗｏｒｋｓ ｍｕｃｈ ｆａｓｔｅｒ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａｌ ＥＬＳＳＴ ａｎｄ ａｌｍｏｓｔ ａｌｌ ｔｈｅ ｏｔｈｅｒ ｔｒａｃｋｅｒｓ； ＩＶＴ ｉｓ ｆａｓｔｅｒ ｔｈａｎ ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＴ ｗｈｅｎ ｄｅａｌｉｎｇ ｗｉｔｈ Ｓｕｒｆｅｒ ａｎｄ Ｄｕｄｅｋ ｓｅｑｕｅｎｃｅｓ， ｂｕｔ ｉｔｓ ｓｕｃｃｅｓｓ ｒａｔｅ ｉｓ ｍｕｃｈ ｗｏｒｓｅ ｔｈａｎ ｔｈａｔ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＴ． Ｉｔ ｉｓ ｓｅｎｓｉｔｉｖｅ ｕｎｄｅｒ ｔｈｅ ｐｈｅｎｏｍｅｎａ ｏｆ ｏｃｃｌｕ⁃ ｓｉｏｎ， ｒｏｔａｔｉｏｎ， ａｎｄ ｔａｒｇｅｔ ｍｏｔｉｏｎ ｂｌｕｒ． Ｔｈｅ ｏｒｉｇｉｎａｌ ｌ １ ⁃ ｔｒａｃｋｅｒ ｐｅｒｆｏｒｍｓ ｗｅｌｌ ｉｎ ｍｏｓｔ ｆｒａｍｅｓ， ｂｕｔ ｉｔ ｉｓ ａｌｓｏ ｔｉｍｅ⁃ｃｏｎｓｕｍｉｎｇ ａｎｄ ｆａｉｌｓ ｔｏ ｔｒａｃｋ ｓｏｍｅｔｉｍｅｓ； Ｃｏｖ⁃ Ｔｒａｃｋｉｎｇ ｉｓ ｓｕｉｔａｂｌｅ ｆｏｒ ｏｃｃｌｕｓｉｏｎ ａｎｄ ｒｏｔａｔｉｏｎ， ｂｕｔ ｆａｉｌｓ ｗｈｅｎ ｆａｃｉｎｇ ａ ｃｏｍｐｌｅｘ ｂａｃｋｇｒｏｕｎｄ． 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１４３·

·144 智 能系统学 报 第11卷 (m)Sequence bike(228 frames) (n)Sequence cardark(393 frames) (o)Sequence jumping(313 frames) Fig.4 Some tracking results C-tracker NLSSSC-tracker 350 NLSSSC-tracker acker 800 C-tracker 250 ELSS SC-trackerl 300 racker ELSSSC-tracker2 ELSSSC-tracker2 250 II-tracke 700 -11-tracker 200 I-tracker -VT IVT 200 8 150 100 50 100 (E 50 100150200250300350 #Frame #Frame #Frame (a)Sequence surfer(375 frames) (b)Sequence dudek(1145 frames) (c)Sequence faceocc2(819 frames) NLSSSC-tracker NLSSSC-tracker er 300 700 150 NLSSSC-acker 250 racker 600 -tracker2 IVT 200 CovTracking 100 400 CovTracking 300 100 200 0 50 100 nk 100 200.300 400 500 050100150200250300350400 #Frame #F ame #Frame (d)Sequence animal(71 frames) (e)Sequence girl(500 frames) (f)Sequence S tone (593 frames) 350 LSSSC-tracker NISSSC-trac 250 NLSSSC-tracker 300 ELSSSC-trackerl 120 C-trac -tracker 250 ELSSSC-tracker2 100 ELSSSC-tracker2 200 SC-tracke I-tracker tracker cker 200 VT IVT 20 150 CovTracking 00 CovTracking 100 100 50 50 85 0 50 100150200250300350 0 50 100150200 250300 0 50 100150200250300350400 #Frame #Frame #Frame (g)Sequence car(374 frames) (h)Sequence cup (303 frames) (i)Sequence face (415 frames) NLSSSC-tracker -NLSSSC-tracker 400 SC-tracker 500 SC-tracker 500 -tracker 350 ELSSSC-tracker2 ELSSSC-tracker2 C-tracker2 300 11-tracker 400 -tracker IVT 250 CovTracking cking 300 CevTracking 200 150 200 100 5s0 100 100 0 50 100150200250300350 400 0 50 100150200250300350 0 20 40 60 80100120140160 #Frame #Frame #Frame (j)Sequence juice (404 frames) (k)Sequence singer(351 frames) (1)Sequence sunshade (172 frames) NLSSSC-tra cke ker SSS C-tracker NLSSSC-tracker 400 150 -tracker 250 C-tracker 350 I-tracker ELSSSC-tracker2 300 200 II-tracker CovTracking 100 IVT 200 CoyTracking 50 100 50 50 的 50 100 150 200 050100150200250300350400 0 50100150200250300 #Frame #Frame #Frame (m)Sequence bike (228 frames) (n)Sequence cardark(393 frames) (o)Sequence jumping (313 frames) Fig.5 Quantitative evaluation in terms of center location error in pixel)

Ｆｉｇ． ４ Ｓｏｍｅ ｔｒａｃｋｉｎｇ ｒｅｓｕｌｔｓ Ｆｉｇ． ５ Ｑｕａｎｔｉｔａｔｉｖｅ ｅｖａｌｕａｔｉｏｎ ｉｎ ｔｅｒｍｓ ｏｆ ｃｅｎｔｅｒ ｌｏｃａｔｉｏｎ ｅｒｒｏｒ （ｉｎ ｐｉｘｅｌ） ·１４４· 智 能 系 统 学 报 第 １１ 卷

1 WANG Hongyuan,et al:Efficient tracker based on sparse coding with Euclidean local structure-based constraint .145. Table 3 Average Success Rates Video IVT CovTrack 1-tracker NLSSST ELSST1 ELSST2 Sufer 0.0515 0.4770 0.0388 0.4646 0.4667 0.4052 Dudek 0.2011 0.4216 0.6215 0.6528 0.6726 0.6604 Faceocc2 0.4553 0.3918 0.6084 0.4579 0.5747 0.4641 Animal 0.0218 0.2701 0.0336 0.3692 0.4078 0.4117 Girl 0.0228 0.2171 0.4869 0.4853 0.4006 0.4693 Stone 0.0974 0.1114 0.5834 0.4109 0.6611 0.6572 Car 0.0607 0.1858 0.0956 0.3418 0.3278 0.3825 Cup 0.6300 0.3769 0.5598 0.5738 0.5238 0.5637 Face 0.3341 0.2806 0.0479 0.5248 0.5496 0.5827 Juice 0.0743 0.4218 0.5111 0.5299 0.5186 0.5835 Singer 0.3326 0.1361 0.1184 0.5790 0.4781 0.5651 Sunshade 0.0481 0.1803 0.5257 0.5348 0.4743 0.4948 Bike 0.0576 0.3721 0.0451 0.4438 0.3608 0.3917 CarDark 0.0831 0.3087 0.0790 0.0110 0.4208 0.3737 Jumping 0.0577 0.2755 0.0711 0.0847 0.4530 0.4505 The best two results are shown in bold.Our original and improved algorithms are shown in the last two columns,respectively. Table 4 Average Frames per Second Video IVT CovTrack 1-tracker NLSSST ELSSTI ELSST2 Sufer 2.8649 1.5707 0.0358 0.0141 0.0156 2.3469 Dudek 3.3211 1.2454 0.0388 0.0171 0.0179 3.2454 Faceoce2 2.7886 1.1278 0.0180 0.0107 0.0142 3.1278 Animal 1.8979 1.2534 0.0312 0.0150 0.0071 3.2534 Girl 1.6548 1.2209 0.0376 0.0167 0.0098 3.2209 Stone 1.2903 1.8890 0.0271 0.0144 0.0146 4.1138 Car 3.6841 2.8502 0.0621 0.0525 0.0365 6.2253 Cup 7.8175 3.5479 0.0798 0.0677 0.0538 6.3949 Face 6.7422 2.8961 0.0543 0.0417 0.0546 6.1681 Juice 7.0489 3.9297 0.0635 0.0665 0.0586 5.4738 Singer 6.0959 2.8026 0.0195 0.0683 0.0481 6.1891 Sunshade 7.3027 2.7905 0.0713 0.0587 0.0781 6.0601 Bike 6.9747 2.7192 0.0163 0.0320 0.0210 5.8400 CarDark 3.7041 1.3951 0.0226 0.0552 0.0295 2.4221 Jumping 7.3296 2.6080 0.0520 0.0476 0.0579 3.5519 The best two results are shown in bold.Our original and improved algorithms are shown in the last two columns,respectively

Ｔａｂｌｅ ３ Ａｖｅｒａｇｅ Ｓｕｃｃｅｓｓ Ｒａｔｅｓ Ｖｉｄｅｏ ＩＶＴ ＣｏｖＴｒａｃｋ ｌ １ ⁃ｔｒａｃｋｅｒ ＮＬＳＳＳＴ ＥＬＳＳＴ１ ＥＬＳＳＴ２ Ｓｕｆｅｒ ０．０５１ ５ ０．４７７ ０ ０．０３８ ８ ０．４６４ ６ ０．４６６ ７ ０．４０５ ２ Ｄｕｄｅｋ ０．２０１ １ ０．４２１ ６ ０．６２１ ５ ０．６５２ ８ ０．６７２ ６ ０．６６０ ４ Ｆａｃｅｏｃｃ２ ０．４５５ ３ ０．３９１ ８ ０．６０８ ４ ０．４５７ ９ ０．５７４ ７ ０．４６４ １ Ａｎｉｍａｌ ０．０２１ ８ ０．２７０ １ ０．０３３ ６ ０．３６９ ２ ０．４０７ ８ ０．４１１ ７ Ｇｉｒｌ ０．０２２ ８ ０．２１７ １ ０．４８６ ９ ０．４８５ ３ ０．４００ ６ ０．４６９ ３ Ｓｔｏｎｅ ０．０９７ ４ ０．１１１ ４ ０．５８３ ４ ０．４１０ ９ ０．６６１ １ ０．６５７ ２ Ｃａｒ ０．０６０ ７ ０．１８５ ８ ０．０９５ ６ ０．３４１ ８ ０．３２７ ８ ０．３８２ ５ Ｃｕｐ ０．６３０ ０ ０．３７６ ９ ０．５５９ ８ ０．５７３ ８ ０．５２３ ８ ０．５６３ ７ Ｆａｃｅ ０．３３４ １ ０．２８０ ６ ０．０４７ ９ ０．５２４ ８ ０．５４９ ６ ０．５８２ ７ Ｊｕｉｃｅ ０．０７４ ３ ０．４２１ ８ ０．５１１ １ ０．５２９ ９ ０．５１８ ６ ０．５８３ ５ Ｓｉｎｇｅｒ ０．３３２ ６ ０．１３６ １ ０．１１８ ４ ０．５７９ ０ ０．４７８ １ ０．５６５ １ Ｓｕｎｓｈａｄｅ ０．０４８ １ ０．１８０ ３ ０．５２５ ７ ０．５３４ ８ ０．４７４ ３ ０．４９４ ８ Ｂｉｋｅ ０．０５７ ６ ０．３７２ １ ０．０４５ １ ０．４４３ ８ ０．３６０ ８ ０．３９１ ７ ＣａｒＤａｒｋ ０．０８３ １ ０．３０８ ７ ０．０７９ ０ ０．０１１ ０ ０．４２０ ８ ０．３７３ ７ Ｊｕｍｐｉｎｇ ０．０５７ ７ ０．２７５ ５ ０．０７１ １ ０．０８４ ７ ０．４５３ ０ ０．４５０ ５ Ｔｈｅ ｂｅｓｔ ｔｗｏ ｒｅｓｕｌｔｓ ａｒｅ ｓｈｏｗｎ ｉｎ ｂｏｌｄ． Ｏｕｒ ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｓｈｏｗｎ ｉｎ ｔｈｅ ｌａｓｔ ｔｗｏ ｃｏｌｕｍｎｓ， ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｔａｂｌｅ ４ Ａｖｅｒａｇｅ Ｆｒａｍｅｓ ｐｅｒ Ｓｅｃｏｎｄ Ｖｉｄｅｏ ＩＶＴ ＣｏｖＴｒａｃｋ ｌ １ ⁃ｔｒａｃｋｅｒ ＮＬＳＳＳＴ ＥＬＳＳＴ１ ＥＬＳＳＴ２ Ｓｕｆｅｒ ２．８６４ ９ １．５７０ ７ ０．０３５ ８ ０．０１４ １ ０．０１５ ６ ２．３４６ ９ Ｄｕｄｅｋ ３．３２１ １ １．２４５ ４ ０．０３８ ８ ０．０１７ １ ０．０１７ ９ ３．２４５ ４ Ｆａｃｅｏｃｃ２ ２．７８８ ６ １．１２７ ８ ０．０１８ ０ ０．０１０ ７ ０．０１４ ２ ３．１２７ ８ Ａｎｉｍａｌ １．８９７ ９ １．２５３ ４ ０．０３１ ２ ０．０１５ ０ ０．００７ １ ３．２５３ ４ Ｇｉｒｌ １．６５４ ８ １．２２０ ９ ０．０３７ ６ ０．０１６ ７ ０．００９ ８ ３．２２０ ９ Ｓｔｏｎｅ １．２９０ ３ １．８８９ ０ ０．０２７ １ ０．０１４ ４ ０．０１４ ６ ４．１１３ ８ Ｃａｒ ３．６８４ １ ２．８５０ ２ ０．０６２ １ ０．０５２ ５ ０．０３６ ５ ６．２２５ ３ Ｃｕｐ ７．８１７ ５ ３．５４７ ９ ０．０７９ ８ ０．０６７ ７ ０．０５３ ８ ６．３９４ ９ Ｆａｃｅ ６．７４２ ２ ２．８９６ １ ０．０５４ ３ ０．０４１ ７ ０．０５４ ６ ６．１６８ １ Ｊｕｉｃｅ ７．０４８ ９ ３．９２９ ７ ０．０６３ ５ ０．０６６ ５ ０．０５８ ６ ５．４７３ ８ Ｓｉｎｇｅｒ ６．０９５ ９ ２．８０２ ６ ０．０１９ ５ ０．０６８ ３ ０．０４８ １ ６．１８９ １ Ｓｕｎｓｈａｄｅ ７．３０２ ７ ２．７９０ ５ ０．０７１ ３ ０．０５８ ７ ０．０７８ １ ６．０６０ １ Ｂｉｋｅ ６．９７４ ７ ２．７１９ ２ ０．０１６ ３ ０．０３２ ０ ０．０２１ ０ ５．８４０ ０ ＣａｒＤａｒｋ ３．７０４ １ １．３９５ １ ０．０２２ ６ ０．０５５ ２ ０．０２９ ５ ２．４２２ １ Ｊｕｍｐｉｎｇ ７．３２９ ６ ２．６０８ ０ ０．０５２ ０ ０．０４７ ６ ０．０５７ ９ ３．５５１ ９ Ｔｈｅ ｂｅｓｔ ｔｗｏ ｒｅｓｕｌｔｓ ａｒｅ ｓｈｏｗｎ ｉｎ ｂｏｌｄ． Ｏｕｒ ｏｒｉｇｉｎａｌ ａｎｄ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｓｈｏｗｎ ｉｎ ｔｈｅ ｌａｓｔ ｔｗｏ ｃｏｌｕｍｎｓ， ｒｅｓｐｅｃｔｉｖｅｌｙ． 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１４５·