IMaG: Integrated Vector and Raster GIS and Image Processing Using An Expert System Approach

Overview

From a very fundamental data representation and analysis perspective, GIS/Remote Sensing attempts to resolve information extraction issues from a complex and unconventional data matrix as shown in the following schematic diagram. (Figure 1)

In Figure 1, Column 1 contains a region identification number or code. A region could be a census track #100 in a city determined by the political boundary system set by the U.S. Census Bureau. Column 2 contains (x,y) coordinate data for the centroid of each region, such as row 20 and column 65. Column 3 contains four (x,y) coordinate data points that form a rectangle to enclose the corresponding region, such as census track #100. Column 4 contains pixels inside each corresponding region. In addition, each pixel is described in terms of its location (x,y coordinates) and the spectral signature of that particular pixel. Spectral signature is defined by a set of electromagnetic radiation readings generated from one or more sensors. For example, a region is defined in terms of a vegetated area that is composed of 1000 pixels, each representing one square meter of land. If the image source is derived from a black/white photograph, the vegetation pixels will be relatively dark as compared to areas occupied by sand or concrete. The graytone level of the vegetation region can be interpreted as a type of spectral signature. Column 5 contains data that describe the boundary contour of each region; within the boundary are interior pixels represented by Column 4. For example, assume that the above-discussed vegetation region contains 1000 pixels, the outermost pixels of these 1000 pixels separating the vegetation region from its background such as a grass area constitute the boundary contour of the vegetation region. In general, Column 4 data are called raster representation, whereas, Column 5 data are designated as vector representation of a region. Within the subject of vector representation, there exist a number of ways by which a boundary contour is represented. For example the chain code; it uses numerous boundary pixels as one approach, and a topological structure of polygons that uses nodes and relational information as another.

The data in Columns 6 through k are generally called an attribute table or a DBF, database file. Here, each column represents one region descriptor, such as average income or number of persons with age greater than 60, and so on. If one combines data in Column 1 and in Column 6 through k, one yields essentially the information contained in the U.S. Census Bureau generated TIGER File. Many conventional GIS analyses are based on the TIGER file or similar data.

The science and technology for dealing with data in Columns k+1 through n in Figure 1 belong to remote sensing and image processing. With image data, the location of the boundary of a region is highly dependent on the sensor type and the resolution of the data. For example, a dirt road surrounded by grass with exposed soil can be easily extracted from an image generated from the red spectral region. The same road, however, may not be visible in an image generated from the near infrared spectral region. The same phenomenon exists in extracting a road using high resolution imagery vs. using low resolution imagery. For example, using the same red-band image, the road can be extracted easily; however, it is difficult to perform the same task using the same image source with a very low-resolution scene. Since a political boundary, like the census track is permanent, whereas, its counterpart in the image domain is variable, we create Column (n+1) for image data based on Region ID to contrast against the Column 1 data designated as political boundary based regions, such as the TIGER file.

From this data model perspective, one can extract two general types of GIS analysis. The first type uses fixed political boundaries to create regions, and second type uses image data determined boundaries to create regions. If one designates the process by which a region is created as Segmentation, the first type of GIS does not requires segmentation, whereas, the second type of GIS is highly dependent on segmentation results. On the other hand, if one selects to use a manual method to perform image data based segmentation, the second-type GIS may resemble the first type. However, an unresolved issue is how to generate an attribute table for these hand-segmented regions. For example, with a hand-segmentation method, one uses a polygon to enclose a vegetated area, and another polygon to define a cultivated field. Then, how does one characterize these two hand-segmented regions using Tone, Texture and Shape attributes. It would be absurd for one to perform manually-based tone, texture, and shape analyses using remote sensing data even through region boundaries are given. For example, would one enumerate all the 1000 pixels in the above-discussed vegetation region by hand, and compute the average of the greytone level using a calculator? Therefore, a semi-automated analysis is acceptable, and a totally automated approach is a much preferred option.

In this paper, we would discuss how the SRE's IMaG system achieves integration between GIS and Remote Sensing on one hand, and vector and raster processing on the other using an expert system (shell) language. In the process of performing system integration, we also resolve the above-discussed issues on how to integrate the first-type and the second-type GIS analysis. In the end, we have developed expert systems by which information is extracted from various primary remote sensing based data sources, and then converted into a spatial database consistent with the data model presented in Figure 1. With these expert systems, one will be able to extract meaningful information through the process of inter-column and inter-row communication among the data cells in the data matrix of Figure 1, and use it to aid the decision makers in making correct and timely environmental management decisions. For example, one can extract three or more block groups that are contiguous and have both a high percentage of baby population and high percentage of teenage population , and designate them in whole as a neighborhood. Here contiguous block groups are extracted through a process of inter-row and inter-column communication, whereas, combining multiple socio-economic attributes is achieved through inter-column communication. Once such areas with distinct socio-economic and demographic characteristics are identified, the city planners can design a strategy to deliver the needed services to these "targeted" areas.

Introduction

"In a sense, the great majority of the data contained in digital, spatial databases is derived from remote sensing. The derivation is indirect since most data are captured by digitization (either manual or automatic) from map documents which are, in turn, frequently derived from photogrammetric processing of aerial photography. However, the direct utilization of remote sensing inputs (especially those based on orbital sensors) is found in only a limited number of cases at present."

The strength of image processing lies in using a set of well-established digital processing methods to extract information directly from digital images of various sensor-based sources with minimal human intervention and manual digitization. In general, the weakness of conventional image processing is resolving spatial relationships among defined objects. Therefore, it is advantageous to integrate remote sensing/image processing with GIS by using the following approaches:

1. to perform certain image processing functions in the vector domain;
2. to perform some or all GIS functions in the raster domain;
3. to perform raster-to-vector and vector-to-raster conversion without losing information in the process.

Expert System as the IMaG System Integrator

A Fifth Generation Programming Language

Figure 2. A Four Ring Structure of the IMaG Information Processing Environment

Programming Language and Environment as a Means for System Integration

Ring 1: IMaG Processors and Functions that contain these subsections:

Bands = 2;
Band 2 = (:1: > 140) * 250;
Band 3 = :1: + :2:;

Block #2: Initial Segmentation and Subsequent Region Merging. For example, we wrote this two-line code first to perform initial segmentation, and then a one-pass region merging:

Initial Cutoff = 50 percent;
(if Initial Cutoff = 5, Merge 1 = INIT; Merge 1 = 5 also)

Using a cutoff value of 5, neighboring pixels will be merged together if the contrast (absolute difference between them in intensity value) is less than 5. After initial segmentation, various regions are formed, each having a specific average tone value. Two neighboring regions will be merged together if their contrast represented by the absolute difference in mean tones is less than 5.

It should be pointed out that numerous programming options can be constructed to force neighboring regions to merge and become a uniform field by using tone, size and shape criteria. Since merger is done by removing the edge values from neighboring regions, the functions to perform this task are called general penalty functions. After segmentation analysis is completed, IMaG generates a database for the user to perform object extraction using a language style similar to a Standard Query Language (SQL).

Block #3: Object Extraction. For example, we would like to extract a car on a highway given that the road, and man-made objects (small buildings and cars) have been segmented. Each of the regions, road, small building, and car, is described by a set of attributes such as Size, Tone, Linearity, Texture, Elongation, etc. Given the above information, one can use the following code to perform "car" extraction:

Seek Bright Small BrightSmall;
Region Bright: [#2 Tone 2 = (200 250)] ;
Region Small : [#2 Size 1 = ( 1 50)] ;
Region SmallBright: [is Small] [touches Bright] ;

While the object "SmallBright" extraction program contains only three lines of code, this program teaches a user to use a simple tree-structure based strategy to define an object. For example, we define Bright and Small first, and then define SmallBright as a combination of the above. While IMaG itself may choose its own solution, such as backward chaining, the user is recommended to think and program in terms of a "forward chaining"style to achieve simplicity and clarity in object extraction tasks.

Block #4: Display and Data Output: For example,

Display Bright= red Small=cyan SmallBright=yellow;
File Display Bright=red Small=cyan SmallBright=yellow;
#2 Segmentation File 1 = DBASE;

IMaG.exe Expert System Name Infiles band1 band2 --- Outfiles file1 file2 ----

Ring 2: Expert System Language as a special means for integrating GIS with Remote Sensing:

It has been noted above that this statement:

Band k = Segmentation;

# i Segmentation File j = Segmentation

A typical GIS database can be represented by the following table:

Figure 3:  An Symbolic Representation of a GIS Database

     Column #1      Column #2       Column #3          Column # n+1 
------------------------------------------------------------------------
     Region ID     Attribute 1    Attribute 2		Attribute n 
          1           f11      		f12                 f1n       
          2           f12    		f22                 f2n       
          k           f21    		fk2                 fkn       
(Census Track #)  (Income)  	   (Age Category)    (Education Level)
------------------------------------------------------------------------
Internal			Attributes of each 
Segmentation Map		segmented region

As explained above the column #1 data are represented by a 32-bit image, and the totality of the table in Figure 3 is called an attribute table. To extract the information from this attribute table and correlate it against its counterpart in the 32-bit image domain, one follows the following rules:

1. the 32-bit base map based image is identified as "phantom" image using this syntax:

   BANDS = 2; (as an example)
   PHANTOM BAND 2 = SEGMENTATION;
   

2. extracting the attribute information using the EXTERNAL VARIABLE ... END EXTERNAL statement;

3. defining singe objects using SEEK and REGION statements as usual;

4. defining multiple attribute objects using a series of [is object] statements

5. the attributes are defined using the following format

EXTERNAL VARIABLES;
SEGMENTATION BAND 2 NUMBER "baby" = "P0110001" IN "bingage.DBF";
END EXTERNAL VARIABLES;
Seek Hibaby;
Region Hibaby : [EXTRN "baby" = (20 999999) ] ;
DISPLAY Hibaby=magenta;

The above programming language setting allows one to perform conventional GIS analysis in the IMaG environment. In addition to having "instant" GIS analysis result, one is allowed to perform a number of data analysis functions that are extremely difficult to do using a vector GIS based system. For example, one would like to extract a neighborhood that contains three or more contiguous "Hibaby" regions. This task puts an additional constraint on the topological conditions among neighboring regions. With IMaG, one can accomplish this task by using a function called "subregions" because this function allows one to count how many contiguous subregions were there before they were merged together to form a uniform field (one pass later).

Another example of constrained GIS is to merge map data with image data, such as using the SPOTview satellite image data to update roads on an out-dated map. Here, IMaG will treat a map as if it is an image, therefore, any correlation, or lack of, between these two layers of information is performed efficiently and effectively. In this case, all the roads are extracted from the SPOT data first, and then designated as a distinct layer or coverage. Second, all the roads on the map are extracted and designated as another distinct layer. A constrained GIS analysis aimed at detecting the existence of new roads by means a digital overlay analysis is performed using these two newly-created layers: road layer from the SPOT imagery, and the road layer from the old map. The key words in IMaG kernel for executing spatial overlays include "touches," "surrounded" and so on. If one defines No Change as "roads" in the SPOT data layer that "touches" their counterparts in the map data domain, "new roads" are those that do not touch the map-based roads. Additional examples using these key words will be given in the following sections.

Ring 3: Input Data Files with a script format

1. the name of the IMaG executable program,
2. the name of the expert system that contains the rule set used to perform various designated tasks,
3. Infiles, and
4. Outfiles.

Ring 4: Output Files capable of Interacting with the IMaG Program and Input Files

1. the results from the analysis,
2. full scene based region characterization using a 32-bit image and a corresponding attribute table, and
3. the expert system stored in a text file.

One of the most distinct features of the IMaG system is the preservation of knowledge from the expert who had developed the rule set. In addition, the rule set can be modified, expanded and compiled in real time when such action is necessary.

Finally, with IMaG the output files can be used as input files as additional layers to the original input files. This process can be achieved either within the expert system itself or by performing another IMaG analysis that combines the output files of the previous process with the input files of the current process. It is our experience that the latter option is rarely needed.

Robustness of IMaG: Applications Scenarios with Various Data Sources

Robust Rule Set based on Human Visual Analysis and Physical Models

Seek Road Small PossibleCar;
Region Road: [#2 linearity 1= (8500 10000)] ;
Region Small: [#2 Size 2 = ( 1 10 ) ] ;
Region PossibleCar : [ is Small ] [ surrounded Road ] ;

The above rule set is robust because each rule is based on a well-established logical or physical reality model. In general, the IMaG environment influences or forces the analyst to develop robust expert systems. In many cases, inferior expert systems are not allowed to exist simply because IMaG does not provide an environment in which "ad hoc" based algorithms can be easily developed, although if one would intentionally develop nonsense expert systems, IMaG cannot prevent this from happening.

Robust Expert Systems based on Scene Content Determined Segmentation

To resolve the above-noted segmentation issue, IMaG provides the user with a segmenter that is highly dependent on the content of the scene rather than ad hoc rules such as arbitrary thresholding parameters. In general, one can automatically set an initial cutoff for the initial segmentation analysis, and a scene-content-determined, iterative segmentation scheme to perform subsequent region merging process. The segmentation process will automatically stop when the scene structure reaches a stable structure point which is mathematically determined by this criterion: segmentation stops when the slope change value on a scene characteristics curve is greater than zero. For example, in IMaG one is allowed to perform a stable structure segmentation using the following code because the key word "STOP1" is designed as one-pass beyond the stable structure point:

Initial Cutoff = 50 percent; (as an example)
Merge = 40, 1 STOP1 - 1;

Robust Algorithms as Evidenced from Test Against Various Image Data Sources

a. Case Studies with LANDSAT TM Data

LANDSAT TM data have seven channels with a resolution level of 30 by 30 meters per pixel except the thermal channel, Band 6. While one can usually perform object extraction by means of a pixel based spectral analysis, segmentation analysis plus a spatial analysis can improve the performance of the classifier. The performance of the IMaG system has been proven effective when a segmentation based analysis is necessary to aid the user in extracting objects in a relatively complex environment.

b. Case Studies with High-resolution Multispectral, M-7, Data

The M-7 data set has 16 multispectral channels with a resolution level of 1 by 1 meter per pixel. At this resolution level, a segmentation analysis is usually needed to partition the scene into logical regions. This is particularly true with respect to the UV band for extracting man-made objects.

c. Case Studies with High-resolution Panchromatic Image Data

High resolution panchromatic image data are usually derived from aerial photography. The resolution level can be set at the 1-meter level or higher depending on the densitometer scanning aperture. We have processed a number of subscenes extracted from a test site located in San Jose, CA. The results indicate that IMaG is extremely effective as a preprocessor to a rule-based, expert system based classifier because the segmenter is capable of extracting the boundary of an object with a precision comparable to a human analyst. The segmenter based solution can be considered as a better solution because human-based solutions are subject to individual difference and thus unstable.

d. Case Studies with Synthetic Aperture Radar Data

We have conducted experiments with high-resolution SAR image data, and obtained results indicating that IMaG treats SAR images like ordinary panchromatic images; therefore, no modifications on the segmenter are needed for SAR-based object extraction.

e. Case Studies with High and Low Resolution Thermal Image Data

We have processed an enormous amount of thermal image data and can conclude that the IMaG segmenter is extremely powerful for extracting objects in the thermal domain. In many cases, the objects exist in a form of spatial clustering rather than a uniform field. In this case, one more step of segmentation analysis is needed to merge each individual clustering of small regions into a uniform field. The number of regions prior to becoming a uniform field is a mesotexture measure of that particular object. A complex region is defined as one that has two or more subregions. In IMaG one can use this "subregions" measure to define an object of a complex nature. This approach is also applicable to extracting objects from high-resolution panchromatic images.

f. Map Feature Extraction Using U.S.G.S. Digital Raster Graphic (DRG) Data

The United States Geographical Survey (U.S.G.S.) has converted some of its topographic maps into digital images. This product is called Digital Raster Graphic (DRG). While in its original form a DRG is a color image, it can be easily converted into an 8-bit panchromatic image, each of the 256 integers representing a specific color. For example, black is represented by 0, and red is represented by 95 or 94. On a topomap, one of the major highways is symbolized by alternating black and red bars. In this case, one needs to use both colors and the spatial relationships between colored bars to recognize a major highway. With six map features for testing, we have proven that IMaG is equipped with sufficient pattern recognition and spatial analysis functions for one to extract map features from DRG data with very insignificant error of omission and error of commission.

g. Automatic Feature Extraction with Digital Orthophoto Quad (DOQ)

Along with DRG's, the U.S.G.S. produces digital orthophoto images called Digital Orthophoto Quad (DOQ) for map updating. While currently the primary use of the DOQ's is for operator-based map updating using interactive graphic methods, we have empirical evidence to show that certain terrain features like forested regions can be successfully extracted by IMaG with a high degree of accuracy.

Generalization from Multispectral Analysis to Hyperspectral Analysis using A Combined GIS and Expert System Approach

Characteristics of Hyperspectral vs. Multipsectral Data in Image Processing

Using a GIS Data Model to Access the Totality of the Hyperspectral Information without have to Store All the Images in the Memory

 Figure 4:  A GIS Data Model for Hyperspectral Images

    Column #1      Column #2       Column #3          Column # n+1
-------------------------------------------------------------------
     Pixel ID     Channel 1  	    Channel 2    	Channel n
         1           f11               f12                 f1n
         2           f21               f22                 f2n
         k           fk1               fk2                 fkn
-------------------------------------------------------------------
    Internal                        Spectral Information 
    Segmentation Map                from each channel 
   

Suppose that a given hyperspectral imaging system has 256 channels, and each scene is composed of 512 by 512 pixels. Using the above data model, k = 262,144 and n = 256; therefore, one needs only to store one 32-bit based 512 by 512 image in memory, and a matrix of size 262, 144 by 256 in the hard disk. Since the latter amounts to only a storage space of slightly above 67 mega bytes, one can process the entire 256-channel based hyperspectral image data set with a PC based computing system.

Unification of GIS with Hyperspectral based Data Model

Using the GIS based data model approach, we have in fact reduced hyperspectral imagery into one single band, yielding an extremely significant rate of data compression without loss of any information.

Conclusions on Using Expert System Approach to Perform System Integration

Integrated Raster and Vector Processing in Remote Sensing

Relating this capability to the data model presented in Figure 1, IMaG integrates Column 4 with Column 5: pixel representation and boundary representation of a region.

Integrated GIS and Remote Sensing Analysis

Relating this capability to the data model of Figure 1, IMaG integrates all the data elements in all columns of Figure 1, particularly, between data in Columns (6 through k) and those in Columns (k+1 through n). Thus, by integrating the first type of GIS with image processing, one yields the second type of GIS.

Vector-to-Raster and Raster-to-Vector Conversion without Loss of Information

Relating this capability to the data model of Figure 1, IMaG permits a one-to-one interchange between Column 4 data and Column 5 data in view of the fact that IMaG provides means for vecterization of raster images, and Rasterization of vector based boundary files.

Generalizability of Expert Systems

Expert Systems as A "Culture"

Relating this "culture" creation capability to the data model of Figure 1, IMaG provides an environment for one to generate new data models that represent either a modification or an enrichment of the data model represented by Figure 1 in August 1994.

References

Arthur, Lowell J. and Burns, Ted.  UNIX Shell Programming.
	Third Ed.  John Wiley and Sons: New York, 1994.

Peuquet, Donna J. and Marble, Duane F. Editors.  
	Introductory Readings in Geographic Information Systems.
	Taylor and Francis:  New York, 1990.

United States Department of Commerce, Patent and Trademark Office.
	Notice of Allowance for a Patent dated 01/18/95. Title of 
	Invention: "Process for Identifying Simple and Complex Objects
	from Fused Images and Map Data," Inventor: Shin-yi
	Hsu, Series Code/Serial No. 08/066,691,
	Filing Date: 5/21/93.