scott wrote:
>> Your 1D example seemed to be about the image boundaries rather than 
>> the image being represented by real/complex numbers.  The point about 
>> the image boundaries is true, and will prevent an exact deconvolution 
>> as you pointed out.  You can still often get a good approximate 
>> solution by either assuming boundary conditions or by using an image 
>> prior.  I believe the latter is these is what's generally used in 
>> practice for image deblurring.
> 
> The example I was referring to was this one:
> 
> Convolution kernel: {1,2,1}
> Source image: {a,b,c,d,e,f,g,h}
> Result: {12,12,12,12,12,12,12,12}
> 
> What is the source image?
> 


I think my last post was not clear enough.  I'm agreeing with you that 
you can't exactly recover the source image in your example.  What I'm 
disagreeing with are two things:

1) This has anything to do with complex numbers, even if you use the FFT 
method to recover the source image.

2) This prevents you from getting an approximate answer in practice.

Both of these assertions can be tested pretty easily, so I'll treat them 
in turn.  Also, sorry for the long post, but it seemed useful to go into 
a fair bit of detail.


---------- (1) complex numbers aren't the issue

First of all, let's try the FFT method for solving for the source image. 
  This code should run in both matlab and octave:

n = 8; % size of images
k = [1 2 1]; % kernel
k2 = [zeros(1,ceil((n-3)/2)) k zeros(1,floor((n-3)/2))]; % padded kernel
y = 12 + zeros(1,n); % result image

disp('source image (FFT method)');
ifft(fft(y)./(fft(k2)+1e-8)) % +1e-8 is a regularization hack

 >>>>>> result:

{3 3 3 3 3 3 3 3}

So despite not having any complex numbers in "the photo" (i.e. the 
result image) the method worked just fine and gave us a pretty 
reasonable looking result.

"But there's not enough information to derive a result!" I imagine 
you're thinking.  This is correct, so clearly something was happening 
behind the scenes that allows the method to actually compute a source 
image.  The answer is that the FFT method makes an implicit assumption 
about what happens beyond the boundaries of the result image by treating 
the image as cyclic.  Thus the source image isn't just 
{a,b,c,d,e,f,g,h}, it's actually treated as 
{...,f,g,h,a,b,c,d,e,f,g,h,a,b,c,...}, which is what allows this method 
to work.

This is the point I was making earlier that one way to solve the problem 
is to make an assumption about what happens beyond the boundaries of the 
image.  A natural next question to ask is what sort of errors this 
outright assumption might give in the reconstructed source image.


---------- (2) approximate solutions are possible

Let's look at the source images reconstructed under three different 
"reasonable" assumptions about what happens beyond the boundaries of the 
image:

cyclic: {...,f,g,h,a,b,c,d,e,f,g,h,a,b,c,...}

zero:  {...,0,0,0,a,b,c,d,e,f,g,h,0,0,0,...}

full-intensity: {...,12,12,12,a,b,c,d,e,f,g,h,12,12,12,...}

For each case the resulting source images are:

cyclic-source: {3 3 3 3 3 3 3 3}

zero-source: {5.3333, 1.3333, 4.0000, 2.6667, 2.6667, 4.0000, 1.3333, 
5.3333}

full-intensity-source: {4.5556, 1.8889, 3.6667, 2.7778, 2.7778, 3.6667, 
1.8889, 4.5556}

Clearly the different assumptions have given rise to different 
reconstructed images.  Nevertheless, notice that the center pixels in 
each of the three cases take the values of 3.0, 2.67, and 2.78.  Despite 
the fact that the assumptions for what happened beyond the boundary 
range from 0 to 12, the value of the center pixels only ranges from 2.67 
to 3.0 -- a factor of 36 less.

Basically, an incorrect assumption about what happens beyond the edges 
of the image resulted in errors concentrated at the edges of the 
reconstructed image, so in the center of the source image the FFT method 
actually can actually give a pretty accurate answer.  For a larger image 
(and the same kernel) the center values will be even more accurate.


---------- side notes

I want to emphasize that the deblurring method I gave is only to 
illustrate the basic theoretical principles behind using FFT to 
accelerate the deconvolution process.  In practice inaccurate kernels 
and image noise will result in a pretty poor result if you just use the 
method I gave.  However, people can and have developed pretty good 
deblurring methods which are more sophisticated and do work well in 
practice.  In many (but not all) of these approaches, using the FFT and 
performing some operations in frequency space is very useful for 
speeding up the algorithm.

Post a reply to this message