Forgot to cc the perldl list... -------- Original Message -------- Subject: conv1d algorithm Date: Thu, 7 Jan 2010 18:43:09 -0500 (EST) From: Chris Marshall <[email protected]> To: [email protected]
Cliff Sobchuk wrote: > > Hi Gents. I don't understand why the output > sequence has less zero padding than the input. > > Input => [0 0 0 0 0 0 1 0 0 0 0 0] > Filter => [ 2 0 -1] > > Is this not the correct output? > :: Input convolved with Filter => [0 0 0 0 0 0 2 0 -1 0 0 0 0 0] > :: That is what I get out of Octave as well as when I do a sample > :: by sample manual convolution. See 'help conv1d' in the PDL-2.4.6 perldl shell for what is being calculated. If it is not clear, please send corrections/suggestions. > The output that is shown has less zero padding > at both the start of the result as well as > the tail of the result. Yes. I took a look at Octave's convolutions and they appear to all be polynomial arithmetic based. For that you *would* have output data with more elements than the input array. [N.B. Wikipedia has a discussion of the conv1d calculation on their Convolution page] > Does PDL constrain the output to the original > dimension of the largest array? I believe the current PDL convolution routines implement a fixed size array via boundary conditions. > I expect that in image processing this may not > be a big deal (maybe it is, I am not qualified > to answer), Correct/consistent handling of boundary conditions is important in *both* signal and image processing. > in control systems and DSP it is an important > distinction as the signal does continue and > artefacts (possibly instability) would occur. Periodic BCs are useful for computations in the Fourier domain. Reflecting can be useful for specific symmetries at the boundaries... > So I ran a couple of tests across all three > forms that are listed and compared them to the > output from Octave. I changed the input because > I had a feeling it would give me different > results for each of the functions. > > Input (x)=> [0 0 0 0 0 1 0 0 0 0 1] > Filter (h)=> [ 2 0 -1] > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > Octave : > x= [0,0,0,0,0,1,0,0,0,0,0] > h=[2,0,-1] > y=conv(x,h) > output (y) => 0.00 0.00 0.00 0.00 0.00 2.00 0.00 -1.00 0.00 0.00 > 2.00 0.00 -1.00 > > z=conv(fliplr(x),h) > :: reversing the time sequence - something that > DSP engineers do often, and I thought maybe > that was what conv1d was doing, wrong. > > output (z) => 2.00 0.00 -1.00 0.00 0.00 2.00 0.00 -1.00 0.00 0.00 > 0.00 0.00 0.00 > > > PDL : > $a=zeroes(11);$a(5).=1;$a(10).=1;$b=pdl(2,0,-1) > p conv1d $a,$b > output (y) => [2 0 0 0 -1 0 2 0 0 -1 0] > > use PDL::Image2D > p conv2d $a,$b > output (y) => [ [-1 0 0 0 2 0 -1 0 0 2 0] ] > > use PDL::ImageND > p convolveND $a,$b > output (y) => [0 0 0 0 2 0 -1 0 0 2 0] > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > Hence, I don't think that any of the PDL > functions provide the true convolution. There are no PDL routines that implement the expanding boundary conditions for convolve. You can get the expand boundary handling by pre-padding your data with the correct numnber of zeros around the edges. > convolveND is the closest, but still fails in > that the leading zeroes is incorrect and that > the entire input is not processed lengthening > the output. > > Comments? The only difference between the PDL-2.4.6 conv1d routine and previous PDL versions is that it is now consistent with convolveND and conv2D in actually calculating the convolution rather than the correlation of the two arguments. Cheers, Chris _______________________________________________ Perldl mailing list [email protected] http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
