Datastructure and algorithm for merging multiple ranges of integer in C

Question

I am working on a Computer Vision problem, in which I have to merge regions of an image. A region (or blob) is defined by its lines, i.e. the following region of O:

  0123456789
0 XXXXOXXXXX
1 XXXOOOXXXX
2 XXXOOXXXXX
3 XXXOXXXXXX
4 XXXXXXXXXX

is defined by :

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

I chose this datastructure because I need to be able to find quickly the neighbors of a region, i.e. all the pixels that "touch" it.

Now, my problem is that I want to merge two regions, i.e. compute the union of them. This means that I may end up with several ranges of columns in my data structure shown above.

With this setup, I have two questions:

1. In C, what is the best datastructure for this data ? A typical image is 16x16, which means not that many rows/columns. I will do a lot of merging (the goal of the thing is to start with one region per pixel and end with one big region, i.e. 16x16 - 1 merges). I could go with a pointer and allocate/free the things, or use a char* to store the cols and parse it afterwards, for instance.

2. How to efficiently merge two regions? I need to find potential columns that are adjacent to merge them (e.g., 3-5 and 6-9 become 3-9), preferably without always reallocating and copying things.

Answer 1

Since you said you have a small number of rows and cols, the best structure is probably just a simple multidimensional array. For these small dimensions, any speed increase you get from being able to find the neighbors in constant time will probably be overshadowed by memory access latency and by the time it takes to perform the merge operation.

Billy3

Answer 2

Are you willing to trade space for speed? In such case you could statically allocate the whole 16x16 structure.

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

every row ([0..15], [16..31]...) will contain at most 16 different ranges (assuming you don't have binary data only, in such case 8 will do), the last range would be denoted by some sentinel value like '-1' or '0' or something.

Depending on the operation, it might be preferable to have struct range defined like:

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

Merging by creating a new image is easy - you traverse each row in both 'input' images simulatneously from the left and output the one with smaller 'startpos', in case of a merge of adjacent regions you update the last written region.

In-place merging isn't that hard either, with some buffer it can be done in one run as well.

Answer 3

If your data is for a two color image...black and white, why not just use an array of unsigned shorts that is 16 elements long?

unsigned short image[16]

The merging could be done with bitwise logic which is pretty efficient over a 16 element array.

Answer 4

If memory is not an issue, it might be possible to improve lookup speeds by storing pointers to the neighboring pixels. eg, create a "Pixel" struct which will store its value and a list of pointers to the neighboring pixels. As mentioned above, create a 16x16 multi-dimensional array of "Pixel"s. Once the memory is set-up, go through the array and set up the neighbor pixel list to point to the neighboring pixels. After everything is set up, finding a pixel and its neighbors should be really quick.