inpaint_nans

How do I stop extrapolation (interpolation only)?

Excelent code, does it's job admirably. I used it for radio signals and algorithm 4 was great.

A=[14.0985; 2.5852; NaN];

inpaint_nans(A,2)

Subscript indices must either be real positive integers or logicals.
Error in inpaint_nans (line 239)
fda(nm,[nm,nm-1,nm-n])=[-2 1 1];

If I supply A as a row vector works fine.

did you use the multiple regression for this? would you tell me how the method works? i have the problem with imputation the NaNs in the matrix too, but it's not about digital painting at all :( i hope it will works on my own too.
thanks before

fantastic, thanks John

Really helpful code, thanks. A couple of questions which hopefully someone can answer for me. Looking through the different methods, I think I understand roughly what's happening (though correct me if I'm wrong), but I am unsure where the coefficients for the higher order pde's come from.

For methods 0,1 & 2 a set of linear equations are formulated then solved from the partial derivatives derived from the discrete Laplacian approximation / finite element method (to give rise to the co-efficients for 2nd order [1 -2 1]) in each plane. I think I understand this and why the sum of the partial derivatives are set to 0 etc.

For method 3, how are the co-efficients calculated/derived for the 4th (del^4) order pde's? The co-efficients in the code are [1 2 -8 2 1 -8 20 -8 1 2 -8 2 1] and uses a 5x5 diamond structure but looking the algorithm and background research I can't see how they have been composed.

After 5 hours of searching and testing finally this one helped! Thanks so much

Actually, I made a mistake. I've mixed two examples I was looking at.

The average of 2 and 0 is of course 1.
So I would pick 1 as a solution.

What I see in your code is that the problem above is solved by the following set of equations:

2 x = 1+3 = 4
x = 10+6+4 - 4*5 = 0

The least squares solution for this set of equations, is indeed x=1.6.
But why is the first equation multiplied by 2?

If you keep the factor for x in both equations equal to one, you get

x = (1+3)/2 = 2
x = 10+6+4-4*5 = 0

This gives x=1 as least squares solution.

A =
1 4 7
NaN 5 10
3 6 11

Lets call the NaN value x.

Your function gives x=1.6.
I think x=1.5 is more logical, how about you?

If we look at the first column, we have x=0.5*(1+3). ==> x=2
If we look at the 5, we have
5=0.25*(x+10+4+6). ==> x=0

If we average these values, we have x=1.5.

I have a 2D data, last few rows have NaNs. I used your function to fill them up. I had a result. Then I created another matrix such that x=[x; flipud(x)] and then again used your function to fill the holes. In both the case, I get the same values in place of NaNs. I was hoping in the second case that the values will be more smoother. Please let me know if its possible. Thanks a lot.

I will definitely look up gridfit - thanks a lot!

Excellent job!

One question however, would it be possible to use method 4 (i.e. the one with "springs") on data where the spacing between columns and rows are not the same? (One example is if the x-axis (along the columns) is non-linear so that the spring to the right is weaker than the oppsite spring to the left.)

NaNs of a different color? I.e., two types of NaN. My only suggestion is to allow them all to be estimated, and then convert those you wish to remain NaN back into NaNs.

If you don't do that, then you may be unable to estimate other NaN elements that may lie in the same neighborhood.

works great! Could use an updated example image.

(I resolved Kaah's problem by e-mail.)

As for Paulo, this is not an inpaint_nans issue. You are asking how to get imwrite to write out a one channel (grayscale) image? I'm not really sure what you don't understand here, but I think you need to do a quick read of the help for imwrite (a simple function, although the help is admittedly long.) Or perhaps you don't understand what a grayscale image is, or how to convert it back to a 3 channel image (although still grayscale)? In any event, this is not an inpaint_nans problem.

I have no idea what you are doing wrong. The following tests show absolutely no problems, with any of the methods. I tested it for sparse or full inputs.

>> A = rand(100);
>> A(rand(100)>.5) = nan;
>> B = inpaint_nans(A,3);
>> B = inpaint_nans(sparse(A),3);

Please send me an e-mail with an example that shows your problem.

THANK YOU!!!!

Very helpful function!!
Does it work if the meshgrid is not evenly spaced? I imagine it won't. Is there anything i can do to deal with this other than removing data an uneven increments and making sure n and m are evenly spaced?

Works graeat

This is one of the most useful functions I have seen on the file exchange. It would be nice to have variable window-sizes, for various image-processing methods. I'll come back and rate it once I have used it.

Actually, it is not the size of the matrix that matters, as much as how many NaNs are to be inpainted, and the location of those nan elements. And of course, if you are running 64 bit matlab, much larger problems can be processed. The method used will be crucial too.

I ran a quick test on a machine with a new CPU (R2010b, 64 bit matlab, 4 cores, 8 gigs of ram) compared to the one I originally wrote the code on. The test case was a 1000x1000 array with 50% randomly inserted nan elements - it took only a few seconds to interpolate for most methods.

>> [x,y] =meshgrid(1:1000);
>> z = exp((x+y)/1000);
>> zap = rand(size(x)) < .5;
>> z(zap) =NaN;

>> tic,zhat = inpaint_nans(z,0);toc
Elapsed time is 8.251664 seconds.

>> tic,zhat = inpaint_nans(z,1);toc
Elapsed time is 6.098041 seconds.

>> tic,zhat = inpaint_nans(z,2);toc
Elapsed time is 2.293744 seconds.

>> tic,zhat = inpaint_nans(z,3);toc
Elapsed time is 35.743856 seconds.

>> tic,zhat = inpaint_nans(z,4);toc
Elapsed time is 3.057140 seconds.

Method 3 is the most memory intensive. It used all the cores, and on this test, roughly 2 gig of system ram was used. The less intensive methods used considerably less than 1 gig of ram on this test. In any case, I find it impressive that MATLAB is able to solve the required linear system of equations with roughly 500,000 unknowns in that period of time.

That would be awesome if you could do that. I would greatly appreciate it.

This is exactly what I needed. Thank you.

I do have one suggestion though. I have geographical data that I am interpolating using this script and then plotting using meshm and it works great except that the left and right edges of the matrix are actually the same point on the earth so I have had to put copies of the same matrix on both the left right and and rotated copies on the top and bottom to get the interpolation to "wrap around" and then remove those extra parts. While this works great for the data around the equator the interpolation is not correct around the poles, because the top row of the square matrix is in reality the same point on the earth.
So my suggestion (unless there is already a way to do this) is to make this or a new program that will inpaint nans for a geolocated square matrix. That would be incredibly usefull.

(If anyone knows already how to do this, please let me know)

Hello, I recently started studying about inpainting and i ran across Mr. D'Errico's program and I have to say it's pretty cool, tried it on a few pics of mine and i wase pleased with the results.
I need some help about understanding the basic theory on the subject, how the elliptic PDE's are implemented in inpainting etc. and if anyone could give me a hint on where i could find some books, documents on the matter i would be very grateful. Regards

John, I saw in your zip file how you are thinking of removing method 5. Let me make a counter suggestion: expand it. I can think many of reasons and applications where a neighborhood average would be useful. In terms of expansion: Well, you could allow for the size of the neighborhood, its orientation (forward, backward, center), and the function (sum, mean, var, mode, etc.) to be passed as additional arguments. Either way, this function is very useful and I use it often in place of standard Matlab functions.

@Marco,

You appear to have completely missed the point of this function. It is designed to REMOVE NaNs appearing in a matrix, overwriting those values with interpolated values obtained from neighboring entries. You seem to think that John is arbitrarily redefining what NaN is... he is not, because that would be a silly waste of time. The numbers he computes to REPLACE the NaNs are approximated from the surrounding values with a number of different methods.

As far as some of the errors you got, John could probably place error checks in the function to allow for a more graceful and informative exit. However, there's no reason you would/should ever enter some of those arguments in the first place. For example, entering a scalar NaN is silly, since the program has no nearby non-NaN elements to use for extrapolating replacement values.

This submission certainly doesn't deserve the low rating you gave it, especially since the misunderstanding lies with your own misinterpretation of what it does.

Thank you once again John,
exactly what I needed.

Please TMW: include this in next release of matlab!

Comment=[T H A N NaN Y O U V E NaN Y M NaN NaN H];

[M,N] = size(Comment);
for k = 1:length(M);
Comment=inpaint_nans(Comment);
end

Comment=
T H A N K Y O U V E R Y M U C H

Here you have my 5 stars... Congratulations, and thanks for sharing it...

Really helpful with minimal fuss!

Thank you! This does exactly what I was hoping it would!

great!

very fast, thanks!

Well done !

excellent!

I love it!

A very useful and meticulously coded, data-driven function. A must to look at and learn from for anybody who is working with incomplete 2D data sets, in particular, dirty images.