第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ｅｃｔｉｖｅｎｅｓｓ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ⁃ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ； ｌ １ ⁃ｔｒａｃｋｅｒ； ｓｐａｒｓｅ ｃｏｄｉｎｇ； ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ＣＬＣ Ｎｕｍｂｅｒ：ＴＰ１８； ＴＰ３０１．６ Ｄｏｃｕｍｅｎｔ Ｃｏｄｅ：Ａ Ａｒｔｉｃｌｅ ＩＤ：１６７３⁃４７８５（２０１６）０１⁃０１３６⁃１２ Ｃｉｔａｔｉｏｎ：ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ＺＨＡＮＧ Ｊｉ， ＣＨＥＮ Ｆｕｈｕａ． Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃ⁃ ｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（１）： １３６⁃１４７． Ｒｅｃｅｉｖｅｄ Ｄａｔｅ：２０１５⁃０７⁃３１． Ｏｎｌｉｎｅ Ｐｕｌｉｃａｔｉｏｎ：２０１５⁃０９⁃３０． Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍ： Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒａｎｔ （６１５７２０８５，６１５０２０５８）． Ｃｏｒｒｅｓｐｏｎｄｉｎｇ Ａｕｔｈｏｒ：Ｈｏｎｇｙｕａｎ Ｗａｎｇ． Ｅ⁃ｍａｉｌ： ｈｙｗａｎｇ＠ ｃｃｚｕ．ｅｄｕ．ｃｎ． Ｒｅｃｅｎｔｌｙ， ｖｉｓｕａｌ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ｗａｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｓｅｃｕｒｉｔｙ ｓｕｒｖｅｉｌｌａｎｃｅ， ｎａｖｉｇａｔｉｏｎ， ｈｕｍａｎ⁃ｃｏｍｐｕｔｅｒ ｉｎｔｅｒａｃｔｉｏｎ， ａｎｄ ｏｔｈｅｒ ａｐｐｌｉｃａｔｉｏｎｓ ［１⁃２］ ． Ｉｎ ａ ｖｉｄｅｏ ｓｅ⁃ ｑｕｅｎｃｅ， ｔａｒｇｅｔｓ ｆｏｒ ｔｒａｃｋｉｎｇ ｏｆｔｅｎ ｃｈａｎｇｅ ｄｙｎａｍｉｃａｌｌｙ ａｎｄ ｕｎｃｅｒｔａｉｎｌｙ ｂｅｃａｕｓｅ ｏｆ ｄｉｓｔｕｒｂａｎｃｅ ｐｈｅｎｏｍｅｎａ ｓｕｃｈ ａｓ ｏｃｃｌｕｓｉｏｎ， ｎｏｉｓｙ ａｎｄ ｖａｒｙｉｎｇ ｉｌｌｕｍｉｎａｔｉｏｎ， ａｎｄ ｏｂｊｅｃｔ ａｐｐｅａｒａｎｃｅ． Ｍａｎｙ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｗｅｒｅ ｐｒｏ⁃ ｐｏｓｅｄ ｉｎ ｔｈｅ ｌａｓｔ ｔｗｅｎｔｙ ｙｅａｒｓ ｔｈａｔ ｃａｎ ｂｅ ｄｉｖｉｄｅｄ ｉｎｔｏ ｔｗｏ ｃａｔｅｇｏｒｉｅｓ： ｇｅｎｅｒａｔｉｖｅ ｔｒａｃｋｉｎｇ ａｎｄ ｄｉｓｃｒｉｍｉｎａｎｔ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍｓ ［１⁃２］ ． Ｇｅｎｅｒａｔｉｖｅ ａｌｇｏｒｉｔｈｍｓ （ ｅ． ｇ．， ｅｉｇｅｎ ｔｒａｃｋｅｒ， ｍｅａｎ⁃ｓｈｉｆｔ ｔｒａｃｋｅｒ， ｉｎｃｒｅｍｅｎｔａｌ ｔｒａｃｋｅｒ， ｃｏｖａｒｉａｎｃｅ ｔｒａｃｋｅｒ ［２］ ） ａｄｏｐｔ ａｐｐｅａｒａｎｃｅ ｍｏｄｅｌｓ ｔｏ ｅｘ⁃ ｐｒｅｓｓ ｔｈｅ ｔａｒｇｅｔ ｏｂｓｅｒｖａｔｉｏｎｓ， ｗｈｅｒｅａｓ ｄｉｓｃｒｉｍｉｎａｎｔ ａｌ⁃ ｇｏｒｉｔｈｍｓ （ ｅ． ｇ．， ＴＬＤ ［３］ ， ｅｎｓｅｍｂｌｅ ｔｒａｃｋｉｎｇ ［４］ ， ａｎｄ ＭＩＬＴｒａｃｋ ［５］ ） ｖｉｅｗ ｔｒａｃｋｉｎｇ ａｓ ａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍ， ｔｈｕｓ ａｔｔｅｍｐｔｉｎｇ ｔｏ ｄｉｓｔｉｎｇｕｉｓｈ ｔｈｅ ｔａｒｇｅｔ ｆｒｏｍ ｔｈｅ ｂａｃｋｇｒｏｕｎｄｓ． Ｈｅｒｅ， ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗ ｇｅｎｅｒａｔｉｖｅ ａｌｇｏ⁃ ｒｉｔｈｍ． Ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ （ ＳＣ； ａｌｓｏ ｒｅｆｅｒｒｅｄ ｔｏ ａｓ ｓｐａｒｓｅ ｓｅｎｓｉｎｇ ｏｒ ｃｏｍｐｒｅｓｓｉｖｅ ｓｅｎｓｉｎｇ） ［６⁃７］ ， Ｍｅｉ ｐｒｏ⁃ ｐｏｓｅｄ ａｎ ｌ １ ⁃ｔｒａｃｋｅｒ ｆｏｒ ｇｅｎｅｒａｔｉｖｅ ｔｒａｃｋｉｎｇ ［８⁃９］ ， ａｄ⁃ ｄｒｅｓｓｉｎｇ ｏｃｃｌｕｓｉｏｎ， ｃｏｒｒｕｐｔｉｏｎ， ａｎｄ ｓｏｍｅ ｏｔｈｅｒ ｃｈａｌ⁃ ｌｅｎｇｉｎｇ ｉｓｓｕｅｓ． Ｈｏｗｅｖｅｒ， ｔｈｉｓ ｔｒａｃｋｅｒ ｉｎｃｕｒｓ ａ ｖｅｒｙ ｈｉｇｈ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｓｔ ｔｏ ａｃｈｉｅｖｅ ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｉｎｇ （ｓｅｅ ｓｅｃｔｉｏｎ ２．１ ａｎｄ Ｆｉｇ．１ ｆｏｒ ｄｅｔａｉｌｓ）， ａｎｄ ｔｈｅ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅｓ ｏｆ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ ａｒｅ ｉｇｎｏｒｅｄ， ｗｈｉｃｈ ｍａｙ ｃａｕｓｅ ｔｈｅ ｉｎｓｔａｂｉｌｉｔｙ ａｎｄ ｅｖｅｎ ｆａｉｌｕｒｅ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ． Ｉｎｄｅｅｄ， ｔｈｅ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ， ｆｏｒ ｒｅｐｒｅｓｅｎｔｉｎｇ ｓｉｘ ｓｉｍｉｌａｒ ｒｅｇｉｏｎｓ （ＣＲ１ －ＣＲ６ ） ｕｎｄｅｒ ｔｅｎ ｔｅｍｐｌａｔｅ ｒｅｇｉｏｎｓ （ Ｔ１ －Ｔ１０ ） ｗｉｔｈ ｏｒｉｇｉｎａｌ ｌ １ ⁃ｔｒａｃｋｅｒ， ａｒｅ ｄｉｖｅｒｓｉｆｉｅｄ （Ｆｉｇ． ３）． Ｃｏｎｓｉｄｅｒｉｎｇ ＣＲ１ ａｎｄ ＣＲ４ ， ｆｏｒ ｅｘａｍｐｌｅ， ｗｅ ｃａｎ ｓｅｅ ｔｈａｔ ａｌｔｈｏｕｇｈ ｔｈｅ ｌａｔｔｅｒ ｉｓ ａｌｍｏｓｔ ｔｈｅ ｐａｒｔｉａｌ ｏｃｃｌｕ⁃ ｓｉｏｎ ｖｅｒｓｉｏｎ ｏｆ ｔｈｅ ｆｏｒｍｅｒ， ｔｈｅｉｒ ｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ ａｒｅ ｖｅｒｙ ｄｉｆｆｅｒｅｎｔ． Ｔｒａｃｋｉｎｇ ＣＲ４ （ ｔｈｅ ｗｏｍａｎ􀆳ｓ ｆａｃｅ） ｍａｙ ｆａｉｌ， ｂｅｃａｕｓｅ ｔｈｅ ｔｒａｃｋｅｒ ｉｓ ｌｉｋｅｌｙ ｔｏ ｉｎｃｏｒｒｅｃｔｌｙ ｃｏｎｓｉｄｅｒ ｔｈｅ ｒｅｇｉｏｎ Ｔ８（ｔｈｅ ｂｏｏｋ） ａｓ ｉｔｓ ｔａｒｇｅｔ． Ｃｏｎｔｒａｒｙ ｔｏ ｅｘｐｅｃｔａｔｉｏｎｓ， Ｘｕ ｐｒｏｖｅｄ ｔｈａｔ ａ ｓｐａｒｓｅ ａｌｇｏｒｉｔｈｍ ｃａｎｎｏｔ ｂｅ ｓｔａｂｌｅ ａｎｄ ｔｈａｔ ｓｉｍｉｌａｒ ｓｉｇｎａｌｓ ｍａｙ ｎｏｔ ｅｘｈｉｂｉｔ ｓｉｍｉｌａｒ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔｓ ［１０］ ． Ｔｈｕｓ， ａ