Hi @sokian,
thank you very much for your contribution but I think that the upper bound for the maximum number of labels in LabelingGrana that you have defined is too big. I think that:

const size_t Plength = (h+1)*(w+1)/4 + 1;

is absolutely enough!! I will explain it in the following with some examples.

First of all it is important to highlight that Grana’s algorithm treats only 8-way connectivity. So, for example, considering a binary image of 6x6 some of the worst cases (i.e. in which the maximum number of labels will be generated) are given by configurations reported in figures 1, 2, 3 and 4. In that cases the maximum number of labels is given by the following formula:

(h*w)/4 + 1 (1)

one label for every 2x2 block + one label for the background.

Now, if we consider the case of images with odd number of columns, rows or both (6x5 or 5x6 or 5x5) some examples of the worst cases are the ones presented in figures 5, 6, 7. In such cases, the formula (1) may fails because some of 2x2 blocks are “incomplete”. In these cases, just adding one to the matrix width and height (i.e h+1 and w+1 in the general formula above) we solve the issue obtaining an effective general upper bound.

Figure 1	Figure 2	Figure 3

Figure 4	Figure 5	Figure 6

Figure 7

Hi @prittt,

Oh, I see, if this algorithm will be used only for 8-connectivity case, then there should be an Assert

CV_Assert(connectivity == 8);

But now it has Assert:

CV_Assert(connectivity == 8 || connectivity == 4);

And, of course, I agree with you for upper bound in 8-connectivity case, it's obvious right (thanks for such beautiful explanation with example images).

👍

There is another PR with complete rewrite of connectedComponents pending. Let's merge that one first, and then, if this one is still relevant, it should be updated.

ok, let's close this one for now. please, reopen if it's still relevant