Shortest-Path Route Extraction From City Map: Difference between revisions
No edit summary |
|||
| Line 2: | Line 2: | ||
[[File:Manhattan-1829_base-map.jpg|300px|right|thumb|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).]] | [[File:Manhattan-1829_base-map.jpg|300px|right|thumb|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 | We are working on a historical map of Manhattan, depicting mostly Lower Manhattan as well as some part to the north-east side. 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 | ||
* | * Source material of the map states: "The greater part from actual survey made expressly for the purpose (the rest from authentic documents)" | ||
* | * By Thomas H. Pappleton, City Surveyor | ||
* | * Published by Prior & Bowne | ||
* | * Revised and 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, | The map features a clear visual distinction between two sections. The first one, delimited to the north-east by North Street, Bowery, Eighth Street, Greenwich Lane, and Great Kill Road, is characterized by buildings drawn shaded-in. This is in contrast to the other section, where buildings are drawn more lightly. Places that are superimposed over roads are drawn in a dashed style. The former section depicts parts of the city that are already built, 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) what the meaning of the different shadings of the buildings is. However, another map<ref name="map_1836" /> from around the same time (1836), allowed us to draw this conclusion. This other map 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". | ||
For the project, only the darker section on the map, corresponding to already built parts of the city, is used | For the project, only the darker section on the map, corresponding to already built parts of the city, is used - the rest is ignored. | ||
== Extraction methods == | == Extraction methods == | ||
For the proposed application, the relevant information that needs to be extracted from the map is | For the proposed application, the relevant information that needs to be extracted from the map is a usable representation of the road network. For this, the Python tool [http://nefi.mpi-inf.mpg.de NEFI]<ref name="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<ref name="Guo-Hall" /> 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. | ||
However, simply running NEFI on the map image as it 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. enhance contrast, blur). While the latter could be achieved using NEFI's inbuilt preprocessing capabilities, these are fairly limited, so using an external program is likely advisable. | * 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. enhance contrast, blur). 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. | * 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, | * 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, permit manual editing of 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<ref name="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 | 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<ref name="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 ordered steps: | ||
* "Watershed DE Otsus" from category ''Segmentation'', short for "Watershed with Dilation, Erosion and Otsu’s Threshold". Default settings are used. | * "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 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. | * "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 | * "Keep only LCC" from category ''Graph Filtering''. This removes all but the longest connected components 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 | 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 perform manual graph extraction conveniently: forgoing the indirect route via NEFI entirely. You could also 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. | ||
Additionally, the manual segmentation during the preprocessing inevitably introduces some human-input-related ambiguity. However, this is not inherently different from the ambiguity that would arise in direct manual graph extraction or the ambiguity involved with assessing the accuracy of an extracted graph | Additionally, the manual segmentation during the preprocessing inevitably introduces some human-input-related ambiguity. However, this is not inherently different from the ambiguity that would arise in direct manual graph extraction or the ambiguity involved with assessing the accuracy of an extracted graph. Some degree of ambiguity of this type therefore seems unavoidable. | ||
== Project Plan and Milestones == | == Project Plan and Milestones == | ||
Revision as of 09:53, 5 December 2018
The Historical Document
We are working on a historical map of Manhattan, depicting mostly Lower Manhattan as well as some part to the north-east side. 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
- Source material of the map states: "The greater part from actual survey made expressly for the purpose (the rest from authentic documents)"
- By Thomas H. Pappleton, City Surveyor
- Published by Prior & Bowne
- Revised and 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, Eighth Street, Greenwich Lane, and Great Kill Road, is characterized by buildings drawn shaded-in. This is in contrast to the other section, where buildings are drawn more lightly. Places that are superimposed over roads are drawn in a dashed style. The former section depicts parts of the city that are already built, 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) what the meaning of the different shadings of the buildings is. However, another map[1] from around the same time (1836), allowed us to draw this conclusion. This other map 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".
For the project, only the darker section on the map, corresponding to already built parts of the city, is used - the rest is ignored.
Extraction methods
For the proposed application, the relevant information that needs to be extracted from the map is a usable representation of the road network. For this, the Python tool NEFI[2] (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[3] 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.
However, simply running NEFI on the map image as it 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. enhance contrast, blur). 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, permit manual editing of 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[4] (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 ordered steps:
- "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 components 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 perform manual graph extraction conveniently: forgoing the indirect route via NEFI entirely. You could also 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.
Additionally, the manual segmentation during the preprocessing inevitably introduces some human-input-related ambiguity. However, this is not inherently different from the ambiguity that would arise in direct manual graph extraction or the ambiguity involved with assessing the accuracy of an extracted graph. Some degree of ambiguity of this type therefore seems unavoidable.
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
- 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.
References
- ↑ https://www.loc.gov/item/2007627512/
- ↑ 2.0 2.1 Dirnberger, M. and Kehl, T. and Neumann, A., "NEFI: Network Extraction From Images", Scientific Reports, 5 (2015), http://dx.doi.org/10.1038/srep15669
- ↑ Guo, Zicheng & W. Hall, Richard. "Parallel thinning with two-subiteration algorithms". Communications of the ACM 32 (1989), 359-373. http://doi.acm.org/10.1145/62065.62074
- ↑ https://www.gimp.org/