inpaint_nans

Interpolates (& extrapolates) NaN elements in a 2d array.

Description

Interpolate NaN elements in a 2-d array using non-NaN elements. Can also extrapolate, as it does not use a triangulation of the data. Inpaint_nans offers several different approaches to the interpolation, which give tradeoffs in accuracy versus speed and memory required. All the methods currently found in inpaint_nans are based on sparse linear algebra and PDE discretizations. In essence, a PDE is solved to be consistent with the information supplied.

• Acknowledgements: This submission has inspired the following:; Inpaint over missing data in N-D arrays, inpaint_nans3, PIVlab - time-resolved particle image velocimetry (PIV) tool
• MATLAB release: MATLAB 5.2 (R10)
• Other requirements: Written in version 5.2, tested up to release 14 SP1

[Urs Schwarz (us)]

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.

[Evan Zamir]

Nice! Especially method 4 using the virtual springs.

[Tom Reiser]

I love it!

[d d]

 

[jing tian]

excellent!

[gok gok]

how to handle non-rectangular areas? Triangle for example.
I'm getting holes from DELAUNAY and your routine will be very helpful to fix this bug.

[K. Sturm]

Well done !

[Cris C.]

Really a good work. Thank you.

[sacrosancttayyar sacrosancttayyar]

 

[Rajeev Srivastava]

excellent work.

[Ian Howat]

very fast, thanks!

[Mike Kadour]

Just what I was looking for! Many thanks!

[mario fiorini]

great!

[Amar chawla]

Great piece of work! really helped....

[Emily Spahn]

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

[martin klöppel]

realy useful

[Sara Alexander]

Really helpful with minimal fuss!

[D. G.]

Simply excellent. Nothing to declare.

[Carlos Adrián Vargas Aguilera]

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

[Bob Field]

Magical

[E E]

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

[Sherif Abd El-Gawad]

Thanks a lot and Good Contribution

[Frederic Moisy]

Thank you once again John,
exactly what I needed.

Please TMW: include this in next release of matlab!

[Kenneth Eaton]

 

[V. Poor]

 

[alain boyer]

 

[Kenneth Eaton]

@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.

[Kenneth Eaton]

@Marco,

If you want more specific information about the methods than what is in the help documentation, you would have to either delve into the code itself or have John explain it to you.

Also, the word "lies" is a conjugation of the verb "to lay", not a noun meaning "falsehoods". To rewrite my statement in another way: "...the misunderstanding is a result of your own misinterpretation."

[C Schwalm]

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.

[Karel]

 

[Stuart]

 

[Stefan]

 

[Stefan]

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

[Andrey Rubshtein]

 

[Jon]

 

[Raghavendra]

 

[Bryant Svedin]

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)

[John D'Errico]

It would be fairly easy to re-write this for a single method of interpolation to allow for some variety of periodic boundary conditions. But I think the class described by you are really toroidal BCs, not correctly spherical, as you point out. If they are an adequate approximation for your problem, I would be able to post a modified version for this specific problem.

The problem with true spherical BCs at the poles is that all the elements along the top edge of the array should be identical. I could probably implement such a BC though by adding a single phantom node at each of the north and south poles.

[Bryant Svedin]

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

[Alexandra]

 

[Nitin Kumar]

 

[Daniel]

Fantastic program. Exactly what I needed.

What is the largest 2d matrix which inpaint_nans can handle?

[John D'Errico]

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.

[Paolo]

good work!

[Francis Esmonde-White]

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.

[Matt Patten]

Absolutely perfect!

[Matt Patten]

 

[Tannistha]

thanks a lot, i created a matrix using griddata and had no idea how to get rid of the NaN values

[Tobias Kienzler]

 

[Venkateswara Rao Narukull]

Excellent job...this is what exactly I needed

[Trevor]

Works graeat

[TAFKARS]

Good work, much appreciated

[Vineet Mehta]

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?

[Michael Völker]

 

[Claire]

THANK YOU!!!!

[Kaah]

Great m-file. Thanks immensely for this.

When I tried using method 3, I got this error message from MATLAB:

 Error using ==> sparse
Index into matrix must be positive.

Error in ==> inpaint_nans at 291
    fda=fda+sparse(repmat(all_list(L,1),1,5), ...

Please could someone help explain why this occurs?

[John D'Errico]

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.

[Paulo]

great work! i am using your work in my project but i am getting problems on how to save the output. when showing the output, it needs square bracketts,[] in IMSHOW command. but how to do it in IMWRITE? thanks!

irisImage = imread('C:\test.bmp'); irisImageGrayScale = rgb2gray(irisImage);

                irisImageGrayScale = double(irisImageGrayScale);
irisImageGrayScale(irisImageGrayScale>170) = nan;
irisImageGrayScale2 = inpaint_nans(irisImageGrayScale);
irisImageGrayScale2(irisImageGrayScale2<0)=0;
irisImageGrayScale2(irisImageGrayScale2>255)=255;

        figure;imshow(irisImageGrayScale2,[])

[John D'Errico]

(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.

[Patrick Jackman]

 

[Patrick Jackman]

 

[Patrick Jackman]

Hello John
I have been looking at your inpainting algorithm as an option for coping with missing data in a three dimensional matrix. Do you have a three dimensional version of the algorithm that you can share with us? If not could you give some tips on how to modify the two dimensional version?
Thanks

[Cameron Sparr]

works great! Could use an updated example image.

[David Provencher]

Works great!

I'm wondering if there would be a way to exclude some NaNs from the interpolation (to keep them as NaNs). At the moment, I'm masking the results away, but I'd rather exclude them altogether. I thought about modifying nan_list and known_list, but it seems to me I'd run onto problems if the input matrix wasn't "full". Any help on this?
Thanks

(I'm using inpaint-nans in a stereo vision application to interpolate holes in the disparity maps. However, the images from which I compute disparity maps may have very large regions of invalid pixels which I don't need/want to interpolate).

[John D'Errico]

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.

[David Provencher]

Ok, I suspected this might be the case. I was already doing what you suggest, but I figured I might ask just in case.

Thanks for your answer!

[Tomas]

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.)

[John D'Errico]

inpaint_nans does not allow the idea of a non-uniform grid, making it perhaps more efficient and simpler to use. However, one could use gridfit under those circumstances, which DOES allow a general spacing. Of course, gridfit does not presume the data is sacrosanct as does inpaint_nans, but those deviations from a true interpolant will often be small if you use a relatively small smoothness parameter.

[Tomas]

I will definitely look up gridfit - thanks a lot!

[S K]

 

[S K]

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.

[jianfeng]

Good job!

[Willem-Jan de Goeij]

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.

[John D'Errico]

Willem - Personally, I think that 1.57982346157884756363579013421232435 is a slightly better value, although I am willing to negotiate on the last few digits. My point is, you are apparently trying to second guess the value predicted by less than 10% on a very uncertain value. How many angels can fit on the head of a pin anyway?

So feel perfectly free to pick whatever value you like there, when you write your own code. The value that was generated is the one consistent with the equations I specified, including the boundary conditions I chose. While those equations make some rational sense, I've won't claim that the predictions inpaint_nans makes are perfect, or that it will make all users blissfully happy. That would be impossible anyway, and I'm just too busy counting angels.

[Willem-Jan de Goeij]

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.

[John D'Errico]

For the answer to your questions, you need to dive more deeply into the equations, and how they arise. The factor of 2 you found actually appears to be correct and consistent in context.

If you prefer to make up any of a variety of arbitrary equations that make sense to you, of course you can get any result you like. The fact is, that will need to wait until you write your own code.

I'm sorry, but sitting here arguing with someone who has not bothered to understand the underlying code that a factor of 2 should or should not belong seems silly to me. For some reason you seem to be trying to reverse engineer the underlying equations from a few coefficients, and are then deciding if they make sense to you, without actually expending the effort. It is the wrong direction to go when you are trying to understand a piece of software. Start from the beginning, not the end.