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

Ответ 1

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

// 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 или поиск по ширине и ширине.

Ответ 2

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

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

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

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 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 

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

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

Ответ 3

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

Приветствия

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; j<height; j++)
{
    // current row
    for(i=0; i<width; i++)
    {
        if(pOutImage[i+j*width]>0)
        {
            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; x<count; x++)
                    {
                        if(pOutImage[i+(j-1)*width]==list[x])
                            bAdd=false;
                    }

                    if(bAdd)
                        list[count++]=pOutImage[i+(j-1)*width];
                }

                if(i<width-1)
                {
                    if((pOutImage[(i+1)+(j-1)*width]>0) && (CON8 > 0))
                    {
                        for(x=0, bAdd=true; x<count; x++)
                        {
                            if(pOutImage[(i+1)+(j-1)*width]==list[x])
                                bAdd=false;
                        }

                        if(bAdd)
                            list[count++]=pOutImage[(i+1)+(j-1)*width];
                    }
                }
            }

            if(i>0)
            {
                if(pOutImage[(i-1)+j*width]>0)
                {
                    for(x=0, bAdd=true; x<count; x++)
                    {
                        if(pOutImage[(i-1)+j*width]==list[x])
                            bAdd=false;
                    }

                    if(bAdd)
                        list[count++]=pOutImage[(i-1)+j*width];
                }
            }

            // has a neighbour label
            if(count==0)
                pOutImage[i+j*width]=newLabel++;
            else
            {
                pOutImage[i+j*width]=list[0];

                if(count>1)
                {
                    // store equivalences in table
                    for(x=0; x<count; x++)
                        for(y=0; y<count; y++)
                            equivalences[list[x]+list[y]*maxEQ]=1;
                }

            }
        }
    }
}

 // floyd-Warshall algorithm - transitive closure - slow though :-(
 for(i=0; i<newLabel; i++)
    for(j=0; j<newLabel; j++)
    {
        if(equivalences[i+j*maxEQ]>0)
        {
            for(k=0; k<newLabel; k++)
            {
                equivalences[k+j*maxEQ]= equivalences[k+j*maxEQ] || equivalences[k+i*maxEQ];
            }
        }
    }


eq=(int*) calloc(sizeof(int), newLabel);

for(i=0; i<newLabel; i++)
    for(j=0; j<newLabel; j++)
    {
        if(equivalences[i+j*maxEQ]>0)
        {
            eq[i]=j;
            break;
        }
    }


free(equivalences);

// label image with equivalents
for(i=0; i<width*height; i++)
{
    if(pOutImage[i]>0&&eq[pOutImage[i]]>0)
        pOutImage[i]=eq[pOutImage[i]];
}

free(eq);
}

Ответ 4

очень полезно Документ = > https://docs.google.com/file/d/0B8gQ5d6E54ZDM204VFVxMkNtYjg/edit

java application - с открытым исходным кодом - извлекает объекты из связанных с изображением компонентных меток = > 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;



 }

}

Ответ 5

Ниже приведен пример кода для маркировки подключенных компонентов. Код написан в 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("");

        }


    }

}