2つのイメージ間のイメージサブセットの検索

Question

ハードウェアベースのビットマップアニメーションを処理する方法を検討中です。入力として、私は単純なビットマップの画像シーケンスを持っています（ビデオではなく、ビットマップ塗りつぶしを含んでいてもシンプルなシェイプのようなものです）。私はこのアニメーションのテクスチャアトラスを作っています（GPUですばやくレンダリングできるようにしています）。このシーケンスではほとんどの部分が静止していることがありますが、その一部はアニメーション化されています。 2つの画像間の「共通部分」なので、メモリを節約できます。

イメージのサイズが同じでない場合（オブジェクトが大きくなったり小さくなったりする場合など）、2つの間の最大の共通領域を検出する方法が必要です。私はthis answerを見て、それは私の問題を部分的に解決します。私は知っているが、私の場合のためのより良いアルゴリズムは、特にサイズが異なることができますので、1つの画像は必ずしも他の内に含まれていないので、私は知ってほしいが、私は二。

Answer 1

私が見ている1つの問題は、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 
} 

UPDATE：重複の数を見つけ、その後、ほとんどのオーバーラップを見つけようとするように修正適応度関数

全体のアルゴリズムは次のようになります。