Gibbs phenomenon

Hi!

I am working over high quality image processing algorithms (image shifts,
image rotation, etc). I am trying to use 1D sinc interpolation, but it
produces Gibbs artifacts. Is it possible to modify sinc interpolation in
some way in order to reduce these artidacts? Perhaps, it is better to use
some other interpolations for the case of sharp edges? 
I have tried to apply some windows (Hann, Lanczos) - but they have not
satisfied me - the sharpness of edges is being lost due to them.

thanks!     




_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

On May 10, 8:00 am, "SEngel" <khr...@yandex.ru> wrote:
> Hi!
>
> I am working over high quality image processing algorithms (image shifts,
> image rotation, etc). I am trying to use 1D sinc interpolation, but it
> produces Gibbs artifacts. Is it possible to modify sinc interpolation in
> some way in order to reduce these artidacts? Perhaps, it is better to use
> some other interpolations for the case of sharp edges?
> I have tried to apply some windows (Hann, Lanczos) - but they have not
> satisfied me - the sharpness of edges is being lost due to them.
>
> thanks!
>
> _____________________________________
> Do you know a company who employs DSP engineers?
> Is it already listed athttp://dsprelated.com/employers.php?

The Gibbs phenomenon is a direct result of your signal being
bandlimited; you need infinite bandwidth to have completely "sharp"
edges, and obviously you can't do that with a sampled signal.
Windowing can't really help you; when you interpolate, you don't get
any new information about the signal. The interpolated signal conveys
the same amount of information as your original. Since your original
is bandlimited based upon your sample rate, then the interpolated
signal can't have any "sharper" edges, since its spectrum has
identical bandwidth (in the continuous-time domain; in the discrete-
time domain, the spectrum gets compressed) to the original.

Jason

>The Gibbs phenomenon is a direct result of your signal being
>bandlimited; you need infinite bandwidth to have completely "sharp"
>edges, and obviously you can't do that with a sampled signal.
>Windowing can't really help you; when you interpolate, you don't get
>any new information about the signal. The interpolated signal conveys
>the same amount of information as your original. Since your original
>is bandlimited based upon your sample rate, then the interpolated
>signal can't have any "sharper" edges, since its spectrum has
>identical bandwidth (in the continuous-time domain; in the discrete-
>time domain, the spectrum gets compressed) to the original.
>
>Jason
>
>

Does it mean that sinc interpolator is not suitable for such cases? Are
there better interpolators which do not produce Gibbs ripples? I have
tried  polynomial interpolation and it is much worse than the sinc one.  

As I can see, professional software (like Photoshop) interpolates images
without such artifacts..  
    


_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

"SEngel" <khrden@yandex.ru> wrote in message 
news:frKdneXY8dD-lN7bnZ2dnUVZWhednZ2d@giganews.com...
> Hi!
>
> I am working over high quality image processing algorithms (image shifts,
> image rotation, etc). I am trying to use 1D sinc interpolation, but it
> produces Gibbs artifacts. Is it possible to modify sinc interpolation in
> some way in order to reduce these artidacts? Perhaps, it is better to use
> some other interpolations for the case of sharp edges?
> I have tried to apply some windows (Hann, Lanczos) - but they have not
> satisfied me - the sharpness of edges is being lost due to them.

Well, you haven't told us how they are dissatisfying so it's hard to know 
how to help.  You also didn't say whether the interpolation was in space or 
spatial frequency - which might be nice to know.  I suppose it's in space 
though...

The Gibbs phenonmenon is a direct result of using a sinc.  It's simply the 
integral of a sinc that you see when convolving over a step / edge. 
Convolution with a sinc will always do this perforce.

As you've apparently tried, the way around this is to use a different kernel 
for interpolation.  A fact of life is that as the Gibbs phenomenon is 
reduced, the width of the central peak of the kernel function increases - 
and this makes edges less sharp.  In real life the increase isn't all that 
much though.  You should be able to reduce the Gibbs phenomenon effects 
quite a bit with only a small reduction in edge resolution.

Studies have been done to find the best / narrowest kernels with the 
narrowest *and* monotonic step response.  From a December 2003 post on 
comp.dsp:

"Take a look at page 199 of Temes, Barcilon and Marshall "The Optimization 
of
Bandlimited Sytems" Proc IEEE Vol 61 No. 2 Feb 1973 pp 196-234.  Here,
Victor Barcilon discusses time spread and frequency spread, deltaT and
deltaOmega respectively, and shows that the Gaussian is optimum, that
deltaT*deltaOmega>=1/2, etc......  These are optimum functions and not
system functions."

So, you might try using something that approximates a Guassian function. 
Or, you might use something that's a bit narrower but with just a bit of 
ringing.  Again, the width differences tend to be small when going from one 
"good" window or kernel to another of the same general type.

Bhaskar says in another post: "A kaiser window is a good approximation in 
the discrete domain for a Gaussian filter in the contn domain (although they 
each have different
equations). I don't have a proof for this but this is what my intuition
tells me."

So, maybe try a Kaiser window function here.

Understand that we are talking about a narrow kernel in whichever space 
you're in.  It's transformed counterpart is a very wide function and 
Guassian corresponds to Gaussian I believe you will find.  So, the 
interpolation in space with a narrow kernel will have the effect of cutting 
the high frequencies.  With no ringing (Gibbs) the frequency domain function 
will be zero at the ends and at least the first derivative will also be zero 
at the ends.  There's a relationship between ringing and the derivatives at 
the ends.

A gate in frequency corresponds to a sinc and decays as 1/x
A triangle in frequency corresponds to a sinc^2 and decays as 1/x^2
A raised cosine in frequency corresponds to [1/4 1/2 1/4] in space I do 
believe and is often used for image/video interpolation because it's OK in 
performance and easy to implement.  Generally you don't want an interpolator 
for images that is very long at all.

One might try an experiment like this:
Start with the sinc as you've done.
Gradually build functions that will eventually become a full-fledged raised 
cosine by adding ever-growing cosine to the gate corresponding to the sinc.
At each stage, look at the result until you see something that looks 
relatively satisfying.  I think this means using kernels that look like 
this:

[ 0 1 0] corresponding to a sinc .. it's the "do nothing" case.
[ .05 .9 .05]
[.1 .8 .1]
[.15 .7 .15]
[.2 .6 .2]
[.25 .5 .25]

Well, these steps aren't very gradual but you should get the idea.  Then you 
might experiment with wider kernels but I'm not so sure that's what you 
want.  What is the interpolation factor anyway?

Fred 

Fred Marshall wrote:

   ...

> [ 0 1 0] corresponding to a sinc .. it's the "do nothing" case.
> [ .05 .9 .05]
> [.1 .8 .1]
> [.15 .7 .15]
> [.2 .6 .2]
> [.25 .5 .25]

   ...

Note that [.25 .5 .25] = [1 2 1]/4 (excuse the notation!) is the second 
line of Pascal's triangle. Binomial expansions are discrete 
approximations of a Gaussian, the expansions with higher powers being 
better approximations. The next ones in the series are [1 3 3 1]/8 and 
[1 4 6 4 1]/16, for what that may be worth.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

>
>"SEngel" <khrden@yandex.ru> wrote in message 
>news:frKdneXY8dD-lN7bnZ2dnUVZWhednZ2d@giganews.com...
>> Hi!
>>
>> I am working over high quality image processing algorithms (image
shifts,
>> image rotation, etc). I am trying to use 1D sinc interpolation, but it
>> produces Gibbs artifacts. Is it possible to modify sinc interpolation
in
>> some way in order to reduce these artidacts? Perhaps, it is better to
use
>> some other interpolations for the case of sharp edges?
>> I have tried to apply some windows (Hann, Lanczos) - but they have not
>> satisfied me - the sharpness of edges is being lost due to them.
>
>Well, you haven't told us how they are dissatisfying so it's hard to know

>how to help.  You also didn't say whether the interpolation was in space
or 
>spatial frequency - which might be nice to know.  I suppose it's in space

>though...
>
>The Gibbs phenonmenon is a direct result of using a sinc.  It's simply
the 
>integral of a sinc that you see when convolving over a step / edge. 
>Convolution with a sinc will always do this perforce.
>
>As you've apparently tried, the way around this is to use a different
kernel 
>for interpolation.  A fact of life is that as the Gibbs phenomenon is 
>reduced, the width of the central peak of the kernel function increases -

>and this makes edges less sharp.  In real life the increase isn't all
that 
>much though.  You should be able to reduce the Gibbs phenomenon effects 
>quite a bit with only a small reduction in edge resolution.
>
>Studies have been done to find the best / narrowest kernels with the 
>narrowest *and* monotonic step response.  From a December 2003 post on 
>comp.dsp:
>
>"Take a look at page 199 of Temes, Barcilon and Marshall "The
Optimization 
>of
>Bandlimited Sytems" Proc IEEE Vol 61 No. 2 Feb 1973 pp 196-234.  Here,
>Victor Barcilon discusses time spread and frequency spread, deltaT and
>deltaOmega respectively, and shows that the Gaussian is optimum, that
>deltaT*deltaOmega>=1/2, etc......  These are optimum functions and not
>system functions."
>
>So, you might try using something that approximates a Guassian function.

>Or, you might use something that's a bit narrower but with just a bit of

>ringing.  Again, the width differences tend to be small when going from
one 
>"good" window or kernel to another of the same general type.
>
>Bhaskar says in another post: "A kaiser window is a good approximation in

>the discrete domain for a Gaussian filter in the contn domain (although
they 
>each have different
>equations). I don't have a proof for this but this is what my intuition
>tells me."
>
>So, maybe try a Kaiser window function here.
>
>Understand that we are talking about a narrow kernel in whichever space 
>you're in.  It's transformed counterpart is a very wide function and 
>Guassian corresponds to Gaussian I believe you will find.  So, the 
>interpolation in space with a narrow kernel will have the effect of
cutting 
>the high frequencies.  With no ringing (Gibbs) the frequency domain
function 
>will be zero at the ends and at least the first derivative will also be
zero 
>at the ends.  There's a relationship between ringing and the derivatives
at 
>the ends.
>
>A gate in frequency corresponds to a sinc and decays as 1/x
>A triangle in frequency corresponds to a sinc^2 and decays as 1/x^2
>A raised cosine in frequency corresponds to [1/4 1/2 1/4] in space I do 
>believe and is often used for image/video interpolation because it's OK
in 
>performance and easy to implement.  Generally you don't want an
interpolator 
>for images that is very long at all.
>
>One might try an experiment like this:
>Start with the sinc as you've done.
>Gradually build functions that will eventually become a full-fledged
raised 
>cosine by adding ever-growing cosine to the gate corresponding to the
sinc.
>At each stage, look at the result until you see something that looks 
>relatively satisfying.  I think this means using kernels that look like 
>this:
>
>[ 0 1 0] corresponding to a sinc .. it's the "do nothing" case.
>[ .05 .9 .05]
>[.1 .8 .1]
>[.15 .7 .15]
>[.2 .6 .2]
>[.25 .5 .25]
>
>Well, these steps aren't very gradual but you should get the idea.  Then
you 
>might experiment with wider kernels but I'm not so sure that's what you 
>want.  What is the interpolation factor anyway?
>
>Fred 
>
>
>

Now I try to apply sinc interpolation for the image rotation. 
Image rotation can be reduced to the problem of arbitrary shift of one
image line (so called 3-pass algorithm). 

So I compute sinc interpolation in spatial domain for one line of the
image. By means of respective multiplication in the frequency domain I get
the shifted line. And here Gibbs phenomenon appear.

You can see it on the following example. I have taken white square on the
black background and rotated it. 

Here is the zoomed result of the rotated square side: 

http://www.ljplus.ru/img3/b/o/boshetunmaj/square_sinc.jpg   

You can see Gibbs oscillations on the right from the square side. 

I have done the same transformation in Photoshop - the picture is
free from any artifacts:

http://www.ljplus.ru/img3/b/o/boshetunmaj/square_ps.jpg

Thank you for information about filters - I will look for the best one!
(I have already decided before your post that they are not good in this
case...)

>  What is the interpolation factor anyway?

Do you mean the size? I use 16 samples for the interpolation. 




_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

SEngel wrote:
> 
> >
> >"SEngel" <khrden@yandex.ru> wrote in message
> >news:frKdneXY8dD-lN7bnZ2dnUVZWhednZ2d@giganews.com...
> >> Hi!
> >>
> >> I am working over high quality image processing algorithms (image
> shifts,
> >> image rotation, etc). I am trying to use 1D sinc interpolation, but it
> >> produces Gibbs artifacts. Is it possible to modify sinc interpolation
> in
> >> some way in order to reduce these artidacts? Perhaps, it is better to
> use
> >> some other interpolations for the case of sharp edges?
> >> I have tried to apply some windows (Hann, Lanczos) - but they have not
> >> satisfied me - the sharpness of edges is being lost due to them.
> >
> >Well, you haven't told us how they are dissatisfying so it's hard to know
> 
> >how to help.  You also didn't say whether the interpolation was in space
> or
> >spatial frequency - which might be nice to know.  I suppose it's in space
> 
> >though...
> >
> >The Gibbs phenonmenon is a direct result of using a sinc.  It's simply
> the
> >integral of a sinc that you see when convolving over a step / edge.
> >Convolution with a sinc will always do this perforce.
> >
> >As you've apparently tried, the way around this is to use a different
> kernel
> >for interpolation.  A fact of life is that as the Gibbs phenomenon is
> >reduced, the width of the central peak of the kernel function increases -
> 
> >and this makes edges less sharp.  In real life the increase isn't all
> that
> >much though.  You should be able to reduce the Gibbs phenomenon effects
> >quite a bit with only a small reduction in edge resolution.
> >
> >Studies have been done to find the best / narrowest kernels with the
> >narrowest *and* monotonic step response.  From a December 2003 post on
> >comp.dsp:
> >
> >"Take a look at page 199 of Temes, Barcilon and Marshall "The
> Optimization
> >of
> >Bandlimited Sytems" Proc IEEE Vol 61 No. 2 Feb 1973 pp 196-234.  Here,
> >Victor Barcilon discusses time spread and frequency spread, deltaT and
> >deltaOmega respectively, and shows that the Gaussian is optimum, that
> >deltaT*deltaOmega>=1/2, etc......  These are optimum functions and not
> >system functions."
> >
> >So, you might try using something that approximates a Guassian function.
> 
> >Or, you might use something that's a bit narrower but with just a bit of
> 
> >ringing.  Again, the width differences tend to be small when going from
> one
> >"good" window or kernel to another of the same general type.
> >
> >Bhaskar says in another post: "A kaiser window is a good approximation in
> 
> >the discrete domain for a Gaussian filter in the contn domain (although
> they
> >each have different
> >equations). I don't have a proof for this but this is what my intuition
> >tells me."
> >
> >So, maybe try a Kaiser window function here.
> >
> >Understand that we are talking about a narrow kernel in whichever space
> >you're in.  It's transformed counterpart is a very wide function and
> >Guassian corresponds to Gaussian I believe you will find.  So, the
> >interpolation in space with a narrow kernel will have the effect of
> cutting
> >the high frequencies.  With no ringing (Gibbs) the frequency domain
> function
> >will be zero at the ends and at least the first derivative will also be
> zero
> >at the ends.  There's a relationship between ringing and the derivatives
> at
> >the ends.
> >
> >A gate in frequency corresponds to a sinc and decays as 1/x
> >A triangle in frequency corresponds to a sinc^2 and decays as 1/x^2
> >A raised cosine in frequency corresponds to [1/4 1/2 1/4] in space I do
> >believe and is often used for image/video interpolation because it's OK
> in
> >performance and easy to implement.  Generally you don't want an
> interpolator
> >for images that is very long at all.
> >
> >One might try an experiment like this:
> >Start with the sinc as you've done.
> >Gradually build functions that will eventually become a full-fledged
> raised
> >cosine by adding ever-growing cosine to the gate corresponding to the
> sinc.
> >At each stage, look at the result until you see something that looks
> >relatively satisfying.  I think this means using kernels that look like
> >this:
> >
> >[ 0 1 0] corresponding to a sinc .. it's the "do nothing" case.
> >[ .05 .9 .05]
> >[.1 .8 .1]
> >[.15 .7 .15]
> >[.2 .6 .2]
> >[.25 .5 .25]
> >
> >Well, these steps aren't very gradual but you should get the idea.  Then
> you
> >might experiment with wider kernels but I'm not so sure that's what you
> >want.  What is the interpolation factor anyway?
> >
> >Fred
> >
> >
> >
> 
> Now I try to apply sinc interpolation for the image rotation.
> Image rotation can be reduced to the problem of arbitrary shift of one
> image line (so called 3-pass algorithm).
> 
> So I compute sinc interpolation in spatial domain for one line of the
> image. By means of respective multiplication in the frequency domain I get
> the shifted line. And here Gibbs phenomenon appear.
> 
> You can see it on the following example. I have taken white square on the
> black background and rotated it.
> 
> Here is the zoomed result of the rotated square side:
> 
> http://www.ljplus.ru/img3/b/o/boshetunmaj/square_sinc.jpg
> 
> You can see Gibbs oscillations on the right from the square side.
> 
> I have done the same transformation in Photoshop - the picture is
> free from any artifacts:
> 
> http://www.ljplus.ru/img3/b/o/boshetunmaj/square_ps.jpg
> 
> Thank you for information about filters - I will look for the best one!
> (I have already decided before your post that they are not good in this
> case...)
> 
> >  What is the interpolation factor anyway?
> 
> Do you mean the size? I use 16 samples for the interpolation.


By 16 samples you mean 16 samples wide? Obviously your Photoshop example
is using a much narrower interpolation scheme. Yours doesn't seem to be
a correctly implemented sinc interpolator. The ringing is far more
exaggerated than it should be. It might be that clipping is contributing
to the poor performance of your method. Also, Photoshop may not be using
a strictly linear process. How it works may be dependent on the data
being processed. Methods that detect sharp transitions in the image and
adapt to them are sometimes used to avoid ringing artifacts around sharp
edges.

-Jim



> 
> _____________________________________
> Do you know a company who employs DSP engineers?
> Is it already listed at http://dsprelated.com/employers.php ?

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

On 10 May, 14:00, "SEngel" <khr...@yandex.ru> wrote:
> Hi!
>
> I am working over high quality image processing algorithms (image shifts,
> image rotation, etc). I am trying to use 1D sinc interpolation, but it
> produces Gibbs artifacts.

Have you tried to use splines for interpolation?

Rune

>
>By 16 samples you mean 16 samples wide? Obviously your Photoshop example
>is using a much narrower interpolation scheme. Yours doesn't seem to be
>a correctly implemented sinc interpolator. The ringing is far more
>exaggerated than it should be. It might be that clipping is contributing
>to the poor performance of your method. Also, Photoshop may not be using
>a strictly linear process. How it works may be dependent on the data
>being processed. Methods that detect sharp transitions in the image and
>adapt to them are sometimes used to avoid ringing artifacts around sharp
>edges.
>
>-Jim
>
>
>
>> 
>> _____________________________________
>> Do you know a company who employs DSP engineers?
>> Is it already listed at http://dsprelated.com/employers.php ?
>
>----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet
News==----
>http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+
Newsgroups
>----= East and West-Coast Server Farms - Total Privacy via Encryption
=----
>

Yes, I use a sliding window of 8 pixels wide for the central pixel
interpolation. For the reduction of Gibbs oscillations I flip the data -
it helps a little. 

I have tried to use 4 sample window. The result looks worse because
aliasing components appear.

Detection of sharp edges is an easy task while the main question is : what
is the best best technique to deal with them?  




_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

>On 10 May, 14:00, "SEngel" <khr...@yandex.ru> wrote:
>> Hi!
>>
>> I am working over high quality image processing algorithms (image
shifts,
>> image rotation, etc). I am trying to use 1D sinc interpolation, but it
>> produces Gibbs artifacts.
>
>Have you tried to use splines for interpolation?
>
>Rune
>
>

No. I have tried only polynomial approximations. Do you think splines are
more effective than sinc?  

_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?