Brief (né Budig), Benedikt - Chair of Computer Science I

Research Interests

Metadata extraction from historical maps
Algorithms for Geographic Information Systems
Systems with user interaction
Implementation (GitHub organisation of the chair)

Projects

Talks

"Glyph Miner: A System for Efficiently Extracting Glyphs from Early Prints in the Context of OCR" [PDF], presented at JCDL 2016.
"Towards a Pipeline for Metadata Extraction from Historical Maps" [PDF], presented at the International Workshop on Exploring Old Maps (EOM 2016).
"Efficient Algorithms and User Interaction for Metadata Extraction from Historical Maps" [PDF], presented at the ACM SIGSPATIAL 2015 PhD Symposium.
"Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing" [PDF], presented at the 2nd ACM SIGSPATIAL Workshop on MapInteraction 2014.

Scholarships und Awards

July 2017:
Distinction "Best of Computing – Notable Article" for "Matching Labels and Markers in Historical Maps: An Algorithm with Interactive Postprocessing" [paper] by the ACM Computing Review. With Thomas van Dijk und Alexander Wolff.
November 2015:
Best Poster Award Runners up at 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2015 (ACMGIS) for "There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points." [PDF] With Lukas Beckmann, Thomas van Dijk and Johannes Schamel.
October 2015:
Best Applied Paper Award at Discovery Science 2015 for "Active Learning for Classifying Template Matches in Historical Maps." [PDF] With Thomas van Dijk.
October 2014:
Doctoral scholarship of the German National Academic Foundation (Studienstiftung des deutschen Volkes)

Teaching

SS17: Tutorials Algorithms for Geographic Information Systems
WS16: Seminar Algorithms for Extracting Data from Historical Maps (new!)
WS16: Tutorials Approximation Algorithms
SS16: Tutorials Visualization of Graphs
WS15: Tutorials Approximation Algorithms
SS15: Tutorials Algorithms for Geographic Information Systems
WS14: Tutorials Computational Geometry

Publications

2016[ to top ]

Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing. Budig, Benedikt; van Dijk, Thomas C.; Wolff, Alexander. In Transactions on Spatial Algorithms and Systems (TSAS), 2(4), pp. 13:1–13:24. ACM, 2016.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
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.}, author = {Budig, Benedikt and van Dijk, Thomas C. and Wolff, Alexander}, journal = {Transactions on Spatial Algorithms and Systems (TSAS)}, keywords = {historical-maps}, month = 11, number = 4, pages = {13:1-13:24}, publisher = {ACM}, title = {Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing}, volume = 2, year = 2016 }
Polygon Consensus: Smart Crowdsourcing for Extracting Building Footprints from Historical Maps. Budig, Benedikt; Van Dijk, Thomas C.; Feitsch, Fabian; Giraldo Arteaga, Mauricio. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2016), pp. 66:1–66:4. 2016.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Over the course of three years, the New York Public Library has run a crowdsourcing project to extract polygonal representation of the building footprints from insurance atlases of the 19th and early-20th century. As is common in crowdsourcing projects, the overall problem was decomposed into small user tasks and each task was given to multiple users. In the case of polygons representing building footprints, it is unclear how best to integrate the answers into a majority vote: given a set of polygons ostensibly describing the same footprint, what is the consensus? We discuss desirable properties of such a "consensus polygon" and arrive at an efficient algorithm. We have manually evaluated the algorithm on approximately 3,000 polygons corresponding to 200 footprints and observe that our algorithmic consensus polygons are correct for 96% of the footprints whereas only 85% of the (input) crowd polygons are correct.

@inproceedings{budig2016polygon, abstract = {Over the course of three years, the New York Public Library has run a crowdsourcing project to extract polygonal representation of the building footprints from insurance atlases of the 19th and early-20th century. As is common in crowdsourcing projects, the overall problem was decomposed into small user tasks and each task was given to multiple users. In the case of polygons representing building footprints, it is unclear how best to integrate the answers into a majority vote: given a set of polygons ostensibly describing the same footprint, what is the consensus? We discuss desirable properties of such a "consensus polygon" and arrive at an efficient algorithm. We have manually evaluated the algorithm on approximately 3,000 polygons corresponding to 200 footprints and observe that our algorithmic consensus polygons are correct for 96% of the footprints whereas only 85% of the (input) crowd polygons are correct.}, author = {Budig, Benedikt and Van Dijk, Thomas C. and Feitsch, Fabian and Giraldo Arteaga, Mauricio}, booktitle = {Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2016)}, keywords = {historicalmaps}, pages = {66:1–66:4}, title = {Polygon Consensus: Smart Crowdsourcing for Extracting Building Footprints from Historical Maps}, year = 2016 }
Glyph Miner: A System for Efficiently Extracting Glyphs from Early Prints in the Context of OCR. Budig, Benedikt; van Dijk, Thomas C.; Kirchner, Felix. In Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries, of JCDL ’16, N. R. Adam, L. (Boots) Cassel, Y. Yesha, R. Furuta, M. C. Weigle (eds.), pp. 31–34. ACM, 2016.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
While off-the-shelf OCR systems work well on many modern documents, the heterogeneity of early prints provides a significant challenge. To achieve good recognition quality, existing software must be "trained" specifically to each particular corpus. This is a tedious process that involves significant user effort. In this paper we demonstrate a system that generically replaces a common part of the training pipeline with a more efficient workflow: Given a set of scanned pages of a historical document, our system uses an efficient user interaction to semi-automatically extract large numbers of occurrences of glyphs indicated by the user. In a preliminary case study, we evaluate the effectiveness of our approach by embedding our system into the workflow at the University Library Würzburg.

@inproceedings{conf/jcdl/BudigDK16, abstract = {While off-the-shelf OCR systems work well on many modern documents, the heterogeneity of early prints provides a significant challenge. To achieve good recognition quality, existing software must be "trained" specifically to each particular corpus. This is a tedious process that involves significant user effort. In this paper we demonstrate a system that generically replaces a common part of the training pipeline with a more efficient workflow: Given a set of scanned pages of a historical document, our system uses an efficient user interaction to semi-automatically extract large numbers of occurrences of glyphs indicated by the user. In a preliminary case study, we evaluate the effectiveness of our approach by embedding our system into the workflow at the University Library Würzburg.}, author = {Budig, Benedikt and van Dijk, Thomas C. and Kirchner, Felix}, booktitle = {Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries}, crossref = {conf/jcdl/2016}, editor = {Adam, Nabil R. and Cassel, Lillian (Boots) and Yesha, Yelena and Furuta, Richard and Weigle, Michele C.}, keywords = {incunables}, pages = {31–34}, publisher = {ACM}, series = {JCDL '16}, title = {Glyph Miner: A System for Efficiently Extracting Glyphs from Early Prints in the Context of OCR.}, year = 2016 }
Efficient Algorithms and User Interaction for Metadata Extraction from Historical Maps. Budig, Benedikt. In Proceedings of the 2nd ACM SIGSPATIAL PhD Workshop, of SIGSPATIAL PhD ’15, pp. 4:1–4:4. ACM, Bellevue, Washington, 2016.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
In this research project we develop a system for metadata extraction from historical maps. Such maps are valuable sources of information for researchers of various disciplines. However, metadata describing their (geographic) contents are scarce, because such information mostly has to be extracted by hand. Examining related work, we find that no holistic, automated solutions for this problem have been developed so far. Our system aims at speeding up the process of metadata extraction, using efficient algorithms combined with user interaction. We present our approach, which is a pipeline consisting of several steps. The layout of this system is modular; we discuss two modules in the pipeline that we have already developed and sketch our solutions. We conclude this report with an outlook and future work, which includes crowdsourcing applications.

@inproceedings{Budig:2015:EAU:2855680.2855841, abstract = {In this research project we develop a system for metadata extraction from historical maps. Such maps are valuable sources of information for researchers of various disciplines. However, metadata describing their (geographic) contents are scarce, because such information mostly has to be extracted by hand. Examining related work, we find that no holistic, automated solutions for this problem have been developed so far. Our system aims at speeding up the process of metadata extraction, using efficient algorithms combined with user interaction. We present our approach, which is a pipeline consisting of several steps. The layout of this system is modular; we discuss two modules in the pipeline that we have already developed and sketch our solutions. We conclude this report with an outlook and future work, which includes crowdsourcing applications.}, address = {New York, NY, USA}, author = {Budig, Benedikt}, booktitle = {Proceedings of the 2nd ACM SIGSPATIAL PhD Workshop}, keywords = {hci}, pages = {4:1–4:4}, publisher = {ACM}, series = {SIGSPATIAL PhD '15}, title = {Efficient Algorithms and User Interaction for Metadata Extraction from Historical Maps}, year = 2016 }

2015[ to top ]

There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points. Beckmann, Lukas; Budig, Benedikt; van Dijk, Thomas C.; Schamel, Johannes. In Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015), pp. 238–241. ACM, 2015.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
There is much interest in the automatic analysis of GPS trajectories, motivated amongst others by animal tracking, traffic modelling and tourism studies. Core questions involve for example detecting stopping points and flocking behaviour, and developing routing models. In this paper we consider turning points. We develop a formal definition of "turning point" based on analysing the structure of free-space diagrams for Fréchet distance. We give an efficient algorithm for computing an optimal set of turning points under this criterion. Our method is evaluated in the context of a current study on tourist preferences at Berchtesgaden National Park, Germany. We evaluate the suitability of our definition and the efficiency of our algorithm on a large set of real-world GPS trajectories collected by outdoor recreationists. A ground truth of turning points was established by hand for the complete data set. Experiments show that the runtime and quality of our method are suitable for practical applications.

@inproceedings{beckmann2015there, abstract = {There is much interest in the automatic analysis of GPS trajectories, motivated amongst others by animal tracking, traffic modelling and tourism studies. Core questions involve for example detecting stopping points and flocking behaviour, and developing routing models. In this paper we consider turning points. We develop a formal definition of "turning point" based on analysing the structure of free-space diagrams for Fréchet distance. We give an efficient algorithm for computing an optimal set of turning points under this criterion. Our method is evaluated in the context of a current study on tourist preferences at Berchtesgaden National Park, Germany. We evaluate the suitability of our definition and the efficiency of our algorithm on a large set of real-world GPS trajectories collected by outdoor recreationists. A ground truth of turning points was established by hand for the complete data set. Experiments show that the runtime and quality of our method are suitable for practical applications.}, author = {Beckmann, Lukas and Budig, Benedikt and van Dijk, Thomas C. and Schamel, Johannes}, booktitle = {Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015)}, keywords = {frechet}, pages = {238–241}, publisher = {ACM}, title = {There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points}, year = 2015 }
Active Learning for Classifying Template Matches in Historical Maps. Budig, Benedikt; van Dijk, Thomas C. In Proceedings of the 18th International Conference on Discovery Science, Vol. 9356 of Lecture Notes in Computer Science, pp. 33–47. Springer, 2015.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Historical maps are important sources of information for scholars of various disciplines. Many libraries are digitising their map collections as bitmap images, but for these collections to be most useful, there is a need for searchable metadata. Due to the heterogeneity of the images, metadata are mostly extracted by hand - if at all: many collections are so large that it is important to minimise the effort spent on individual maps. We propose an active-learning approach to one of the practical problems in automatic metadata extraction from historical maps: locating occurrences of image elements such as text or place markers. For that, we combine template matching (to locate possible occurrences) with active learning (to efficiently determine a classification). Using this approach, we design a human computer interaction in which large numbers of elements on a map can be located reliably using little user effort. We experimentally demonstrate the effectiveness of this approach on real-world data.

@inproceedings{conf/dis/BudigD15, abstract = {Historical maps are important sources of information for scholars of various disciplines. Many libraries are digitising their map collections as bitmap images, but for these collections to be most useful, there is a need for searchable metadata. Due to the heterogeneity of the images, metadata are mostly extracted by hand - if at all: many collections are so large that it is important to minimise the effort spent on individual maps. We propose an active-learning approach to one of the practical problems in automatic metadata extraction from historical maps: locating occurrences of image elements such as text or place markers. For that, we combine template matching (to locate possible occurrences) with active learning (to efficiently determine a classification). Using this approach, we design a human computer interaction in which large numbers of elements on a map can be located reliably using little user effort. We experimentally demonstrate the effectiveness of this approach on real-world data.}, author = {Budig, Benedikt and van Dijk, Thomas C.}, booktitle = {Proceedings of the 18th International Conference on Discovery Science}, crossref = {conf/dis/2015}, keywords = {template-matching}, pages = {33-47}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Active Learning for Classifying Template Matches in Historical Maps}, volume = 9356, year = 2015 }

2014[ to top ]

Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing. Budig, B.; van Dijk, T. C.; Wolff, A. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction (MapInteract ’14), pp. 22–28. ACM, 2014.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
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.}, author = {Budig, B. and van Dijk, T. C. and Wolff, A.}, booktitle = {Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction (MapInteract '14)}, keywords = {sys:relevantfor:csuniwue}, pages = {22–28}, publisher = {ACM}, title = {Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing}, year = 2014 }

2012[ to top ]

An algorithm for map matching given incomplete road data. Haunert, Jan-Henrik; Budig, Benedikt. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS ’12), pp. 510–513. ACM, 2012.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336--343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.

@inproceedings{HaunertBudig2012, abstract = {We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336–343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.}, author = {Haunert, Jan-Henrik and Budig, Benedikt}, booktitle = {Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS '12)}, keywords = {sys:relevantfor:csuniwue}, pages = {510–513}, publisher = {ACM}, title = {An algorithm for map matching given incomplete road data}, year = 2012 }

Projects

Talks

Scholarships und Awards

Picture credits