Abstract
This paper addresses the computational bottleneck of applying Deep Neural Networks (DNNs) to large images for tasks such as segmentation and object detection. We introduce a dynamic programming technique called "fragmentation" that allows Max-Pooling Convolutional Neural Networks to scan images significantly faster than traditional sliding-window approaches. By eliminating redundant computations, the proposed method achieves theoretical speedups of up to 780x and a practical 32x speedup in a MATLAB implementation compared to a heavily optimized GPU-based sliding-window implementation.
Introduction
Deep Neural Networks have become the standard for image classification, typically processing small, isolated patches. However, applying these models to full-scale images for pixel-wise labeling or object detection is computationally expensive. The standard "sliding window" approach—cropping a patch, running the network, and moving the window—is inherently redundant because overlapping patches share the majority of their pixels. While convolutional layers can be scaled to whole images, max-pooling layers traditionally break this efficiency by downsampling and discarding spatial offsets.
Methodology: The Fragmentation Approach
The authors propose an optimized forward-propagation method that treats the entire image as a single input, rather than a collection of independent patches.
Extended Maps and Fragmentation
Instead of processing small patches, the network operates on "extended maps" covering the full input image. The core innovation occurs at the max-pooling layers. When the algorithm encounters a max-pooling layer with a kernel size of $k \times k$, it does not simply produce one downsampled map. Instead, it generates $k^2$ separate fragments.
Offset Tracking
Each fragment corresponds to one of the possible spatial offsets (or "phases") of the pooling window. For a 2x2 pool, four fragments are produced, representing the offsets (0,0), (1,0), (0,1), and (1,1). Subsequent layers then process these fragments independently. Because each fragment is smaller than the original map, the total number of pixels processed remains constant, but the redundant re-calculation of convolutions is entirely eliminated. This dynamic programming approach ensures that each convolution for each pixel is calculated exactly once.
Key Results
The efficiency gains of the fragmentation method are dramatic, particularly in reducing the number of floating-point operations (FLOPS).
Theoretical Speedup
For an 11-layer network applied to a 512x512 image, the traditional patch-based approach requires approximately 63,636 GFLOPS. In contrast, the image-based fragmentation approach requires only 81.6 GFLOPS—a theoretical improvement of nearly 780x. The most significant gains are seen in the early layers, where the speedup can exceed 7000x.
Practical Performance
In empirical tests, the authors compared a basic MATLAB implementation of their method against a highly optimized CUDA/GPU implementation of the sliding-window approach. Despite the overhead of the MATLAB environment, the fragmentation method was 32.8 times faster than the optimized GPU code. This suggests that a dedicated GPU implementation of fragmentation would yield even greater real-world performance.
Conclusion and Future Work
The fragmentation method provides a mathematically exact way to accelerate dense image scanning without the approximations used in other speedup techniques. While it introduces complexity in managing an increasing number of fragments in deep architectures, the reduction in redundant computation is transformative for high-resolution tasks. Future work includes optimizing fragment management and developing native GPU implementations to further exploit these computational savings.
Summary updated