Print

发布时间: 2018-05-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.170461
2018 | Volume 23 | Number 5




    图像理解和计算机视觉    




  <<上一篇 




  下一篇>> 





字典重建和空间分布关系约束下的特征选择与图像拼接
expand article info 于邓1, 刘玉杰1, 隋国华2, 陈晓明1, 李宗民1, 范建平3
1. 中国石油大学(华东)计算机与通信工程学院, 青岛 266580;
2. 中国石油化工股份有限公司 胜利油田分公司物探研究院, 东营 257022;
3. 北卡罗来纳大学夏洛特分校计算机科学学院, 美国夏洛特 28223

摘要

目的 针对大型图像检索领域中,复杂图像中SIFT特征描述子的冗余和高维问题,提出了一种基于字典重建和空间分布关系约束的特征选择的方法,来消除冗余特征并保留最具表现力的、保留原始空间结构性的SIFT特征描述子。方法 首先,实验发现了特征选择和字典学习方法在稀疏表示方面的内在联系,将特征选择问题转化为字典重构任务;其次,在SIFT特征选择问题中,为了保证特征空间中特征的鲁棒性,设计了新型的字典学习模型,并采用模拟退火算法进行迭代求解;最后,在字典学习的过程中,加入熵理论来约束特征的空间分布,使学习到的特征描述子能最大限度保持原始SIFT特征空间的空间拓扑关系。结果 在公开数据集Holiday大型场景图片检索数据库上,通过与国际公认的特征选择方法进行实验对比,本文提出的特征选择方法在节省内存空间和提高时间效率(30%~50%)的同时,还能保证所筛选的特征描述子的检索准确率比同类特征提高8%~14.1%;在国际通用的大型场景图片拼接数据库IPM上,验证本文方法在图像拼接应用中特征提取和特征匹配上的有效性,实验表明本文方法能节省(50%~70%)图像拼接时间。结论 与已有的方法比较,本文的特征选择方法既不依赖训练数据集,也不丢失重要的空间结构和纹理信息,在大型图像检索、图像拼接领域和3D检索领域中,能够精简特征,提高特征匹配效率和准确率。

关键词

特征选择; 字典重建; 熵空间分布约束; 大规模图像检索; 图像拼接

Feature selection and image stitching based on dictionary reconstruction and spatial distribution
expand article info Yu Deng1, Liu Yujie1, Sui Guohua2, Chen Xiaoming1, Li Zongmin1, Fan Jianping3
1. College of Computer & Communication Engineering, China University of Petroleum, Qingdao 266580, China;
2. Geophysical Research Institute of Shengli Oilfield Branch Co., Dongying 257022, China;
3. Department of Computer Science, University of North Carolina at Charlotte, Charlotte 28223, America
Supported by: National Natural Science Foundation of China (61379106, 61379082, 61227802); Natural Science Foundation of Shandong Province (ZR2013FM036, ZR2015FM011); Open Project Program of the State Key Lab of CAD & CG (A1315)

Abstract

Objective In the research field of feature extraction and feature matching in large-scale 2D image retrieval, 3D model retrieval, and image stitching, we determined that the large number of redundant feature descriptors in an image and the high dimensionality of these feature descriptors have caused an intractable problem for large-scale image databases in terms of feature matching speed and retrieval efficiency and have resulted in the poor performance scalability of these feature descriptors. In this study, for the previously mentioned problems, we present a feature descriptor selection algorithm based on dictionary learning and entropy spatial constraints to reduce and even remove the redundant feature descriptors to the maximum extent. That is, in our algorithm, we aim to preserve only the most representative subset of feature descriptors and to ensure that the selected feature descriptors in our algorithm can have a consistent spatial distribution with the original feature descriptors set. Method First, during our experiments, we observed the inner relativity between feature descriptor selection and dictionary learning problems in terms of the feature descriptor sparse representations. That is, based on the conception of sparse coding in dictionary learning, we determined that feature descriptor selection and dictionary learning are transferable between each other. Thus, we turn our feature descriptor selection problem into the research field of dictionary reconstruction. In the field of feature descriptor selection, we need to reduce the repeated feature descriptor points and save a small set of the most representative feature descriptors. After the transformation of the feature descriptor selection problems into dictionary learning tasks, we only need to identify the best key feature descriptors to reconstruct the original feature descriptor set under some conditions, such as the sparse and representative conditions, which we called dictionary reconstruction. After the transformation of the feature selection problem into the dictionary reconstruction task, we turn the feature descriptor selection problem into the research field of dictionary optimization. Second, after the transformation of our feature descriptor selection problem into a dictionary learning task, for the new dictionary of the original feature set, we design a new dictionary learning model to keep the robustness of our selected feature descriptors. In the field of dictionary learning, we take the entire original feature descriptor set as a dictionary and take the best representative feature descriptors as the keywords in our dictionary learning model. We derive the object functions of our dictionary reconstruction model, but our dictionary learning model is different from that of other situations because, in our dictionary learning model, we must ensure that the bases of our dictionary are unchangeable and the coefficients of the corresponding base are non-negative. On the basis of these limitations, we employ the simulated annealing algorithm to solve our object function and obtain the optimal solutions, which we finally take as the selected feature descriptors. Finally, during the process of dictionary learning, we add the entropy sparse constraint to save the spatial distribution characteristic of the original feature descriptor points to the largest extent, that is, we use entropy theory to limit dictionary learning. If the distribution of our final selected feature descriptor points is consistent with the original feature descriptor points, then the entropy value is low; otherwise, the entropy value is high. Thus, in this manner, we force our dictionary learning model to select the representative feature descriptor points with low value during the learning process, that is, our dictionary learning model tends to preserve the representative feature descriptor points whose spatial distribution is in accordance with the original feature descriptor points. Thus, we can finally obtain a small set of representative feature descriptors with good spatial distribution. Result We test our selected feature descriptors on two research fields to verify our feature descriptor selection algorithm. On the one hand, we implement our experiments on a large-scale image retrieval dataset, i.e., holiday image retrieval dataset, by comparing our algorithm with the existing feature descriptor selection methods. The experiments showed that our algorithm can considerably save memory space, increase the time efficiency of feature matching and image retrieval (30% to 50%), and improve the retrieval accuracy by approximately 8% to 14.1%. On the other hand, we test our feature descriptor selection algorithm on the standard image stitching dataset, i.e., IPM image stitching dataset. We verified our feature descriptor selection method on the aspects of feature extraction and feature matching in the research field of image stitching. The experiments on the IPM image stitching dataset proved that our feature descriptor selection algorithm achieved the best time saving (50% to 70%) with a low range of accuracy degradation. Conclusion Compared with the existing methods, our feature descriptor selection algorithm neither relies on the database nor loses important spatial structure and texture information, that is, our feature descriptor selection algorithm has a stable performance and strong scalability in different situations, many datasets, and various tasks, such as video retrieval, image search, picture retrieval, and image matching, which require feature extraction, feature selection, and feature matching operations. The experimental results indicated that our model has a stable adaptive performance to different datasets and various scenes. The image retrieval and image stitching experiments illustrated that our feature descriptor selection algorithm can be adapted to different situations and achieve a good performance, which surpasses that of other feature selection approaches. By contrast, with the advent of Big Data, the demand for the most valuable feature descriptors in our large number of image datasets is urgent, and our feature selection approach can be further adopted to reduce the redundant descriptors. According to our feature descriptor selection algorithm, we can achieve 50% to 70% reduction of noise feature descriptors and the main advantage of our approach in improving the efficiency and accuracy of feature matching in many mainstream tasks, such as the research fields of large-scale image retrieval, image stitching, and 3D model retrieval.

Key words

feature selection; dictionary reconstruction; entropy spatial constrains; large-scale image retrieval; image stitching

0 引言

特征表示是计算机视觉中至关重要的研究领域,并在其他的研究领域起到基石性的作用,比如目标识别、目标检测、图像检索和分类等领域。其中,最经典的、最广为大家使用的是在1999年Lowe首次提出的SIFT[1](scale invariant feature transform)特征。在2004年由Lowe [2]组织并深度开发的SIFT特征,在稳定性和特征不变性又得到了极大的提升。标准的SIFT特征描述子是由图像上兴趣点局部边缘的梯度所提取的方向和量级构成的,同时被标准量化到一个128维的统一长度的向量。SIFT特征描述子是用来描述数字图片内容的显著性的不变特征, 在尺度鲁棒和旋转不变性上远超其他特征,被认为是最重要的图像局部特征[3],广泛应用于真实世界的图像应用,比如:图像检索、图像拼接、视频分析和3维重建等领域。随着大数据媒体的到来,伴随着应用场景的复杂化,传统的SIFT特征面临着巨大的挑战:通常一张背景复杂的自然图片会提取出大量的高维的兴趣点,为大规模图像数据集的速度和扩展性方面带来的困难。例如,大规模目标识别任务可能包含数百万计的高维SIFT描述子,在距离度量上花费大量时间并占用大量内存空间。

目前,解决上述特征冗余问题的方法可以分为3类。

第1类方法是对于128维的SIFT特征向量本身进行删减降维,经典的工作是PCA_SIFT[4]和SURF[5](speeded up robust features)。以上方法在降低原始SIFT维度的同时,可能会丢失细节纹理和空间结构信息。第2类方法是基于相似性度量方面的解决方法来加快特征的配准,比如:局部敏感哈希LSH[6-7](local sensitive Hash)和层次结构匹配[8]等方法。尽管这类方法极大地减少了特征之间距离计算的时间,但对于减少特征的所占的存储空间方面却并不起作用。第3类方法主要目标是减少特征描述子的数量,这类方法对于减少计算消耗和存储空间的降低具有显著效果,比如:近几年提出的方法[9-10]。但是这些方法在于特征的可拓展性和普适性方面仍有不可克服的缺陷,即严重依赖所训练的数据集。本文方法属于第3类方法,但以崭新的角度和思路来解决特征选择和匹配问题。

通过对于现有方法的优缺点的分析和比较,提出一种更具普适性和系统性的SIFT特征选择方法。在实验中,发现由Lowe提出的特征检测方法检测出来的原始SIFT特征描述子的数量十分巨大,但提取出来的、数量繁多的特征描述子在扮演着不同的角色。比如在SIFT特征点匹配中,能够精确匹配的特征点对是有限的,但却需要计算的所有可能的SIFT特征点对来寻找这些匹配的特征点对,算法的时间代价方面为$ {\rm O}(N^2)$,并在某种程度伴有降低匹配准确性的可能,即当正常特征与噪音特征匹配时。同时,实验中发现:一幅图片中具有较多的相似和重复的SIFT特征点,特别是在具有复杂的背景的自然图片中,这种情况尤为严重,称之为SIFT特征的冗余特质。本文的目标是去除SIFT特征点的冗余性,选取最有表现力的特征描述子,称之为top-SIFT,如图 1所示。本文通过在图像检索和图像拼接领域的相关实验,来验证本文提出的特征选择方法的有效性。

图 1 SIFT特征点冗杂现象
Fig. 1 The redundancy of SIFT points
((a) original SIFT features; (b) top 20% SIFT features selected from the original feature set)

本文采用字典学习来进行稀疏特征学习,并分析了SIFT特征点的空间分布特性,加入熵空间约束来去除冗余特征点,选择最具描述力的特征描述子。设想top-SIFT应该具有重建、表示其他冗余特征的能力,所以将特征选择任务转化为字典学习中的重建优化问题:top-SIFTs可以最大程度地重构原始的SIFT特征点,如图 2所示。

图 2 本文的特征选择原理图
Fig. 2 The schematic diagram of feature selection

图 2中,$ \mathit{\boldsymbol{X}}$代表原始特征点集,$ \mathit{\boldsymbol{D}}$代表的是选择的特征点集。$ \mathit{\boldsymbol{D}}$$ \mathit{\boldsymbol{X}}$中提取,并且可以用最小的误差来重构$ \mathit{\boldsymbol{X}}$。最终,把特征选择问题转化成稀疏表示的字典重建问题。同时,本文方法与一般字典学习方法的显著区别在于:

1) 在字典学习的过程中,选择固定长度的基作为关键词,也就是说,本文的字典是由真实的样本组成,进一步阐述,即字典中的每一个列向量都是一个128维的SIFT描述子。

2) 本文方法学习字典中基的系数是非负的,因为对于系数来说,负值无法重建原始的SIFT特征点。

3) 在字典学习的过程中加入了SIFT特征点的空间分布信息。

1 相关工作

现有的特征选择方法可以归类为:1)仅保留目标的附近的特征描述子;2)通过某些度量保留最好的$ N$个特征描述子;3)在图像上稀疏采样来减少特征数量。

第1类方法的通用策略:通过研究一组图像的相似内容,然后只在所有图像的共有区域范围内选取特征点。这类方法看似提高了特征点的匹配的准确性,但仅仅是对于单一数据集的有监督训练,通常非常严重地依赖于训练数据集。Knopp等人[11]在场景识别领域中提出了一种丢弃混淆特征点的方法:首先假设待检索图像中匹配的SIFT特征点应该存在于与检索图像中目标所处的、相似的空间区域内;然后,对待检索图像使用滑窗,在滑窗区域内进行混淆程度计算并打分,将滑框所滑过的图像区域块分类:分为目标区域和混淆区域。该方法有效地减少了混淆特征和提高了场景识别的精确度,但是严重依赖数据库,扩展性和迁移性较差。Turcot等人[9]提出有用的特征是重复出现在多张图片中或者相同目标附近的特征点:该方法将词包模型(bag-of-words)应用到图像检索领域,并在最初的检索结果中选择top $ M$张图片作为几何验证,即只有几何一致的特征描述子才会保留.该方法尽管可以保留的原始特征点集中4%的特征点,并保证准确率不降低,但也十分依赖训练数据集。不适合含非关联图片的数据集的检索。Lee等人[12]提出有效的特征多数是从图像的前景中提取出的,并对这些图像进行聚类。该方法假设:如果提取出来的特征点多分布于图像的前景,那么使用从前景区域提取出的特征来进行图像聚类,所获的聚类效果就会更好;另一方面,图像聚类的结果也反过来指导哪些特征被认为是好的特征。所以该方法中特征提取与数据聚类是同时进行的,在性能上极大地超越了其他的方法,但是提取出的特征点与图像聚类之间的紧密联系导致该方法不适用单张图像。

第2类方法的通用策略:基于某种规则对特征点进行排序,然后保留前$ N$个特征。Foo等人[10]提出一种基于由对比度排序的方法,选择最好的$ N$个特征,对比度由高斯差分金字塔(DoG)计算得出。Johnson[13]提出一种基于稳定匹配的特征选择方法,该方法为每一个特征点计算一个匹配可能性的评分,基于匹配评分来选取特征点。Brown等人[14]引入一种自适应的非极大值抑制方法(non-maxima suppression)挑选固定数量具有良好空间分布性质的特征点。这类方法的准确率略低于或者与原始特征的准确率相仿,方法的效率可以大幅提升。但是容易丢失重要的纹理结构和空间信息,仅适用于简单、小型的数据集或者应用。

第3类方法多数采用稀疏采样图片的方法来直接减少描述子,该类方法主要应用于3D重建中,然而文献[15-16]中已经证明:通过对图片稠密取样会产生更好的3D重建效果。

在文献[17]中已经提出top-Sift的概念来挑选最具重建能力的特征描述子。本文更加注重SIFT特征的空间分布特性,引入熵空间约束来约束字典学习,并给出特征点空间位置分布的约束。

2 本文方法

本节给出SIFT特征的评价标准,并基于稀疏和空间约束下的字典学习方法对特征选择问题进行公式化表达并求解,因此,特征选择问题就转换成稀疏表示的字典学习问题。首先,解释问题转化的主要思路;其次,讨论SIFT特征点的空间分布特性;最后,给出字典学习问题的求解算法。

2.1 特征选择问题的公式化表达

传统的SIFT特征检测算法中,通常会检测出大量的特征点,尤其是拥有复杂和斑驳背景的图片背景,比如树木、草地和建筑背景等,如图 3所示。

图 3 背景复杂的图像中的特征冗余问题
Fig. 3 The problem of feature redundancy
((a) original feature set; (b) selected feature set)

图 3中,实际的SIFT特征检测中含有大量的冗余特征点,所以,本文旨在去除冗余特征并保留最具表现力的描述子;同时保证选择的特征点应该具有表示其他特征点的能力。因此问题就可以转化为重建问题,原始的SIFT特征集合可以被挑选出的top-SIFTs重建出来。为了获取描述力最强的特征,最小化全局的字典重构误差,即

$ \underset{\mathit{\boldsymbol{D}}}{\mathop{\rm{min}}}\, \left\| \mathit{\boldsymbol{X}}\rm{-}\mathit{f}\left( \mathit{\boldsymbol{D}} \right) \right\|_{2}^{2} $ (1)

式中,$ \mathit{\boldsymbol{X}}$表示通过传统特征检测方法[2]提取出的原始的SIFT特征点, $ \mathit{\boldsymbol{D}}$定义为top-SIFTs的集合。函数$ f$(·)决定原始SIFT特征集合中每个描述子到字典$ \mathit{\boldsymbol{D}}$的映射,$ f$(·)是线性稀疏函数,$ \mathit{\boldsymbol{X}}$中的每个描述子都可以被$ \mathit{\boldsymbol{D}}$稀疏重建,如图 4所示。

图 4 SIFT特征点的稀疏重建
Fig. 4 Sparse reconstruction of SIFT features

图 4中,$\mathit{\alpha }$是稀疏系数。将特征选择问题化为稀疏化表示的字典学习任务的原因:两者试图寻找一个子集可以表示和重建原始数据集,目标方程定义为

$ \rm{min}\sum\limits_{\mathit{i}\rm{=1}}^{\mathit{n}}{\left\| {{\mathit{x}}_{\mathit{i}}}\rm{-}\sum\limits_{\mathit{j}\rm{=1}}^{\mathit{k}}{{{\mathit{d}}_{\mathit{j}}}{{\mathit{\alpha }}_{\mathit{ji}}}} \right\|}_{2}^{2} $ (2)

式(2)的优化目标是求特征子集与原始的特征集合之间构造误差的最小值,$ \left\| \cdot \right\|_{2}^{2}$表示的$ {\rm L}_2$规范化。这里$ x_i$表示的是第$ i$个128维的SIFT特征描述子,$ n$是一幅图片中特征点的数量。$ d_j$是本文所要学习的top-SIFT的集合,$ \mathit{\alpha }_{ji}$表示第$ j$个基向量对应的稀疏系数。对于每一张图片都学习一个字典,字典的基是最具描述力的特征描述子。

最后考虑到过少的SIFT特征的重建能力是有限的,本文加入在目标方程中稀疏约束以保证保留的SIFT特征在重建过程中的有效性和稳定性。因为字典中的基只有当其所对应的系数是非负值才会在后期的重建过程发挥作用,所以对目标方程的添加稀疏约束,即

$ \underset{\mathit{D}\rm{, }\mathit{A}}{\mathop{\rm{min}}}\, \sum\limits_{\mathit{i}}{\left\| {{\mathit{x}}_{\mathit{i}}}\rm{-}\mathit{D}{{\mathit{\alpha }}_{\mathit{i}}} \right\|_{2}^{2}}\rm{+}\mathit{\lambda }\sum\limits_{\mathit{i}}{{{\left\| {{\mathit{\alpha }}_{\mathit{i}}} \right\|}_{\rm{0}}}} $ (3)

式中,$ {{\left\| \cdot \right\|}_{0}}$表示的是$ {\rm L}_0$规范化项,$ \mathit{\lambda }$是平衡字典重建和稀疏化的参数。

2.2 SIFT特征的空间分布特性

现有的特征选择方法一直关注着128维描述子本身,但忽略了SIFT特征的空间信息。实际上,SIFT特征的空间分布包含着图像内容的结构信息;另外,图像的结构信息具有极强的描述能力,对于图像识别也具有重要的指导作用。本文在此提出一种既考虑128维特征选择,又蕴含特征的空间信息的特征选择方法,保证选择的top-SIFT特征既具有重建原始特征点的能力也能够保留原始特征点的空间分布信息。

本文期望top-SIFT具有与原始SIFT特征点相似的空间分布,即防止在图像的同一区域保留过多特征点,导致在其他区域的选取的特征点过少。Dash等人[18]提出使用熵理论来区分数据集的聚类属性的工作,对本文产生了极大启发。熵理论中,熵可以度量一个系统的无序性,即

$ \begin{align} & \ \ \ \mathit{E}\rm{=-}\sum\limits_{{{\mathit{X}}_{\mathit{i}}}}{\mathit{p}}\rm{(}{{\mathit{X}}_{\mathit{i}}}\rm{)lg}\ \mathit{p}\rm{(}{{\mathit{X}}_{\mathit{i}}}\rm{)-} \\ & \sum\limits_{{{\mathit{X}}_{\mathit{i}}}}{\rm{(1-}\mathit{p}\rm{(}{{\mathit{X}}_{\mathit{i}}}\rm{))}}\rm{lg(1-}\mathit{p}\rm{(}{{\mathit{X}}_{\mathit{i}}}\rm{))} \\ \end{align} $ (4)

式中,$ p(X_i)$表示数据的可能性或者稠密度,当系统中每个样本的概率密度相等时,整个系统的混乱程度最高,即系统的不确定性为最高值,熵值$E$取得最大值。本文改造熵理论来度量、保留SIFT特征点的空间分布:如果特征点在空间中均匀分布,那么系统的不确定高,熵的取值升高;如果特征点的分布是成簇的,那么系统输出的不确定小,熵的取值降低。本文采用特征空间中的特征点之间的距离来替代熵理论中的概率密度,即

$ \begin{align} & \mathit{E}\rm{=-}\sum\limits_{{{\mathit{X}}_{\mathit{i}}}}{\sum{\rm{(}{{\mathit{X}}_{\mathit{j}}}\rm{)}}}\rm{ }[\rm{ }{{\mathit{L}}_{\mathit{ij}}}\rm{lg}\ {{\mathit{L}}_{\mathit{ij}}}\rm{+} \\ & \ \ \ \ \ \ \rm{(1-}{{\mathit{L}}_{\mathit{ij}}}\rm{)lg(1-}{{\mathit{L}}_{\mathit{ij}}}\rm{) }]\rm{ } \\ \end{align} $ (5)

式中,$ L_{ij}$表示特征点$ X_i$$ X_j$之间在特征空间中的欧氏距离。$ L_{ij}$的取值范围被规范化到与概率密度相同的阈值[0.0,1.0]。当特征空间中的特征点具有成簇趋势时,本文算法得到一个比较低的熵值;当特征空间中的特征点均匀分布时,得到一个高熵值,如图 5所示。

图 5 特征空间中均匀分布与成簇趋势的特征点
Fig. 5 The feature points in uniform distribution and the feature points with cluster

然而Dash[18]提出:传统的熵函数及衍生函数,虽然可以粗略区分数据中是否含有成簇的数据点,但是仍然存在一定的缺陷:

1) 由于式(5)中熵函数基于欧氏距离计算,所以很小的距离范围内将会导致熵值增加变快。

2) 假设出现熵值很高的情况,无法确定该现象的真正起因是由于均匀分布的特征点样本导致,还是因为簇内的均匀分布的距离较短的导致。

因此,借鉴文献[18]中的思路,使用指数函数来解决距离较小时,熵值增加过快的问题。对SIFT特征点集合的熵函数的计算公式为

$ {{\mathit{E}}_{\mathit{ij}}}\rm{=}\left\{ \begin{align} & \frac{\rm{exp(}\mathit{\beta }\times {{\mathit{L}}_{\mathit{ij}}}\rm{)-exp}\left( \rm{0} \right)}{\rm{exp}\left( \mathit{\beta }\times \mathit{u} \right)\rm{-exp}\left( \rm{0} \right)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \rm{0}\le {{\mathit{L}}_{\mathit{ij}}}\le \mathit{u} \\ & \frac{\rm{exp(}\mathit{\beta }\times \rm{(1-}{{\mathit{L}}_{\mathit{ij}}}\rm{))-exp}\left( \rm{0} \right)}{\rm{exp}\left( \mathit{\beta }\times \left( \rm{1-}\mathit{u} \right) \right)\rm{-exp}\left( \rm{0} \right)}\ \ \ \ \ \ \mathit{u}\le {{\mathit{L}}_{\mathit{ij}}}\le \rm{1} \\ \end{align} \right. $ (6)

$ \mathit{E}\rm{=}\sum\limits_{{{\mathit{X}}_{\mathit{i}}}}{\sum\limits_{{{\mathit{X}}_{\mathit{j}}}}{{{\mathit{E}}_{\mathit{ij}}}}} $ (7)

式中,$ u$是划分簇内与簇间的参数,设置为0.3;$ \mathit{\beta }$是控制距离变化的系数,设置为10。为了保证最小的全局重构误差,选取具有高熵值的特征点。所以构造的熵空间约束为

$ \frac{{{\mathit{\lambda }}_{\rm{2}}}{{\mathit{R}}_{\rm{1}}}}{\mathit{E}} $ (8)

熵空间约束项中:

1) 分子上$ R_1$表示构造误差,是为了对top-SIFTs字典的空间稀疏性进行约束:即保证本文方法能够稀疏地学习最具描述力的SIFT特征的同时,使得最终的top-SIFTs字典能与原始的SIFT特征集合达到最小的构造误差。$ R_1$的数值由在字典重建的过程中伴随着式(2)计算得出,即在不同的原始SIFT特征点集合中,$ R_1$的取值随之变化,起到对整体目标函数在不同的特征集合中进行归一化操作的作用。

2) 分母上$ E$表示熵空间约束,约束top-SIFT字典在熵空间的分布的均匀性和非簇性,保证学习出的特征字典与原始SIFT特征集合在空间分布的重建误差达到最小。

在字典学习的目标函数中加入熵空间约束条件,最终目标方程为

$ \begin{align} & \underset{\mathit{D}\rm{, }\mathit{A}}{\mathop{\rm{min}}}\, \sum\limits_{\mathit{i}}{\left\| {{\mathit{x}}_{\mathit{i}}}\rm{-}\mathit{D}{{\mathit{\alpha }}_{\mathit{i}}} \right\|_{2}^{2}}\rm{+}{{\mathit{\lambda }}_{\rm{1}}}\sum\limits_{\mathit{i}}{{{\left\| {{\mathit{\alpha }}_{\mathit{i}}} \right\|}_{\rm{0}}}}\rm{+}\frac{{{\mathit{\lambda }}_{\rm{2}}}{{\mathit{R}}_{\rm{1}}}}{\mathit{E}} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \rm{s}\rm{.t}\rm{.}\ \ \ \ \ \ \ \ {{\mathit{\alpha }}_{\mathit{i}}}\ge \rm{0} \\ \end{align} $ (9)

至此,字典学习项、字典构造误差$ R_1$与熵空间约束项$ E$可以进行联合优化。

2.3 目标方程的优化求解

将特征选择问题转化为稀疏表示的字典学习任务,进而对其进行优化求解。然而传统的字典学习的求解算法,比如K-SVD[19]、MOD[20](method of directions)等方法,并不适于本文目标方程的求解:上述方法都是在字典学习的过程中,对于字典的基进行分解,再寻找字典的基与其对应的系数之间组合的最优解;然而本文中字典的基是取自图像原始的SIFT特征点向量,是不允许被分解的。因此受文献[17]工作的启发,采用模拟退火算法(simulated annealing algorithm)来求解本文的目标方程,学习得到最优的top-SIFTs字典,达到最终的特征选择结果。

3 实验

为了验证本文提出的特征选择方法的有效性,将在图像检索和图像拼接领域,与当前的主流的方法进行实验对比。

3.1 图像检索

3.1.1 数据集

在图像检索领域,本文使用的是数据集是法国国家信息与自动化研究所(INRIA)所公布的Holiday[21]公开检索数据集,该数据集主要包含的是个人度假的场景照片,被广泛应用于图像检索领域。数据集中包含500组场景图片,每一组图片表示一个独立的场景或目标,该数据集中的图片都是高分辨率,大尺度的场景图片。实验中取每组的第1张图片作为检索图片,其他的图片作为待检索。

受文献[22]和文献[2]的启发,本文实验采取相同的特征检测方法,共产生2 848 026个特征描述子。使用经典的词包模型(BOW)将SIFT描述子量化为视觉词汇(visual words),并使用tf-idf方法对视觉词汇进行加权处理,实验中聚类的视觉词汇量为20 k。

3.1.2 实验结果

本文使用平均准确率($ map$)作为检索结果的评价指标。采用的对比方法为PCA_SIFT与随机选择(random selection)方法,其中随机选择方法即采用随机算法,在原始SIFT特征点集中随机选取出一定比例的特征点。实验中不同方法的检索结果如表 1所示。

表 1 不同方法的检索表现(平均准确率)
Table 1 Retrieval performance of different methods($ map$)

下载CSV
方法 不同比例的特征描述子
100% 50% 40% 30% 20% 10%
Shape Context[23] 0.423 0.213 0.180 0.155 0.123 0
GLOH[25] 0.436 0.243 0.240 0.222 0.220 0.011
随机选择 0.449 0.256 0.240 0.200 0.162 0.081
PCA-SIFT[24] 0.449 0.360 0.320 0.270 0.224 0.096
top-SIFT 0.449 0.440 0.438 0.424 0.373 0.237

表 1可知,本文提出的方法与现有的方法如:Shape Context[23],PCA_SIFT[24], GLOH[25] (gradient location-orientation histogram)等,在大型图像检索领域相比取得最好的检索精度。在对原始特征点, 进行不同比例的特征选择,实验结果表明:本文选取的top-SIFTs对于图像内容具有较强的描述力,对于图像的背景噪音和冗余特征点具有较稳定的抵抗能力。

3.2 图像拼接

图像拼接的主要算法包括特征提取以及去除噪音特征的RANSEC匹配算法。其中在特征匹配阶段中,大量的特征点增加了匹配算法的时间消耗,所以极大地降低了图像拼接的效率。为了验证本文方法所选取的top-SIFT的有效性,本文设计了图像拼接实验,验证top-SIFT对原始SIFT特征点替代的可行性。

3.2.1 数据集

本文实验中使用的数据集是IPM[26](理论物理和数学研究所)视觉组图像拼接数据集,该数据集包含36组场景的图片,比如森林、街道、建筑等场景;每一组场景都包含着连续的、数量不同的图片。其中相邻两幅图像之间部分重叠或者存在相似的区域(在色彩、光照、和视点等方面存在差异)。

3.2.2 评价指标

本文采用色彩相似度($ CS$)和结构相似度($ SS$) [27],以及拼接时间$ T$作为实验中图像拼接方法的评价指标,其中, $ SS$ ∈ [0.0, 1.0]。

本文采用的评价指标是拼接场景中的第$ i$幅与第$ i$+1幅图片之间的拼接结果以及拼接对的评价指标:颜色相似度,结构相似度和拼接时间。

3.2.3 实验结果

在IPM图像拼接数据集的36组拼接场景中,对本文提取的top特征进行$ CS$(色彩相似度)的评估,实验结果如图 6所示。

图 6 图像拼接中不同特征的色彩相似度评价
Fig. 6 The color similarity assessment of different features in image stitching

图 6在图像拼接实验中,本文通过字典学习和熵空间约束所学习出来的top特征,其色彩相似度的度量并未降低。即本文在特征选择的过程中,筛选掉的大多是冗余特征,并未对整体SIFT特征集合的描述力产生不良影响。

同时对本文的top特征,进行$ SS$(结构相似度)的评估。实验结果如图 7所示。

图 7 图像拼接中不同特征的结构相似度评价
Fig. 7 The structure similarity assessment of different features in image stitching

图 7中,在图像拼接前后的$SS$(结构相似性度)评估实验中:本文所学习出的top特征与原始的SIFT特征的变化趋势基本一致;与此同时,在大多数的场景中,本文所提取的top特征的$SS$值是高于原始SIFT特征的$SS$值;虽然在第16、23、32场景中,top特征的$SS$值低于原始SIFT特征集的$SS$值,各有高低,但是两者相差不超过0.01。

另外,对本文特征选择方法的整体验证实验,如表 2所示。其中$ \overline{\mathit{CS}}$表示的是同一组场景中的所有成对的拼接图像之间的$CS$(色彩相似度)的均值;$ \overline{\mathit{SS}}$表示的是同一组场景中的所有成对的拼接图像之间的$SS$(结构相似性)的均值。

表 2 IPM数据集中8个场景的拼接结果评价
Table 2 The evaluation of stitching results in 8 scenes of IPM dataset

下载CSV
场景序号 SIFT top(50%)-SIFT top(30%)-SIFT
$ \overline{\mathit{CS}}$ $ \overline{\mathit{SS}}$ Run-T/s $ \overline{\mathit{CS}}$ $ \overline{\mathit{SS}}$ Run-T/s $ \overline{\mathit{CS}}$ $ \overline{\mathit{SS}}$ Run-T/s
1 56.89 0.970 6 28.05 56.42 0.971 9 17.98 57.62 0.977 3 13.97
2 60.42 0.994 3 32.64 60.77 0.994 6 18.99 60.52 0.995 1 12.33
3 58.02 0.990 2 47.91 58.03 0.990 8 28.36 58.04 0.992 7 15.76
4 62.67 0.991 8 35.63 62.80 0.991 8 21.30 62.89 0.991 8 13.79
5 70.04 0.993 9 33.29 61.32 0.993 5 18.53 65.21 0.994 8 13.94
6 67.79 0.987 5 42.38 67.44 0.987 9 21.71 67.21 0.987 4 13.71
7 72.80 0.977 8 29.56 72.89 0.981 5 16.12 75.28 0.979 9 13.01
8 68.12 0.978 2 23.86 67.90 0.976 4 18.14 67.91 0.982 9 9.75

表 2中,可以观察到:

1) 与原始的SIFT相比,本文方法提取的top(50%)-SIFT在$CS$$SS$指标上并未显示出明显下降;相反,在第2和第4场景中,两项指标有小幅的增长:表明本文特征选择方法的方法不仅可以消除大量冗余特征,而且在可以在一定程度上消减背景噪声, 对图像拼接的精确度进行增强。与此同时,top(50%)-SIFT减少了原始SIFT特征点近一半的时间消耗。

2) 本文提取的top(30%)-SIFT实现了与原始SIFT几乎等同的拼接表现,见图 6图 7;在时间消耗方面,top(30%)-SIFT远低于top(50%)-SIFT和原始SIFT,极大提高了拼接算法的效率。

以上的图像检索实验和图像拼接领域的实验充分证明了我们的假设:在原始SIFT特征点集合中存在大量的冗余的特征描述子;本文提出的基于字典学习和空间约束的特征选择方法在保持准确率的前提下,可以筛选最具描述力的特征点、提高应用效率。

4 结论

本文发现了特征选择与字典学习在稀疏表示方面的内在联系,并将特征选择问题转化为带空间约束的字典重建任务,提出了一个基于字典学习和熵空间约束的特征选择方法,该方法既不依赖训练数据集,也不会丢失图像中重要的色彩和结构纹理信息。在图像拼接和检索领域的实验中,充分证明了本文特征提取方法在内存节约、提高学率和保持准确度的优越表现。与已有的方法相比,本文特征选择方法及其学习到的特征描述子具有更强的可扩展性。在以后的工作中,我们将拓展到3D重建、图像聚类、场景识别等领域进行特征研究。

参考文献

  • [1] Lowe D G. Object recognition from local scale-invariant features[C]//Proceedings of the Seventh International Conference on Computer Vision. Kerkyra, Greece: IEEE, 1999: 1150-1157. [DOI:10.1109/ICCV.1999.790410]
  • [2] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91–110. [DOI:10.1023/B:VISI.0000029664.99615.94]
  • [3] Zhou N, Fan J P. Jointly learning visually correlated dictionaries for large-scale visual recognition applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(4): 715–730. [DOI:10.1109/TPAMI.2013.189]
  • [4] Lazebnik S, Schmid C, Ponce J. Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[C]//Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, NY, USA: IEEE, 2006: 2169-2178. [DOI:10.1109/CVPR.2006.68]
  • [5] Nowak E, Jurie F, Triggs B. Sampling strategies for bag-of-features image classification[C]//Proceedings of the 9th European Conference on Computer Vision. Graz, Austria: Springer, 2006: 490-503. [DOI:10.1007/11744085_38]
  • [6] Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//Proceedings of the 25th International Conference on Very Large Data Bases. Edinburgh, Scotland, UK: Morgan Kaufmann Publishers Inc., 1999: 518-529.
  • [7] Dean T, Ruzon M A, Segal M, et al. Fast, accurate detection of 100, 000 object classes on a single machine[C]//Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition. Portland, OR, USA: IEEE, 2013: 1814-1821. [DOI:10.1109/CVPR.2013.237]
  • [8] Nister D, Stewenius H. Scalable recognition with a vocabulary tree[C]//Proceedings of 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, NY, USA: IEEE, 2006: 2161-2168. [DOI:10.1109/CVPR.2006.264]
  • [9] Turcot P, Lowe D G. Better matching with fewer features: the selection of useful features in large database recognition problems[C]//Proceedings of the 12th IEEE International Conference on Computer Vision Workshops. Kyoto, Japan: IEEE, 2009: 2109-2116. [DOI:10.1109/ICCVW.2009.5457541]
  • [10] Foo J J, Sinha R. Pruning SIFT for scalable near-duplicate image matching[C]//Proceedings of the Eighteenth Conference on Australasian Database. Ballarat, Victoria, Australia: Australian Computer Society, Inc., 2007: 63-71.
  • [11] Knopp J, Sivic J, Pajdla T. Avoiding confusing features in place recognition[C]//Proceedings of the 11th European Conference on Computer Vision. Heraklion, Crete, Greece: Springer, 2010: 748-761. [DOI:10.1007/978-3-642-15549-9_54]
  • [12] Lee Y J, Grauman K. Foreground focus:unsupervised learning from partially matching images[J]. International Journal of Computer Vision, 2009, 85(2): 143–166. [DOI:10.1007/s11263-009-0252-y]
  • [13] Johnson M, Cipolla R. Stable interest points for improved image retrieval and matching[R]. Matthew Johnson and Roberto Cipolla University of Cambridge, Cambridge, UK, 2006.
  • [14] Brown M, Szeliski R, Winder S. Multi-image matching using multi-scale oriented patches[C]//Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, CA, USA: IEEE, 2005: 510-517. [DOI:10.1109/CVPR.2005.235]
  • [15] Yingze Bao S, Chandraker M, Lin Y Q, et al. Dense object reconstruction with semantic priors[C]//Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Portland, OR, USA: IEEE, 2013: 1264-1271. [DOI:10.1109/CVPR.2013.167]
  • [16] Alcantarilla P F, Beall C, Dellaert F. Large-scale dense 3D reconstruction from stereo imagery[C]//Proceedings of 5th Workshop on Planning, Perception and Navigation for Intelligent Vehicles. Tokyo, Japan: Institute of Electrical and Electronics Engineers, 2013.
  • [17] Liu Y J, Chen X M, Zhao Q L, et al. TOP-SIFT: a new method for SIFT descriptor selection[C]//Proceedings of 2015 IEEE International Conference on Multimedia Big Data. Beijing, China: IEEE, 2015: 236-239. [DOI:10.1109/BigMM.2015.34]
  • [18] Dash M, Choi K, Scheuermann P, et al. Feature selection for clustering-a filter solution[C]//Proceedings of 2002 IEEE International Conference on Data Mining. Maebashi City, Japan: IEEE, 2002: 115-122. [DOI:10.1109/ICDM.2002.1183893]
  • [19] Aharon M, Elad M, Bruckstein A. $ rmK$-SVD:an algorithm for designing overcomplete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11): 4311–4322. [DOI:10.1109/TSP.2006.881199]
  • [20] Engan K, Aase S O, Husoy J H. Frame based signal compression using method of optimal directions (MOD)[C]//1999 IEEE International Symposium on Circuits and Systems. Orlando, FL, USA: IEEE, 1999: 1-4. [DOI:10.1109/ISCAS.1999.779928]
  • [21] Jegou H, Douze M, Schmid C. Hamming embedding and weak geometric consistency for large scale image search[M]//Forsyth D, Torr P, Zisserman A. Computer Vision-ECCV 2008. Berlin, Heidelberg: Springer, 2008: 304-317. [DOI:10.1007/978-3-540-88682-2_24]
  • [22] Zhu J L, Li S J, Wan D S, et al. Content-based remote sensing image retrieval based on feature selection and semi-supervised learning[J]. Journal of Image and Graphics, 2011, 16(8): 1474–1482. [朱佳丽, 李士进, 万定生, 等. 基于特征选择和半监督学习的遥感图像检索[J]. 中国图象图形学报, 2011, 16(8): 1474–1482. ] [DOI:10.11834/jig.100112]
  • [23] Mori G, Belongie S, Malik J. Efficient shape matching using shape contexts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(11): 1832–1837. [DOI:10.1109/TPAMI.2005.220]
  • [24] Ke Y, Sukthankar R. PCA-SIFT: a more distinctive representation for local image descriptors[C]//Proceedings of 2004 IEEE Computer Society Computer Vision and Pattern Recognition. Washington, DC, USA: IEEE, 2004: Ⅱ-506-Ⅱ-513. [DOI:10.1109/CVPR.2004.1315206]
  • [25] Mikolajczyk K, Tuytelaars T, Schmid C, et al. A comparison of affine region detectors[J]. International Journal of Computer Vision, 2005, 65(1-2): 43–72. [DOI:10.1007/s11263-005-3848-x]
  • [26] Sadeghi M A, Hejrati S M M, Gheissari N. Poisson local color correction for image stitching[C]//Proceedings of the Third International Conference on Computer Vision Theory and Applications. Funchal, Madeira, Portugal: VISAPP, 2008: 275-282.
  • [27] Xu W, Mulligan J. Performance evaluation of color correction approaches for automatic multi-view image and video stitching[C]//Proceedings of 2010 IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, CA, USA: IEEE, 2010: 263-270. [DOI:10.1109/CVPR.2010.5540202]