第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ｅｃｔｉｖｅ ａｎｄ ａｃｃｕｒａｔｅ ｔｏ ｉｎｉｔｉａｌｉｚｅ ｃ０ ａｓ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｏｕｒ ｔｒａｃｋｅｒ ｉｓ ｏｆ ｔｈｅ ｓａｍｅ ｏｒｄｅｒ ｏｆ ｍａｇｎｉｔｕｄｅ ａｓ ｔｈａｔ ｏｆ ｔｈｅ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＴ． Ｗｈｅｎ ｗｅ ｒｅｓｉｚｅ ａｌｌ ｎ ＝ １０ ｔａｒ⁃ ｇｅｔｓ ａｎｄ Ｎ ＝ ２００ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎｓ ｔｏ ４０ × ４０， ｉ．ｅ．， ｍ ＝ １ ６００ （ Ｆｉｇｓ． １ ａｎｄ ２）， ｔｈｅｎ ｔｈｅ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ ｉｓ １ ６００ × ３ ２１０ ａｎｄ ｔｈｅ ｏｒｔｈｏｇｏｎａｌ ｍａ⁃ ｔｒｉｘ Ｖ ｉｓ ３ ２１０ × ３ ２１０ ｉｎ Ｅｑ． （１０）． Ｉｔ ｉｓ ｖｅｒｙ ｄｉｆｆｉｃｕｌｔ ｔｏ ｓｏｌｖｅ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｗｉｔｈ ｓｕｃｈ ａ Ｄ （ ｉｎ ｌ １ ⁃ｔｒａｃｋｅｒ ａｎｄ ＮＬＳＳＳＴ） ｏｒ Ｖ （ ｉｎ ｏｕｒ ＥＬＳＳＴ）． Ｗｉｔｈ ｔｈｅ ｉｍｐｒｏｖｅｄ ＥＬＳＳＣ， Σ′ ｉｓ ｔｈｅ ｆｉｒｓｔ ｔｅｎ ｒｏｗｓ ｏｆ Σ， ａｎｄ Ｖ′ ｃｏｎｓｉｓｔｓ ｏｆ ｔｈｅ ｆｉｒｓｔ ｔｅｎ ｒｏｗｓ ａｎｄ ｆｉｒｓｔ ｔｅｎ ｃｏｌｕｍｎｓ ｏｆ Ｖ． Ｔｈｕｓ， ｅａｃｈ ｉｔｅｒａｔｉｏｎ ｏｆ ｅａｃｈ ｃａｎｄｉｄａｔｅ ｒｅｇｉｏｎ ｉｎ ＥＬＳＳＴ ｃａｎ ｂｅ ｒｅｄｕｃｅｄ ｆｒｏｍ ｔｈｅ ｌａｒｇｅ⁃ｓｃａｌｅ ｌ １ ⁃ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｔｏ ａ ｍｕｃｈ ｓｍａｌｌｅｒ ｏｎｅ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｍｕｃｈ ｓｍａｌｌｅｒ ｓｃａｌｅ Ｖ′ ∈ Ｒ １０×１０ ． Ｔｏ ｏｖｅｒｃｏｍｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｏｃｃｌｕｓｉｏｎｓ ｉｎ ｔｒａｃｋｉｎｇ， ｔｈｅ ａｎａｌｏｇｏｕｓ ｔｒｉｖｉａｌ ｔｅｍｐｌａｔｅｓ ａｒｅ ｕｓｅｄ ｔｏ ｃｏｎｓｔｒｕｃｔ ｔｈｅ ｎｅｗ ｄｉｃｔｉｏｎａ⁃ ｒｙＶ″ ∈ Ｒ １０×３０ ， ｉ．ｅ．， ａ ｔｅｎ⁃ｏｒｄｅｒｅｄ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ ａｎｄ ｔｅｎ⁃ｏｒｄｅｒｅｄ ｎｅｇａｔｉｖｅ ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ． ·１４０· 智 能 系 统 学 报 第 １１ 卷