Keywords: Line tracking, Line extraction, Skeletonization
Abstract Line is often regarded as one of the most valuable features in a map. Cartographic line tracking tools found in most commercial software typically are semi-automated process. This research studied and purposed an automatic method. It consists of line thinning, and line following steps. The algorithm has been examined using several scanned contour maps. An experimental result is also included herein.
Introduction
The simplest and perhaps the most useful feature in a map is line. This feature contains some essential structural information which is useful for further analysis. Although the line extraction process requires basic understanding of computer vision, many researchers in cartography have tried to study and applied them to their own discipline. Some researchers are interested in detecting lines directly from an original image (Apaphant and Bethel, 2000), while the others concentrate in tracking this feature from a line image. Except for extracting important information from an image, one of their common goals is to reduce memory space. Recently, there are many line tracking tools available in commercial GIS software. However they are semi-automatic process which can be tardy and expensive. Some tools even create artifacts. Hence the automation of the process can definitely bring considerable benefits to users of GIS system.
To track lines in a line image, two basic steps, i.e., skeletonization and line following, are required. Some research have emphasized developments only on the individual steps. Skeletonization is the process that reduces thick lines into single pixel wide lines. All 256 possible surrounding conditions for the pixel of interest were employed for decision-making of line thinning (Cohan and Landy, 1985). Nevertheless, their methods produced poor results in some specific cases. The medial axis method detected skeletons based on the maximum distance from all edges of the original line (Peuquet, 1981). This method could not be assured that the information of the original medial axis is always held. Line following is the process that identifies the series of coordinates in each individual thinned line. It is categorized into two approaches (Rosenfeld and Kak, 1982). The scan-line based method search for an object by scanning either row-by-row basis or column-by-column basis (Peuquet, 1981). The object-based method typically first detected endpoints of lines (Greenlee, 1987)(Moore, 1992). The individual objects are then followed from the beginning node of the objects through the ending node of the objects. Motivated by these problems, an automated line tracking is proposed in this paper. This method improves and assembles the two basic steps into one suite, without human intervention.
Skeletonization
Thinning , also called Skeletonization, is the process that reduces thick lines into lines with single pixel thickness. It reduces data to be stored while brings out the structure of the pattern. The remaining pixels of each object form a line-string on the medial line of the original object. Since there are many possible applications of thinning, it is difficult to design criteria that will satisfy all applications. In cartography and GIS applications, two criteria are often required. Firstly, the removal must not change continuity of an original objects. This means that the removal operator must not create any discontinuity or holes. Secondly, the shape of an object must be preserved. However, due to the flawed computer decision during thinning, some small holes may be created. This problem can be addressed by a procedure so called Gap filling. It searches for the pixels which appear to be gaps and replaces them with object pixels. For the sake of completeness, this thinning algorithm is therefore itemized into two steps which are, thinning and gap filling.
Figure 1: North border segments (N)
The proposed algorithm is based on the peeling approach. The thickness of a line is reduced by one unit at a time on each border of an object until its skeleton remains. We first define a border point of an object as a point whose adjacent point in its eight neighbors is not an object point. We divide the border points into four types i.e., north, south, west, and east borders. For instance the object points with character "N" in Figure 1 are the north border points. Another terminology often employed in this thinning algorithm is an obese point. A point, p, is a candidate for an obese if originally there is only one region adjacent to p based on the four neighboring definition. If point p is removed and that one region is still preserved then the p is called an obese point. This thinning process begins with iteratively deleting only the boundary segments which are obese points, on the north, south, east, and west borders consecutively. For example, in the first iteration, all north border points categorized as obese points are marked for deletion and then simultaneously removed for the entire image. After that, the thinned image and the original one are compared pixel by pixel for the entire image. If they are exactly the same, the iteration is stopped and the skeleton is obtained from the result of this pass. Otherwise the original image is updated. And the updated image is thinned along the south border and then compared. If the thinning process is still required, the same procedure performs on the east and west directions consecutively. After the updating, if the skeleton image is still not received, the next iteration is then continued with the same procedure. The iteration should stop when there are no further deletions. Note that change of thinning order may cause slightly different on the final result. Figure 2 illustrates the thinning procedure. Figure 2B is the output from thinning the north obese segments of the original one (Figure 2A). Figure 2C is the thinning result after the first iteration. And Figure 2D is the skeletons.
The point removal process may create small gaps in some places. To preserve the continuity of the lines, these gaps must be filled. They are converted to object points, if found. A general problem which often occurs in other algorithms is bridging between adjacent object. It is taken care in this study by not allowing gaps between parallel lines to be filled. It can be noticed that this proposed algorithm produces the reducing object pixels systematically. Using this approach, the number of iterations for thinning an object is approximately on half of the objects thickness measured in pixel units. The resulting figure should be a line drawing retaining continuity and shape information of the original one. These thinned lines are spatially placed along the medial regions of the original objects. They therefore conform closely to the original but thinner (Figure 3).
 |
| (A) |
(B) |
 |
| (C) |
(D) |
Figure 2:Thinning procedure
