Algorithm and data structure for finding and storing neighborhood superpixels in C ++

Question

I have an image containing segmentation results, like this one.

I need to plot the neighborhood of patches painted in different colors. As a result, I need a structure representing the following

Here the numbers are separate patches, and the lines are neighborhoods of patches. Currently, I cannot figure out where to start, what are the keywords for google.

Can anyone suggest anything useful?

The image is saved in the OpenCV class cv :: Mat, as for the graph, I plan to use the Boost.Graph library.

So, please give me some links to code samples and algorithms or keywords.

Thanks.

Update . After a coffee break and some discussions, the following occurred to me.

• Create a large lattice graph, where each node corresponds to each pixel in the image, and the links connect 8 or 4 neighbors.
• Label each node graph with a corresponding pixel value.
• Try merging nodes with the same label.

My other problem is that I am not familiar with BGL (but the book is on the way :)).

So what do you think of this decision?

Update2 Probably this link may help.

However, a solution has not yet been found.

Answer 1

You could solve it like this:

• Define the regions (your numbers on the chart)

  • create a 2D array that stores the area number
  • start with (0/0) and set it to 1 (area number)
  • set the entire area as 1 using the fill algorithm or something like that.
  • during the fill, you are likely to encounter coordinates that have a different color. keep them in line. start filling out these coordinates and increase the region number if your previous fill is completed.

  .

• Creating links between regions

  • iterate through your 2D array.
  • If you have adjacent numbers, save the pair number (probably in a sorted way, you also need to check if the pair already exists or not). You only need to check the element below, on the right and one diagonal to the right if you are moving from left to right.

Although I have to admit that I know nothing about this topic .. just my simple idea ..

Answer 2

You can use BFS to mark regions.

To expose cv :: Mat in BGL, you have to write a lot of code. I think writing your own bfs is a lot easier.

Than for every two blacks you write your marks on std::set<std::pair<mark_t, mark_t>> . And how to build a graph from this.

Answer 3

I think if your color patches are random, you probably need a brute force algorithm to do what you want. An idea could be:

• Do the first brute force search. This should identify all patches. For example, make the matrix A the same size as the image and initialize it to 0. For each pixel that is still zero, start with it and mark it as a new patch and try the brute force approach to find the integer size of the patch. Each matrix cell will have a value equal to the patch number in which it is located.
• Patch numbers must be 2^N , e.g. 1, 2, 4, 8, ...
• Make another image size matrix B, but each cell has two values. This will be a connection between the pixels. For each cell of matrix B, the first value will be the absolute difference between the patch number in the pixel and the patch number of the neighboring pixel. The first value is the difference with the pixel below, the second with a pixel to the left.
• Select all the unique values ​​in matrix B, you have all the possible connections.

This works because each difference between the number of patches is unique. For example, if in B you get the numbers 3, 6, 7, this will mean that there are contacts between the patches (4.1), (8.2) and (8.1). A value of 0, of course, means that there are two pixels next to one patch, so you just ignore them.