{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T03:56:52Z","timestamp":1774670212391,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,11,19]],"date-time":"2016-11-19T00:00:00Z","timestamp":1479513600000},"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. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2016,11,29]]},"abstract":"<jats:p>\n            In this article, we present an algorithmic system for determining the proper correspondence between place markers and their labels in historical maps. We assume that the locations of place markers (usually pictographs) and labels (pieces of text) have already been determined -- either algorithmically or by hand -- and we want to match the labels to the markers. This time-consuming step in the digitization process of historical maps is nontrivial even for humans but provides valuable metadata (e.g., when subsequently georeferencing the map). To speed up this process, we model the problem in terms of combinatorial optimization, solve that problem efficiently, and show how user interaction can be used to improve the quality of the results. We also consider a version of the model where we are given label fragments and additionally have to decide which fragments go together. We show that this problem is NP-hard. However, we give a polynomial-time algorithm for a restricted version of this fragment assignment problem. We have implemented the algorithm for the main problem and tested it on a manually extracted ground truth for eight historical maps with a combined total of more than 12,800 markers and labels. On average, the algorithm correctly matches 96% of the labels and is robust against noisy input. It furthermore performs a\n            <jats:italic>sensitivity analysis<\/jats:italic>\n            and in this way computes a measure of confidence for each of the matches. We use this as the basis for an interactive system where the user\u2019s effort is directed to checking those parts of the map where the algorithm is unsure; any corrections the user makes are propagated by the algorithm. We discuss a prototype of this system and statistically confirm that it successfully locates those areas on the map where the algorithm needs help.\n          <\/jats:p>","DOI":"10.1145\/2994598","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T14:01:46Z","timestamp":1479736906000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Matching Labels and Markers in Historical Maps"],"prefix":"10.1145","volume":"2","author":[{"given":"Benedikt","family":"Budig","sequence":"first","affiliation":[{"name":"Universit\u00e4t W\u00fcrzburg, Am Hubland, W\u00fcrzburg"}]},{"given":"Thomas C. Van","family":"Dijk","sequence":"additional","affiliation":[{"name":"Universit\u00e4t W\u00fcrzburg, Am Hubland, W\u00fcrzburg"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[{"name":"Universit\u00e4t W\u00fcrzburg, Am Hubland, W\u00fcrzburg"}]}],"member":"320","published-online":{"date-parts":[[2016,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534931.2534932"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 18th International Conference on Discovery Science (DS\u201915)","volume":"9356","author":"Budig Benedikt","unstructured":"Benedikt Budig and Thomas C . van Dijk. 2015. Active learning for classifying template matches in historical maps . In Proceedings of the 18th International Conference on Discovery Science (DS\u201915) (Lecture Notes in Computer Science) , Vol. 9356 . Springer, 33--47. Benedikt Budig and Thomas C. van Dijk. 2015. Active learning for classifying template matches in historical maps. In Proceedings of the 18th International Conference on Discovery Science (DS\u201915) (Lecture Notes in Computer Science), Vol. 9356. Springer, 33--47."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820887"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0203-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2557423"},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5540041"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96)","author":"Ester Martin","year":"1996","unstructured":"Martin Ester , Hans-Peter Kriegel , J\u00f6rg Sander , and Xiaowei Xu . 1996 . A density-based algorithm for discovering clusters in large spatial databases with noise . In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96) . The AAAI Press, Menlo Park, California, 226--231. Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96). The AAAI Press, Menlo Park, California, 226--231."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2005.10.010"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1045\/november2012-fleet"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.0805"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38628-2_50"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2467696.2467734"},{"key":"e_1_2_1_14_1","volume-title":"Applied Logistic Regression","author":"Hosmer David W.","unstructured":"David W. Hosmer Jr . and Stanley Lemeshow . 2004. Applied Logistic Regression . John Wiley 8 Sons. David W. Hosmer Jr. and Stanley Lemeshow. 2004. Applied Logistic Regression. John Wiley 8 Sons."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-8137.1912.tb05611.x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2011.01.005"},{"key":"e_1_2_1_17_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Springer , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Springer, 85--103."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.10.018"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSMC.2012.6377689"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDAR.2009.104"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201903)","volume":"2","author":"Toni","unstructured":"Toni M. Rath and Raghavan Manmatha. 2003. Word image matching using dynamic time warping . In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201903) , Vol. 2 . IEEE, II--521--II--527. Toni M. Rath and Raghavan Manmatha. 2003. Word image matching using dynamic time warping. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201903), Vol. 2. IEEE, II--521--II--527."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10032-006-0027-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2467696.2467729"},{"key":"e_1_2_1_24_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency . Springer . Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IS8T\/SPIE Electronic Imaging","author":"Shaw Tenzing","year":"2011","unstructured":"Tenzing Shaw and Peter Bajcsy . 2011. Automation of digital historical map analyses . In Proceedings of the IS8T\/SPIE Electronic Imaging 2011 , Vol. 7869 . SPIE. Tenzing Shaw and Peter Bajcsy. 2011. Automation of digital historical map analyses. In Proceedings of the IS8T\/SPIE Electronic Imaging 2011, Vol. 7869. SPIE."},{"key":"e_1_2_1_26_1","volume-title":"Linking early geospatial documents, one place at a time: Annotation of geographic documents with recogito. e-Perimetron 10, 2","author":"Simon Rainer","year":"2015","unstructured":"Rainer Simon , Elton Barker , Leif Isaksen , and Pau de Soto Ca\u00f1amares . 2015. Linking early geospatial documents, one place at a time: Annotation of geographic documents with recogito. e-Perimetron 10, 2 ( 2015 ), 49--59. Rainer Simon, Elton Barker, Leif Isaksen, and Pau de Soto Ca\u00f1amares. 2015. Linking early geospatial documents, one place at a time: Annotation of geographic documents with recogito. e-Perimetron 10, 2 (2015), 49--59."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998076.1998114"},{"key":"e_1_2_1_28_1","volume-title":"Towards semi-automatic annotation of toponyms on old maps. e-Perimetron 9, 3","author":"Simon Rainer","year":"2014","unstructured":"Rainer Simon , Peter Pilgerstorfer , Leif Isaksen , and Elton Barker . 2014. Towards semi-automatic annotation of toponyms on old maps. e-Perimetron 9, 3 ( 2014 ), 105--112. Rainer Simon, Peter Pilgerstorfer, Leif Isaksen, and Elton Barker. 2014. Towards semi-automatic annotation of toponyms on old maps. e-Perimetron 9, 3 (2014), 105--112."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126402"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDAR.2013.209"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2994598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2994598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:48Z","timestamp":1750217988000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2994598"}},"subtitle":["An Algorithm with Interactive Postprocessing"],"short-title":[],"issued":{"date-parts":[[2016,11,19]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,29]]}},"alternative-id":["10.1145\/2994598"],"URL":"https:\/\/doi.org\/10.1145\/2994598","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,19]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}