我有从网络上收集图片的习惯，时间久了就积攒了大量的图片，其中不乏重复的图片。手工筛选工作量太大，于是写了一段程序，利用OpenCV的图像处理功能找出这些重复的图片。

        一个文件夹中的图片尺寸千差万别，有些重复图片的尺寸相同，有些则不同，所以需要对所有图片的尺寸归一化。再者，图片中含有大量像素点，如果直接比较两个图片会比较耗时。我也希望在寻找重复图片的同时对所图片重新命名，便于以后从文件名上就能唯一辨识图片。所以我想到建立数字ID的方法，以数字ID判别图片是否重复，而且也可以把ID作为图片的名称。

        建立数字ID的过程如下：

        1. 将所有图片归一化为8×8的灰度图像，灰度级别映射到0-7，这样每张图片就得到了64个八进制数；

        2. 把第i个和第i+1个八进制数相加（i为奇数），变为32个十六进制数；

        3. 将这32个十六进制数按图像矩阵中从上到下、从左到右顺序排列，得到一个长度为16的字符串，即图片的数字ID。

---

代码

        编程环境为Windows 7 + Visual Studio 2010。需要OpenCV库与dirent.h头文件。OpenCV的环境配置可以参考本博这篇文章《Windows7+VS2010下OpenCV环境配置》，本文采用的版本是2.4.9；dirent.h可以从这里下载http://softagalleria.net/dirent.php，本文采用的版本是1.10。

        代码也可以在这里下载：https://github.com/johnhany/SameImages

---

代码详解

        首先，用dirent.h提供的接口读取指定文件夹下的所有文件路径，并保存在vector<string> file_paths中。使用dirent.h可以省去自己配置读取文件所需变量的繁琐过程，但是不能读取子文件夹中的文件。在读取文件路径的同时调用readPicture()，使用OpenCV读入图片，并保存在Mat中，然后用resize()缩小到8×8，并用LUT()（Look Up Table，查找表）把灰度级别从0-255映射到0-7，将结果保存在vector<Mat> stamp_img中。考虑到把一张尺寸几百像素的图片缩小到8×8，会产生非常大的误差，所以从这里开始寻找相同图片的问题实际上变成了寻找相似图片的问题。

        之后调用generateStamps()，把64个8进制数转化为长度32的字符串，保存在vector<string> stamp_str中，同时计算每张归一化图片的均值和方差，保存在vector<pair<int,float> > stamp_stats中。

        接着用roughClassify()根据图像的方差使用K-均值法对所有图像进行分类。因为如果直接对所有字符串进行两两比对，时间复杂度是O(n^2)，n是图片的总数；如果先分类，只在同类中进行两两比对，时间复杂度就是O(mn)，m是每类的图片平均数量。归一化图像的灰度级别只有8级，方差最大一般不超过50，类别数量较多会使得某些类中只有1个样本。为了保证不同类间不会存在相似的图片，m就不能过小。这里最大类别数量限制为10。分类结果保存在vector<vector<pair<string,int> >> stamp_class中，第一层vector表示类别，第二层的vector表示类内样本，string是数字ID，int是vector<string> file_paths中对应的编号。

        然后调用comparePictures()，在不同类别中对数字ID进行一一比对。这里有三种规则可以选择，EXACT_SAME表示只有两个数字ID完全相同时才认为图片相同，MOST_MATCHES表示当两个字符串中相同的字符数量超过一定值时才认为图片相同（这里取25），NEAREST_DISTANCE表示两个字符串所代表的16进制数序列的绝对值距离小于一定值时才认为图片相同（也就是统计投票数，每一位上数值相同时得2票，数值相差1时得1票，得票总数越多相似度越高。这里阈值取51）。使用找到的图片序号保存在vector<pair<int,int> > out_same中。

        最后，用deleteSameFile()删除多余的图片，其中flag参数的含义如下：DELETE_FIRST表示删除先读到的图片，DELETE_LAST表示删除后读到的图片，DELETE_LARGE表示删除尺寸较大的图片，DELETE_SMALL表示删除尺寸较小的图片。再用renamePictures()为余下的图片重新命名。

---

测试

        测试集：262张图片，其中25张重复，而且尺寸都经过了不同比例的缩放。

        对结果精确性影响较大的是comparePictures()中判定规则的选取。EXACT_SAME显然很不合适；MOST_MATCHES找到了18张；NEAREST_DISTANCE找到了全部的25张。所以推荐使用NEAREST_DISTANCE进行判别。

        这是重命名后的部分结果，可以发现在顶部有大片空白的图片都聚集到文件夹末尾了。