如何在大量无损压缩图像中提取重复图像对（完全相同）？如何在内存中std:：hash？

Question

我的应用程序问题是，我可以得到大约500个图像，但可能有1个或2个两个图像是完全相同的，这意味着文件的校验和是相同的。我的最终目标是找出巴黎的重复形象。在

但是现在我不得不对这500张图像应用压缩算法，因为未压缩的图像占用了太多的磁盘空间。好吧，压缩破坏了校验和，所以我不能使用压缩图像文件的校验和来找出哪些是重复的图像对。在

幸运的是，我的压缩算法是无损的，这意味着恢复的未压缩图像仍然可以以某种方式散列。但我只想在没有太多磁盘写入访问的内存中执行此操作。所以我的问题是如何有效地从内存中的大量图像文件中提取重复图像？在

我经常使用opencv，但只要它是有效的，而不在磁盘上保存任何文件，答案都是好的。Python／BASH代码也可以接受，C/C++和OpenCV是首选。在

我可以考虑在std:：hash中使用OpenCV的Mat，但是std:：hash不能直接工作，我必须具体地对std::hash<cv::Mat>进行编码，而且我还不知道如何正确地进行编码。在

我当然能做到

For each 2 images in all my images:
            if ((cv::Mat)img1 == (cv::Mat)img2):
                   print img1 and img2 are identical

但这是非常低效的，基本上是一个n^4算法。在

注意我的问题不是图像相似性问题，而是memroy中的哈希问题。

Answer 1

获取图像哈希算法的想法：

1. 减小原始图像的大小（cvResize（）），以便只有重要的对象保留在图片上（去掉高频）。 将图像减少到8x8，则像素总数将为64，哈希将适合所有类型的图像，而不管它们的大小和纵横比。

2. 去掉颜色。将在上一步中获得的图像转换为灰度。（CVCVT颜色（））。因此，hash将从192（三个通道的64个值-红色、绿色和蓝色）减少到64个亮度值。

3. 找到结果图像的平均亮度。（cvAvg（））

4. 图像的二值化。（cvThreshold（））只保留那些大于平均值的像素（将它们视为1，所有其他像素都视为0）。

5. 构建哈希。将1和0图片的64个值转换为一个64位哈希值。

接下来，如果您需要比较两个图像，那么只需为每个图像构建一个哈希，并计算不同位的数量（使用Hamming距离）。 汉明距离-相同长度的两个二进制字的各自数目不同的位置数。在

距离为零意味着它很可能是相同的图像，而其他值表示它们之间的差异有多大。在

Answer 2

如果它是您想要的图像的精确副本，您可以开始比较所有图像的像素1,1，并按像素1,1上的相同值对它们进行分组。在那之后，你认识了团体（希望有很多团体？）然后比较每组像素1,2。这样你就一个像素一个像素地工作，直到你得到大约100个组。而不是你只需要在每个小组里比较他们。这样你就可以使用慢n^4算法，但是每次都是5张图片组成的一组，而不是每次500张图片。我假设你可以一个像素一个像素地读入你的图像，我知道这是可能的，如果他们是在.fits，与pyfits模块，但我猜几乎任何图像格式都有替代品？在

所以这背后的想法是，如果像素1,1不同，整个图像就不同。这样你就可以列出前3个像素的值。如果在这个列表中，有足够的可变性，您可以对更小的图像组进行1-1个完整的图像检查，而不是一次检查500个图像。 这听起来像是你想要的吗？在

Answer 3

好吧，我自己想出了一个解决方案，欢迎有更好的解决方案。我把代码贴在这里。在

#include "opencv2/core/core.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/highgui/highgui.hpp"
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <functional>
#include <openssl/md5.h>

using namespace std;
using namespace cv;

static void help()
{
}

char *str2md5(const char *str, int length) {
    int n;
    MD5_CTX c;
    unsigned char digest[16];
    char *out = (char*)malloc(33);

    MD5_Init(&c);

    while (length > 0) {
        if (length > 512) {
            MD5_Update(&c, str, 512);
        } else {
            MD5_Update(&c, str, length);
        }
        length -= 512;
        str += 512;
    }

    MD5_Final(digest, &c);

    for (n = 0; n < 16; ++n) {
        snprintf(&(out[n*2]), 16*2, "%02x", (unsigned int)digest[n]);
    }

    return out;
}


int main(int argc, const char** argv)
{
    help();

    if (argc != 2)
    {
        return EXIT_FAILURE ;
    }

    string inputfile = argv[1] ;

    Mat src = imread (inputfile, -1) ;

    if (src.empty())
    {
        return EXIT_FAILURE ;
    }



    cout << str2md5((char*)src.data, (int)src.step[0] * src.rows) << " " << inputfile << endl ;




    return 0;
}

您必须在您的机器中安装OpenSSL（libssl dev）才能编译此代码。它将图像加载到内存中，并计算其md5值。因此，要找到重复映像对，只需使用编译的程序编写一个简单的bash/python脚本，在文件的md5值数组中进行搜索。注意，这个md5检查代码不能处理巨大的图像文件。在