%0 Journal Article %1 budig2014matching %A Budig, B. %A van Dijk, T. C. %A Wolff, A. %D 2014 %J Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction %K myown %T Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing %X In this paper 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 want to match the labels to the markers. This time-consuming step in the digitization process of historical maps is non-trivial even for humans, but provides valuable metadata (for example when subsequently georeferencing the map). In order 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 results. We test the algorithm on a manually-extracted ground truth for two historical maps with a combined total of over 4000 markers and labels. The algorithm correctly matches 99% of the labels and is robust against noisy input. It furthermore performs a sensitivity analysis and in this way computes a measure of confidence for each of the assignments. We use this as the basis of an interactive system, where the user's effort is directed to checking the parts of the map where the algorithm is unsure; any corrections the user makes can be propagated by the algorithm. We discuss an early prototype of this system and statistically confirm that it successfully locates the areas on the map where the algorithm needs help.

@article{budig2014matching, abstract = {In this paper 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 want to match the labels to the markers. This time-consuming step in the digitization process of historical maps is non-trivial even for humans, but provides valuable metadata (for example when subsequently georeferencing the map). In order 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 results. We test the algorithm on a manually-extracted ground truth for two historical maps with a combined total of over 4000 markers and labels. The algorithm correctly matches 99% of the labels and is robust against noisy input. It furthermore performs a sensitivity analysis and in this way computes a measure of confidence for each of the assignments. We use this as the basis of an interactive system, where the user's effort is directed to checking the parts of the map where the algorithm is unsure; any corrections the user makes can be propagated by the algorithm. We discuss an early prototype of this system and statistically confirm that it successfully locates the areas on the map where the algorithm needs help.}, added-at = {2014-10-14T13:57:55.000+0200}, author = {Budig, B. and van Dijk, T. C. and Wolff, A.}, biburl = {https://www.bibsonomy.org/bibtex/2959f7f35877dff70d7b06c6fa186d427/thomasd}, interhash = {552fa4282c58da9438e47c6997c866c2}, intrahash = {959f7f35877dff70d7b06c6fa186d427}, journal = {Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction}, keywords = {myown}, note = {Best paper.}, timestamp = {2015-09-28T17:05:35.000+0200}, title = {Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing}, year = 2014 }