我正在寻找创建一个图像基础表，然后比较任何新图像，以确定新图像是否是基础的精确（或接近）副本 .
例如：如果您想减少100次相同图像的存储，您可以存储它的一个副本并提供它的参考链接 . 输入新图像时，您想要与现有图像进行比较，以确保它不是重复的...想法？
我的一个想法是缩小到一个小缩略图，然后随机选择100个像素位置并进行比较 .
我相信将图像的大小降低到几乎图标大小，比如48x48，然后转换为灰度，然后取像素或Delta之间的差异应该可以正常工作 . 因为我们正在比较像素颜色的变化而不是实际的像素颜色，所以如果图像稍微更亮或更暗则无关紧要 . 大的变化将很重要，因为像素变得太亮/暗将会丢失 . 您可以将这个应用于一行，也可以根据需要随意应用，以提高准确性 . 为了形成类似的密钥，你最多需要47x47 = 2,209次减法 .
正如cartman指出的那样，您可以使用任何类型的哈希值来查找完全相同的重复项 .
找到近景图像的一个起点可能是here . 这是CG公司用来检查修改过的图像是否仍然显示基本相同的场景的工具 .
以下是解决此问题的三种方法（还有许多其他方法） .
第一种是计算机视觉，关键点匹配的标准方法 . 这可能需要一些背景知识来实现，并且可能很慢 .
第二种方法仅使用基本图像处理，并且可能比第一种方法更快，并且可以直接实现 . 然而，它在可理解性方面获得了什么，缺乏鲁棒性 - 在缩放，旋转或变色图像上匹配失败 .
第三种方法既快速又健壮，但可能是最难实现的方法 .
Keypoint Matching
挑选100个随机点比挑选100个重点要好 . 图像的某些部分比其他部分（特别是边缘和角落）具有更多信息，这些是您希望用于智能图像匹配的部分 . 谷歌“keypoint extraction " and " keypoint matching”，你会发现很多关于这个问题的学术论文 . 如今，SIFT keypoints可以说是最受欢迎的，因为它们可以匹配不同比例，旋转和光照下的图像 . 可以找到一些SIFT实现here .
关键点匹配的一个缺点是天真实现的运行时间：O（n ^ 2m），其中n是每个图像中关键点的数量，m是数据库中的图像数量 . 一些聪明的算法可能会更快找到最接近的匹配，如四叉树或二进制空间分区 .
Alternative solution: Histogram method
另一个不太稳健但可能更快的解决方案是为每个图像构建特征直方图，并选择最接近输入图像直方图的直方图图像 . 我将其实现为本科生，我们使用3种颜色直方图（红色，绿色和蓝色）和两种纹理直方图，方向和比例 . 我将在下面给出详细信息，但我应该注意，这只适用于匹配图像非常类似于数据库图像 . 使用此方法重新缩放，旋转或变色的图像可能会失败，但像裁剪这样的小变化不会破坏算法
计算颜色直方图很简单 - 只需选择直方图桶的范围，并为每个范围计算具有该范围颜色的像素数 . 例如，考虑“绿色”直方图，并假设我们为直方图选择4个桶：0-63,64-127,128-191和192-255 . 然后，对于每个像素，我们查看绿色值，并向相应的桶添加计数 . 当我们完成计数时，我们将每个桶总数除以整个图像中的像素数，以获得绿色通道的标准化直方图 .
对于纹理方向直方图，我们首先对图像进行边缘检测 . 每个边缘点具有指向垂直于边缘的方向的法向矢量 . 我们将法向量的角度量化为0和PI之间的6个桶中的一个（因为边缘具有180度对称性，我们将-PI和0之间的角度转换为0和PI之间） . 在计算每个方向上的边缘点的数量之后，我们具有表示纹理方向的非标准化直方图，我们通过将每个桶除以图像中的边缘点的总数来标准化 .
为了计算纹理比例直方图，对于每个边缘点，我们测量到具有相同方向的下一个最近边缘点的距离 . 例如，如果边缘点A具有45度的方向，则算法沿该方向行走，直到找到具有45度方向（或在合理偏差内）的另一个边缘点 . 在为每个边缘点计算此距离后，我们将这些值转储到直方图中，并通过除以边缘点的总数来对其进行标准化 .
现在每个图像有5个直方图 . 要比较两个图像，您可以获取每个直方图桶之间差异的绝对值，然后对这些值求和 . 例如，为了比较图像A和B，我们将进行计算
|A.green_histogram.bucket_1 - B.green_histogram.bucket_1|
对于绿色直方图中的每个桶，并重复其他直方图，然后总结所有结果 . 结果越小，匹配越好 . 对数据库中的所有图像重复，并获得最小结果的匹配 . 你可能想要一个阈值，超过该阈值，算法得出结论，没有找到匹配 .
Third Choice - Keypoints + Decision Trees
第三种方法可能比其他两种方法快得多，使用semantic texton forests（PDF） . 这涉及提取简单的关键点和使用收集决策树来对图像进行分类 . 这比简单的SIFT关键点匹配更快，因为它避免了昂贵的匹配过程，并且关键点比SIFT简单得多，因此关键点提取要快得多 . 但是，它保留了SIFT方法对旋转，缩放和光照的不变性，这是直方图方法所缺乏的一个重要特征 .
Update ：
我的错误 - Semantic Texton Forests的论文并不是专门针对图像匹配，而是区域标记 . 匹配的原始论文是这一篇：Keypoint Recognition using Randomized Trees . 此外，下面的论文继续发展思路并代表最新技术水平（c.2010）：
Fast Keypoint Recognition using Random Ferns - 比Lepetit 06更快，更具可扩展性
BRIEF: Binary Robust Independent Elementary Features - 不太健壮但非常快 - 我认为这里的目标是智能手机和其他手持设备上的实时匹配
如果你有大量的图像，请查看Bloom filter，它使用多个哈希值来获得可能但效率很高的结果 . 如果图像数量不是很大，那么像md5这样的加密哈希就足够了 .
这篇文章是我的解决方案的起点，这里有很多好点子，所以我会分享我的结果 . 主要的见解是，我找到了一种方法，通过利用phash的速度来解决基于关键点的图像匹配的缓慢 .
对于一般解决方案，最好采用几种策略 . 每种算法最适合某些类型的图像转换，您可以利用它 .
在顶部，最快的算法;在底部最慢（虽然更准确） . 如果在更快的级别找到一个好的匹配，你可以跳过慢的 .
基于文件哈希（md5，sha1等）的精确重复项
重新缩放图像的感知哈希（phash）_999_基于特征的（SIFT）用于修改的图像
我用phash得到了非常好的结果 . 精确度适用于重新缩放的图像 . 它对于（感知上）修改过的图像（裁剪，旋转，镜像等）并不好 . 为了处理散列速度，我们必须使用磁盘缓存/数据库来维护haystack的哈希值 .
关于phash的一个非常好的事情是，一旦你构建了哈希数据库（对我来说大约是1000个图像/秒），搜索可以非常非常快，特别是当你可以将整个哈希数据库保存在内存中时 . 这是相当实用的，因为哈希只有8个字节 .
例如，如果您有100万个图像，则需要一个包含100万个64位哈希值（8 MB）的数组 . 在某些CPU上，这适合L2 / L3缓存！在实际应用中，我看到核心数据比较超过1千兆赫/秒，这只是CPU内存带宽的问题 . 一个10亿像素的数据库在64位CPU（需要8GB RAM）上是实用的，搜索不会超过1秒！
对于修改/裁剪的图像，它似乎是一个变换不变的特征/关键点检测器，如SIFT是要走的路 . SIFT将生成检测裁剪/旋转/镜像等的良好关键点 . 然而，与phash使用的汉明距离相比，描述符比较非常慢 . 这是一个主要限制 . 有很多比较要做，因为有最大的IxJxK描述符比较查找一个图像（I = num haystack图像，J =每个干草堆图像的目标关键点，K =每个针图像的目标关键点） .
为了解决速度问题，我尝试在每个找到的关键点周围使用phash，使用特征尺寸/半径来确定子矩形 . 使这项工作顺利进行的技巧是增大/缩小半径以生成不同的子矩形水平（在针图像上） . 通常情况下，第一级（未缩放）将匹配，但通常需要更多 . 我不是百分之百确定为什么会这样，但我可以想象它能够实现太小而不能使用phash的功能（phash将图像缩小到32x32） .
另一个问题是SIFT不会以最佳方式分发关键点 . 如果图像的一部分有很多边缘，那么关键点将聚集在那里，你将不会在另一个区域中得到任何关键点 . 我在OpenCV中使用GridAdaptedFeatureDetector来改进分发 . 不确定网格尺寸最好，我使用的是小网格（1x3或3x1，具体取决于图像方向） .
您可能希望在特征检测之前将所有干草堆图像（和针）缩放到较小的尺寸（沿最大尺寸使用210px） . 这将减少图像中的噪声（对于计算机视觉算法来说总是一个问题），也会将探测器集中在更突出的特征上 .
对于人物图像，您可以尝试使用面部检测并使用它来确定要缩放到的图像大小和网格大小（例如，最大面部缩放为100px） . 特征检测器考虑了多个比例级别（使用金字塔）但是它将使用多少级别（当然这是可调的）是有限的 .
当关键点检测器返回的数量少于您想要的功能数量时，它可能效果最佳 . 例如，如果你要求400并获得300，这是好的 . 如果你回来了400每次都可能遗漏一些好的功能 .
针图像可以比干草堆图像具有更少的关键点，并且仍然获得良好的结果 . 添加更多不一定会带来巨大的收益，例如J = 400和K = 40，我的命中率约为92％ . 当J = 400且K = 400时，命中率仅上升至96％ .
我们可以利用汉明函数的极速来解决缩放，旋转，镜像等问题 . 可以使用多次通过技术 . 在每次迭代时，转换子矩形，重新哈希，然后再次运行搜索功能 .
我有一个想法，它可以工作，它很可能非常快 . 您可以对图像进行二次采样，使其分辨率为80x60或具有可比性，并将其转换为灰度（在二次采样后，它会更快） . 处理您想要比较的两个图像 . 然后运行两个图像（查询图像和每个来自数据库）之间的归一化平方差的和，或甚至更好的标准化交叉相关，如果两个图像相似，则响应更接近1 . 然后，如果图像相似，您可以继续使用更复杂的技术来验证它是相同的图像 . 显然，这个算法在数据库中的图像数量方面是线性的，因此即使它在现代硬件上的速度高达每秒10000个图像 . 如果你需要旋转的不变性，那么可以为这个小图像计算主导梯度，然后整个坐标系可以旋转到规范方向，但这会慢一些 . 不，这里没有不变的规模 .
如果你想要更通用的东西或使用大型数据库（数百万张图像），那么你需要研究图像检索理论（过去5年出现的大量论文） . 其他答案中有一些指示 . 但它可能是矫枉过正，建议直方图方法将起作用 . 虽然我认为许多不同快速方法的组合会更好 .
我所知道的最好的方法是使用Perceptual Hash . 似乎有一个很好的开源实现这样的哈希可用于：
http://phash.org/
主要思想是通过识别原始图像文件中的显着特征并散列这些特征的紧凑表示（而不是直接对图像数据进行散列）来将每个图像缩小为小的哈希码或“指纹” . 这意味着通过简单的方法可以大大降低误报率，例如将图像缩小到微小的指纹尺寸图像并比较指纹 .
phash提供了几种类型的哈希，可用于图像，音频或视频 .
挑选100个随机点可能意味着相似（或偶尔甚至不相似）的图像将被标记为相同，我认为这不是您想要的 . 如果图像是不同的格式（png，jpeg等），具有不同的大小或具有不同的元数据，MD5哈希将不起作用 . 将所有图像缩小到更小的尺寸是一个不错的选择，只要您使用的是良好的图像库/快速语言，并且尺寸足够小，进行逐像素比较就不会花费太长时间 .
您可以尝试将它们变得很小，然后如果它们相同则在更大尺寸上执行另一次比较 - 可能是速度和准确性的良好组合......
8 回答
我相信将图像的大小降低到几乎图标大小，比如48x48，然后转换为灰度，然后取像素或Delta之间的差异应该可以正常工作 . 因为我们正在比较像素颜色的变化而不是实际的像素颜色，所以如果图像稍微更亮或更暗则无关紧要 . 大的变化将很重要，因为像素变得太亮/暗将会丢失 . 您可以将这个应用于一行，也可以根据需要随意应用，以提高准确性 . 为了形成类似的密钥，你最多需要47x47 = 2,209次减法 .
正如cartman指出的那样，您可以使用任何类型的哈希值来查找完全相同的重复项 .
找到近景图像的一个起点可能是here . 这是CG公司用来检查修改过的图像是否仍然显示基本相同的场景的工具 .
以下是解决此问题的三种方法（还有许多其他方法） .
第一种是计算机视觉，关键点匹配的标准方法 . 这可能需要一些背景知识来实现，并且可能很慢 .
第二种方法仅使用基本图像处理，并且可能比第一种方法更快，并且可以直接实现 . 然而，它在可理解性方面获得了什么，缺乏鲁棒性 - 在缩放，旋转或变色图像上匹配失败 .
第三种方法既快速又健壮，但可能是最难实现的方法 .
Keypoint Matching
挑选100个随机点比挑选100个重点要好 . 图像的某些部分比其他部分（特别是边缘和角落）具有更多信息，这些是您希望用于智能图像匹配的部分 . 谷歌“keypoint extraction " and " keypoint matching”，你会发现很多关于这个问题的学术论文 . 如今，SIFT keypoints可以说是最受欢迎的，因为它们可以匹配不同比例，旋转和光照下的图像 . 可以找到一些SIFT实现here .
关键点匹配的一个缺点是天真实现的运行时间：O（n ^ 2m），其中n是每个图像中关键点的数量，m是数据库中的图像数量 . 一些聪明的算法可能会更快找到最接近的匹配，如四叉树或二进制空间分区 .
Alternative solution: Histogram method
另一个不太稳健但可能更快的解决方案是为每个图像构建特征直方图，并选择最接近输入图像直方图的直方图图像 . 我将其实现为本科生，我们使用3种颜色直方图（红色，绿色和蓝色）和两种纹理直方图，方向和比例 . 我将在下面给出详细信息，但我应该注意，这只适用于匹配图像非常类似于数据库图像 . 使用此方法重新缩放，旋转或变色的图像可能会失败，但像裁剪这样的小变化不会破坏算法
计算颜色直方图很简单 - 只需选择直方图桶的范围，并为每个范围计算具有该范围颜色的像素数 . 例如，考虑“绿色”直方图，并假设我们为直方图选择4个桶：0-63,64-127,128-191和192-255 . 然后，对于每个像素，我们查看绿色值，并向相应的桶添加计数 . 当我们完成计数时，我们将每个桶总数除以整个图像中的像素数，以获得绿色通道的标准化直方图 .
对于纹理方向直方图，我们首先对图像进行边缘检测 . 每个边缘点具有指向垂直于边缘的方向的法向矢量 . 我们将法向量的角度量化为0和PI之间的6个桶中的一个（因为边缘具有180度对称性，我们将-PI和0之间的角度转换为0和PI之间） . 在计算每个方向上的边缘点的数量之后，我们具有表示纹理方向的非标准化直方图，我们通过将每个桶除以图像中的边缘点的总数来标准化 .
为了计算纹理比例直方图，对于每个边缘点，我们测量到具有相同方向的下一个最近边缘点的距离 . 例如，如果边缘点A具有45度的方向，则算法沿该方向行走，直到找到具有45度方向（或在合理偏差内）的另一个边缘点 . 在为每个边缘点计算此距离后，我们将这些值转储到直方图中，并通过除以边缘点的总数来对其进行标准化 .
现在每个图像有5个直方图 . 要比较两个图像，您可以获取每个直方图桶之间差异的绝对值，然后对这些值求和 . 例如，为了比较图像A和B，我们将进行计算
对于绿色直方图中的每个桶，并重复其他直方图，然后总结所有结果 . 结果越小，匹配越好 . 对数据库中的所有图像重复，并获得最小结果的匹配 . 你可能想要一个阈值，超过该阈值，算法得出结论，没有找到匹配 .
Third Choice - Keypoints + Decision Trees
第三种方法可能比其他两种方法快得多，使用semantic texton forests（PDF） . 这涉及提取简单的关键点和使用收集决策树来对图像进行分类 . 这比简单的SIFT关键点匹配更快，因为它避免了昂贵的匹配过程，并且关键点比SIFT简单得多，因此关键点提取要快得多 . 但是，它保留了SIFT方法对旋转，缩放和光照的不变性，这是直方图方法所缺乏的一个重要特征 .
Update ：
我的错误 - Semantic Texton Forests的论文并不是专门针对图像匹配，而是区域标记 . 匹配的原始论文是这一篇：Keypoint Recognition using Randomized Trees . 此外，下面的论文继续发展思路并代表最新技术水平（c.2010）：
Fast Keypoint Recognition using Random Ferns - 比Lepetit 06更快，更具可扩展性
BRIEF: Binary Robust Independent Elementary Features - 不太健壮但非常快 - 我认为这里的目标是智能手机和其他手持设备上的实时匹配
如果你有大量的图像，请查看Bloom filter，它使用多个哈希值来获得可能但效率很高的结果 . 如果图像数量不是很大，那么像md5这样的加密哈希就足够了 .
这篇文章是我的解决方案的起点，这里有很多好点子，所以我会分享我的结果 . 主要的见解是，我找到了一种方法，通过利用phash的速度来解决基于关键点的图像匹配的缓慢 .
对于一般解决方案，最好采用几种策略 . 每种算法最适合某些类型的图像转换，您可以利用它 .
在顶部，最快的算法;在底部最慢（虽然更准确） . 如果在更快的级别找到一个好的匹配，你可以跳过慢的 .
基于文件哈希（md5，sha1等）的精确重复项
重新缩放图像的感知哈希（phash）
_999_基于特征的（SIFT）用于修改的图像
我用phash得到了非常好的结果 . 精确度适用于重新缩放的图像 . 它对于（感知上）修改过的图像（裁剪，旋转，镜像等）并不好 . 为了处理散列速度，我们必须使用磁盘缓存/数据库来维护haystack的哈希值 .
关于phash的一个非常好的事情是，一旦你构建了哈希数据库（对我来说大约是1000个图像/秒），搜索可以非常非常快，特别是当你可以将整个哈希数据库保存在内存中时 . 这是相当实用的，因为哈希只有8个字节 .
例如，如果您有100万个图像，则需要一个包含100万个64位哈希值（8 MB）的数组 . 在某些CPU上，这适合L2 / L3缓存！在实际应用中，我看到核心数据比较超过1千兆赫/秒，这只是CPU内存带宽的问题 . 一个10亿像素的数据库在64位CPU（需要8GB RAM）上是实用的，搜索不会超过1秒！
对于修改/裁剪的图像，它似乎是一个变换不变的特征/关键点检测器，如SIFT是要走的路 . SIFT将生成检测裁剪/旋转/镜像等的良好关键点 . 然而，与phash使用的汉明距离相比，描述符比较非常慢 . 这是一个主要限制 . 有很多比较要做，因为有最大的IxJxK描述符比较查找一个图像（I = num haystack图像，J =每个干草堆图像的目标关键点，K =每个针图像的目标关键点） .
为了解决速度问题，我尝试在每个找到的关键点周围使用phash，使用特征尺寸/半径来确定子矩形 . 使这项工作顺利进行的技巧是增大/缩小半径以生成不同的子矩形水平（在针图像上） . 通常情况下，第一级（未缩放）将匹配，但通常需要更多 . 我不是百分之百确定为什么会这样，但我可以想象它能够实现太小而不能使用phash的功能（phash将图像缩小到32x32） .
另一个问题是SIFT不会以最佳方式分发关键点 . 如果图像的一部分有很多边缘，那么关键点将聚集在那里，你将不会在另一个区域中得到任何关键点 . 我在OpenCV中使用GridAdaptedFeatureDetector来改进分发 . 不确定网格尺寸最好，我使用的是小网格（1x3或3x1，具体取决于图像方向） .
您可能希望在特征检测之前将所有干草堆图像（和针）缩放到较小的尺寸（沿最大尺寸使用210px） . 这将减少图像中的噪声（对于计算机视觉算法来说总是一个问题），也会将探测器集中在更突出的特征上 .
对于人物图像，您可以尝试使用面部检测并使用它来确定要缩放到的图像大小和网格大小（例如，最大面部缩放为100px） . 特征检测器考虑了多个比例级别（使用金字塔）但是它将使用多少级别（当然这是可调的）是有限的 .
当关键点检测器返回的数量少于您想要的功能数量时，它可能效果最佳 . 例如，如果你要求400并获得300，这是好的 . 如果你回来了400每次都可能遗漏一些好的功能 .
针图像可以比干草堆图像具有更少的关键点，并且仍然获得良好的结果 . 添加更多不一定会带来巨大的收益，例如J = 400和K = 40，我的命中率约为92％ . 当J = 400且K = 400时，命中率仅上升至96％ .
我们可以利用汉明函数的极速来解决缩放，旋转，镜像等问题 . 可以使用多次通过技术 . 在每次迭代时，转换子矩形，重新哈希，然后再次运行搜索功能 .
我有一个想法，它可以工作，它很可能非常快 . 您可以对图像进行二次采样，使其分辨率为80x60或具有可比性，并将其转换为灰度（在二次采样后，它会更快） . 处理您想要比较的两个图像 . 然后运行两个图像（查询图像和每个来自数据库）之间的归一化平方差的和，或甚至更好的标准化交叉相关，如果两个图像相似，则响应更接近1 . 然后，如果图像相似，您可以继续使用更复杂的技术来验证它是相同的图像 . 显然，这个算法在数据库中的图像数量方面是线性的，因此即使它在现代硬件上的速度高达每秒10000个图像 . 如果你需要旋转的不变性，那么可以为这个小图像计算主导梯度，然后整个坐标系可以旋转到规范方向，但这会慢一些 . 不，这里没有不变的规模 .
如果你想要更通用的东西或使用大型数据库（数百万张图像），那么你需要研究图像检索理论（过去5年出现的大量论文） . 其他答案中有一些指示 . 但它可能是矫枉过正，建议直方图方法将起作用 . 虽然我认为许多不同快速方法的组合会更好 .
我所知道的最好的方法是使用Perceptual Hash . 似乎有一个很好的开源实现这样的哈希可用于：
http://phash.org/
主要思想是通过识别原始图像文件中的显着特征并散列这些特征的紧凑表示（而不是直接对图像数据进行散列）来将每个图像缩小为小的哈希码或“指纹” . 这意味着通过简单的方法可以大大降低误报率，例如将图像缩小到微小的指纹尺寸图像并比较指纹 .
phash提供了几种类型的哈希，可用于图像，音频或视频 .
挑选100个随机点可能意味着相似（或偶尔甚至不相似）的图像将被标记为相同，我认为这不是您想要的 . 如果图像是不同的格式（png，jpeg等），具有不同的大小或具有不同的元数据，MD5哈希将不起作用 . 将所有图像缩小到更小的尺寸是一个不错的选择，只要您使用的是良好的图像库/快速语言，并且尺寸足够小，进行逐像素比较就不会花费太长时间 .
您可以尝试将它们变得很小，然后如果它们相同则在更大尺寸上执行另一次比较 - 可能是速度和准确性的良好组合......