与えられた1000x1000の配列にはさまざまな長方形があります。では<Figure 1>、黄色のセルとして表示されるシリアル「1」は長方形のパターンです。の長方形の最小サイズは<Figure 1>、緑色のセルとして表示される3x3です。
長方形の内側に「0」が少なくとも1つ必要です。
しかし、この配列には、閉じていない形状や直線パターンも存在します。
（配列の初期値は「0」であり、パターンは一連の「1」で表されます。これらは重複したり、互いに含まれたりすることはありません。）
閉じていない形状または直線を除いて、配列内の完全なregtangleを見つけるための効率的なアルゴリズムは何でしょうか？たとえば、上の図では、完全な長方形の数は3です。
これは非常に簡単です。n正方形がある場合は、長方形を数えることができますO(n)。
仮定:
入力と同じ大きさの追加のメモリが必要になります。visitedこれを呼び出して、0 で初期化しましょう。
最初にヘルパー関数を作成しましょう。
is_rectangle(square s)
from s, go right while you see 1s and visited is 0
mark them as 1 in visited
if less than 3 steps
return 0
then, go down while you see 1s and visited is 0
mark them as 1 in visited
if less than 3 steps
return 0
then, go left while you see 1s and visited is 0
mark them as 1 in visited
if less than 3 steps
return 0
then, go up while you see 1s and visited is 0
mark them as 1 in visited
if then one above is not s
return 0
return 1
この関数は、基本的には 1 を上下左右の方向にトレースし、条件 (長さが 3 以上で開始位置に到達) が満たされているかどうかをチェックします。また、訪問した正方形をマークします。
この関数について注意すべき重要な点は、最初の正方形が左上隅にある場合にのみ正しく機能することです。
さて、問題の解決策は簡単です:
num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
for c in columns
if visitied[r][c] or image[r][c] == 0
continue
num_rectangles += is_rectangle(<r,c>)
return num_rectangles
アルゴリズムの実行方法は次のとおりです。
1. 悪い四角形の失敗した (そしてマークされた) 部分
2. 四角形を見つけて (マークを付けて) ます。
3. (垂直線の) 1 つの正方形で失敗した
4. (垂直線の) 1 つの正方形で失敗した
5. (垂直線の) 1 つの正方形で失敗した
6. 多くの同様の手順の後、次の長方形が見つかりました。
7. そして次の長方形
8. アルゴリズム終了
次の O(n) アルゴリズムは、0/1 値の任意の 2D マトリックスで機能します(つまり、任意の非長方形の開いた/閉じた形状と同様に、交差/重複する長方形が許可されます)。ここで使用している長方形の定義は、「内部は完全に 0 のセルで構成されている」です (つまり、ある長方形に別の長方形が完全に含まれている場合、内側の長方形のみが検出されます。含まれている長方形も考慮する必要がある場合は、見つかった各長方形を削除して、アルゴリズムを再起動できます)。これは、各 0 セルが最大で 1 つの 1-rectangleの内部に存在できるという観察に基づいています。
x = 0 が一番左の位置で、y = 0 が一番上の位置であるという規則を使用します。
配列に長方形しか持てない場合、それはバイナリ イメージの計算に関する古典的な問題と同じです。つまり、接続されたコンポーネントに標準のアルゴリズムを適用するだけです。0 の連結要素のみにラベルを付け、それらを数えます。
たとえば、http://en.wikipedia.org/wiki/Connected-component_labelingを参照してください。このタイプのアルゴリズムは画像では非常に単純ですが、ある程度のメモリを必要とします (short または int 型の入力配列と同じサイズ)。接続性に注意してください。4 接続性を選択すると、一部の角が欠けていても、囲まれた四角形がカウントされます。ただし、アルゴリズムは 8 接続性よりも単純です。
より複雑な囲まれた形状を作成できる場合は、後処理を追加するだけです。接続されたコンポーネントごとに、コンポーネントの境界ボックス内のピクセル数を数えます (2 つの数値が等しい場合は、長方形になります)。
ちょっと考えてみた。私はこの方法を思いつきました：
1) エッジの周りのすべてのゼロを削除します - それらの値を 2 に変更します
2) 2 の周りの行列を塗りつぶします
これにより、凸性をテストできるゼロの島だけが残ります。したがって、各島について：
3) X と Y で 0 の値の範囲を探します - 潜在的な内側の四角形を与えます
4) 内側の四角形に 1 が含まれる場合、または外側の四角形に 0 が含まれる場合、この島は凸状ではない (したがって四角形ではない) ため、フラッドはこの島を 2 で埋めます。
優れたフラッド フィル アルゴリズム (私のものとは異なります) を見つけることができると仮定すると、これは検索スペースをすばやく削減するのに効率的であるはずです。
それでは、コードについて (申し訳ありませんが C シャープです):
using System;
using System.Collections.Generic;
namespace Test
{
class MainClass
{
static private int [,] matrix = new int[,] {
{0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
{0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
{0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
{0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
{0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,1,0,0,1,1,1,0,1,1,0},
{0,0,1,1,1,1,0,0,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1,1,0,0,0,0}
};
static private int width = matrix.GetLength(0);
static private int height = matrix.GetLength(1);
private const int DEAD = 2;
private const int RECT = 3;
public static void Main (string[] args)
{
//width = matrix.GetLength(0);
//height = matrix.GetLength(1);
PrintMatrix ();
EliminateFromEdges (DEAD);
PrintMatrix ();
FloodFill (DEAD); // very inefficient - find a better floodfill algorithm
PrintMatrix ();
// test each island of zeros for convexness
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (matrix[i,j] == 0)
{
if (TestIsland(i,j) == false)
{
// eliminate this island as it is not convex
matrix[i,j] = DEAD;
FloodFill(DEAD);
PrintMatrix ();
}
else
{
// flag this rectangle as such
matrix[i,j] = RECT;
FloodFill(RECT);
PrintMatrix ();
}
}
}
}
// We're done, anything flagged as RECT can be expanded to yield the rectangles
PrintMatrix ();
}
// flag any zero at edge of matrix as 'dead'
static private void EliminateFromEdges(int value)
{
for (int i = 0; i < width; i++)
{
if (matrix [i, 0] == 0)
{
matrix [i, 0] = value;
}
if (matrix [i, height - 1] == 0)
{
matrix [i, height - 1] = value;
}
}
for (int j = 1; j < height - 1; j++)
{
if (matrix [0, j] == 0)
{
matrix [0, j] = value;
}
if (matrix [width - 1, j] == 0)
{
matrix [width - 1, j] = value;
}
}
}
// propagte a value to neighbouring cells
static private void FloodFill (int value)
{
bool change_made = true; // set to true to start things off
while (change_made) {
change_made = false;
for (int i = 1; i < width - 1; i++) {
for (int j = 1; j < height - 1; j++) {
if ((matrix [i, j] == 0) &&
((matrix [i - 1, j] == value) ||
(matrix [i + 1, j] == value) ||
(matrix [i, j - 1] == value) ||
(matrix [i, j + 1] == value))) {
matrix [i, j] = value;
change_made = true;
}
}
}
}
}
static private bool TestIsland (int x, int y)
{
// find convex extend of island
int x2 = x;
int y2 = y;
while (matrix[++x2, y] == 0);
x2--;
while (matrix[x,++y2] == 0);
y2--;
// check inner cells (want all zeroes)
for (int i = x; i <= x2; i++)
{
for (int j = y; j <= y2; j++)
{
if (matrix[i,y] != 0)
{
return false;
}
}
}
// check surrounding cells (want all ones)
x--; y--;
x2++; y2++;
for (int i = x; i <= x2; i++)
{
if ((matrix[i,y] != 1) || (matrix[i,y2] != 1))
{
return false;
}
}
for (int j = y + 1; j <= y2 - 1; j++)
{
if ((matrix[x,j] != 1) || (matrix[x2,j] != 1))
{
return false;
}
}
return true;
}
// for debug purposes
static private void PrintMatrix ()
{
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
switch(matrix[i,j])
{
case DEAD:
Console.Write("-");
break;
case RECT:
Console.Write("+");
break;
default:
Console.Write(matrix[i,j]);
break;
}
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
このコードの出力
000000001111000
011111101001010
010000101001010
010000101001010
010000101000010
010000101000010
011111101001010
000000001111000
001111000000000
001001001110110
001111001010000
000000001110000
--------1111---
-1111110100101-
-1000010100101-
-1000010100101-
-1000010100001-
-1000010100001-
-1111110100101-
-0000000111100-
-0111100000000-
-0100100111011-
-0111100101000-
--------111----
--------1111---
-111111-1--1-1-
-100001-1--1-1-
-100001-1--1-1-
-100001-1----1-
-100001-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----
これは私が思うことですが、かなりリソース効率が悪い可能性があります。それについては知りません。
1秒が見つからない限り、列に沿ってトラバースします。boolean、結果は の形式になります。（すべての操作100..001を実行できると仮定します）boolean1の s が見つかった場合は、四角形が見つかりました。