我正在尝试优化联合查找算法以查找映像中的连接组件。我的图像可以是2d或3d文件,由0和1组成。我在这个线程中找到了一个实现:Connected Component Labelling,用户Dukering给出了答案。联盟查找的效率提高
我改编了我的目的代码。代码有效,但执行时间很快变得太大。我不明白这个问题。
我的代码如下所示。我正在测试的文件链接如下:https://utexas.box.com/s/k12m17rg24fw1yh1p21hytxwq5q8959u 这是一个2223x2223大小的文件(在下面的程序中定义)。
正如原始用户提到的,这是union-find的基本实现,并且可以使其更有效。我不明白如何。另外,我在Matlab中测试了这个图像,并且Matlab速度更快。例如,上面链接的图像在我的计算机上需要大约1.5分钟,但Matlab使用bwlabel在一秒钟内完成。我检查了bwlabel使用的算法,它似乎是union-find的一些变体,这就是我首先开始这项工作的原因。如何让我的代码尽快运行?我还应该提到,我希望在更大的图像上运行我的代码(高达1000^3)。我目前的版本无法做到这一点。
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#define w 2223
#define h 2223
void writeArrayInt(int *data, int dims[], char *filename)
{
FILE *fp;
fp = fopen(filename,"w");
/* write grid dimensions */
fwrite(dims, sizeof(int), 3, fp);
/* write data array */
fwrite(data, sizeof(int), w*h, fp);
fclose(fp);
}
void readArrayInt(int *data, int dims[], char *filename)
{
FILE *fp;
fp = fopen(filename,"r");
/* read grid dimensions */
fread(dims, sizeof(int), 3, fp);
/* read data array */
fread(data, sizeof(int), w*h, fp);
fclose(fp);
}
void doUnion(int a, int b, int *component)
{
// 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, int *component, int *input)
{
int ind1 = x*h + y;
int ind2 = x2*h + y2;
if (y2 < h && x2 < w && input[ind1] && input[ind2] && y2 >= 0 && x2 >= 0)
doUnion(ind1, ind2, component);
}
int main()
{
int i, j;
int *input = (int *)malloc((w*h)*sizeof(int));
int *output = (int *)malloc((w*h)*sizeof(int));
int dims[3];
char fname[256];
sprintf(fname, "phi_w_bin");
readArrayInt(input, dims, fname);
int *component = (int *)malloc((w*h)*sizeof(int));
for (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, component, input);
unionCoords(x, y, x, y+1, component, input);
unionCoords(x, y, x-1, y, component, input);
unionCoords(x, y, x, y-1, component, input);
unionCoords(x, y, x+1, y+1, component, input);
unionCoords(x, y, x-1, y+1, component, input);
unionCoords(x, y, x+1, y-1, component, input);
unionCoords(x, y, x-1, y-1, component, input);
}
for (int x = 0; x < w; x++)
{
for (int y = 0; y < h; y++)
{
int c = x*h + y;
if (input[c] == 0)
{
output[c] = input[c];
continue;
}
while (component[c] != c) c = component[c];
int c1 = x*h + y;
output[c1] = component[c];
}
}
sprintf(fname, "outputImage2d");
writeArrayInt(output, dims, fname);
free(input);
free(output);
free(component);
}
如果您的代码正在工作,并且您希望提供有关如何改进其性能的建议,那么[codereview.se]是此问题的更合适的位置。 – kaylum
请缩进您的代码。如果您使用Tab键缩进,现在是时候去找到如何告诉您的IDE插入空格... – Lundin
您的缩进真的需要帮助:修复它可以帮助您获得帮助。 – Richard