On Fri, 20 Jun 2003 23:58:03 -0700
Joel Rodriguez <[EMAIL PROTECTED]> wrote:

> Thanks for your attention to the matter Esnst:
> it is enough information to get me going   :)
> I will take a close look at the link which by the way looks very impressive,
> the approach was thinking was not conjugate gradient itself, but a variant
> of constrained optimization:
> http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/constropt.html
> particularly the least squares solution, for which I'm familiar with:
> http://www.sbsi-sol-optimize.com/products_lssol.htm

> P.S. wont bother for a while, thanks for your attention,  yesterday's 
> tequila,
> some times make me feel that P=NP,..he,...  :)

Oh, but that is a valid feeling even when you're sober, nobody has
proved that they are different.

It might be wise to wait with reading the rest of this post until
you have fully recovered :)

But when you have recovered, I would advice you to study Fourier
Analysis. I found it very helpful in explaining why deconvolution is
so difficult. One important fact is that a convolution can be
described as a multiplication in the Fourier domain, i.e.  the Fourier
transform of the result is equal to the multiplication of the Fourier
transform of the input times the Fourier transform of the
convolution. Now this implies that the inverse operation (the
deconvolution) can be described in the Fourier domain as a division by
the Fourier transform of the convolution. But in virtually all cases
the Fourier transform of the convolution contains some values that are
very small. In the case that your convolution is circular symmetric,
it is possible to prove that its Fourier transform must contain at
least one value that is equal to zero. It is obvious that when the
Fourier transform of the convolution contains any zeroes, that there
cannot be an exact inverse because division by zero is undefined.
Also the small values in the Fourier transform cause problems:
when you divide by a small number that is of course equivalent
to multiplying with a big number, in other words the inverse of
the convolution will greatly magnify all errors in the image
that correspond with the small valued component. 

This also helps to explain why least square minimizations frequently
give horrible results. Take an image for which the Fourier transform
only contains values that are significantly different from zero for
the components where the Fourier transform is close to zero.
It should be clear that the result of convolving this image with
the convolution gives a result where every pixel is almost equal
to zero. Because convolution is a linear operation, when you
add this image A to another image B and then apply the convolution,
the end result must be equal to the sum of the convolution of
A plus the convolution of B. But because the convolution of
A is almost zero, it is easy to see that the convolution of
A + B is almost equal to the convolution of B. But this
means that the least square criterion is not very well defined,
because when some multiple of A is added to an image the
least squares distance will only change by a very small amount.

In practice this means, that I can have two completely different
images, one that shows a "normal" image and another one that
completely looks like random noise. But when I use a convolution
on both images the result can be almost identical. The problem
with least squares optimization is that this procedure cannot
distinguish between these two images. 
This is the reason that least squares optimization procedures
do not perform well, often the optimal solution visually completely
looks like random noise. Most techniques that are based on
least squares minimization are iterative and do not attempt to
find the real minimum. Normally they require user intervention
to determine the number of iterative steps.

Perhaps this explanation is a bit too convoluted, but I think
that it contains some important points. Feel free to ask
when you have any problems.


Ernst Lippe

Gimp-developer mailing list

Reply via email to