Filling a hole in an image in O(nlogn)


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