Convolution-based image interpolation

Michel Rouzic wrote:
> chris_bore@yahoo.co.uk wrote:
> > Michel Rouzic wrote:
> > > who would want to interpolate images by FIRs anyways?
> >
> > It is quite common to interpolate images by FIRs. This is especially so
> > in digital video where natural images are concerned, as it may give the
> > most pleasing visual effect. It can also be very suitable where
> > interpolation by non-simple integer ratios is needed, as polyphase FIR
> > filters can be used and are often available as hardware blocks.
>
> oh, I didn't know. my main problem with FIRs in what I want to do is
> that it introduces ripples where I don't want any...

Why don't you want ripples?  How do you know they don't belong
in the image?


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

jim wrote:
> Michel Rouzic wrote:
>
> >
> > > Would the
> > > result then be a new value for the new samples between the old and all
> > > the old would remain the same or would the old samples be modified also?
> >
> > Well, it depends on whether the bell-curved function is finite (like a
> > Blackman window) or not (like a gaussian function, i think). if the
> > function is finite, and it's what I would like best, then yeah the old
> > samples would keep their original value.
>
> Well its not going to be a function. Its just going to be a set of
> weights or coefficients (i.e. numbers) you are going to be using. You
> might arrive at those values by sampling some function.

Isn't it the same thing?

> 	If you want the old samples to stay unchanged and you stuff one zero
> between each old sample and convolve then your 1d kernel would have to
> look like this:
>
>   .....X 0 X 1 X 0 X .....  {where sum of all X values should total one)
>
> That doesn't look much like it came from a bell shaped function.

Sorry but there I don't follow you anymore.. oh by the way, the
function would have to be overlapable or whatever you wanna call that,
just like the Blackman function and the likes.

> Maybe
> you mean in the frequency domain.

Not at all :-)

> It wouldn't be hard to construct a set
> of coefficients that fit this pattern that had a bell shaped frequency
> response  (raised cosine).

You know, what I'm asking about, it's not about inventing a whole new
solution or anything, I'm just asking, which function have people been
using to interpolate images when they weren't using FIRs, linear
interpolation or spline interpolation.

> > >        At any rate it all boils down to this: for each new sample take a
> > > weighted sum of some defined set of old samples that are in the
> > > neighborhood.
> >
> > Provided that I take the weighted sums of the two nearby old samples,
> > wouldn't it be linear interpolation?
>
> yes, provided that weight was on a line between the 2 old values at the
> point where you are to create the new value (like half way).
>
> >I don't know what it would be if I
> > took for example four, but i'm pretty sure it's not what I'm looking
> > for.
> >
>
> That could be some variation on cubic interpolation. If you are working
> in 2d that would actually mean 16 old samples to create one new - do you
> want to use more?

It's not about using more, it's about the shape of the result. let's
say that I got this signal :

0   0   0   0   1   1   1   1

And that I interpolate it to twice its length using a weighted sum of
the four neighbohouring samples, an immediate neighbor counting for 1/3
and otherwise 1/6, i'd get the following :

0   0   0   0   0   0.167   0   0.5   1   0.833   1   1   1   0.833   1

Not really what I want, and I don't see how I could possibly change the
1/3 and 1/6 weightings in order to get to something that'd be more like

0   0   0   0   0   0   0   0.5   1   1   1   1   1   1   1

well changing them to 0.5 and 0 would do it, but like I said, I don't
want linear interpolation. Besides that, it doesn't give you much
freedom, at least not the freedom of zero-stuffing by any number of
samples you want and convolve

I persist in asking for a bell-shaped function :-)

Ron N. wrote:
> Michel Rouzic wrote:
> > chris_bore@yahoo.co.uk wrote:
> > > Michel Rouzic wrote:
> > > > who would want to interpolate images by FIRs anyways?
> > >
> > > It is quite common to interpolate images by FIRs. This is especially so
> > > in digital video where natural images are concerned, as it may give the
> > > most pleasing visual effect. It can also be very suitable where
> > > interpolation by non-simple integer ratios is needed, as polyphase FIR
> > > filters can be used and are often available as hardware blocks.
> >
> > oh, I didn't know. my main problem with FIRs in what I want to do is
> > that it introduces ripples where I don't want any...
>
> Why don't you want ripples?  How do you know they don't belong
> in the image?

I'll try to explain you without going to deep into the details
particular to my application. What I want to interpolate is not an
image, but a simple 1d curve, this curve represents an envelope to
apply to a signal. However, this envelope has a much lower samplerate
than the signal to modulate it with, thus I gotta interpolate.

The problem with interpolating it with a FIR is, well, let's illustrate
it like this, imagine this is a chunk of my enveloppe

               *    *    *    *
               *    *    *    *
               *    *    *    *
               *    *    *    *
*    *    *    *    *    *    *

and here's how it'd be like when I interpolate with a FIR

                **    ****   **
               ****  **********
       **      ****************
      ****    *****************
*******************************
 ***      ****
           **
as in reality the curve that I want to obtain is more like :

	          *************
	      *****************
	     ******************
           ********************
*******************************

in the first half of the signal, i'd like to have full silence, and it
to start increasing only between the last 0 value and the first 1
value, otherwise due to the ripples I'd have the signal to modulate
partially "let by" when it should, plus for quite a long time, as I
want full silence.

Ron N. wrote:
> Michel Rouzic wrote:
> > chris_bore@yahoo.co.uk wrote:
> > > Michel Rouzic wrote:
> > > > who would want to interpolate images by FIRs anyways?
> > >
> > > It is quite common to interpolate images by FIRs. This is especially so
> > > in digital video where natural images are concerned, as it may give the
> > > most pleasing visual effect. It can also be very suitable where
> > > interpolation by non-simple integer ratios is needed, as polyphase FIR
> > > filters can be used and are often available as hardware blocks.
> >
> > oh, I didn't know. my main problem with FIRs in what I want to do is
> > that it introduces ripples where I don't want any...
>
> Why don't you want ripples?  How do you know they don't belong
> in the image?

by the way, I'm like a hungry shark only asking to be thrown pieces of
meat at, and all you people is doing is discussing why I would want
that. That's cool, but if you could also throw some names of suitable
bell-shaped functions for image interpolation, I'd appreciate that.

I'm sure that in the end I'll have explained you all why some method
won't work and why I want what i claim to want, but I'm not sure to
even be told the name of a single bell-shaped self-overlapping function
as it's really all I'm asking for.

Michel Rouzic wrote:
> jim wrote:
> > Michel Rouzic wrote:
> > > > Would the
> > > > result then be a new value for the new samples between the old and all
> > > > the old would remain the same or would the old samples be modified also?
> > >
> > > Well, it depends on whether the bell-curved function is finite (like a
> > > Blackman window) or not (like a gaussian function, i think). if the
> > > function is finite, and it's what I would like best, then yeah the old
> > > samples would keep their original value.
> >
> > Well its not going to be a function. Its just going to be a set of
> > weights or coefficients (i.e. numbers) you are going to be using. You
> > might arrive at those values by sampling some function.
>
> Isn't it the same thing?
>
> > 	If you want the old samples to stay unchanged and you stuff one zero
> > between each old sample and convolve then your 1d kernel would have to
> > look like this:
> >
> >   .....X 0 X 1 X 0 X .....  {where sum of all X values should total one)
> >
> > That doesn't look much like it came from a bell shaped function.
>
> Sorry but there I don't follow you anymore..

What don't you follow?  Do you want the old samples to change?
If not, then any input to the covolution which could change the
old sample has to be multiplied by a zero.  Do you agree?

> oh by the way, the
> function would have to be overlapable or whatever you wanna call that,
> just like the Blackman function and the likes.

Why?

> > Maybe
> > you mean in the frequency domain.
>
> Not at all :-)
>
> > It wouldn't be hard to construct a set
> > of coefficients that fit this pattern that had a bell shaped frequency
> > response  (raised cosine).
>
> You know, what I'm asking about, it's not about inventing a whole new
> solution or anything, I'm just asking, which function have people been
> using to interpolate images when they weren't using FIRs, linear
> interpolation or spline interpolation.

Why do you think that isn't some whole new interpolation method?

> > > >        At any rate it all boils down to this: for each new sample take a
> > > > weighted sum of some defined set of old samples that are in the
> > > > neighborhood.
> > >
> > > Provided that I take the weighted sums of the two nearby old samples,
> > > wouldn't it be linear interpolation?
> >
> > yes, provided that weight was on a line between the 2 old values at the
> > point where you are to create the new value (like half way).
> >
> > >I don't know what it would be if I
> > > took for example four, but i'm pretty sure it's not what I'm looking
> > > for.
> > >
> >
> > That could be some variation on cubic interpolation. If you are working
> > in 2d that would actually mean 16 old samples to create one new - do you
> > want to use more?
>
> It's not about using more, it's about the shape of the result. let's
> say that I got this signal :
>
> 0   0   0   0   1   1   1   1
>
> And that I interpolate it to twice its length using a weighted sum of
> the four neighbohouring samples, an immediate neighbor counting for 1/3
> and otherwise 1/6, i'd get the following :
>
> 0   0   0   0   0   0.167   0   0.5   1   0.833   1   1   1   0.833   1
>
> Not really what I want, and I don't see how I could possibly change the
> 1/3 and 1/6 weightings in order to get to something that'd be more like
>
> 0   0   0   0   0   0   0   0.5   1   1   1   1   1   1   1

That looks like the result of a linear interpolation.

> well changing them to 0.5 and 0 would do it, but like I said, I don't
> want linear interpolation.

Then why does you example above look exactly like linear
interpolation?

> Besides that, it doesn't give you much
> freedom, at least not the freedom of zero-stuffing by any number of
> samples you want and convolve
>
> I persist in asking for a bell-shaped function :-)

A Gaussian blur is bell-shaped.  But it doesn't preserve the old
samples.  Which do you want?


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

Michel Rouzic wrote:

> > Well its not going to be a function. Its just going to be a set of
> > weights or coefficients (i.e. numbers) you are going to be using. You
> > might arrive at those values by sampling some function.
> 
> Isn't it the same thing?

In the limit yes if you have an infinite number of points it approaches
the same thing as a function, but when you have 4 points then I would
say no its not even close to the same thing.

> 
> >       If you want the old samples to stay unchanged and you stuff one zero
> > between each old sample and convolve then your 1d kernel would have to
> > look like this:
> >
> >   .....X 0 X 1 X 0 X .....  {where sum of all X values should total one)
> >
> > That doesn't look much like it came from a bell shaped function.

> It's not about using more, it's about the shape of the result. let's
> say that I got this signal :
> 
> 0   0   0   0   1   1   1   1
> 
> And that I interpolate it to twice its length using a weighted sum of
> the four neighbohouring samples, an immediate neighbor counting for 1/3
> and otherwise 1/6, i'd get the following :
> 
> 0   0   0   0   0   0.167   0   0.5   1   0.833   1   1   1   0.833   1
> 
> Not really what I want, and I don't see how I could possibly change the
> 1/3 and 1/6 weightings in order to get to something that'd be more like

You are saying you are using the convolution kernel [1 0 2 6 2 0 1]/6 
to get those results. The ripple is really due to your constraint that
the old samples remain the same if you are willing to give up that
requirement you can make something that has a step response that is more
rounded with no ripple (nice and warm and fuzzy). Otherwise you are
going to have to put in those zeroes in your kernel (or keep the length
less than 4)


> 
> 0   0   0   0   0   0   0   0.5   1   1   1   1   1   1   1


That would be the convolution kernel [1 2 1]/2 That will be the only
kernel that fits all your criteria for upsampling by 2. It can be fitted
to a gaussian function (bell shape) and it leaves the old samples
unchanged. You can't really go to anything else that will meet all your
criteria.

> 
> well changing them to 0.5 and 0 would do it, but like I said, I don't
> want linear interpolation.

Do you mean using a convolution kernel of [1 1] ? That would give you

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1  from  0 0 0 0 1 1 1 1



> Besides that, it doesn't give you much
> freedom, at least not the freedom of zero-stuffing by any number of
> samples you want and convolve
> 

That's where spline interpolation is real handy. Its essentially a
method of calculating the needed weighting to calculate each new sample
for any arbitrary point between the old samples. Zero stuffing is not
going to work very well for anything but upsampling by integer amounts.



> I persist in asking for a bell-shaped function :-)

Google "Pascal's triangle".

-jim

----== 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 =----

Michel Rouzic wrote:
> Ron N. wrote:
> > Michel Rouzic wrote:
> > > chris_bore@yahoo.co.uk wrote:
> > > > Michel Rouzic wrote:
> > > > > who would want to interpolate images by FIRs anyways?
> > > >
> > > > It is quite common to interpolate images by FIRs. This is especially so
> > > > in digital video where natural images are concerned, as it may give the
> > > > most pleasing visual effect. It can also be very suitable where
> > > > interpolation by non-simple integer ratios is needed, as polyphase FIR
> > > > filters can be used and are often available as hardware blocks.
> > >
> > > oh, I didn't know. my main problem with FIRs in what I want to do is
> > > that it introduces ripples where I don't want any...
> >
> > Why don't you want ripples?  How do you know they don't belong
> > in the image?
>
> by the way, I'm like a hungry shark only asking to be thrown pieces of
> meat at, and all you people is doing is discussing why I would want
> that. That's cool, but if you could also throw some names of suitable
> bell-shaped functions for image interpolation, I'd appreciate that.
>
> I'm sure that in the end I'll have explained you all why some method
> won't work and why I want what i claim to want, but I'm not sure to
> even be told the name of a single bell-shaped self-overlapping function
> as it's really all I'm asking for.

Inverted Cosine.  One cycle.

Ron N. wrote:
> Michel Rouzic wrote:
> > jim wrote:
> > > Michel Rouzic wrote:
> > > > > Would the
> > > > > result then be a new value for the new samples between the old and all
> > > > > the old would remain the same or would the old samples be modified also?
> > > >
> > > > Well, it depends on whether the bell-curved function is finite (like a
> > > > Blackman window) or not (like a gaussian function, i think). if the
> > > > function is finite, and it's what I would like best, then yeah the old
> > > > samples would keep their original value.
> > >
> > > Well its not going to be a function. Its just going to be a set of
> > > weights or coefficients (i.e. numbers) you are going to be using. You
> > > might arrive at those values by sampling some function.
> >
> > Isn't it the same thing?
> >
> > > 	If you want the old samples to stay unchanged and you stuff one zero
> > > between each old sample and convolve then your 1d kernel would have to
> > > look like this:
> > >
> > >   .....X 0 X 1 X 0 X .....  {where sum of all X values should total one)
> > >
> > > That doesn't look much like it came from a bell shaped function.
> >
> > Sorry but there I don't follow you anymore..
>
> What don't you follow?  Do you want the old samples to change?
> If not, then any input to the covolution which could change the
> old sample has to be multiplied by a zero.  Do you agree?
>
> > oh by the way, the
> > function would have to be overlapable or whatever you wanna call that,
> > just like the Blackman function and the likes.
>
> Why?

overlapable so that if I have the following signal : 1   1   1   1 it
will be interpolated as 1   1   1   1   1   1   1   1   1 if for
example it has to be interpolated to twice its length

> > > Maybe
> > > you mean in the frequency domain.
> >
> > Not at all :-)
> >
> > > It wouldn't be hard to construct a set
> > > of coefficients that fit this pattern that had a bell shaped frequency
> > > response  (raised cosine).
> >
> > You know, what I'm asking about, it's not about inventing a whole new
> > solution or anything, I'm just asking, which function have people been
> > using to interpolate images when they weren't using FIRs, linear
> > interpolation or spline interpolation.
>
> Why do you think that isn't some whole new interpolation method?

dude... interpolating a signal by some bell-shaped function cannot
possibly be some whole new thing...

> > > > >        At any rate it all boils down to this: for each new sample take a
> > > > > weighted sum of some defined set of old samples that are in the
> > > > > neighborhood.
> > > >
> > > > Provided that I take the weighted sums of the two nearby old samples,
> > > > wouldn't it be linear interpolation?
> > >
> > > yes, provided that weight was on a line between the 2 old values at the
> > > point where you are to create the new value (like half way).
> > >
> > > >I don't know what it would be if I
> > > > took for example four, but i'm pretty sure it's not what I'm looking
> > > > for.
> > > >
> > >
> > > That could be some variation on cubic interpolation. If you are working
> > > in 2d that would actually mean 16 old samples to create one new - do you
> > > want to use more?
> >
> > It's not about using more, it's about the shape of the result. let's
> > say that I got this signal :
> >
> > 0   0   0   0   1   1   1   1
> >
> > And that I interpolate it to twice its length using a weighted sum of
> > the four neighbohouring samples, an immediate neighbor counting for 1/3
> > and otherwise 1/6, i'd get the following :
> >
> > 0   0   0   0   0   0.167   0   0.5   1   0.833   1   1   1   0.833   1
> >
> > Not really what I want, and I don't see how I could possibly change the
> > 1/3 and 1/6 weightings in order to get to something that'd be more like
> >
> > 0   0   0   0   0   0   0   0.5   1   1   1   1   1   1   1
>
> That looks like the result of a linear interpolation.

Exactly, because this isn't a good example :-) if you were to
interpolate the example of above once again you would get in the middle
0   0.25   0.5   0.75   1 as I'd rather expect something close to 0
0.15   0.5   0.85   1

> > well changing them to 0.5 and 0 would do it, but like I said, I don't
> > want linear interpolation.
>
> Then why does you example above look exactly like linear
> interpolation?
>
> > Besides that, it doesn't give you much
> > freedom, at least not the freedom of zero-stuffing by any number of
> > samples you want and convolve
> >
> > I persist in asking for a bell-shaped function :-)
>
> A Gaussian blur is bell-shaped.  But it doesn't preserve the old
> samples.  Which do you want?

Well I thought about using a Gaussian function, but it isn't time
limited, and i'd need one that'd be limited in time.

jim wrote:
> Michel Rouzic wrote:
>
> > > Well its not going to be a function. Its just going to be a set of
> > > weights or coefficients (i.e. numbers) you are going to be using. You
> > > might arrive at those values by sampling some function.
> >
> > Isn't it the same thing?
>
> In the limit yes if you have an infinite number of points it approaches
> the same thing as a function, but when you have 4 points then I would
> say no its not even close to the same thing.
>
> >
> > >       If you want the old samples to stay unchanged and you stuff one zero
> > > between each old sample and convolve then your 1d kernel would have to
> > > look like this:
> > >
> > >   .....X 0 X 1 X 0 X .....  {where sum of all X values should total one)
> > >
> > > That doesn't look much like it came from a bell shaped function.
>
> > It's not about using more, it's about the shape of the result. let's
> > say that I got this signal :
> >
> > 0   0   0   0   1   1   1   1
> >
> > And that I interpolate it to twice its length using a weighted sum of
> > the four neighbohouring samples, an immediate neighbor counting for 1/3
> > and otherwise 1/6, i'd get the following :
> >
> > 0   0   0   0   0   0.167   0   0.5   1   0.833   1   1   1   0.833   1
> >
> > Not really what I want, and I don't see how I could possibly change the
> > 1/3 and 1/6 weightings in order to get to something that'd be more like
>
> You are saying you are using the convolution kernel [1 0 2 6 2 0 1]/6
> to get those results. The ripple is really due to your constraint that
> the old samples remain the same if you are willing to give up that
> requirement you can make something that has a step response that is more
> rounded with no ripple (nice and warm and fuzzy). Otherwise you are
> going to have to put in those zeroes in your kernel (or keep the length
> less than 4)

old samples remaining the same is not a constraint, but they would
remain the same the way I imagined them.

> >
> > 0   0   0   0   0   0   0   0.5   1   1   1   1   1   1   1
>
>
> That would be the convolution kernel [1 2 1]/2 That will be the only
> kernel that fits all your criteria for upsampling by 2. It can be fitted
> to a gaussian function (bell shape) and it leaves the old samples
> unchanged. You can't really go to anything else that will meet all your
> criteria.

But wait, a gaussian function isn't limited in time, right?

> >
> > well changing them to 0.5 and 0 would do it, but like I said, I don't
> > want linear interpolation.
>
> Do you mean using a convolution kernel of [1 1] ? That would give you
>
> 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1  from  0 0 0 0 1 1 1 1

are you sure? wouldn't it give you a bunch of 2's?

> > Besides that, it doesn't give you much
> > freedom, at least not the freedom of zero-stuffing by any number of
> > samples you want and convolve
> >
>
> That's where spline interpolation is real handy. Its essentially a
> method of calculating the needed weighting to calculate each new sample
> for any arbitrary point between the old samples.

Yeah, sounds pretty good, but that's up to implementing it that the
difficulty seems to reside. the equations didn't seem that simple,
mostly that it had polynomials, but i might try to implement that
anyways. given that i'm not sure to understand how to implement it i
won't count on it tho

> Zero stuffing is not
> going to work very well for anything but upsampling by integer amounts.
>
>
>
> > I persist in asking for a bell-shaped function :-)
>
> Google "Pascal's triangle".

do you mean that there's anyone interpolating signals with anything
from pascal's triangle?

Ron N. wrote:
> Michel Rouzic wrote:
> > Ron N. wrote:
> > > Michel Rouzic wrote:
> > > > chris_bore@yahoo.co.uk wrote:
> > > > > Michel Rouzic wrote:
> > > > > > who would want to interpolate images by FIRs anyways?
> > > > >
> > > > > It is quite common to interpolate images by FIRs. This is especially so
> > > > > in digital video where natural images are concerned, as it may give the
> > > > > most pleasing visual effect. It can also be very suitable where
> > > > > interpolation by non-simple integer ratios is needed, as polyphase FIR
> > > > > filters can be used and are often available as hardware blocks.
> > > >
> > > > oh, I didn't know. my main problem with FIRs in what I want to do is
> > > > that it introduces ripples where I don't want any...
> > >
> > > Why don't you want ripples?  How do you know they don't belong
> > > in the image?
> >
> > by the way, I'm like a hungry shark only asking to be thrown pieces of
> > meat at, and all you people is doing is discussing why I would want
> > that. That's cool, but if you could also throw some names of suitable
> > bell-shaped functions for image interpolation, I'd appreciate that.
> >
> > I'm sure that in the end I'll have explained you all why some method
> > won't work and why I want what i claim to want, but I'm not sure to
> > even be told the name of a single bell-shaped self-overlapping function
> > as it's really all I'm asking for.
>
> Inverted Cosine.  One cycle.

oh, wow, ok, sounds good. i'll give it a try, thanks alot.