Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples

Liming Lou     Paul Nguyen     Jason Lawrence     Connelly Barnes

ACM Transactions on Graphics (presented at ACM SIGGRAPH 2016)



Optimizing an image pipeline using image perforation. An anisotropic radial artistic blur is applied to (a, inset at top left) an input image to produce (a) the reference output. (b) An optimized version of this pipeline is automatically found by image perforation (the bottom row shows zoom regions). Image perforation works by transforming loops over image arrays to skip certain samples that are subsequently reconstructed from the available samples. This achieves faster running times at the cost of some loss in image fidelity. In this case, a speedup of 6x is achieved for a negligible amount of error. Photo credit: Cheon Fong Liew.

Abstract

Image pipelines arise frequently in modern computational photography systems and consist of multiple processing stages where each stage produces an intermediate image that serves as input to a future stage. Inspired by recent work on loop perforation [Sidiroglou-Douskos et al. 2011], this paper introduces image perforation, a new optimization technique that allows automatically exploring the space of performance-accuracy trade-offs within an image pipeline. Image perforation works by transforming loops over the image at each pipeline stage into coarser loops that effectively “skip” certain samples. These missing samples are reconstructed for later stages using a number of different interpolation strategies that are relatively inexpensive to perform compared to the original cost of computing the sample. We describe a genetic algorithm for automatically exploring the resulting combinatoric search space of which loops to perforate, in what manner, by how much, and using what reconstruction method. We also present a prototype language that implements image perforation along with several other domain-specific optimizations and show results for a number of different image pipelines and inputs. For these cases, image perforation achieves speedups of 2x-10x with acceptable loss in visual quality and significantly outperforms loop perforation.

Links Photo credits

The photos in the paper are licensed under Creative Commons licenses. Links to the original photographs on Flickr (which includes each full license text) are included as hyperlinks in the paper. The testing and training images also include links to the associated photos and licenses.