最近从不同网站下载了非常多的动漫壁纸，其中有一些内容相同，但是大小、背景颜色、色调、主人公的位置不同（例子如下）。正因为如此，基础的均方误差、直方图检测等方法很难识别出这些相似的图片。
OpenCV中有很多用来对特征点进行检测和计算的函数，这些函数能够利用像素点及其周围的灰度检测其是否是图像中的特征点，并计算出它的信息，比如ORB、SIFT、SURF、AKANA。同时OpenCV还有一些利用特征点的信息对特征点进行匹配的算法，比如BF、FLANN。我们可以先把参与匹配的每个图片的特征点和信息计算出来，然后对图片两两进行特征点匹配，如果两幅图片匹配上的特征点数量超过一个定值，即认为这两个图片相似。这种方法因为是直接对图像的特征进行考虑，因此对于大小、色调、主人公的位置不同的相似图片也能很好的匹配。
对于特征点检测，这些算法分为两类，一类输出的特征点信息是二进制串，包括ORB、AKANA等，一类输出的特征点信息是浮点数，包括SIFT、SURF，但是SIFT和SURF这两个算法是有专利的，商用要付钱，所以OpenCV把它们放进了Contrib扩展包里面，如果你用的是python版的OpenCV，必须下载3.4.2.16版本的opencv-contrib-python才能用OpenCV里的SIFT和SURF函数。我用的是C++版本的OpenCV，你需要下载OpenCV的源码和OpenCV-contrib扩展包然后自己编译，很麻烦，所以我选择的是ORB。对于特征点匹配，FLANN不论效率还是效果都比BF好很多（当然也有可能是我BF没用对），但是网上很多教程（包括OpenCV自己的文档）都是ORB配BF，SIFT配FLANN，StackOverflow也有人问ORB怎么搭配FLANN使用，有的回答直接说特征点信息是整数的算法不能搭配FLANN，但幸好这个问题下的另一个人给出了FLANN搭配ORB时的参数，（https://stackoverflow.com/questions/43830849/opencv-use-flann-with-orb-descriptors-to-match-features）这也说明了这个问题还是被很多人忽视的，毕竟当今世界是深度学习的天下，很少人去关注这些传统算法了。
这个程序效率比较低，需要进行一些优化。首先我们用于求特征点和匹配的图片应该是原图的灰度图经过缩小后的版本，同时注意这个操作不要用cv::resize完成，不然会慢很多，直接在imread的时候指定第二个参数为cv::IMREAD_REDUCE_COLOR_4可以在读入图片的同时缩小。当然，瓶颈还是在那个两两匹配的二重循环里，为了减少FLANN的操作，我先预处理出图像各个通道的平均值，用这个值来大致表示这个图像的色调，在二重循环中，如果两个图片的平均值相差太大（我设置的是60），就认为它们不相似，不进行特征点匹配，当然这样会导致多出不少漏网之鱼，不过实践证明这样做大部分相似的图片还是不会被筛掉的，而且速度也提高了很多。 为了降低实例代码的复杂度，把相关代码删掉了，读者可以自行参考文档添加相关优化。
#include <io.h>
#include <ctime>
#include <vector>
#include <opencv2/opencv.hpp>
int main() {
std::vector <cv::String> filelist;
typedef std::tuple <cv::String, cv::String, int> data;
std::vector <std::vector <cv::KeyPoint>> kplist;
std::vector <cv::Mat> deslist;
std::vector <data> same;
_finddata_t fd;
intptr_t pf = _findfirst("*.??g", &fd);
filelist.push_back(fd.name);
while (!_findnext(pf, &fd)) filelist.push_back(fd.name);
_findclose(pf);
//列举出图片，这里用的是io.h里的_findfirst和_findnext，通配符.??g筛选出.jpg和.png的文件
cv::Ptr <cv::ORB> orb = cv::ORB::create();
for (auto i : filelist) {
cv::Mat img = cv::imread(i, cv::IMREAD_REDUCED_GRAYSCALE_4);
std::vector<cv::KeyPoint> kp; cv::Mat des;
//kp是特征点，des是特征点的信息
orb->detectAndCompute(img, cv::Mat(), kp, des);
kplist.push_back(kp);
deslist.push_back(des);
}
std::cout << "Successfully found keypoints." << std::endl;
cv::FlannBasedMatcher flann(cv::makePtr<cv::flann::LshIndexParams>(12, 20, 2));
//这个cv::makePtr<cv::flann::LshIndexParams>(12, 20, 2)就是使FLANN能搭配ORB的参数，默认构造函数指定的是随机KD树算法，只能用于SIFT和SURF
for (int i = 0; i < filelist.size(); i++)
for (int j = i + 1; j < filelist.size(); j++) {
std::vector<cv::KeyPoint> kpl, kps; cv::Mat desl, dess;
kpl = kplist[i]; desl = deslist[i];
kps = kplist[j]; dess = deslist[j];
std::vector<std::vector<cv::DMatch>> matches;
flann.knnMatch(dess, desl, matches, 2);
std::vector <cv::DMatch> good;
for (auto k : matches) {
if (k.size() > 1 && k[0].distance < 0.5 * k[1].distance)
good.push_back(k[0]);
//knnMatch的k=2时，每个Dmatch会返回distance最小的两组匹配，当最小的这两组的distance相差足够大时，较小的那一组才可能是合法匹配
}
if (good.size() > 10) {
same.push_back(std::make_tuple(filelist[i], filelist[j], good.size()));
// cv::Mat img;
// cv::drawMatches(cv::imread(filelist[i], cv::IMREAD_REDUCED_GRAYSCALE_4), kpl, cv::imread(filelist[j], cv::IMREAD_REDUCED_GRAYSCALE_4), kps, good, img);
// cv::imshow("img", img); cv::waitKey();
}
}
std::sort(same.begin(), same.end(), [](data x, data y) {
return std::get<2>(x) > std::get<2>(y);
}); //把匹配的图片按匹配的特征点数排序
for (data i: same) {
std::cout << std::get<0>(i) << ' ' << std::get<1>(i) << ' ' << std::get<2>(i) << std::endl;
}
return 0;
}最近学了图像处理课程，想起来这篇文章，所以在这重新回顾一下。关于特征点检测部分，主要挑选的是具有尺度不变性和旋转不变性的特征点检测算法，比如SIFT和ORB，前面也说了，两者得到的特征向量类型不同，因此后面的匹配过程也不一样。
FLANN库实际上是OpenCV实现的一个最近邻检索库，和Faiss这种库是类似的，里面实现了多种最近邻检索算法，这些算法当然比BF，也就是brute-force暴力算法快。最近邻检索算法一般分为四类：量化、哈希、基于树的和基于图的。其中KD树是基于树的，因为涉及到空间的划分，所以只能支持浮点特征向量。而LSH全称是局部敏感性哈希，其核心是针对特征向量设计距离哈希函数，浮点向量可以用欧氏距离，二进制向量可以用海明距离，所以两种向量类型都可以支持。当然FLANN其实还是蛮弱的，一方面基于图的和量化相关的算法没有，另一方面没有支持GPU。可以使用Faiss库，支持的算法多，而且一部分算法也有GPU优化，也可以直接用PyTorch实现一个GPU上跑的暴力算法，效率都会有很大提升。
之前因为没搞清楚怎么在Python版的OpenCV里给FlannBasedMatcher传入LshIndexParams，后来在这里找到了，遂在这里给出Python代码：
import cv2
import glob
from matplotlib import pyplot as plt
filelist = glob.glob('*.??g')
orb = cv2.ORB_create()
kplist = []
deslist = []
index_params= {'algorithm': 6}
flann = cv2.FlannBasedMatcher(index_params);
same = []
for i in filelist:
img = cv2.imread(i, cv2.IMREAD_REDUCED_GRAYSCALE_4);
kp, des = orb.detectAndCompute(img, None);
kplist.append(kp);
deslist.append(des);
print("Successfully found keypoints.")
for i in range(len(filelist)):
for j in range(i + 1, len(filelist)):
kpl, desl = kplist[i], deslist[i]
kps, dess = kplist[j], deslist[j]
matches = flann.knnMatch(dess, desl, k=2)
good = []
for k in matches:
if len(k) > 1 and k[0].distance < 0.5 * k[1].distance:
good.append(k[0])
if len(good) > 10:
same.append((filelist[i], filelist[j], len(good)))
# img = cv2.drawMatches(cv2.imread(filelist[j], cv2.IMREAD_REDUCED_GRAYSCALE_4), kps, cv2.imread(filelist[i], cv2.IMREAD_REDUCED_GRAYSCALE_4), kpl, good, None);
# plt.imshow(img)
# plt.show()
same = iter(sorted(same, key=lambda x: x[2], reverse=True))
for i in same:
print(i)直接传入一个字典就可以了，具体取值可以看OpenCV的源码（具体可以查看FLANN模块下all_indices.h、defines.h这几个文件，LshIndexParams构造函数的三个参数取值都是默认值，这里就没给出了。根据前面的分析，理论上LSH是支持浮点特征向量的，但源码默认是海明距离，所以估计还要传什么参数，我没有仔细研究，还请读者自行思考。
从运行结果可以看到，ORB特征点好像对颜色对比度较大的角点比较感兴趣，所以可能在检测特征点之前把图片的对比度拉高一点效果会更好。
顺便说一下，SIFT专利已于2020年3月到期，Github上的OpenCV源代码已将SIFT收录至主分支，不知Python版的OpenCV库是否已更新。