Shortest-Path Route Extraction From City Map

The Historical Document

Original map which forms the basis of the project. Note the distinction between already built sections (darker, south-west) and unfinished or planned sections (lighter, north-east).

We are working on a historical map of Manhattan, depicting mostly Lower Manhattan as well as some part to the north-east of that. The following is a compilation of some contextual information retrieved directly from within the map:

• self-designated as "Plan of the City of New-York"
• published in 1829
• in the English language
• As for the source material of the map, it is stated: "The greater part from actual survey made expressely for the purpose (the rest from authentic documents)"
• by Thomas H. Pappleton, City Surveyor
• published by Prior & Bowne
• revised, corrected by William Hooker

The map features a clear visual distinction between two sections. The first one, delimited to the north-east by North Street, Bowery, Eigth Street, Greenwich Lane, and Great Kill Road, is characterized by buildings drawn hatched, thus appearing darker. This is in constrast to the other section, where buildings are drawn more lightly, and in places superimposed over roads, that are drawn in a dashed style, or natural terrain features. The former section depicts built parts of the city, while the latter represents parts that are unfinished or only at a planning stage. While this interpretation is natural, it is not evident beyond doubt from the map itself which lacks a legend explaining the meaning of the different shadings of buildings. However, another map from around the same time (1836), which contains a broadly similar division, as well as a legend revealing the darker areas as "Section[s] of City built" and the lighter ones as either "Opened or being regulated" or "established by Ordinance", allowed us to draw this conclusion.

For the project, only the darker section on the map, corresponding to already built parts of the city, is used, while the rest is ignored.

Extraction methods

For the proposed application, the relevant information that needs to be extracted from the map is some usable representation of the road network. For this, the Python tool NEFI (Network Extraction From Images), developed at Max Planck Institut für Informatik, is used. The tool performs automated detection of networks in images based on the Guo-Hall thinning algorithm and outputs the extracted network as an undirected planar graph, stored in a text file. Intersections are the nodes of the graph in this representation, while roads are edges. Besides the fundamental graph extraction step, the tool also provides functionality for some basic image preprocessing before graph extraction, as well as some options for post-processing the extracted graph.

Simply running NEFI on the map image as it is, however, is not enough, to get satisfactory graph extraction results. In fact, for the application at hand, nothing less than an optimal graph is acceptable since a graph where edges and nodes do not accurately coincide with roads and intersections will be either unsuitable for direction-finding or at least visually displeasing when overlaying computed routes onto the map image. A desirable workflow for the whole graph extraction process might look like this:

• Crop the image, remove from the outset portions of the image that are irrelevant (in this case: margins, sea, sections corresponding to parts of the city not yet built), basic image preprocessing (e.g. contrast enhancing, blurring). While the latter could be achieved using NEFI's inbuilt preprocessing capabilities, these are fairly limited, so using an external program is likely advisable.
• Automated graph extraction using NEFI.
• Visually assessing and, as required, manually correcting inaccuracies in the graph extracted from the map. For this task, ideally, we would need a GUI tool that provides the possibility to overlay the graph onto the original map and, directly in this view, permits to manually define nodes and their connections in accordance with the underlying image.

Unfortunately, no such convenient way of correcting errors in the extracted graphs by means of a graphical editor was found. This leaves us with no option for correcting graph errors but editing directly the text file in some way, which is highly impractical. As a result, the preprocessing and cleaning of the image before graph extraction becomes all the more important. To get decent results, we had to resort to rather heavy preprocessing, manually segmenting the image into roads and inaccessible areas (i.e., coloring them black and white, respectively) using GIMP (Gnu Image Manipulation Program). Graph extraction using NEFI is then run on the manually segmented image. The pipeline that was specified in NEFI consists of the following steps, in that order:

• "Watershed DE Otsus" from category Segmentation, short for "Watershed with Dilation, Erosion and Otsu’s Threshold". Default settings are used.
• "Guo Hall Thinning" from category Thinning. This algorithm does not have any settings.
• "Guo Hall Graph Detection" from category Graph Detection. This algorithm does not have any settings.
• "Keep only LCC" from category Graph Filtering. This removes all but the longest connected component from the graph obtained. This algorithm does not have any settings.

We realize this approach is far from ideal, and not very efficient, since the manual segmentation in the preprocessing step actually amounts to (implicitly) doing a big part of the graph extraction by hand, but the indirect route via NEFI still has to be taken for the actual graph extraction. We nonetheless decided to stick to that approach, since it works in principle, and spending more time searching for a user-friendly tool for manual extraction and editing of graphs based on images was deemed not worthwhile. However, for future similar projects, it might be advisable to invest some time in researching, or even creating, such a tool. Having such a tool at one's disposal, one could either perform manual graph extraction conveniently, forgoing the indirect route via NEFI entirely, or cut down on the necessary preprocessing before the automated graph extraction via NEFI, since there would now be a feasible way of correcting errors afterwards.

Project Plan and Milestones

Note that, by design, this section is a snapshot of the project planning at an intermediary stage (as of November 14), and therefore might not accurately reflect all steps taken at later stages.

Our final goal is to create a simple Google-Maps-style navigation tool for the past. The user will be able to select two points, and see the shortest path between these two points. This would be a useful for someone to estimate how they would navigate through a city - possibly hundreds of years ago. Florian has been tasked with pre-processing the historical map. This involves searching for the best maps and cleaning them. Cleaning is crucial to ensure that an accurate graph is extracted from the map. Jonathan is working on representing the graph visually, creating interactivity, and hosting it on a website.

Already Completed

• Researched software that will help us with graph extraction

• Took the first steps to developing a cleaning process for each map

• Written Python code to display a graph from a text list of nodes and edges

• Completed simple routing between two nodes

• Setup a website and domain (www.dhproject.cf) to showcase our project

Future Goals

• Take a decision on which overall direction to pursue for the remainder of the project: Generality, by including several other maps? Or, adding selection of start and end point based on address input, to more closely mimic the interface and functionality of services like Google Maps? (November 23)

• Letting a user select two nodes on the map, and displaying the shortest path between the two nodes. (November 23)

• Displaying the interactive graph on the website. (November 23)

• Calculating and displaying the actual estimated distance between the two points. (end of November)

• Overlay the graph representation onto the historical map. (end of November)

• Develop a manual process for assessing how accurate graph extraction is, and correcting if necessary. (end of November)

• Some buffer time, to allow for unforeseen work. (December 1 to 9)

• Finish Wiki writing (December 12)

• Refine (and automate) the cleaning process. This may involve researching other maps and choosing the best ones for our needs. (no hard time frame, depending on feasibility and necessity)

• Possibly move the network extraction, which is currently done via GUI, to a script. (no hard time frame, depending on feasibility and necessity)

• (Stretch goal) Allow a user to upload their own map which will be processed and displayed.