Hand-drawn cadastral map parsing, stitching and assembly via jigsaw puzzles

We present a robust method for parsing the content of hand-drawn cadastral maps in order to obtain high-resolution, digitized assemblies of larger regions from individual maps. The parsing phase involves solving a challenging background grid detection plem. We exploit the geometry of detected grids for stitching overlapping map images. A novel method for computing geometric compatibilities between non-overlapping map pieces is also introduced. It is shown to be important since existing chromatic compatibility measures are not as useful for hand-drawn maps. Assembly of maps involves solving an arbitrary-boundary jigsaw puzzle problem with non-overlapping pieces of the same rectangular shape. It corresponds to finding a maximum spanning graph within a multigraph whose edge weights are the piece compatibilities. Since the problem is NP-hard, we develop a polynomial time approximation algorithm that involves two distinct greedy decisions at each iteration. In contrast to existing evaluation metrics for fixed-boundary jigsaw puzzles, we present an \(F_1\) $F_1$ -score based evaluation scheme for the arbitrary-boundary jigsaw problem that evaluates relative placements of pieces instead of absolute locations. On a testing set of 218 images of 109 cadastral maps comprising 15 different map assembly problems, we achieve a high average \(F_1\) $F_1$ -score of 0.88. Results validate our compatibility measure as well as the two-stage greedy nature of our method. An ablation study isolates the importance of individual modules of the developed pipeline.