## Boxlets: a Fast Convolution Algorithm for Neural Networks and Signal Processing

*Abstract*:
Signal processing and pattern recognition algorithms make extensive use of convolution.
In many cases, computational accuracy is
not as important as computational speed. In feature extraction,
for instance, the features of interest in a signal are usually quite
distorted. This form of noise justifies some level of quantization in
order to achieve faster feature extraction. Our approach consists
of approximating regions of the signal with low degree polynomials,
and then differentiating the resulting signals in order to obtain
impulse functions (or derivatives of impulse functions). With this
representation, convolution becomes extremely simple and can be
implemented quite effectively. The true convolution can be recov-
ered by integrating the result of the convolution. This method
yields substantial speed up in feature extraction and is applicable
to convolutional neural networks.

**Boxlets: a fast convolution algorithm for neural networks and signal processing**,

*Advances in Neural Information Processing Systems*, 11, MIT Press, Denver, 1999.

@incollection{simard-99, author = {Simard, Patrice and Bottou , L\'{e}on and Haffner, Patrick and {LeCun}, Yann}, title = {Boxlets: a fast convolution algorithm for neural networks and signal processing}, booktitle = {Advances in Neural Information Processing Systems}, address = {Denver}, volume = {11}, publisher = {MIT Press}, year = {1999}, url = {http://leon.bottou.org/papers/simard-99}, }

### Notes

Maybe the most famous use of boxlets is the computation of the features of the Viola-Jones object recognition system [1,2]. The *integral image* representation is a boxlet of order zero. Such particular cases were also described in [3] (see the paper for details.)

**[1]**Paul Viola, Michael Jones: Robust Real-time Object Detection,*Second International Workshop on Statistical and Computational Theories of Vision - Modeling, Learning, Computing, and Sampling*, Vancouver, July 2001.**[2]**Paul Viola, Michael Jones: Robust Real-time Object Detection,*International Journal of Computer Vision*, 57(2):137-154, 2004**[3]**Paul S. Heckberg: Filtering by repeated integration.*ACM SlGGRAPH conference on Computer graphics*, 20:315-321, Dallas, 1986