快速算法
我正在寻找创建一个基本的图像表，然后比较任何新的图像，以确定新图像是否是基准的精确（或接近）重复。
例如：如果您想减少同一张图片100次的存储空间，您可以存储它的一个副本并提供参考链接。 当输入一个新图像时，你想比较一个现有的图像，以确保它不是重复的想法？
我的想法之一是缩小到一个小缩略图，然后随机挑选100个像素位置并进行比较。
下面是解决这个问题的三种方法（还有很多其他方法）。
第一个是计算机视觉和关键点匹配的标准方法。 这可能需要一些背景知识来执行，并且可能会很慢。
第二种方法仅使用基本图像处理，并且可能比第一种方法更快，并且易于实现。 然而，它在可理解性方面所获得的结果缺乏稳健性 - 在缩放，旋转或变色的图像上匹配失败。
第三种方法既快速又健壮，但可能最难实施。
关键点匹配
比挑选100个随机点更好的是挑选100个重要点。 图像的某些部分比其他部分具有更多信息（特别是在边缘和角落处），这些是您希望用于智能图像匹配的部分。 谷歌“关键点提取”和“关键点匹配”，你会发现不少关于这个问题的学术论文。 目前，SIFT关键点可以说是最受欢迎的，因为它们可以在不同尺度，旋转和照明条件下匹配图像。 一些SIFT实现可以在这里找到。
关键点匹配的一个缺点是无用实现的运行时间：O（n ^ 2m），其中n是每个图像中关键点的数量，m是数据库中图像的数量。 一些聪明的算法可能会更快地找到最接近的匹配，例如四叉树或二进制空间分区。
替代解决方案：直方图法
另一个不太强大但可能更快的解决方案是为每个图像构建特征直方图，并选择最接近输入图像直方图的直方图的图像。 我将它作为一个本科生来实现，我们使用了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|
对于绿色直方图中的每个桶，然后重复其他直方图，然后总结所有结果。 结果越小，匹配越好。 对数据库中的所有图像重复，最小结果的匹配胜出。 你可能想要有一个门槛，高于该门槛算法的结论是没有找到匹配。
第三选择 - 关键点+决策树
第三种方法可能比其他两种方法更快使用语义森林（PDF）。 这包括提取简单的关键点并使用集合决策树对图像进行分类。 这比简单的SIFT关键点匹配更快，因为它避免了昂贵的匹配过程，并且关键点比SIFT简单得多，因此关键点提取速度更快。 但是，它保留了SIFT方法对旋转，缩放和光照的不变性，这是直方图方法缺少的一个重要特征。
更新 ：
我的错误 - Semantic Texton Forests论文不是专门关于图像匹配，而是区域标签。 匹配的原始文件是这一个：使用随机树的关键点识别。 此外，下面的文章继续发展的想法和代表最先进的艺术（2010年）：
我知道的最好的方法是使用感知哈希。 似乎有一个很好的开源实现这样的散列可在：
http://phash.org/
主要思想是通过识别原始图像文件中的显着特征并散列这些特征的紧凑表示（而不是直接对图像数据进行散列处理），将每幅图像缩减为小哈希码或“指纹”。 这意味着误报率会比简单的方法大大降低，例如将图像缩小为微小指纹大小的图像并比较指纹。
phash提供了多种类型的散列，可用于图像，音频或视频。
这篇文章是我的解决方案的起点，在这里有很多好主意，所以我尽管我会分享我的结果。 主要见解是我发现了一种通过利用phash速度来解决基于关键点的图像匹配缓慢的方法。
对于通用解决方案，最好采用多种策略。 每种算法最适合于某些类型的图像转换，您可以利用它。
顶部是最快的算法; 底部最慢（尽管更准确）。 如果在更快的级别找到一个好的匹配，你可以跳过慢的。
Phash的成绩非常好。 精确度对于重新缩放的图像是很好的。 这对于（感知）修改的图像（裁剪，旋转，镜像等）是不好的。 为了处理哈希速度，我们必须使用磁盘缓存/数据库来维护haystack的哈希值。
关于phash的真正好处在于，一旦建立了散列数据库（对于我来说大约为1000张图像/秒），搜索就会非常快速，尤其是当您可以将整个散列数据库保存在内存中时。 这是相当实用的，因为散列只有8个字节。
例如，如果您有一百万张图像，则需要一个包含一百万个64位散列值（8 MB）的数组。 在某些CPU上，这适合L2 / L3缓存！ 在实际使用中，我看到一个corei7的速度超过1千兆/秒，这只是CPU的内存带宽问题。 一个10亿图像数据库在64位CPU上是实用的（需要8GB RAM），搜索不会超过1秒！
对于修改/裁剪的图像，它看起来像SIFT这样的变换不变特征/关键点检测器是要走的路。 SIFT将产生检测作物/旋转/镜像等的良好关键点。然而，描述符比较与phash使用的汉明距离相比非常慢。 这是一个主要限制。 由于最大IxJxK描述符比较来查找一幅图像（I = num haystack图像，J =每个干草堆图像的目标关键点，K =每个针图像的目标关键点），因此需要做大量的比较。
为了解决速度问题，我尝试在每个找到的关键点周围使用phash，使用特征尺寸/半径来确定子矩形。 使这项工作顺利进行的诀窍是增大/缩小半径以生成不同的子矩形（在针图像上）。 通常情况下，第一级（无标度）匹配，但通常需要多一些。 我并不是100％确定它为什么可以工作，但我可以想象它会启用太小的功能以使phash无法正常工作（phash将图像缩小到32x32）。
另一个问题是SIFT不会以最佳方式分配关键点。 如果图像的一部分具有很多边缘，则关键点将聚集在那里，而您将不会在另一个区域获取任何图像。 我在OpenCV中使用GridAdaptedFeatureDetector来改进分配。 不知道什么网格大小是最好的，我正在使用一个小网格（1x3或3x1取决于图像的方向）。
您可能希望在特征检测之前将所有干草堆图像（和针）缩放到较小的尺寸（沿最大尺寸使用210px）。 这将减少图像中的噪声（对于计算机视觉算法总是一个问题），也会将检测器集中在更突出的特征上。
对于人物图像，您可以尝试人脸检测并使用它来确定要缩放的图像大小和网格大小（例如，最大的人脸缩放为100px）。 特征检测器考虑多个比例级别（使用金字塔），但是它会使用多少级别（当然这是可调的）。
关键点检测器在返回的功能数量少于您想要的功能数量时可能效果最佳。 例如，如果你要求400和300回来，那很好。 如果你每次获得400回，可能有一些不错的功能不得不被忽略。
针图像可以具有比干草堆图像更少的关键点，并且仍然获得良好的结果。 增加更多并不一定会让你获得巨大收益，例如J = 400和K = 40时，我的命中率大约为92％。 随着J = 400和K = 400，命中率仅上升到96％。
我们可以利用海明函数的极端速度来解决缩放，旋转，镜像等问题。可以使用多遍技术。 在每次迭代中，转换子矩形，重新散列，然后再次运行搜索功能。
链接地址: http://www.djcxy.com/p/58529.html上一篇: fast algorithm
下一篇: How do I do a case