algorithm - 画像内の最大の凸状の黒い領域を見つける

Question

私はこれが小さな切り抜きである画像を持っています:

ご覧のとおり、黒い背景に白いピクセルです。これらのピクセル (または点) の間に想像上の線を描くことができます。これらの線で領域を囲むことができます。

この画像で白いピクセルを含まない最大の凸状の黒い領域を見つけるにはどうすればよいですか?

これは、最大の凸状の黒い領域によって私が意味することの小さな手描きの例です:

PS: 画像はノイズではなく、10000000 未満の素数を水平方向に並べたものです。

Answer 1

最大の凸領域を見つけようとするのは難しい作業です。最大面積の長方形を見つけるだけでいいのではないですか? この問題ははるかに簡単で、O(n) - ピクセル数の線形時間で解決できます。アルゴリズムは次のとおりです。

フリー（白）ピクセルの最大の長方形を見つけたいとします（申し訳ありませんが、さまざまな色の画像があります-白は黒に相当し、グレーは白に相当します）。

これは、2 パス線形O(n)時間アルゴリズム (n はピクセル数)によって非常に効率的に行うことができます。

1) 最初のパスでは、下から上に列ごとに移動し、各ピクセルについて、このピクセルまでに使用可能な連続したピクセルの数を示します。

まで繰り返します:

2) 2 番目のパスで、行ごとに移動し、読み取りますcurrent_number。各数値kについて、連続した数値の合計を追跡します>= k(つまり、高さの潜在的な四角形k)。の合計 (潜在的な長方形) を閉じてk > current_number、合計 (~ 長方形の面積) が現在の最大値よりも大きいかどうかを調べます。そうであれば、最大値を更新します。各行の終わりで、開いている可能性のある四角形をすべて閉じます (すべての についてk)。

このようにして、すべての最大長方形を取得します。もちろん、これは最大凸領域と同じではありませんが、最大凸領域をどこで探すべきかについてのヒント (ヒューリスティックス) が得られるでしょう。

Answer 2

正しいポリタイム アルゴリズムをスケッチします。間違いなくデータ構造を改善する必要がありますが、非常に大きなデータセットを検索するには、特にこの問題をよりよく理解する必要があると思います (または、おそらく、ポリゴン）。

メイン ループは、最大の凸多角形の最低点 p を推測し (左端の点を優先して同点を打ち破る)、次に (qy > py) || (qy == py && qx > px)。

動的プログラムは、 Graham のスキャンと同じ幾何学的事実に依存しています。一般性を失うことなく p = (0, 0) と仮定し、点 q を x 軸と反時計回りの角度の順に並べ替えます (内積の符号を考慮して 2 つの点を比較します)。ソートされた点を q ₁ , …, q _nとする。q ₀ = p とする。0 ≤ i < j ≤ n ごとに、点 q _{0上の最大凸多角形、q 1}、…、q _i-1、q _i、および q _jのサブセットを計算します。

i = 0 の基本ケースは簡単です。なぜなら、唯一の「多角形」は面積がゼロのセグメント q ₀ q _{j だから}です。帰納的に、(i, j) エントリを計算するために、すべての 0 ≤ k ≤ i について、(k, i) ポリゴンを (i, j) で拡張してみます。いつこれを行うことができますか？まず、三角形 q ₀ q _i q _jに他の点が含まれてはなりません。もう 1 つの条件は、角度 q _k q _i q _jが右折でない方がよいということです (もう一度、適切な内積の符号を確認してください)。

最後に、見つかった最大のポリゴンを返します。なぜこれが機能するのですか？凸多角形が動的プログラムに必要な最適な部分構造を持っていること、およびグラハムの凸性の特性を満たす多角形をプログラムが正確に考慮していることを証明することは難しくありません。

Answer 3

ピクセルを頂点として扱い、ポイントセットのDelaunay 三角形分割を実行してみてください。次に、凹面形状を作成せず、内部頂点を持たない、接続された三角形の最大のセットを見つける必要があります。

Answer 4

私はこの問題を解決するためのアプローチを考えました：

すべてのポイントのセットから、すべての可能な3ポイントサブセットを生成します。これは、スペース内のすべての三角形のセットです。このセットから、別のポイントを含むすべての三角形を削除すると、すべての空の三角形のセットが取得されます。

次に、空の三角形ごとに、最大サイズに拡大します。つまり、長方形の外側のすべてのポイントについて、ポリゴンの最も近い2つのポイントの間に挿入し、この新しい三角形内にポイントがあるかどうかを確認します。そうでない場合は、そのポイントとそれが追加する領域を覚えています。新しいポイントごとに、追加された領域を最大化するポイントを追加します。これ以上ポイントを追加できない場合は、最大の凸多角形が作成されています。各ポリゴンの面積を記録し、面積が最大のポリゴンを覚えておいてください。

このアルゴリズムのパフォーマンスにとって重要なのは、a）ポイントが三角形内にあるかどうか、およびb）特定のポイントを追加した後もポリゴンが凸状のままであるかどうかを判断する能力です。

b）をa）の問題に減らすことができると思います。そうすれば、点が三角形の中にあるかどうかを判断するための最も効率的な方法を見つけるだけで済みます。サーチスペースの縮小は、次のように実現できます。三角形を取り、すべてのエッジを両方向で無限の長さに増やします。これにより、三角形の外側の領域が6つのサブ領域に分割されます。私たちにとって良いのは、これらのサブ領域のうち、凸性の制約に準拠するポイントを含めることができるのは3つだけであるということです。したがって、テストする各ポイントについて、それが凸状に拡大するサブ領域にあるかどうかを判断する必要があります。これも、特定の三角形にあるかどうかの問題です。

多角形が進化して円の形に近づくにつれて、多角形全体がますます小さな領域を持ち、それでも凸状の拡張が可能になります。凹面領域に一度入ったポイントは、再び凸面拡張領域の一部になることはないため、拡張のために考慮する必要のあるポイントの数をすばやく減らすことができます。さらに、拡張のためにポイントをテストしている間、可能なポイントのリストをさらに減らすことができます。ポイントがfalseでテストされた場合、それは別のポイントの凹型サブ領域にあり、したがって、テストされたポイントの凹型サブ領域内の他のすべてのポイントは、内側のポイントの凹型サブ領域にもあるため、考慮する必要はありません。あなたは非常に迅速に可能なポイントのリストに切り詰めることができるはずです。

もちろん、空の三角形ごとにこれを行う必要があります。

残念ながら、常に最大の新しい領域を追加することによって、ポリゴンが可能な最大のポリゴンになることを保証することはできません。