Image interpolation from random pixels

Question

I would like to ask a question regarding single channel image interpolation. Single channel is chosen just for simplicity otherwise I'm working on multiple channel images. Assume there is a single channel image with pure black background ( pixel intensity 0) on which there are some pixels with non-zero intensity values. I want to apply an interpolation algorithm to fill the entire black area of the image with interpolated values coming from the neighboring non-zero intensity pixels.

What interpolation algorithm would you recommend for a smooth interpolation applicable to this problem?

As inputs, we of course know the location of those non-black pixels and their intensity. But the location is somewhat random ( in one row may be 10 pixels, in another row only 8).

enter image description here

Andrey Rubshtein · Accepted Answer · 2012-09-14T17:46:05.320

The regular interp2 will not work here, since your points are not located at regular intervals (Not sitting on a grid). You can either try TriScatteredInterp or download inpaint_nans from the file exchange.

Here is the solution in your case with TriScatteredInterp:

enter image description here

function solveStackOverflowProblem()
    im = imread('https://i.stack.imgur.com/lMaYR.png');
    im = im(:,:,2);
    [i,j] = find(im);
    y = j; x = i;
    indexes = sub2ind(size(im),i,j);
    interpolator = TriScatteredInterp(x,y,double(im(indexes)));

    [Y,X] = meshgrid( 1:size(im,2),1:size(im,1));
    reconstructedImage = interpolator(X,Y);

    figure;imshow(reconstructedImage/255)
end

score 4 · Answer 2 · answered Sep 14 '12 at 20:44

4

Your best solution is to use gridfit. Its designed to improve on all the native Matlab functions like TriScatteredInterp and griddata.

answered Sep 14 '12 at 20:44

twerdster

4,977
3
40
70

1

inpaint_nans will also work here. Replace the zeros with NaN elements, then throw it into inpaint_nans. The virtue of course is that inpaint_nans may be more efficient if there are few elements to interpolate, since it need not fit the entire image, but only interpolate the holes from those pixels that border them. If there are only a few valid pixels provided, then gridfit is just as good. (Disclosure: I am the author of both gridfit and inpaint_nans.) – Sep 30 '13 at 15:13

AJMansfield · Answer 3 · 2013-09-30T15:07:43.563

For a relatively small number of points, the ideal way to interpolate them would be to create a triangular mesh, using only the vertices of each region to determine pixels within that region, using a weighted mean to determine each pixel's color.

To find the color of a pixel inside a triangular region, the weights to use for each pixel are, for the points, A, B, and C, respectively, (bc-A)/a, (ac-B)/b, and (a*b-C)/c. This ensures that each point's influence deteriorates to zero as the point gets closer to the opposite edge, so that transitions between triangles are smooth.

Keep in mind that you can use any type of mean, including harmonic and geometric, not just arithmetic, to do the calculation (appearances will change, but other types of means might be better anyway).

Diagram labeling triangle parts

I am unfamiliar with matlab, so I don't know for sure, but Andrey's answer may actually be identical to mine, just using an existing library function to do it. If it is, though, the interpolator he is using is only using an arithmetic mean, when it would be very advantageous to use a different one. — AJMansfield, Sep 14 '12 at 19:34

image_doctor · Answer 4 · 2012-09-15T13:39:57.153

Here is a solution based on using Radial Basis Functions ( in this case a Gaussian ) to build interpolations for randomly spaced points with varying intensities.

Essentially this drops a Gaussian on each point, weights it by the point intensity and sums the result.

The sharpness of the interpolation function is controllable via the standard deviation of the chosen Gaussian function.

The points:

Mathematica graphics

The interpolation:

Mathematica graphics

Viewed in 3D: Mathematica graphics

With a smaller standard deviation: Mathematica graphics

The code:

pts = Table[{{RandomReal[{0, 200}], RandomReal[{0, 200}]}, 
   RandomReal[]}, {20}]

dists = Function[points, 
  Plus @@ ((PDF[
          MultinormalDistribution[#, 200 IdentityMatrix[2]], {x, 
           y}] & /@ points[[All, 1]] ) points[[All, 2]])/Length@points]

DensityPlot[dists[pts], {x, 0, 200}, {y, 0, 200}, PlotPoints -> 100]

score 0 · Answer 5 · answered Sep 14 '12 at 17:33

0

Any interpolation will look really bad with this few non-zero points, but you can try convolving the image with a 2-D filter such as a Gaussian kernel and see if you like it.

answered Sep 14 '12 at 17:33

HerrKaputt

2,594
18
17

Image interpolation from random pixels

5 Answers5

Linked