{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T04:43:16Z","timestamp":1790052196083,"version":"4.0.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,12,7]],"date-time":"2017-12-07T00:00:00Z","timestamp":1512604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Kress Foundation, Seeger Foundation, Thera Foundation, Cotsen Family Foundation, and National Science Foundation","award":["NSF-GRFP and IIS-1251217"],"award-info":[{"award-number":["NSF-GRFP and IIS-1251217"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Comput. Cult. Herit."],"published-print":{"date-parts":[[2018,1,27]]},"abstract":"<jats:p>Global reconstruction of two-dimensional wall paintings (frescoes) from fragments is an important problem for many archaeological sites. The goal is to find the global position and rotation for each fragment so that all fragments jointly \u201creconstruct\u201d the original surface (i.e., solve the puzzle). Manual fragment placement is difficult and time-consuming, especially when fragments are irregularly shaped and uncolored. Systems have been proposed to first acquire 3D surface scans of the fragments and then use computer algorithms to solve the reconstruction problem. These systems work well for small test cases and for puzzles with distinctive features, but fail for larger reconstructions of real wall paintings with eroded and missing fragments due to the complexity of the reconstruction search space. We address the search problem with an unsupervised genetic algorithm: we evolve a pool of partial reconstructions that grow through recombination and selection over the course of generations. We introduce a novel algorithm for combining partial reconstructions that is robust to noise and outliers, and we provide a new selection procedure that balances fitness and diversity in the population. In experiments with a benchmark dataset, our algorithm is able to achieve larger and more accurate global reconstructions than previous automatic algorithms.<\/jats:p>","DOI":"10.1145\/3084547","type":"journal-article","created":{"date-parts":[[2017,12,11]],"date-time":"2017-12-11T08:26:47Z","timestamp":1512980807000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Wall Painting Reconstruction Using a Genetic Algorithm"],"prefix":"10.1145","volume":"11","author":[{"given":"Elena","family":"Sizikova","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Funkhouser","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE International Conference on Image Processing (ICIP\u201905)","author":"Biswas A.","unstructured":"A. Biswas , P. Bhowmick , and B. B. Bhattacharya . 2005. Reconstruction of torn documents using contour maps . In Proceedings of the IEEE International Conference on Image Processing (ICIP\u201905) . A. Biswas, P. Bhowmick, and B. B. Bhattacharya. 2005. Reconstruction of torn documents using contour maps. In Proceedings of the IEEE International Conference on Image Processing (ICIP\u201905)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1260\/2047-4970.1.2.313"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360683"},{"key":"e_1_2_1_4_1","volume-title":"Computer Analysis of Images and Patterns","author":"Bunke Horst","unstructured":"Horst Bunke and Guido Kaufmann . 1993. Jigsaw puzzle solving using approximate string matching and best-first search . In Computer Analysis of Images and Patterns . Springer , 299--308. Horst Bunke and Guido Kaufmann. 1993. Jigsaw puzzle solving using approximate string matching and best-first search. In Computer Analysis of Images and Patterns. Springer, 299--308."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Conference on Virtual Reality, Archaeology and Cultural Heritage (VAST\u201911)","author":"Casta\u00f1eda Antonio Garc\u00eda","year":"2011","unstructured":"Antonio Garc\u00eda Casta\u00f1eda , Benedict J. Brown , Szymon Rusinkiewicz , Thomas A. Funkhouser , and Tim Weyrich . 2011 . Global consistency in the automatic assembly of fragmented artefacts . In Proceedings of the International Conference on Virtual Reality, Archaeology and Cultural Heritage (VAST\u201911) . Antonio Garc\u00eda Casta\u00f1eda, Benedict J. Brown, Szymon Rusinkiewicz, Thomas A. Funkhouser, and Tim Weyrich. 2011. Global consistency in the automatic assembly of fragmented artefacts. In Proceedings of the International Conference on Virtual Reality, Archaeology and Cultural Heritage (VAST\u201911)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/584993.585032"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1033215"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDAR.2009.7"},{"key":"e_1_2_1_9_1","volume-title":"The Wall-Paintings of Thera","author":"Doumas C.","unstructured":"C. Doumas . 1992. The Wall-Paintings of Thera . Thera Foundation , Athens . C. Doumas. 1992. The Wall-Paintings of Thera. Thera Foundation, Athens."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3014027.3014031"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.03.014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1964.263781"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037820.2037824"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513410"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Symposium on Experimental Robotics (ISER\u201910)","author":"Henry Peter","year":"2010","unstructured":"Peter Henry , Michael Krainin , Evan Herbst , Xiaofeng Ren , and Dieter Fox . 2010 . RGB-D mapping: Using depth cameras for dense 3D modeling of indoor environments . In Proceedings of the International Symposium on Experimental Robotics (ISER\u201910) . Peter Henry, Michael Krainin, Evan Herbst, Xiaofeng Ren, and Dieter Fox. 2010. RGB-D mapping: Using depth cameras for dense 3D modeling of indoor environments. In Proceedings of the International Symposium on Experimental Robotics (ISER\u201910)."},{"key":"e_1_2_1_16_1","volume-title":"Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence","author":"Holland John","unstructured":"John Holland . 1992. Holland , Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence . MIT Press , Cambridge, MA . John Holland. 1992. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141925"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDAR.2009.154"},{"key":"e_1_2_1_19_1","first-page":"103","article-title":"Computer-aided reconstruction and new matches in the forma urbis romae","volume":"2","author":"Koller David","year":"2006","unstructured":"David Koller and Marc Levoy . 2006 . Computer-aided reconstruction and new matches in the forma urbis romae . Bull. Comm. Archeol. Comunale di Roma 2 (2006), 103 -- 125 . David Koller and Marc Levoy. 2006. Computer-aided reconstruction and new matches in the forma urbis romae. Bull. Comm. Archeol. Comunale di Roma 2 (2006), 103--125.","journal-title":"Bull. Comm. Archeol. Comunale di Roma"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201901)","author":"Kong Weixin","unstructured":"Weixin Kong and Benjamin B. Kimia . 2001. On solving 2D and 3D puzzles using curve matching . In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201901) . Weixin Kong and Benjamin B. Kimia. 2001. On solving 2D and 3D puzzles using curve matching. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201901)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1332477.1333477"},{"key":"e_1_2_1_22_1","volume-title":"International Joint Conference on Artificial Intelligence (IJCAI).","author":"Lucas Bruce D.","year":"1981","unstructured":"Bruce D. Lucas , Takeo Kanade , 1981 . An iterative image registration technique with an application to stereo vision . In International Joint Conference on Artificial Intelligence (IJCAI). Bruce D. Lucas, Takeo Kanade, et al. 1981. An iterative image registration technique with an application to stereo vision. In International Joint Conference on Artificial Intelligence (IJCAI)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2006.312891"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201903)","author":"Jonah","unstructured":"Jonah C. McBride and Benjamin B. Kimia. 2003. Archaeological fragment reconstruction using curve-matching . In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201903) Workshop. Jonah C. McBride and Benjamin B. Kimia. 2003. Archaeological fragment reconstruction using curve-matching. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201903) Workshop."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Onur Ozyesil et al. 2014. Camera motion estimation by convex programming (Doctoral dissertation Princeton University).  Onur Ozyesil et al. 2014. Camera motion estimation by convex programming (Doctoral dissertation Princeton University).","DOI":"10.1109\/CVPR.2015.7298883"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7299116"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0262-8856(03)00008-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009905"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2002.1003053"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IM.2001.924423"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2006.184"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11750-010-0156-6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/VSMM.2014.7136671"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.231"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.02.001"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866207"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/846227.848605"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(99)00075-8"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the IEEE International Symposium on Signal Processing and Information Technology.","author":"Ukovich Anna","unstructured":"Anna Ukovich , Giovanni Ramponi , Haralambos Doulaverakis , Yiannis Kompatsiaris , and M. G. Strintzis . 2004. Shredded document reconstruction using MPEG-7 standard descriptors . In Proceedings of the IEEE International Symposium on Signal Processing and Information Technology. Anna Ukovich, Giovanni Ramponi, Haralambos Doulaverakis, Yiannis Kompatsiaris, and M. G. Strintzis. 2004. Shredded document reconstruction using MPEG-7 standard descriptors. In Proceedings of the IEEE International Symposium on Signal Processing and Information Technology."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Eduardo Vendrell Vidal and Carlos S\u00e1nchez Belenguer. 2012. Automatic archaeological fragment reconstruction using hierarchical depth maps. In Conferencia Latinoamericana En Informatica (CLEI\u201912).  Eduardo Vendrell Vidal and Carlos S\u00e1nchez Belenguer. 2012. Automatic archaeological fragment reconstruction using hierarchical depth maps. In Conferencia Latinoamericana En Informatica (CLEI\u201912).","DOI":"10.1109\/CLEI.2012.6427149"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597178"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2008.923101"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186360"}],"container-title":["Journal on Computing and Cultural Heritage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084547","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:30:22Z","timestamp":1750203022000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,7]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,27]]}},"alternative-id":["10.1145\/3084547"],"URL":"https:\/\/doi.org\/10.1145\/3084547","relation":{},"ISSN":["1556-4673","1556-4711"],"issn-type":[{"value":"1556-4673","type":"print"},{"value":"1556-4711","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,7]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}