“Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples” by Zhu, Nguyen, Lawrence and Barnes

  • ©Liming Zhu, Paul Nguyen, Jason Lawrence, and Connelly Barnes

Conference:


Type:


Title:

    Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples

Session/Category Title: OPTIMIZING IMAGE PROCESSING

Presenter(s)/Author(s):


Moderator(s):


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.

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. 
    3. A. V. Aho, R. Sethi, and J. D. Ullman. 1986. Compilers Principles, Techniques, and Tools. Addison-Wesley, Reading, MA. 
    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. 
    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. 
    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. DOI:http://dx.doi.org/10.1145/192161.192195 
    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. 
    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). 
    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. 
    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. DOI:http://dx.doi.org/10.1145/1654059.1654065 
    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. 
    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). DOI:http://dx.doi.org/10.1145/1276377.1276506 
    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. DOI:http://dx.doi.org/10.1109/IPDPS.2011.70 
    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. DOI:http://dx.doi.org/10.1111/1467-8659.t01-1-00646
    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. 
    19. Zeev Farbman, Raanan Fattal, and Dani Lischinski. 2011. Convolution pyramids. ACM Trans. Graph. 30, 6 (2011), 175:1–175:8. 
    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. 
    23. Paul S. Heckbert. 1986. Filtering by repeated integration. ACM SIGGRAPH Comput. Graph. 20, 4 (1986), 315–321. 
    24. Henry Kang, Seungyong Lee, and Charles K. Chui. 2009. Flow-based image abstraction. IEEE Trans. Vis. Comput. Graph. 15, 1 (2009), 62–76. 
    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. DOI:http://dx.doi.org/10.1145/258734.258769 
    26. John R. Koza. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA. 
    27. Sasa Misailovic, Daniel M. Roy, and Martin C. Rinard. 2011. Probabilistically accurate program transformations. In Static Analysis. Springer, Berlin, 316–333. 
    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. 
    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. DOI:http://dx.doi.org/10.1145/383259.383326 
    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. DOI:http://dx.doi.org/10.1145/2010324.1964963 
    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). 
    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). DOI:http://dx.doi.org/10.1145/1189762.1189764 
    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. 
    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. 
    41. P. Sitthi-amorn, N. Modly, W. Weimer, and J. Lawrence. 2011. Genetic programming for shader simplification. ACM Trans. Graph. 24, 111 (2011), 647. 
    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. 
    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. 
    46. Li-Yi Wei. 2008. Parallel Poisson disk sampling. In ACM Transactions on Graphics (TOG), Vol. 27. ACM, New York, NY, 20. 
    47. Lei Yang, Pedro V. Sander, and Jason Lawrence. 2008. Geometry-aware framebuffer level of detail. In Eurographics Symposium on Rendering (EGSR). 
    48. Ian T. Young and Lucas J. Van Vliet. 1995. Recursive implementation of the Gaussian filter. Sign. Process. 44, 2 (1995), 139–151. 
    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.

ACM Digital Library Publication:


Overview Page: