5.0

5.0 | 56 ratings Rate this file 212 Downloads (last 30 days) File Size: 269.05 KB File ID: #4551
image thumbnail

inpaint_nans

by John D'Errico

 

29 Feb 2004 (Updated 28 Jun 2006)

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

Editor's Notes:


This is a File Exchange Select file.

Select files are submissions that have been peer-reviewed and approved as meeting a high standard of utility and quality.

| Watch this File

File Information
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
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (76)
03 Mar 2004 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.

28 Jun 2004 Evan Zamir

Nice! Especially method 4 using the virtual springs.

10 Aug 2004 Tom Reiser

I love it!

29 Oct 2004 d d  
30 Oct 2004 jing tian

excellent!

06 Dec 2004 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.

14 Feb 2005 K. Sturm

Well done !

16 Jun 2005 Cris C.

Really a good work. Thank you.

19 Apr 2006 sacrosancttayyar sacrosancttayyar  
21 Apr 2006 Rajeev Srivastava

excellent work.

21 Apr 2006 Ian Howat

very fast, thanks!

31 Aug 2006 Mike Kadour

Just what I was looking for! Many thanks!

13 Oct 2006 mario fiorini

great!

17 Jan 2007 Amar chawla

Great piece of work! really helped....

24 Sep 2007 Emily Spahn

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

31 Oct 2007 martin klöppel

realy useful

30 Dec 2007 Sara Alexander

Really helpful with minimal fuss!

08 Feb 2008 D. G.

Simply excellent. Nothing to declare.

08 Mar 2008 Carlos Adrián Vargas Aguilera

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

16 Apr 2008 Bob Field

Magical

13 Aug 2008 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

16 Sep 2008 Sherif Abd El-Gawad

Thanks a lot and Good Contribution

07 Oct 2008 Frederic Moisy

Thank you once again John,
exactly what I needed.

Please TMW: include this in next release of matlab!

16 Dec 2008 Kenneth Eaton  
19 Dec 2008 V. Poor  
19 Dec 2008 alain boyer  
19 Dec 2008 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.

19 Dec 2008 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."

14 Jan 2009 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.

24 Mar 2009 Karel  
28 Mar 2009 Stuart  
25 May 2009 Stefan  
25 May 2009 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

09 Jun 2009 Andrey Rubshtein  
28 Sep 2009 Jon  
28 Nov 2009 Raghavendra  
26 Apr 2010 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)

26 Apr 2010 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.

26 Apr 2010 Bryant Svedin

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

12 May 2010 Alexandra  
07 Jul 2010 Nitin Kumar  
13 Oct 2010 Daniel

Fantastic program. Exactly what I needed.

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

13 Oct 2010 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.

12 Nov 2010 Paolo

good work!

12 Jan 2011 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.

11 Mar 2011 Matt Patten

Absolutely perfect!

11 Mar 2011 Matt Patten  
05 Apr 2011 Tannistha

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

24 May 2011 Tobias Kienzler  
20 Aug 2011 Venkateswara Rao Narukull

Excellent job...this is what exactly I needed

02 Sep 2011 Trevor

Works graeat

13 Sep 2011 TAFKARS

Good work, much appreciated

19 Sep 2011 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?

29 Sep 2011 Michael Völker  
30 Sep 2011 Claire

THANK YOU!!!!

04 Oct 2011 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?

04 Oct 2011 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.

24 Oct 2011 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,[])

24 Oct 2011 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.

08 Nov 2011 Patrick Jackman  
08 Nov 2011 Patrick Jackman  
08 Nov 2011 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

29 Nov 2011 Cameron Sparr

works great! Could use an updated example image.

01 Dec 2011 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).

01 Dec 2011 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.

05 Dec 2011 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!

19 Dec 2011 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.)

19 Dec 2011 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.

19 Dec 2011 Tomas

I will definitely look up gridfit - thanks a lot!

22 Dec 2011 S K  
22 Dec 2011 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.

16 Jan 2012 jianfeng

Good job!

03 Feb 2012 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.

03 Feb 2012 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.

04 Feb 2012 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.

04 Feb 2012 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.

Please login to add a comment or rating.
Updates
18 Jul 2005

This version of inpaint_nans will also handle
inpainting (interpolating/extrapolating) simple
vectors with NaN elements.

17 Apr 2006

Release 2:
Bug fix for method 5. Clean up help. Add HTML, screenshot, examples, demo comparison to griddata.

28 Jun 2006

Created Select directory structure

Tag Activity for this File
Tag Applied By Date/Time
inpainting John D'Errico 25 Jan 2012 09:12:56
interpolation John D'Errico 25 Jan 2012 09:12:56
holes John D'Errico 25 Jan 2012 09:12:56
missing values image artifacts John D'Errico 25 Jan 2012 09:12:56
missing values John D'Errico 25 Jan 2012 09:19:08
image artifacts John D'Errico 25 Jan 2012 09:19:08

Contact us at files@mathworks.com