Dear all,<div><br></div><div>I would like to add that DCT transforms can be used in certain cases to perform convolution <b>even faster</b> than FFT-based convolution. Thus having good DCT code is very useful.</div><div><br>
</div><div>DCT transforms can be used to perform fast convolutions with symmetric boundary handling under the condition that the filter is symmetric, e.g., the filter can be a Gaussian or a Laplacian.</div><div><br></div>
<div>With the FFT, convolution with symmetric boundary handling can be achieved by first reflecting the signal to twice its length, </div><div><br></div><div>f1,f2,...,fN <span style="font-family:verdana,helvetica,arial,sans-serif;font-size:12px;background-color:rgb(255,255,255)">→</span> f1,f2,...,fN,fN,...,f2,f1</div>
<div><br></div><div>In this way, the periodization implied by the FFT produces half-sample symmetric boundaries. A length-2N real-to-complex FFT transform can be applied to obtain the transform as N+1 complex values. Then do (complex) multiplication with the transformed filter, perform the complex-to-real inverse FFT to obtain a length-2N result, and take the first N values to obtain the convolution.</div>
<div><br></div><div>With the DCT-II transform, the symmetric boundaries are already implied by the transform. To convolve a length-N signal, compute its DCT-II transform to obtain N real values. Then multiply the transform values with the DCT-I (not DCT-II) transform of the filter. Perform the inverse DCT-II transform and you are done. The key point is that we never needed arrays longer than N floats to do it, so the convolution is more memory efficient. </div>
<div><br></div><div><br></div><div>1D symmetric convolution of length N</div><div>DCT-based: requires N floats </div><div>FFT-based: requires 2N+2 floats (N+1 complex values)</div><div><br></div><div>The advantages are even better in higher dimensions:</div>
<div><br></div><div>2D symmetric convolution of size N x N</div><div><div>DCT-based: requires N^2 floats </div><div>FFT-based: requires 4N^2 + 4N floats (2N x (N + 1) complex array)</div></div><div><br></div><div>3D symmetric convolution of size N x N x N</div>
<div><div>DCT-based: requires N^3 floats </div><div>FFT-based: requires 8N^3 + 4N^2 floats (2N x 2N x (N + 1) complex array)</div></div><div><br></div><div><br></div><div>For more details, I describe DCT-based convolution in the section "Convolution with Boundary Handling" of</div>
<div><br></div><div><a href="http://www.ipol.im/pub/algo/g_tv_deconvolution/" target="_blank">http://www.ipol.im/pub/algo/g_tv_deconvolution/</a></div><div><br></div><div>Also see the paper by Martucci<span style="background-color:rgb(250,250,250);font-family:Arial,Helvetica,sans-serif;font-size:14px;text-align:justify">, </span><a href="http://dx.doi.org/10.1109/78.295213" target="_blank" style="background-color:rgb(250,250,250);color:rgb(80,32,95);text-decoration:none;font-family:Arial,Helvetica,sans-serif;font-size:14px;text-align:justify">“Symmetric convolution and the discrete sine and cosine transforms.”</a></div>
<div><br></div><div>Best,</div><div>Pascal</div><div><br></div><br><div class="gmail_quote">On Tue, Feb 28, 2012 at 11:04, Pascal Monasse <span dir="ltr"><<a href="mailto:monasse@imagine.enpc.fr">monasse@imagine.enpc.fr</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Miguel,<br>
<div class="im"><br>
> It even analyzes the numerical expressions and tries to compute it the<br>
> shorter and faster way.<br>
> For example, if y = f(y) + 2*f(y) + 3*f(y), it doesn't call f(y) three<br>
> times.<br>
<br>
</div>I doubt that the compiler would dare such an aggressive optimization. f may<br>
have side effects that the compiler is not able to analyze, therefore it may<br>
think it is safer to call f(y) three times...<br>
<br>
Best,<br>
Pascal<br>
<div class="HOEnZb"><div class="h5"><br>
_______________________________________________<br>
discuss mailing list<br>
<a href="mailto:discuss@list.ipol.im">discuss@list.ipol.im</a><br>
<a href="http://tools.ipol.im/mailman/listinfo/discuss" target="_blank">http://tools.ipol.im/mailman/listinfo/discuss</a><br>
</div></div></blockquote></div><br>