algorithm 高速 接続されたコンポーネントのラベリング




ラベリング 高速 アルゴリズム (4)

私は最初にあなたにコードを与えて、少し説明します:

// direction vectors
const int dx[] = {+1, 0, -1, 0};
const int dy[] = {0, +1, 0, -1};

// matrix dimensions
int row_count;
int col_count;

// the input matrix
int m[MAX][MAX];

// the labels, 0 means unlabeled
int label[MAX][MAX];

void dfs(int x, int y, int current_label) {
  if (x < 0 || x == row_count) return; // out of bounds
  if (y < 0 || y == col_count) return; // out of bounds
  if (label[x][y] || !m[x][y]) return; // already labeled or not marked with 1 in m

  // mark the current cell
  label[x][y] = current_label;

  // recursively mark the neighbors
  for (int direction = 0; direction < 4; ++direction)
    dfs(x + dx[direction], y + dy[direction], current_label);
}

void find_components() {
  int component = 0;
  for (int i = 0; i < row_count; ++i) 
    for (int j = 0; j < col_count; ++j) 
      if (!label[i][j] && m[i][j]) dfs(i, j, ++component);
}

これはこの問題を解決する一般的な方法です。

方向ベクトルは、(4つの方向のそれぞれの)隣接するセルを見つけるのにちょうど良い方法です。

dfs関数は、グリッドの深さ優先探索を実行します。 これは単に、開始細胞から到達可能なすべての細胞を訪れることを意味します。 各セルはcurrent_labelでマークされます

find_components関数は、グリッドのすべてのセルを通過し、ラベルが付いていないセル(1でマークされている)が見つかると、コンポーネントのラベル付けを開始します。

これは、スタックを使用して繰り返し実行することもできます。 スタックをキューに置き換えると、 bfsまたはbreadth-first-searchが取得されます

私は数日前に同様の質問をしましたが、私はまだ問題を解決する効率的な方法を見つけていません。 私は単純なコンソールゲームを開発しています。私は次のような2D配列を持っています:

1,0,0,0,1
1,1,0,1,1
0,1,0,0,1
1,1,1,1,0
0,0,0,1,0

私は近隣の1(4方向接続性)からなるすべての領域を見つけることを試みています。 したがって、この例では、次の2つの領域があります。

1
1,1
  1
1,1,1,1
      1

と:

       1
     1,1
       1

私が取り組んできたアルゴリズムは、セルの隣人のすべての隣人を見つけ、この種の行列で完璧に動作します。 しかし、より大きい配列(90 * 90など)を使用すると、プログラムが非常に遅くなり、使用される巨大な配列がスタックオーバーフローを引き起こすことがあります。

私の他の質問の一人は、私の問題の効率的な解決策として、接続コンポーネントのラベル付けについて教えてくれました。

誰かがこのアルゴリズムを使っているC ++コードを私に見せてもらえますか?私はこのディスジョイントセットのデータ構造物と実際にどのように動作するのかちょっと混乱しています。

あなたの助けと時間をいただきありがとうございます。


非常に便利なドキュメント=> https://docs.google.com/file/d/0B8gQ5d6E54ZDM204VFVxMkNtYjg/edit

Javaアプリケーション - オープンソース - 画像結合コンポーネントからオブジェクトを抽出する=> https://drive.google.com/file/d/0B8gQ5d6E54ZDTVdsWE1ic2lpaHM/edit?usp=sharing

    import java.util.ArrayList;

public class cclabeling

{

 int neighbourindex;ArrayList<Integer> Temp;

 ArrayList<ArrayList<Integer>> cc=new ArrayList<>();

 public int[][][] cclabel(boolean[] Main,int w){

 /* this method return array of arrays "xycc" each array contains 

 the x,y coordinates of pixels of one connected component 

 – Main => binary array of image 

 – w => width of image */

long start=System.nanoTime();

int len=Main.length;int id=0;

int[] dir={-w-1,-w,-w+1,-1,+1,+w-1,+w,+w+1};

for(int i=0;i<len;i+=1){

if(Main[i]){

Temp=new ArrayList<>();

Temp.add(i);

for(int x=0;x<Temp.size();x+=1){

id=Temp.get(x);

for(int u=0;u<8;u+=1){

neighbourindex=id+dir[u];

 if(Main[neighbourindex]){ 

 Temp.add(neighbourindex);

 Main[neighbourindex]=false;

 }

 }

Main[id]=false;

}

cc.add(Temp);

    }

}

int[][][] xycc=new int[cc.size()][][];

int x;int y;

for(int i=0;i<cc.size();i+=1){

 xycc[i]=new int[cc.get(i).size()][2];



 for(int v=0;v<cc.get(i).size();v+=1){

 y=Math.round(cc.get(i).get(v)/w);

 x=cc.get(i).get(v)-y*w;

 xycc[i][v][0]=x;

 xycc[i][v][1]=y;

 }



}

long end=System.nanoTime();

long time=end-start;

System.out.println("Connected Component Labeling Time =>"+time/1000000+" milliseconds");

System.out.println("Number Of Shapes => "+xycc.length);

 return xycc;



 }

}

以下に、接続コンポーネントのラベル付けのサンプルコードを示します。 コードはJAVAで書かれています

package addressextraction;

public class ConnectedComponentLabelling {

    int[] dx={+1, 0, -1, 0};
    int[] dy={0, +1, 0, -1};
    int row_count=0;
    int col_count=0;
    int[][] m;
    int[][] label;

    public ConnectedComponentLabelling(int row_count,int col_count) {
        this.row_count=row_count;
        this.col_count=col_count;
        m=new int[row_count][col_count];
        label=new int[row_count][col_count];
    }

    void dfs(int x, int y, int current_label) {
          if (x < 0 || x == row_count) return; // out of bounds
          if (y < 0 || y == col_count) return; // out of bounds
          if (label[x][y]!=0 || m[x][y]!=1) return; // already labeled or not marked with 1 in m

          // mark the current cell
          label[x][y] = current_label;
         // System.out.println("****************************");

          // recursively mark the neighbors
          int direction = 0;
          for (direction = 0; direction < 4; ++direction)
            dfs(x + dx[direction], y + dy[direction], current_label);
        }

    void find_components() {
          int component = 0;
          for (int i = 0; i < row_count; ++i) 
            for (int j = 0; j < col_count; ++j) 
              if (label[i][j]==0 && m[i][j]==1) dfs(i, j, ++component);
        }


    public static void main(String[] args) {
        ConnectedComponentLabelling l=new ConnectedComponentLabelling(4,4);
        l.m[0][0]=0;
        l.m[0][1]=0;
        l.m[0][2]=0;
        l.m[0][3]=0;

        l.m[1][0]=0;
        l.m[1][1]=1;
        l.m[1][2]=0;
        l.m[1][3]=0;

        l.m[2][0]=0;
        l.m[2][1]=0;
        l.m[2][2]=0;
        l.m[2][3]=0;

        l.m[3][0]=0;
        l.m[3][1]=1;
        l.m[3][2]=0;
        l.m[3][3]=0;

        l.find_components();

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(l.label[i][j]);
            }
            System.out.println("");

        }


    }

}

これはunion findで解決できます (ただし、DFSはもう1つの答えに示されていますが、おそらく少し単純です)。

このデータ構造の背後にある基本的な考え方は、同じコンポーネント内の要素を繰り返しマージすることです。 これは、各コンポーネントをツリーとして表現することで実行されます(ノードは自分の親を追跡して、別の方法ではなく)。ルートノードに移動してノードをマージすることで、2つの要素が同じコンポーネント内にあるかどうかを確認できます単純に一方のルートをもう一方のルートの親にすることによって実行されます。

これを示す短いコードサンプル:

const int w = 5, h = 5;
int input[w][h] =  {{1,0,0,0,1},
                    {1,1,0,1,1},
                    {0,1,0,0,1},
                    {1,1,1,1,0},
                    {0,0,0,1,0}};
int component[w*h];

void doUnion(int a, int b)
{
    // get the root component of a and b, and set the one's parent to the other
    while (component[a] != a)
        a = component[a];
    while (component[b] != b)
        b = component[b];
    component[b] = a;
}

void unionCoords(int x, int y, int x2, int y2)
{
    if (y2 < h && x2 < w && input[x][y] && input[x2][y2])
        doUnion(x*h + y, x2*h + y2);
}

int main()
{
    for (int i = 0; i < w*h; i++)
        component[i] = i;
    for (int x = 0; x < w; x++)
    for (int y = 0; y < h; y++)
    {
        unionCoords(x, y, x+1, y);
        unionCoords(x, y, x, y+1);
    }

    // print the array
    for (int x = 0; x < w; x++)
    {
        for (int y = 0; y < h; y++)
        {
            if (input[x][y] == 0)
            {
                cout << ' ';
                continue;
            }
            int c = x*h + y;
            while (component[c] != c) c = component[c];
            cout << (char)('a'+c);
        }
        cout << "\n";
    }
}

ライブデモ

上記はアルファベットの別の文字を使用して各グループを表示します。

p   i
pp ii
 p  i
pppp 
   p 

これを変更してコンポーネントを個別に取得するか、各コンポーネントに対応する要素のリストを取得するのは簡単です。 1つのアイデアは、 cout << (char)('a'+c);を置き換えることcout << (char)('a'+c); componentMapmap<int, list<Point>>であるcomponentMap[c].add(Point(x,y)) 、このマップの各エントリはコンポーネントに対応し、ポイントのリストを返します。

ユニオン検索の効率を改善するためのさまざまな最適化がありますが、上記は基本的な実装に過ぎません。







neighbours