Current Issue Cover
字典重建和空间分布关系约束下的特征选择与图像拼接

于邓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

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)

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.
Keywords

订阅号|日报