# Convolution-based image interpolation

Started by April 23, 2006
```Michel Rouzic wrote:

...

> 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
^ ???
I get
0   0   0   1/6  1/2  5/6  1   1   1

Where did that zero come from?
> 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 :-)

The rows of Pascal's triangle approximate a Gaussian and are finite in
extent. Higher orders can be derived by convolving the sequence [1 1]
with itself any number of times. Each row is normalized by a division by
a power of 2.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;
```
```
Michel Rouzic wrote:
>
>
> But wait, a gaussian function isn't limited in time, right?
>

Whatever you use and whatever you choose to call it I can assure you it
will be not extend to infinity. Trust me you don't have to worry about
that :^)

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

each one. It's good you have realized that you don't actually need to do
the multiplying by zero, but remember if you are not going to require
that the old points remain unchanged then you are going to have to
calculate the new values at all the new positions not just the ones that
fall between the old.

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

It's not too bad. Lot's of different possible implementations. For a
simple cubic spline you are using 4 old points to find one new point.
That new point is situated somewhere between the middle 2 old points.
Just plug the position (from 0 to 1) of the desired new point into the
formula and out pops the new value for that position. Then move ahead to
the next new position and do the same using the 4 old points that
bracket that position.

> > 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 :-)
> >
>
> do you mean that there's anyone interpolating signals with anything
> from pascal's triangle?

Well the {1 2 1]/2 kernel discussed earlier is the second row of
Pascal's triangle. Applying it a second time as you suggested in another
post and that is equivalent to applying the 4th row of Pascal's triangle
as a kernel once.

-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:
> > > 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.

Don't thank me.  It won't do what you want.  Try it on a ramp signal
( 0, 1, 2, 3, 4, 5, 6, 7 ) . Using a small bell-shaped kernel will
scallop your interpolation.  A windowed-Sinc FIR will give you a
much smoother interpolation.

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

```
```Jerry Avins wrote:
> Michel Rouzic wrote:
>
>    ...
>
> > 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
>                                ^ ???
> I get
>    0   0   0   1/6  1/2  5/6  1   1   1
>
> Where did that zero come from?

how can you have 9 values when I had 8 at the beginning and that I
interpolated to twice its length. That zero is the last of the original
0's

> > 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 :-)
>
> The rows of Pascal's triangle approximate a Gaussian and are finite in
> extent. Higher orders can be derived by convolving the sequence [1 1]
> with itself any number of times. Each row is normalized by a division by
> a power of 2.

oh alright. well, sounds like just what I need, plus the algorithm to
get to that is quite simple.

```
```Ron N. wrote:
> Michel Rouzic wrote:
> > 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.
>
> Don't thank me.  It won't do what you want.  Try it on a ramp signal
> ( 0, 1, 2, 3, 4, 5, 6, 7 ) . Using a small bell-shaped kernel will
> scallop your interpolation.  A windowed-Sinc FIR will give you a
> much smoother interpolation.

1 1] cases. Well, since I don't want an FIR interpolation, widowed-sinc
or not, the only choice left is spline interpolation it seems... thanks
alot for help!

```
```
Michel Rouzic wrote:
>
> Jerry Avins wrote:

> >
> > I get
> >    0   0   0   1/6  1/2  5/6  1   1   1
^^^

This is OK as an interpolating scheme but not what was asked for. He had
the requirement that only the new values between the old be interpolated
(old values must remain unchanged). Yours fails to meet that
requirement. His didn't and was done correctly. It was (by design) made
to operate only on the new points locations since operations on the old
points locations is a waste of time.
But trying to preserve all the old values *and* using only positive
coefficients makes a fairly ugly interpolating scheme.

-jim

> >
> > Where did that zero come from?
>
> how can you have 9 values when I had 8 at the beginning and that I
> interpolated to twice its length. That zero is the last of the original
> 0's
>
> > > 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 :-)
> >
> > The rows of Pascal's triangle approximate a Gaussian and are finite in
> > extent. Higher orders can be derived by convolving the sequence [1 1]
> > with itself any number of times. Each row is normalized by a division by
> > a power of 2.
>
> oh alright. well, sounds like just what I need, plus the algorithm to
> get to that is quite simple.

----== 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:
> Jerry Avins wrote:

...

>>>0   0   0   0   0   0.167   0   0.5   1   0.833   1   1   1   0.833   1
>>
>>                               ^ ???
>>I get
>>   0   0   0   1/6  1/2  5/6  1   1   1
>>
>>Where did that zero come from?
>
>
> how can you have 9 values when I had 8 at the beginning and that I
> interpolated to twice its length. That zero is the last of the original
> 0's

I only wrote out the interesting part. My assumptions were different
from yours, and so my expansion may not be what you want. Where you
stuff zeros to double, I stuff Xs. Then the four points that are acted
on by the kernel are 4 _original_ points.

0  X  0  X  0  X  0  X  1  X  1  X  1  ....; a unit step. All the
initial Xs will be zero and the final Xs will be one. The interesting
region is the transition. For four points, I use the row of Pascal's
triangle [1 3 3 1]/8.

v
0  0  0  0  0  X  0  X  1  X  1  X  1  The indicated X becomes 1/8.
1/8   3/8   3/8   1/8 <- Kernel

v
0  0  0  0  0 1/8 0  X  1  X  1  X  1  The indicated X becomes 1/2.
1/8   3/8   3/8   1/8

v
0  0  0  0  0 1/8 0 1/2 1  X  1  X  1  The indicated X becomes 7/8.
1/8   3/8   3/8   1/8

All subsequent Xs become 1.

If you're not doubling, the details become harder to work out. Inserting
zeros and then filtering is only one way to interpolate. With splines
and binomial smoothing, intermediate points are calculated directly.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;
```
```Michel Rouzic wrote:
> Ron N. wrote:
> > Michel Rouzic wrote:
> > > 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.
> >
> > Don't thank me.  It won't do what you want.  Try it on a ramp signal
> > ( 0, 1, 2, 3, 4, 5, 6, 7 ) . Using a small bell-shaped kernel will
> > scallop your interpolation.  A windowed-Sinc FIR will give you a
> > much smoother interpolation.
>
> oh yeah! I hadn't thought about it... I only thought about the [0 0 0 1
> 1 1] cases. Well, since I don't want an FIR interpolation, widowed-sinc
> or not, the only choice left is spline interpolation it seems...

A spline won't do what you wanted in your example either.  A low
enough degree spline would be the same as linear interpolation, and
a high degree spline would show "ripples" before and/or after any
step function.  If you want an interpolation that has none of the
above, start inventing.

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

```
```jim wrote:
> Michel Rouzic wrote:
> >
> > Jerry Avins wrote:
>
> > >
> > > I get
> > >    0   0   0   1/6  1/2  5/6  1   1   1
>                         ^^^
>
> This is OK as an interpolating scheme but not what was asked for. He had
> the requirement that only the new values between the old be interpolated
> (old values must remain unchanged). Yours fails to meet that
> requirement. His didn't and was done correctly. It was (by design) made
> to operate only on the new points locations since operations on the old
> points locations is a waste of time.
> 	But trying to preserve all the old values *and* using only positive
> coefficients makes a fairly ugly interpolating scheme.

I use only positive coefficients because that's all I'll be using. But
somebody pointed out that using a bell-shaped curve would scallop a
ramp, and because of this I have no other choice but to use spline
interpolation if i don't want to meet this problem. makes things harder
that I wanted but i've met bigger difficulties and anyways it was only
a matter of time before I had to deal with splines I guess.

```
```
"Ron N." wrote:

> A spline won't do what you wanted in your example either.  A low
> enough degree spline would be the same as linear interpolation, and
> a high degree spline would show "ripples" before and/or after any
> step function.

Nope that's bad information. Some will and some won't. It depends on the
type of spline interpolation.

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