research-article

Public Access

Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples

Authors:

Jason Lawrence,

Connelly BarnesAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 35, Issue 5

Article No.: 153, Pages 1 - 14

https://doi.org/10.1145/2904903

Published: 02 September 2016 Publication History

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 article introduces image perforation, a new optimization technique that allows us to automatically explore the space of performance-accuracy tradeoffs 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 which 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 2 × --10 × with acceptable loss in visual quality and significantly outperforms loop perforation.

Supplementary Material

a153-lou-supp.pdf (lou.zip)

Supplemental movie, appendix, image and software files for, Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples

Download
7.20 MB

References

[1]

Edward H. Adelson, Charles H. Anderson, James R. Bergen, Peter J. Burt, and Joan M. Ogden. 1984. Pyramid methods in image processing. RCA Eng. 29, 6 (1984), 33--41.

[2]

Sameer Agarwal, Ravi Ramamoorthi, Serge Belongie, and Henrik Wann Jensen. 2003. Structured importance sampling of environment maps. ACM Trans. Graph. 22, 3 (2003), 605--612.

Digital Library

[3]

A. V. Aho, R. Sethi, and J. D. Ullman. 1986. Compilers Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.

Digital Library

[4]

Anna I. Esparcia Alcázar and Ken C. Sharman. 1996. Some applications of genetic programming in digital signal processing. Late Breaking Papers at the Genetic Programming 1996 Conference Stanford University.

[5]

J. Ansel, S. Kamil, K. Veeramachaneni, U. O’Reilly, and S. Amarasinghe. 2013. OpenTuner: An extensible framework for program autotuning.

[6]

Soonmin Bae, Sylvain Paris, and Frédo Durand. 2006. Two-scale tone management for photographic look. In ACM Transactions on Graphics (TOG), Vol. 25. ACM, New York, NY, 637--645.

Digital Library

[7]

Francesco Banterle, Massimiliano Corsini, Paolo Cignoni, and Roberto Scopigno. 2012. A low-memory, straightforward and fast bilateral filter through subsampling in spatial domain. Comput. Graph. Forum 31, 1 (February 2012), 19--32. http://vcg.isti.cnr.it/Publications/2012/BCCS12.

Digital Library

[8]

Gary Bishop, Henry Fuchs, Leonard McMillan, and Ellen J. Scher Zagier. 1994. Frameless rendering: Double buffering considered harmful. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’94). ACM, New York, NY, 175--176.

Digital Library

[9]

Green Magenta Red Blue Black. 2009. YUV color space. Communications Engineering Desk Reference (2009), 469.

[10]

Adam Brady, Jason Lawrence, Pieter Peers, and Westley Weimer. 2014. genBRDF: Discovering new analytic BRDFs with genetic programming. ACM Transactions on Graphics (Proc. SIGGRAPH) (Aug. 2014). ACM, New York, NY.

Digital Library

[11]

I. Buck. 2007. GPU computing: Programming a massively parallel processor. CGO’07: Proceedings of the International Symposium on Code Generation and Optimization, IEEE Computer Society (2007).

Digital Library

[12]

Ian Buck, Tim Foley, Daniel Horn, Jeremy Sugerman, Kayvon Fatahalian, Mike Houston, and Pat Hanrahan. 2004. Brook for GPUs: Stream computing on graphics hardware. In ACM Transactions on Graphics (TOG), Vol. 23. ACM, New York, NY, 777--786.

Digital Library

[13]

Cy Chan, Jason Ansel, Yee Lok Wong, Saman Amarasinghe, and Alan Edelman. 2009. Autotuning multigrid with PetaBricks. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. IEEE, Article 5 (2009), 12 pages.

Digital Library

[14]

Swarat Chaudhuri, Sumit Gulwani, Roberto Lublinerman, and Sara Navidpour. 2011. Proving programs robust. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering. ACM, New York, NY, 102--112.

Digital Library

[15]

Jiawen Chen, Sylvain Paris, and Frédo Durand. 2007. Real-time edge-aware image processing with the bilateral grid. ACM Trans. Graph. 26, 3, Article 103 (July 2007).

Digital Library

[16]

Matthias Christen, Olaf Schenk, and Helmar Burkhart. 2011. Patus: A code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures. In Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS). IEEE, 676--687.

Digital Library

[17]

Cyrille Damez, Kirill Dmitriev, and Karol Myszkowski. 2003. State of the art in global illumination for interactive applications and high-quality animations. Comput. Graph. Forum 22, 1 (2003), 55--77.

[18]

Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An efficient SMT solver. In Tools and Algorithms for the Construction and Analysis of Systems. Springer, Berlin, 337--340.

Digital Library

[19]

Zeev Farbman, Raanan Fattal, and Dani Lischinski. 2011. Convolution pyramids. ACM Trans. Graph. 30, 6 (2011), 175:1--175:8.

Digital Library

[20]

R. W. Floyd and L. Steinberg. 1976. An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display 17 (1976), 75--77.

[21]

B. Guenter and D. Nehab. 2010. The neon image processing language. Tech. Rep. MSR-TR-2010-175, Microsoft Research (2010).

[22]

Yong He, Yan Gu, and Kayvon Fatahalian. 2014. Extending the graphics pipeline with adaptive, multi-rate shading. ACM Trans. Graph. 33, 4 (2014), 142.

Digital Library

[23]

Paul S. Heckbert. 1986. Filtering by repeated integration. ACM SIGGRAPH Comput. Graph. 20, 4 (1986), 315--321.

Digital Library

[24]

Henry Kang, Seungyong Lee, and Charles K. Chui. 2009. Flow-based image abstraction. IEEE Trans. Vis. Comput. Graph. 15, 1 (2009), 62--76.

Digital Library

[25]

Alexander Keller. 1997. Instant radiosity. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’97). ACM Press/Addison-Wesley Publishing Co., New York, NY, 49--56.

Digital Library

[26]

John R. Koza. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA.

Digital Library

[27]

Sasa Misailovic, Daniel M. Roy, and Martin C. Rinard. 2011. Probabilistically accurate program transformations. In Static Analysis. Springer, Berlin, 316--333.

Digital Library

[28]

Diego Nehab, André Maximo, Rodolfo S. Lima, and Hugues Hoppe. 2011. GPU-efficient recursive filtering and summed-area tables. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, New York, NY, 176.

Digital Library

[29]

OpenCL. 2013. The OpenCL specification, version 2.0. http://www.khronos.org/registry/cl/specs/opencl-1.2.pdf, Khronos Group (2013).

[30]

Victor Ostromoukhov. 2001. A simple and efficient error-diffusion algorithm. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’01). ACM, New York, NY, 567--572.

Digital Library

[31]

Sylvain Paris, Samuel W. Hasinoff, and Jan Kautz. 2011. Local Laplacian filters: Edge-aware image processing with a Laplacian pyramid. ACM Trans. Graph. 30, 4, Article 68 (July 2011), 12 pages.

Digital Library

[32]

C. A. Párraga, G. Brelstaff, T. Troscianko, and I. R. Moorehead. 1998. Color and luminance information in natural scenes. J. Opt. Soc. Am. 15, 3 (1998), 563--569.

[33]

Theodosios Pavlidis. 2012. Algorithms for Graphics and Image Processing. Springer Science & Business Media, Berlin.

[34]

PixelBender. 2010. Adobe PixelBender reference. Adobe (2010).

[35]

J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. Amarasinghe. 2013. Halide: A language and compiler for optimizing parallelism, locality and recomputation in image processing pipelines. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (Jun 2013).

Digital Library

[36]

Ravi Ramamoorthi, Dhruv Mahajan, and Peter Belhumeur. 2007. A first-order analysis of lighting, shading, and shadows. ACM Trans. Graph. 26, 1, Article 2 (Jan. 2007).

Digital Library

[37]

Azriel Rosenfeld and John L. Pfaltz. 1968. Distance functions on digital pictures. Pattern Recogn. 1, 1 (1968), 33--61.

[38]

M. A. Shantzis. 1994. A model for efficient and flexible image computing. ACM Transactions on Graphics (Proc. SIGGRAPH) (Aug. 1994). ACM, New York, NY.

Digital Library

[39]

K. C. Sharman, A. I. E. Alcazar, and Y. Li. 1998. Evolving signal processing algorithms by genetic programming. In Genetic Algorithms in Engineering Systems: Innovations and Applications, 1995. GALESIA. First International Conference on (Conf. Publ. No. 414). 473--480.

[40]

Stelios Sidiroglou-Douskos, Sasa Misailovic, Henry Hoffmann, and Martin Rinard. 2011. Managing performance vs. accuracy tradeoffs with loop perforation. In Proceedings of the 19th ACM SIGSOFT Symposium. ACM, New York, NY, 124--134.

Digital Library

[41]

P. Sitthi-amorn, N. Modly, W. Weimer, and J. Lawrence. 2011. Genetic programming for shader simplification. ACM Trans. Graph. 24, 111 (2011), 647.

Digital Library

[42]

C. Tomasi and R. Manduchi. 1998. Bilateral filtering for gray and color images. In Proceedings of the International Conference on Computer Vision (ICCV). 839--846.

Digital Library

[43]

K. Uesaka. 2003. Evolutionary synthesis of digital filter structures using genetic programming. IEEE Trans. Circuit. Syst. II: Analog Digital Sign. Process. 50, 12 (2003).

[44]

K. Uesaka and M. Kawamata. 2000. Synthesis of low-sensitivity second-order digital filters using genetic programming with automatically defined functions. IEEE Sign. Process. Lett. 7, 4 (2000), 83--85.

[45]

Karthik Vaidyanathan, Marco Salvi, Robert Toth, Tim Foley, Tomas Akenine-Möller, Jim Nilsson, Jacob Munkberg, Jon Hasselgren, Masamichi Sugihara, Petrik Clarberg, and others. 2014. Coarse pixel shading. In High Performance Graphics.

Digital Library

[46]

Li-Yi Wei. 2008. Parallel Poisson disk sampling. In ACM Transactions on Graphics (TOG), Vol. 27. ACM, New York, NY, 20.

Digital Library

[47]

Lei Yang, Pedro V. Sander, and Jason Lawrence. 2008. Geometry-aware framebuffer level of detail. In Eurographics Symposium on Rendering (EGSR).

Digital Library

[48]

Ian T. Young and Lucas J. Van Vliet. 1995. Recursive implementation of the Gaussian filter. Sign. Process. 44, 2 (1995), 139--151.

Digital Library

[49]

Yang Yu and Yu Xinjie. 2007. Cooperative coevolutionary genetic algorithm for digital IIR filter design. IEEE Trans. Industr. Electron. 54, 3 (2007), 1311--1318.

Cited By

Oishi SFukushima N(2023)Retinex-Based Relighting for Night PhotographyApplied Sciences10.3390/app1303171913:3(1719)Online publication date: 29-Jan-2023
https://doi.org/10.3390/app13031719
Raza MJaved SKazmi MAziz AUl Haque MQazi S(2023)Approximate Computing: Hardware and Software Techniques, Tools and Their ApplicationsJournal of Circuits, Systems and Computers10.1142/S021812662430001033:04Online publication date: 20-Sep-2023
https://doi.org/10.1142/S0218126624300010
Ma KGharbi MAdams AKamil SLi TBarnes CRagan-Kelley J(2022)Searching for Fast Demosaicking AlgorithmsACM Transactions on Graphics10.1145/350846141:5(1-18)Online publication date: 13-May-2022
https://dl.acm.org/doi/10.1145/3508461
Show More Cited By

Index Terms

Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
  2. Computer graphics
    1. Image manipulation
2. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction techniques

Recommendations

Managing performance vs. accuracy trade-offs with loop perforation
ESEC/FSE '11: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering

Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-...
An Optimized Dependence Convex Hull Partitioning Technique to Maximize Parallelism of Nested Loops with Non-Uniform Dependences
ICPADS '00: Proceedings of the Seventh International Conference on Parallel and Distributed Systems

There are many methods existing for nested loop partitioning; however, most of them perform poorly when partitioning loops with non-uniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism to exploit parallelism ...
Computing the correct Increment of Induction Pointers with application to loop unrolling

Induction pointers (IPs) are the analogue of induction variables (IVs), namely, pointers that are advanced by a fixed amount every iteration of a loop (e.g., p=p->next->next). Although IPs have been considered in previous works, there is no algorithm to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 35, Issue 5

September 2016

156 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2965650

Editor:
Kavita Bala
Cornell University

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 September 2016

Accepted: 01 March 2016

Revised: 01 February 2016

Received: 01 September 2015

Published in TOG Volume 35, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
504
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)21

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Oishi SFukushima N(2023)Retinex-Based Relighting for Night PhotographyApplied Sciences10.3390/app1303171913:3(1719)Online publication date: 29-Jan-2023
https://doi.org/10.3390/app13031719
Raza MJaved SKazmi MAziz AUl Haque MQazi S(2023)Approximate Computing: Hardware and Software Techniques, Tools and Their ApplicationsJournal of Circuits, Systems and Computers10.1142/S021812662430001033:04Online publication date: 20-Sep-2023
https://doi.org/10.1142/S0218126624300010
Ma KGharbi MAdams AKamil SLi TBarnes CRagan-Kelley J(2022)Searching for Fast Demosaicking AlgorithmsACM Transactions on Graphics10.1145/350846141:5(1-18)Online publication date: 13-May-2022
https://dl.acm.org/doi/10.1145/3508461
Yang YBarnes CFinkelstein A(2022)Learning from Shader Program TracesComputer Graphics Forum10.1111/cgf.1445741:2(41-56)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14457
Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Fukushima NTsubokawa TMaeda Y(2019)Vector Addressing for Non-Sequential Sampling in Fir Image Filtering2019 IEEE International Conference on Image Processing (ICIP)10.1109/ICIP.2019.8803565(4185-4189)Online publication date: Sep-2019
https://doi.org/10.1109/ICIP.2019.8803565
Maier DMammeri NCosenza BJuurlink B(2019)Approximating Memory-bound Applications on Mobile GPUs2019 International Conference on High Performance Computing & Simulation (HPCS)10.1109/HPCS48598.2019.9188051(329-335)Online publication date: Jul-2019
https://doi.org/10.1109/HPCS48598.2019.9188051
Maeda YFukushima NMatsuo H(2018)Taxonomy of Vectorization Patterns of Programming for FIR Image Filters Using Kernel Subsampling and New OneApplied Sciences10.3390/app80812358:8(1235)Online publication date: 26-Jul-2018
https://doi.org/10.3390/app8081235
Bonnot JDesnos KMenard DMudge TPnevmatikatos D(2018)Algorithm-level approximation for fast (or not) embedded stereovision algorithmProceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation10.1145/3229631.3229638(139-145)Online publication date: 15-Jul-2018
https://dl.acm.org/doi/10.1145/3229631.3229638
Maier DCosenza BJuurlink B(2018)Local memory-aware kernel perforationProceedings of the 2018 International Symposium on Code Generation and Optimization - CGO 201810.1145/3179541.3168814(278-287)Online publication date: 2018
https://doi.org/10.1145/3179541.3168814
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents