Graph representation of line networks

An abstract representation of the studied features allows us to only keep the relevant information for the tackled problem.

A graph $G=\{X,U\}$ is defined by:

• a set X of nodes.
• a set U of edges.
• Eventually a third set  A  which represents the attributes corresponding to each node.

For our problem:
 

on cartographic data:
 

X : set of road segments
U : edge between connected segments
A : length, orientation, localization (for the first step)

on image data:
 

X : 1st step: road pixels,  3rd step: chains of road pixels
U : 1st step: neighbor pixels (8 connectivity), 3rd step: connected chains
A : 1st step: localization, 3rd step: length, orientation

November 1998