2. 哈尔滨工业大学深圳研究生院 生物计算研究中心, 广东 深圳 518055;
3. 广东技术师范学院 科研处, 广州 510665
2. Bio-Computing Research Center, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen Guangdong 518055, China;
3. Department of Scientific Research, Guangdong Polytechnic Normal University, Guangzhou Guangdong 510665, China
稀疏编码利用一组“超完备”的基向量高效地表示样本数据,被广泛的应用于图像处理、模式识别和计算机视觉等领域。字典学习是稀疏编码的一个重要研究方向,其基本思想是从训练样本中学习一组“超完备”的基向量,该组基向量通常称为字典,每个基向量称为一个原子。判别字典学习(Discriminative Dictionary Learning, DDL)是字典学习的一个重要研究分支,其核心问题是如何设计判别式约束项提高字典的判别性能。由于训练样本的类标特征在模式分类中起到非常重要的作用,研究者提出许多基于训练样本类标特征约束的判别字典学习算法[1-3]。典型的算法是Yang等[2]提出的Fisher判别字典学习(Fisher DDL, FDDL)算法。该算法根据同类训练样本对应的编码系数应该比不同类训练样本对应的编码系数更相似,构造基于编码系数的Fisher准则作为判别式约束项,并根据不同类原子对样本的重构性能构造判别性保真度约束项,提高了字典学习算法的分类性能。随后,Cai等[3]提出利用训练样本类标构造自适应的编码系数权重的支持矢量指导的字典学习(Support Vector Guided Dictionary Learning, SVGDL)算法,并认为FDDL算法是SVGDL算法的一种特殊形式。上述算法目的都是促使同类的训练样本对应的编码系数尽可能地相似,提高判别字典学习算法的分类性能。但是它们都忽略了同类原子和不同类原子间的关系,降低了字典的判别性能。
为了利用原子的特征,研究者利用特定类字典学习算法为原子分配类标,提出利用原子类标与其他特征构造约束项的判别字典学习算法[4-6]。Jiang等[4]利用原子类标与编码系数构造类标一致的K奇异值分解算法(Label Consistent K-means-based Singular Value Decomposition, LC-KSVD)算法提高编码系数的判别性能。由于LC-KSVD算法仅仅考虑了原子类标特征,忽略了原子间的相似性特征,提高字典的判别性能有限。为此,Li等[5]利用原子的类标和局部特征构造嵌入约束的字典学习(Locality Constrained and Label Embedding Dictionary Learning, LCLE-DL)算法。虽然LCLE-DL算法考虑了同类原子间的相似性,但是忽略了不同类原子间的差异,也可能影响字典的判别性能。
由于理想情况下同类训练样本应该单独由某些原子进行重构,并且这些原子的类标与重构的训练样本一致[7]。因此,在字典学习算法中,应该尽可能地增大不同类原子间的差异,减少同类原子间的自相关性。然而,上述字典学习算法并没有利用该特征。为了利用原子间的相似性和自相关性特征,本文提出基于原子Fisher判别准则约束的字典学习算法AFDDL (Fisher Discriminative Dictionary Learning of Atoms)。该算法利用同类原子和不同类原子的散度矩阵的迹的差作为判别式约束项,增大不同类原子间的差异并减少原子间的自相关性,增强字典的判别性能,提高字典学习算法的分类性能。
1 原子的Fisher判别准则根据文献[4]可知,如果为字典中的每个原子分配一个类标,并利用原子类标构造判别式约束项,可以提高字典的判别性能。利用特定类字典学习算法,可把训练样本的类标分配给对应的原子。假设:X=[x1, x2, …, xr]∈Rv×r是训练样本集合;v是训练样本的维数;r是训练样本的个数;D=[d1, d2, …, dk]∈Rv×k是字典,di∈Rv是第i个原子;k是原子个数;Y=[y1, y2, …, yr]∈Rk×r是编码系数矩阵,yi=[y1i, y2i, …, yki]T∈Rk(1≤i≤r)是第i个训练样本对应于字典D的编码系数。原子类标的分配方法如下:
1) 针对第i类训练样本,利用K-SVD算法学习一个特定类字典Di。因此,c类训练样本可以学习得到特定类字典D=[D1, D2, …, Di, …, Dc],字典D包含c类原子。
2) 由于字典Di是利用第i类训练样本学习得到,如果原子di∈Di,则原子di的类标可定义为hi=[0, 0, …,0, 1, 0, …, 0]∈Rc(1≤i≤c), hi中的第i个元素为1,其余c-1个元素均为零。因此,字典D中的原子类标矩阵H可以定义为H=[h1, h2, …, hk]T∈Rk×c。
一旦获得原子类标,可以计算原子的类内散度矩阵SW(D)和类间散度矩阵SB(D)。
${\mathit{\boldsymbol{S}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right) = \sum\limits_{i = 1}^k {\sum\limits_{{{\mathit{\boldsymbol{d}}}_i} \in {{\mathit{\boldsymbol{D}}}_j}} {\left( {{{\mathit{\boldsymbol{d}}}_i} - {{\mathit{\boldsymbol{m}}}_j}} \right)} } {\left( {{{\mathit{\boldsymbol{d}}}_i} - {{\mathit{\boldsymbol{m}}}_j}} \right)^{\rm{T}}}$ | (1) |
${{\mathit{\boldsymbol{S}}}_{\rm{B}}}\left( {\mathit{\boldsymbol{D}}} \right) = \sum\limits_{i = 1}^c {{n_i}\left( {{{\mathit{\boldsymbol{m}}}_i} - {\mathit{\boldsymbol{m}}}} \right){{\left( {{{\mathit{\boldsymbol{m}}}_i} - {\mathit{\boldsymbol{m}}}} \right)}^{\rm{T}}}} $ | (2) |
其中:Di表示第i类原子;mi表示第i类原子的均值矢量;ni表示第i类原子的数目;m是所有原子的均值矢量;c是原子的类数。在字典学习中,原子个数的选择有很多种方式。根据文献[4],假设字典中的原子个数等于训练样本个数,且每类原子个数都为f,则字典中原子个数k=c×f。
因此,式(1) 可以转换为式(3):
${{\mathit{\boldsymbol{S}}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right) = \sum\limits_{i = 1}^c {\sum\limits_{j = 1, {\rm{ }}{{\mathit{\boldsymbol{d}}}_j} \in {{\mathit{\boldsymbol{D}}}_i}, }^f {\left( {{{\mathit{\boldsymbol{d}}}_j} - {{\mathit{\boldsymbol{m}}}_i}} \right)} } {\left( {{{\mathit{\boldsymbol{d}}}_j} - {{\mathit{\boldsymbol{m}}}_i}} \right)^{\rm{T}}}$ | (3) |
式(3) 中的第i类原子对应的散度矩阵计算如式(4):
$\begin{array}{l} \left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 1}} - {{\mathit{\boldsymbol{m}}}_i}} \right){\left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 1}} - {{\mathit{\boldsymbol{m}}}_i}} \right)^{\rm{T}}} + \left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 2}} - {{\mathit{\boldsymbol{m}}}_i}} \right){\left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 2}} - {{\mathit{\boldsymbol{m}}}_i}} \right)^{\rm{T}}} + \\ \quad \cdots + \left( {{{\mathit{\boldsymbol{d}}}_{if}} - {{\mathit{\boldsymbol{m}}}_i}} \right){\left( {{{\mathit{\boldsymbol{d}}}_{if}} - {{\mathit{\boldsymbol{m}}}_i}} \right)^{\rm{T}}}\\ \quad = {{\mathit{\boldsymbol{d}}}_{(i - 1)f + 1}}{\left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 1}}} \right)^{\rm{T}}} + {{\mathit{\boldsymbol{d}}}_{(i - 1)f + 2}}{\left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 2}}} \right)^{\rm{T}}}{\rm{ + }} \cdots + {{\mathit{\boldsymbol{d}}}_{if}}{\left( {{{\mathit{\boldsymbol{d}}}_{if}}} \right)^{\rm{T}}} + \\ \quad f{{\mathit{\boldsymbol{m}}}_i}{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)^{\rm{T}}} - 2\left( {{{\mathit{\boldsymbol{d}}}_{(i - 1)f + 1}}{{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}} + {{\mathit{\boldsymbol{d}}}_{(i - 1)f + 2}}{{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}}{\rm{ + }} \cdots + {{\mathit{\boldsymbol{d}}}_{if}}{{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}}} \right) \end{array}$ | (4) |
把式(4) 代入式(3),类内散度矩阵SW(D)可以利用式(5) 计算:
$\begin{array}{l} {{\mathit{\boldsymbol{S}}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right) = \sum\limits_{i = 1}^k {{{\mathit{\boldsymbol{d}}}_i}{{\left( {{{\mathit{\boldsymbol{d}}}_i}} \right)}^{\rm{T}}}} + f\sum\limits_{i = 1}^c {{{\mathit{\boldsymbol{m}}}_i}{{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}}} \\ \quad - 2\sum\limits_{i = 1}^c {\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right){{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}}} \end{array}$ | (5) |
由于mi是第i类原子的均值矢量,即mi=(d(i-1) f+1+d(i-1) f+2+…+dif)/f,因此式(5) 可以转换为式(6):
$\begin{array}{l} {{\mathit{\boldsymbol{S}}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right) = \sum\limits_{i = 1}^k {{{\mathit{\boldsymbol{d}}}_i}{{\left( {{{\mathit{\boldsymbol{d}}}_i}} \right)}^{\rm{T}}}} - \\ \quad \frac{1}{f}\sum\limits_{i = 1}^c {\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right) \cdot} \\ \quad {\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right)^{\rm{T}}} \end{array}$ | (6) |
另外,原子的类间散度矩阵计算式(2) 可以转换为式(7):
$\begin{array}{l} {{\mathit{\boldsymbol{S}}}_{\rm{B}}}\left( {\mathit{\boldsymbol{D}}} \right) = f\sum\limits_{i = 1}^c {\left( {{{\mathit{\boldsymbol{m}}}_i} - {\mathit{\boldsymbol{m}}}} \right){{\left( {{{\mathit{\boldsymbol{m}}}_i} - {\mathit{\boldsymbol{m}}}} \right)}^{\rm{T}}}} \\ \quad = f\sum\limits_{i = 1}^c {{{\mathit{\boldsymbol{m}}}_i}{{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}} + fc} {\mathit{\boldsymbol{m}}}{\left( {\mathit{\boldsymbol{m}}} \right)^{\rm{T}}} - 2f\sum\limits_{i = 1}^c {{{\mathit{\boldsymbol{m}}}_i}{{\left( {\mathit{\boldsymbol{m}}} \right)}^{\rm{T}}}} \end{array}$ | (7) |
由于m是所有原子的均值矢量,即
$\begin{array}{*{20}{l}} {{{\mathit{\boldsymbol{S}}}_B}\left( {\mathit{\boldsymbol{D}}} \right) = f\sum\limits_{i = 1}^c {{{\mathit{\boldsymbol{m}}}_i}{{\left( {{{\mathit{\boldsymbol{m}}}_i}} \right)}^{\rm{T}}} + k} {\mathit{\boldsymbol{m}}}{{\left( {\mathit{\boldsymbol{m}}} \right)}^{\rm{T}}} - 2f\sum\limits_{i = 1}^c {{{\mathit{\boldsymbol{m}}}_i}{{\left( {\mathit{\boldsymbol{m}}} \right)}^{\rm{T}}}} = }\\ \begin{array}{l} \quad \frac{1}{f}\sum\limits_{i = 1}^c {(\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right)} \cdot \\ \quad {\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right)^{\rm{T}}}) - \end{array}\\ {\quad \frac{1}{k}\left( {{{\mathit{\boldsymbol{d}}}_1} + {{\mathit{\boldsymbol{d}}}_2} + \cdots + {{\mathit{\boldsymbol{d}}}_f} + \cdots + {{\mathit{\boldsymbol{d}}}_k}} \right) \cdot }\\ {\quad {{\left( {{{\mathit{\boldsymbol{d}}}_1} + {{\mathit{\boldsymbol{d}}}_2} + \cdots + {{\mathit{\boldsymbol{d}}}_f} + \cdots + {{\mathit{\boldsymbol{d}}}_k}} \right)}^{\rm{T}}}} \end{array}$ | (8) |
为了提高编码系数的判别性,文献[2]提出最小化编码系数的类内散度矩阵和类间散度矩阵的迹的差作为判别式约束项。为了增强原子的判别性能,使得不同类原子间的差异最大化和同类原子间的差异最小化,设计的原子Fisher判别准则如式(9)。
${\rm{min}}\left( {{\rm{Tr}}({{\mathit{\boldsymbol{S}}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right)) - {\rm{Tr}}({{\mathit{\boldsymbol{S}}}_{\rm{B}}}\left( {\mathit{\boldsymbol{D}}} \right))} \right)$ | (9) |
其中: Tr(·)表示矩阵的迹。式(9) 最小化同类原子类内散度矩阵和最大化不同类原子的类间散度矩阵。
根据式(6) 和式(8),式(9) 转换为式(10)。
$\begin{array}{*{20}{l}} {{\rm{min}}\left\{ {{\rm{Tr}}({{\mathit{\boldsymbol{S}}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right)) - {\rm{Tr}}({{\mathit{\boldsymbol{S}}}_B}\left( {\mathit{\boldsymbol{D}}} \right))} \right\} = }\\ {\quad {\rm{min}}\{ {\rm{Tr}}(\sum\limits_{i = 1}^k {{{\mathit{\boldsymbol{d}}}_i}{{\left( {{{\mathit{\boldsymbol{d}}}_i}} \right)}^{\rm{T}}}} - \frac{1}{f}}\\ \begin{array}{l} \quad \sum\limits_{i = 1}^c {} (\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right)\\ \quad {\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right)^{\rm{T}}})\} - \end{array}\\ {\quad {\rm{min}}\{ {\rm{Tr}}(\frac{1}{f}}\\ \begin{array}{l} \quad \sum\limits_{i = 1}^c {} (\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right) \cdot \\ \quad {\left( {{{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 1}} + {{\mathit{\boldsymbol{d}}}_{\left( {i - 1} \right)f + 2}} + \cdots + {{\mathit{\boldsymbol{d}}}_{if}}} \right)^{\rm{T}}})\} - \end{array}\\ \begin{array}{l} \quad {\rm{min}}\{ {\rm{Tr}}(\frac{1}{k}\left( {{{\mathit{\boldsymbol{d}}}_1} + {{\mathit{\boldsymbol{d}}}_2} + \cdots + {{\mathit{\boldsymbol{d}}}_f} + \cdots + {{\mathit{\boldsymbol{d}}}_k}} \right) \cdot \\ \quad {\left( {{{\mathit{\boldsymbol{d}}}_1} + {{\mathit{\boldsymbol{d}}}_2} \cdots + {{\mathit{\boldsymbol{d}}}_f} + \cdots + {{\mathit{\boldsymbol{d}}}_k}} \right)^{\rm{T}}}\} \end{array} \end{array}$ | (10) |
令A为元素均为1的k阶方阵,P也为k阶方阵,且矩阵P=VVT/f, V=H (HTH)-1/2,式(10) 可以转换为式(11) :
$\begin{array}{l} {\rm{min}}\left( {{\rm{Tr}}({{\mathit{\boldsymbol{S}}}_{\rm{W}}}\left( {\mathit{\boldsymbol{D}}} \right)) - {\rm{Tr}}({{\mathit{\boldsymbol{S}}}_B}\left( {\mathit{\boldsymbol{D}}} \right))} \right) = \\ \quad {\rm{min}}\left( {{\rm{Tr}}({\mathit{\boldsymbol{D}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}) + \frac{1}{k}{\rm{Tr}}({\mathit{\boldsymbol{DA}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}) - \frac{2}{f}{\rm{Tr}}\left( {{\mathit{\boldsymbol{DP}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}} \right)} \right) = \\ \quad {\rm{min}}\left( {{\rm{Tr}}({\mathit{\boldsymbol{DU}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}})} \right) \end{array}$ | (11) |
其中:U=I+A-2×P,I是单位矩阵。
2 AFDDL算法 2.1 AFDDL算法的目标函数根据文献[7],在判别字典学习算法中,对于不同类的训练样本,字典中的原子应该具有不同的重构性能,在理想情况下,一些原子应该只重构某一类样本。根据文献[4],利用特定类字典学习算法为每类训练样本学习一类原子,在字典学习中促使该类原子尽可能地重构该类样本。因此,基于原子的Fisher判别准则约束字典学习算法的目标函数如式(12)。
$\begin{array}{l} \quad \mathop {{\rm{min}}}\limits_{{\mathit{\boldsymbol{D}}}, {\mathit{\boldsymbol{Y}}}} \{ \left\| {{\mathit{\boldsymbol{X}}} - {\mathit{\boldsymbol{DY}}}} \right\|_2^2 + \alpha {\rm{Tr}}\left( {{\mathit{\boldsymbol{DU}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}} \right) + \beta {\left\| {\mathit{\boldsymbol{Y}}} \right\|_2} \}\\ {\rm{s}}{\rm{.t}}.\quad {\left\| {{{\mathit{\boldsymbol{d}}}_j}} \right\|^2} \le 1, j = 1, 2, \cdots , k \end{array}$ | (12) |
其中:‖X-DY‖22表示字典的重构性能;Tr(DUDT)表示原子的Fisher判别准则;‖Y‖2是编码系数的正则项;α和β是参数。U是反映原子的类内散度矩阵和类间散度矩阵关系的常量。由于U包含有原子的类标信息,在字典学习中min(Tr(DUDT))可以促使不同类原子间的差异最大化。另外,由于min(Tr(DUDT))=min(Tr(DTDU)),min(Tr(DUDT))在保持同类原子间的差异最小化的同时减少原子间的自相关性,能够增强字典的判别性能。此外,在目标函数中利用L2范数约束编码系数,使得式(12) 可以直接求导,降低算法的计算复杂度。
虽然AFDDL算法和LC-KSVD算法都是利用特定类字典学习算法为原子分配类标特征,并在此基础上设计判别式约束项。但是LC-KSVD算法主要是利用训练样本与原子类标的一致性构造一个对角的矩阵,在此基础上设计编码分类误差项,促使同类的训练样本对应的编码系数尽可能地相似,增强编码系数的判别性能,提高字典学习算法的分类性能。由于理想情况下,同类原子应该尽可能地重构某一类训练样本。而LC-KSVD算法没有考虑不同类原子间的差异,降低了字典的判别性。AFDDL算法通过构造原子的Fisher判别准则,促使不同类原子间的差异最大化以及同类原子差异最小化,并减少原子间的自相关性,增强字典的判别性能,提高字典学习算法的分类性能。虽然AFDDL算法和LCLE-DL算法都利用了原子的特性,AFDDL算法是在原子类标的基础上利用原子的相似性特征,而LC-KSVD算法仅仅利用原子的类标特征。因此,AFDDL算法能在一定程度上解决了LC-KSVD算法存在的问题。
此外,AFDDL算法和FDDL算法都利用了Fisher判别准则。FDDL算法主要是最小化同类训练样本对应编码系数的散度矩阵和最大化不同类训练样本对应编码系数的散度矩阵,增强编码系数矩阵的判别性能。虽然,FDDL算法还利用了同类原子的重构性能设计判别式约束想,由于其忽略了不同类原子间的差异,可能导致学习得到的字典具有一定的冗余性。而AFDDL算法通过利用原子的Fisher判别准则也能够在一定程度上解决了FDDL算法存在的问题。
2.2 AFDDL算法的求解由于AFDDL算法的目标函数可以采取交替约束直接求导的方法进行求解,利用K-SVD算法初始化字典D和编码系数矩阵Y,然后不断地更新目标函数直到算法收敛。
2.2.1 字典D的求解假设式(12) 中的编码系数矩阵Y是常量,AFDDL算法的目标函数可以转换为式(13):
$\begin{array}{l} \quad \mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{D}}} \{ \left\| {{\mathit{\boldsymbol{X}}} - {\mathit{\boldsymbol{DY}}}} \right\|_2^2 + \alpha {\rm{Tr}}\left( {{\mathit{\boldsymbol{DU}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}} \right) \}\\ {\rm{s}}{\rm{.t.}}\quad {\left\| {{{\mathit{\boldsymbol{d}}}_i}} \right\|^2} \le 1, i = 1, 2, \cdots , k \end{array}$ | (13) |
根据文献[8],利用拉格朗日函数对式(13) 进行求解可得到式(14):
$g\left( {\mathit{\boldsymbol{w}}} \right) = {\rm{inf}}\left( {\left\| {{\mathit{\boldsymbol{X}}} - {\mathit{\boldsymbol{DY}}}} \right\|_2^2 + \alpha {\rm{Tr}}\left( {{\mathit{\boldsymbol{DU}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}} \right) + \sum\limits_{i = 1}^k {{w_i}\left( {{{\left\| {{{\mathit{\boldsymbol{d}}}_i}} \right\|}^2} - 1} \right)} } \right)$ | (14) |
其中:w=[w1, w2, …, wi, …, wk](i∈[1, 2, …, k]),wi是第i个等式约束(‖di‖2≤1) 的拉格朗日乘子。假设k阶对角方阵为Λ∈Rk×k, 对角元素Λii=wi,式(14) 可以转换为式(15):
$\begin{array}{l} L\left( {{\mathit{\boldsymbol{D}}}, {\mathit{\boldsymbol{w}}}} \right) = \left\| {{\mathit{\boldsymbol{X}}} - {\mathit{\boldsymbol{DY}}}} \right\|_2^2 + \alpha {\rm{Tr}}\left( {{\mathit{\boldsymbol{DU}}}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}} \right) + \\ \quad \quad \quad \quad {\rm{Tr}}\left( {{{\mathit{\boldsymbol{D}}}^{\rm{T}}}{\mathit{\boldsymbol{D \boldsymbol{\varLambda} }}}} \right) - {\rm{Tr}}\left( {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}} \right) \end{array}$ | (15) |
为了获得最优字典D,对式(15) 求一阶导数并令其等于零可得式(16):
${{\mathit{\boldsymbol{D}}}^ * } = {\mathit{\boldsymbol{X}}}{{\mathit{\boldsymbol{Y}}}^{\rm{T}}}{\left( {{\mathit{\boldsymbol{Y}}}{{\mathit{\boldsymbol{Y}}}^{\rm{T}}} + \alpha {\mathit{\boldsymbol{U}}} + {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}} \right)^{ - 1}}{\rm{ }}$ | (16) |
为了减少计算复杂度,利用式(17) 获得最优字典D*:
${{\mathit{\boldsymbol{D}}}^ * } = {\mathit{\boldsymbol{X}}}{{\mathit{\boldsymbol{Y}}}^{\rm{T}}}{\left( {{\mathit{\boldsymbol{Y}}}{{\mathit{\boldsymbol{Y}}}^{\rm{T}}} + \alpha {\mathit{\boldsymbol{U}}} + \gamma {\mathit{\boldsymbol{I}}}} \right)^{ - 1}}{\rm{ }}$ | (17) |
其中:γ是参数,I是单位矩阵。利用式(17) 计算字典,可能对算法性能的稳定性产生一定的影响。因此,Λ的最优求解方法见文献[8]。
2.2.2 编码系数矩阵Y的求解假设AFDDL目标函数中字典D是常量,则式(12) 转换为:
$\mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{Y}}} \{ \left\| {{\mathit{\boldsymbol{X}}} - {\mathit{\boldsymbol{DY}}}} \right\|_2^2 + \beta \left\| {\mathit{\boldsymbol{Y}}} \right\|_2^2 \}$ | (18) |
式(18) 可以直接求导得到编码系数矩阵Y。因此,对式(18) 求导并令其为零,则可以得到:
$ - {{\mathit{\boldsymbol{D}}}^{\rm{T}}}{\mathit{\boldsymbol{X}}} + {{\mathit{\boldsymbol{D}}}^{\rm{T}}}{\mathit{\boldsymbol{DY}}} + \beta {\mathit{\boldsymbol{Y}}} = 0{\rm{ }}$ | (19) |
利用式(19) 获得最优的编码系数矩阵Y*:
${{\mathit{\boldsymbol{Y}}}^ * } = {\left( {{{\mathit{\boldsymbol{D}}}^{\rm{T}}}{\mathit{\boldsymbol{D}}} + \beta {\mathit{\boldsymbol{I}}}} \right)^{ - 1}}{\rm{ }}{{\mathit{\boldsymbol{D}}}^{\rm{T}}}{\mathit{\boldsymbol{X}}}$ | (20) |
由于AFDDL算法中原子具有类标信息,而且不同类原子具有较大的差异,拟采用FDDL算法中的全局分类方法为AFDDL算法的分类方法。
对于测试样本x和字典D,利用式(21) 获得测试样本x的最优表示系数
${\mathit{\boldsymbol{\hat a}}} = {\rm{arg}}\mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{a}}} \left\{ {\left\| {{\mathit{\boldsymbol{x}}} - {\mathit{\boldsymbol{Da}}}} \right\|_2^2 + \eta {{\left\| {\mathit{\boldsymbol{a}}} \right\|}_1}} \right\}$ | (21) |
其中:η是参数;‖·‖1是L1范数约束。
假设
${e_i} = \left\| {{\mathit{\boldsymbol{x}}} - {{\mathit{\boldsymbol{D}}}_i}{{\hat {\mathit{\boldsymbol{a}}}}_i}} \right\|_2^2 + \omega \left\| {\hat {\mathit{\boldsymbol{a}}} - {{\mathit{\boldsymbol{q}}}_i}} \right\|_2^2$ | (22) |
其中:ω是参数;qi是第i类训练样本对应编码系的均值矢量;ei是第i类字典对测试样本的重构误差,测试样本x的类标分配到获得最小误差ei对应的类。
AFDDL算法的分类过程如下:
1) 针对训练样本中的第i类样本,利用K-SVD算法初始化特定类字典Di和编码系数矩阵Yi。
2) 获得初始化字典D0=[D1, D2, …, Dc]和原子的类标矩阵H以及编码系数矩阵Y0=[Y1, Y2, …, Yc]。
3) 利用矩阵H计算矩阵P,并构造元素全为1的k阶矩阵P。
4) 利用矩阵A和矩阵P,根据公式U=I+A-2×P计算U。
5)
For i=1:t
利用式(17) 计算字典Di
利用式(20) 计算编码系数矩阵Yi
End
6) 获得最优的字典D=Dt和编码系数矩阵Y=Yt。
7) 针对测试样本x,利用式(21) 获得表示系数,并提取每类原子对应的表示系数。
8) 利用式(22) 计算重构误差,测试样本x的类标分配到最小误差对应的类。
3 实验结果与分析由于AFDDL算法是在原子类标的基础上构造的基于Fisher准则的判别约束项,而LC-KSVD、SVGDL和LCLE-DL算法都利用原子类标构造约束项,因此,把LC-KSVD、SVGDL和LCLE-DL算法作为对比算法。由于FDDL算法和AFDDL算法都利用了Fisher判别准则,不同之处在于FDDL算法利用的是编码系数的Fisher判别准则而AFDDL利用的是原子的Fisher判别准则。因此,把FDDL算法也作为AFDDL算法的对比算法。此外,在基于字典学习的模式分类中,通常也把以训练样本集合作为字典的稀疏表示分类(Sparse Representation based Classification, SRC) [9]和协同表示分类(Collaborative Representation based Classification, CRC)[10]算法作为对比算法。本章给出AFDDL算法和六个对比算法在AR[11]、LFW[12]和FERET[13]人脸数据库以及USPS[8]手写字体数据库中的实验结果。对于SRC算法,根据文献[9], 利用l1_ls方法获得测试样本的表示系数。由于LC-KSVD2比LC-KSVD1取得更好的分类性能,本文中的LC-KSVD算法的实验结果指的是LC-KSVD2算法。
在本文中所有实验中,AFDDL算法的参数为α=10-5、β=10-2和γ=10-2,最大迭代次数t=20。此外,参数ω和η与FDDL算法中的参数设置一样,即ω=0.5和η=0.005。
3.1 AR数据库中的实验结果AR数据库中共有126个人,超过4 000幅彩色人脸图像,这些图像采集于两个不同的阶段,每幅图像具有不同的表情、亮度和遮挡。根据文献[14],选择120个人作为子集合,图像被调整为40×50像素大小的灰度图像。在本文实验中,每类第一阶段的13幅图像作为训练样本,第二阶段的13幅图像作为测试样本。字典大小为1 560,实验结果如表 1所示。
从表 1中可以看出,AFDDL算法比6个对比算法均取得更高的识别率。此外,LCLE-DL等4个字典学习算法也都比CRC和SRC算法取得更高的识别率。
图 1显示AR数据库中的部分训练样本和被误分类的样本。从图 1中可以看出,被误分类的样本的表情和姿态与训练样本之间有较大的变化,表示利用原子的Fisher判别准则存在着不能有效地提取同类样本的某些特征,导致部分样本被误分类。
LFW数据库共计有1 680个人的13 000幅来自于互联网的人脸图像。根据文献[15],利用LFW数据的裁剪版本(LFW crop)为实验所用数据集合。LFW crop数据库中的人脸图像包括不对称、尺度变化和平面外旋转等真实情况。根据文献[16],从LFW crop数据库中选择每类图像个数为11~20的人脸图像作为数据集合,则共有86人的1 215幅图像,并把图像调整为32×32像素大小。
在本文实验中,每人随机选择5幅图像作为训练样本,剩下的作为测试样本。字典的大小为430。重复运行AFDDL算法和6个对比算法10次,实验结果如表 2所示。
从表 2中可以看出,AFDDL算法比6个对比算法均取得更高的识别率。但是,CRC算法比LC-KSVD,FDDL和SVGDL算法取得更高的识别率。而本文提出的AFDDL算法和LCLE-DL算法均比CRC取得更高的分类性能。上述实验结果表明利用原子间的特征能够有效地增强字典的判别性能。
图 2显示LFW数据库中的部分训练样本和被误分类的样本。从图 2中可以看出,被误分类的样本除了表情和姿态与训练样本之间有较大的变化,还有头发等因素导致提取的原子不能表示测试样本间的变化。
FERET数据库包含14 051幅多姿态和光照的人脸图像。根据文献[17],选择FERET数据库的一个子集合,包含200个人共计1 400幅图像作为本实验所用数据集合,图像的分辨率被调整为40×40像素大小。
在本文实验中,每类选择3幅人脸图像作为训练样本,剩余的作为测试样本。字典的大小为600。由于FERET数据库中每类人脸图像共有7幅图像,则一共有C73=35种组合。重复运行AFDDL算法和6个对比算法35次,实验结果如表 3所示。
从表 3中可以看出:AFDDL算法比6个对比算法均取得更高的识别率;另外,FDDL算法比LCLE-DL、LC-KSVD和SVGDL算法获得更高的识别率。上述结果表明利用原子或编码系数构造的Fisher判别准则,能够提高基于字典学习算法的分类性能。
图 3显示FERET数据库中的部分训练样本和被误分类的样本。从图 3中可以看出,表情和姿态仍然是影响算法的性能的重要因素。
根据文献[8],实验所用的USPS手写字体数据库共包括9 298个手写数字图像,每类图像数目从708~1 553不等,图像被调整为16×16像素大小。在本文实验中,从每类中固定选取前50个样本作为训练样本,剩余的作为测试样本,实验结果如表 4所示。
从表 4中可以看出:AFDDL算法比6个对比算法均取得更高的识别率;另外,SRC算法比LCLE-DL和SVGDL算法获得更高的识别率,与FDDL和LCLE-DL的识别率几乎相等。主要原因可能是USPS数据库中样本的背景简单和差异较小,直接利用原始样本的SRC算法也能够较好地表示测试样本。
图 4显示USPS数据库中的部分训练样本和被误分类的样本。从图 4中可以看出,字体形状的变化是影响算法的性能的重要因素。
1) 在四个数据库中,AFDDL算法的识别率比LC-KSVD提高了4.5、5.8、6.5和4.3个百分点,主要原因是LC-KSVD算法利用原子类标和编码系数构造编码分类误差项,促使同类的训练样本对应的编码系数尽可能地相似,增强编码系数的判别性能,但是其忽略了不同类原子间的差异。而AFDDL算法构造原子的Fisher判别约束项促使不同类原子间的差异最大化以及同类原子差异最小化,并减少原子间的自相关性,增强字典的判别性能,能够克服LC-KSVD算法存在的缺陷。
2) 表 1~4表明AFDDL算法的识别率分别比FDDL算法提高了2.9、3.9、1.1和2.5个百分点。FDDL算法利用编码系数的Fisher判别准则,促使同类训练样本对应的编码系数尽可能地相似,并结合原子的重构特征提高字典的判别性能,但是其忽略了原子间的自相关性特征及不同类原子间的差异。AFDDL算法利用原子的Fisher判别准则,不仅能够最大化不同类原子间的差异,而且能够在最小化同类原子间差异的同时最小化原子间的自相关性,促使同类的原子尽可能地重构同类训练样本,增强字典的判别性能。虽然,FDDL算法和AFDDL算法都利用了Fisher准则设计判别式约束项,但是AFDDL算法不仅具有FDDL算法的优点,还能够保持原子间的特征关系。因此,AFDDL算法比FDDL算法取得更好的分类性能。
3) 在四个数据库中,AFDDL算法比LCLE-DL和SVGDL算法均取得更高的识别率。主要原因是LCLE-DL算法仅考虑了同类原子间的特征,忽略了不同类原子间的差异。SVGDL算法利用训练样本的类标作为编码系数的权重,忽略了原子的特征。而AFDDL算法构造原子的Fisher判别约束项能够克服LCLE-DL和SVGDL算法存在的缺陷。
4) 当原子个数等于训练样本个数时,表 1~4表明AFDDL算法比CRC和SRC算法获得更高的识别率,主要原因是在通常情况下利用学习得到的字典比直接利用原始的训练样本具有更好的分类性能。
5) 在计算字典的训练时间时,AFDDL算法和对比算法的迭代次数均设定为20次。表 1~4表明,AFDDL算法的训练字典的时间比FDDL、SVGDL、LC-KSVD算法都小,与LCLE-DL算法几乎相等。主要原因是AFDDL和LCLE-DL算法都采用L2范数约束,目标函数可以直接求导,降低了算法的计算复杂度。由于使用相同的分类方法,AFDDL算法与FDDL算法的分类时间几乎相等,比LC-KSVD和LCLE-DL算法都高。由此可见,利用L2范数约束字典学习算法中的编码系数,不仅能够减少字典学习算法的训练时间,也能使得字典学习算法获得较好的分类性能。
4 结语为了提高基于字典学习算法的分类性能,本文提出一种新的判别式约束项模型。根据理想情况下,同类原子应该仅仅重构同一类样本,构造原子的Fisher判别准则。与目前字典学习算法不同的是,该判别式约束项不仅能够最大化不同类原子间的差异,而且能够在最小化同类原子间差异的同时减少原子间的自相关性,促使同类原子尽可能地重构某一类样本,增强字典的判别性能。实验结果表明AFDDL算法的识别率不仅比直接利用原始训练的SRC和CRC算法高,而且比FDDL、SVGDL和LCLE-DL等字典学习算法高。因此,字典学习中不同类原子间的差异对于增强字典的判别性能具有一定的促进作用。下一步的研究方向是如何把原子间的差异与编码系数间的差异统一到约束项中,增强字典学习算法的分类性能。
[1] | ZHANG Q, LI B X. Discriminative K-SVD for dictionary learning in face recognition[C]//CVPR 2010:Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ:IEEE, 2010:2691-2698. |
[2] | YANG M, ZHANG L, FENG X C, et al. Sparse representation based Fisher discrimination dictionary learning for image classification[J]. International Journal of Computer Vision, 2014, 109(3): 209-232. doi: 10.1007/s11263-014-0722-8 |
[3] | CAI S J, ZUO W M, ZHANG L, et al. Support vector guided dictionary learning[C]//ECCV 2014:Proceedings of the 13th European Conference on Computer Vision, LNCS 8692. Berlin:Springer, 2014:624-639. |
[4] | JIANG Z L, LIN Z, DAVIS L S. Label consistent K-SVD:learning a discriminative dictionary for recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2651-2664. doi: 10.1109/TPAMI.2013.88 |
[5] | LI Z M, LAI Z H, XU Y, et al. A locality-constrained and label embedding dictionary learning algorithm for image classification[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(2): 278-293. doi: 10.1109/TNNLS.2015.2508025 |
[6] | 甘岚, 张永焕. 基于字典学习的正则化鲁棒稀疏表示肿瘤细胞图像识别[J]. 计算机应用, 2016, 36(10): 2895-2899. ( GAN L, ZHANG Y H. Regularized robust coding for tumor cell image recognition based on dictionary learning[J]. Journal of Computer Applications, 2016, 36(10): 2895-2899. doi: 10.11772/j.issn.1001-9081.2016.10.2895 ) |
[7] | ZHANG Y, JIANG Z, DAVIS L S. Learning structured low-rank representations for image classification[C]//CVPR 2013:Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2013:676-683. |
[8] | ZHENG M, BU J, CHEN C, et al. Graph regularized sparse coding for image representation[J]. IEEE Transactions on Image Processing, 2011, 20(5): 1327-1336. doi: 10.1109/TIP.2010.2090535 |
[9] | WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227. doi: 10.1109/TPAMI.2008.79 |
[10] | ZHANG L, YANG M, FENG X C. Sparse representation or collaborative representation:which helps face recognition?[C]//ICCV 2011:Proceedings of the 2011 IEEE International Conference on Computer Vision. Washington, DC:IEEE Computer Society, 2011:471-478. |
[11] | MARTINEZA M, BENAVENTE R. The AR face database, TR #24[R]. Barcelona, Spain:Computer Vision Center, 1998. |
[12] | HUANG G B, RAMESH M, BERG T, et al. Labeled faces in the wild:a database for studying face recognition in unconstrained environments, TR 07-49[R]. Amherst, MA:University of Massachusetts Amherst, 2007. |
[13] | PHILLIPS P J, MOON H, RIZVI S A, et al. The FERET evaluation methodology for face recognition algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 22(10): 1090-1104. |
[14] | YANG J, ZHANG D, YANG J Y, et al. Globally maximizing, locally minimizing:unsupervised discriminant projection with applications to face and palm biometrics[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(4): 650-664. doi: 10.1109/TPAMI.2007.1008 |
[15] | SANDERSON C, LOVELL B C. Multi-region probabilistic histograms for robust and scalable identity inference[C]//ICB 2009:Proceedings of the Third Edition of the International Conference on Biometrics, LNCS 5558. Berlin:Springer, 2009:199-208. |
[16] | WANG S J, YANG J, SUN M F, et al. Sparse tensor discriminant color space for face verification[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(6): 876-888. doi: 10.1109/TNNLS.2012.2191620 |
[17] | XU Y, ZHU X J, LI Z M, et al. Using the original and symmetrical face training samples to perform representation based two-step face recognition[J]. Pattern Recognition, 2013, 46(4): 1151-1158. doi: 10.1016/j.patcog.2012.11.003 |