%0 Journal Article %1 budig2016matching %A Budig, Benedikt %A van Dijk, Thomas C. %A Wolff, Alexander %D 2016 %I ACM %J Transactions on Spatial Algorithms and Systems (TSAS) %K early-prints historical-maps myown %N 4 %P 13:1-13:24 %T Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing %U http://doi.acm.org/10.1145/2994598 %V 2 %X 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 sensitivity analysis 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’s 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.

@article{budig2016matching, abstract = {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 sensitivity analysis 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’s 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.}, added-at = {2016-11-29T10:49:37.000+0100}, author = {Budig, Benedikt and van Dijk, Thomas C. and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/250afafb554e24a93d8bc4f3d529f0e8f/benedikt.budig}, interhash = {b8ace3e81f219f502b6bff848c1cbf44}, intrahash = {50afafb554e24a93d8bc4f3d529f0e8f}, journal = {Transactions on Spatial Algorithms and Systems (TSAS)}, keywords = {early-prints historical-maps myown}, month = nov, number = 4, pages = {13:1-13:24}, publisher = {ACM}, timestamp = {2016-11-29T10:49:37.000+0100}, title = {Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing}, url = {http://doi.acm.org/10.1145/2994598}, volume = 2, year = 2016 }