226 BINARY DIGITAL IMAGE PROCESSING
8.2 Road map image
We now show how a similar analysis can be operated on the image of a
transportation network. Consider the 230z230 bitmap of the line image pre-
sented in Figure 8.6.
Figure 8.6 Image "Road map": bitmap
The upper -level structure of this image is retrieved as follows. Two points
are characterised as extremities of the shortest path of largest length within the
grid graph of the image. The set of all possible k-shortest paths between these
two points will visit the complete network, excluding branches leading to "free
ends". By dismissing these paths and re-iterating the procedure, all central
paths within the image are characterised. Their junctions and end points form
the vertices of the upper-level graph. Such a graph is shown in Figure 8.7.
For this application, the connectivity between vertices of the upper-level
graph is important for finding a route between two given points within the image.
It is therefore the structure in which the image will be stored for further analysis.
By defining a centrality weight for each arc in the grid graph, the set of maximum
weighted paths between the pairs of vertices representing the arcs of the upper-
level graph will form the skeleton, as shown in Figure 8.8.
This application highlights the advantage of using graph theory as an ap-
proach for defining the skeleton since, at this stage, measuring the length (and
other characteristics such as curvature) of each skeleton branch is straightfor-
ward. Such characteristics, associated with arcs in the upper-level graph, now
form the basis for an automated route planning system.