{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:58:03Z","timestamp":1771703883416,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>We introduce a new tool to solve the large linear systems arising from gradient-domain image processing. Specifically, we develop a streaming multigrid solver, which needs just two sequential passes over out-of-core data. This fast solution is enabled by a combination of three techniques: (1) use of second-order finite elements (rather than traditional finite differences) to reach sufficient accuracy in a single V-cycle, (2) temporally blocked relaxation, and (3) multi-level streaming to pipeline the restriction and prolongation phases into single streaming passes. A key contribution is the extension of the B-spline finite-element method to be compatible with the forward-difference gradient representation commonly used with images. Our streaming solver is also efficient for in-memory images, due to its fast convergence and excellent cache behavior. Remarkably, it can outperform spatially adaptive solvers that exploit application-specific knowledge. We demonstrate seamless stitching and tone-mapping of gigapixel images in about an hour on a notebook PC.<\/jats:p>","DOI":"10.1145\/1360612.1360620","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":95,"title":["Streaming multigrid for gradient-domain operations on large images"],"prefix":"10.1145","volume":"27","author":[{"given":"Michael","family":"Kazhdan","sequence":"first","affiliation":[{"name":"Johns Hopkins University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugues","family":"Hoppe","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015718"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276495"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073269"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141935"},{"key":"e_1_2_2_5_1","volume-title":"Symposium on Geometry Processing, 69--78","author":"Bolitho M.","unstructured":"Bolitho , M. , Kazhdan , M. , Burns , R. , and Hoppe , H . 2007. Multilevel streaming for out-of-core surface reconstruction . In Symposium on Geometry Processing, 69--78 . Bolitho, M., Kazhdan, M., Burns, R., and Hoppe, H. 2007. Multilevel streaming for out-of-core surface reconstruction. In Symposium on Geometry Processing, 69--78."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882364"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0431719-X"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Briggs W. Henson V. and McCormick S. 2000. A Multigrid Tutorial. Society for Industrial and Applied Mathematics.   Briggs W. Henson V. and McCormick S. 2000. A Multigrid Tutorial . Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719505"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02510352"},{"key":"e_1_2_2_10_1","first-page":"21","article-title":"Cache optimization for structured and unstructured grid multigrid","volume":"10","author":"Douglas C.","year":"2000","unstructured":"Douglas , C. , Hu , J. , Kowarschik , M. , R\u00fcde , U. , and Weiss , C. 2000 . Cache optimization for structured and unstructured grid multigrid . Electronic Transactions on Numerical Analysis 10 , 21 -- 40 . Douglas, C., Hu, J., Kowarschik, M., R\u00fcde, U., and Weiss, C. 2000. Cache optimization for structured and unstructured grid multigrid. Electronic Transactions on Numerical Analysis 10, 21--40.","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566573"},{"key":"e_1_2_2_12_1","volume-title":"European Conference on Computer Vision, 129--132","author":"Finlayson G.","unstructured":"Finlayson , G. , Hordley , S. , and Drew , M . 2002. Removing shadows from images . In European Conference on Computer Vision, 129--132 . Finlayson, G., Hordley, S., and Drew, M. 2002. Removing shadows from images. In European Conference on Computer Vision, 129--132."},{"key":"e_1_2_2_13_1","volume-title":"Computational Galerkin Methods","author":"Fletcher C.","unstructured":"Fletcher , C. 1984. Computational Galerkin Methods . Springer . Fletcher, C. 1984. Computational Galerkin Methods. Springer."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJCSE.2008.021111"},{"key":"e_1_2_2_15_1","volume-title":"Proc. of Graphics Hardware, 102--111","author":"Goodnight N.","unstructured":"Goodnight , N. , Woolley , C. , Lewin , G. , Luebke , D. , and Humphreys , G . 2003. A multigrid solver for boundary value problems using programmable graphics hardware . In Proc. of Graphics Hardware, 102--111 . Goodnight, N., Woolley, C., Lewin, G., Luebke, D., and Humphreys, G. 2003. A multigrid solver for boundary value problems using programmable graphics hardware. In Proc. of Graphics Hardware, 102--111."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199410"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142900373208"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(74)90022-7"},{"key":"e_1_2_2_19_1","volume-title":"Symposium on Geometry Processing, 73--82","author":"Kazhdan M.","unstructured":"Kazhdan , M. , Bolitho , M. , and Hoppe , H . 2006. Poisson surface reconstruction . In Symposium on Geometry Processing, 73--82 . Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, 73--82."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276497"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276494"},{"key":"e_1_2_2_22_1","volume-title":"European Conference on Computer Vision, 377--389","author":"Levin A.","unstructured":"Levin , A. , Zomet , A. , Peleg , S. , and Weiss , Y . 2004. Seamless image stitching in the gradient domain . In European Conference on Computer Vision, 377--389 . Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In European Conference on Computer Vision, 377--389."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015745"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360692"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882269"},{"key":"e_1_2_2_26_1","first-page":"365","article-title":"Data flow and storage allocation for the PDQ-5 program on the Philco-2000","volume":"6","author":"Pfeifer C.","year":"1963","unstructured":"Pfeifer , C. 1963 . Data flow and storage allocation for the PDQ-5 program on the Philco-2000 . Communications of the ACM 6 , 7, 365 -- 366 . Pfeifer, C. 1963. Data flow and storage allocation for the PDQ-5 program on the Philco-2000. Communications of the ACM 6, 7, 365--366.","journal-title":"Communications of the ACM"},{"key":"e_1_2_2_27_1","volume-title":"Tech. Rep. MSR-TR-2008-58, Microsoft Research.","author":"Szeliski R.","year":"2008","unstructured":"Szeliski , R. , Uyttendaele , M. , and Steedly , D . 2008 . Fast Poisson blending using multi-splines. Tech. Rep. MSR-TR-2008-58, Microsoft Research. Szeliski, R., Uyttendaele, M., and Steedly, D. 2008. Fast Poisson blending using multi-splines. Tech. Rep. MSR-TR-2008-58, Microsoft Research."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1142005"},{"key":"e_1_2_2_29_1","volume-title":"American","author":"Toledo S.","unstructured":"Toledo , S. 1999. A survey of out-of-core algorithms in numerical linear algebra . In External Memory Algorithms and Visualization, J. Abello and J. S. Vitter, Eds. American Mathematical Society Press , Providence, RI , 161--180. Toledo, S. 1999. A survey of out-of-core algorithms in numerical linear algebra. In External Memory Algorithms and Visualization, J. Abello and J. S. Vitter, Eds. American Mathematical Society Press, Providence, RI, 161--180."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2001.937606"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1360612.1360620","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1360612.1360620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:09Z","timestamp":1750254969000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1360612.1360620"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1360612.1360620"],"URL":"https:\/\/doi.org\/10.1145\/1360612.1360620","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2008-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}