黎曼核局部线性编码

引用本文

姜伟, 毕婷婷, 李克秋, 杨炳儒. 黎曼核局部线性编码[J].软件学报,2015, 26(7): 1812-1823.http://www.jos.org.cn/1000-9825/4714.html 复制到剪切板

JIANG Wei, BI Ting-Ting, LI Ke-Qiu, YANG Bing-Ru. Local Linear Coding Based on Riemannian Kernel[J]. Ruan Jian Xue Bao/ Journal of Software, 2015, 26(7): 1812-1823.http://www.jos.org.cn/1000-9825/4714.html 复制到剪切板

黎曼核局部线性编码

姜伟¹ , 毕婷婷¹, 李克秋², 杨炳儒³

1. 辽宁师范大学数学学院, 辽宁大连 116029;
2. 大连理工大学计算机科学与技术学院, 辽宁大连 116024;
3. 北京科技大学计算机与通信工程学院, 北京 100083

收稿时间: 2014-05-06; 修改时间: 2014-06-28; 定稿时间: 2014-09-01

基金项目:国家自然科学基金(61175048); 辽宁省教育厅科学研究项目(L2013408)

作者简介：毕婷婷(1990－),女,硕士,主要研究领域为机器学习,模式识别,图像处理.
李克秋(1972－),男,博士,教授,博士生导师,CCF 杰出会员,主要研究领域为云计算,图像处理.
杨炳儒(1943－),男,博士,教授,博士生导师,CCF 高级会员,主要研究领域为知识发现,柔性建模.

通讯作者：姜伟(1969－),男,辽宁大连人,博士,副教授,CCF 会员,主要研究领域为机器学习, 模式识别,图像处理.E-mail:

摘要：最近的研究表明:在许多计算机视觉任务中,将对称正定矩阵表示为黎曼流形上的点能够获得更好的识别性能.然而,已有大多数算法仅由切空间局部逼近黎曼流形,不能有效地刻画样本分布.受核方法的启发,提出了一种新的黎曼核局部线性编码方法,并成功地应用于视觉分类问题.首先,借助于最近所提出的黎曼核,把对称正定矩阵映射到再生核希尔伯特空间中,通过局部线性编码理论建立稀疏编码和黎曼字典学习数学模型;其次,结合凸优化方法,给出了黎曼核局部线性编码的字典学习算法;最后,构造一个迭代更新算法优化目标函数,并且利用最近邻分类器完成测试样本的鉴别.在3个视觉分类数据集上的实验结果表明,该算法在分类精度上获得了相当大的提升.

关键词：黎曼流形对称正定矩阵切空间局部约束线性编码稀疏表示

Local Linear Coding Based on Riemannian Kernel

JIANG Wei¹ , BI Ting-Ting¹, LI Ke-Qiu², YANG Bing-Ru³

1. School of Mathematics, Liaoning Normal University, Dalian 116029, China;
2. School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China;
3. School of Computer & Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China

Corresponding author:

Abstract: Recent research has shown that better recognition performance can be attained through representing symmetric positive definite matrices as points on Riemannian manifolds for many computer vision tasks. However, most existing algorithms only approximate the Riemannian manifold locally by its tangent space and are incapable of scaling effectively distribution of samples. Inspired by kernel methods, a novel method, called local linear coding based on Riemannian kernel (LLCRK), is proposed and applied successfully to vision classification issues. Firstly, with the aid of recently introduced Riemannian kernel, symmetric positive definite matrices are mapped into the reproducing kernel Hilbert space by kernel method and a mathematical model of sparse coding and Riemannian dictionary learning is constructed by local linear coding theory. Secondly, an efficient algorithm of LLCRK is presented for dictionary learning according to the convex optimization methods. Finally, an iterative updating algorithm is constructed to optimize the objective function, and the test samples are classified by nearest neighbor classifier. Experimental results on three visual classification data sets demonstrate that the proposed algorithm achieves considerable improvement in discrimination accuracy.

Key words: Riemannian manifold symmetric positive definite matrix tangent space locality-constrained linear coding sparserepresentation

稀疏表示(sparse representation,简称SR)源于对经典信号表示的扩展,已广泛应用于机器学习、模式识别以及信号处理等许多领域.SR的核心思想是:信号在适当选取一组过完备基(overcomplete bases)或称字典(dictionary)下,使用尽可能少的基向量来简洁地表达输入信号,以此来揭示信号的内在结构和本质属性.2006年, Huang等人^[1]首次将稀疏表示方法应用于分类研究,开启了稀疏表示理论与应用研究的热潮;Cai等人^[2]通过对数据投影方向施加稀疏性限制,构造了统一的稀疏子空间学习模型;Raina等人^[3]利用稀疏表示设计了自教(self- taught)学习方法,基于此,从大量无标签数据中获取高层语义特征;Mairal等人^{[4, 5]}提出许多应用于纹理分类、手写数字识别等任务的稀疏表示算法;Wright等人^[6]基于压缩感知^[7]理论与稀疏表示提出的SRC(sparse representation-based classification)分类器在某些标准人脸数据集上获得了非常好的效果.稀疏编码研究表明:非零系数的基更靠近编码数据,基于此,Yu等人^[8]在研究高维非线性Lipschitz平滑函数进行学习时,基于流形假设,提出了一种在高维非线性流形上的半监督学习方法.该方法是将高维的非线性学习问题转化为简单的全局线性学习问题,通过局部坐标编码(local coordinate coding,简称LCC)学习得到基向量的一组锚点,构成一个局部坐标系,流形上的每个点仅由几个近邻锚点的线性组合来拟合,而线性组合的权重系数就是这个点的局部坐标编码,从而实现稀疏和局部一致性^[9].受LCC方法启发,局部约束线性编码(locality-constrainedlinear coding,简称LLC)^[10]方法同样是在编码时施以局部性约束,但优化问题的求解效率却很高.LLC编码可以看作是LCC编码的一种快速实现.

然而,SR和LLC是在欧几里德空间框架下,应用欧氏测度来执行字典学习.正如研究物理问题的时空不完全是欧氏空间一样,我们所面临的数据未必分布在欧氏空间.认知心理学研究表明:就感知数据而言,样本空间用弯曲的黎曼流形表达,能够对样本给出很好的解释.在计算机视觉领域,对称正定(symmetric positive define,简称SPD)矩阵所诱导的结构非常有用,形成一个非欧、弯曲的黎曼流形,提供了紧凑的目标模型表示方法,融合了图像多种特征,对目标大小、形状和光照变化等具有很强的鲁棒性,成功地应用在目标跟踪^[11]、人脸识别^[12]、纹理分类^[13]、行人检测^[14]和动作识别^[15]等领域.

作为是一种新型、有效的特征表示模式,可以用矩阵在欧氏空间计算框架下处理SPD矩阵,最简单的方法是把nxn维SPD矩阵看作是一个Rⁿ^(n+1)/2向量,这样,应用欧氏空间相似测度来评价SPD矩阵之间的相似度.向量化对称正定矩阵,欧氏距离忽略特征空间的结构信息,降低了特征的有效性.为此,Pennec等人^[11]给SPD矩阵空间赋予一种仿射不变黎曼度量(affineinvariant Riemannian metric,简称AIRM),使SPD矩阵空间晋升为黎曼流形,但利用AIRM来度量两个对称正定矩阵之间距离是很耗时的.Tuzel等人^[15]提出了采用图像的区域协方差矩阵(即,对称正定矩阵)作为描述子,在所有正例样本的均值处构建切空间,并把所有特征映射到切空间上,训练多个弱分类器,利用LogitBoosting算法将多个弱分类器整合为一个强分类器,实现两类分类问题.切空间的分类问题是基于流形在局部上与欧氏空间存在着同胚(diffeomorphsim)映射,这导致指数与对数映射只在一个局部邻域内是一一映射,因此,流形上的点没有全局坐标.针对以上问题,Arsigny等人^[16]通过在对称正定矩阵空间上赋予Log-Euclidean测度代替AIRM,形成一种李群结构.这样,Log-Euclidean框架定义了一个从黎曼流形到向量空间同构、同胚与等距映射.在此基础上,Tosato等人^[17]进一步将两类问题推广到多类.最近,Carreira等人^[18]基于Log-Euclidean测度,利用支持向量机对多类问题进行分类,较许多state-of-the-art方法更有效.

基于黎曼流形理论,可先通过对数映射将SPD矩阵映射到切空间进行相应的计算,再通过指数算子映射回原空间获得最终分析结果.该思想可以非常方便地将欧氏空间的学习方法推广到黎曼空间,但此类方法存在两个局限性:第一,需要频繁使用对数映射与指数映射,使算法的效率低下;第二,切空间上的欧氏距离只是流形上测地距离的近似.为了克服这种局限性,借助于黎曼核,将黎曼流形上的点映射到一个更高维甚至是无限维的再生核Hilbert空间.进而,将欧氏空间的数据分析方法推广到黎曼流形^{[19, 20, 21, 22, 23]}.在许多情况下,这类方法比切空间方法具有更优的性能.受此启发,Li等人^[24]提出了基于黎曼核的稀疏表示与字典学习方法,在学习过程,考虑数据的几何结构,并在黎曼空间更新字典矩阵.然而,局部性具有比稀疏性更重要、更本质的特性,因为局部性必然导致稀疏性,反之则不成立.基于以上分析,本文结合局部坐标编码与黎曼核方法的思想,提出了黎曼核局部线性编码(local linear codingbased on Riemannian kernel,简称LLCRK)方法,以对称正定矩阵为输入单位,通过黎曼核将其映射到一个更高维甚至是无限维的特征空间,由此,黎曼流形上的局部线性编码问题转化为特征空间的局部线性编码问题.通过局部线性编码理论,构建字典与编码学习的数学模型.结合最优化理论,给出了高效的优化算法.

1.1 黎曼流形

设M是一个d维黎曼流形,则对于任意一点X∈M,都有X的一个开邻域与欧氏空间R^d的一个开子集同胚.点X所有切向量全体张成的线性空间称为M在点X处的切空间,记为T_XM;切空间矢量v∈T_XM的范数记为$||v||_X^2 = {\langle v,v\rangle _X}$;X与Y两点之间的距离是连接X与Y的一条光滑曲线,测地线为所有在流形上连接X和Y的最短光滑曲线;对于完备流形来说,任意两点之间只存在一条测地线.切空间T_XM构成向量空间,而黎曼流形M是非向量空间.流形、测地线、切空间和切矢量的关系如图 1所示.通过黎曼指数映射E_X:T_X→M映射切向量v到黎曼流形M上从点X出发等长同向测地线.E_X逆映射L_X:M→T_XM将黎曼流形M上点X到点Y测地线映射为切空间T_X中等长同向矢量v.对于X,Y∈M,从X到Y测地线的切向量定义为$v = \overrightarrow {XY} = {L_X}(Y),$并且指数映射将v映射到流形上的点Y=E_X(v).

Fig.1 Geodesic and tangent vector 图 1 测地线与切向量

设S⁺(n)={X|X∈S(n),u^TXu>0,∀u∈$\mathbb{R}$ⁿ}表示n×n阶对称正定矩阵集合,则S⁺(n)是一个可微的黎曼流形M.对于任意矩阵P∈S⁺(n),P可被分解为P=ULU^T,其中,U为P的特征向量构成的矩阵,L是对角矩阵,则相应指数与对数运算为

$\begin{array}{l} \exp (P) = \sum\limits_{k = 0}^\infty {\frac{{{P^k}}}{{k!}}} = U\exp (\Lambda ){U^T},\\ \log (P) = \sum\limits_{k = 0}^\infty {\frac{{{{( - 1)}^{k - 1}}}}{k}} {(P - I)^k} = U\log (\Lambda ){U^T}. \end{array}$

对于黎曼流形M上的任意一点X,均可做一切空间T_XM与流形M的微分同胚.对于切空间中每一个切向量S_i,可通过指数映射将S_i映射为流形M上从点X出发的等长同向的测地线,则指数映射定义为

E_X(S_i)=P_i=X^1/2exp(X^-1/2S_iX^-1/2)X^1/2,

其中,exp(·)表示矩阵指数算子.

而指数映射逆映射,即对数映射定义为

L_X(P_i)=S_i=X^1/2log(X^-1/2P_iX^-1/2)X^1/2,

其中,log(·)表示矩阵对数算子.

1.2 稀疏表示与局部线性编码 1.2.1 稀疏表示

稀疏表示^[25]是在一定的误差范围内,从一组过完备基$\{ {d_i} \in {\mathbb{R}^m}\} _{i = 1}^n$组成的集合中选取少量基信号,线性表示输入信号x∈$\mathbb{R}$^m.通常,这些基被称之为原子,它们的集合称为字典,稀疏表示数学模型定义如下:

$\left\{ \begin{gathered} \mathop {\min }\limits_\alpha ||\alpha |{|_0} \hfill \\ {\text{s}}{\text{.t}}{\text{. }}x = D\alpha \hfill \\ \end{gathered} \right.$

(1)

其中,D=[d₁,d₂,…,d_n]∈$\mathbb{R}$^m^xⁿ为基矩阵,α∈$\mathbb{R}$ⁿ为系数向量,向量α的ℓ₀范数表示向量中非零元素的数目.但是,公式(1)已被证明是一个NP-hard问题,计算非常复杂.知名学者Donoho^[7],Candes和Tao^[26]已证明:在足够稀疏的条件下,ℓ₁范数等价ℓ₀范数,即:

$\left\{ \begin{gathered} \mathop {\min }\limits_\alpha ||\alpha |{|_1} \hfill \\ {\text{s}}{\text{.t}}{\text{. }}x = D\alpha \hfill \\ \end{gathered} \right.$

(2)

由于ℓ₁范数是凸的,所以公式(2)是凸优化问题.考虑到信号通常被噪声污染,在公式(2)中引入噪声项,则稀疏表示模型为

$\mathop {\min }\limits_x ||\alpha |{|_1},{\text{ s}}{\text{.t}}{\text{. }}||x - D\alpha |{|_2} \leqslant \varepsilon $

(3)

另外,稀疏表示模型还可表示为如下正则化表达方式:

$\mathop {\min }\limits_x \frac{1}{2}||x - D\alpha ||_2^2 + \lambda ||\alpha |{|_1}$

(4)

其中,λ为正则化参数,用于均衡稀疏性与稀疏表达误差.

1.2.2 局部线性编码

局部线性编码是将数据信号x∈$\mathbb{R}$^m分解为锚点的线性组合.也就是说,每个数据信号是由数据点近邻的少数几个基信号或者字典原子的线性组合,局部线性编码严格的数学模型如下所示:

$\{ \hat D,\{ {\hat \alpha _i}\} _1^N\} = \mathop {\min }\limits_{D \in \wp ,\alpha } \sum\limits_i {\left( {\frac{1}{2}||{x_i} - D{\alpha _i}||_2^2 + \mu \sum\limits_j {|\alpha _i^j|} ||{d_j} - {x_i}||_2^2} \right)} $

(5)

其中,D=[d₁,…,d_n]∈$\mathbb{R}$^m^xⁿ为基矩阵,℘={D|||d_i||≤1,i=1,…,n}是D的凸可行集,a_i∈Rⁿ是重构系数.目标函数的第1项为重构误差;第2项表示局部性,物理意义是数据点x离字典原子d_j越近,其重构系数越大.参数μ用于折中目标函数中两项的重要程度,||·||₂表示ℓ₂范数.由于目标函数中有两个变量,目标函数对于它们不能同时是凸的,但如果一个固定,则对另一个量,其目标函数是凸的.因此,我们首先固定字典D,求解稀疏编码α,那么目标函数(5)变换为如下形式:

$\hat \alpha = \mathop {\min }\limits_\alpha \frac{1}{2}||x - D\alpha ||_2^2 + \mu \sum\limits_j {|{\alpha ^j}|} ||{d_j} - x||_2^2$

(6)

令${\Lambda _{jj}} = ||{d_j} - x||_2^2$,β=Λα,并且假设d_j≠x,则目标函数(6)改写为如下形式:

$\hat \beta = \mathop {\min }\limits_\beta \frac{1}{2}||x - D{\Lambda ^{ - 1}}\beta ||_2^2 + \mu ||\beta |{|_1}$

(7)

其中,$||\beta |{|_1} = \sum\nolimits_j {|{\beta ^j}|} $表示β的ℓ₁范数.

令Γ_i=DΛ^-1,公式(7)被重写为

$\hat \beta = \mathop {\min }\limits_\beta \frac{1}{2}||x - \Gamma \beta ||_2^2 + \mu ||\beta |{|_1}$

(8)

这等价于标准的稀疏编码,我们可以利用feature-sign-search^[27]算法优化目标函数求得稀疏编码.获得数据信号的稀疏编码以后,再把字典D看作未知变量,对其进行优化,重写目标函数(5)如下:

$\hat D = \mathop {\min }\limits_{D \in \wp } \frac{1}{2}||x - D\alpha ||_2^2 + \mu \sum\limits_j {|{\alpha ^j}|} ||{d_j} - x||_2^2$

(9)

显然,公式(9)是一个二次规划问题,我们可以利用块坐标下降法和随机梯度下降法求解.

2 黎曼核局部线性编码

S⁺(n)不是欧氏空间,而是一个可微的黎曼流形,没有点积运算,因此,欧式空间的核函数不能用于对称正定矩阵样本集.基于此,最近几年,黎曼核得到广泛的研究,文献^[14]给出了基于测地距离的伪核.

k_R(X,Y)=exp{-σ^-1d_G(X,Y)}

(10)

其中,${d_G}(X,Y) = trace\left( {{{\log }^2}\left( {{X^{ - \frac{1}{2}}}Y{X^{ - \frac{1}{2}}}} \right)} \right)$,trace(×)表示矩阵的迹.最近,Sra等人^[19]使用Bregman测度引入半正定Stein核,即:

$k(X,Y) = {{\text{e}}^{ - \sigma S(X,Y)}} = {2^{d\sigma }}\frac{{\sqrt {\det {{(X)}^\sigma }\det {{(Y)}^\sigma }} }}{{\det {{(X + Y)}^\sigma }}}$

(11)

其中,$\sigma \in \left\{ {\frac{1}{2},\frac{2}{2},...,\frac{{d - 1}}{2}} \right\} \cup \left\{ {\tau \in \mathbb{R}:\tau > \frac{{d - 1}}{2}} \right\}$,d为X的行数,或者列数.Li等人^[24]研究了Log-Euclidean黎曼度量下协方差矩阵的李群结构,给出了黎曼正定核函数表达:

k_R(X,Y)=exp(-γ||log(X)-log(Y)||²)

(12)

第1种把欧式空间的高斯核函数引入黎曼流形的方式是,仅将欧式空间距离函数替换仿射不变黎曼度量(affine invariant Riemannian metric,简称AIRM)^[28],这样并不能确保替换后一定是正定核;第2种核函数使用Stein度量近似测地距离,只有在核宽度s取某些值的情况下,才能保证正定性;第3种克服了前两种的缺点,所提出的核函数能够有效地刻画测地距离,这样可以精确地测量重建误差,并且也满足Mercer条件.因此,本文采用第3种核进行数据分析.

2.1 目标函数

给定d维黎曼流形M中的一个样本集X=[X₁,X₂,…,X_N],X是对称正定矩阵集合,N为样本总数.黎曼流形框架上局部线性编码的基本思想是:首先,通过非线性映射f将分布在黎曼流形M上的样本映射到再生核Hilbert空间F中,即,Φ(X)=[Φ(X₁),…,Φ(X_N)];然后,在空F中实现局部线性编码.这样,黎曼流形框架上局部线性编码准则函数可表示为

$\{ \hat D,\{ {\hat \alpha _i}\} _1^N\} = \mathop {\min }\limits_{D \in \wp ,{\alpha _i} \in {\mathbb{R}^n}} \sum\limits_{i = 1}^N {\left( {||\phi ({X_i}) - \phi (D){\alpha _i}||_2^2 + \mu \sum\limits_{k = 1}^n {|\alpha _i^k|} ||\phi ({D_k}) - \phi ({X_i})||_2^2} \right)} $

(13)

其中,X_i是样本集X中的第i个样本;${\alpha _i} = {[\alpha _i^1,...,\alpha _i^n]^T}$是X_i的稀疏表示向量;D_k是字典原子,并且D=[D₁,D₂,…,D_n]; 参数μ用于折中目标函数两项的重要程度.

2.2 优化算法

目标函数是D和α_i非凸函数,因此它没有闭式解(close-form solution).本文构建了一种迭代算法用以优化这个目标函数,其核心思想是:固定字典矩阵D,求出一个最优的稀疏编码向量α_i;然后固定α_i,求出一个最优的字典D,当某个迭代终止条件满足时,输出字典D和编码向量α_i.对于每一个样本X_i,在给定D的情况下,对稀疏编码α_i学习,重写目标函数(13)如下:

${\hat \alpha _i} = \mathop {\min }\limits_{{\alpha _i} \in {\mathbb{R}^n}} \left( {||\phi ({X_i}) - \phi (D){\alpha _i}||_2^2 + \mu \sum\limits_{j = 1}^n {|\alpha _i^j|} ||\phi ({D_j}) - \phi ({X_i})||_2^2} \right)$

(14)

令对角矩阵Λ_i的对角元素为${\Lambda _i}(k,k) = ||\phi ({X_i}) - \phi ({D_k})||_2^2,$k=1,…,n;b_i=Λ_iα_i,并且假设D_j≠X_i,则目标函数(14)改写为如下形式:

${\hat \beta _i} = \mathop {\min }\limits_{{\beta _i}} \frac{1}{2}||\phi ({X_i}) - \phi (D)\Lambda _i^{ - 1}{\beta _i}||_2^2 + \mu ||{\beta _i}|{|_1}$

(15)

其中,$||{\beta _i}|{|_1} = \sum\nolimits_j {|\beta _i^j|} $表示β_i的ℓ₁范数.

展开目标函数(15),除去与β_i无关的项,利用核函数重写目标函数为

${\hat \beta _i} = \mathop {\arg \min }\limits_{{\beta _i}} k({X_i},{X_i}) + \beta _i^T\Lambda _i^{ - 1}K(D,D)\Lambda _i^{ - 1}\beta - 2K({X_i},D)\Lambda _i^{ - 1}{\beta _i} + \mu ||{\beta _i}|{|_1}$

(16)

其中,

·K(X_i,D)=[a_j]_n_x₁,a_j=k(X_i,D_j);

·K(D,D)=[a_ij]_n_x_n,a_ij=k(D_i,D_j);

·${\Lambda _i}(k,k) = ||\phi ({X_i}) - \phi ({D_k})||_2^2 = K({X_i},{X_i}) + K({D_k},{D_k}) - 2K({X_i},{D_k}).$

我们可以利用feature-sign-search优化目标函数求得稀疏编码.获得数据信号的稀疏编码后,对字典D进行学习,重写目标函数(13),展开并除去与字典无关项,即:

$\begin{gathered} J = \mathop {\min }\limits_{D \in \wp } \sum\limits_{i = 1}^N {\left( {\left\| {\phi ({X_i}) - \sum\limits_{j = 1}^n {\alpha _i^j\phi ({D_j})} } \right\|_{{\text{ }}2}^{{\text{ }}2} + \mu \sum\limits_{k = 1}^n {|\alpha _i^k|} ||\phi ({D_k}) - \phi ({X_i})||_2^2} \right)} \\ = \mathop {\min }\limits_{D \in \wp } \sum\limits_{i = 1}^N {\left( {\frac{1}{2}\sum\limits_{j = 1}^n {\sum\limits_{q = 1}^n {\alpha _i^j\alpha _i^q\phi {{({D_j})}^T}\phi ({D_q})} } - \sum\limits_{j = 1}^n {\alpha _i^j\phi {{({D_j})}^T}\phi ({X_i})} + \mu \sum\limits_{k = 1}^n {|\alpha _i^k|(\phi {{({D_k})}^T}\phi ({D_k}) - 2\phi {{({D_k})}^T}\phi ({X_i}))} } \right)} \\ = \mathop {\min }\limits_{D \in \wp } \sum\limits_{i = 1}^N {\left( {\frac{1}{2}\sum\limits_{j = 1}^n {\sum\limits_{q = 1}^n {\alpha _i^j\alpha _i^qK({D_j},{D_q})} } - \sum\limits_{j = 1}^n {\alpha _i^jK({D_j},{X_i})} + \mu \sum\limits_{k = 1}^n {|\alpha _i^k|} (K({D_k},{D_k}) - 2K({D_k},{X_i}))} \right)} \\ \end{gathered} $

(17)

采用迭代优化字典每一原子的方法来进行字典学习.设当前需要优化的字典第m原子为D_m,m∈(1,2,…,n),对目标函数(17)求导,可得:

$\frac{{\partial J}}{{\partial {D_m}}} = - \frac{1}{{{D_m}}}\gamma \sum\limits_{i = 1}^N {\left( {\frac{1}{2}\sum\limits_{q = 1}^n {\alpha _i^m\alpha _i^qK({D_m},{D_q})} (\log {D_m} - \log {D_q}) - K({D_m},{X_i})(\log {D_m} - \log {X_i})(\alpha _i^m + |\alpha _i^m|)} \right)} $

(18)

为了获得优化的D_m,令$\partial $J/$\partial $D_m=0.这样,我们很容易得到logD_m.然而,由于目标函数中存在核函数项K(D_m,×)和logD_q,求解仍很困难.因此,采用迭代算法来获得近似解.在第k次迭代中,我们使用第k-1次结果计算核函数项K(D_m,×)和logD_q.采用文献^[24]中提供的方法获得字典更新的表达式,即:

${D_m} = \exp (\log ({D_m}) + {d_{{D_m}}}\log ( - \varepsilon \partial f/\partial {D_m}))$

(19)

其中,${d_{{D_m}}}(U)$表示在D_m点的矩阵对数与切矩阵U位移之差.

2.3 算法描述

输入:来自黎曼流形上的训练集$X = \{ {X_i}\} _{i = 1}^N$,X_i为对称正定矩阵;测试样本Y;核函数;

输出:黎曼字典$D = \{ {D_i}\} _{i = 1}^n.$

步骤1. 从X中随机选取n个样本初始化字典D={D_i};

步骤2. 根据当前D,由公式(16)求解稀疏表示β_i,再由${\alpha _i} = \Lambda _i^{ - 1}{\beta _i};$

步骤3. 固定α_i,由公式(17)求得D;

步骤4. 返回步骤2,直至目标函数的值在连续两次迭代中足够接近或达到最大迭代次数.

3 实验

为了保证实验的充分性与广泛性,选用了3个具有不同特点的数据集,分别是Brodatz纹理数据集、ETHZ行人数据集和FERET人脸数据集,以验证LLCRK算法的有效性.实验中采用协方差矩阵(即,对称正定矩阵)表示图像,以此构成Riemannian流形上的数据.设I表示灰度图像灰度值或三维彩色图像分量集合,F是从图像I中提取的图像特征,则有:

F(x,y)=Φ(I,x,y),

其中,Φ表示与图像属性有关的映射,比如灰度、颜色和梯度等.Φ(I,x,y)的值域可以张成d维实空间,所有像素对应的Φ(I,x,y)值均为d维实空间中的一点.对于给定目标区域,区域内所有像素对应的Φ值可以表示为$\{ {z_i}\} _{i = 1}^n$,z_i为d维实向量,n为区域内像素个数,则目标区域协方差矩阵C_R定义为

${C_R} = \frac{1}{{n - 1}}\sum\limits_{k = 1}^n {({z_k} - \mu ){{({z_k} - \mu )}^T}} ,$

其中,μ为向量集$\{ {z_i}\} _{i = 1}^n$的均值.

3.1 数据集描述

在我们的实验中用到了3个数据集,数据集的信息汇总如下.

·Brodatz纹理数据集

该数据集包括111幅640x640的纹理图像,也即有111个不同纹理类,具有256个灰度级.图 2显示了来自Brodatz纹理数据集的部分纹理图像.首先把每张图像不重叠地分割成16张160x160的子图,即,每类含有16个数据,共1 776个数据.实验中取$\phi (I,x,y) = {\left( {x,y,I(x,y),\left| {\frac{{\partial I}}{{\partial x}}} \right|,\left| {\frac{{\partial I}}{{\partial y}}} \right|,\left| {\frac{{{\partial ^2}I}}{{\partial {x^2}}}} \right|,\left| {\frac{{{\partial ^2}I}}{{\partial {y^2}}}} \right|} \right)^T}$,其中,I(x,y)坐标为(x,y)处灰度值, $\frac{{\partial I}}{{\partial x}}$为(x,y)处横向一阶梯度,$\frac{{\partial I}}{{\partial y}}$为(x,y)处纵向一阶梯度,$\frac{{{\partial ^2}I}}{{\partial {x^2}}}$为(x,y)处横向二阶梯度,$\frac{{{\partial ^2}I}}{{\partial {y^2}}}$为(x,y)处纵向二阶梯度.这样,得到z_i的维数是7维,计算得到C_R为7x7的对称正定矩阵.

Fig.2 Some textureimages from Brodatz texturedata set 图 2 来自Brodatz纹理数据集的部分纹理图像

·ETHZ行人数据集

该数据集广泛用于视频跟踪和人体目标再识别算法的实验评价,由移动像机从不同角度拍摄的3个图像序列组成,提供了一系列行人外观变化.第1个图像序列包括83个行人的4 857幅图像;第2个图像序列包括35个行人的1 936幅图像;第3个图像序列包括28个行人的1 762幅图像.这些跟踪序列包含部分遮挡、严重遮挡以及剧烈光照变化的图像.图 3显示了来自ETHZ数据集的部分行人图像.为了描述每幅图像,使用如下特征计算方差加以描述:$\phi (I,x,y) = [x,y,{R_{x,y}},{G_{x,y}},{B_{x,y}},{R'_{x,y}},{G'_{x,y}},{B'_{x,y}},{R''_{x,y}},{G''_{x,y}},{B''_{x,y}}],$其中,x,y表示像素的位置.R_x_,y,G_x_,y和B_x_,y分别表示相应的颜色信息,而且,${C'_{x,y}} = \left[ {\left| {\frac{{\partial C}}{{\partial x}}} \right|,\left| {\frac{{\partial C}}{{\partial y}}} \right|} \right]$和${C''_{x,y}} = \left[ {\left| {\frac{{{\partial ^2}C}}{{\partial {x^2}}}} \right|,\left| {\frac{{{\partial ^2}C}}{{\partial {y^2}}}} \right|} \right]$分别表示颜色C的梯度和拉普拉斯算子.这样得到z_i的维数是11维,计算得到C_R为11x11的对称正定矩阵.

Fig.3 Some pedestrian images from ETHZdata set 图 3 来自ETHZ数据集的部分行人图像

·FERET人脸数据集

该数据集由1 199人的14126幅人脸图像组成,包括不同表情、光照条件、姿态以及不同时间拍摄的图像.本文选取其中带有‘b’的一个子集进行算法性能评价,该子集由198个人组成,每个人7幅图片.在实验中,所有人脸图像都经过了标准化处理,即:首先标定出人脸图像中两眼的位置,并在该位置将图像对齐;然后,剪切出图像中的面部区域,并将其缩放成统一的64x64大小.图 4显示了来自FERET数据集的部分人脸图像,这些图像包含了ba,bd,be,bf,bg,bj,bk这7种标识符.实验中,取x,y坐标,(x,y)处灰度值,选择5个尺度、8个方向Gabor变换提取图像的局部特征,得到z_i的维数是43维.这样,计算得到C_R为43x43的对称正定矩阵.

Fig.4 Some face images of one person fromFERET data set 图 4 来自FERET数据集中某个人的部分人脸图像

3.2 实验环境设置

针对LLCRK算法与其他相关算法的关系,对比算法包括:

·稀疏表示分类(sparserepresentation-based classification,简称SRC)^[6];

·局部限制线性编码(locality-constrainedlinear coding,简称LLC)^[10];

·张量稀疏编码(tensorsparse coding,简称TSC)^[29];

·Log-Euclidean稀疏表示(log-Euclidean sparse representation,简称logE-SR)^[30];

·基于Stein核的黎曼稀疏表示(Riemannian sparserepresentation,简称RSR)^[19];

·Log-Euclidean核稀疏表示(log-Euclidean sparse representation,简称logE-KSR)^[24].

其中,SRC是经典稀疏表示学习算法,LLC是由局部限制所诱导出的稀疏表示分类学习算法,这两种算法处理的数据用向量表示,是基于非黎曼框架的方法;TSC扩展了基于向量形式的稀疏编码,编码的对象是对称正定矩阵,衡量两个对称正定矩阵的逼近程度是LogDet散度;logE-SR利用黎曼测度度量对称正定矩阵之间的距离,并在对数域进行稀疏分解;RSR利用半正定Stein核在高维希尔伯特空间度量黎曼流形两点之间的相似性,并在该空间求解稀疏表示;logE-KSR利用正定高斯核度量黎曼流形点与点之间的相似性测度,基于此进行稀疏分解.

实验中涉及到的算法均需设置参数,为了公平起见,对每一种算法,我们都尝试了多种参数的设置,最后选择最佳的参数作为最终实验结果.对于RSR算法,Stein核参数σ的搜索范围为$\left\{ {\frac{1}{2},\frac{2}{2},...,\frac{{m - 1}}{2}} \right\}$,m为对称正定矩阵的行数或者列数.对于我们所提出的算法,核函数选择公式(12)给出的黎曼核,其中,g遍历集合{10^-4,10^-3,10^-2, 10^-1,10⁰,10¹,10²}的所有值.

对于Brodatz纹理数据集,随机地选取每类中的t(t=8,10,12)个图像作为训练数据,其余作为测试数据进行实验.对于ETHZ行人集,为了计算上方便起见,将图像统一缩放至64x32分辨率,对于每个行人,随机地选择t=10张图像作为训练集,剩下的作为测试集;对于FERET人脸数据集,随机地选取每个人的t(t=3,4,5)个图像作为训练数据,剩下的作为测试数据进行实验.对每种数据集的训练\测试分割,重复10轮,得到训练数据集和测试数据集的不同划分,平均识别率作为最终性能指标.在实验中,首先基于训练集提取特征,构造一个超完备字典,分别利用以上算法获得数据紧致的稀疏表示,进而采用简单的最近邻分类器对得到的稀疏特征进行分类.

3.3 识别率

基于上述数据集和环境设置,表 1~表 3列出了不同算法的最优识别率及其对应的标准差和字典原子个数.图 5~图 7显示了不同算法的分类性能对字典原子个数变化曲线,横坐标表示字典原子个数,纵坐标为识别率.

Table 1 Performance of different algorithmson Brodatz dataset表 1 Brodatz数据集上不同算法的性能

Table 2 Performance of different algorithmson ETHZ dataset表 2 ETHZ数据集上不同算法的性能

Table 3 Performance of different algorithms on FERET dataset表 3 FERET数据集上不同算法的性能

Fig.5 Recognition rate curves of different algorithms versus different numbers of atoms for Braodatz dataset 图 5 不同算法在Brodatz数据集中随着字典原子个数变化的识别率曲线图

Fig.6 Recognition rate curves of different algorithms versus different numbers of atoms for ETHZ dataset 图 6 不同算法在ETHZ数据集中随着字典原子个数变化的识别率曲线图

Fig.7 Recognition rate curves of different algorithms versus different numbers of atoms for FERET dataset 图 7 不同算法在FERET数据集中随着字典原子数变化的识别率曲线图

3.4 参数敏感性

参数选择是一个公开问题,没有可靠的理论作为依据,这部分主要考察正则化参数μ与黎曼核参数γ对分类精度的影响.具体而言,我们在FERET数据集中随机地选取每类中的3个数据作为训练集,其余作为测试数据进行实验,通过最近邻分类器计算分类识别率.实验对每种训练\测试分割,重复10轮,得到训练数据集和测试数据集的不同划分,平均识别率作为最终性能指标.图 8显示了固定字典原子个数为500和正则化参数μ=10,遍历不同核参数γ所对应的识别率.图 9显示了固定字典原子个数为500和核参数γ=1,不同正则化参数μ,LLCRK在FERET数据集上识别率的对比情况.

Fig.8 Classification accuracies using different kernel parameter γ? 图 8 不同核参数γ对应的识别率

Fig.9 lassification accuracies using different regularization parameter μ 图 9 不同正则化参数μ对应的识别率

3.5 实验结果总体讨论

上面我们在3个不同图像数据集上对所提算法进行了较为全面的评价,表 1~表 3列出了各种算法对应的最好结果及其对应的标准差和字典原子数,图 5~图 7给出了各种算法平均识别率对字典原子数变化曲线,图 8、图 9分别对参数的敏感性进行了研究性实验.从上述实验结果可以得到如下主要结论:

(1)通过实验中在相同数据集下各种算法识别率的综合比较,TSC算法的效果在矩阵表示方法中最差.这表明,黎曼测度较欧氏测度能够在一定程度上刻画数据的非线性结构,可更有效地保留数据判别信息;

(2)只要字典原子个数超过某个阈值,LCCRK均一致地超过其余的4种算法,这说明,具有局部限制结构与正定黎曼核相融合的方法更有助于刻画数据的非线性流形结构,因而在实验中能够获得最优的识别性能;

(3)字典原子的个数并不是越多越好,当字典原子达到饱和时,再继续增加字典原子个数,识别率反而下降.这也印证了字典原子增多反而会破坏稀疏性条件,使识别率有所降低的结论;

(4)算法缺点:算法中使用了核函数,且核函数由于需要进行对数运算,其算法时间复杂度相对较高,很难推广到大数据中.考虑使用Nystrom等算法来加速核函数的计算,是进一步的研究方向.

4 总结

本文提出一种新颖的黎曼核局部线性编码分析算法,在黎曼流形框架下,将数据从原始的黎曼流形上映射到一个更高维甚至是无穷维的特征空间中,进而把局部线性编码与黎曼核整合在单目标函数中,提取用对称正定矩阵所描述数据有效稀疏表示.在所有数据集上,LCCRK算法在实验中表现得最好,主要是因为LCCRK同时考虑了数据的局部性和非线性性质,并且全面继承了logE-KSR算法的优点,从而得到最优的识别性能.进一步的研究方向:考虑使用Nystrom等算法来加速核函数的计算和探索高效的核函数,实现黎曼流形上局部线性编码.

致谢在此,我们向对本文的工作给予支持和建议的同行,尤其是北京交通大学计算机科学技术系于剑教授来辽宁师范大学进行学术交流时给予的指导表示感谢.

参考文献

[1]	Huang K, Aviyente S. Sparse representation for signalclassification. In: Proc. of the Advances in Neural Information ProcessingSystems. 2006. 609-616. http://papers.nips.cc/paper/3130-sparse-representation-for-signal-classification.pdf
[2]	Cai D, He XF, Han JW. Spectral regression: A unified approach forsparse subspace learning. In: Proc. of the IEEE Int’l Conf. on Data Mining.2007. 73-82 .
[3]	Raina R, Battle A, Lee H, Packer B, Ng AY. Self-Taught learning: Transferlearning from unlabeled data. In: Proc. of the Int’l Conf. on Machine Learning.Oregon: ACM Press, 2007. 759-766 .
[4]	Mairal J, Bach F, Ponce J, Sapiro G, Zisserman A. Supervised dictionarylearning. In: Proc. of the Advances in Neural Information Processing Systems.2008. http://papers.nips.cc/paper/3448-supervised-dictionary-learning.pdf
[5]	Mairal J, Bach F, Ponce J, Sapiro G, Zisserman A. Discriminative learned dictionaries for local image analysis. In:Proc. of the 2008 IEEE Conf. on Computer Vision and Pattern Recognition. Anchorage:IEEE Computer Society Press, 2008. 1-8 .
[6]	Wright J, Yang AY, Ganesh A, Sastry SS, Ma Y. Robust facerecognition via sparse representation. IEEE Trans. on Pattern Analysis andMachine Intelligence, 2009,31(2):210-227 .
[7]	Donoho DL. Compressed sensing. IEEE Trans. on Information Theory,2006,52(4):1289-1306 .
[8]	Yu K, Zhang T, Gong Y. Nonlinear learning using local coordinatecoding. In: Proc. of the Advances in Neural Information Processing Systems,Vol.22. 2009. 2223-2231. http://papers.nips.cc/paper/3875-nonlinear-learning-using-local-coordinate-coding.pdf
[9]	Wei CP, Chao YW, Yeh YR, Wang YCF. Locality-Sensitive dictionary learningfor sparse representation based classification. Pattern Recognition, 2013,46(5):1277-1287 .
[10]	Wang JJ, Yang JC, Yu K, Lü F, Huang TS. Gong YH. Locality-Constrainedlinear coding for image classification. In: Proc. of the 2010 IEEE Int’l Conf.on Computer Vision. Washington: IEEE Computer Society Press, 2010.3360-3367 .
[11]	Hu WM, Li X, Luo WH, Zhang XQ, Maybank S, Zhang ZF. Single andmultiple object tracking using log-Euclidean Riemannian subspace andblock-division appearance model. IEEE Trans. on Pattern Analysis and MachineIntelligence, 2012,34(12): 2420-2440 .
[12]	Pang Y, Yuan Y, Li X. Gabor-Based region covariance matrices forface recognition. IEEE Trans. on Circuits and Systems for Video Technology,2008,18(7):989-993 .
[13]	Bak S, Corvee E, Bremond F, Thonnat M. Boosted humanre-identification using Riemannian manifolds. Journal Image and VisionComputing, 2012,30(6-7):443-452 .
[14]	Harandi MT, Sanderson C, Wiliem A, Lovell BC. Kernel analysis overRiemannian manifolds for visual recognition of actions, pedestrians andtextures. In: Proc. of the 2012 IEEE Workshop on the Applications of ComputerVision. Washington: IEEE Computer Society Press, 2012.433-439 .
[15]	Tuzel O, Porikli F, Meer P. Pedestrian detection via classificationon Riemannian manifolds. IEEE Trans. on Pattern Analysis and Intelligence,2008,30(10):1713-1727 .
[16]	Arsigny V, Fillard P, Pennec X, Ayache N. Geometric means in a novelvector space structure on symmetric positive-definite matrices. SIAM Journal onMatrix Analysis and Applications, 2006,29(1):328-347 .
[17]	Tosato D, Farenzena M, Cristani M, Spera M, Murino V. Multi-Classclassification on Riemannian manifolds for video surveillance. In: Proc. of the11th European Conf. on Computer Vision. Heraklion: Eurographics AssociationPress, 2010.378-391 .
[18]	Carreira J, Caseiro R, Batista J, Sminchisescu C. Semantic segmentationwith second-order pooling. In: Proc. of the 12th European Conf. on ComputerVision. Heraklion: Eurographics Association Press, 2012.430-443 .
[19]	Harandi MT, Sanderson C, Hartley R, Lovel BC. Sparse coding and dictionarylearning for symmetric positive definite matrices: A kernel approach. In: Proc.of the 12th European Conf. on Computer Vision. Heraklion: EurographicsAssociation Press, 2012.216-229 .
[20]	Jayasumana S, Hartley R, Salzmann M, Li H, Harandi MT. Kernel methodson the Riemannian manifold of symmetric positive definite matrices. In: Proc.of the 2013 IEEE Conf. on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2013.73-80 .
[21]	Harandi MT, Sanderson C, Shen CH, Lovell B. Dictionary learning andsparse coding on Grassmann manifolds: An extrinsic solution. In: Proc. of the2013 IEEE Int’l Conf. on Computer Vision. Washington: IEEE Computer SocietyPress, 2013.3120-3127 .
[22]	Sanin A, Sanderson C, Harandi MT, Lovell BC. Spatio-Temporal covariancedescriptors for action and gesture recognition. In: Proc. of the IEEE Workshopon Applications of Computer Vision (WACV). Washington: IEEE Computer SocietyPress, 2013.103-110 .
[23]	Jayasumana S, Hartley R, Salzmann M, Li HD, Harandi MT. Combining multiplemanifold-alued descriptors for improved object recognition. In: Proc. of theDigital Image Computing: Techniques and Applications. 2013.1-6 .
[24]	Li PH, Wang QL, Zuo WM, Zhang L. Log-Euclidean kernels for sparse representationand dictionary learning. In: Proc. of the 2013 IEEE Int’l Conf. on ComputerVision. Washington: IEEE Computer Society Press, 2013.1601-1608 .
[25]	Chen SS, Donoho DL, Saunders MA. Atomic decomposition by basispursuit. Journal of SIAM Review, 2001,43(1):129-159 .
[26]	Candes E, Tao T. Near optimal signal recovery from randomprojections: Universal encoding strategies? IEEE Trans. on Information Theory,2006,52(12):5406-5425 .
[27]	Lee H, Battle A, Raina R, Andrew YN. Efficient sparse codingalgorithms. In: Proc. of the Advances in Neural Information Processing Systems.2006. 801-808. http://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf
[28]	Pennec X, Fillard P, Ayache N. A Riemannian framework for tensorcomputing. Int’l Journal of Computer Vision, 2006,66(1): 41-66 .
[29]	Sivalingam R, Boley D, Morellas V, Papanikolopoulos N. Tensor sparsecoding for region covariances. In: Proc. of the 11th European Conf. on ComputerVision. Berlin: Eurographics Association Press, 2010.722-735 .
[30]	Guo K, Ishwar P, Konrad J. Action recognition using sparserepresentation on covariance manifolds of optical flow. In: Proc. of the 20107th IEEE Int’l Conf. on Advanced Video and Signal Based Surveillance.Washington: IEEE Computer Society Press, 2010.188-195 .