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