Feature Extraction from 1:24K Scale Digital Raster Graphics(DRG's) Using Fuzzy Logic

Digital Raster Graphics that are developed from USGS 1:24k scale quadrangles contain enormous amounts of accurate geographic information. Many of the features they contain, such as hydrography networks, are potentially useful as data inputs to wildlife models, but are not in usable digital form. We have developed a fuzzy-logic algorithm for extracting hydrographic features from topographic maps with extremely promising results. This algorithm needs to be expanded to include ensembles of various fuzzy classifiers, documented and assessed for accuracy.

When a human being views a scene or image, the brain considers multiple simultaneous factors to differentiate and comprehend objects. The mind considers physical qualities such as shape and size, spectral information such as tone or hue, and spatial information including pattern, frequency, geographic location, and association with other objects (Lillesand and Kiefer, pp 115-116). Raster data, or image data such as aerial photography or remotely sensed data, is a two dimensional representation of the three dimensional real world. Each object is flattened and merged together to form the two dimensional raster. While the human mind can interpret these images, automated computer analysis is more difficult.

Topographic maps are a complex representation of multiple levels of geographic information which contain enormous amounts of information. Producing the maps so that humans can understand them is as much an art form as a scientific endeavor. Topographic maps produced by the United States Geological Survey (USGS) are converted to Digital Raster Graphics (DRGs) for computer use by scanning and georeferencing the original paper maps, which are usually hand drawn. The human mind, again, has no problem understanding the images when viewed on a computer. However, these data are two dimensional and features are not easily separable from one another except using human perceptions of connectivity and association. Pixels are laid together on a single plane, connected only by spectral and spatial patterns that a human viewer may perceive.

Hydrography networks are important features that are mapped in DRGs. At normal viewing distance, a given stream may appear as an unimpeded line of blue pixels moving from point A to point B. When this area is examined at close range, it can be seen that the representation of the stream is actually interspersed with many gaps resulting from the imposition of another feature (such as contour lines or boundaries), imperfect drawing by the original cartographer, a natural bleeding of colors during creation, or color alteration during scanning. As a result it is difficult to incorporate DRGs as inputs to automated geographic information system (GIS) analyses or wildlife models. Hydrography layers are available nationwide at the 1:100k scale, but not in the finer detail of 1:24k DRGs necessary for many habitat models. We need a method that quickly, reliably, and cheaply extracts features from these highly accurate maps.

There are a number of methods currently used for extracting features from DRGs. The usual method of extracting features from DRGs involves manually digitizing vector layers with the DRG as a backdrop or guide. This method is time consuming, surprisingly inaccurate and therefore not feasible for large-scale projects or those which require high levels of accuracy. Another method of extracting information from digital images is the use of traditional computer image processing and classification programs. However, most image processing algorithms either consider only color values of a single pixel, or operate on continuous values and therefore do not handle the discreet values of thematic DRG images correctly.

The alternative technique used here for extracting features from simple thematic imagery incorporates recent advances in understanding human perception through cognitive psychology (Kosko). This scalable method, formally known as fuzzy logic or soft computing, is a powerful tool for image processing within medical fields, especially when combined with the methodologies of machine learning and traditional image processing techniques (Tizhoosh). Literature reviews suggest, however, that little or no valuable research has been done in applying and extending this technology to the geoinformatics sciences for feature extraction or computer vision.

The algorithm we have developed expands on traditional image analysis techniques by incorporating soft computing and machine learning with traditional vector and raster processing techniques. Opitz has shown that machine learning techniques are useful for extracting features from raster data, especially when combined with hierarchical methods (Opitz et al.). The methods proposed by Opitz, however, are dependent on continuous values and do not scale to thematic imagery, such as DRGs. Our method is designed to work equally well on both continuous values and also thematic imagery.

Our initial results demonstrate that accurate inferences can be made and features can be accurately extracted from thematic raster data. The algorithm is capable of quickly producing an accurate line representation of streams and small rivers at a 1:24k scale. Initial testing has been performed on 250 DRGs within six subbasins of central Washington. While our method is resistant to errors caused by noise and artifacts in the data set as well as missing data, there is still a good deal of hand editing that must be performed.

We propose to develop our soft computing extraction process such that 1:24k scale hydrography layers can be reliably produced in an automated fashion through a graphical user interface, including flow direction and stream flow enumeration. This will be accomplished by (1) adding weighted voting by an ensemble of various types of fuzzy learners to our algorithm, (2) providing an easy-to-use graphical front end, (3) performing an accuracy assessment, and (4) documenting and publishing the process and results.

Various ensemble methods boost the accuracy of an individual learner's prediction by applying the rule that many opinions are better than one opinion. When applied to our technique, ensembles of various types of fuzzy learners will classify based on the weighted votes of all learners. This will reduce errors of omission and commission by allowing each learner to error in different areas of the input set and will allow the system to understand increasingly complex concepts of DRG features.

Providing an intuitive graphical user interface will enable the user to use the software with little or no training. As our technique utilizes the functionality of several GIS-based functions to perform post processing tasks, a graphical user interface will provide the user with a seamless, transparent interface to the underlying task.

The accuracy levels of stream extraction are difficult to quantify. Our extraction process requires two stages: the automated stage, in which all tasks are performed by the computer, and the manual stage, where finishing edits are performed by an analyst. The assessment method proposed here is a statistical comparison of the raw output of the automated stage and the finished hydrography layer from the manual stage.

References

Kosko B. Fuzzy Thinking: The New Science of Fuzzy Logic. Hyperion, New York, NY, 1994.

Lillesand T. M. Kiefer R. W. . Remote Sensing and Image Interpretation SE. Whiley and Sons, New York, NY 1987

Opitz D. Mangrich M. Mason S. C. .Feature Extraction from Digital Imagery, A Hierachical Method. In IASTED Conference on Visual Imagery and Image Processing, 2001.

Schapire R. E.. The boosting approach to machine learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, 2002.

Tizhoosh H. R.. Fuzzy Image Processing. Springer-Verlag, Heidelberg, Germany. Oct, 1997.

Principal Investigator	Roland L. Redmond
Senior Image Analyst	J. Chris Winne
Chief Research Programmer	Shane C. Mason
Cartographer	Jim Schumacher