2つの画像の差のバウンディングボックスを見つけるか？

Question

私は2つのビットマップ画像を持っています。ここで、1はもう一方のわずかなバリエーションです。 ここでは、できるだけ早く変更領域のバウンディングボックスを計算したいと思います。 これを行うためのスマートなアルゴリズムはありますか、それともブルートフォース処理のケースですか？

編集： 画像はスクリーンキャプチャになります。私は "このボックスの外には何も変わっていない"のように、変更された領域の最小境界ボックスを探したい。

Answer 1

バウンディングボックスが1つだけ必要な場合は、少なくともイメージ間に違いがある場合は、「ブルートフォース」（すべてのピクセル、2 * w * h操作を常にチェックする）よりも優れています。 4つの異なる罫線から始まる4つの最初の異なる行/列のピクセルを探してください。擬似コード：上記

bounding_box_y1 = -1; 
loop y = 1..h { 
loop x = 1..w { 
    if image1(x,y) != image2(x,y) { 
    bounding_box_y1 = y 
    exit loops 
    } 
} 
} 

擬似コードは、それがbounding_box_y1を返し、異なる画素が見つかるまで、一番上の行から開始し、画像列を通過します。さらに3つのループを追加してください（行は下部=>bounding_box_y2、左端の列は>bounding_box_x1、右端の列は>bounding_box_x2）、境界ボックスの座標が表示されます。

このアルゴリズムは、まだ（この場合には、bounding_box_y1は-1に滞在し、あなたは追加の3つのループをスキップすることができますことに注意してください）同じ画像に対して2つの* Wの* hの操作を行いますが、画像に違いがある場合もはるかに高速になります（最良の場合、4つのコーナーピクセルのみをチェックする）。

EDIT：あなたの質問を編集した後、私は別のアプローチのアイデアを持っていました。イメージを他のイメージと数回比較している場合、追加のチェックサム情報を保存できます。 16x16ピクセル領域のチェックサムを格納するには追加の記憶領域が必要ですが、ピクセルではなくチェックサムを比較する方がずっと速く、ブーディングボックスの見積もりが得られます。どちらの場合も、特に最悪のシナリオでは、これは上記のアプローチよりもはるかに高速です。しかし、それはあなたの設定に依存し、 "速度のためのサイズ"のトレードオフです。