最近在清手机存储空间时想到一个问题，就是通过判断图片的重复性来删除不必要的文件，以节省空间，于是这两个月就一直在想应该怎么弄。由于灰度图像属于二维数据，所以判断图像整体的重复其实就是判断两个图像各自二维空间内的所有特征点是否在很大程度上重复，在二维数据点集匹配方面，OpenCV提供了一个非常好的模板库，那就是FLANN。
FLANN全称Fast Library for Approximate Nearest Neighbors，是一种用于近似最近邻搜索的库，而不是算法（很多人刚开始学这玩意的时候很容易混淆这个概念！）。它作为一个模板，包含了随机k-d树、优先搜索k-means树、k-medoids聚类树这几种近似数据结构，当使用FLANN进行匹配时它会根据数据规模自动选择最佳的数据结构，也可以手动指定。
FLANN工作时，首先将数据集划分为若干较小的子集，并使用这些子集来进行近似最近邻搜索，然后使用近似算法来计算每个子集中最近邻的近似距离。最后将所有子集的最近邻进行比较，并返回最小距离的最近邻。FLANN的算法更快，但是找到的是最近邻近似匹配而不是最佳的匹配，一般用于性能要求高但对错误容忍度较高的场景下。
与之对应的则是暴力匹配法，它需要先计算某一个特征点描述子与其他所有特征点描述子之间的距离，再将得到的距离进行排序，最后取距离最近的一个作为匹配点，这样一来算法复杂度就非常高，对于二维及以上高维特征，找到训练数据中的最近邻需要花费大量时间，占用大量系统资源。但其匹配精度和准确度高，用于要求苛刻但对时间不敏感的情况下。但实际生活中，大部分场景都是要求快速出结果的，因此一般采用FLANN法。
在OpenCV中，暴力匹配法使用的是BFMatcher模板类，而FLANN匹配法使用的是FlannBasedMatcher模板类，本文中只讨论FlannBasedMatcher。FLANN提供了三种函数，分别对应三种匹配算法：match()对于给定查询集合中的每个特征描述子，寻找最佳匹配，返回值按距离升序排列；knnMatch()对于给定查询集合中的每个特征描述子，寻找k个最佳匹配；radiusMatch()则是在特定范围内寻找特征描述子，返回特定距离内的匹配。综合考量，我们采用的是knnMatch()法，它的主要思路大致是：
计算两幅图像中间各个特征点之间的距离按照升序（从小到大）对距离（欧氏距离）进行排序，然后选取一个特征点对于选取的特征点，再选取距离最小的前k个点确定前k个点所在类别出现的频率返回前k个点中出现频率最高的类别作为选取特征点的分类选取下一个特征点，重复步骤2~6，直到所有特征点分类完成，然后根据“相似分类”的个数及设定阈值判断两张图片是否重复。
思路大致就是这样。对于计算图像的特征点集合，我们采用的是SIFT算法。SIFT即“尺度不变的特征变换”，它通过使用尺度不变性（构建金字塔）和关键点检测（求图像中的的极值点）来提取图像中的关键点，然后通过计算图像中每个关键点周围的梯度方向直方图，并结合上面求得关键点的位置来描述图像的特征。因此这使得SIFT算法能够在图像的尺度，旋转和形变变化的情况下能够准确的提取出图像特征点，故首选此法。
下面就是代码部分了，这里使用的是C++实现的（主要是考虑嵌入式设备上的运行效率，Python不太友好）：
#include
#include
#include
#include
using namespace cv;
using namespace cv::xfeatures2d;
int main(int argc, char** argv) {
std::string r1, r2;
std::cin >> r1;
std::cin >> r2;
// 读取两张图片
Mat image1 = imread(r1, IMREAD_GRAYSCALE);
Mat image2 = imread(r2, IMREAD_GRAYSCALE);
// 使用SIFT计算两幅图像的特征点集合
Ptr
std::vector
Mat descriptors1, descriptors2; // 描述符(点集以矩阵的形式存储，减少空间开销)
sift->detectAndCompute(image1, Mat(), keypoints1, descriptors1); // SIFT算法
sift->detectAndCompute(image2, Mat(), keypoints2, descriptors2);
// FLANN算法
Ptr
Ptr
FlannBasedMatcher matcher(indexParams, searchParams);
std::vector
matcher.knnMatch(descriptors1, descriptors2, matches, 2); // 算法是kNN, k = 2
// 使用洛氏比率过滤结果
std::vector
for(size_t i = 0; i < matches.size(); i++) {
if(matches[i][0].distance < 0.7 * matches[i][1].distance) {
goodMatches.push_back(matches[i][0]);
}
}
// 检查匹配点的数量，以确认这些图像是否是重复的，这里我选择的是50，如果对效果不满意可以适当调整
if(goodMatches.size() >= 50) {
std::cout << "Matched" << std::endl;
} else {
std::cout << "Did not match" << std::endl;
}
return 0;
}
主要思路就是，以灰度图形式读入两幅彩色图像（一定要是灰度图，否则算法时间会大大增加，因为要处理R,G,B三个通道，而这里仅仅是根据灰度值计算导数和梯度来判断特征点，所以只要有亮度上的区分就行了，黑白图像足矣），接着用SIFT算法计算特征点的矩阵，再采用套上FLANN壳子的K-D树和KNN最近邻算法匹配相似点，然后用Lowe比率过滤掉不稳定的点（因为关键点可能随着图像的变换而改变），这里就需要自己通过调试选出来了，我选的是0.7，最后根据匹配点数量来判断是否重复。
效果：
文章链接
发表评论