Boxlets: A Fast Convolution Algorithm for Signal Processing and Neural Networks

Patrice Y. Simard, Léon Bottou, Patrick Haffner, Yann LeCunNeurIPS 1998 · OpenReview

TL;DR

The "Boxlets" algorithm accelerates convolutions by approximating images as piecewise polynomials (rectangular "boxlets"), differentiating them into sparse impulse functions, and convolving those instead. By trading a small amount of mathematical precision for a massive reduction in operations, the authors achieve speedups of up to 13x for feature extraction and neural networks.

What Problem Does This Paper Address?

Convolution is the fundamental operation of signal processing and computer vision, but it is computationally expensive. For an image of size $N$ and a filter of size $M$, a standard convolution requires $O(N \cdot M)$ operations. While the Fast Fourier Transform (FFT) can reduce this to $O(N \log N)$, it is often inefficient for the small kernels (e.g., $5 \times 5$) typically used in feature extraction and convolutional neural networks (CNNs).

The authors observe that in many real-world applications, like optical character recognition (OCR) or pattern recognition, the input signal is already noisy or distorted. Therefore, perfect mathematical precision is rarely necessary. The challenge is to find a way to simplify the image representation so that convolution becomes trivial, without losing the essential features needed for recognition.

Methods

The core of the "Boxlet" algorithm relies on a clever calculus identity: the convolution of two signals can be computed by differentiating them, convolving their derivatives, and then integrating the result back.

1D illustration of the Boxlet algorithm: quantization, differentiation, sparse convolution, and integration.

The process breaks down into four main steps:

  1. Boxletization (Quantization): The image is partitioned into rectangular regions called "boxlets." Inside each boxlet, the signal is approximated by a low-degree polynomial. Usually, this is degree 0, meaning the boxlet has a constant color or value.
  2. Differentiation: When you differentiate a piecewise constant function, the "flat" parts become zero, and the boundaries become impulse functions (Dirac deltas).
  3. Sparse Convolution: Convolving two sets of impulse functions is incredibly fast. It essentially involves a few additions and multiplications only at the specific coordinates where the impulses exist.
  4. Integration: To recover the final result, the output of the sparse convolution is integrated (summed up) twice.

The authors propose two ways to create these boxlets: a Greedy Algorithm that finds the largest possible rectangle under an error threshold, and Recursive Splitting, a quadtree-like approach that recursively splits the image. Recursive splitting is preferred because it aligns the boundaries of the boxlets, allowing many impulse functions to "cancel out" or combine, further increasing computational speed.

Key Insights and Ideas

Examples of image boxletization showing the visual effect of different quantization thresholds.
  • The Precision-Speed Trade-off: By adjusting the error threshold ($K$) for the boxlet approximation, users can choose exactly how much accuracy they are willing to sacrifice for speed.
  • Boundary Alignment Matters: The recursive splitting method is superior to the greedy method not because it approximates the image better, but because it creates structured boundaries. When boxlets line up, their derivatives often merge, leading to a much sparser representation.
  • 2D Run-Length Encoding: For binary images, the Boxlet algorithm essentially acts as a highly efficient 2D version of run-length encoding. It turns the "area" of a shape into a "contour" of impulses, making the computation proportional to the perimeter rather than the area.
  • Amortized Costs: While "boxletizing" an image takes time upfront, that cost is shared (amortized) if you are convolving the same image with many different filters—which is exactly what happens in the layers of a CNN.

Key Results

The authors evaluated the algorithm using sample grayscale images and synthetic kernels of varying sizes ($5 \times 5$ up to $20 \times 20$) to measure speedup factors (standard convolution time divided by Boxlet convolution time).

  • General Images: Speedups ranged from 1.5x to 13.8x.
  • Kernel Size: The larger the convolution kernel, the greater the speedup. For a $20 \times 20$ kernel with a high error threshold, the algorithm was nearly 14 times faster than the standard approach.
  • Binary Images: For simple binary shapes, the speedup can reach an order of magnitude (10x+) with zero loss in accuracy, as the impulse representation is exact for flat binary regions.

Limitations and Future Work

  • Quantization Noise: The main drawback is the introduction of approximation error. While negligible for many pattern recognition tasks, it might be problematic for high-precision scientific imaging.
  • Implementation Overhead: The algorithm requires specialized data structures (sorted lists of impulses) and integration steps, adding complexity compared to a simple nested loop.
  • Neural Network Integration: While the authors suggest this is directly applicable to the forward pass of CNNs, the paper does not provide results for a full-scale trained network or discuss how to handle the backward pass (training).
  • Hardware Acceleration: Written before the era of modern GPUs, standard convolutions today are highly optimized in hardware. It remains an open question how well the sparse, branch-heavy nature of Boxlets would map to modern parallel architectures.

Summary updated

Abstract

Signal processing and pattern recognition algorithms make exten(cid:173) sive 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 polynomi(cid:173) als, 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(cid:173) ered by integrating the result of the convolution. This method yields substantial speed up in feature extraction and is applicable to convolutional neural networks.
BibTeX
@inproceedings{simard1998boxlets,
  author = {Patrice Y. Simard and Léon Bottou and Patrick Haffner and Yann LeCun},
  title = {{Boxlets: A Fast Convolution Algorithm for Signal Processing and Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
  url = {https://openreview.net/forum?id=HkVuEPbdZB},
}
Figure