Fast Sliding Window Classification with Convolutional Neural Networks

Henry G. R. Gouk, Anthony M. BlakeIVCNZ 2014 · DOI

TL;DR

This paper tackles the computational bottleneck of using Convolutional Neural Networks (CNNs) for real-time object detection via sliding window classification. By combining frequency domain convolution techniques with architectural optimizations, the authors achieve significant speedups without sacrificing accuracy, making CNNs more practical for time-sensitive applications.

What Problem Does This Paper Address?

Convolutional Neural Networks (CNNs) have become the gold standard for image classification, but their high computational complexity makes them slow for tasks like object detection that require evaluating many overlapping sub-windows within a large image. Traditional sliding window approaches involve running the CNN on each sub-window independently, which is computationally prohibitive for real-time applications. While frequency domain methods can speed up convolutions, their application to CNNs has primarily focused on training, not inference. This paper aims to bridge this gap by optimizing the entire sliding window inference process for CNNs.

Methods

The core of this paper lies in combining two key advancements:

  • Frequency Domain Convolution (from [6]): This method leverages the convolution theorem, which states that convolution in the spatial domain is equivalent to point-wise multiplication in the frequency domain. By transforming images and kernels into the frequency domain, convolutions can be computed much faster, especially for larger kernels. The authors adopt a strategy that minimizes the number of inverse Fourier Transforms (FFTs) required.
  • Spatial Domain Sliding Window Optimization (from [8]): This approach recognizes that feature maps computed for adjacent sub-windows in a CNN contain significant overlap. Instead of processing each sub-window independently, it proposes processing the entire input image at once through the convolutional layers. This avoids redundant computations.

The authors combine these by applying the frequency domain convolution method to the entire input image, as proposed in [8]. They also introduce architectural optimizations:

  • Optimizing Fully Connected Layers: Fully connected layers are often a bottleneck. The authors propose a heuristic: only convert convolutional layers with sufficiently large kernels to use the frequency domain method. Fully connected layers (or convolutional layers with 1x1 kernels) are processed in the spatial domain. Further optimization involves unrolling inner loops for these layers to exploit the single-element kernel.
  • Memory Reduction Strategy: To address the memory explosion caused by zero-padding required for linear convolution in the frequency domain, the authors suggest coarsely dividing the large input image into smaller overlapping sub-images. This reduces the memory footprint at the cost of some re-introduced redundancy.

Datasets

The paper does not explicitly mention specific named datasets for training or evaluation. Instead, it focuses on evaluating the performance of its algorithms on synthetically generated images of varying resolutions and using different network architectures (shallow and deep).

Key Insights and Ideas

  • Synergy of Frequency and Spatial Optimizations: The paper demonstrates that combining frequency domain convolutions with spatial domain sliding window strategies can yield substantial speedups for CNN inference.
  • The FFT Implementation Matters: The performance of the frequency domain approach is heavily influenced by the quality and efficiency of the FFT implementation. Inconsistent performance observed with varying kernel sizes is attributed to the FFT's sensitivity to non-power-of-two input sizes.
  • Trade-off Between Memory and Speed: The memory reduction strategy (dividing images) is crucial for handling large inputs but comes at the cost of some performance degradation, highlighting a key trade-off in practical deployment.
  • Targeted Optimization for Fully Connected Layers: Simply applying frequency domain methods to all layers, including fully connected ones, is inefficient. Optimizing these layers separately based on their structure is key to maximizing speedup.

Key Results

The paper presents empirical evidence of significant speedups:

  • The proposed optimized frequency domain sliding window method (OSWFP-F) is generally the fastest across various scenarios.
  • The fast spatial domain sliding window method (SWFP-S) offers a speedup of over an order of magnitude compared to naive sub-window processing.
  • The speedup achieved by the frequency domain methods is largely independent of kernel size but is significantly impacted by input image size and the efficiency of the FFT implementation.
  • The memory reduction technique shows a performance impact that is not strongly correlated with the number of sub-images, but it is intended for memory-constrained environments.

Limitations and Future Work

  • Backpropagation: The paper notes that while the fast sliding window algorithm can be extended to backpropagation, its practical utility for object detection is limited due to potential issues with class distribution and catastrophic forgetting. Future work could explore overcoming these limitations.
  • Real-time Constraints for Complex Models: The authors aim to demonstrate that complex CNN models can be applied to tasks with real-time constraints in the future.
  • GPU Implementation: A GPU version of the library is under development, which is expected to further enhance performance.
  • FFT Implementation Dependency: The performance is sensitive to the FFT library used, suggesting that further research into optimizing FFTs for specific hardware or scenarios could be beneficial.

Summary updated

BibTeX
@inproceedings{gouk2014fast,
  author = {Henry G. R. Gouk and Anthony M. Blake},
  title = {{Fast Sliding Window Classification with Convolutional Neural Networks}},
  booktitle = {IVCNZ},
  year = {2014},
  doi = {10.1145/2683405.2683429},
}
Figure