{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:41:37Z","timestamp":1763458897245,"version":"3.45.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,9,2]],"date-time":"2017-09-02T00:00:00Z","timestamp":1504310400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF 0811493 and CCF 0747220"],"award-info":[{"award-number":["CCF 0811493 and CCF 0747220"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,9,22]]},"abstract":"<jats:p>\n                    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\n                    <jats:italic toggle=\"yes\">image perforation<\/jats:italic>\n                    , 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 \u201cskip\u201d 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 \u00d7 --10 \u00d7 with acceptable loss in visual quality and significantly outperforms loop perforation.\n                  <\/jats:p>","DOI":"10.1145\/2904903","type":"journal-article","created":{"date-parts":[[2016,9,2]],"date-time":"2016-09-02T10:33:50Z","timestamp":1472812430000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Image Perforation"],"prefix":"10.1145","volume":"35","author":[{"given":"Liming","family":"Lou","sequence":"first","affiliation":[{"name":"Shandong University and University of Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Nguyen","sequence":"additional","affiliation":[{"name":"University of Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"Lawrence","sequence":"additional","affiliation":[{"name":"University of Virginia and Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Connelly","family":"Barnes","sequence":"additional","affiliation":[{"name":"University of Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,2]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"33","article-title":"Pyramid methods in image processing","volume":"29","author":"Adelson Edward H.","year":"1984","unstructured":"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.","journal-title":"RCA Eng."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882314"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","unstructured":"A. V. Aho R. Sethi and J. D. Ullman. 1986. Compilers Principles Techniques and Tools. Addison-Wesley Reading MA.","DOI":"10.5555\/6448"},{"key":"e_1_2_2_4_1","volume-title":"Esparcia Alc\u00e1zar and Ken C. Sharman","author":"Anna","year":"1996","unstructured":"Anna I. Esparcia Alc\u00e1zar 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."},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"J. Ansel S. Kamil K. Veeramachaneni U. O\u2019Reilly and S. Amarasinghe. 2013. OpenTuner: An extensible framework for program autotuning.","DOI":"10.1145\/2628071.2628092"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141935"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02078.x"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192195"},{"key":"e_1_2_2_9_1","volume-title":"YUV color space. Communications Engineering Desk Reference","author":"Red Blue Black Green Magenta","year":"2009","unstructured":"Green Magenta Red Blue Black. 2009. YUV color space. Communications Engineering Desk Reference (2009), 469."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601193"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.13"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015800"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654065"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025131"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276506"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.70"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.t01-1-00646"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024209"},{"key":"e_1_2_2_20_1","first-page":"75","article-title":"An adaptive algorithm for spatial grey scale","volume":"17","author":"Floyd R. W.","year":"1976","unstructured":"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.","journal-title":"Proceedings of the Society of Information Display"},{"key":"e_1_2_2_21_1","volume-title":"Tech. Rep. MSR-TR-2010-175, Microsoft Research","author":"Guenter B.","year":"2010","unstructured":"B. Guenter and D. Nehab. 2010. The neon image processing language. Tech. Rep. MSR-TR-2010-175, Microsoft Research (2010)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601105"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/15886.15921"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.81"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258769"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/138936"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2041552.2041576"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024210"},{"key":"e_1_2_2_29_1","unstructured":"OpenCL. 2013. The OpenCL specification version 2.0. http:\/\/www.khronos.org\/registry\/cl\/specs\/opencl-1.2.pdf Khronos Group (2013)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383326"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964963"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.15.000563"},{"volume-title":"Algorithms for Graphics and Image Processing","author":"Pavlidis Theodosios","key":"e_1_2_2_33_1","unstructured":"Theodosios Pavlidis. 2012. Algorithms for Graphics and Image Processing. Springer Science & Business Media, Berlin."},{"volume-title":"Adobe PixelBender reference. Adobe","year":"2010","key":"e_1_2_2_34_1","unstructured":"PixelBender. 2010. Adobe PixelBender reference. Adobe (2010)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189762.1189764"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(68)90013-7"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192191"},{"volume-title":"Genetic Algorithms in Engineering Systems: Innovations and Applications, 1995. GALESIA. First International Conference on (Conf. Publ. No. 414)","author":"Sharman K. C.","key":"e_1_2_2_39_1","unstructured":"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."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025133"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024186"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/938978.939190"},{"key":"e_1_2_2_43_1","article-title":"Evolutionary synthesis of digital filter structures using genetic programming","volume":"50","author":"Uesaka K.","year":"2003","unstructured":"K. Uesaka. 2003. Evolutionary synthesis of digital filter structures using genetic programming. IEEE Trans. Circuit. Syst. II: Analog Digital Sign. Process. 50, 12 (2003).","journal-title":"IEEE Trans. Circuit. Syst. II: Analog Digital Sign. Process."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/97.833004"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","unstructured":"Karthik Vaidyanathan Marco Salvi Robert Toth Tim Foley Tomas Akenine-M\u00f6ller Jim Nilsson Jacob Munkberg Jon Hasselgren Masamichi Sugihara Petrik Clarberg and others. 2014. Coarse pixel shading. In High Performance Graphics.","DOI":"10.5555\/2980009.2980011"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360619"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01256.x"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(95)00020-E"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIE.2007.893063"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2904903","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2904903","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2904903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:36:31Z","timestamp":1763458591000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2904903"}},"subtitle":["Automatically Accelerating Image Pipelines by Intelligently Skipping Samples"],"short-title":[],"issued":{"date-parts":[[2016,9,2]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,9,22]]}},"alternative-id":["10.1145\/2904903"],"URL":"https:\/\/doi.org\/10.1145\/2904903","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2016,9,2]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}