algorithm - 查找两个图像之间的图像子集

Question

我正在研究一种处理基于硬件的位图动画的方法。作为输入，我有一个简单位图的图像序列(它不是视频，它更像是简单的形状，即使它们可能包含位图填充)。我正在制作这个动画的纹理图集(因此它可以用 GPU 快速渲染)，并且由于这个序列有时大部分静止不动，而一小部分正在动画，我需要一种算法可以找到两个图像之间的“公共(public)部分”，这样我就可以节省内存。

图像的大小可能不同(例如，如果对象正在增大或缩小)，因此我需要一种方法来检测两者之间最大的公共(public)区域。我看过this answer它部分解决了我的问题。不过，我想知道是否已经有适合我的情况的更好算法，特别是因为尺寸可能会有所不同，所以一张图片不一定包含在另一张图片中，但我需要找到两者之间的共同部分两个。

Answer 1

我看到的一个问题是一张图片可以以多种方式包含在另一张图片中，您如何确定正确的答案？

它必须是实时的吗？如果不是，那么您可以使用适应度函数进行简单的 O(n^4) 搜索。

适应度函数可以是图像之间的误差(它给出了 n^8 算法)。

更新: 不好意思分析错了。搜索是 n^2，适应度函数是 n^2，给出 n^4。

整个算法应该是这样的:

w1 = width of image 1
w2 = width of image 2
h1 = height of image 1
h2 = height of image 2

for x = -w1 to w1+w2
  for y = -h1 to h1+h2
    find max fitness(x,y)

fitness(xc,yc){
  m=0
  for each x where image 1 overlaps image 2 displaced by xc
    for each y where image 1 overlaps image 2 displaced by yc
      if (image1[x][y] == image2[x+xc][y+yc])
        m += 1
  return m
}

更新:修改适应度函数以找到重叠的数量，然后尝试找到最多的重叠。