我几天前问过一个类似的问题，但我还没有找到解决问题的有效方法。我正在开发一个简单的主机游戏，我有一个这样的 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++代码吗，因为我对它实际上如何与这种脱节集数据结构一起工作感到困惑......
非常感谢您的帮助和时间。
我先给你代码，然后再解释一下：
// 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 或广度优先搜索。
这可以通过联合查找来解决（尽管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>> - 然后，此地图中的每个条目将对应于一个组件并给出点列表。
有各种优化来提高联合查找的效率，以上只是一个基本的实现。
您也可以尝试这种传递闭包方法，但是当图像中有许多分离的对象时，传递闭包的三重循环会减慢速度，欢迎建议的代码更改
干杯
戴夫
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);
}
非常有用的文档
=> 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("");
}
}
}