7

1 と 0 の四角形で 1 または 0 の最大のブロックを見つけるためのブルートフォース (素朴な) ソリューションを考え出そうとしていO(n)ます。

1 1 0 1 0 1
1 0 0 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0

上記の長方形では、サイズ 6 の (行 2、列 2) から始まる長方形です。私はこれを考えていました..

各要素を調べてから、そこからすべての方向に繰り返してサイズを見つけます。

ブルートフォースですか？複雑さはどうなりますか？n であるすべての要素を調べていますが、すべての方向に反復しています。

この質問が 100 回聞かれたことは承知していますが、彼らは最適な解決策について語っています。私が探しているのは、ブルートフォース ソリューションとその複雑さですか?

4

3 に答える 3

3

あなたが説明したアルゴリズムは、次の C コードのように見えます。

//for each entry
for(int x = 0; x < width; ++x)
    for(int y = 0; y < height; ++y)
    {
        char lookFor = entries[x][y];
        int area = 0;
        for(int row = y; row < height; ++row)
        {
            if(entries[x, row] != lookFor)
                break;
            for(int col = x; col < width; ++col)
            {
                if(entries[col, row] != lookFor)
                    break;
                int currentArea = (col - x + 1) * (row - y + 1);
                if(currentArea > area)
                {
                    //save the current rect
                }
            }
        }
    }

4 つのネストされたループがあります。外側のループは、正確にn(nエントリの数で) 繰り返されます。内側のループは平均でwidth * f1とheight * f2回反復されます ( とf1はf2一定の割合で)。残りのアルゴリズムには一定の時間がかかり、問題のサイズには依存しません。

したがって、複雑さはO(n * f1 * width * f2 * height) = O(n^2)であり、これは本質的に「各エントリに移動し、そこから各エントリに再度アクセスする」ことを意味します。これは、すべてのエントリを実際にチェックする必要があるか、問題のサイズに応じて増加する一定の割合にすぎないかは関係ありません。

編集

上記の説明は、エントリがランダムに分散されておらず、フィールドが大きいほど均一な部分領域が大きくなる可能性が高いことを前提としています。これが当てはまらず、内部ループの平均反復回数がフィールド サイズにまったく依存しない場合 (たとえば、ランダムに分散されたエントリの場合)、結果として生じる時間計算量は次のようになります。O(n)

于 2013-10-26T18:21:15.817 に答える
0

追加のアイデアについては、「接続されたコンポーネント」アルゴリズムを調べてください。バイナリ値の 2 次元配列として提示したものは、バイナリの白黒画像のように見えます。重要な例外は、画像処理では通常、接続されたコンポーネント (0 または 1 の塊) が長方形以外の形状を持つことを許可することです。既存のマルチパスおよびシングルパス アルゴリズムの微調整は、簡単に実装できるはずです。

http://en.wikipedia.org/wiki/Connected-component_labeling

これは必要以上に一般的な解決策ですが、連結成分アルゴリズムを実行してすべての連結領域 (0 または 1、背景または前景) を見つけ、結果の成分 (別名ブロブ) をフィルター処理することもできます。また、フォアグラウンド コンポーネントについては、「8 接続性」よりも「4 接続性」を選択することをお勧めします。前者は、接続性が中心ピクセルの上下左右のピクセルでのみ許可されることを意味します。後者は、中央のピクセルを囲む 8 つのピクセルのいずれかに対して接続が許可されることを意味します。

少し離れたところで、非常に大きな 2D 配列の場合、最初に「画像ピラミッド」と呼ばれるものを作成することで検索スペースを削減するのに役立つ場合があります。これは、サイズが徐々に小さくなる配列のスタックを意味します。寸法 (必要に応じて入力)、1/4、1/8 など。低解像度の画像で検出可能な四角形は、非常に大きな画像 (またはビットの 2D 配列) で最大の四角形の候補として適しています。これは、検討しているケースに最適なソリューションではないかもしれませんが、スケーラブルです。当然のことながら、配列/画像をスケーリングするコストと、元の大きな画像内の候補矩形の比較的大きなリストを維持するコストを決定するには、ある程度の努力が必要です。

特に、任意の形状の接続されたコンポーネントではなく四角形を扱っているため、ランレングス エンコーディングも役立ちます。ランレングス エンコーディングは、各行をストレッチまたは 0 または 1 の「ランレングス」として表現します。この手法は、10 ～ 20 年前に連結要素アルゴリズムを高速化するために使用されましたが、今でも妥当なアプローチです。

とにかく、それはあなたの質問に対する最も直接的な答えではありませんが、少しでも役立つことを願っています.

于 2013-10-26T18:57:11.830 に答える