A binary image is encoded as a sorted array of non-overlapping runs, which represent value 1. Each run is defined by $r$, $c_s$ and $c_e$, with $c_s \leq c_e$. These are the row, starting and ending column coordinates of the run, inclusive. The runs are sorted by row then column. The image contains $N$ runs.

I want to perform morphological closing on this image, using an axis-aligned rectangular mask of width $w$ and height $h$, producing a new image using the same run-length encoding.

MVTec's Halcon library has implemented an algorithm that does this in $O(N \log{h})$ time. I'm not sure if this is worst-case or some kind of a typical average.[1]

Any idea how this could be accomplished?

For the case of $h=1$, it's easy to figure out: just go through runs, check distances between them if they're on the same row and merge if they're close enough. But I can't figure it out for the $h>1$ case. I sometimes think I can see how to do it in $O(N h)$ time by scanning $h$ rows at the tame, but then I try putting it down on paper and fail.

[1] Technically, they claim $O(2\sqrt{A}\log_2{h})$, with $A$ being the area of all the runs summed up.

Factor 2 probably just means that it's some kind of a two-pass algorithm.

I believe the $\sqrt{A}$ part is just there because the typical number of runs required to represent a relatively well-behaved binary blob grows with the square root of its area. I think so because they put the root even into algorithms which obviously scale linearly with the number of runs (for instance, calculating the total area of the blob or finding the axis-aligned minimum bounding-box).

I think they're just trying to put it in terms they think engineers can more easily understand. Or maybe the fact that they store all blobs using run-length encoding used to be a proprietary implementation detail long time ago when the documentation was written.

  • $\begingroup$ An obvious hint just popped into my mind. The two-pass thing is probably dilation then erosion. Apparently, their algorithms for that are $O(\sqrt{A} \log_2{h})$, without the factor 2. $\endgroup$ Dec 28 '21 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.