在较大的图像中查找已知的子图像

Question

有没有人知道在更大的图像中定位已知图像的算法(或搜索术语/描述)？

例如

我有一个包含各种按钮和区域(目标)的单个桌面窗口的图像.我还有代码捕获当前桌面的屏幕截图.我想要一个算法,它可以帮助我在更大的桌面图像中找到目标图像(窗口所在的x和y坐标是什么).目标图像可能位于较大图像中的任何位置,并且可能不是100%完全相同(非常相似但不完全可能是OS显示差异的b/c)

有谁知道这样的算法或算法类？

我发现了各种图像分割和计算机视觉算法,但它们似乎适用于区域的"模糊"分类,而不是将特定图像定位在另一个区域内.

**我的目标是创建一个框架,给定一些种子目标图像,可以在桌面上找到"外观",找到目标区域并"观察"它的变化.**

Answer 1

看看我写的论文:http://werner.yellowcouch.org/Papers/subimg/index.html.它非常详细,似乎是唯一一篇讨论如何将傅立叶变换应用于子图像发现问题的文章.

简而言之,如果你想使用傅立叶变换,可以应用下面的公式:当图像A在dx上移位时,图像A和图像B之间的相关性,dy在以下矩阵中给出:C = ifft(fft(A) ×共轭(fft(B)).因此,图像C中具有最高值的位置具有最高的相关性,并且该位置反映dx,dy.

该结果适用于相对较大的子图像.对于较小的图像,如文章中所解释的那样,还需要做更多的工作.然而,这种傅里叶变换非常快.它导致大约3*sx sy log_2(sx*sy)+ 3*sx*sy运算.

Answer 2

您说您的图像可能不完全相同，但又说您不想要“模糊”算法。我不确定这些是否兼容。不过，总的来说，我认为您想查看图像配准算法。有一个名为ITK 的开源 C++ 包可能会提供一些提示。此外ImageJ的是一种流行的开源Java包。如果你四处看看，这两者至少都有一些可用的注册功能。

Answer 3

这是您想要使用的代码框架:

// look for all (x,y) positions where target appears in desktop
List<Loc> findMatches(Image desktop, Image target, float threshold) {
  List<Loc> locs;
  for (int y=0; y<desktop.height()-target.height(); y++) {
      for (int x=0; x<desktop.width()-target.width(); x++) {
          if (imageDistance(desktop, x, y, target) < threshold) {
              locs.append(Loc(x,y));
          }
      }
   }
   return locs;
}

// computes the root mean squared error between a rectangular window in 
// bigImg and target.
float imageDistance(Image bigImg, int bx, int by, Image target) {
    float dist = 0.0;
    for (int y=0; y<target.height(); y++) {
        for (int x=0; x<target.width(); x++) {
            // assume RGB images...
            for (int colorChannel=0; colorChannel<3; colorChannel++) {
                dist += Math.pow(target.getPixel(x,y) - bigImg.getPixel(bx+x,by+y), 2);
            }
         }
    }
    return Math.sqrt(dist) / target.width() / target.height();
}

您可以考虑其他图像距离(请参阅类似的问题).对于您的应用程序,RMS错误可能是一个不错的选择.

可能有各种Java库可以有效地为您计算这个距离.