非负稀疏局部线性编码.pdf

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@ Journal of Software, 2011,22(Suppl.(2)):89−95 ©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563 非负稀疏局部线性编码 ∗庄连生 + , 高浩渊, 刘 超, 俞能海 (中国科学技术大学 信息科学技术学院,安徽 合肥 230027) Nonnegative Sparse Locally Linear Coding ZHUANG Lian-Sheng + , GAO Hao-Yuan, LIU Chao, YU Neng-Hai (School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China) + Corresponding author: E-mail: lszhuang@ Zhuang LS, Gao HY, Liu C, Yu NH. Nonnegative sparse locally linear coding. Journal of Software, 2011,22 (Suppl.(2)):89−95. Abstract: Feature quantization is an important component in Bag of word model. This paper proposes a novel method called nonnegative sparse locally linear coding (NSLLC) to improve the performance of locally linear coding. The core ides of NSLLC is to use nonnegative sparse representation to select the nearest neighbors in the same subspace and then encode the local feature with respect to the local coordinate consisting of these nearest neighbors. Experimental results have shown NSLLC has outperformed state-of-the-art local feature coding methods and is in favor of image classification problem. Key words: image classification; bag of word; nonnegative sparse representation; feature quantization 摘 要: 针对视觉词袋模型中的特征量化问题, 提出一种非负稀疏局部线性编码方法. 它能够有效地改善局部 特征编码性能, 提高图像非线性特征的区分能力. 其核心思想是, 利用非负稀疏表示技术选择与待编码局部特征 处于同一线性空间中的近邻点, 然后以这些近邻点作为局部坐标系对当前局部特征进行线性编码. 实验结果表 明, 该局部特征编码方法显著优于现有的特征编码方法, 有效地提高了图像非线性特征的区分能力, 更有利于图 像分类 任务. 关键词: 图像分类; 词袋模型; 非负稀疏表示; 特征量化 图像分类问题是计算机视觉和多媒体领域的一个基本问题,在图像检索、视频监控等领域中有着广泛应 用.图像分类问题的研究首先要解决图像表示问题.视觉词袋(bag of visual words)模型是目前使用最为广泛的 一个图像表示模型.它通过提取图像局部特征(如 SIFT 特征 [1] ),把局部特征量化为视觉词汇(visual words),最后 统计各视觉词汇出现的频率直方图来表示整张图像.由于对平移、旋转等几何变换较为鲁棒,视觉词袋模型在 场景分类 [2] 、物体识别 [3] 等具体图像分类任务中取得了巨大成功,受到学术界和工业界的广泛关注. 字典学习和特征量化是视觉词袋模型的两个关键步骤,直接决定了词袋模型的性能.字典学习的目标是寻 找新的具有较强表达能力的特征空间.特征量化的目标则是寻找一种局部特征编码方法,实现局部特征从原始∗ 基金项目: 国家自然科学基金(60933013, 61103134); 国家科技重大专项(2010ZX03004-003); 中央高校基本科研业务经费 (WK2100230002, WK2101020003) 收稿时间: 2011-07-20; 定稿时间: 2011-12-01 90 Journal of Software 软件学报 Vol.22, Supplement (2), December 2011 特征空间到新特征空间的映射.长期以来,研究人员主要集中于字典学习问题的研究,忽视了特征量化问题的重 要性,经常采用最简单的最近邻方法实现局部特征映射 [4] .但是,近期研究结果表明,当字典达到一定规模之后, 不同字典学习方法对最终分类结果的影响非常有限.在实际应用(如图像检索)中,字典规模一定都比较大,往往 在几十万、数百万数量级之上,此时使用简单的随机采样也可以得到一个分类性能令人满意的字典.相反,特征 量化方法则会对最终分类结果产生显著影响.因此,特征量化成为近年来一个新的研究热点 [4−9] .针对特征量化 问题,本文提出一种特征量化方法,用于改善局部特征编码性能,提高图像分类算法的分类性能. 特征量化也称为特征编码(feature encoding),主要研究如何把局部特征映射到由视觉词典所定义的特征空 间中.早期词袋模型主要采取硬关联策略(hard assignment),利用最近邻算法选择词典中与待编码局部特征距离 最近的视觉词汇来表示局部特征.在这种策略下,每个局部特征只能与 1 个视觉词汇相关联,造成信息损失,难以 处理处于不同词汇中间区域(类边缘地带)的局部特征 [5] .鉴于此,文献 [6] 提出一种软关联(soft assignment)的策 略,允许每个局部特征用多个视觉词汇来表示,有效降低了量化误差,提高了局部特征编码性能.但是,该方法对 关联词汇的个数非常敏感.同时,该方法对局部特征量化之后,直接统计图像的词汇直方图作为图像的线性特 征.该特征必须与非线性分类器相结合中才能取得较好的分类性能.但是,非线性分类器的计算复杂度一般比较 高,泛化能力也较差,难以推广到大规模的应用中. Ya n g等人 [7] 把稀疏编码(sparse coding,简称 SC)技术用于局部特征量化,结合非线性操作(max pooling)提取 图像的非线性特征,利用线性 SVM 作为分类器,取得了很好的分类性能.由于采用线性分类器,该方法分类速度 快,泛化能力也好,很适合大规模图像分类任务.通过对 SC 结果的研究 [9] ,Yu 等人认为局部性比稀疏性更本质. 局部非零一定导致整体稀疏,反之则不成立.基于该观点,他们提出一种局部约束线性编码方法(locality linear coding,简称 LLC),提高了特征编码性能 [8] .从本质上说,LLC编码方法只是局部线性嵌入(local linear embedding, 简称 LLE)算法 [10] 在特征量化中的应用:首先利用 k 近邻算法寻找词典中与待编码的局部特征最接近的 k 个视 觉词汇,然后利用这 k 个视觉词汇来重构当前局部特征,而重 构系数则作为最终编码结果的非零系数项(其他不相关视觉 词汇对应的系数为 0).该算法隐含了一个基本假设:所寻找到 的 k 个最近邻视觉词汇与当前局部特征位于同一个线性子空 间(或仿射子空间),否则编码结果没有意义.从信号表示角度 看,如果用不同子空间(类别)中的信号来重构当前信号,重构 系数已经丧失了其应有的物理含义.但是,k 近邻算法显然难 以保证所找到的 k 个视觉词汇处于同一子空间.如图 1 所示, 圆圈和十字叉分别代表了来自两个不同子空间的基向量,五 角星代表了当前待编码局部特征点(来自圆圈所在的子空间). 圆形区域则是利用 k 近邻算法找到的近邻点范围.显然,我们只希望在五角星所在的子空间寻找近邻点,但是 k 近邻算法会同时找到两个子空间中的点.这会导致 LLC方法的编码性能下降. 压缩感知理论研究表明 [11] ,稀疏表示的非零系数事实上揭示了信号所属的类别关系.受此结论启发,本文在 LLC方法基础上提出一种非负稀疏局部编码方法(nonnegative sparse locally linear coding,简称 NSLLC),以提高 局部特征编码性能.其核心思想是:计算局部特征相对于视觉词典的稀疏表示系数,根据非零系数值的大小来选 择近邻视觉词汇,然后利用近邻视觉词汇来重构局部特征点,重构系数作为编码结果的非零系数项.由于近邻样 本是从非零稀疏表示系数对应的视觉词汇中选择的,这就确保当前局部特征和所选择的近邻视觉词汇来自于 同一子空间(类别),保证随后的重构具有明确的物理含义.在标准稀疏编码技术中,稀疏表示系数可正、可负.这 也意味着,基向量之间可以通过相互“抵消”来重构信号.尽管从数学上负系数不难理解,但对于图像分类应用而 言,负系数却没有清晰、 合理的物理解释.因此,本文采用非负稀疏编码技术(nonnegative sparse coding,简称 NSC) 来选择近邻点.与稀疏编码技术相比,非负稀疏编码技术更加符合生物学模型 [12,13] ,可以更好地揭示信号类别关 系 [14] .从本质上看,NSLLC 方法是对 LLC 方法的改进.但与 LLC 方法相比,由于选择正确的近邻视觉词汇, Fig.1 Diagram of kNN searching results 图 1 k 近邻算法搜索结果示意图 (a) (b) 庄连生 等: 非负稀疏局部线性编码 91 NSLLC方法具有更好的编码性能,对噪声更加鲁棒,更有利于图像分类任务.实验结果也验证了我们的结论. 本文第 1 节首先回顾非负稀疏编码相关模型,给出基于增广拉格朗日乘子法的求解算法.第 2 节介绍非负 稀疏局部编码算法的实现框架.第 3 节是实验结果及分析.第 4 节是全文总结. 1 非负稀疏编码 1.1 非负稀疏表示模型 假设 12 [,, . . . ,] dN N R × =∈ Bbbb 是 d 维空间中的一组包含 N 个基向量的过完备基, 12 (,, . . . ,) Td d yy y R =∈ y 是 d 维空间中的向量.非负稀疏编码假设信号 y 可以用 B 中少数几个基向量的线性组合来表示,即 1 M ii i ys b = == ∑ Bs (1) 其中, 12 , ,..., M ss s =[] T s 是线性组合系数构成的向量,每个分量都大于 0.通常,我们称 s 为信号 y 的非负稀疏表示 (nonnegative sparse representation,简称 NSR).如果 s 中非零元素个数不多于 k 个(且 k 1 || ||sy B s s (3) 显然,式(3)是凸优化问题,可以有很多方法来求解 [17] . 一般而言,观测信号 y 通常伴有随机噪声 e,此时需要对模型进行修正.如果噪声 e 为高斯白噪声,则模型(3) 被通常修正为 1 min || || s。