Source-linked AI summary
Fast Image Scanning with Deep Max-Pooling Convolutional Neural Networks
Alessandro Giusti, Dan C. Cireşan, Jonathan Masci, Luca M. Gambardella, Jürgen Schmidhuber
TL;DR
Sliding-window scanning with deep networks is computationally expensive because overlapping patches repeat work, and max-pooling prevents the simplest whole-image optimization. The paper uses dynamic-programming-style fragment propagation to preserve all patch outputs across arbitrary mixtures of convolutional and max-pooling layers, achieving nearly three orders of magnitude theoretical speedup and a 32-fold practical speedup over an optimized GPU patch implementation.
Problem
Naive sliding-window scanning for image detection and segmentation repeats computations across overlapping patches, while max-pooling defeats straightforward whole-image convolution.
Method
The approach fragments extended maps after max-pooling so independent fragments collectively retain information for all image patches across arbitrary layer orderings.
Results
Nearly three orders of magnitude theoretical speedup is reported for huge networks, while MATLAB achieves a 32-fold speedup over a highly optimized patch-based GPU implementation.
Takeaways & Limitations
The method enables fast forward propagation for sliding-window object detection and image segmentation despite interleaved max-pooling layers.
Takeaways & Limitations
The optimization addresses convolutional and max-pooling layers through layer L; fully-connected forward propagation is not discussed because it is treated as non-redundant.
Abstract
from arXiv · showhide
Deep Neural Networks now excel at image classification, detection and segmentation. When used to scan images by means of a sliding window, however, their high computational complexity can bring even the most powerful hardware to its knees. We show how dynamic programming can speedup the process by orders of magnitude, even when max-pooling layers are present.
IDSIA / USI-SUPSI
The paper is associated with IDSIA, a joint institute of USI and SUPSI founded by the Dalle Molle Foundation in 1988.
- IDSIA is a joint institute of the University of Lugano (USI) and the University of Applied Sciences of Southern Switzerland (SUPSI).
- The institute was founded in 1988 by the Dalle Molle Foundation, which promoted quality of life.
- The paper is titled “Fast Image Scanning with Deep Max-Pooling Convolutional Neural Networks.”
1 Introduction
Sliding-window application of deep networks to image detection and segmentation is prohibitively expensive because overlapping patches cause redundant computation. The paper introduces a general fragmentation approach that preserves all patch information despite max-pooling layers.
- Applying a network to every image patch makes naive segmentation and detection prohibitively expensive.Overlapping patches repeatedly recompute the same convolutions.
- Computing convolutions over the whole image removes redundancy when convolutional layers are used without max-pooling.The resulting extended maps contain outputs for each patch in the image.
- Max-pooling breaks this straightforward optimization because pooled maps retain only patches aligned with particular coordinates.A 2 × 2 operation represents patches whose upper-left corners lie at even coordinates, and later pooling layers worsen the loss.
- The proposed method fragments extended maps after each max-pooling layer so fragments are independent while their union covers all input patches.It handles arbitrary architectures that mix convolutional and max-pooling layers without redundant computation.
2 Method
The method replaces redundant patch-by-patch propagation with whole-image extended maps and fragments, preserving outputs for every contained input window through convolutional and max-pooling layers.
- Network scope: A network consists of input, convolutional, max-pooling, and fully-connected layers, but the optimization targets propagation through convolutional and max-pooling layers up to layer L.Fully-connected forward propagation is not discussed because the straightforward approach does not suffer from redundant computation.
- Fragment representation: Each layer’s image-level output is represented by fragments containing extended maps, with maps in one fragment sharing a size while different fragments may differ.The input image begins as a single fragment, and later layers transform the fragment sets while retaining their associated extended maps.
- Convolutional layers: Convolutional layers preserve the number of fragments and apply ordinary convolutions to large extended maps instead of separately processing small patch maps.Within each fragment, convolution produces extended maps whose dimensions shrink according to the kernel size.
- Max-pooling layers: Max-pooling layers split every input fragment into k^2 output fragments, one for each two-dimensional offset of the square pooling kernel.For k = 2, the offsets are (0, 0), (1, 0), (0, 1), and (1, 1); each output fragment applies pooling starting at its assigned offset.
- Max-pooling layers: Integer division determines the dimensions of pooled extended maps, while max-pooling ignores residual input regions not covered by complete pooling windows.This offset-specific fragmentation addresses the loss of patch coverage caused by directly pooling a single extended map.
3 Discussion and Results
The image-based approach uses fragmenting to preserve all sliding-window patch results despite max-pooling, substantially reducing convolutional computation and runtime.
- Theoretical speedup: Max-pooling layers multiply fragment counts by the square of their kernel size, while convolutional layers preserve the number of fragments.The final fragment count is the product of squared max-pooling kernel sizes; the example network produces 256 output fragments.
- Theoretical speedup: Each fragment contains an independent subset of patches, while all fragments collectively represent every patch in the input image.This preserves the outputs needed for whole-image sliding-window evaluation.
- Theoretical speedup: The FLOPS formulas compare patch-based and image-based convolutional computation using image size, map counts, kernel sizes, and fragment dimensions.The patch-based formula includes a factor of 2 for one addition and multiplication per dot-product component; the image-based formulation accounts for fragment sizes.
- Theoretical speedup: 779.8 times more FLOPS are required by the patch-based approach than by the image-based approach for the network evaluated on a 512×512 image.The comparison covers convolutional layers in the network listed in Table 1.
- Experimental speedup: 32-fold speedup is achieved by matlab-image over the optimized GPU-patch implementation, while GPU-patch is 50 times faster than matlab-patch.The image-based implementation achieves this despite using MATLAB without low-level optimization, whereas GPU-patch uses CUDA on a GTX-580.
4 Conclusions
The method accelerates sliding-window forward propagation in deep networks with interleaved max-pooling, avoiding unnecessary computation for object detection and image segmentation. For large networks, it is theoretically almost three orders of magnitude faster, while a simple MATLAB implementation achieves a 32-fold practical speedup over an optimized GPU baseline.
- 4 Conclusions: The approach speeds up forward-propagating deep neural networks on sliding windows while handling max-pooling interleaved with convolutional layers.It avoids unnecessary computations in settings relevant to object detection and image segmentation.
- 4 Conclusions: Almost three orders of magnitude faster in theory is reported for huge networks compared with straightforward patch-based forward propagation.The cited example includes networks winning the ISBI Electron Microscopy Segmentation Challenge.
- 4 Conclusions: 32-fold practical speedup is achieved by a simple MATLAB implementation over a highly optimized patch-based GPU implementation.Figure 2 concerns electron microscopy segmentation data, for which the exact approach gives identical patch-based and image-based results.