Inverting a Filter

Re: Inverting a Filter.

"4N"  wrote in message 
news:48f381c6$0$40314$4fafbaef@reader5.news.tin.it...
>
> "Jeff"  ha scritto nel messaggio 
> news:EIJIk.236$dN6.127@newsfe18.ams2...
>> Hello
>>
>> Probably a very simple question but it has me a little confused at the 
>> moment.
>>
>> If I convolve an Image A with a small NxN filter F to give image B then 
>> does there exist a inverse filter F' such that F' convolved with B gives 
>> A?
>> If so then what is the size of F' and how can F' be found if only A and B 
>> are known?
>
> To explain it the simple way you should use FFTs.
> In the frequency domain the convolution is done by multiplying every pixel 
> of the transformed filter mask (F) by the corresponding pixel in the 
> transformed image A (both image FFT(F) and FFT(A) have the same 
> dimensions), so to invert  the effect (deconvolution) you divide the 
> transformed result FFT(B) by the transformed filter F...

Thanks for that.
Yes, I'm familiar with the duality that exists between the spatial and 
frequency domains.

But suppose we have two 1024x1024 images which we know are related by some 
small filter which we seek to find. Solving the problem in the frequency 
domain would appear to involve an FFT on two largish images and then a very 
large matrix inversion followed by an equally large inverse FFT. Is this 
really the most efficient way to proceed?

But what's really confusing me is the potential size of the inverse filter. 
I naively assume that the inverse filter would have the same size as the 
forward filter - but is this necessarily the case?

Thanks again
Jeff

Re: Inverting a Filter.

> But suppose we have two 1024x1024 images which we know are related by some 
> small filter which we seek to find. Solving the problem in the frequency 
> domain would appear to involve an FFT on two largish images and then a 
> very large matrix inversion followed by an equally large inverse FFT. Is 
> this really the most efficient way to proceed?

Frequency domain is preferred over spatial domain when the filter mask for 
the convolution is large, in this case
I explained the problem in the frequency domain because it's easier to 
explain, in fact it took only a couple of lines for that.

> But what's really confusing me is the potential size of the inverse 
> filter. I naively assume that the inverse filter would have the same size 
> as the forward filter - but is this necessarily the case?

Maybe I didn't get your question, anyway the transformed filter mask that 
you use for deconvolution is exactly the same you use for convolution.
I mean if you multiply a value v by another f you have to divide by f to 
obtain again v...
Anyway mr. Brown already explained that this problem is ill posed and you 
must know the exact filter that tranformed the original image to proceed 
like explained.
Blind deconvolution is being studied but till now only certain types of 
filters can be inverted, and anyway there're just but a handful of articles 
on this subject. 

Re: Inverting a Filter.

On Oct 13, 9:22=A0am, "Jeff"  wrote:
> Hello
>
> Probably a very simple question but it has me a little confused at the
> moment.
>
> If I convolve an Image A with a small NxN filter F to give image B then d=
oes
> there exist a inverse filter F' such that F' convolved with B gives A?

No, not generally.  Deconvolution is an approximation process and
rarely is it attempted by convolution with some spatially invariant
kernel.

Consider the simple 1D case of convolution with [ 1 1 ] in matrix
form:

y =3D A x

A =3D

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

A is a 3x4 matrix so it is underdetermined and has no inverse.  There
are an infinite number of x that satisfy that equation.  However, one
might select a solution, x', such that xTx is minimum,

x' =3D AT (A AT)^-1 y

Observe,

A x' =3D A AT (A AT)^-1 y =3D y

However, this particular kind of solution does not lead to natural
looking images and is not recommended.

aruzinsky wrote:
> On Oct 13, 9:22 am, "Jeff"  wrote:
>> Hello
>>
>> Probably a very simple question but it has me a little confused at the
>> moment.
>>
>> If I convolve an Image A with a small NxN filter F to give image B then does
>> there exist a inverse filter F' such that F' convolved with B gives A?
> 
> No, not generally.  Deconvolution is an approximation process and
> rarely is it attempted by convolution with some spatially invariant
> kernel.
> 
> Consider the simple 1D case of convolution with [ 1 1 ] in matrix
> form:
> 
> y = A x
> 
> A =
> 
> 1 1 0 0
> 0 1 1 0
> 0 0 1 1
> 
> A is a 3x4 matrix so it is underdetermined and has no inverse.  There
> are an infinite number of x that satisfy that equation.  However, one
> might select a solution, x', such that xTx is minimum,
> 
> x' = AT (A AT)^-1 y
> 
> Observe,
> 
> A x' = A AT (A AT)^-1 y = y
> 
> However, this particular kind of solution does not lead to natural
> looking images and is not recommended.

You are between a rock and a hard place for regularising functions that 
create natural looking images. The best you can hope for in the absence 
of any other prior information is not to create unjustified correlations 
in the reconstructed image. AFAIK Maximum entropy f.log(f) is as good a 
choice as any.

There is a cute Kangaroo problem posed by Steve Gull to illustrate the 
effects of various choices of regularising functions in a very simple 
underdetermined test case where human intuition can see the answer.

You are given just two pieces of data and need to create a 2x2 
contingency table for a bet on the proportion of blue eyed, left handed 
kangaroos in Australia.

The observational data is:

a. 1/3 of kangaroos have blue eyes
b. 1/3 of kangaroos are left handed

Common sense says that since you have no other evidence you would like 
to choose a reconstruction that gives an answer of 1/9 for blue eyed 
left handers. Sum p log(p) passes this test nicely.

The most extreme positive correlation answer is 1/3
and the most extreme negative correlation answer is 0

And the general case is

	L	R
Blue	x       1/3-x
Other   1/3-x	1/3+x

Other popular choices are p.p which gives 1/12 (negative correlation)
And other barrier functions that also encourage positivity like
log p which gives 0.130 (positive correlation)
sqrt(p) which gives 0.122 (positive correlation)

Ultimately you pays your money and takes your choice.

Regards,
Martin Brown
** Posted from http://www.teranews.com **

On Oct 14, 2:10=A0pm, Martin Brown <|||newspam...@nezumi.demon.co.uk>
wrote:
> ...
> The best you can hope for in the absence
> of any other prior information is not to create unjustified correlations
> in the reconstructed image.
> ...

Typically, there is prior information.  The distribution of
derivatives, or gradient magnitudes, for a wide range of natural
images follows ~ exp( -| x/s |^p ) with 0