Drawing in the images

Hi

I want to develop a procedure to remove some inpainted text from images, i.e. I have to estimate the inpainted pixels. I will do that with first an imputation step and then applying SVD (and perhaps later further improvements).

The imputations step just have to give an initial guess of the inpainted pixels. I thought of applying a gaussian filter to get estimates of the inpainted pixels, but I think this does not give good results.

Does somebody know another way to get good inital guesses, i.e. imputations?

Answer 1

[Image Analyst]

I don't know how "imputation" applies to an image. What algorithm is that?

If the text was inpainted, and the inpainting was good, it will smear the surrounding through the text and it will basically disappear. It can be detected however - you can't get back the original text, but you can tell where the inpainting occurred. There are some forensic methods to detect such alterations in an image. And there are methods people use to try to prevent that - those methods are called anti-forensics. And there are even, believe it or not, forensic methods that try to detect when anti-forensic processed have been employed. These are called "counter anti-forensics". You might think I'm joking, but I'm not. Earlier this year I attended a few papers from a conference on it at a larger symposium.

I don't know how you'd use SVD. Why do you think you can? Have you seen a paper on that? Otherwise do a web search for "image forensics". The think is, I don't know how you can remove the inpainting. Once you detect where it was applied, what do you mean by "remove" it? Do you mean replace with black pixels, to make a guesstimate at what the original text might have looked like? That may or may not be possible depending on how far out the inpainting mask outline was.

[Sepp]

Thank you for your answer, Image Analyst.

Imputation is not an algorithm, I just named the step in this way.

In the imputation step I just want initial guesses for the missing (inpainted) pixels. It is not just inpainted text but all kind of inpaintings, e.g. scratches.

To be clear, I know where the inpainting is (I have a mask) and I just want good estimation for the inpainted pixels and the imputation step just gives an initial estimation.

That means I have e.g. a landscape image and some black scratches or text over it and I know which pixels are affected by t he scratches or text. With removing the inpainting I mean guessing the initial value of the pixel without the inpainting.

[Sepp]

I got three solutions:

Proposal 1: Gaussian filter of large radius computed by assigning a null weight to any pixel that belongs to the inpainted area (so that the color of the text you want to get rid of does not "bleed").

Proposal 2: Colour of the nearest pixel which does not belong to the inpainted area.

Proposal 3: For each pixel, randomly sample a handful of points outside of the inpainted area, but not too far away from this pixel. Average the pixel values, weighted by the distance to the pixel.

Do you have an idea how I can realize this computationally efficient? I have an original image, the inpainting areas are 0 (black). And I have a mask with the same size as the original image. If an pixel is inpainted, the corresponding entry of the mask is 1, else 0.

[Image Analyst]

I'm beginning to think your definition of inpainting is different than everyone else's. If this is your original image

99 88 77
82  5 82
79 88 93

And the 5 in the middle is the "scratch", then this is the inpainted image:

99 88 77
82 85 82
79 88 93

Now, there is no way that you could recover the 5 if all you had was the second image, where there is an 85 where the 5 used to be, unless you could somehow first, detect that the middle pixel had been inpainted, and second that there should be a 5 in that location. The 85 is the new, inpainted pixel value, and how could you know that it was previously a 5???

[Sepp]

So first, I have a corresponding mask:

0 0 0
0 1 0
0 0 0

Of course the inpainted 85 cannot be restored exactly to the 5, but I need only a guess from the neighbouring pixels for example. Moreover, I assume that the structure in the image is similar, i.e. that a pixel have similar value as a neighbouring pixel. That means it is unlikely that there is a 5 in the middle and in the neighbourhood much bigger values. So we have a 80 in the middle of the original image and the inpainted value is a 0, i.e. original image:

99 88 77
82 80 82
79 88 93

inpainted image:

99 88 77
82  0 82
79 88 93

Now we can restore the inpainted pixel by just looking at the neighbourhood as I wrote in my 3 proposals above.

Do you have an idea how I can efficiently implement the 3 proposals? Perhaps using convolution? And how can I assign a null weight to any inpainted pixel in the gaussian filter? As I said I have a mask specifying where the inpainted pixels are.

[Image Analyst]

OK, as I suspected. Your terminology is 180 degrees opposite to the standard in the image processing field. You're calling the darker scratches or text the inpainted pixels rather than the "repaired" pixels. Your original dark pixels are not inpainted - they're original, or they were pixels that were painted (not inpainted) or "burned into" (more common lingo) the image. They are the original, initial pixels that you're starting with, and then you try to repair the image by removing them by filling in with surrounding pixels (inpainting).

But anyway, now that I know what you mean, you can run my modified median filter for Salt and Pepper noise. Basically you get a binary image of where the anomalous pixels are. Then you get a median filter of the whole image. Then you set the repaired image to the original first to initialize it. Then you replace only locations identified as anomalous in the image with the corresponding pixels from the median filtered image. See attached demos for color and monochrome.

[Sepp]

Thank you Image Analyst. Now we are talking of the same thing. I have some last questions, hoping that you can help.

1. Why using a median and not a gaussian filter?

2. Should I not assign a null weight to any anomalous pixel in the gaussian/median filter? And if yes, how can I do that?

3. It would save runtime if I would only apply the filter to the anomalous pixels + some neighbourhood pixels and not to the whole image. Is this possible?

4. Unfortunately I'm not able to use the image processing toolbox, so I have to use conv2. For a gaussian filter I will use

function f=gaussian2d(N,sigma)
  % N is grid size, sigma speaks for itself
 [x y]=meshgrid(round(-N/2):round(N/2), round(-N/2):round(N/2));
 f=exp(-x.^2/(2*sigma^2)-y.^2/(2*sigma^2));
 f=f./sum(f(:));

filtered_signal=conv2(Im,gaussian2d(N,sig),'same');

How can this be adapted to a median filter?

[Sepp]

Sorry for disturbing you again, Image Analyst, but do you have any suggestions?

Have a nice weekend.

[Image Analyst]

1. You can do that if you want. Gaussian will weight the up/down/left/right more than the corners but I think will blur the image more. Median's claim to fame is that it reduces noise wtihout blurring edges as much. But if you have a love for Gaussians, go ahead. It might not make much noticeable difference, especially for sparse noise.

2. You should not count the anomalous pixel in the mean. For median it doesn't much matter because you'd just be taking the 4th pixel or 5th pixel depending on whether you excluded it or included it. But for the mean, you don't want to consider an outlier because it will affect the mean, possibly by a great deal. To exclude, just use a kernel with the center pixel of 0.

kernel = [1,1,1; 1,0,1; 1,1,1];
out = conv2(double(in), kernel, 'same');

3. You have to filter the whole image anyway. So you can quit there, and with an image blurred everywhere, or you can spend a little extra time and transfer only those pixels that are identified as noise. Take a little longer but only noise pixels are altered, not your good original.

4. The difference is slight. with uniform, all 8 pixels have the same 0.125 value. With Gaussian, the corners are slightly less than the N, S, E, and West pixels. But you might not notice much difference.

[Sepp]

Thank you so much, Image Analyst, and please excuse my late response. I have some further comments to your last solution and some new questions (the really last ones).

2. For excluding the anomalous pixel in the mean kernel you said, I should just set the center pixel of the kernel to 0. But lets say the center pixel and some of the neighborhood pixels are anomalous. If I only set the center pixel to 0 then the anomalous pixels in the neighborhood get still counted if the kernel lies on top of the center anomalous pixel. Am I wrong?

3. I think you misunderstood my questions (or I misunderstood your answer). My idea was to apply the filter only to the anomalous pixels and some neighborhood of them for saving runtime and then keep the original "good" pixels and replace only the filtered anomalous pixels. But I don't know how I can filter only the anomalous pixels + some neighborhood. Doy ou have an idea how to do that?

5. Would a filter based on Fourier Transform (low pass, high pass, band pass) also be an option?

6. I've read that one can select the best filter parameters by using histograms. How can histograms be used for that?

7. The best parameters for the filter can also be chosen by cross-validation. Currently, I'm tuning the filter by just setting the parameters to different values and then running the filter for 10 images and calculating the mean error and choosing the parameters with lowest error. But this is not cross-validation. In cross-validation I would had to split the 10 images to a training and test set and first train the parameters on the training set and then using the test set for testing it.

But how can I use the training set for training the parameters? I really don't know. The only thing I see is to run over the images and calculating the error but this is not training.

8. The last question. ;) I think it could be a good idea to calculate in advance the size of the biggest are of anomalous pixels. In this way, for a bigger size the kernel could be chosen larger and for a smaller size the kernel could be chosen smaller. But how can I calculate the size of such an area? Let's say I have the following matrix:

0 1 0 0
1 0 0 0
0 0 1 1
0 1 1 1

The biggest area of 1s is 5 (bottom right) but how can I calculate this without going through every pixel (which would require too much runtime)?

[Image Analyst]

2. Correct. You need to identify anomalous pixels in advance then set them to zero. Then you need to do two convolutions, not one, to get the mean of the window.

3. My demos that I attached show you how to do that.

5. Heck no! You've got to be kidding. Absolutely not.

6. Look for bins with counts that are a lot separated from the rest. That may or may not be a good way depending on the image and how many noise pixels there are and if it's global noise or local. 7. Not sure.

8. Just threshold, call bwlabel, and then regionprops.

[Sepp]

Thank you very much Image Analyst.

2. The anomalous pixels are set to once. So far so good. How do you mean two convolutions? Two convolutions on the original image with the same kernel?

6. As I understand a histogram is a barchart of the count of pixels of every tone of gray that occurs in the image. I will take the histogram of the original image. Now, if I have selected such different bins as you proposed, what should I then do? Sorry, but I don't get the point.

[Image Analyst]

First you need to somehow flag "bad" pixels. For example set them to -1, which means you have to convert from uint8 to double. Why flag? Because if you just set them to zero, there might possibly be "good" pixels that have that value and you don't want to ignore those. If you do a straight convolution by convolving with ones(3) then you get the sum of the pixels in the window. If none are black, then divide by 9 and you're done. But what if there are a lot of bad pixels in the window, say 4 of them and only 5 "good" pixels. So if you get the mean by dividing by 9, that's not right - you'd need to divide by 5 (the number of good pixels) in order to get the mean of only the good pixels. So one convolution counts the number of good pixels, and the other sums the good pixels, then you divide them. Let's say that anything over 250 is a bad pixel. Untested code just off the top of my head:

badPixels = grayImage > 250;
% Now flag bad pixels
tempImage = double(grayImage);
tempImage(badPixels) = -1;
% Now count number of good pixels
kernel = ones(3);
goodPixels = double(tempImage ~= -1);
numGoodPixels = conv2(goodPixels, kernel, 'same');
% Sum up the gray values over the good pixels
tempImage = tempImage .* double(goodPixels);
sumImage = conv2(tempImage, kernel, 'same');
% Now divide to get the means over ONLY the good pixels.
repairedImage = sumImage ./ numGoodPixels; % A double image
repairedImageUint8 = uint8(repairedImage);
imshow(repairedImageUint8);

[Sepp]

Very good explanation, thank you, Image Analyst. This is now clear and I try to implement it. I will let you know about my progress.

Do you perhaps have also some help for point 6 (histogram)? Would be very nice.

[Image Analyst]

If you have a uniform image, you might be able to identify outlier pixels if they are substantially different. For a Gaussian around 150 +/- 10, and then a spike at 255.

[Sepp]

Ok, but why does it help to detect outlier pixels for finding the right parameters of the filter?

[Image Analyst]

Not sure what you mean. If 99% of your pixels are in the 140-160 range, don't you think that a few pixels with values up around 250 would be outliers? I do. Once you've identified outliers, you can adjust other parameters, like window size, and observe the effects. Generally the bigger the window, the blurrier will the repaired image be.

[Sepp]

Ah now I think I start to understand. With window size you mean the size of the kernel, right?

You wrote "For a Gaussian around 150 +/- 10, and then a spike at 255.". This I don't understand. I will detect outlier pixels on my original image so why do you relate it to gaussian?

Moreover, I don't see why or how I can adjust the window (or kernel) size dependent on the number of outliers. So let's say I have a lot of outliers, so should I make the window larger? I also only know the number of outliers but not it they are near each other or form a region.

Just a sidenote: I found the roifilt2 method. This seems to be very good for filtering, so I don't have to do 2 times convolution. Do you agree?

[Image Analyst]

Run this code. Let me know if you still don't understand afterwards.

% Create a uniform image of gray value 150.
grayImage = 150 * ones([400,400], 'uint8');
% Add noise
noisyImage = imnoise(grayImage, 'Gaussian', 0, .001);

% Add outliers at random locations.
badPixelLocations = randperm(numel(grayImage), 8000);
noisyImage(badPixelLocations) = 255;

sd = std(double(noisyImage(:)))
subplot(2, 2, 1); 
imshow(grayImage);
axis on;
title('Original Grayscale Image', 'FontSize', fontSize);
% Enlarge figure to full screen.
set(gcf, 'Units', 'Normalized', 'OuterPosition', [0 0 1 1]);
% Give a name to the title bar.
set(gcf, 'Name', 'Demo by ImageAnalyst', 'NumberTitle', 'Off') 

% Show noisy image
subplot(2, 2, 2); 
imshow(noisyImage);
axis on;
title('Noisy Image', 'FontSize', fontSize);

% Let's compute and display the histogram.
[pixelCount, grayLevels] = imhist(noisyImage);
subplot(2, 2, 3:4); 
bar(grayLevels, pixelCount);
grid on;
title('Histogram of noisy image.  Note spike at 255', 'FontSize', fontSize);
xlim([0 grayLevels(end)]); % Scale x axis manually.

Why do you think you need to adjust the windows size based on the number of outliers? That will make it slow and it's probably not really necessary unless you have extraordinary amounts of noise, like you can barely see your image.

roifill would not be appropriate in this case. First you'd have to create a binary image (like with the above algorithm), but then you'd have to dilate it and then it would apply an algorithm to fill the noise pixel in a pretty inefficient way. It's no good unless you have large connected regions to fill, not if you have single noise pixels. Convolutions are very very fast and efficient, even more so for separable kernels (like a uniform box). It's the way to go.

[Sepp]

Thank you for the demo. Now I saw the spikes at 150 and 255 in the histogram.

I thought that have to adjust the window size based on the number of outliers because you wrote "Once you've identified outliers, you can adjust other parameters, like window size, and observe the effects.".

But I think I misunderstood you. You mean that I just change the parameters of the filter and then look again at the histogram. Right? And then choosing the parameters which makes the histogram the most smoothly?

I meant roifilt2 and not roifill. ;) Do you think roifilt2 is also a bad idea?

Regarding roifill. I also tried out this one. I did roifill(image, mask) where the ones in the mask corresponds to anomalous pixels and the 0 to good pixels but I did not see any effect. Why? When I just put ~mask i.e. roifill(image, ~mask) then all except the anomalous pixels are somewhat blurred as I expected. But the other way round, just giving mask as input did not work.

[Image Analyst]

You only look at the histogram once, and that is before everything starts so that you can identify outliers, in those certain images where outliers CAN be identified by the histogram, which is not all images. No need to look at the histogram of the repaired images, unless you want to.

roifilt() is probably okay. From the sounds of it, it appears to do the same thing I said. Filter one image, then return an image which is the original image except in pixels identified by the binary image which will be the filtered image pixels.

The reason you didn't see any change when you used roifill is discussed in Steve's blog: http://blogs.mathworks.com/steve/2014/03/18/roifill-design-critique/

[Sepp]

I've read Steve's blog and now the problem with roifill is clear. "But it actually replaces only the interior pixels of the mask."

roifilt2 (not roifill) could be perhaps a bit faster.

Regarding the histogram I'm still not sure how to use it. So let's say I've detected outliers by using the histogram before everything starts. But how can I then incorporate this information in the further process?

[Image Analyst]

By looking at the histogram, if you have an image with a fairly narrow histogram, you can identify noise, like noise at 255 or 0 or greater or less than some value. If you would have run my demo, you would have seen a line like

% Find the noise.  It will have a gray level of either 0 or 255.
noiseImage = (noisyImage == 0 | noisyImage == 255);

That's how.

[Sepp]

Yes I have seen the line and the noise but my question is what to do then further. ;) So just treat pixels with the noise value (e.g. 255) as anomalous?

[Image Analyst]

Yes. Every pixel where noiseImage is "true" or "1" means that it's a noise pixel, not a true value of what the image should be.

[Sepp]

Ok, now I understand. But the mask pointing to the anomalous pixels is given to me, so I don't have to search for further anomalous pixels.

However, I will try to implement everything and will let you knwo about the progress.

[Sepp]

I just tried to apply the code you posted above for assigning a null weight to anomalous pixels. Namely the following code:

badPixels = grayImage > 250;
% Now flag bad pixels
tempImage = double(grayImage);
tempImage(badPixels) = -1;
% Now count number of good pixels
kernel = ones(3);
goodPixels = double(tempImage ~= -1);
numGoodPixels = conv2(goodPixels, kernel, 'same');
% Sum up the gray values over the good pixels
tempImage = tempImage .* double(goodPixels);
sumImage = conv2(tempImage, kernel, 'same');
% Now divide to get the means over ONLY the good pixels.
repairedImage = sumImage ./ numGoodPixels; % A double image
repairedImageUint8 = uint8(repairedImage);
imshow(repairedImageUint8);

If I use a gaussian kernel, it works perfectly. But if I use a mean kernel as in the above code I get in the resulting images NaN for some pixel. I think this is due to division by zero. How can I repair this? Just substituting eps for zero values in numGoodPixels?

By the way, if I'm using your code for gaussian filtering, i.e. replacing the kernel by a gaussian kernel, do I then still need the following line?

tempImage = tempImage .* double(goodPixels);

[Image Analyst]

I'll try it after you attach your noisy image. If there are no good pixels in the window, then I guess maybe you should just leave the pixels alone. To fix that, before you create the repaired image you should just do

% Find window locations with no good pixels
noGoodPixels = numGoodPixels == 0;
% Set them to 9 (or any non-zero value) 
% so that when we divide by numGoodPixels
% it won't be 0 / 0, which is undefined (infinity)
numGoodPixels(noGoodPixels) = numel(kernel);

[Sepp]

Would it not also work to do the following?

numGoodPixels(numGoodPixels == 0) = eps;

Then I also have no division by zero.

By the way, I achieve the best result using a gaussian filter (and not median or mean).

When I'm using a gaussian filter, I don't get any division by zero with your approach. Why?

[Image Analyst]

So rather than avoid the problem, you just get values of infinity.

I doubt that there is much visible difference for small holes using any of those values.

What you said about Gaussian does not make sense. If there are no "good" pixels in the window, then there are no good pixels in the window and it makes absolutely no difference what the window values are.

Again, attach your image where it fails, and your code if you don't want me to keep guessing because you're making me work "blind". I don't think I've ever had a discussion on image processing go 30 replies without the poster ever even uploading an image.

[Sepp]

Sorry for my late answer. I've solved the problem. I've made a small mistake and therefore it failed. Now it works perfectly. Again, thank you very much for your help.