# Convolution-based image interpolation

Started by April 23, 2006
```I'm looking forward implementing image interpolation in one dimension
at once, however I don't really know how to do it.

Linear interpolation doesn't fit me good, I need something better, more
like cubic spline interpolation, but the only problem that well
implementing it doesn't sound like such an easy thing (I will if I have
to, but it definitely won't be my first choice for that precise
reason), and so I'd like to make it convolution based, because I
understand that good/easily can implement it, however FIR interpolation
(I call that convolution based because it's about zero-stuffing and
then convolution by a FIR) is definitly not what I'm looking for due to
the ripples it creates (who would want to interpolate images by FIRs
anyways?), I thought that some bell-shaped function might do it good,
but I don't really know, so my question is, which function would fit
the job best?

I'm looking for something that would give me results close to cubic
spline interpolation.

```
```alright, maybe didn't I ask the question properly, let me re-phrase it.

What bell-shaped function is the best for image interpolation?

```
```Michel Rouzic wrote:
> alright, maybe didn't I ask the question properly, let me re-phrase it.
>
> What bell-shaped function is the best for image interpolation?

Why do you think that superimposing a bunch of weighted bell curves will
need less computation than spline interpolation? You rejected the simple
solution in favor of a simpler one. There is no answer unless you invent
one yourself.

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

Chris
===================
Chris Bore
www.bores.com

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

```
```Jerry Avins wrote:
> Michel Rouzic wrote:
> > alright, maybe didn't I ask the question properly, let me re-phrase it.
> >
> > What bell-shaped function is the best for image interpolation?
>
> Why do you think that superimposing a bunch of weighted bell curves will
> need less computation than spline interpolation?

simpleness of implementation, since the maths behind the spline
interpolation as I saw on wikipedia are too hard for me (I never
understood polynomials although I studied them in college)

> You rejected the simple
> solution in favor of a simpler one. There is no answer unless you invent
> one yourself.

Now you got me scratching my head. You can't possibly mean that I can't
interpolate a signal by zero-stuffing it and convolving it with a
bell-shaped function, because that's all I want to do, and I know it
can be done. I'd only need to know which of these functions would do it
good.

```
```Michel Rouzic wrote:
> Jerry Avins wrote:
>
>>Michel Rouzic wrote:
>>
>>>alright, maybe didn't I ask the question properly, let me re-phrase it.
>>>
>>>What bell-shaped function is the best for image interpolation?
>>
>>Why do you think that superimposing a bunch of weighted bell curves will
>>need less computation than spline interpolation?
>
>
> uh? who talked about needing less computation? I only talked about
> simpleness of implementation, since the maths behind the spline
> interpolation as I saw on wikipedia are too hard for me (I never
> understood polynomials although I studied them in college)
>
>
>>You rejected the simple
>>solution in favor of a simpler one. There is no answer unless you invent
>>one yourself.
>
>
> Now you got me scratching my head. You can't possibly mean that I can't
> interpolate a signal by zero-stuffing it and convolving it with a
> bell-shaped function, because that's all I want to do, and I know it
> can be done. I'd only need to know which of these functions would do it
> good.

I was confused then. Splines are pretty simple, so it must be the
notation that bothers you. You understand linear interpolation.
Quadratic interpolation consists of finding that parabola that passes
through three successive points (equally spaced on the horizontal axis
simplifies the math) and locating the desired point on it. Cubic
interpolation allows an extra degree of freedom that can be used to
include a fourth point or a slope at an endpoint. Quartic .... You get
the idea. Chuck the book and work out the equations for yourself.

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:

> Now you got me scratching my head. You can't possibly mean that I can't
> interpolate a signal by zero-stuffing

Do you mean (for instance) inserting a zero between each existing sample
and then convolving with a kernel that resembles a bell shape? 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?
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. This is pretty much how it works what ever you choose to
call it. Which particular old samples are to be used to create each new
sample and how much weight to give those samples are what distinguishes
one algorithm from another.
If you are working in 2d you can do the x and y separately or do the
equivalent as one operation.

-jim

> it and convolving it with a
> bell-shaped function, because that's all I want to do, and I know it
> can be done. I'd only need to know which of these functions would do it
> good.

----== 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 =----
```
```jim wrote:
> Michel Rouzic wrote:
>
> > Now you got me scratching my head. You can't possibly mean that I can't
> > interpolate a signal by zero-stuffing
>
> Do you mean (for instance) inserting a zero between each existing sample
> and then convolving with a kernel that resembles a bell shape?

Yup

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

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

> This is pretty much how it works what ever you choose to
> call it. Which particular old samples are to be used to create each new
> sample and how much weight to give those samples are what distinguishes
> one algorithm from another.
> 	If you are working in 2d you can do the x and y separately or do the
> equivalent as one operation.

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

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. Maybe
you mean in the frequency domain. It wouldn't be hard to construct a set
of coefficients that fit this pattern that had a bell shaped frequency
response  (raised cosine).

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

-jim

> > This is pretty much how it works what ever you choose to
> > call it. Which particular old samples are to be used to create each new
> > sample and how much weight to give those samples are what distinguishes
> > one algorithm from another.
> >       If you are working in 2d you can do the x and y separately or do the
> > equivalent as one operation.

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