特征空间中基于半遗传稀疏表示的图像识别

doi:10.11959/j.issn.2096-6652.202137

特征空间中基于半遗传稀疏表示的图像识别

石林瑞, 黄祎婧, 符进武, 郭心悦, 范自柱

华东交通大学理学院，江西南昌 330013

Sparse representation for image recognition based on semi-genetic algorithm in feature space

SHI Linrui, HUANG Yijing, FU Jinwu, GUO Xinyue, FAN Zizhu

School of Science, East China Jiaotong University, Nanchang 330013, China

通讯作者: 范自柱，zzfan3@163.com

修回日期: 2021-08-17 网络出版日期: 2021-09-15

基金资助:

国家自然科学基金资助项目. 61991401
江西省自然科学基金资助项目. 20192ACBL20010

Revised: 2021-08-17 Online: 2021-09-15

Fund supported:

The National Natural Science Foundation of China. 61991401
Jiangxi Provincial Natural Science Foundation. 20192ACBL20010

作者简介 About authors

石林瑞（1996−），女，华东交通大学理学院硕士生，主要研究方向为字典学习、迁移学习、图像处理和模式识别。

黄祎婧（1999−），女，华东交通大学理学院硕士生，主要研究方向为规则学习。

符进武（1998−），男，华东交通大学理学院硕士生，主要研究方向为行人重识别。

郭心悦（1999−），女，华东交通大学理学院硕士生，主要研究方向为目标跟踪。

范自柱（1975−），男，博士，华东交通大学理学院教授、博士生导师，江西省“井岗学者”特聘教授，江西省“百人远航工程”入选者，华东交通大学天佑人才计划第一层次（杰出人才）入选者，华东交通大学数学学科计算机应用技术方向带头人，主要研究方向为人工智能领域的模式识别与机器学习。

摘要

经典的稀疏表示分类（SRC）通常是基于求解L₁最小化问题的。SRC在原始输入空间中求解L₀范数最小化问题，无法很好地获取数据中的非线性信息。为了解决这一问题，应用非线性映射将原始输入数据映射到一个新的高维特征空间，并提出了一种新的基于L₀范数的表示方法。在所提方法中，表示测试样本的字典包含两个部分：第一部分固定在测试样本的近邻；第二部分的训练样本通过半遗传算法（SGA）来选择，利用表示误差确定第二部分的表示字典。在所提方法中，如果训练样本和已确定的测试样本的近邻产生最小表示误差，那么这些训练样本将被 SGA 确定为表示字典的第二部分。在一些常用的人脸数据集和一个手写体数据集上的实验表明，所提方法能够获得更好的分类性能。

关键词： 稀疏表示 ; 图像识别 ; 特征空间 ; L₀范数 ; 遗传算法

Abstract

The typical sparse representation for classification (SRC) is usually based on L₁minimization problem.Conceptually, SRC is essentially an L₀norm minimization problem solved in the original input space, which cannot capture well the nonlinear information within the data.In order to address this problem, a nonlinear mapping to map the original input data into a new high dimensional feature space was applied, and a new representation approach based on L₀norm was proposed.The representing dictionary used to represent the test sample contains two parts in the proposed approach.The first part is fixed to the neighbors of the test sample.The training samples of the second part is chosen by the variation of genetic algorithm (GA), i.e., the semi GA (SGA) algorithm, which exploits the representation error to determine the second part of the representing dictionary.In the approach, if the training samples combining the determined neighbors of the test sample yield the least representation error, these training samples are determined as the second part of the representing dictionary by SGA.Experiments on several popular face databases and one handwritten digit data set demonstrate that the proposed approach can achieve better classification performance.

Keywords： sparse representation ; image recognition ; feature space ; L₀ norm ; genetic algorithm

PDF (1098KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

石林瑞, 黄祎婧, 符进武, 郭心悦, 范自柱. 特征空间中基于半遗传稀疏表示的图像识别. 智能科学与技术学报[J], 2021, 3(3): 359-369 doi:10.11959/j.issn.2096-6652.202137

SHI Linrui. Sparse representation for image recognition based on semi-genetic algorithm in feature space. Chinese Journal of Intelligent Science and Technology[J], 2021, 3(3): 359-369 doi:10.11959/j.issn.2096-6652.202137

1 引言

基于 L₁ 范数及其变体^[1,2,3,4]的稀疏表示分类（sparse representation for classification，SRC）^[5,6,7,8]已被广泛应用于图像识别，如人脸识别^[9-10]、手写数字数据识别和其他应用^{[11,12,13,14]}。从本质上讲，SRC可以看作经典最近邻（nearest neighbor，NN）分类器的泛化。与使用一个子空间学习获得的特征提取器的经典NN分类器相比，如线性判别分析（linear discriminative analysis，LDA）^[15]，SRC 可以在分类精度方面获得更好的分类性能，特别是当它被应用于对有噪声或损坏的数据进行分类时。

SRC 算法的主要思想是对于每个测试样本或数据点，SRC 基于 L₁范数最小化问题的解，使用训练样本来表示测试样本，然后利用表示结果将测试样本分类到表示误差最小的类^[16]。需要注意的是，经典SRC算法的缺点之一是不能很好地应对训练样本数量相对较少的学习场景。基于L₁范数的经典 SRC 算法通常需要每类有足够的训练样本来表示测试样本^[17]。因此，L₁范数最小化问题可以足够稀疏，从而获得理想的分类性能^[18]。从本质上讲， SRC 算法是 L₀范数最小化问题，可以产生最稀疏的解，这可能会带来更好的分类性能^[5]。如果每一类的训练样本不足，基于L₁范数的经典SRC模型就不能保证获得稀疏解。因此，它可能无法达到理想的分类性能。在这种情况下，L₁范数最小化不再适用于求解SRC模型。如果采用L₀范数最小化来求解SRC模型，该模型仍然可以获得稀疏解，这在理论上比基于L₁范数的模型具有更好的分类性能。CF-SECL^[19]算法通过稀疏编码器将测试样本映射到其所属的子空间中，然后将分类器应用到稀疏编码中，通过计算预测出测试样本的标签；基于深度稀疏表示的多模态信号融合分类^[20]算法提出具有共享的全连接层的多模态编码器和解码器，对潜在空间特征进行训练，使其具有判别性，并适用于稀疏表示。基于核方法的稀疏表示解决了非线性分布问题，在图像分类任务中受到了广泛关注， K-LSDSR^[21]算法充分研究了图像数据间的局域性构造问题，可有效地捕获嵌入判别信息，提高了分类准确率。

本文利用 L₀范数最小化来建立一种新的 SRC模型，以克服经典 SRC 模型的不足。经典的 SRC模型可能存在另一个问题，即经典的SRC模型不能很好地处理不同类的样本分布在同一向量方向上的数据集^[22]，即不同类别相同方向（different class same direction，DCSD）。为了解决这个问题，Zhang L等人^[22]借用了基于核方法的思想，如支持向量机（support vector machine，SVM）^[23]。他们选择了一个合适的非线性映射，利用该映射将原始输入数据映射到一个高维数据空间，即特征空间，这个特征空间被称为再现核Hibert空间（reproducing kernel Hibert space，RKHS）^[24]，然后在该特征空间中执行 SRC。这种方法被称为基于核的稀疏表示分类（kernel based SRC，KSRC）^[24,25,26]，理论上可以避免上述DCSD问题。此外，它可以很好地获取数据集中的非线性信息，有助于对样本进行正确分类^[26]。基于核的稀疏表示方法可被应用在许多领域中。例如，Song B等人^[27]利用核稀疏表示对遥感图像进行一类分类。Zhou Y等人^[28]提出了一种基于核稀疏表示（kernel sparse representation，KSR）的手势识别算法，该算法对人类手势较大的变化具有鲁棒性。Huang K K 等人^[29]结合SRC和核判别分析（kernel discriminant analysis，KDA）算法开发了一种核扩展字典（kernel extended dictionary，KED）方法，该方法可以学习大量用于人脸识别的字典。Wang L等人^[30]采用核坐标下降法（kernel coordinate descent，KCD）求解KSR，该方法可用于视觉跟踪任务。受核方法思想^[31]的启发，本文提出的方法首先使用适当的非线性映射将原始输入数据转换到高维特征空间，然后利用L₀范数最小化实现SRC模型。因此，本文提出的方法可以有效地获取非线性信息，避免了之前工作^[32]在理论上无法有效解决的DCSD问题。

L₀范数最小化问题是NP难问题，没有直接的解析解。实际上，L₀范数最小化问题的解决方案是寻找最优训练样本，即表示字典^[33]，通过字典来表示测试样本。使用梯度下降法等解析优化方法很难确定表示测试样本的表示字典^[34]。原则上，通过一种随机优化方法可以有效地确定表示字典，即遗传算法（genetic algorithm，GA）。遗传算法是解决NP 难问题的一种常用方法，已广泛地应用于特征选择及其他应用^[35,36,37]。传统的遗传算法没有利用先验信息，即样本或数据点之间的距离或相似性。将这些信息加入遗传算法中，可以在一定程度上提高其有效性和效率。为此，本文提出的方法的表示字典^[38]分为两部分：第一部分使用先验信息（如距离信息）实现快速计算；第二部分是通过表征结果来确定的，借鉴了参考文献[39]的思想。

给定一个测试样本，它通常与其邻域共享相同的类标签，这些邻域在该测试样本的表示中起着关键作用。因此，它们自然构成了表示字典的第一部分^[40]。欧氏距离是一种常用的、简单的确定邻域的方法。本文应用欧氏距离来确定表示字典的第一部分。虽然欧氏距离可被简单度量，但不能保证使用这个距离就可以获得整个合适的表示字典。因此，需要在确定表示字典的第一部分后确定第二部分，故利用遗传算法选择一些不属于字典第一部分的训练样本。如果这些训练样本结合字典的第一部分表示在测试样本时产生最小的表示误差，则使用这些训练样本构建表示字典的第二部分。表示字典的一部分是固定的，另一部分是基于遗传算法确定的，因此将该方法中确定字典的过程称为半遗传算法（semi-genetic algorithm，SGA）。

综上，本文提出的方法包含以下步骤。第一步是指定一个非线性映射，将输入数据转换到高维特征空间；第二步是采用半遗传算法确定表示字典，然后用确定的字典来表示测试样本；最后，利用表示结果对测试样本进行分类。本文提出的方法被称为核遗传稀疏表示（kernel GA sparse representation， KGASR）算法，它有以下贡献。

首先，本文提出的方法是在特征空间中进行的，它可以有效地克服经典SRC方法不能很好地处理规模非常小的训练集，即训练样本数量非常少的问题。具体来说，KGASR算法可被应用于经典SRC模型无法获得充分稀疏解的学习场景。此外，该方法可以有效地避免DCSD问题，而经典的SRC方法不能很好地解决DCSD问题。

其次，KGASR 算法是一种被普遍认为可以获取数据中非线性信息的核方法。与经典的SRC方法相比，其工作是寻找一个更强大的工具来寻找类之间的非线性边界。特别是，本文提出的方法非常适合高维、小规模的数据集。主要原因是，在本文提出的方法中，非线性数据被映射到特征空间中，在这个空间中类之间的边界趋向于线性。显然，这种边界很容易找到。

最后，笔者使用半遗传算法来确定表示字典。SGA方案有两个优点，第一个优点是SGA使用欧氏距离来计算测试样本的邻域，该方案有效地利用了数据分布的先验信息来确定最适合表示测试样本的训练样本，进而有效地提高其表现性能；第二个优点是因为表示字典的第一部分是固定的，所以搜索空间显著缩小，从而提高了计算效率。

2 SRC概述

经典SRC的基本思想最初来自信号处理领域。2009年，J.Wright等人首次将SRC引入人脸识别领域，并引起了该领域的广泛关注^[1,41]。下面简单介绍SRC的基本原理。

假设有N个训练样本 $X = [x_{1}, x_{2}, \dots, x_{N}] \in R^{d \times N}$ 和一个测试样本y∈R^d。经典的SRC模型可解决以下优化问题^[1]。

{\hat{α}}_{1} = \arg \min {‖ α ‖}_{1}, subject to y = X α (1)

其中， $α = [α_{1}, α_{2}, \dots, α_{N}]^{⊤}$ ，α_i是第i个训练样本对应的表示系数， ${‖ α ‖}_{1} = \sum_{i = 1}^{N} | α_{i} |$ 。当处理数据中存在小密度噪声时，式（1）可以修改为：

{\hat{α}}_{1} = \arg \min {‖ α ‖}_{1}, subject to {‖ y - X α ‖}_{2}^{} \leq δ (2)

其中，δ是一个小的正数。显然，上面的SRC模型是基于L₁范数最小化的。最小化问题通常可转为下面的最小化问题：

{\hat{α}}_{1} = \arg \min_{α} ({‖ y - X α ‖}_{2}^{2} + λ {| α |}_{1}) (3)

其中，λ是平衡稀疏性和表示误差的正则化参数。当每类的训练样本足够多、解足够稀疏时，式（2）中的模型可以取得很好的学习效果。如果训练集规模较小，L₁范数最小化不能保证在此类数据集中表现良好。事实上，SRC的目标是为测试样本找到最稀疏的表示。它本质上是基于L₀范数最小化的，其计算式如下：

{\hat{α}}_{1} = \arg \min {‖ α ‖}_{0}, subject to {‖ y - X α ‖}_{2}^{} \leq δ (4)

其中， ${‖ α ‖}_{0}$ 为系数向量中非零项的数量，即 $α$ 的L₀范数。理论上，当训练集规模较小时，式（4）可以很好地为测试样本产生最稀疏的表示。本文提出的KGASR算法基于式（4）对小规模高维训练集进行分类。

3 核遗传稀疏表示

3.1 核稀疏表示

核稀疏表示可以被看作一种基于核的方法，它采用非线性映射将原始输入数据映射到高维特征空间，其中内积可以通过核函数计算^[42-43]。非线性映射是不需要明确表示的，在核方法中由特定核函数及其参数决定。核稀疏表示是在特征空间中进行的，本质上是在原始输入数据空间中实现的传统稀疏表示的基于核的非线性扩展。

首先采用非线性映射（φ:R^d →F，其中F是特征空间）将训练样本和测试样本映射到特征空间，这样在这个特征空间中就获得了训练集和测试样本；然后利用核函数计算样本向量 $ϕ (X) = [ϕ (x_{1}), ϕ (x_{2}), \dots, ϕ (x_{N})] \in R^{D \times N}$ 和测试样本φ(y)∈R^D之间的内积，这个方法被称为核技巧。核函数有3种基本类型：线性核函数、多项式核函数和高斯核函数。使用高斯核函数在理论上可以将原始输入数据映射到非常高甚至无限维的特征空间，并且其核参数易于调整，因此本文采用目前广泛使用的高斯核函数，其表达式如下：

k (x_{i}, x_{j}) = \exp \frac{- {‖ x_{i} - x_{j} ‖}^{2}}{2 σ^{2}} (5)

其中，σ是核函数的高斯核宽度参数。

理论上来说，特征空间中的测试样本可以由映射的训练样本稀疏表示。与输入空间中的经典SRC算法一样，特征空间中基于L₁范数的核稀疏表示模型定义为：

{\hat{β}}_{1} = \arg \min {‖ β ‖}_{1}, subject to {‖ ϕ (y) - ϕ (X) β ‖}_{2}^{} \leq ξ (6)

其中，ξ是一个小的正数。同样，当训练集规模较小且数据维数很高时，基于L₁范数的KSR无法保证获得足够稀疏的解。因此，可以利用L₀范数最小化来构建新的KSR模型，如下所示：

{\hat{β}}_{1} = \arg \min {‖ β ‖}_{0}, subject to {‖ ϕ (y) - ϕ (X) β ‖}_{2}^{} \leq ξ (7)

类似于在输入空间中基于 L₀范数的经典 SRC分类算法，在理论上可获得非常理想的分类性能，在特征空间中基于L₀范数的KSR算法也可以得到最稀疏解。需要注意的是，基于L₀范数的KSR模型也是一个NP难问题，可以采用一种改进的遗传算法来解决它。后文将详细描述这种改进的遗传算法，其被称为半遗传算法。图1给出了SRC方法与KSRC方法的基本原理。

3.2 本文提出的方法

3.2.1 确定表示字典

本文提出的 SGA 在特征空间中进行。给定一个测试样本φ(y)，在特征空间中计算它与其他样本φ(x)之间的欧氏距离，计算式如下：

ed = {‖ ϕ (y) - ϕ (x) ‖}_{2}^{2} = (ϕ (y) - ϕ (x))^{⊤} (ϕ (y) - ϕ (x)) =

ϕ^{⊤} (y) ϕ (y) - ϕ^{⊤} (y) ϕ (x) - ϕ^{⊤} (x) ϕ (y) + ϕ^{⊤} (x) ϕ (x) (8)

通过使用核技巧，有：

ed = k (y, y) - 2 k (x, y) + k (x, x) (9)

因此，使用欧氏距离来确定近邻的数量（如K个近邻），并将其作为表示字典的第一部分，表示为 $D_{1} = {ϕ ({x^{'}}_{1}), ϕ ({x^{'}}_{2}), \dots, ϕ ({x^{'}}_{K})}$ 。

在确定了测试样本的 K 个近邻后，需要使用SGA确定整个表示字典。在SGA中，表示字典的第一部分是固定的。SGA将表示误差最小的样本作为表示字典的第二部分。在描述 SGA 过程之前，先给出一些关于遗传算法的基本概念（详情请见参考文献[44]）。第一个概念是个体或状态，通常表示为0和1的串。个体的每个元素都与一个训练样本相关联。许多个体生成种群，这是遗传算法术语中的第二个基本概念。每个个体通常通过适应度函数进行评估。

在本文中，每个个体都被视为一个向量，其中每个元素都是0或1。向量的长度等于训练样本的数量。如果个体的元素为 1，则其对应的训练样本属于表示字典。首先，将与测试样本相关联的元素在个体中设置为1，并且它们在整个SGA过程中是固定的。这些元素产生了个体的第一部分。虽然有些训练样本没有被包含在表示字典的第一部分，但它们在表示测试样本方面可能起着非常重要的作用。因此，它们也应该被确定并放入表示字典中。换句话说，它们对应的元素在个体的第二部分是1。确定个体第二部分元素的第一步是将这些元素随机设置为0或1；第二步是根据适应度函数对个体的第二部分进行多代选择、交叉和变异操作。如果多个训练样本结合确定的近邻产生最小的表示误差，即最小的适应度，则它们的关联元素在个体的第二部分中为1。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 SRC方法与KSRC方法的基本原理

SGA 中的适应度函数被定义为使用个体对应的训练样本来表示测试样本产生的表示误差。假设个体中1的数量为M，有M个训练样本（包括测试样本的K个最近邻）与这些1相关联。个体的适应度计算如下：

f = {‖ ϕ (y) - \sum_{i = 1}^{M} β_{i} ϕ ({x^{'}}_{i}) ‖}_{2}^{2} (10)

通过使用核技巧，有：

f = k (y, y) - 2 \sum_{i = 1}^{M} β_{i} k ({x^{'}}_{i}, y) + \sum_{i = 1}^{M} \sum_{j = 1}^{M} β_{i} β_{j} k ({x^{'}}_{i}, {x^{'}}_{j}) (11)

其中， $β_{i} (i = 1, 2, \dots, M)$ 是使用训练样本 $I = [ϕ ({x^{'}}_{1}), ϕ ({x^{'}}_{2}), \dots, ϕ ({x^{'}}_{M})]$ 表示测试样本的系数。

3.2.2 表示和分类

确定测试样本φ(y)的表示字典后，使用该字典对φ(y)进行表示和分类。假设已确定的表示字典来自 t 个类，即 $C = {{c^{'}}_{1}, {c^{'}}_{2}, \dots, {c^{'}}_{t}}$ 。分别利用表示字典中属于每个类的样本来表示测试样本，并计算表示误差，其计算式如下：

r_{j} (ϕ (y)) = {‖ ϕ (y) - \sum_{i = 1}^{n_{j}} β_{{c^{'}}_{j}, i}^{*} ϕ (x_{{c^{'}}_{j}, i}^{*}) ‖}_{2}^{2} (12)

同样，使用核技巧，可得

r_{j} (ϕ (y)) = k (y, y) - 2 \sum_{i = 1}^{n_{j}} β_{{c^{'}}_{j}, i}^{*} k (x_{{c^{'}}_{j}, i}^{*}, y) +

\sum_{i = 1}^{n_{j}} \sum_{j = 1}^{n_{j}} β_{{c^{'}}_{j}, i}^{*} β_{{c^{'}}_{j}, j}^{*} k (x_{{c^{'}}_{j}, i}^{*}, x_{{c^{'}}_{j}, j}^{*}) (13)

其中，n_j是字典中属于类 ${c^{'}}_{j} (j = 1, 2, \dots, t)$ 的样本数， $ϕ (x_{{c^{'}}_{j}, i}^{*})$ 是特征空间中类 ${c^{'}}_{j}$ 的第i个训练样本， $β_{{c^{'}}_{j}, i}^{*}$ 是当应用表示字典表示测试样本φ(y)时，样本 $ϕ (x_{{c^{'}}_{j}, i}^{*})$ 的表示系数。本文使用了高斯核函数，因此式（13）中的 k(y,y)=1。最后，将测试样本分配到导致表示误差最小的类中：

id (y) = \arg \min_{j} r_{j} (ϕ (y)) (j = 1, 2, \dots, t) (14)

其中，id表示测试样本y的类别。

KGASR算法如下。

算法1 核遗传算法稀疏表示（KGASR）

输入训练样本 $X = [x_{1}, x_{2}, \dots, x_{N}] \in R^{m \times N}$ ，测试样本y∈R^m，进化代数P、个体数量Q。

步骤 1：利用特征空间中的欧氏距离确定测试样本的K个近邻。

步骤2：生成包含Q个个体的种群，其中与确定的近邻相关的元素为 1，其他元素随机设置为 1或0。

步骤3：For i= 1:Q

1）使用式（12）计算种群中每个个体的适应度。

2）与确定的近邻相关联的元素在每个个体中始终为1。对其他元素执行经典遗传算法的操作以产生新的种群。

3）如果当前代个体的最小适应度没有减少，则转到步骤5。

步骤4：确定导致最小适应度的表示字典。

步骤5：使用式（13）和式（14）对测试样本进行分类。

输出测试样本的标签。

3.3 KGASR算法分析

需要注意的是，如果使用传统的遗传算法来确定表示字典，其搜索空间规模为2^N，其中 N 是训练样本的总数。测试样本的K个确定的近邻对应的元素固定为 1，因此提出的算法的搜索空间规模为2^N-K，KGASR算法在理论上比传统的遗传算法更快。KGASR 算法的训练时间适中，测试时间快。在KGASR算法中，每次表示和分类一个测试样本。学习一个测试样本的过程与学习另一个测试样本的过程是独立的。也就是说，KGASR 算法的学习过程是并行的。如果利用并行程序来实现 KGASR算法，其计算效率将大大提高。

此外，KGASR 算法选择训练样本来生成具有非常强大的表示能力的表示字典来表示测试样本。所选的表示字典包含测试样本的近邻。因此，确定的字典可以获取测试样本的局部结构。众所周知，局部性通常会导致稀疏性，这个优点有助于KGASR算法产生绝对稀疏的解决方案。也就是说，在表示测试样本时，在表示系数向量中得到了多个零。因为除表示字典外的训练样本的系数都是零，所以该方案可以在很大程度上减少噪声或那些表示能力较差的训练样本的影响。这是KGASR算法能够达到良好分类性能的原因之一。

近年来，深度学习在机器学习领域引起了很高的关注。深度学习可以在训练集规模非常大的情况下取得很好的分类性能。然而，笔者的工作侧重于小规模的数据集，并且数据维度非常高。如果在笔者的工作中使用深度学习，可能无法获得很好的分类性能。

KGASR 算法与相关深度学习方法有学习特征并通过学习到的特征对测试样本进行稀疏表示的共性^[20]。深度学习方法可以在大规模的训练集下取得很好的分类性能，其将模型的上一层输出作为下一层的输入，实现了对输入数据信息的分级表达，最终达到特征学习的目的。KGASR 算法侧重于小规模且数据维度高的数据集，且应用非线性映射很好地捕捉了数据的非线性信息，有效地处理了不同类样本在同一向量方向上的数据分布问题。

4 实验

笔者在4个流行的数据集上进行了实验，以证明提出的方法可以在分类精度方面达到理想的性能。数据集包括CMU-PIE、EYB（Extended YaleB）、AR和MNIST数据集。前3个数据集是人脸图像数据集，第4个数据集是手写数字数据集。在本文的实验部分，笔者比较了一些经典的基于表示的分类方法，如协作表示分类（collaborative representation for classification，CRC）^[16]、SRC^[1]、KSRC^[22]、核坐标下降^[30]、扩展SRC（extended SRC，ESRC）^[17]、两阶段测试样本稀疏表示（two-phase test sample sparse representation，TPTSR）^[39]和通过结构和非凸约束的核群稀疏表示方法（KGSRSN）^[45]。本文提出的算法可被看作字典学习方法的一种。因此，将提出的方法与一些典型的字典学习方法进行了比较，它们分别是核扩展字典（KED）算法^[29]、局部约束和标签嵌入（locality-constrained and label embedding，LCLE）字典学习方法^[46]、K奇异值分解（K-singular value decomposition，KSVD）算法^[47]和鉴别Fisher嵌入字典学习算法（DFEDL）^[48]。

随机选择训练样本可以保证分类性能与训练集的任何特殊选择无关。与之前的许多工作相同，笔者随机选择了一部分样本进行训练，其余样本用于在每个数据集中进行测试。在本文实验中，KSRC算法利用了高斯核函数，其核函数参数σ（即高斯核宽度）设置为r× d_t，其中，d_t表示原始输入空间中训练样本的平均欧氏距离，即 $d_{t} = \frac{1}{N^{2}} \sum_{i, j}^{} (x_{i} - x_{j})^{2}$ ，N表示训练样本的数量。在所有实验中，KSRC中的参数r设置为0.001。在经典的SRC算法中，正则化参数设置为 0.01，在 ESRC 算法中也是如此。在KGASR 算法中，表示字典中的样本数与训练样本数之比设为0.1，进化代数P设为50，每个种群中的个体数Q设为20。

4.1 在CMU-PIE数据集上的实验

第一个实验是在包含 68 个人的图像的卡内基梅隆大学（CMU）-PIE人脸数据集上进行的。每个人都有在13种不同姿势和43种不同照明条件以及4种不同表情下获取的图像^[49]，图2为该数据集的一些示例。这个实验选取前 30 个人的图像，所有图像都被裁剪并调整为32×32像素的分辨率。对于每个人，随机选择 M（M=5、10 和 15）张图像进行训练，其余图像用于测试。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 CMU-PIE人脸数据集的一些图像样本

为了节省计算成本，在所有算法开始之前使用主成分分析（principal component analysis，PCA）法将人脸图像数据降维至 100 维。在 KGASR 和KCD算法中，从{0.1,0.2,…,1}和{1.1,1.2,…,10}两个集中选择高斯核宽度参数 r。如果这两组中的一个值导致最佳分类性能，则将r设置为该值。本文的其他实验使用相同的方案来选择 KGASR 和 KCD算法中的参数r。r在KGASR和KCD中设置为3。在TPTSR算法中，测试样本的邻居数设置为35，随机运行每个算法10次。

表1给出了分类结果，包括每种算法的平均分类准确率和标准偏差。其中，M表示每个人的人脸图像数量。从表1可以观察到，KGASR算法的分类精度明显优于其他所有比较算法。此外，当训练集规模较小时，KGASR 算法的分类性能有较大的提升。

表1 在CMU-PIE数据集上的分类精度

算法	M=5	M=10	M=15
CRC	62.09%±1.76	75.75%±1.71	82.65%±1.36
TPTSR	59.43%±2.02	75.05%±1.59	82.91%±0.81
SRC	61.78%±1.84	77.13%±1.77	84.84%±0.92
KSRC	66.63%±1.61	80.43%±1.47	86.33%±0.61
KCD	70.49%±1.98	82.54%±1.65	87.99%±1.04
KED	53.96%±1.94	63.95%±1.35	69.82%±1.50
KSVD	68.73%±1.95	78.67%±1.81	81.66%±1.34
LCLE	70.25%±1.93	81.26%±0.89	84.35%±1.07
ESRC	68.60%±2.08	82.45%±1.75	88.46%±0.93
KGSRSN	46.55%±0.54	66.06%±0.52	77.20%±0.35
DFEDL	62.85%±0.71	78.58%±0.68	86.35%±0.39
KGASR	71.55%±1.65	85.25%±0.99	91.05%±0.22

新窗口打开| 下载CSV

4.2 在EYB数据集上的实验

EYB数据集包含38个受试者的2 414张正面图像。所有图像均是在不同照明条件下拍摄的^[1]，图3为该数据集的一些示例。所有图像被裁剪并调整为40×35像素的分辨率。对于每个受试者，随机选择 M（M=4、5、6、7）张图像进行训练，其余图像用于测试。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 EYB数据集的一些图像样本

使用PCA将数据维数降至100维。KGASR算法的高斯核宽度设置为4× d_t，KCD算法中的参数r设置为1。在TPTSR算法中，测试样本的近邻数设置为50，从而使该算法的分类效果最好，随机运行每个算法10次。

表2给出了该数据集的分类结果，从表2可以看出，本文提出的算法性能优于其他所有比较算法。与SRC算法相比，KGASR算法再次证明了当训练集规模较小时，它可以实现更大的分类性能提升。当 M=4 时，KGASR 算法的分类准确率为66.25%，比 SRC 算法高 4.66%。而当 M=7 时， KGASR算法的分类准确率比SRC算法高1.27%。实验表明，本文提出的方法比SRC算法更适合处理小规模的训练集。

表2 在EYB数据集上的分类精度

算法	M=4	M=5	M=6	M=7
CRC	60.05%±1.22	64.48%±1.68	68.85%±1.3	71.59%±1.96
TPTSR	60.16%±1.18	65.22%±1.76	70.34%±1.49	74.47%±1.26
SRC	61.59%±1.64	67.01%±2.01	71.92%±1.56	75.59%±1.45
KSRC	62.25%±0.93	66.97%±1.8	70.81%±1.3	74.18%±1.37
KCD	63.16%±1.26	67.64%±1.95	72.09%±1.49	75.42%±1.18
KED	62.4%±3.4	67.35%±2.75	71.28%±2.41	74.9%±2.49
KSVD	63.3%±1.39	67.65%±1.87	69.05%±1.23	71.55%±1.56
LCLE	63.72%±1.17	67.41%±1.92	70.63%±0.98	73.21%±1.14
ESRC	62.84%±1.47	67.50%±1.91	72.72%±1.24	76%±1.3
KGSRSN	43.8%±0.35	49.96%±0.47	54.77%±0.57	60.51%±0.46
DFEDL	31.52%±0.31	61.59%±0.54	66.29%±0.46	70.34%±0.47
KGASR	66.25%±1.44	71.31%±1.69	75.7%±1.14	76.86%±1.03

新窗口打开| 下载CSV

4.3 在AR数据集上的实验

AR人脸数据集包含126个人（126个类别）的图像，每个人包含不同面部表情、光照条件和遮挡的人脸正面视图^[50-51]，图4为该数据集的一些示例。本文使用了 120 个人的人脸图像，每个人有 26 张图像。所有图像首先被更改为灰色图像，然后被裁剪并调整大小为50×40像素。对每个人选择的训练图像数量为3和4，它们构成了训练数据的两个子集。

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 AR数据集的一些图像样本

与前两个实验相同，在所有方法实现之前，使用PCA将人脸图像数据维数降至120维。在KGASR算法中，高斯核宽度设置为5×d_t，KCD算法中的参数r设置为1.5。对于TPTSR算法，测试样本的近邻数设置为30，随机运行每个算法10次。

表3给出了该数据集的分类结果。从表3可以看出，KGASR算法优于其他比较先进的分类算法。KGASR 算法在本实验中的分类性能与前两次实验一致。也就是说，本文提出的方法在分类准确率方面达到了稳定且理想的分类性能。

4.4 在MNIST数据集上的实验

第4个实验是在MNIST数据集上进行的，该数据集是一个手写数字数据集，共有10个类，即0、1、2、…、9每个数字产生一个类^[52]。在每个类中，训练集包含6 000个图像样本，测试集包含1 000个图像样本。每张图片的像素大小为28×28。图5为该数据集的一些示例。在这个实验中，从每个类的训练集中随机选择样本，这些样本被用作训练样本。每个类别选择的训练样本数分别为5、10和15。因此，获得了训练数据的3个子集。对于每个子集，从每个类的测试集中随机选择样本作为测试样本，为每个类别选择的测试样本数为 300。因此，生成了3个测试子集，分别与3个训练数据子集相关联。每个测试子集包含3 000个测试样本。

表3 在AR数据集上的分类精度

算法	M=3	M=4
CRC	78.86%±1.74	84.07%±0.97
TPTSR	78.75%±1.38	84.06%±0.88
SRC	78.39%±1.31	84.19%±0.7
KSRC	79.4%±1.33	84.69%±0.83
KCD	80.97%±1.52	86.14%±0.75
KED	82.54%±1.19	87.31%±0.91
KSVD	75.24%±1.77	81.94%±0.91
LCLE	78.9%±1.54	82.86%±0.96
ESRC	81.25%±1.22	86.46%±1.23
KGSRSN	64.5%±0.47	72.49%±0.35
DFEDL	78.59%±0.59	84.37%±0.27
KGASR	82.99%±1.45	87.47%±0.82

新窗口打开| 下载CSV

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 MNIST数据集的一些图像样本

类似地，使用 PCA 将人脸图像数据维数减少到40维。KGASR算法中的高斯核宽度设置为d_t。在TPTSR算法中，测试样本的近邻数设置为15。此外，随机运行每个算法10次。

图6给出了该数据集的分类结果。从图6可以看出，与SRC、KSRC和ESRC算法相比，KGASR算法的分类精度高了近 10%。在该数据集中， KGSRSN算法的分类效果稍高于KGASR算法，但综合比较4个数据集的分类性能，KGASR的分类性能更稳定、更鲁棒。

通过以上实验可知，本文提出的算法达到了理想的分类性能。其性能较好的主要原因是可以有效地克服经典SRC和KSRC算法的缺点。具体来说， KGASR算法可以有效地避免DCSD问题。此外，它使用半遗传算法确定合适的表示字典，从而很好地处理小规模和高维数据集，即欠采样数据集^[17]，因此，在处理欠采样数据集时，ESRC 算法可能会被KGASR算法取代。

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 在MNIST数据集上的分类精度

4.5 收敛性分析

KGASR 算法中表示字典的确定主要基于全局优化能力强的遗传算法。特征空间中的 SGA 是KGASR算法中的关键过程。实际上，SGA是一种具有良好的收敛性的遗传算法，通常用于解决全局优化问题。接下来通过实验证明 SGA 在 4 个数据集上的收敛性。

在每个数据集中，随机选择一个测试样本，并根据式（12）中定义的适应度函数，使用 SGA 来确定表示字典。在 CMU-PIE、EYB 和 AR 数据集中，进化代数P设置为5 000，个体数量Q设置为 5 000。在 MNIST 数据集中，P 设为 500，Q设为5 000。SGA中的其他参数与前4次实验相同。图7显示了不同代在4个数据集上的适应度值。从图7可以看出，KGASR算法实现了适应度函数的全局最小化。对于CMU-PIE数据集，在1 200代左右时适应度值下降到最小；对于EYB数据集，在2 200代左右时适应度值下降到最小；对于AR数据集，代数为5 000左右时降到最低；对于MNIST数据集，代数为1 500左右（MNIST数据集中个体数Q为500）时适应度值下降到最小。KGASR算法在4个数据集上都是收敛的。因此，可以得出结论：KGASR算法具有良好的收敛性。此外，该实验表明，如果设置更大的P和Q，KGASR算法可以获得更好的分类性能。

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 不同代在CMU-PIE、EYB、AR和MNIST数据集上的适应度值

5 结束语

本文从一个新的角度研究了经典SRC算法。也就是说，经典SRC算法可以通过最小化特征空间中的L₀范数来改进。为了有效地解决L₀范数最小化问题，引入一种半遗传算法来确定一个具有强大表示和分类测试样本能力的表示字典。本文提出的KGASR 算法在理论上克服了现有的基于表示分类的算法的不足，特别是基于L₁范数的表示方法，如经典SRC、KSRC和ESRC算法。KGASR算法适用于处理小规模和高维数据集，还可以有效地避免DCSD 问题。KGASR 算法适用于许多应用，如图像分类和特征选择。实验证明，与比较算法相比， KGASR算法的分类精度最好。

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

SHEKHAR

, PATEL

V M

, NASRABADI

N M

,et al.

Joint sparse representation for robust multimodal biometrics recognition

[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013,36(1): 113-126.

[本文引用: 5]

[2]

YANG

, ZHANG

, FENG

,et al.

Sparse representation based fisher discrimination dictionary learning for image classification

[J]. International Journal of Computer Vision, 2014,109(3): 209-232.