Маркировка подключенных компонентов - реализация

algorithm image-processing multidimensional-array area neighbours

24847 просмотра

5 ответа

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

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

Источник Размещён: 12.11.2019 09:34

Ответы (5)


28 плюса

Решение

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

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

Автор: gus Размещён: 22.01.2013 07:05

9 плюса

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

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

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

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

Автор: Dukeling Размещён: 22.01.2013 07:07

0 плюса

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

ура

Дейв

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);
}
Автор: ejectamenta Размещён: 03.05.2013 11:05

0 плюса

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



 }

}
Автор: ostaz Размещён: 02.07.2014 06:31

0 плюса

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

        }


    }

}
Автор: Nithin K Anil Размещён: 29.07.2016 04:46
Вопросы из категории :
32x32