I have a grayscale image (given by a float matrix with values between (0, 1)) with a *hole* in it (a cluster of pixels/cells with values of -1).

Definitions:

The `boundary`

of the hole as all the cells that are 4-connected to a *hole pixel* (a pixel with -1 value) (you can read more about pixel connectivity here: https://en.wikipedia.org/wiki/Pixel_connectivity).

`I(v)`

is the color of the pixel *v*.

I need the fill the hole using this formula:

Denote the `boundary`

with *B*. So for each u – hole pixel:

begin{equation}

I(u) = frac{Sigma_v{_in}_B w(u,v) * I(v))}{Sigma_v{_in}_B w(u,v)}

end{equation}

Where *w* is some arbitrary weighting function (for example using euclidean distance)

begin{equation}

w(v,u) = frac{1}{|| u – v||}

end{equation}

Denote the number of hole pixels with *n*, the naive solution will be O(n^2), since for each hole pixel, we sum over all boundary pixels (and the upper bound for the amount of boundary pixels is 4n, of course).

I was told a solution could be achieved in O(nlogn), but I couldn’t think of anything even close to that.

I thought of doing some bitwise operations, but I reached a dead end. I also tried reusing computations, but I couldn’t find any.

Moreover, the way I see it, there’s no avoiding calculating w(u,v) for the n^2 pairs of hole/boundary pixels – which is already more than O(nlogn).

What am I missing? Could you point me at the right direction?

Thanks