filter and downsampling vs averaging

Hello,

What's wrong with achieving decimation by averaging points from the source
signal for each point in the reduced destination signal? For non-integer
reduction this can be achieved without throwing away information from the
source signal by taking into account the fractional parts of source signal
points. This can be done quickly in fixed point on a DSP and seems to give
good results. So why use a filter?
I'm doing decimation for image reduction. Each scanline is reduced to
achieve a horizontal reduction. Is my averaging method ok or should I be
using a polyphase filter method?

Thanks

peterbone wrote:
> Hello,
>
> What's wrong with achieving decimation by averaging points from the source
> signal for each point in the reduced destination signal? For non-integer
> reduction this can be achieved without throwing away information from the
> source signal by taking into account the fractional parts of source signal
> points. This can be done quickly in fixed point on a DSP and seems to give
> good results. So why use a filter?
> I'm doing decimation for image reduction. Each scanline is reduced to
> achieve a horizontal reduction. Is my averaging method ok or should I be
> using a polyphase filter method?
>
> Thanks

You are using a length N boxcar filter. All coefficients have value
1/N. The frequency response has a sinx/x shape. There is nothing wrong
with this method if the frequency response meets your requirements.
Note that it is possible to efficiently compute the boxcar with one MAC
and one subtract per input sample.

Polyphase is not a filter per se, it's a filtering optimization that
factors out computations that do not contribute to the output. If the
boxcar meets your requirements and is implemented efficiently enough
then there is no need to look at polyphase.

John

peterbone wrote:
> Hello,
> 
> What's wrong with achieving decimation by averaging points from the source
> signal for each point in the reduced destination signal? For non-integer
> reduction this can be achieved without throwing away information from the
> source signal by taking into account the fractional parts of source signal
> points. This can be done quickly in fixed point on a DSP and seems to give
> good results. So why use a filter?
> I'm doing decimation for image reduction. Each scanline is reduced to
> achieve a horizontal reduction. Is my averaging method ok or should I be
> using a polyphase filter method?
> 
> Thanks

Averaging /is/ a filter.  It's just not a very good one.

-- 
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com    (603) 226-0404 x536
The real fun of living wisely is that you get to be smug about it. - Hobbes

Averaging is a type of filtering, whenever you do decimation make sure you 
design a filter that minimize aliasing if SNR is important to you.

Tom
"peterbone" <peterbone@hotmail.com> wrote in message 
news:l8adnfQiZ8-1XsTYnZ2dnUVZ_sydnZ2d@giganews.com...
> Hello,
>
> What's wrong with achieving decimation by averaging points from the source
> signal for each point in the reduced destination signal? For non-integer
> reduction this can be achieved without throwing away information from the
> source signal by taking into account the fractional parts of source signal
> points. This can be done quickly in fixed point on a DSP and seems to give
> good results. So why use a filter?
> I'm doing decimation for image reduction. Each scanline is reduced to
> achieve a horizontal reduction. Is my averaging method ok or should I be
> using a polyphase filter method?
>
> Thanks
>
>
> 

>
>peterbone wrote:
>> Hello,
>>
>> What's wrong with achieving decimation by averaging points from the
source
>> signal for each point in the reduced destination signal? For
non-integer
>> reduction this can be achieved without throwing away information from
the
>> source signal by taking into account the fractional parts of source
signal
>> points. This can be done quickly in fixed point on a DSP and seems to
give
>> good results. So why use a filter?
>> I'm doing decimation for image reduction. Each scanline is reduced to
>> achieve a horizontal reduction. Is my averaging method ok or should I
be
>> using a polyphase filter method?
>>
>> Thanks
>
>You are using a length N boxcar filter. All coefficients have value
>1/N. The frequency response has a sinx/x shape. There is nothing wrong
>with this method if the frequency response meets your requirements.
>Note that it is possible to efficiently compute the boxcar with one MAC
>and one subtract per input sample.
>
>Polyphase is not a filter per se, it's a filtering optimization that
>factors out computations that do not contribute to the output. If the
>boxcar meets your requirements and is implemented efficiently enough
>then there is no need to look at polyphase.
>
>John

Thanks. Could you please elaborate on -
"Note that it is possible to efficiently compute the boxcar with one MAC 
and one subtract per input sample."
Could you direct me somewhere so I can see how this algorithm is
implemented on a DSP?

peterbone wrote:
> 
> Hello,
> 
> What's wrong with achieving decimation by averaging points from the source
> signal for each point in the reduced destination signal? For non-integer
> reduction this can be achieved without throwing away information from the
> source signal by taking into account the fractional parts of source signal
> points. This can be done quickly in fixed point on a DSP and seems to give
> good results. So why use a filter?

You already are using a filter. 


> I'm doing decimation for image reduction. Each scanline is reduced to
> achieve a horizontal reduction. Is my averaging method ok or should I be
> using a polyphase filter method?

From what you described you already are using a poly-phase
implementation for non-integer reduction. 

	You might be able to implement a  better scheme depending on how you
define "better". If speed is what is most important, you may already be
implementing the best method.

-jim

> 
> Thanks

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

>
> Thanks. Could you please elaborate on -
> "Note that it is possible to efficiently compute the boxcar with one MAC
> and one subtract per input sample."
> Could you direct me somewhere so I can see how this algorithm is
> implemented on a DSP?

Keep of circular buffer of the past N inputs. Keep a running sum of the
inputs, but subtract the oldest input from the sum as it falls out of
the circular buffer. On a DSP you can use circular address modes and
parallel load/compute/store to strip this down to just a few
instructions per input sample.

John

>
>>
>> Thanks. Could you please elaborate on -
>> "Note that it is possible to efficiently compute the boxcar with one
MAC
>> and one subtract per input sample."
>> Could you direct me somewhere so I can see how this algorithm is
>> implemented on a DSP?
>
>Keep of circular buffer of the past N inputs. Keep a running sum of the
>inputs, but subtract the oldest input from the sum as it falls out of
>the circular buffer. On a DSP you can use circular address modes and
>parallel load/compute/store to strip this down to just a few
>instructions per input sample.
>
>John
>

Ok, thanks, but I'm still confused about how this works for non integer
reduction ratios. It doesn't sound like it's taking into account the
fractional parts of pixels. Also, how do you know when to assign your
output sample. For non integer ratios that requires some high precision
integer arithmetic to calculate when the next output pixel has been
reached. Some code would be great.

Here's the MATLAB code I wrote before writing the c version for the DSP.
In the DSP version I'm using scaled up integers instead of floats. The if
statement is what really slows it down because it prevents the compiler
from pipelining the loop.

function D = reduceLine(S, Dlen)

D = zeros(1, Dlen);
Slen = length(S); % source line length
ratio = Dlen / Slen;
ratioInv = Slen / Dlen;
ndp = Slen / Dlen; % next destination pixel
ndpfrac = ndp - floor(ndp);
sum = 0;
i = 1; % destination pixel index

for x = 1 : Slen
    if x-1 < floor(ndp)  
        sum = sum + S(x);
    else % source pixel coincides with a desination pixel
        % accumulate fractional part of source pixel
        sum = sum + ndpfrac*S(x);
        % assign destination pixel
        D(i) = floor(sum * ratio);
        i = i + 1;
        % accumulate remaining fractional part of source pixel
        sum = (1-ndpfrac)*S(x);
        % calculate next destination pixel position
        ndp = i * ratioInv;
        ndpfrac = ndp - floor(ndp);
    end    
end    
        
if i = Dlen
    D(i) = floor(sum * ratio);
end


Thanks

Peter

peterbone wrote:

> Hello,
>
> What's wrong with achieving decimation by averaging points from the source
> signal for each point in the reduced destination signal? For non-integer
> reduction this can be achieved without throwing away information from the
> source signal by taking into account the fractional parts of source signal
> points. This can be done quickly in fixed point on a DSP and seems to give
> good results. So why use a filter?

You might get something out of this discussion:

http://groups.google.com/group/comp.dsp/browse_frm/thread/e4175ce9ff70f74e/b8161db5b95bfed8?#b8161db5b95bfed8

Regards,
Andor

peterbone wrote:
> 
> >
> >>
> >> Thanks. Could you please elaborate on -
> >> "Note that it is possible to efficiently compute the boxcar with one
> MAC
> >> and one subtract per input sample."
> >> Could you direct me somewhere so I can see how this algorithm is
> >> implemented on a DSP?
> >
> >Keep of circular buffer of the past N inputs. Keep a running sum of the
> >inputs, but subtract the oldest input from the sum as it falls out of
> >the circular buffer. On a DSP you can use circular address modes and
> >parallel load/compute/store to strip this down to just a few
> >instructions per input sample.
> >
> >John
> >
> 
> Ok, thanks, but I'm still confused about how this works for non integer
> reduction ratios. 

It doesn't. It doesn't help any for integer reduction case either since
it sounds like you are simply summing the old pixels that lie underneath
each new pixel to create the reduced form. Since each successive new
output does not share any input values with its neighbors there is no
gain in doing anything other than just summing the inputs.

-jim


>It doesn't sound like it's taking into account the
> fractional parts of pixels. Also, how do you know when to assign your
> output sample. For non integer ratios that requires some high precision
> integer arithmetic to calculate when the next output pixel has been
> reached. Some code would be great.
> 
> Here's the MATLAB code I wrote before writing the c version for the DSP.
> In the DSP version I'm using scaled up integers instead of floats. The if
> statement is what really slows it down because it prevents the compiler
> from pipelining the loop.
> 
> function D = reduceLine(S, Dlen)
> 
> D = zeros(1, Dlen);
> Slen = length(S); % source line length
> ratio = Dlen / Slen;
> ratioInv = Slen / Dlen;
> ndp = Slen / Dlen; % next destination pixel
> ndpfrac = ndp - floor(ndp);
> sum = 0;
> i = 1; % destination pixel index
> 
> for x = 1 : Slen
>     if x-1 < floor(ndp)
>         sum = sum + S(x);
>     else % source pixel coincides with a desination pixel
>         % accumulate fractional part of source pixel
>         sum = sum + ndpfrac*S(x);
>         % assign destination pixel
>         D(i) = floor(sum * ratio);
>         i = i + 1;
>         % accumulate remaining fractional part of source pixel
>         sum = (1-ndpfrac)*S(x);
>         % calculate next destination pixel position
>         ndp = i * ratioInv;
>         ndpfrac = ndp - floor(ndp);
>     end
> end
> 
> if i = Dlen
>     D(i) = floor(sum * ratio);
> end
> 
> Thanks
> 
> Peter

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