Code covered by the BSD License

### Highlights frominpaint_nans

5.0

5.0 | 64 ratings Rate this file 330 Downloads (last 30 days) File Size: 273 KB File ID: #4551

# inpaint_nans

29 Feb 2004 (Updated 13 Aug 2012)

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.

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
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
04 Apr 2013
28 Nov 2012

David - inpaint_nans will fill in all nan elements. However, the springs method (method 4) does what I think you wish to see. It will do a CONSTANT extrapolation, to the extent that is possible to achieve in two dimensions.

Thus, in one dimension, we can easily see what a constant extrapolant will look like. It takes on the value of the extremal point on the curve. However, imagine a non-convex blob of a surface with two independent variables, that changes value around the perimeter? Here you must decide which path to follow outwards from that blob. Depending on you you proceed outwards, a constant extrapolant would differ. Inpaint_nans tries to resolve that conflict smoothly.

Finally, there is the case of intrapolation. This is where you have large internal holes in your array. Here inpaint_nans (with any method, including method 4) will fill in the hole as smoothly as possible.

28 Nov 2012
28 Nov 2012
28 Nov 2012

How do I stop extrapolation (interpolation only)?

26 Nov 2012
30 Oct 2012

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

11 Aug 2012

I had to do some repairs, to better handle vector input. I don't know if this is version related, as vector input was working in the past. I just sent in the new version.

05 Aug 2012

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.

22 Apr 2012

No, I don't use multiple regression techniques in here. There are some explanations provided with the code. all I can do is suggest you read them.

You don't need to be doing classical inpainting on an image to use this code. In fact, it was not designed for that class of problem at all. Any 1-d or 2-d array with NaN elements in it where you wish to interpolate them from their neighboring points will work.

22 Apr 2012

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

22 Apr 2012

did you use the multiple regression for this? would you tell me how the method works? thanks before

04 Apr 2012

fantastic, thanks John

04 Apr 2012

Well, it has been many years since I wrote that tool, but why not start with the finite difference approximation for del^4?

http://en.wikipedia.org/wiki/Biharmonic_equation

04 Apr 2012

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.

04 Apr 2012
16 Mar 2012

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

04 Feb 2012

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.

04 Feb 2012

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.

03 Feb 2012

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.

03 Feb 2012

A =
1 4 7
NaN 5 10
3 6 11

Lets call the NaN value x.

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.

16 Jan 2012

Good job!

22 Dec 2011

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.

22 Dec 2011
19 Dec 2011

I will definitely look up gridfit - thanks a lot!

19 Dec 2011

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

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

05 Dec 2011

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

01 Dec 2011

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.

01 Dec 2011

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

29 Nov 2011

works great! Could use an updated example image.

08 Nov 2011

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

08 Nov 2011
08 Nov 2011
24 Oct 2011

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

24 Oct 2011

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

04 Oct 2011

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.

04 Oct 2011

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?

30 Sep 2011

THANK YOU!!!!

29 Sep 2011
19 Sep 2011

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?

13 Sep 2011

Good work, much appreciated

02 Sep 2011

Works graeat

20 Aug 2011

Excellent job...this is what exactly I needed

24 May 2011
05 Apr 2011

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

11 Mar 2011
11 Mar 2011

Absolutely perfect!

12 Jan 2011

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.

12 Nov 2010

good work!

13 Oct 2010

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.

13 Oct 2010

Fantastic program. Exactly what I needed.

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

07 Jul 2010
12 May 2010
26 Apr 2010

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

26 Apr 2010

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

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)

28 Nov 2009
28 Sep 2009
09 Jun 2009
25 May 2009

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

25 May 2009
28 Mar 2009
24 Mar 2009
14 Jan 2009

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.

19 Dec 2008

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

19 Dec 2008

@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
19 Dec 2008
16 Dec 2008
07 Oct 2008

Thank you once again John,
exactly what I needed.

Please TMW: include this in next release of matlab!

16 Sep 2008

Thanks a lot and Good Contribution

13 Aug 2008

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 Apr 2008

Magical

08 Mar 2008

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

08 Feb 2008

Simply excellent. Nothing to declare.

30 Dec 2007

31 Oct 2007

realy useful

24 Sep 2007

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

17 Jan 2007

Great piece of work! really helped....

13 Oct 2006

great!

31 Aug 2006

Just what I was looking for! Many thanks!

21 Apr 2006

very fast, thanks!

21 Apr 2006

excellent work.

19 Apr 2006
16 Jun 2005

Really a good work. Thank you.

14 Feb 2005

Well done !

06 Dec 2004

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.

30 Oct 2004

excellent!

29 Oct 2004
10 Aug 2004

I love it!

28 Jun 2004

Nice! Especially method 4 using the virtual springs.

03 Mar 2004

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.

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

13 Aug 2012

Repaired problems for vector input.