Let's say I have a signal (an impulse response) which contains no
frequency components above a certain frequency. Let's say that the
highest frequency component has a period matching to half the width of
the impulse response (which on our graph is the width of the
triangle).
Considering this, if I wanted to obtain a signal identical to the step
response (aka the anti-derivative of the impulse response) of this
signal by simply adding a bunch of offset copies of this impulse
response together, what would be the largest offset I could use
between the copies in order to obtain a signal that matches exactly to
the anti-derivative of the original impulse response?
*
* *
* * <--- That's the impulse response
we
* * begin with
**************** ************
+
*
* *
* * <--- We add offset copies to
itself
* *
******************** ********
+
*
* *
* *
* *
************************ *****
+
*
* *
* *
* *
**************************** *
+
*
*
*
*
********************************
=
*****************
* Ultimately we obtain a
signal
* <--- matching to the anti-
derivative
* of the impulse response,
hence a
**************** step response
But how do we calculate the largest usable offset? Also, can I assume
that any offset smaller than that largest offset is suitable?
Thanks in advance.
PS : Please don't ask what I really need this for (since I don't
actually need it to just turn an impulse response into a step
response), I just couldn't explain what I need this for in a way that
would make sense to anyone but myself.
Step response from adding impulse responses together
Started by ●February 18, 2008
Reply by ●February 18, 20082008-02-18
Michel Rouzic wrote:> Let's say I have a signal (an impulse response) which contains no > frequency components above a certain frequency. Let's say that the > highest frequency component has a period matching to half the width of > the impulse response (which on our graph is the width of the > triangle).So sorry to pick nits, but if the time-domain response is of finite extent, then the frequency response is of infinite extent. An infinite time-domain response doesn't necessarily imply a finite frequency response, though.> > Considering this, if I wanted to obtain a signal identical to the step > response (aka the anti-derivative of the impulse response) of this > signal by simply adding a bunch of offset copies of this impulse > response together, what would be the largest offset I could use > between the copies in order to obtain a signal that matches exactly to > the anti-derivative of the original impulse response? >Once the offset is equal to the full extent of the non-zero impulse response, then you're done.> > PS : Please don't ask what I really need this for (since I don't > actually need it to just turn an impulse response into a step > response), I just couldn't explain what I need this for in a way that > would make sense to anyone but myself.OK. I'll contain my curiosity, with difficulty :-). -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●February 18, 20082008-02-18
Tim Wescott wrote:> Michel Rouzic wrote: > > Let's say I have a signal (an impulse response) which contains no > > frequency components above a certain frequency. Let's say that the > > highest frequency component has a period matching to half the width of > > the impulse response (which on our graph is the width of the > > triangle). > > So sorry to pick nits, but if the time-domain response is of finite > extent, then the frequency response is of infinite extent. An infinite > time-domain response doesn't necessarily imply a finite frequency > response, though.Crap, now that you're telling me this, I'm realising that my impulse response is going to have a frequency response of infinite extent because it's zero-padded.> Once the offset is equal to the full extent of the non-zero impulse > response, then you're done.The full extent? Wouldn't the result look like that then : * * * * * * * * * * * * * * * * * * **************** * *> OK. I'll contain my curiosity, with difficulty :-).I don't know if it's a sarcasm, but I'll assume it's not. The thing is, I noticed that interpolation by nearest neighbour produce dimmer mirror images than interpolation by zero-stuffing. Going from there, the idea is to replace zero-stuffing prior to convolution with a low- pass filter by a nearest neighbour. In order to implement that, considered that nearest neighbour interpolation is like zero stuffing + convolution with a rectangle (is it even correct?), my idea is to convolve a rectangle of appropriate size (the spacing between original bins once zero-stuffing is applied) with the low-pass filtering FIR, and to use that new FIR to filter the zero stuffed signal. The problem is, in my case, I want to use that to downsize signals by non-integer ratios, and in order to do that I need to calculate interpolated/filtered bins at non-integer indexes. Traditionally, one would calculate the value of this bin at a non-integer index by having the weighted sums of the neighbour original bins and their weight would be function of the distance to the new bin using the formula used to calculate the FIR. The problem is that with what I want to do, I wouldn't just use the FIR formula once to weight each neighbour bin, I would use it multiple times to do as if that FIR was convolved with the rectangle. The question is, depending on the FIR formula and the width of the rectangle, how much space can I have at most between copies of this FIR in order to act as if the FIR was convolved with the rectangle? Oh and if at that point you're wondering "Why oh why going through all that trouble?", well that's cause I want to use a FIR with a fairly poor low-pass filtering characteristics, namely a Blackman function.
Reply by ●February 18, 20082008-02-18
Michel Rouzic wrote:> > Tim Wescott wrote: >> Michel Rouzic wrote: >>> Let's say I have a signal (an impulse response) which contains no >>> frequency components above a certain frequency. Let's say that the >>> highest frequency component has a period matching to half the width of >>> the impulse response (which on our graph is the width of the >>> triangle). >> So sorry to pick nits, but if the time-domain response is of finite >> extent, then the frequency response is of infinite extent. An infinite >> time-domain response doesn't necessarily imply a finite frequency >> response, though. > > Crap, now that you're telling me this, I'm realising that my impulse > response is going to have a frequency response of infinite extent > because it's zero-padded. > >> Once the offset is equal to the full extent of the non-zero impulse >> response, then you're done. > > The full extent? Wouldn't the result look like that then : > > * * * > * * * * * > * * * * * > * * * * * > **************** * * >Hmm. Try this: "Once the offset is equal to the full extent of the non-zero impulse response, the result will be constant". Better? With a triangular impulse response the step response will be a pair of parabolas, one starting at 0 and rising up to 1/2 of the total at the peak of the impulse response (if it's a symmetrical triangle), and one starting where the first leaves off and rising to the total sum of the non-zero samples of the impulse response, then a straight line from there to infinity.> >> OK. I'll contain my curiosity, with difficulty :-). > > I don't know if it's a sarcasm, but I'll assume it's not.It was, but it was directed at me, not you.> The thing > is, I noticed that interpolation by nearest neighbour produce dimmer > mirror images than interpolation by zero-stuffing. Going from there, > the idea is to replace zero-stuffing prior to convolution with a low- > pass filter by a nearest neighbour. > > In order to implement that, considered that nearest neighbour > interpolation is like zero stuffing + convolution with a rectangle (is > it even correct?), my idea is to convolve a rectangle of appropriate > size (the spacing between original bins once zero-stuffing is applied) > with the low-pass filtering FIR, and to use that new FIR to filter the > zero stuffed signal. > > The problem is, in my case, I want to use that to downsize signals by > non-integer ratios, and in order to do that I need to calculate > interpolated/filtered bins at non-integer indexes. Traditionally, one > would calculate the value of this bin at a non-integer index by having > the weighted sums of the neighbour original bins and their weight > would be function of the distance to the new bin using the formula > used to calculate the FIR. The problem is that with what I want to do, > I wouldn't just use the FIR formula once to weight each neighbour bin, > I would use it multiple times to do as if that FIR was convolved with > the rectangle. > > The question is, depending on the FIR formula and the width of the > rectangle, how much space can I have at most between copies of this > FIR in order to act as if the FIR was convolved with the rectangle? > > Oh and if at that point you're wondering "Why oh why going through all > that trouble?", well that's cause I want to use a FIR with a fairly > poor low-pass filtering characteristics, namely a Blackman function.I'm not much of a vidiot, but I suspect that your image isn't getting _dimmer_ so much as the edges are softening up. Without going to really sophisticated algorithms that interpolate the positions of edges and regenerate the image from that, I suspect that no matter what you do you're going to get either some fuzzing of your image or some stair-stepping. There is a lot of non-integer digital zooming going on out there today; I would assume that there's plenty of literature on various ways to do it, both clever and dumb -- have you done a literature search? -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●February 18, 20082008-02-18
Michel Rouzic wrote:> Let's say I have a signal (an impulse response) which contains no > frequency components above a certain frequency. Let's say that the > highest frequency component has a period matching to half the width of > the impulse response (which on our graph is the width of the > triangle).Semantics: Impulse response is a property of a system. It is not a signal. Observation: The high frequencies present will be strongly determined by the sharpness of the peak and a bit less by the sharpness of the junctions with the horizontal baseline. Any relation to the width of the impulse is coincidental.> Considering this, if I wanted to obtain a signal identical to the step > response (aka the anti-derivative of the impulse response) of this > signal by simply adding a bunch of offset copies of this impulse > response together, what would be the largest offset I could use > between the copies in order to obtain a signal that matches exactly to > the anti-derivative of the original impulse response? > > > * > * * > * * <--- That's the impulse response we > * * begin with > **************** ************ > > + > * > * * > * * <--- We add offset copies to itself > * * > ******************** ******** > > + > * > * * > * * > * * > ************************ ***** > > + > * > * * > * * > * * > **************************** * > > + > * > * > * > * > ******************************** > > = > > ***************** > * Ultimately we obtain a > signal > * <--- matching to the anti- > derivative > * of the impulse response, > hence a > **************** step response > > But how do we calculate the largest usable offset? Also, can I assume > that any offset smaller than that largest offset is suitable?An infinite number of impulses, spaced as you have shown (i.e., each peaks where its predecessor ends) produces a flat summation, while any other spacing makes bumps. The flat summation can't be the true step response. I leave the reason for you to puzzle over.> Thanks in advance.You're welcome. Thanks for the fun.> PS : Please don't ask what I really need this for (since I don't > actually need it to just turn an impulse response into a step > response), I just couldn't explain what I need this for in a way that > would make sense to anyone but myself.I will restrain myself. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●February 18, 20082008-02-18
Tim Wescott wrote:> Hmm. Try this: "Once the offset is equal to the full extent of the > non-zero impulse response, the result will be constant". > > Better?I'm afraid not, I'm quite confused. It seems to say that the offset should be the extent of the IR, which would make it never overlap its copies..> With a triangular impulse response the step response will be a pair of > parabolas, one starting at 0 and rising up to 1/2 of the total at the > peak of the impulse response (if it's a symmetrical triangle), and one > starting where the first leaves off and rising to the total sum of the > non-zero samples of the impulse response, then a straight line from > there to infinity.Hmm, indeed, I hadn't visualised what it would be like before. It sounds like my assumption that you can obtain the antiderivative of a function by convolving it with a step is completely off the mark, isn't it? I've been thinking about my problem some more and it occurred to me that because the width (or extent if you prefer) of the original filtering function would be proportional to the width of the rectangle (unless I'm once again mistaken), one could derive a fixed formula for it from the original filtering formula. Unfortunately I don't think I can figure out how to do that.> I'm not much of a vidiot, but I suspect that your image isn't getting > _dimmer_ so much as the edges are softening up.By "image", are we both referring to the artifacts due to aliasing present in frequencies above the original Nyquist frequency? Also, is it for some reason a bad idea to substitute zero-padding with nearest neighbour interpolation prior to filtering?> There is a lot of non-integer digital zooming going on out there today; > I would assume that there's plenty of literature on various ways to do > it, both clever and dumb -- have you done a literature search?No I haven't, unfortunately. I must say I spend a hell of a lot more time thinking than reading, also when I want to look for literature on the topic of what I'm researching I often find it fairly difficult to put into words what I'm looking for. I have however spent quite some time searching online for image resizing algorithms (which is quite on- topic) and I hardly could find anything helpful, be it on the topic of spline-based algorithms or linear filtering, so I would greatly appreciate any pointers you might have on relevant literature.
Reply by ●February 18, 20082008-02-18
Jerry Avins wrote:> An infinite number of impulses, spaced as you have shown (i.e., each > peaks where its predecessor ends) produces a flat summation, while any > other spacing makes bumps. The flat summation can't be the true step > response. I leave the reason for you to puzzle over.Well it's not the easiest thing to visualise without the ability to plot it, but I guess I can see that, which makes me think that my original assumption that> You're welcome. Thanks for the fun.No problem. I'm glad someone can derive fun from my misconceptions and wrong assumptions. The elder shall teach the younger, who in return shall amuse the elder.
Reply by ●February 18, 20082008-02-18
Michel Rouzic wrote:> > Tim Wescott wrote: >> Hmm. Try this: "Once the offset is equal to the full extent of the >> non-zero impulse response, the result will be constant". >> >> Better? > > I'm afraid not, I'm quite confused. It seems to say that the offset > should be the extent of the IR, which would make it never overlap its > copies..I think we're talking about different offsets. It seems you mean the amount you move it over each time, while I'm talking about the amount you've moved it over when you call yourself 'done'. You're working in sampled time, right? So if your filter impulse response is x_n, then your convolved output is x_0, (x_0 + x_1), (x_0 + x_1 + x_2), ... sum from k = 0, k = n, x_k.> >> With a triangular impulse response the step response will be a pair of >> parabolas, one starting at 0 and rising up to 1/2 of the total at the >> peak of the impulse response (if it's a symmetrical triangle), and one >> starting where the first leaves off and rising to the total sum of the >> non-zero samples of the impulse response, then a straight line from >> there to infinity. > > Hmm, indeed, I hadn't visualised what it would be like before. It > sounds like my assumption that you can obtain the antiderivative of a > function by convolving it with a step is completely off the mark, > isn't it? >Uh, no, it's exactly right, except if you're working in sampled time (or space, with pixels) it's a summation, not an integral.> I've been thinking about my problem some more and it occurred to me > that because the width (or extent if you prefer) of the original > filtering function would be proportional to the width of the rectangle > (unless I'm once again mistaken), one could derive a fixed formula for > it from the original filtering formula. Unfortunately I don't think I > can figure out how to do that. > >> I'm not much of a vidiot, but I suspect that your image isn't getting >> _dimmer_ so much as the edges are softening up. > > By "image", are we both referring to the artifacts due to aliasing > present in frequencies above the original Nyquist frequency? Also, is > it for some reason a bad idea to substitute zero-padding with nearest > neighbour interpolation prior to filtering?No, I was referring to what you see when you look at your video screen.> >> There is a lot of non-integer digital zooming going on out there today; >> I would assume that there's plenty of literature on various ways to do >> it, both clever and dumb -- have you done a literature search? > > No I haven't, unfortunately. I must say I spend a hell of a lot more > time thinking than reading, also when I want to look for literature on > the topic of what I'm researching I often find it fairly difficult to > put into words what I'm looking for. I have however spent quite some > time searching online for image resizing algorithms (which is quite on- > topic) and I hardly could find anything helpful, be it on the topic of > spline-based algorithms or linear filtering, so I would greatly > appreciate any pointers you might have on relevant literature.Try "electronic zoom". There's certainly an art to finding relevant search terms, and I don't always get it right. I've _seen_ relevant literature, but mostly in the hands of colleagues. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●February 18, 20082008-02-18
i don't know if u have come across this already. Technical report university of cambridge computer lab Image Resampling. Neil Anthony Dodgson August 1992. Regards Bharat Pathak bharat@arithos.com Arithos Designs www.Arithos.com
Reply by ●February 19, 20082008-02-19
Michel Rouzic wrote:> > Tim Wescott wrote: >> Hmm. Try this: "Once the offset is equal to the full extent of the >> non-zero impulse response, the result will be constant". >> >> Better? > > I'm afraid not, I'm quite confused. It seems to say that the offset > should be the extent of the IR, which would make it never overlap its > copies..You want the trailing edge of a copy to be contemporaneous with the leading edge of the one that follows. That way the slopes cancel and the result is a constant sum.>> With a triangular impulse response the step response will be a pair of >> parabolas, one starting at 0 and rising up to 1/2 of the total at the >> peak of the impulse response (if it's a symmetrical triangle), and one >> starting where the first leaves off and rising to the total sum of the >> non-zero samples of the impulse response, then a straight line from >> there to infinity. > > Hmm, indeed, I hadn't visualised what it would be like before. It > sounds like my assumption that you can obtain the antiderivative of a > function by convolving it with a step is completely off the mark, > isn't it?It is. You want to achieve integration by convolution. What led you to assume that's possible? The function you chose only seems to work because the rising and falling slopes are the same.> I've been thinking about my problem some more and it occurred to me > that because the width (or extent if you prefer) of the original > filtering function would be proportional to the width of the rectangle > (unless I'm once again mistaken), one could derive a fixed formula for > it from the original filtering formula. Unfortunately I don't think I > can figure out how to do that.Don't let that distress you. If I understand you correctly, there is no way.>> I'm not much of a vidiot, but I suspect that your image isn't getting >> _dimmer_ so much as the edges are softening up. > > By "image", are we both referring to the artifacts due to aliasing > present in frequencies above the original Nyquist frequency? Also, is > it for some reason a bad idea to substitute zero-padding with nearest > neighbour interpolation prior to filtering? > >> There is a lot of non-integer digital zooming going on out there today; >> I would assume that there's plenty of literature on various ways to do >> it, both clever and dumb -- have you done a literature search? > > No I haven't, unfortunately. I must say I spend a hell of a lot more > time thinking than reading, also when I want to look for literature on > the topic of what I'm researching I often find it fairly difficult to > put into words what I'm looking for. I have however spent quite some > time searching online for image resizing algorithms (which is quite on- > topic) and I hardly could find anything helpful, be it on the topic of > spline-based algorithms or linear filtering, so I would greatly > appreciate any pointers you might have on relevant literature.Gimp (Gnu Image Manipulation Program) is an open-source program that does what you want. Maybe it can help you. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
