Convolution-based image interpolation

Started by Michel Rouzic 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. �����������������������������������������������������������������������
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?
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.
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. �����������������������������������������������������������������������

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