Line Following
It is possible to express a line as an equation if its geometry is simple and can be defined by simple mathematics equation. Unfortunately, most lines in cartography applications have complex geometry. In addition, database queries in geographic information systems are mostly framed in terms of the coordinates of figures in the map. A curved cartographic line is then often expressed by a string of consecutive head-to-tail vectors. These vectors are normally retrieved using line following technique. It identifies the series of coordinates in the individual lines. This process would be complicate if the ending nodes of each line-string were unknown. Therefore node marking is a required preprocess for the line following.
Figure 3: Skeletons overlaid on the original scanned portion
One method to build up a vector by coordinates is to begin with the endpoints and then find coordinates of the individual lines between these two points. Hence, after lines are thinned, node detection is performed on every object pixel. The decision rule, whether or not a pixel is a node, is based on some characteristics of the 256 possible combinations the eight connected neighboring pixels. Firstly the number of object pixels in the eight neighbors, denoted as N (x), is introduced. The number of object pixel to background pixel transitions in the eight neighbors cyclically, denoted as T(x), is also employed in this rule. Actually there are three types of node pixel. They are the isolated node, the junction node, and the terminated node. Generally, the isolated nodes are black spots in an image. Only the terminated nodes and the junction nodes may be the ending points of the line-string. It should be noted that a junction node may be the ending points of several line-strings. If the pixel of interest is denoted by x, the following rules are applied.
1. If N (x) = 0, x is an isolated node.
2. If N (x) < 3 and T (x) = 2, x is a terminated node.
3. If N (x) > 2 and T(x) = 2, x is a junction node.
4. If T (x) > 5, x is a junction node.
Once the coordinates of all nodes are obtained, the line following may simply launch. From the node list, the first node is retrieved and the line string of this node is then tracked until the other end is reached. The process is iterative for the entire node list. An ambiguity can occur when a line intersection is met. In this research, a decision is automatically made which direction to follow.
Figure 4: A portion of the scanned contour map
