convolution

[pieter1976]

Does somebody know where I can find convolution matrices for filtering images?
I would like to have them in different sizes: 3x3/5x5/7x7/9x9

I doubled the size of a image and now I want to smooth the pixels by using convolution. what filter matrix should I use?

Does a 9x9 matrix give better results than a 3x3 matrix?

Do image filter equalizers exist? where you can change scrollbars to set te frequenties.

[Manao]

If you exactly doubled the size of your picture, the best to do is to use the following : source.pointresize(halfwidth, halfheight).lanczosresize(width, height)

[pieter1976]

Thanks for you reply but lanczos is not accurate enough. The edges aren't smooth. And I know that an other option would be Spline but that is not what I am looking for. I want to see if convolution can give good result and I want to know what the effect of bigger matrices will be.

I can't find any good convolution matrices on the internet.
There are a few 3x3 ones but not bigger ones. I know that with some math I can make my own but I am not so good at maths.

I want to use the filters for my research in interpolation.
The program XnView has an option for editing convolution matrices with different sizes.

[Manao]

Thanks for you reply but lanczos is not accurate enoughHowever, it acts as if you were using a 11x11 kernel on your upsized picture.

You won't get better results than lanczos with a 9x9 matrix.

If it's 'not accurate enough' ( I guess you're meaning not sharp enough ), then sharpen the result.

[pieter1976]

I would like to know how the lanczos filter works. Do you know where I can find a nice explanation of the algorithm.

[Manao]

It works as bicubic and bilinear work.

To explain it, I'll take a 1-dimension example. Imagine you have the following serie f(0)=1, f(1)=5, f(2)=4, f(3)=2, f(4)=3. Now, you would like to know what is the value of f in non integer position.

To do so, you will convole it by another function. That amounts to 'smooth' f.

Now, each resizing algorithm will correspond to a specific convolution kernel used in the convolution :

* Pointresize : the kernel is the step function which is 1 on [-0.5 ; 0.5], zero elsewhere. When you convole f by this kernel, it amounts to say that f(x) = f(closest_integer_to(x)). Visually, f will be extended around each integer by an horizontal line. Upscaling by 2 in that case would give the following serie : 1 1 5 5 4 4 2 2 3 3

* BilinearResize : the kernel is the function whose graph is a triangle : zero outside [-1 ; 1], a ramp from 0 to 1 in [-1 ; 0] and a ramp from 1 to 0 in [0 ; 1]. Convoling f by this kernel amounts to say, if x is between a and a+1 :
f(x) = (x-a) * f(a+1) + (a+1-x) * f(a)
Visually, each point of the graph of f will be linked by a segment. Upscaling would give : 1 3 5 4.5 4 3 2 2.5 3 3

* Bicubic : we use a kernel that is defined by two parameters ( b and c ), which is zero outside [-2 ; 2], negative on [-2 ; -1] & [1 ; 2], and positive in [-1 ; 1]. Upscaling would give something close to Bilinear.

* Lanczos3 : we use a kernel which is a sinus cardinal on [-3 ; 3], zero elsewhere.

* Lanczos4 : we work on [-4 ; 4].

[Wilbert]

Can I ask a stupid question about this? Suppose you want to decimate by a factor of 2 (or any integer factor). What's the difference between bilinear and bicubic when doing this?

My understanding is that you simply drop pixels. But that means there won't be any difference?

[Manao]

My understanding is that you simply drop pixelsNo. If you downscale, the basis of the kernel is extended by the redizing ratio.

So reducing by 2 in bilinear will amount to compute (f(x-1) + 2 * f(x) + f(x+1)) / 4 for each x = 2 * k, which in our case give the following serie : 2 4.25 2.75

With bicubic, you'll take into account f(x), f(x-1), f(x-3), f(x+1) and f(x+3) ( f(x+2) and f(x-3) are weighted by a null coefficient ).

[Wilbert]

Hmm, shouldn't be too difficult. It's only math.

f(0)=1, f(1)=5, f(2)=4, f(3)=2, f(4)=3

filter: (f(x-1) + 2 * f(x) + f(x+1)) / 4 for each x = 2 * k

k=0; x=0: I guess this should be (2*f(0)+f(1))/3 = 7/3 = 2.333
k=1; x=2: (f(1)+2*f(2)+f(3))/4 = 15/4 = 3.75
k=2; x=4: I guess this should be (f(3)+2*f(4))/3 = 8/3 = 2.666

What am I doing wrong?

[Manao]

Well, I considered that f(-1) = f(0) = 1, and f(5) = f(4) = 3, and for k=1, I made a mistake ( I was sure 4 + 4 + 5 + 2 = 17 :D )

[pieter1976]

Can I use sample rate conversion for image scaling?
Doing this horizontal and vertical.

What do televisions use for scaling the image?

[Richard Berg]

Televisions are analog.

[pieter1976]

They use digital processing for filtering.
why not for scaling?

[Richard Berg]

What is there to scale? You just turn up the gain on the sweep circuits until it fills the screen.

[pieter1976]

what about LCD and plasma TVs?

[pieter1976]

I have been reading a documents of a philips SAA4998 IC and I have to conclude that you are right. It is done analog.

[trevlac]

Originally posted by pieter1976
I have been reading a documents of a philips SAA4998 IC and I have to conclude that you are right. It is done analog.

You gave up too easy. :D

I'm sure many devices (like a DVD player zoom), resample in the digital domain.


Here is a snellwilcox paper about it.
http://www.snellwilcox.com/knowledgecenter/whitepapers/papers/digital_arc.pdf

Here is a fir calculator to let you see the cutoff your kernels.
http://www.digitalfilter.com/fircalwav/fircalwav.html

A problem with using a convolution larger than 5x5 is that there is no filter that would do this for you. Richard's does up to 5x5.

Lanczos does a 6x6. If I understand correctly (which I probably don't ), It calculates the coefficients 'on the fly' based upon the resize ratio. For a 2x size, this should be sin(x)/x * sin(x/3)/x/3 where x is {-1.5, -1, -0.5, 0 , .5, 1, 1.5} The center coefficient is 1. Or something like that ....

I don't really get why this is 'better' than a 11 tap kernel, but I'm a bit of a novice on this stuff.

[Manao]

It's better only in this particular case, where his picture is formed by 2x2 uniform squares.

[pieter1976]

This is what I want to try:

I will calculate a 1D impulse response using a lowpass filter with a variable cutoff frequency.

The impulse response will be used to calculate a 2d filled circle.
(It should look like a drip falling in the water making circular waves)

The results are used for convolution.

[MfA]

Just stick to gaussian filtering, you can do it in two 1D passes ... but it is still circulary symmetric.

[Manao]

But it will blur too much imho.

Trevlac : A problem with using a convolution larger than 5x5 is that there is no filter that would do this for you. Richard's does up to 5x5.You should have a look at YV12Convolution, inside the masktools.

[MfA]

Linear filtering gives you the choice between blurring and ringing ... those are the only two options.

[pieter1976]

Audio filters have slopes at the cuttoff frequency. The slope is measure in db / octave. How important is this with image filters?

[Manao]

What is a sloop ?

Anyway, since it's measured in dB / octave, I think it's not relevant in image filtering : human eyes don't see frequencies ( as the ears hear them ).

[pieter1976]

sorry I mean Slope.
My english needs to get better.


|
|
|-------\
| \ <- down slope
| \
| \-----------
-----------------------
-> freq



An other word would be rolloff I think.

[Manao]

Alright, then it is relevant in image processing. The sronger the slope, the higher the ringing, the lesser the blurring.

[pieter1976]

How do I remove ringing without making the image blurry.
Do I have to use something like Xsharpen for doing this?

[MfA]

You have to use nonlinear filtering, using xsharpen after blur is one way to do that. Or you could use mipsmooth, or filters based on anisotropic diffusion or bilateral filtering if someone ever brings out a good one (Ill get the second one right someday :)).

PS. speaking of the devil, tritical beat me to it (see usage board).

[pieter1976]

I want to show you some of the results I have made by removing Ringing. I also have some delphi code for the ones who are interested.



resized 4x input (http://home.zonnet.nl/pieterboots/RemoveRinging/input640480.gif)

Ringing Removed (http://home.zonnet.nl/pieterboots/RemoveRinging/output640480.gif)

code (http://home.zonnet.nl/pieterboots/RemoveRinging/RemoveRinging.zip)

[Wilbert]

Nice, is she your girlfriend?

Looking at her face, it is a bit too sharp.

[pieter1976]

The sharpness can be lower very easely.
The picture is an old one of Cindy Crawford.
I hope the source will be usefull for somebody who wants to make a similar filter for Avisynth.

[pieter1976]

Here is cindy (http://home.zonnet.nl/pieterboots/RemoveRinging/outp.gif) with edges being less sharp.

[ajordan]

Originally posted by Manao
Trevlac : You should have a look at YV12Convolution, inside the masktools.

Manao: I couldn't find any reference to a filter named YV12Convolution, either as part of masktools or otherwise... Where is it?

[Manao]

Searching for "YV12Convolution" would have lead you to the filter. Anyway, download the latest version (http://jourdan.madism.org/~manao/masktools-v1.5.zip), you'll see that there is a filter named YV12Convolution bundled with it.

[trevlac]

@pieter1976

I appreciate your work. I have been learning a bit about this myself.

It seems your method was a point resize and then a gausian blur. It would still probably be better to do a Lanczos. From what I can tell, this has 11 coeffieients itself. To get a Lanczos filter, you take a sinc function truncated it (to +/- 3) and multiply it by sinc(x/3).

Here is the avs code that does this for Lanczos 3. SinC(x) = sin(PI*x) / (PI*x) , where x is the new pixel position from the center pixel {-2.5, -2, -1.5, -1, -.5, 0, .5, 1, 1.5, 2, 2.5} for a 2x resize, I THINK this is how you calculate the coefficients.


/***********************
*** Lanczos3 filter ***
***********************/

double Lanczos3Filter::sinc(double value)
{
if (value != 0.0)
{
value *= M_PI;
return sin(value) / value;
}
else
{
return 1.0;
}
}

double Lanczos3Filter::f(double value)
{
if (value < 0.0)
{
value = -value;
}
if (value < 3.0)
{
return (sinc(value) * sinc(value / 3.0));
}
else
{
return 0.0;
}
}


Anyway The reason it is better is that if you point resize 1st, you are adding artifacts to your picture. Then you are removing them with a blur. Probably better to reconstruct the signal with a more precise filter.

PS: I'm a novice on all of this ... but it is my understanding that 'ringing' is usually a reference to the artifacts you get when you truncate a sinc function. Seen as xtra edges just past the 'real' edge. I think a point resamples artifacts are just referred to as aliasing.


[edit]

I'm not really sure on all of this myself. Perhaps someone can correct me. I'm really just learning this. Thanks.

[ajordan]

Originally posted by Manao
Searching for "YV12Convolution" would have lead you to the filter. Anyway, download the latest version (http://jourdan.madism.org/~manao/masktools-v1.5.zip), you'll see that there is a filter named YV12Convolution bundled with it.

Yes, I forgot to use the doom9 search. I searched in Google and in the external filters page in avisynth.org. The link to masktools there is not up to date... Thanks for the help!

[pieter1976]

Originally posted by trevlac
It seems your method was a point resize and then a gausian blur.

I used the Lanczos resizer of Ifrafiew to make the picture.
Using a sinc filter with lots of coefficients would give better edges but it will also intoduce artifacts. Alexey Lukin (http://audio.rightmark.org/lukin/graphics/lhouse_more.htm) has a nice site where he compares different interpolators. Maybe a hybrid filter would do the trick, using a sinc with lots of coefficients for edges and blurr for the other parts of the image. After this the ringing can be removed with a nonlinear filter like Xsharpen.

I used a down scaled image for removing ringing. The program looks for a 3x3 pixels match in the down scaled image. This methode is very slow but easy to make you self. The down scaled image has sharper edges.If the filter is executed the ringing will be replaced by the shaper edges.

[trevlac]

Originally posted by pieter1976
Using a sinc filter with lots of coefficients would give better edges but it will also intoduce artifacts.

Yes. This is because a Sinc has an infinate length. One must truncate it to actually use it. The 'windowing' filters like lanczos, start with a truncated Sinc which they then smooth out. Hence (if i understand correctly) MfA's comments about the tradeoff between ringing and bluring. There of course is a 3rd factor. That is time of computation. The more coefficients, the less ringing, the less you probably need to smooth it out.

I am really just beginning to understand all of this. Thank you for that link with the resample comparisons. Seems 'their' filter was the best!

Cheers

[pieter1976]

Here is a link to some information about the sinc function.

info sinc (http://ccrma.stanford.edu/~jos/Interpolation/sinc_function.html)

[pieter1976]

Originally posted by trevlac
Seems 'their' filter was the best!


I don't think that is totaly true. Smart-Edge removes a lot of detail and contrast the same for the NEDI filters. You want to keep the details Preserved. The Altamira Fractals program has more detail but the edges are not very nice.

[MfA]

Originally posted by trevlac
The more coefficients, the less ringing, the less you probably need to smooth it out.

No not really ...

Resampling filters for images dont serve the same task as a resampling filter does for for instance audio. There we are resampling bandwith limited signals ... but our eyes and cameras arent really bandwith limited sampling devices, they are area sampling devices.

Long truncated sinc filters work okay for images ... but they are far from ideal. Linear filters cant compete with nonlinear ones at most tasks in image processing.

[trevlac]

Originally posted by MfA
No not really ...

Resampling filters for images dont serve the same task as a resampling filter does for for instance audio. There we are resampling bandwith limited signals ... but our eyes and cameras arent really bandwith limited sampling devices, they are area sampling devices.

Long truncated sinc filters work okay for images ... but they are far from ideal. Linear filters cant compete with nonlinear ones at most tasks in image processing.

Ah MfA,

I am getting closer to understanding some of this stuff. Hopefully some day I will be able to see that:

"The idea is to vary the data path delay on the basis of a function of the second derivative of the U and V signal." == warpsharp.

:D

[pieter1976]

Does a resizer with sinc option exist for Avisynth?
I like the smooth edges. The artifacts can be removed i think.

(Why make it yourself when it already exist)

trevlac are you a developer yourself?

[Wilbert]

Does a resizer with sinc option exist for Avisynth?
Nope, not yet. It would be nice if someone could make one :)

[MfA]

Lanczos.

[trevlac]

Originally posted by pieter1976
Does a resizer with sinc option exist for Avisynth?
I like the smooth edges. The artifacts can be removed i think.

(Why make it yourself when it already exist)

trevlac are you a developer yourself?

As MfA pointed out, and I tried to explain. Lanczos is a 'windowed' sinc. Blackman, han, hamming, kaiser, I think these are other window function used on a sinc to make it usable. You have to truncate it and then the window smooths the effect of the truncation.

The Sinc example in your post must have been just a truncated version. It had really bad ringing.

If you would like a resizer/resampler that allows you to use your own filter coefficients, I'd say one does not really exist.

BTW: I have been learning this C programming stuff. It facilitates learning the digital video stuff. You actually get to see how things work. Does take quite a bit of time and patients. I'm probably further on with the C, than with the DSP. I'm a bit of a math dummy, so that holds me back. :)

[geoffwa]

Originally posted by trevlac


"The idea is to vary the data path delay on the basis of a function of the second derivative of the U and V signal." == warpsharp.



Is this true? I always assumed warpsharp worked on the first derivative (just looking at its output)

[trevlac]

Originally posted by geoffwa
Is this true? I always assumed warpsharp worked on the first derivative (just looking at its output)

That was a quote from a Philips doc MfA posted in the following thread:

http://forum.doom9.org/showthread.php?s=&threadid=76616

MfA said it is what warpsharp does. Beats me. :)

[MfA]

The first derivative doesnt tell you what part of an edge you are on, you can just use the first derivative but then you would displace edges. Only by using the second derivative can you warp toward the center of an edge.

Or something like the second derivative, the original photoshop/GIMP scripts from which most warpsharps evolved used edge-detection->blur->derivative but that isnt too far removed ... the original algorithm from the academic paper which started it all used a complex optimization procedure which accomplished pretty much the same thing in a really roundabout way, I suspect he just chose the way described in the paper because it allowed him to use a decent amount of math whereas the good implementations of warpsharp all would have been too simple and ad-hoc for him to get the paper published :)

Dunno what exactly warpsharp uses, the source code is unreadable.