Alignment of XIXth century cadasters

Introduction

About a thousand of French napoleonian cadasters have been scanned and need from now to be aligned. A lot of different cities are included in this catalogue as La Rochelle, Bordeaux, Lyon, Lille, Le Havre and also cities that are no longer under French juridiction as Rotterdam.

Similarly to the work that had been done by the Venice Time Machine project, the idea is to attach every maps from a cadaster in order to get a single map of each city.

The main challenge for this project is the automatisation of this process, despite all inconsistencies in the maps, in terms of scale, orientation or conventions. Indeed, even if the instructions for the realisation of the maps were quite strict, some differences might last. For example, if there were nothing to show in some areas, geometers were allowed to represent them at larger scale. Other example, maps are not always oriented top-north (which is even not always indicated).

Deliverables

This project provides an exploration of possible automation leads to align cadastres, as well as the development of an interface (in the form of a Jupyter Notebook) to supervise this task.

Together with this report, the deliverables are:

• AlignmentTool: the tool developed to supervise cadastres' alignment. GitHub repository: https://github.com/noe-d/AlignmentTool.
• La Rochelle's 1811 cadastres case study (hosted on the shared Google Drive):
  • predicted lines in La Rochelle's 1811 cadastres.
  • graph storing the matches between adjacent cadastres in JSON format.
  • recomposed image of La Rochelle's intramural cadastres.

Project setup

Methods exploration on Berney's cadaster

For the primary research of methods to reattach cadastral maps, the so called cadastre Berney from Lausanne (1827) has been used, as long as the ground truth for this particular case is known and lot of processing steps (as lines and classes predictions) have already been made. The first exercise has been made on the two first maps, using the lines prediction files. The quandary was to be able to detect the common parts of these two maps, in this case the Rue Pépinet and the top of Rue du petit chêne. Many different methods have been tested for that task, mainly with help of the OpenCV python library. The researches have focused on scale invariant feature transform (SIFT), General Hough Transform (GHT) and Template Matching (TM). The method that gave the most satisfying results (in terms of final output and computation time) was the template matching.

Template matching principle

Template matching is an OpenCV function provided under the name cv.matchTemplate(). It takes as an imput a large scale image and smaller one, called template, that it will try to find in the first image. Concretely, the function slides the template through the initial image and for each position, gives a score of closeness. Note that the template always fully overlap the image, therefore the template must be fully included in the initial image. The function gives then as an output a matrix (an example of such a heatmap can be seen below) with score for each position. It is then easy to find the position of the best score.

The function provides several ways to compute that score. The one used for this project is the so called TM_CCOEFF_NORMED, defined as :

where

and where T and I refer to pixels of the template, respectively initial, images, and finally w and h are width, respectively height, of the template.

Template matching is known to have better results on simpler images exhibiting clear contrasts between shapes. It is therefore a wise decision to preprocess the cadastres in order to bring their main features out. Thus, TM is performed here on the detected lines (see lines detection section for more details) when available, or on cadastres' edges otherwise.

First reattachment of two cadastral maps

Now that a sufficiently satisfying function had been found, the first milestone of this project was the first reattachment of two cadastral maps. The strategy was to manually cut a template in one of the maps and find the best match in the other one. Attaching the two maps together is then an almost straightforeward task, as long as the lines prediction files are only black (0) or white (255) pixels, and the final result is just the sum of the two of them adapted with the best matching position.

• 

  Berney 001

• 

  Template manually selected from Berney 001

• 

  Berney 002

Heatmap of the Template Matching process and detected template on the target image.

Alignment of Berney's 1827 cadastral maps 001 and 002

Organisation

As suggested before, the first steps of this project were quite empiric. Almost no step was automitzed and there were no other method than giving the two first maps to the function we were trying to use and hope that the result would be sufficiently satisfying and quickly computed. This finally gave us an heuristic argument to choose the template matching function.

But after this liminary choice, many challenges were still standing in front of us in order to perform large scale cadastres alignment.

• First, it was necessary to find criteria for the template’s extraction, ie. could we find a way that the pipeline detects by itself the common part of two maps ?
• Secondly, the orientation and scale differences in-between the maps were still problematic. Again, shall we indicate those variation « by hand » or could the pipeline understand it by itself ?
• A third problem was the capacity of our pipeline to be sufficiently precise to close loops of maps correctly, ie. would errors in successive matching cancel each other or propagate such that it would be impossible to place correctly the last map of a loop ?
• Finally, the probably most prominent challenge was our lack of metric. Indeed, the appreciation of the quality of the result of the matching was left to our own vision of the result. It would have been really beneficial to find an objective way to define the quality of the result, thanks to a metric.

The following table summaries the different ways we tried to handle those difficulties. Obviously, some methods were abandoned and some have been used until the end.

	Paradigm	Matching method	Template extraction	Data structure	Growth	Lines detection
Week 4	Automation	SIFT	-	-	1 to 1	-
Week 5		SIFT and GHT	Manual
Week 6		GHT and TM			Semi-automated 1 to 1
Week 7
Week 8		Template Matching	Manual and along lines	Dictionary
Week 9					1 to 1 or N
Week 10
Week 11	Supervision		Manual with user tool		1 to N	First attempts on La Rochelle
Week 12				Network
Week 13						Final steps on La Rochelle, with Google Colab and sliced images
Week 14

Automation process

Automatic extraction of 9 templates. Best match found is satisfying.

Automatic extraction of 8 templates. Best match found is not satisfying.

In order to automate the alignment task, efforts where put in three of the main challenges identified. A pipeline was then built to automatically extract templates, take into account variations in scales and orientations and iteratively spread over adjacent cadastres to cover large areas. However the incapacity to meet the fourth challenge, defining a semantically coherent metric, hindered the generalisation of this approach and led to mixed results.

This exploration was undertook on the lines pre-extracted from Berney's 1827 cadastres of Lausanne.

Automatic template extraction

In cadastres, the overlapping areas are situated on the borders of the maps. Hence, the template extraction process was automated to extract templates around most excentric points along given lines that still coded for a line.

To do so, an imaginary path parametrised by an angle is drawn from the center of the cadastre to its edge. Pixels values along this path are extracted and used to retrieve the coordinates of the last non-zero pixel value (ie. extracted line on the cadastre). A template can then be extracted around this point.

The function automating this task takes an integer N as argument that defines the number of templates to be extracted. Templates are then extracted along paths parametrised by the linear division of the circle in N pieces (see extract_templates). Examples are shown in the left hand side plot present in the figure on the right.

Nevertheless these plot mainly highlight the fragility of the matching method. Indeed they underline that the TM score doesn't align with the human understanding of the problem. Moreover, as TM is highly dependent on the templates, this approach is highly dependent on the chosen number of extracted templates N. For example here extracting 9 templates resulted in a coherent best match but extracting one less template yielded wrong results.

Orientation and scale integration

One of the factor deteriorating the quality of the matches are the slight variations of orientation. Thus, in order to limit this influence (and potentially to prepare to non-oriented cadastres) the matching process was made orientation invariant (over a given discrete range). The same procedure was applied to scales as Lausanne's cadastres relative scales are mixed between 1:1 and 1:2 (or inversly 1:0.5). The matching process was then a grid-search over the specified angles and scales, with scores obtained by matching the extracted template on the modified (rotated and rescaled) target cadastre.

However, beside increasing the computational cost, multiplying the number of parameters also heightens the chance of semantically incoherent match to get the best score (as there is only one, or few, good match and all others are deceiving).

NB.: at this state of the project, this method was achieved by rescaling and rotating the whole target cadastre. This approach is largely suboptimal and computationally very expensive, it was changed afterwards (as described here).

Peripheral growth

Both of the previously stated methods (Automatic template extraction and scale and orientation invariant TM) were then combined in an algorithm anchoring iteratively adjacents cadastres to the already integrated ones to spread the covered area. The list of adjacent cadastres were manually encoded and the parameters manually fine-tuned to reach meaningful results over several cadastres, see for example the left hand-side figure below. However this method demonstrated poor reliability and generalisation power, as illustrated on the right hand-side. There template 006 is wrongly matched on 008 and any additional consideration on this cadastre would be meaningless and detrimental to the general workflow.

• Iterative growth with successive anchors 001, 009, 010 and 008. Taking into account slight variations in orientation and two scales.
• 

  Before matching 006 onto 008. Matches are satisfying.

• 

  After matching 006 onto 008. Semantically wrong match.

Limitations

If automated, this approach still exhibited major drawbacks. First, it is computationally expensive. Plus, it is highly non-stable as it depends on the very sensitive TM algorithm. This matching method often produces semantically wrong results, which is even more true in less dense (or rural) areas. Moreover, poor matches cause dramatic error propagation. Finally, it is very time-consuming as it requires extensive manual fine-tuning of the parameters to reach meaningful results, even over reduced areas.

These issues inhibit any possibility of generalisation and complete automation. Nonetheless, most of these problems are believed to be, at least partly, solvable by determining a better metric to render the quality of the matches. A measure closer to human understanding could discard semantically wrong matches to avoid errors to plague the results. It would also ease the optimisation of the parameters, that could then be handled automatically through Machine Learning algorithms. Such metric could also take the form of an additional classifier based on more heuristics or directly be integrated by the machine through Deep Learning.

Facing the incapacity to define a convincing metric, we decided to shift paradigm and directly involve human understanding in the loop by developing a tool to supervise the alignment task.

AlignmentTool

The AlignmentTool was developed to offer a highly supervised method to perform the cadastres' alignment. The backend processes are mainly handled through OpenCv, the data structure is managed with NetworkX, and the Notebook interface relies on jupyter-innotater. The architecture and proceeding of each of these components are detailed below. Finally, the results of the proof of concept undertook on La Rochelle's Napoleonic cadastres from 1811 within Ferry's rampart are described and illustrated.

Backbone

The development of this tool compelled us to slightly revise the conceptual and theoretical framework for the matching and composition processes. The three major steps consisting in homologous points retrieval, pair-wise transformations computation and propagation are described in this section.

Matching

Example of a rotated template with tagged points.

The matching model aims at finding two pairs of homologous points in the anchor and target cadastres (see get_target_homologous). It relies on TM (described above). On the anchor cadastres the tagged positions are the top-left and bottom-right corners of the extracted template. On the target one, the corresponding points are retrieved from the best match found.

If both of the cadastres share the same orientation (ie. matches are evaluated without taking into account additional rotations), then the pixel associated with the top-left corner of the template corresponds to the location with the highest value computed through TM and the pixel associated with the bottom-right corner is given by adding the template width and height.

If both of the cadastres don't share the same orientation, this task requires slightly more efforts. This procedure iteratively rotates the template, resulting in images of different shapes filled with void, and performs TM using these rotated templates (see orientation_matching). Thus, the coordinates of the best match will correspond to the top-left corner of the best rotated template, which is no longer in line with the top-right corner of the extracted template. The new pixel coordinates corresponding to the orignial template top-left and bottom-right corners are retrieved by artificially rotating the original template and computing the displacement of specified points (see shift_template).

An example of points tracking in the rotated templates is shown on the figure on the right. The figure below displays the results obtained through this method on a pair of non-aligned cadastres.

Visualisation of the template's top left and bottom right corners on the anchor cadastre (left, cadastre E) and their corresponding points on the target cadastre (right, cadastre D).

Homography

Homographies are transformation matrices (3 by 3), widely used in computer vision, mapping points in one image to corresponding ones in another image. In the context of this project, homographies are restricted to Euclidean transformations (allowing rotations and translations but preserving the distance between every pair of points). However, as the rest of the implementation is more general, slight modifications of the homographies' computation could enable the intergration of more complex transformations (eg. affine or projective) within the pipeline.

The pairs of homologous points retrieved through the matching process allows to compute the corresponding homography between the anchor and target cadastres. On both images the pair of coordinates define a vector from the top right to the bottom left tags. As they are considered to refer to the same geographic entity, the cadastres can be re-oriented (relatively to one another) by calculating the angle α between these vectors. The translations in 𝑥 and 𝓎, t_𝑥 and t_𝓎, are computed by comparing points corresponding to the top left corner in the anchor image and target one (after re-orientation). The homography matrix is then given by:

This process is encoded in the function vector_alignment. It allows to turn the matches characterised by two pairs of homologous points into a transformation matrix, which can be applied on the target cadastre to obtain its composition with its anchor through warpTwoImages based on cv2.warpPerspective.

Propagation

Homographies demonstrate convenient properties that allow to propagate pairwise homographies in order to reconstruct larger areas.

1. Inversion — If H_1,2 is known, then H_2,1 is given by the inverse of H_1,2
   Allows to get rid of the directionality of the graph
2. Composition — If H_1,2 and H_2,3 are known, then H_1,3 is given by the product of H_1,2 and H_2,3
   Allows to directly link each connected nodes to each others

Thus, taking benefits of the network structure of the data (descibed below), the pairwise homographies can be operated to recover whole areas. This procedure is done by building a new graph centered on a selected node, and linked to every node that was connected to it in the original network (without notion of directionality). All other nodes are only connected (as targets) to this central node. Each one of the edges is characterised by an homography between the central node (anchor) and the connected component (target). These homographies are computed as the product of pair-wise homographies along the shortest path linking the selected central node to the target in the original graph (see buildCenteredNetwork).

The two images below show an example of cadastres composition, either using direct match (left) or homographies propagation along a path in the network (right). One can see that the quality of the composition is better in the direct match configuration, yet the propagation still provides satisfying results considering that it encompasses the proliferation of errors along four matches.

• Alignment of cadastres with direct edge or through propagation.
• 

  Direct match from A1 to D.

• 

  Propagation of matches A1 to A2 to B to C to D.

Network structure

The matches (when selected by the user) are collected in a directed graph. The nodes are the cadastres (or their labels) and the edges link the anchors (cadastres within which templates have been extracted) to their targets (cadastres matched). The edges store information about the matches between anchors and targets: their score and informations related to the matched positions (top left and bottom right corners of the extracted template in the anchor and corresponding positions in the target). An exemple of a possible realisation of such graph (for La Rochelle, 1811) is shown below.

These graph can be saved in JSON format with the following generic structure:

Network visualisation.

{
    "directed": true,
    "multigraph": false,
    "graph": {},
    "nodes": [{
        "h": int — height of the corresponding image,
        "w": int — width of the corresponding image,
        "label": str — name
    }, {
        "h": int — height of the corresponding image,
        "w": int — width of the corresponding image,
        "label": str — name
    }],
    "match": [{
        "score": float — score of the template matching process,
        "anchor_tl": tuple: two int — coordinate of the template top left corner on the anchor,
        "anchor_br": tuple: two int — coordinate of the template bottom right corner on the anchor,
        "target_tl": tuple: two int — coordinate corresponding to anchor_tl on target,
        "target_br": tuple: two int — coordinate corresponding to anchor_br on target,
        "anchor": str — name of the anchor cadastre\node,
        "target": str — name of the target cadastre\node
    }]
}

User guide

Matching flowchart.

The AlignemntTool service is provided as a jupyter notebook. It offers easily understandable ways to preprocess, match and recompose the cadastres, while requiring only low computational literacy.

The different steps are described in the notebook to guide the user during its use. Few considerations about the functionalities of the tool and the way they are meant to be used are reported in this section.

Preprocessing

AlignmentTool allows to preprocess the cadastres in two main ways. They can be reoriented using the bearing arrows potentially drawn on the cadastres, and renamed, which can be very convenient for further uses (eg. referring to them directly by their label during the matching process). Yet, in the context of this project the rescaling step was not included in the preprocessing pipeline. It could however be added with little efforts based on already developed functions.

These modifications can then be saved. Plus, edges can be computed through Canny edge detection in order to provide a coarse, but quick, denoising of the images. This can be used as a low-cost line detector.

Matching

The matching process (illustrated on the matching flowchart on the right) takes the form of a constant dialog between the user and the machine. First the user needs to establish discussion by entering the labels of the anchor and target cadastres. Both of them will then be displayed in the notebook. The anchor will lie on the left-hand side. The user must draw the bounding-box around the template to be used for TM on this image. The target cadastre is then displayed on the right-hand side and the user can select the area within which the TM process should occur. This selected area should be large enough to include completely the template and all its rotated version). A boolean parameter also allows to disable the rotations of the templates if the cadastres have already been correctly oriented. The best match found through TM is then displayed as the composition of both of the cadasters. The user must evaluate this match and tell to the algorithm if the match is satisfying, thus should be stored, or if it has to be discarded. This is an iterative process meant to be realised until completion of the studied area.

Visualisation

The results can be visualised within the notebook, either by printing the structure of the graph built during the process or, more graphically, by displaying the composition of a pair or more cadastres. Note that if several representations of the cadastres are available (eg. scans, edges, detected lines, etc.) all of them can be used by adjusting one parameter.

Saving and loading

Finally two functions provides handy ways to save/load the graphs obtained through the process in/from JSON format. The JSON as the architecture described above.

Case Study: La Rochelle 1811

La Rochelle fortifications' inner cadastres from 1811 have been selected to assess the usability and performances of the tool. In order to reduce the noise on the images, lines have been extracted from the cadastres (see here). These files have been renamed together with the initial cadastres (it took 1min30s from initialisation to saving), and TM has been performed on the predicted lines. Independently of the considered cadastres, 80 angles were tested, for each degree between -40 and 40. While this is quite computationally expensive, the computational time is mainly dominated by the display of the composition.

As a benchmark, details of the process are detailed in the table below. "Attempts" refers to the number of attempts before obtaining a satisfying match, "Time" is the corresponding time. * The total time also includes the initialisation and the post-matching visualisation of the whole area process.

								Total
Steps	A2→A1	B→A2	B→C	D→A1	E→D	C→F1	F1→F2	7
Attempts	1	1	1	2	1	1	1	8
Time	24"	30"	28"	46"	33"	37"	38"	4'44" *

Note however that these statistics were obtained thanks to previous knowledge of the cadastres. Few time was spent selecting adjacent cadastres or looking for overlapping areas. These figures might be much higher on first trials (in particular it would be really surprising to have such low number of attempts on a first investigation, resulting ultimately in more time spent).

The results from this process are exhibited below as the realignment of the eight considered cadastres. From a human perspective, the results obtained are mostly satisfying even thought there seems to be some incoherences around le havre and the quartier du Perrot (see here) in the bottom middle. Nonetheless this is also due to the quality of the cadastres that seem to disclose inconsistencies in scales around this neighbourhood.

Alignment of La Rochelle's 1811 Napoleonic cadastres.

These results can be reproduced by downloading the data folder LaRochelle_PoC from the shared Google Drive and putting it at the same root as the AlignmentTool repository. Then the network can be loaded, using the function presented in the last section of the notebook, and the map recomposed. Matches can also be recomputed in the section Matching of the notebook.

[ ] State where the data are stored
[ ] Describe the different steps
[x] Time the process
[x] Count the number of attempts before success for each match

Lines detection process

At this step of the project, the only data available were the digitised cadasters themselves, but no process such as lines or class detection had been done on them. As mentioned previously, our method uses the lines detection files to find homologous points. It was therefore needed to process the cadasters we wanted to reattach. This task was done thanks to pretrained models provided by the teaching assistants, models trained on four cadasters (Neuchâtel, Berney and Melotte from Lausanne and finally Venice).

dhSegment

dhSegment presents itself as a tool for Historical Document Processing. It can be used to recognise several types of elements in different digitised document types. It is based on a CNN-architecture.

Procedure

The first step was to slice each map in many parts. Indeed, because of their size, the algorithm was not able to process them all at once. Therefore, the maps were cut in 3x3 parts to reduce the computational cost (some of the maps even needed to be cut in 4x4). Each of these slices was then insert in the whole lines detection pipeline. Finally, the slices were reattached together (a much simpler task than reattaching different maps, as long as the slicing method was kept in memory and it was only needed to invert it).

Limitations and possible improvements

As long as this step was one of the last that had been implemented, it can only be considered as a first draft and a few improvements could have been made on it if more time had been available.

First, to make this first draft simpler, no overlap has been left between the slices of a map. As many tools of that type, dhSegment is known to have results of lower quality on the edge of the image. Adding an overlap between the slices could improve the sharpness of the line in junctions of the slices, even if no clear black line, or other problem of that type, can be seen on the actual obtained images.

The second possible upgrade of this method could be source of much greater enhancement than the first one. The problem we want to mention here is the fact that the maps have not been per-processed in order to remove all the non-map parts of the picture. The parts that could be removed in this step are text, map number or letter, compass rose, borders of paper, or all the white areas that were obviously crumpled by time and are now just source of noise for our pipeline. However, this is a purely manual work that could only be done with human selection on a software like Photoshop or GIMP. For that reason, it would unfortunately take way too much time to be performed in the context of this project.

Discussion and limitations

[ ] enlever cette section et bouger dans les parties correspondantes ?
- [ ] Lack of convincing metric / purely qualitative results
- [ ] Failing to automate the task
- [ ] No overlap between slices before line detection (to avoid border effects)
- [ ] No preprossesing of maps (ie cut the non-map parts)

Future Work

In the future, we would like to improve the AlignmentTool: its functionalities, for example integrating rescaling and scale-invariant matching and other homologous points retrieval methods, as well as its UI/UX to make it more user-friendly and less austere. The alignment reconstruction method should also be revisited in order to encompass the matches of every adjacent cadastres and possibly distort the representation accordingly. The images composition could also be boosted using other techniques such as bundle adjustment. Once the foundation of the map of large areas recovered, an algorithm enabling slight variations of individual cadastres could be implemented in order to iteratively correct the whole structure.

This tool could also be used to build ground truth datasets to investigate Machine Learning or Deep Learning approaches. It could also serve as a way for the machine to learn a metric of goodness of match by integrating the feedbacks from the users for both satisfying and discarded matches.

The automation should also be reconsidered by integrating more domain knowledge and heuristic considerations into traditional Machine Learning and Computer Vision approaches. Nonetheless, in order to meet the challenges of this task state-of-the-art Deep Learning methods would certainly need to be embraced. Exploration of such techniques have already shown solid results on similar tasks .

Finally, to ease further analyses, or even improve the alignment scheme, the cadastres should be georeferenced and diachronically aligned with contemporary maps (for instance present-day cadastres or OpenStreetMap).

- [ ] Tool roadmap
   - [ ] Integration of other matching methods
   - [ ] Integration of more automation (adjacent matching)
   - [ ] improve UX
   - [ ] Use tool annotation (also discarded matches) to learn better metric ?
- [ ] Taking into account matches from all adjacent cadastres and recursive adjustments 
   - [ ] eg. Bundle Adjustment
- [ ] Automation
   - [ ] more heuristic and domain knowledge — in traditional ML/CV methods
   - [ ] investigate "deeper" approaches => add some literature: eg.  
- [ ] Alignment on Openstreetmap