图像比较 – 快速algorithm
我正在寻找创build一个图像的基础表，然后比较任何新的图像，以确定如果新的形象是一个精确（或closures）的基地重复。
例如：如果你想减less同一个图像的存储时间，你可以存储它的一个副本，并提供参考链接。 当input一个新的图像，你想比较一个现有的图像，以确保它不是一个重复的想法？
我的一个想法是缩小到一个小的缩略图，然后随机挑选100个像素的位置，并进行比较。
下面是解决这个问题的三种方法（还有很多其他的）。
-
第一个是计算机视觉中的标准方法，即关键点匹配。 这可能需要一些背景知识来执行，并且可能会很慢。
-
第二种方法仅使用基本image processing，并且可能比第一种方法更快，并且易于实现。 然而，它在可理解性方面所获得的结果缺乏稳健性 – 在缩放，旋转或变色的图像上匹配失败。
-
第三种方法既快速又健壮，但可能是最难实施的。
关键点匹配
比挑选100个随机点更好的是挑选100个重点 。 图像的某些部分比其他部分（尤其是边缘和angular落）具有更多的信息，这些是您想要用于智能图像匹配的部分。 谷歌“ 关键点提取 ”和“ 关键点匹配 ”，你会发现不less学术论文。 现在， SIFT关键点可以说是最受欢迎的，因为它们可以在不同的尺度，旋转和光照下匹配图像。 一些SIFT实现可以在这里find。
关键点匹配的一个缺点是一个简单实现的运行时间：O（n ^ 2m），其中n是每个图像中关键点的数量，m是数据库中图像的数量。 一些聪明的algorithm可能会更快地find最接近的匹配，如四叉树或二进制空间分区。
替代解决scheme：直方图方法
另一个不太健壮但可能更快的解决scheme是为每个图像构build特征直方图，并select最接近input图像直方图的直方图。 我把它作为一个本科生来实现，我们使用了3个颜色直方图（红色，绿色和蓝色）以及两个纹理直方图，方向和比例。 我将在下面提供详细信息，但是我应该注意，这只适用于匹配非常类似于数据库映像的映像。 使用此方法重新缩放，旋转或变色的图像可能会失败，但是裁剪等细微变化不会破坏algorithm
计算颜色直方图非常简单 – 只需为直方图桶选取范围，然后在每个范围内，使用该范围内的颜色计算像素数。 例如，考虑“绿色”直方图，并假设我们为我们的直方图select了4个桶：0-63,64-127,128-191和192-255。 然后，对于每个像素，我们看绿色的值，并添加一个理货到适当的桶。 当我们完成统计时，我们将每个桶的总数除以整个图像中的像素数，得到绿色通道的归一化直方图。
对于纹理方向直方图，我们首先对图像执行边缘检测。 每个边缘点都有一个垂直于边缘方向的法向vector。 我们将法向vector的angular度量化为0和PI之间的6个桶中的一个（因为边具有180度对称性，我们将-PI和0之间的angular度转换为0和PI之间）。 在计算每个方向上边缘点的数量之后，我们有一个表示纹理方向的非归一化直方图，通过将每个桶除以图像中边缘点的总数来归一化。
为了计算纹理缩放直方图，对于每个边缘点，我们测量到具有相同方向的下一个最接近的边缘点的距离。 例如，如果边缘点A的方向为45度，则该algorithm沿着该方向行进，直到find具有45度方向（或在合理的偏差内）的另一个边缘点。 在计算每个边缘点的距离之后，我们将这些值转储到一个直方图中，并通过除以边缘点的总数将其归一化。
现在你有每个图像5个直方图。 要比较两幅图像，需要获取每个直方图桶之间差异的绝对值，然后对这些值进行求和。 例如，为了比较图像A和B，我们将进行计算
|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 对于绿色直方图中的每个桶，重复其他直方图，然后总结所有结果。 结果越小，比赛就越好。 重复数据库中的所有图像，最小结果的匹配胜出。 你可能想要有一个门槛，高于这个algorithm的结论是没有find匹配。
第三select – 关键点+决策树
第三种方法可能比另外两种方法快得多，就是使用语义森林 （PDF）。 这包括提取简单的关键点并使用集合决策树对图像进行分类。 这比简单的SIFT关键点匹配要快，因为它避免了昂贵的匹配过程，并且关键点比SIFT简单得多，因此关键点提取速度更快。 但是，它保留了SIFT方法对于旋转，缩放和光照的不变性，这是直方图方法缺乏的一个重要特征。
更新 ：
我的错误 – 语义文本森林论文不是专门针对图像匹配，而是区域标注。 匹配的原始文件是这样的： 使用随机树的关键点识别 。 此外，下面的文件继续发展的想法和代表的艺术水平（c。2010）：
- 使用随机蕨类的快速关键点识别 – 比Lepetit 06更快，更具可扩展性
-
简介：二进制健壮的独立基本function– 不太健壮，但非常快 – 我认为这里的目标是实时匹配智能手机和其他手持设备
我知道的最好的方法是使用感知哈希。 似乎有一个很好的开源的实现这样的散列可在：
其主要思想是通过识别原始图像文件中的显着特征并散列这些特征的紧凑表示（而不是直接对图像数据进行散列），将每个图像缩减为小的散列码或“指纹”。 这意味着误报率比单纯的方法大大减less，例如将图像缩小为微小的指纹图像并比较指纹。
phash提供了几种types的散列，可用于图像，audio或video。
这篇文章是我的解决scheme的起点，很多好主意，所以我尽pipe我会分享我的结果。 主要的观点是我已经find了一种通过利用phash的速度来解决基于关键点的图像匹配缓慢的方法。
对于一般的解决scheme，最好采用几种策略。 每种algorithm最适合于某些types的图像转换，您可以利用它。
顶部是最快的algorithm; 底部最慢（尽pipe更准确）。 如果在更快的级别find一个好的匹配，你可以跳过慢的。
- 基于文件哈希（md5，sha1等）的确切重复
- 感知哈希（phash）重新缩放图像
- 基于特征（SIFT）修改的图像
我用phash有非常好的效果。 精确度对于重新缩放的图像是很好的。 这对于（感知）修改的图像（裁剪，旋转，镜像等）是不好的。 为了处理哈希速度，我们必须使用磁盘caching/数据库来维护haystack的哈希值。
关于phash的真正好处在于，一旦构build了散列数据库（对于我而言大约为1000张图像/秒），search就会非常快速，尤其是当您可以将整个散列数据库保存在内存中时。 这是相当实际的，因为散列只有8个字节。
例如，如果您有一百万个图像，则需要一个包含一百万个64位散列值（8 MB）的数组。 在一些CPU上，这适合L2 / L3caching！ 在实际使用中我看到一个corei7比较超过1千兆/秒，这只是CPU的内存带宽问题。 一个10亿图像数据库在64位CPU（需要8GB RAM）上是实用的，search不会超过1秒！
对于修改/裁剪的图像，似乎像SIFT这样的变换不变特征/关键点检测器是要走的路。 SIFT将产生很好的关键点，可以检测作物/旋转/镜像等。然而，描述符比较相对phash使用的汉明距离来说非常慢。 这是一个主要的限制。 因为IxJxK描述符与查找一个图像（I = num haystack图像，J =每个干草堆图像的目标关键点，K =每个针图像的目标关键点）相比有最大的IxJxK描述符比较。
为了解决速度问题，我尝试在每个find的关键点周围使用phash，使用特征尺寸/半径来确定子矩形。 使这项工作顺利进行的诀窍是增大/缩小半径以生成不同的子矩形（在针图像上）。 通常情况下，第一级（无标度）将匹配，但经常需要几个。 我不是100％确定这是为什么这个工作，但我可以想象它使太多的function，phash的工作（phash缩放图像下降到32×32）。
另一个问题是SIFT不会优化地分配关键点。 如果图像的一部分具有很多边缘，则关键点将聚集在那里，而您将不会在另一个区域中获取任何图像。 我正在使用OpenCV中的GridAdaptedFeatureDetector来改善分配。 不知道什么网格大小是最好的，我正在使用一个小网格（1×3或3×1取决于图像的方向）。
您可能希望在进行特征检测之前将所有干草堆图像（和针）缩放到较小的尺寸（沿最大尺寸使用210px）。 这将减less图像中的噪声（对于计算机视觉algorithm总是一个问题），也将把检测器集中在更显着的特征上。
对于人物图像，您可以尝试人脸检测并使用它来确定要缩放的图像大小和网格大小（例如最大的人脸缩放为100px）。 特征检测器考虑多个比例级别（使用金字塔），但是它将使用多less级别（当然这是可调的）是有限制的。
关键点检测器在返回的function数量less于所需要的function时可能效果最好。 例如，如果你要求400和300回来，那很好。 如果你每次拿回400，那么可能有些好的function不得不被排除在外。
针图像可以比干草堆图像less关键点，仍然得到好的结果。 增加更多并不一定会带来巨大的收益，例如J = 400和K = 40，我的命中率大约是92％。 J = 400和K = 400时，命中率只有96％。
我们可以利用海明函数的极端速度来解决缩放，旋转，镜像等问题。可以使用多遍技术。 在每次迭代中，转换子矩形，重新散列，然后再次运行searchfunction。
我有一个想法，可以工作，最有可能是非常快的。 您可以对图像进行二次采样，以表示80×60分辨率或可比较的图像，并将其转换为灰度（在二次采样之后会更快）。 处理您想要比较的两个图像。 然后运行两个图像（查询图像和每个数据库）之间的归一化差异平方和，或者甚至更好的归一化互相关，如果两个图像相似，则给出接近1的响应。 然后，如果图像是相似的，你可以继续更复杂的技术来validation它是相同的图像。 显然，这个algorithm在数据库中的图像数量上是线性的，所以即使它在现代硬件上的速度要高达每秒10000个图像。 如果你需要旋转的不变性，那么可以为这个小图像计算一个主要的梯度，然后整个坐标系统可以旋转到规范的方向，但是这个速度会变慢。 不，在这里没有稳定的规模。
如果你想要更一般的东西或者使用大型数据库（数百万个图像），那么你需要研究图像检索理论（在过去的5年中出现大量的论文）。 其他答案有一些指针。 但它可能是矫枉过正，build议的直方图方法将完成这项工作。 虽然我会认为许多不同的快速方法的组合会更好。
正如cartman指出的那样，您可以使用任何types的散列值来查找精确的重复项。
find密切的图像的一个起点可能在这里 。 这是CG公司使用的一个工具，用来检查修改后的图像是否仍然显示相同的场景。
我相信，将图像的大小降低到几乎是48×48的图标大小，然后转换为灰度，然后采取像素之间的差异，或达美，应该工作。 因为我们正在比较像素颜色的变化，而不是实际的像素颜色，所以如果图像稍微更亮或更暗，则无关紧要。 由于像素太亮/太暗会丢失，所以大的变化很重要。 您可以将其应用于一行或多个您想要的位置，以提高准确性。 为了形成一个可比较的密钥，最多只有47×47 = 2,209的减法。
挑选100个随机点可能意味着类似的（或偶尔甚至不相似的）图像将被标记为相同的，我认为这不是你想要的。 如果图像是不同的格式（PNG，JPEG等），具有不同的大小，或具有不同的元数据，MD5哈希将无法正常工作。 把所有的图像缩小到更小的尺寸是一个不错的select，只要你使用了一个好的图像库/快速语言，并且尺寸足够小，那么做一个像素到像素的比较不应该花太长的时间。
你可以尝试使它们变得微小，如果它们是相同的，则在更大的尺寸上进行另一个比较 – 可以是速度和准确度的良好组合。
如果您有大量图像，请查看布卢姆filter ，该filter使用多个散列表示可能的但有效的结果。 如果图像的数量不是很大，那么像md5这样的密码散列就足够了。
