![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
scott wrote:
>> No. Only if everything in the frame is at approximately the same focal
>> distance does it approximate a 2D convolution.
>
> I doubt that happens very often, usually the camera gets a point in
> focus you didn't intend (and the bit you did intend is then out of focus).
No, as demonstrated, the problem I usually have is that my camera's
optics physically can't focus near enough. That blurry image I posted is
of a flat piece of ground. The focal depth is probably near-identical
everywhere. (Except that I think the ground plane might be tilted
relative to the camera...)
> But is it accurate enough to visibly improve the sharpness of an image?
> Judging by all the software I've seen that claims to do this, usually not.
OK. That's kind of what I was asking. DSP theory says it can be done,
but are the results worth it?
(DSP theory also says that a perfect deconvolution would require
infinity gain at certain frequencies. You just *know* that's not going
to work well in the Real World.)
>> This merely means that you can't deconvolve the edges properly.
>
> True, more precisely a region half the size of the convolution kernel
> along each edge.
For the image I'm thinking of, that wouldn't matter. The bit I want is
the person's head in the center.
>> A much bigger problem is figuring out what the hell the convolution
>> kernel might have been, given only the blurred image...
>
> Indeed, and it might not be constant for every pixel.
I suppose if it changes sufficiently slowly, it might still be possible
to estimate... maybe...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> (Except that I think the ground plane might be tilted relative to the
> camera...)
So each point will have a different convolution kernel...
Maybe if you thought about the optics of your camera you could derive an
approximate kernel as a function of depth and focal distance, you could then
apply this for each pixel using some trial&error method to get the sharpest
image (or some other method).
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> The problem is when you apply a convolution to an image, you get a bigger
>> image (the size of the original image + the size of the convolution
>> window). The extra data around the edges is needed in order to do the
>> deconvolution. Obviously in a photo you don't get this information.
>
> This merely means that you can't deconvolve the edges properly.
I thought about this some more and don't agree with you. Take this 1D
example:
Convolution kernel: {1,2,1}
Source image: {a,b,c,d,e,f,g,h}
Result: {12,12,12,12,12,12,12,12}
Can you figure out *any* of the pixels in the source image?
If you write out the convolution by hand, the first pixel gives you one
equation with 3 unknowns - obviously you can't solve this. Each additional
pixel gives you one more equation and 1 more unknown. You can never solve
this!
In the mathematical world though, your source image is actually:
{0,0,...,0,0,a,b,c,d,e,f,g,h,0,0,...,0,0}
and when you apply your convolution you get edge data too.
With this extra information you can solve the deconvolution (because you
know the source pixels are zero outside of the image).
IRL the source data is not zero outside of your photo.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> Echo, focal blur and motion blur are all instances of convolution. That
> means, hypothetically, that by applying a suitable *deconvolution*, you
> should be able to get back the original signal.
>
> Question: Is it actually feasible to do this in the real world?
Without artifacting? No.
Now you could make a huge matrix (N x N, where N is the number of
elements in the image to be sharpened) and solve it. But for an image
of, say, typical embedded YouTube size, you are looking an matrix that
is on the order of 80K x 80k elements. Granted, most of the elements
are zero, but it's still a headache.
Regards,
John
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
John VanSickle wrote:
>
> Now you could make a huge matrix (N x N, where N is the number of
> elements in the image to be sharpened) and solve it. But for an image
> of, say, typical embedded YouTube size, you are looking an matrix that
> is on the order of 80K x 80k elements. Granted, most of the elements
> are zero, but it's still a headache.
In the particular case of deconvolution there are much more efficient
algorithms available. There's various techniques, but one insight that
is commonly exploited is that convolution in the spatial domain is
equivalent to multiplication in the Fourier domain. This in the absence
of noise (which is a *big* assumption) and ignoring image boundaries you
could compute (non-blind) deconvolution by using FFT on the image and
the kernel and dividing, which is a pretty efficient operation.
IIRC the approach above isn't used much in practice, largely because of
the noise assumptions, but some of the more sophisticated methods still
perform operations in frequency space for efficiency.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> This in the absence of noise (which is a *big* assumption) and ignoring
> image boundaries you could compute (non-blind) deconvolution by using FFT
> on the image and the kernel and dividing, which is a pretty efficient
> operation.
The problem is the convoluted version you have "the photo" is not made of
complex numbers (which it would be if you did the convolution yourself).
You need this in order to do the deconvolution, otherwise you don't have
enough information. See my 1D example in the other post.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
scott wrote:
>> This in the absence of noise (which is a *big* assumption) and
>> ignoring image boundaries you could compute (non-blind) deconvolution
>> by using FFT on the image and the kernel and dividing, which is a
>> pretty efficient operation.
>
> The problem is the convoluted version you have "the photo" is not made
> of complex numbers (which it would be if you did the convolution
> yourself). You need this in order to do the deconvolution, otherwise you
> don't have enough information. See my 1D example in the other post.
I'm a bit confused by what you mean here. If both the image and the
kernel are real then complex numbers would only be used in the frequency
space versions of the images, once you apply the IFFT everything should
be real again. I don't see how you'd need a (non-trivial) complex
version of the image anywhere.
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.
In the case of the most basic FFT method for convolution, the boundary
conditions for the image would be implicitly cyclic. I should point out
that (IIRC) the naive deconvolution method of x=ifft(fft(y)/fft(k))
generally doesn't work well in practice, but the idea of using the
Fourier transform to accelerate the computations still carries across to
more sophisticated approaches.
Unless I'm missing something somewhere?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 1) This has anything to do with complex numbers, even if you use the FFT
> method to recover the source image.
Agreed, I incorrectly thought that if you had some complex version of the
resultant you would have more information to regenerate the source, but with
real source image and real kernel that is obviously not possible.
> 2) This prevents you from getting an approximate answer in practice.
> >>>>>> result:
>
> {3 3 3 3 3 3 3 3}
>
> 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}
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.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |