Маркировка связанных компонентов

Несколько дней назад я задал подобный вопрос, но мне еще предстоит найти эффективный способ решения моей проблемы. Я разрабатываю простую консольную игру, и у меня есть 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 

Алгоритм, над которым я работал, находит всех соседей соседей ячейки и отлично работает на таких matrixх. Однако, когда я использую большие массивы (например, 90 * 90), программа работает очень медленно, и иногда огромные массивы, которые используются, вызывают переполнение стека.

Один парень по моему другому вопросу рассказал мне о маркировке связанных компонентов как эффективное решение моей проблемы.

Может ли кто-нибудь показать мне какой-нибудь код на C ++, который использует этот алгоритм, потому что я немного смущен тем, как он работает вместе с этой структурой данных, не связанной с разделом …

Большое спасибо за вашу помощь и время.

Сначала я дам вам код, а затем немного объясню:

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

Это общий способ решения этой проблемы.

Направление векторов - это просто хороший способ найти соседние ячейки (в каждом из четырех направлений).

Функция dfs выполняет поиск по глубине сетки. Это просто означает, что он посетит все ячейки, доступные из исходной клетки. Каждая ячейка будет отмечена знаком current_label

Функция find_components проходит через все ячейки сетки и запускает маркировку компонентов, если она обнаруживает немеченную ячейку (помеченную 1).

Это также можно сделать итеративно, используя стек. Если вы замените стек на очередь, вы получите bfs или first-search .

Это можно решить с помощью объединения (хотя DFS, как показано в другом ответе, возможно, немного проще).

Основная идея этой структуры данных состоит в том, чтобы повторно объединять элементы в одном компоненте. Это делается путем представления каждого компонента в виде дерева (с узлами, отслеживающими их собственный родительский объект, а не наоборот), вы можете проверить, находятся ли два элемента в одном компоненте, перейдя к корневому узлу, и вы можете объединить узлы просто сделав один корень родителем другого корня.

Пример короткого кода, демонстрирующий это:

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

Демо-версия .

Вышеупомянутая группа будет отображать каждую группу из них, используя другую букву алфавита.

 pi pp ii pi pppp p 

Это должно быть легко изменить, чтобы получить компоненты отдельно или получить список элементов, соответствующих каждому компоненту. Одна из идей заключается в замене cout << (char)('a'+c); выше с componentMap[c].add(Point(x,y)) где componentMap является map> - каждая запись на этой карте будет соответствовать компоненту и давать список точек.

Существуют различные оптимизации для повышения эффективности поиска профсоюзов, выше всего это просто базовая реализация.

Вы также можете попробовать этот транзитивный подход закрытия, однако тройной цикл для транзитивного замыкания замедляет работу, когда на изображении много выделенных объектов, предлагаемые изменения кода приветствуются

ура

Дейв

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

очень полезно Документ => 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 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; } } 

Ниже приведен пример кода для маркировки подключенных компонентов. Код написан в 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(""); } } } 
  • Java: multidimensional array против одномерного
  • Преобразование многомерных массивов в указатели в c ++
  • Как передать multidimensional array функции в C и C ++
  • Получение длины массива 2D-массива в Java
  • ReDim Сохраняет multidimensional array в Visual Basic 6
  • Манипулировать multidimensional array в функции
  • Как я могу добавить два массива 2d (стадия), используя вложенные для циклов?
  • Почему 248x248 максимальный размер двумерного массива, который я могу объявить?
  • Как я могу работать с динамически распределенными произвольномерными массивами?
  • Как инициализировать 3D-массив в C ++
  • C ++ Возвращаемый массив многомерности из функции
  • Interesting Posts
    Давайте будем гением компьютера.