File Exchange

inpaint_nans

version 1.1.0.0 (273 KB) by John D'Errico

John D'Errico (view profile)

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

Updated 13 Aug 2012

Editor's Note: This file was selected as MATLAB Central Pick of the Week

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.

Cite As

John D'Errico (2020). inpaint_nans (https://www.mathworks.com/matlabcentral/fileexchange/4551-inpaint_nans), MATLAB Central File Exchange. Retrieved .

Kin Sung Chan

Kin Sung Chan (view profile)

Thanks for the code shared by the author.

I have written an alternative solution that some others may possibly find it to be helpful.
https://www.mathworks.com/matlabcentral/fileexchange/75758-inpaint-nan-using-griddata

Hugo Laurell

Tino Merkel

Tino Merkel (view profile)

just what I was looking for

Ryan Potter

Ali Sinmaz

Ali Sinmaz (view profile)

Hayat Ullah Kakakhel

Hayat Ullah Kakakhel (view profile)

Andrea Quintarelli

Namwon Kim

Yogesh Regmi

Patrick Hergan

Patrick Hergan (view profile)

I added a few lines of code to cast the function input to Double. This alleviates a bug that I was experiencing (and also Bao Thai mentioned).

Simon Zeder

Shahar Grossbard

NS

NS (view profile)

If I have a datatime table wherein DATES are rows and COLUMNS are TIME and I need to interpolate PRICES ROW-WISE using this code, how to mention that interpolation should be done ROW-WISE.(After converting table into array)
T4 = inpaint_nans(T3)

Vanessa Li

Akram Ghoudi

Simão Marto

Maurizio Santoro

Paola Paruta

Alex

Alex (view profile)

What a great piece of code... well done!

Elif Yilmaz

Raphael Morency

Shakir Hussain

Sreelatha P

Very useful code

Ezra Huscher

Albert Schwinn

Zahra

Mina Masoud

Sirshendu Misra

Dario Solano

Dario Solano (view profile)

Hi Jhon,
Thank you so much for your amazing work, it has really helped me a lot during my PhD. I'm close to graduate and need to justify why some interpolated areas work very well and some others don't.
Is there any measurement of the quality of the interpolation I can use? Very isolated areas, for example, are "too interpolated" and I cannot trust them. Can you point me to an approach to quantify the quality of the interpolated points?
Thanks you so much.
Darío Solano.

Carles Otero

Zijie Zhao

Daehyeon Han

Lamin Barleben

Lamin Barleben (view profile)

Thank you very much. Its perfect.

Marco Debus

Stef_forrest

John Papantonis

John Papantonis (view profile)

Guillaume de Guyon

Guillaume de Guyon (view profile)

Perfect for my flow data reconstruction. Thank you.

Lauren Biermann

Lauren Biermann (view profile)

I tried a number of different approaches, but this method turned out to be the best for filling in ocean colour data gaps. Thank you!

chayma chaabani

chayma chaabani (view profile)

Just perfect, thank you!

marceline86

marceline86 (view profile)

Amazing! Thank you very much

kelian dascher-cousineau

Molly Glass

Bao Thai

Bao Thai (view profile)

Having trouble trying to inpaint over a RGB matrix. New beginner to matlab, wonder if there is a reason for this particular error??

Error using *
MTIMES is not fully supported for integer classes. At least one input must be scalar.
To compute elementwise TIMES, use TIMES (.*) instead.

Error in inpaint_nans (line 184)

Error in glarescript (line 21)
imd(:,:,1) = inpaint_nans(imd(:,:,1));

jb5cents

jb5cents (view profile)

Exactly what I needed, and fast! Thought about how to do it myself for an hour, and then glad I searched. Perfect for filling in the NaN's in remote sensing data.

Stef_forrest

Carlo Di Giovine

Ritabrata Thakur

Anton

Zoran Cenev

Terrific work!

ImagingScience

ImagingScience

Lionel

kiben17

rabbasi

SL

SL (view profile)

This is really useful contribution by the user!

Matlab should motivate the contributor, pay the contributor and include his code in the main software. It is really worth it. We should do everything to get him back here, since the tool needs maintenance. Its development should not be stop.

Andrew Salij

John D'Errico

John D'Errico (view profile)

When I originally wrote the code for the springs method, my plan was to include the diagonal terms, thinking they would be necessary. However, I think I found that it worked well enough without them, so I never added those terms in. They would only create matrices which were less full to solve, so slower code. But since I generally try to write the help first, it looks like I then forgot to take out that information.

Given that it works fine as is, I am not sure that it justifies a lower rating, but that is your opinion.

Ken Hughes

Ken Hughes (view profile)

The documentation (methods_of_inpaint_nans.m) for method four (springs) appears to differ from the actual code. According to the documentation, each value is connected to its immediate neighbours as well as those on the diagonal. I cannot anywhere in the code (apart from a comment) where diagonals are addressed.

Note that the example in method_of_inpaint_nans.m does include the diagonal terms and consequently gives a different answer than if I took the matrix A from that file and ran inpaint_nans(A, 4)

On the other hand, this function has been helpful in guiding the solution for my problem

Matt King

Matt King (view profile)

Thanks very much John for this great tool. We've used it before to great success but on my current application I'm getting 2-d array returned which still has NaNs in it. The NaNs that remain are fully enclosed by data so my understanding is that this should not happen. Are there conditions I should be aware of when infilling does not work?

>> version
8.5.0.197613 (R2015a)

>> rate_filled=inpaint_nans(rate,2);

>> sum(isnan(rate(:)))

ans =

10980

>> sum(isnan(rate_filled(:)))

ans =

5512

>> whos rate
Name Size Bytes Class Attributes

rate 659x698 3679856 double

Other methods leave similar, but not identical, numbers of NaNs.

Kin Sung Chan

INDRANIL SAAKI

kco

kco (view profile)

i'm getting this error when I try to call your function in my nxm matrix

inpaint_nans(ingdata)

"
Error using unique (line 29)
First parameter must be a square matrix

Error in inpaint_nans>identify_neighbors (line 550)
neighbors_list=unique(neighbors_list,'rows');

Error in inpaint_nans (line 155)
neighbors_list=identify_neighbors(n,m,nan_list,talks_to);
"

any idea as to why? I should add that often times when I run things i get the error "Error using unique (line 29)" even when I don't use that function in my script or function file.

thanks!

Bertrand Pinet

Thank you

Jeroen

Léo DUMAS

Léo DUMAS (view profile)

Excellent ! I needed exactly this and would have lost a lot of time to do something worse.
If one day you have time, you should write a paper on it. I imagine it would definitely be a reference function !

Abdulrahman

Abdulrahman (view profile)

I DONT HAVE TO TEST THE TOOL. I KNOW ITS AMAZING. JOHN YOU ARE AN ABSOLUTE LEGEND. THANK YOU SO MUCH

Stylianos Kritsotalakis

Ali A

Ali A (view profile)

Stavros Sklavenitis

John D'Errico

John D'Errico (view profile)

inpaint_nans does no smoothing. I have NEVER claimed that it does anything of the sort. If you have noise in your image, using inpaint_nans will leave a noisy image. In fact, the image will be completely unchanged.

inpaint_nans ONLY replaces NaN elements in the image with inpainted elements, SMOOTHLY interpolated from the neighboring elements around any hole.

So if your goal is to do image smoothing, you need to find a specific tool for that problem. For example, use conv2 to apply a blurring kernel to an array. Of course, conv2 will fail when there are NaN (missing) elements, so you may need to first apply inpaint_nans to an array, then apply conv2 to smooth it.

asmaa atalaa

asmaa atalaa (view profile)

I want the code to deal with a noisy image I have used the following code
G1(:,:) = inpaint_nans(G(:,:),2);

figure
subplot(1,3,1)
imshow(garden)

subplot(1,3,2)
imshow(uint8(G))
title 'Corrupted - 50%'

subplot(1,3,3)
imshow(uint8(G1))
title 'Inpainted Garden'
psnr(garden,uint8(G))
psnr(garden,uint8(G1))

ans =

18.3803

ans =

18.3803
And found that the PSNR remains the same

Whyjay Zheng

Whyjay Zheng (view profile)

Awesome function to process noises and NaNs.

Doppler Effect

Doppler Effect (view profile)

Amazing. I used this on 96-98% NaN and final result looks excellent. Of course, this is more about first impression without critical analysis. But I guess Your job worth, at worst case, three stars. Keep it going!

John D'Errico

John D'Errico (view profile)

BVP stands for Boundary Value Problem. In differential equations methods, given a differential equation defined over a field, with information provided at the boundaries of that field, this is called, logically, a BVP.

Inpaint_nans does exactly that (for most of the methods, though not the springs method, which is completely ad hoc but still useful.) Formulate a PDE over the field of the holes, provide information around the boundaries, and solve for the interior unknowns. This applies even for extrapolation. The explicit PDE chosen can be viewed as a simple diffusion one in the default case. Think about it as propagation of heat into the "holes", where the temperature is fixed around the boundaries.

As such, the solution is well posed always and efficiently solved as an elliptic problem. Solution methods are always simple finite difference approximations to the PDE and boundary conditions.

Phillip

Phillip (view profile)

Thanks for the reply John, I will use that for a citation. The other reason I asked is that I would like to include a brief summary of how the interpolation works, but I cannot quite figure it out from your description (specifically for the method = 2 option).

eg "Direct solve for del^2 BVP across holes... generate sparse array with second partials on row variable for each nan element"

... leaves me guessing a little. I understand the concept of a second partial derivative, but what is BVP? And does the method interpolate in just one direction? (you mention row variable, but then a little later mention column variable)

Any explanation you can offer to explain the workings of this wondrous tool would be much appreciated :)

B.k Sumedha

John D'Errico

John D'Errico (view profile)

No paper I've ever written that you can cite, nor do I know of any that describe the various methods employed by inpaint_nans.

However, you can cite file exchange submissions directly. Some years ago, we developed a pair of forms that made sense for citations, as shown on this page:

http://blogs.mathworks.com/community/2010/12/13/citing-file-exchange-submissions/

about file exchange citations. While they apply to my own gridfit instead, you can convert the citation to inpaint_nans easily enough.

Phillip

Phillip (view profile)

John, is there an academic citation that we can use for this tool?

Drewan Sanders

Drewan Sanders (view profile)

Saved my bacon! thanks

Mitchell Thayer

Mitchell Thayer (view profile)

Fantastic! I've been emulating satellite measurements from data we collected from aircraft, and this is perfect for interpolating between legs of the flight track. Well documented, with plug n play functionality. Thanks for sharing!

-:- Mitchell

John D'Errico

John D'Errico (view profile)

No. It is not linear interpolation, nor is it a spline. inpaint_nans was originally designed to work in 2-d, where linear interpolation would clearly not be an option. The goal is a smooth interpolant, generated by minimizing the sum of squares of the second derivative at each node, as measured by finite differences on the grid. The same approach is used in one dimension. The virtue is this is quite efficient to do using sparse linear algebra, even for large problems.

If you really desire linear interpolation, you can get it for the 1-d case, by using interp1. Simply extract the elements that are known, then use them to interpolate the NaN elements.

Rita

Rita (view profile)

Thanks for sharing this function.I used this function (method4 amd just one dimension vector)and compare the results with linear interpolation in matlab.The results are the same.Can I say that this function is linear interpolation for 1D inputs?

Rita

Rita (view profile)

Thanks for sharing this function.I used this function (method4 amd just one dimension vector)and compare the results with linear interpolation in matlab.The results are the same.Can I say that this function is linear interpolation for 1D inputs?

Egor

Egor (view profile)

Method 3 from this script has been ported to Python with n-dimesnional data support.
In case someone needs it - http://scikit-image.org/docs/dev/auto_examples/filters/plot_inpaint.html

akber basha

Varvara Osokina

Thank you!!

Phillip

Phillip (view profile)

Works beautifully, nice job

Maximilian

Maximilian (view profile)

Working extremely well, thanks a lot!

E. Cheynet

Vivek

Vivek (view profile)

Works amazingly well. Thanks. But I only wish to interpolate the data (without extrapolation). Is there a way of doing so? Method 4 is better than others for this, but it does extrapolate the data as well.

Moyses

John D'Errico

John D'Errico (view profile)

@haisheng - I'm confused as to what "example" you want to see for extrapolation.

Yes, it can extrapolate, depending on the method used. Most of the methods will give you linear extrapolation. Of course, linear extrapolation in two dimensions of a curvilinear surface with a potentially ragged boundary is difficult to quantify. But if you look at the shape of the result as it proceeds away from the boundary, it will be essentially linear to the extent that is possible.

Method 4 will give you a "constant" extrapolation behavior. Again, depending on the trajectory you follow away from a ragged edge on a curvilinear surface, "constant" is again difficult to quantify.

Of course, in one dimension, constant and linear are very much what they sound like.

You do nothing different from how you would use it otherwise, so I see no reason to give an example. You use the code just as you would use it normally. There are examples of use in the demos already.

Abhinna Behera

haisheng ZHOU

haisheng ZHOU (view profile)

good, thanks for your work. My question is how it works for data extrapolation , can you give an example? Thanks

Bo-An Chen

Bo-An Chen (view profile)

thank god i see you

Bruno

Daniel Anema

daniel

daniel (view profile)

WOW, props man I dig it!

Jan-Philipp Roth

Jan-Philipp Roth (view profile)

This has saved my day. Thank you!

Yorum

John D'Errico

John D'Errico (view profile)

Citing files on the FEX has come up often, enough so that we had a discussion about it, and came up with several schemes that seem viable. Find them at this link:

http://blogs.mathworks.com/community/2010/12/13/citing-file-exchange-submissions/

All you need do is modify the citation style you prefer to fit inpaint_nans, instead of gridfit.

Poulomi

Poulomi (view profile)

how to cite this work in papers ? Want to cite.

Poulomi

Ander Biguri

Ivy

Ivy

Ivy (view profile)

Hi John, your code is very useful for my work. I want to cite it in my paper, could you please tell me how to cite it properly? Thanks!

Egor

Egor (view profile)

Yeah, sorry. Was talking about method 3. On my test imagesest it gives best results.

John D'Errico

John D'Errico (view profile)

No. A biharmonic is only one of the options. It is not even the default method due to a slower speed.

Egor

Egor (view profile)

Seems like this method was used - http://www.ima.umn.edu/~damelin/biharmonic

Kaiyu

Raul

Karthik Karri

Karthik Karri (view profile)

I don't know how to thank you. I have been struggling to this on my own. Thanks a lot!!

Tiberius

Ivan Brezani

Ivan Brezani (view profile)

Just what I was looking for. Excellent job.

Debejyo Chakraborty

Debejyo Chakraborty (view profile)

Excellent job. Why not write a proper pdf document with all the equations? Is there a publication associated to this?

John D'Errico

John D'Errico (view profile)

Harish - sorry but I never wrote a paper, just used a logical idea to solve a problem that I had at the time.

There are inpainting papers that describe the general idea of inpainting using PDE models, but as I recall, those are usually Navier-Stokes based, nonlinear in some form depending on which terms they included. Those schemes were usually also proprietary. While that has some benefits in terms of the set of solutions that are admitted, the nonlinearity is a serious cost.

You can view the main scheme in this code as such an inpainting scheme, since there is a diffusion term in the NS equations. The nice thing is if we use pure diffusion to solve the problem, it becomes well posed and very easy to solve as a sparse large scale linear system of equations.

harish

harish (view profile)

Can someone link me to the mathematical background/papers that this code is based upon ? Would be of much help.Thanks.

Sven

Sven (view profile)

@arnold - You've described an iterative mode filter.

While you may think it feels similar to inpaint_nans, but as John has said, it's actually a completely different type of problem in the one way that matters - how to solve it (iteratively rather than linear algebra).

I suggest you give it a shot yourself - just work out how to:

1. Find a "border" NaN pixel
2. Find the mode of its neighbours
3. Fill it in
4. Repeat.

That would be a start. You can also find hints here which point to a faster and more stable implementation involving filters:

In order to use that, you'll want to run the filter over the whole image, and then "pack" the border NaN pixels back into the original and repeat.

arnold

arnold (view profile)

Thanks John. I understand what you are getting at but I do think that there can be a good approach which should gives a unique answer in almost any case (filling a nan area from the outside in i.e.). I disagree, that a random pick (from adjacent values with same occurence) would be unsatisfactory. I actually think it's the right thing to do if you don't have more information, since all it is is noise.

What kind of assumptions can be made of course primarily depends on the specific problem/dataset.

Thanks anyways, as usual some fine code of yours!

John D'Errico

John D'Errico (view profile)

Arnold - Thank you for your input, however your goal is not well-posed, in the sense that there may often be no unique answer and a random choice seems unsatisfactory. As well, since a linear algebraic solution will not be viable for this nonlinear goal, one would need to consider each missing element, then perusing its neighbors.

arnold

arnold (view profile)

nice function, thanks.
I could use a method which replaces a nan by the most common, discrete (!) neighbor value. I can think of various applications for that.
For instance: I have an array containing blobs with n discrete values [1,2,3,4...n] with some data missing at the intersections of those "areas". It makes no sense to fill the nan-gaps with an interpolated value.

I think this wouldn't be too hard to add. Either immediate neighbor analysis or even a defined distance weighting, bu the fill should be the exact value of one of the neighbors.

cheers

John D'Errico

John D'Errico (view profile)

Hamed - I'm sorry, but I don't do consulting in the comments. This is not the place for it. I told you what you need to do, and what I told you was not to simply run that included demo script, but to read it and to learn how to use this tool to solve your problems.

hamed abdulaziz

hamed abdulaziz (view profile)

I ran inpaint_nans and there is no problem but what I need to do is inpainting on the JPEG images(not surface),so I tried to run test_main but I am always have this error message!,any help for this purpose?

John D'Errico

John D'Errico (view profile)

Look at the examples I've provided with this tool. In there, I show how one can apply inpaint_nans to an image. In fact, I do exactly that. But you will need to use the tool as it is designed. Simply throwing an arbitrary jpg file at it will not work unless you do as I show.

Sven

Sven (view profile)

Hamed - this has nothing to do with JPEG files. Try to run the _example_ from inpaint_nans, and you'll see that it currently won't work for you either. This is because (as the error message suggests) the inpain_nans.m file is not currently on your path. You need to make sure inpain_nans is on your path.

hamed abdulaziz

hamed abdulaziz (view profile)

Thank you very Mr. John D'Errico,my problem is : I have dermoscopy image (skin images)which contains a hair I want to remove this hair by inpainting methods,for this purpose I downloaded inpaint_nans , but this code does not work with JPG image type?could you guide me please thank you in advance.

John D'Errico

hamed abdulaziz

hamed abdulaziz (view profile)

Mr. John D'Errico,you did excellent job.
I have an image of type JPG when I run test_main on it I have this error :

Undefined function 'inpaint_nans' for input arguments of type
'double'.

Sven

Sven (view profile)

Oh, maybe not enough info for that second typo. It's on line 141:
[bcclass,errorclass] = validstring(arg,valid);

Sven

Sven (view profile)

Very nice indeed. I've been using inpaint_nans for a while and was thinking of how to apply cyclic boundary constraints... all I needed to do was check a bit closer and see that this already exists. Very well done.

And John, just a note that there are a couple of typos in inpaint_nans_bc:

1. Help lines 1:3 spell nans as nsns.
2. "arg" should be "bcclass"

Finally, while using toroid BCs for my current application works just fine, the physical reality of my problem is more like a cylinder (ie, first and last columns should be treated as adjacent, whereas the remaining elements on the first and last rows can be left without constraint). Any thoughts on whether this functionality can be implemented easily? I *think* it would just be a case similar to toroid but with a different talks_to list for the first and last rows.

John D'Errico

John D'Errico (view profile)

Sorry. inpaint_nans will interpolate all the nan elements in your array from the remainder. You will need to find the gaps of interest, then use a tool like interp1, interpolating only those gaps you have identified.

Karolina

Karolina (view profile)

Hi,
I wanted to ask if it's possible to use inpaint_nans only to interpolate small gaps, sya I want to interpolate only if there is 5 or less consecutive nans in a column.
Karolina

John D'Errico

John D'Errico (view profile)

Dimitry - I'm sorry, but I lack the time or the energy to go into an in-depth discussion, nor do I really wish to put that much depth into the comments.

If you have read through the code, you will have seen many comments about del^4, often also called the biharmonic operator. I'm pretty sure that if you make the effort to derive a discretization of del^4, you might find some interesting coefficients.

Dimitry

Dimitry (view profile)

Mr. John D'Errico,
Please let me know how does method 3 and 4 work and how do they solve for the NaN using those interpolation techniques, and what the algorithm does in those methods. In addition, when I was using method 3 to solve for some NaN’s , I noticed that method 3 is trying to interpolate my data with NaN present values in there. I have noticed while going thought the code and I became confused with some of the code, please let me know what is going on after if nl>0, where you are solving for the sparse matrix and you have a bunch of constants in the equation
“fda=sparse(repmat(all_list(L,1),1,13), ...
repmat(all_list(L,1),1,13) + ...
repmat([-2*n,-n-1,-n,-n+1,-2,-1,0,1,2,n-1,n,n+1,2*n],nl,1), ...
repmat([1 2 -8 2 1 -8 20 -8 1 2 -8 2 1],nl,1),nm,nm);”
Please let me know what do those constants do and why did you select them. Lastly please let me know if you can in-depth on how does method 3 and 4 work.

-D

Dimitry

Dimitry (view profile)

Sorry not Eric but John

besbesmany besbesmany

besbesmany besbesmany (view profile)

what is the algorithms used in details, is there description about methods used in details?

I used the code for error concealment on video transmission, but I don't know how to support the method and formulas behind that, I'd be thankful if you could provide me the algorithm and mathematical model which is used for interpolation

Han

Han

Han (view profile)

works pretty well and it's fast!

christhechris

John D'Errico

John D'Errico (view profile)

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.

David C

David C

David C

David C (view profile)

How do I stop extrapolation (interpolation only)?

Hans

MoDu

MoDu (view profile)

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

John D'Errico

John D'Errico (view profile)

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.

Oleg Komarov

Oleg Komarov (view profile)

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.

John D'Errico

John D'Errico (view profile)

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.

Isti

Isti (view profile)

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

Isti

Isti (view profile)

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

Laurence

Laurence (view profile)

fantastic, thanks John

John D'Errico

John D'Errico (view profile)

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

Laurence

Laurence (view profile)

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.

Laurence

Sobhan

Sobhan (view profile)

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

John D'Errico

John D'Errico (view profile)

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.

Willem-Jan de Goeij

Willem-Jan de Goeij (view profile)

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

John D'Errico (view profile)

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

Willem-Jan de Goeij (view profile)

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.

jianfeng

Good job!

S K

S K (view profile)

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.

S K

Tomas

Tomas (view profile)

I will definitely look up gridfit - thanks a lot!

John D'Errico

John D'Errico (view profile)

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

Tomas (view profile)

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

David Provencher

David Provencher (view profile)

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

John D'Errico

John D'Errico (view profile)

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

David Provencher (view profile)

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

Cameron Sparr

Cameron Sparr (view profile)

works great! Could use an updated example image.

Patrick Jackman

Patrick Jackman (view profile)

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

Patrick Jackman

Patrick Jackman

John D'Errico

John D'Errico (view profile)

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

Paulo

Paulo (view profile)

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

John D'Errico (view profile)

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.

Kaah

Kaah (view profile)

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?

Claire

THANK YOU!!!!

Michael Völker

Vineet Mehta

Vineet Mehta (view profile)

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?

TAFKARS

TAFKARS (view profile)

Good work, much appreciated

Trevor

Trevor (view profile)

Works graeat

Venkateswara Rao Narukull

Venkateswara Rao Narukull (view profile)

Excellent job...this is what exactly I needed

Tobias Kienzler

Tannistha

Tannistha (view profile)

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

Matt Patten

Matt Patten

Matt Patten (view profile)

Absolutely perfect!

Francis Esmonde-White

Francis Esmonde-White (view profile)

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.

Paolo

good work!

John D'Errico

John D'Errico (view profile)

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.

Daniel

Daniel (view profile)

Fantastic program. Exactly what I needed.

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

Nitin

Alexandra

Bryant Svedin

Bryant Svedin (view profile)

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

John D'Errico

John D'Errico (view profile)

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

Bryant Svedin (view profile)

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)

Raghavendra

Jon

Andrey Rubshtein

Stefan

Stefan (view profile)

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

Stefan

Stuart

Karel

Karel (view profile)

Randall Lawerence

Randall Lawerence (view profile)

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.

Kenneth Eaton

Kenneth Eaton (view profile)

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

Kenneth Eaton

Kenneth Eaton (view profile)

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

alain boyer

V. Poor

Kenneth Eaton

Kenneth Eaton (view profile)

Frederic Moisy

Thank you once again John,
exactly what I needed.

Please TMW: include this in next release of matlab!

Thanks a lot and Good Contribution

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

Bob Field

Magical

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

D. G.

Simply excellent. Nothing to declare.

Sara Alexander

martin klöppel

realy useful

Emily Spahn

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

Amar chawla

Great piece of work! really helped....

mario fiorini

great!

Just what I was looking for! Many thanks!

Ian Howat

very fast, thanks!

Rajeev Srivastava

excellent work.

sacrosancttayyar sacrosancttayyar

Cris C.

Really a good work. Thank you.

K. Sturm

Well done !

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.

jing tian

excellent!

d d

Tom Reiser

I love it!

Evan Zamir

Nice! Especially method 4 using the virtual springs.

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.

 11 Aug 2012 1.1.0.0 Repaired problems for vector input. 28 Jun 2006 1.0.0.0 Created Select directory structure 17 Apr 2006 Release 2: Bug fix for method 5. Clean up help. Add HTML, screenshot, examples, demo comparison to griddata. 18 Jul 2005 This version of inpaint_nans will also handle inpainting (interpolating/extrapolating) simple vectors with NaN elements.
MATLAB Release Compatibility
Created with R10
Compatible with any release
Platform Compatibility
Windows macOS Linux