Binary Digital Image Processing

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.