Etiquetado de componentes conectados

Hace algunos días hice una pregunta similar, pero todavía no he encontrado una manera eficiente de resolver mi problema. Estoy desarrollando un juego de consola simple, y tengo una matriz 2D como esta:

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 

Estoy tratando de encontrar todas las áreas que consisten en 1 vecinos (conectividad de 4 vías). Entonces, en este ejemplo, las 2 áreas son las siguientes:

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

y:

  1 1,1 1 

El algoritmo, en el que he estado trabajando, encuentra todos los vecinos de los vecinos de una celda y funciona perfectamente bien en este tipo de matrices. Sin embargo, cuando uso matrices más grandes (como 90 * 90), el progtwig es muy lento y, a veces, las grandes matrices que se utilizan causan desbordamientos de stack.

Un hombre en mi otra pregunta me habló sobre el etiquetado de componentes conectados como una solución eficiente a mi problema.

¿Alguien puede mostrarme cualquier código C ++ que use este algoritmo, porque estoy un poco confundido acerca de cómo funciona realmente junto con esta cosa de estructura de datos disjuntos …

Muchas gracias por su ayuda y tiempo.

Primero te daré el código y luego lo explicaré un poco:

 // 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); } 

Esta es una forma común de resolver este problema.

Los vectores de dirección son solo una buena manera de encontrar las celdas vecinas (en cada una de las cuatro direcciones).

La función dfs realiza una búsqueda en profundidad de la cuadrícula. Eso simplemente significa que visitará todas las celdas accesibles desde la celda de partida. Cada celda se marcará con current_label

La función find_components recorre todas las celdas de la grilla e inicia una etiqueta de componente si encuentra una celda sin etiqueta (marcada con 1).

Esto también se puede hacer de forma iterativa usando una stack. Si reemplazas la stack con una cola, obtienes la bfs o la búsqueda por anchura .

Esto se puede resolver con union find (aunque DFS, como se muestra en la otra respuesta, es probablemente un poco más simple).

La idea básica detrás de esta estructura de datos es combinar elementos repetidamente en el mismo componente. Esto se hace representando cada componente como un árbol (con nodos haciendo un seguimiento de su propio padre, en lugar de al revés), puede verificar si dos elementos están en el mismo componente atravesando el nodo raíz y puede fusionar nodos simplemente haciendo una raíz el padre de la otra raíz.

Un ejemplo de código corto que demuestra esto:

 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"; } } 

Demostración en vivo

Lo anterior mostrará cada grupo de unos con una letra diferente del alfabeto.

 pi pp ii pi pppp p 

Debería ser fácil modificar esto para obtener los componentes por separado o obtener una lista de elementos correspondientes a cada componente. Una idea es reemplazar cout << (char)('a'+c); arriba con componentMap[c].add(Point(x,y)) con componentMap como un map> - cada entrada en este mapa corresponderá a un componente y dará una lista de puntos.

Hay varias optimizaciones para mejorar la eficiencia de union find, lo anterior es solo una implementación básica.

También podría intentar este enfoque de cierre transitivo, sin embargo, el ciclo triple para el cierre transitivo disminuye la velocidad cuando hay muchos objetos separados en la imagen, los cambios de código sugeridos son bienvenidos.

Aclamaciones

Dave

 void CC(unsigned char* pBinImage, unsigned char* pOutImage, int width, int height, int CON8) { int i, j, x, y, k, maxIndX, maxIndY, sum, ct, newLabel=1, count, maxVal=0, sumVal=0, maxEQ=10000; int *eq=NULL, list[4]; int bAdd; memcpy(pOutImage, pBinImage, width*height*sizeof(unsigned char)); unsigned char* equivalences=(unsigned char*) calloc(sizeof(unsigned char), maxEQ*maxEQ); // modify labels this should be done with iterators to modify elements // current column for(j=0; j0) { count=0; // go through blocks list[0]=0; list[1]=0; list[2]=0; list[3]=0; if(j>0) { if((i>0)) { if((pOutImage[(i-1)+(j-1)*width]>0) && (CON8 > 0)) list[count++]=pOutImage[(i-1)+(j-1)*width]; } if(pOutImage[i+(j-1)*width]>0) { for(x=0, bAdd=true; x0) && (CON8 > 0)) { for(x=0, bAdd=true; x0) { if(pOutImage[(i-1)+j*width]>0) { for(x=0, bAdd=true; x1) { // store equivalences in table for(x=0; x0) { for(k=0; k0) { eq[i]=j; break; } } free(equivalences); // label image with equivalents for(i=0; i0&&eq[pOutImage[i]]>0) pOutImage[i]=eq[pOutImage[i]]; } free(eq); } 

Documento muy útil => https://docs.google.com/file/d/0B8gQ5d6E54ZDM204VFVxMkNtYjg/edit

aplicación java – fuente abierta – extraer objetos de la imagen – etiquetado de componentes conectados => https://drive.google.com/file/d/0B8gQ5d6E54ZDTVdsWE1ic2lpaHM/edit?usp=sharing

  import java.util.ArrayList; public class cclabeling { int neighbourindex;ArrayList Temp; ArrayList> 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(); Temp.add(i); for(int x=0;x"+time/1000000+" milliseconds"); System.out.println("Number Of Shapes => "+xycc.length); return xycc; } } 

A continuación, encontrará el código de muestra para el etiquetado de componentes conectados. El código está escrito en 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); lm[0][0]=0; lm[0][1]=0; lm[0][2]=0; lm[0][3]=0; lm[1][0]=0; lm[1][1]=1; lm[1][2]=0; lm[1][3]=0; lm[2][0]=0; lm[2][1]=0; lm[2][2]=0; lm[2][3]=0; lm[3][0]=0; lm[3][1]=1; lm[3][2]=0; lm[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(""); } } }