0
$\begingroup$

I need a data structure/algorithm to efficiently retrieve borders and update changes.

There may be many (unconnected) regions of the same color. The shape of regions changes frequently over time and pixels may be randomly inserted - although most changes happen along the borders.

In this case, a pixel borders another if it is directly above, below, or to the left or right of it (Von Neumann neighborhood).

The lookup is as follows: retrieve all pixel coordinates with value Y that are neighbors of pixels with value X

Example: requesting all blue pixels bordering red pixels should return a list of pixels coordinates, here indicated in white:

enter image description here

So far I have tried the naive approach of checking every pixel, and then checking its neighbors if it is the required color, but this is too slow. I then changed to using a quadtree with a hierarchy of counters to avoid checking quads that do not contain either of the colors, but I feel this is still not the best solution. I have also tried using a bidirectional dictionary that maps values <-> coordinates, but this has been slower than the quadtree.

Edit: Using a better bidirectional directionary implementation, I can achieve about the same speed as the quadtree variant.

$\endgroup$
6
  • $\begingroup$ Can you give a general specification of what queries you want to be able to answer? An example is not a substitute for a general problem statement. $\endgroup$
    – D.W.
    Dec 21, 2022 at 1:04
  • $\begingroup$ Checking all four neighbors of every (blue) pixel seems close to optimal. I wonder why you conclude that this is too slow. $\endgroup$
    – user16034
    Jan 20, 2023 at 19:23
  • $\begingroup$ @YvesDaoust Because in practice, it was too slow. Low FPS $\endgroup$
    – 2080
    Jan 20, 2023 at 19:24
  • $\begingroup$ Of course, but what is the time per pixel ? What architecture ? What image processing library ? $\endgroup$
    – user16034
    Jan 20, 2023 at 19:25
  • $\begingroup$ If this needs to be performed only upon image modification, how are the changes described ? $\endgroup$
    – user16034
    Jan 20, 2023 at 19:27

1 Answer 1

0
$\begingroup$

I solved this by saving, in addition to the map[y][x] -> color multidimensional array, a defaultdict(lambda : defaultdict(dict)) map, which maps from color -> [True, False] -> (Coordinates -> True).

dict[color][True] contains all coordinates which lie on a border (to either unclaimed or other color values), and so have to be checked when trying to find out borders, and dict[color][False] maps to all coordinates that are surrounded only by their own color (or, in my special case, "unreachable" regions). These can be skipped when trying to search for neighboring pixels of a different color.

The last value is irrelevant, I only use a dictionary there to check if a coordinate is in there in O(1).

When setting a pixel, in addition to updating the map, all its four surrounding neighbors are checked if they have the same value, and if they do, the coordinate is saved in the dictionary[color][False] map, otherwise in dictionary[color][True]. Also, importantly, the same is done for all four neighbors themselves, because from their perspective, a value (may) be changing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.