algorithm - 2D ブロブに四角形をベスト フィットする

Question

バイナリブロブ (画像を参照) があり、既知の幅と高さの四角形をその上に合わせたいと考えています。

最適なフィッティング長方形、つまり、前景ピクセルの最大量が内側にあり、背景ピクセルの最大量が外側にある長方形を見つけるにはどうすればよいですか?

(これはベスト フィットの私の暫定的な定義であり、他の提案も受け付けています)

既知のサイズの長方形を探していますが、任意のサイズの解決策があれば、それも素晴らしいでしょう。

ブロブの例:

これらの長方形を見つけたい：

これまでの私のアイデアが含まれています

• 最小の囲み長方形から始めます。しかし、それはこれらのブロブには適していません
• 囲まれた長方形の最大値。同じ問題に加えて、そのためのアルゴリズムがありません
• ハフ変換で長方形の辺を見つけます。そのためにはデータにノイズが多すぎます。

私の基準に適合する同じブロブに対して複数の長方形が存在する可能性があることを認識しています。理想的には、すべての候補を見つけることができるアルゴリズムが必要です (それはおそらく難しいので、候補を 1 つだけ見つける方法があれば幸いです)。 :

私は主に opencv と cvBlobLib を使用してデータを処理していますが、一般的な解決策についてはオープンです。

Answer 1

進化論的アプローチに基づいた、同様の主題 (RGB 平面を覆う円) に関する論文を見たことがあります。

• 目的関数は明確に定義されていました (四角形はいくつありますか? 大きさは? それらは重なり合うことができますか? 小さい四角形または重なっている四角形にはペナルティを科したいと思うでしょう)。
• k-means アルゴリズムを実行してデータを前処理することから始めることができます。つまり、正方形の潜在的な中心点を見つけることができます。

私が思い出したように、SGA、CGA、eCGA が比較され (CGA は初期の k-means ベースのカバーで開始されました)、SGA が他のものよりも優れていました。それらは画像ごとに実行されました。約 30 人の個人と 20 世代があり、実行時間は約 2 分でした。

SGA に関しては、クロスオーバー オペレーターは一度に 2 つの親を取得し、両方の親からクローズ/最も類似した円をペアにします。次に、各ペアに対して、2 つの円の半径の間の半径を持つ子円をその間のどこかに描画します。(ただし、親の値の間の値を正確に取得しないことをお勧めしますが、範囲外の +/- 15% を許可します。これにより、母集団が時期尚早に収束するのを防ぐことができます)。

長方形の場合は、アプローチを少し変更する必要があります。各長方形はタプル(x、y、幅、高さ、回転)であり、xとyは中心の座標です。