scott wrote:
> 
> My point was that the following are all valid solutions to the source 
> image:
> 
> {3,3,3,3,3,3,3,3}
> {2,4,2,4,2,4,2,4}
> {1,5,1,5,1,5,1,5}
> {6,0,6,0,6,0,6,0}
> 
> In this case even the centre pixels could be anywhere from 0 to 6, and 
> the "appearance" of the image is radically different in each case.  
> Surely this is exactly the sort of detail a "deblurring" filter needs to 
> recover, but it seems impossible.

Ok, I think I better understand what you were asking now.  To answer it 
I think I should get into some stuff I had alluded to earlier (i.e. "use 
an image prior").  This will probably be another semi-lengthy post, and 
I'll break it into two parts:

1) Looking at your example in the frequency domain to get a good 
theoretical grasp of what's happening.

2) Some discussion of the practical (as opposed to theoretical) issues 
and solutions.

---------- 1) theoretical discussion

Throughout this section I'll be assuming that the image is "cyclic" so 
that it's easy to analyze it in the frequency domain.  Fortunately your 
examples above still work in a cyclic image.

As you've noted, it's possible to reconstruct multiple source images in 
your example.  The reason for this is that you happened to choose an 
"unlucky" kernel.  The reason why it's unlucky can be seen pretty easily 
by looking at the kernel in frequency space.

In using the FFT on the kernel, I has to pad the kernel to make it the 
same size as the image, yielding the padded kernel:

k = {0, 0, 0, 1, 2, 1, 0, 0}

If we now calculate abs(fft(k)), we get:

kf = {4.0, 3.4, 2.0, 0.6, 0.0, 0.6, 2.0, 3.4}

The key thing to notice here is that this contains a element which is 
zero.  This means that the convolution kernel will "kill" certain 
frequencies in the source image.  Basically, we'll get the same result 
image for any source-image + c*ifft([0 0 0 0 1 0 0 0]). Unsurprisingly, 
if we calculate 8*ifft([0 0 0 0 1 0 0 0]) we get:

{1, -1, 1, -1, 1, -1, 1, -1}

Which perfectly explains the nature of the examples you gave which all 
convolve to the same result image.  IIRC most kernels in practice won't 
contain exact zeros like this, and it turns out that even a slightly 
different version of your kernel wouldn't have had this problem:

abs(fft([0 0 0 0.01 1.98 1.01 0 0]))
   = {4.0, 3.4, 1.98, 0.55, 0.04, 0.55, 1.98, 3.4}

It also wouldn't work on images which are an odd number of pixels across 
(still assuming a cyclic image of course), which is possible why you 
chose an image that was an even number of pixels across.

In the code snipped I gave to deconvolve your example, I dealt with this 
issue in a very simple way:

ifft(fft(y)./(fft(k2)+1e-8))

It's the +1e-8 that was the key here, and in your example it's necessary 
to prevent a divide by zero.  The effect of this is that the 
deconvolution didn't "hallucinate" any frequencies that weren't in the 
result image, even if they would technically also be correct 
deconvolutions.  This is why it gave the {3, 3, 3, 3, 3, 3, 3, 3} answer 
rather than one of the others you gave.


---------- 2) practical discussion

As far as I'm aware in practice having a kernel like yours which happens 
to kill certain "unlucky" frequencies isn't really an issue.  What can 
be an issue is that your kernel will suppress high frequencies to the 
point that they fall below the accuracy of your camera sensor (or even 
numerical precision).  This is why undoing a depth of field blur won't 
always be possible (even if everything is at the same depth), since the 
blur kernel in that case heavily suppresses high frequencies.  This 
means that only a limited amount of deblurring is possible (as an aside, 
there's also been work on designing camera apertures so as to minimize 
this).

Fortunately in the case of blur from camera shake the kernel is normally 
a bit more kind and doesn't destroy high frequencies quite so much. 
What is a much bigger issue is that you don't know what the blur kernel 
was, and getting it wrong can induce artifacts into the image.

Fortunately, we can do quite a bit by assuming a good image prior.  The 
artifacts produced by an incorrect deconvolution tend to pretty 
obviously not look like any "real" image.  There's some examples which a 
good explanation here:

http://www.mathworks.com/products/demos/image/ipexblind/ipexblind.html

The best image deblurring algorithms I know use this insight pretty 
heavily, and optimize a deconvolution by comparing how the statistics of 
the deconvolved image compare the expected statistics of "real" images. 
  It turns out that even pretty weak models of what real images look 
like can help quite a bit and often give surprisingly good results.

In some sense the simple deconvolution method I gave was also implicitly 
using an image prior which favors smoother images (for a very particular 
definition of smoothness).

Did this answer your questions?

Post a reply to this message

> If we now calculate abs(fft(k)), we get:
>
> kf = {4.0, 3.4, 2.0, 0.6, 0.0, 0.6, 2.0, 3.4}
>
> The key thing to notice here is that this contains a element which is 
> zero.  This means that the convolution kernel will "kill" certain 
> frequencies in the source image.

OK that makes sense.

> As far as I'm aware in practice having a kernel like yours which happens 
> to kill certain "unlucky" frequencies isn't really an issue.  What can be 
> an issue is that your kernel will suppress high frequencies to the point 
> that they fall below the accuracy of your camera sensor (or even numerical 
> precision).

Yes, this was my expectation of what would happen in a practical situation. 
I would imagine a focal-blur kernel would suppress the high frequencies, 
such that the information was either impossible to recover (due to noise 
levels) or what was recoverable would be heavily aliased due to the limited 
precision.

> This is why undoing a depth of field blur won't always be possible (even 
> if everything is at the same depth),

This was my initial thought in response to Andrew's original statement that 
you could get back the original signal because it was a convolution.

> Fortunately in the case of blur from camera shake the kernel is normally a 
> bit more kind and doesn't destroy high frequencies quite so much. What is 
> a much bigger issue is that you don't know what the blur kernel was, and 
> getting it wrong can induce artifacts into the image.

Yes, often you can even see a bright light source in the resultant image and 
how it has moved (maybe a zig-zag pattern due to camera shake) - you could 
probably use this as a basis for the kernel, maybe optimising the kernel 
until the resultant image had the light source as small as possible.

> Did this answer your questions?

Yes thanks!

Post a reply to this message