C中合并多个整数范围的数据结构和算法

Question

我正在研究一个计算机视觉问题，在这个问题中，我必须合并图像的区域。区域(或blob)由其行定义，即O的以下区域

  0123456789
0 XXXXOXXXXX
1 XXXOOOXXXX
2 XXXOOXXXXX
3 XXXOXXXXXX
4 XXXXXXXXXX

定义如下：

row: 0, cols: 4-4
row: 1, cols: 3-5
row: 2, cols: 3-4
row: 3, cols: 3-3

我选择这个数据结构是因为我需要能够快速找到一个区域的邻居，即所有“触摸”它的像素。

现在，我的问题是，我想要合并两个区域，即计算它们的联合。这意味着我的数据结构中可能有几个列的范围，如上文所示。

通过这种设置，我有两个问题：

1. In C，该数据的最佳数据结构是什么？一个典型的图像是16x16，这意味着没有那么多行/列。我会做很多合并(目标是从每像素一个区域开始，以一个大区域结束，即16x16-1合并)。例如，我可以使用指针来分配/释放事物，或者使用char*来存储科尔，然后解析它。
2. 如何有效地合并两个区域？我需要找到与合并相邻的潜在列(例如，3-5和6-9变成3-9)，最好不要总是重新分配和复制东西。

Answer 1

如果您的数据是两个颜色的image...black和白色，为什么不使用一个没有签名的短裤数组，即16个元素长？

unsigned short image[16]

合并可以用位逻辑来完成，这在一个16个元素数组上是非常有效的。

Answer 2

因为您已经说过您有少量的行和科尔，所以最好的结构可能只是一个简单的多维数组。对于这些小维度，在固定时间内找到邻居所获得的任何速度增长都可能被内存访问延迟和执行合并操作所需的时间所掩盖。

Billy3

Answer 3

你愿意用空间换取速度吗？在这种情况下，您可以静态地分配整个16x16结构。

struct Image {
    struct Range ranges[16*16];
};

每一行(0.15，16.31.)最多包含16个不同的范围(假设您不只有二进制数据，在这种情况下，8就可以)，最后一个范围将由'-1‘或'0’之类的哨位值来表示。

根据操作的不同，最好将struct范围定义为：

struct Range {
    int startpos;
    int count; /* or int endpos - depending on your preference */
};

通过创建一个新图像进行合并是很容易的--您可以从左边同步遍历两个“输入”图像中的每一行，并输出具有较小的“startpos”的行，以便在相邻区域合并的情况下更新最后一个写入区域。

就地合并也没有那么难，使用一些缓冲区也可以在一次运行中完成。