R.N.Williams and J.S.Hartnett
Artificial Intelligence and Spatial Systems Research Group,
School of Computing, University of Tasmania
Email: R.Williams@utas.edu.au
This paper describes the design and implementation of a spatial data structure, called the "mini-raster", which uses a raster-based technique to represent individual objects depicted in satellite images. An image is divided into spatial objects using an appropriate segmentation technique; then each object is represented by its own miniature raster. This mini-raster is created by extracting that part of the segmented image contained within the bounding rectangle of the object and using it to create a binary mask defining the precise spatial extent of the object, with a 1 representing a pixel within the bounding rectangle which belongs to the specified object and a 0 representing a pixel which does not. The mini-raster, together with other relevant details relating to the object, is stored in working memory, in a structure resembling the frame data structure commonly used in knowledge-based systems.
The mini-rasters store full spatial information about all defined objects within the image in a way that allows us to determine individual object attributes (such as area, perimeter and shape characteristics) and to establish relationships (such as containment and adjacency) between small groups of objects, as required. Moreover, it enables this information to be retained in a raster form. The data structure is less efficient, in terms of storage space, than a vector structure or more sophisticated raster-like structures such as quadtrees, but the fact that it can be stored and manipulated as a simple two-dimensional binary array has very significant computational advantages.
Despite the rapidly increasing capabilities of computer sytems, both in memory capacity and processing speed, over the last two decades, the interpretation of remotely sensed images is still largely carried out manually. The time-consuming and often highly subjective nature of this manual interpretation process has been one factor which has reduced the ability of the remote sensing field to supply large amounts of spatial data for use in many application areas (Williams, 1995). Computer-based techniques have been used in an attempt to automate the image interpretation process but these have largely involved individual pixel-by-pixel analysis in which the spectral characteristics of a pixel, as measured in several different image bands simultaneously, are used to identify the surface cover being represented by that pixel. These techniques have proven to be faster, but often much less accurate, than the human image interpreters carrying out the same task and the reason given is that the human interpreters are experienced in using a variety of other cues, as well as the spectral characteristics of the pixel, to determine the surface cover (Richards, 1993). They use spatial knowledge (the relationship between the specified pixel and its neighbours) and ancillary knowledge (such as the time of year or the prevailing weather conditions) to help them determine what is being represented by the pixel. The inability of pixel-by-pixel analysis techniques to use this knowledge is a regarded as a significant factor contributing to their reduced accuracy.
We have been developing a knowledge-based image analysis system for iceberg detection and classification, which incorporates spatial and ancillary knowledge into the automated analysis process (Williams and Crowther, 1998). In order to implement a knowledge-based mechanism for the automated analysis of remotely sensed images, it is necessary to be able to identify various physical objects being depicted within the images and then to determine relevant characteristics of these objects and significant spatial relationships between them. These characteristics and relationships can be provided to a knowledge-based reasoning system which uses spatial and ancillary knowledge to come to appropriate conclusions about the objects and to analyse the image as a whole. As a result of the conclusions made, the system may also wish to alter the spatial representation of some of these objects (eg. merging them, splitting them into parts or altering their shape in some way).
Before one can define and reason with spatial objects within a satellite image, it is necessary to represent them using appropriate data structures. Spatial data structures fall into two main categories: raster types (where geographical space is represented as a two-dimensional array of values, called pixels) and vector types (where geographical space is populated by various individual objects, specified as polygons using an appropriate coordinate system). Satellite images are stored and manipulated using raster data structures, since this type of structure maps well to the scanning mechanisms employed by satellite sensors. However, a raster data structure essentially regards an image as a single field-like entity and it is more common to use a vector structure when explicitly representing spatial objects.
In the process of developing the iceberg analysis system (Williams and Crowther, 1998), we needed a spatial data structure which fitted naturally within a raster-based environment yet was capable of adequately representing individual objects depicted in a satellite image. To meet these two requirements, a form of "mini-raster" data structure has been implemented in which a satellite image is divided (using an appropriate segmentation technique) into individual spatial objects and each one of these is represented by its own miniature raster.
In our system, the initial segmentation process divides the image into spatial objects and a mini-raster is created for each object by extracting that part of the image contained within the bounding rectangle for the object and using it to create a binary mask (Figure 1). A pixel with a value of 1 in the mask represents a pixel belonging to the specified object and a pixel with a value of 0 represents a pixel which does not belong to the object. This mini-raster is then stored in working memory, together with other relevant details relating to the object, such as the object identification number (idno) and the dimensions and location of the bounding rectangle (brec) from which the mini-raster was derived. All of the details relating to one object are stored together in a unit similar to the "frame" commonly used to store information in knowledge-based systems, and the mini-raster is stored as one of the components of this frame.
Figure 1 - Mini-Raster Data Structures.
The mini-raster structure can store full spatial information about all defined objects within the image in a way that allows us to determine individual object attributes (such as area, perimeter, compactness and a variety of other shape measures) and to establish relationships (such as containment and adjacency) between small groups of objects, when required. This eliminates the need to calculate and store a wide variety of different spatial attributes and relationships for the objects when only a small subset of these is likely to be relevant during a particular analysis phase.
The use of mini-rasters to represent all of the objects within an image individually, rather than using a single raster to represent the image as a whole, has the advantage of allowing attention to be focussed on a small number of specific objects at a time, without the necessity to scan the whole image whenever a processing step is being performed. It also allows the objects to be displayed individually on the screen and to be manipulated directly by the user, via mouse operations, in an interactive (semi-automated) analysis system.
The mini-raster data structure is less efficient, in terms of storage space, than a vector structure or some of the more sophisticated raster-like structures, such as quadtrees. However, the fact that it can stored and manipulated as a simple two-dimensional binary array has very significant computational advantages, especially if it is being implemented in a specialised array-processing language such as the Interactive Data Language (developed and marketed by Research Systems Inc). We have used IDL as our implementation language because it has highly optimised routines for manipulating arrays and so is very efficient in its handling of raster data. It also contains an excellent toolbox for creating graphical user interfaces and is capable of creating applications which can be readily used in Unix, Windows or Macintosh environments (Research Systems, 1997).
The data structure has been implemented within a semi-automated image analysis system designed to detect and delineate icebergs in synthetic aperture radar images. In this case each tentatively identified iceberg is regarded as an object within the image and represented by its own mini-raster. Individual objects can then be accessed, processed, displayed on the screen and manipulated by the user via a mouse interface. Such an approach gives a great deal of flexibility as far as the subsequent analysis process is concerned. It means that, after the initial segmentation has been done, spatial and non-spatial attributes can be derived for each object and these can be used within a knowledge-based reasoning process which will select specific objects for further consideration, either by the system or by the user. Each of these individual objects can then be analysed in detail. This analysis may result in some of them being rejected as valid icebergs and others having their outlines changed to more accurately reflect the size and shape of the real icebergs being depicted in the image.
The use of the mini-raster structure within this process can be illustrated by considering how a synthetic aperture radar (SAR) image, such as that shown in Figure 2(a), is analysed. Firstly the image is segmented, using a method based on local image homogeneity (Williams and Crowther, 1998). One segment is identified as the background and all others are tentatively identified as icebergs. The segmented image is shown in Figure 2(b). The analysis system then creates a separate frame-like data structure for each segment which has been tentatively identified as an iceberg. This data structure contains several slots, the first of which is the identification number of the segment and the second to fifth contain the boundaries of the enclosing rectangle. The sixth slot in the frame contains the mini-raster itself, for the specified segment. That is, it contains the two-dimensional binary array which represents the shape of the object.
(a) (b)
Figure 2 - (a) Portion of a SAR image depicting icebergs off the Antarcic coastline near to Casey Station. (b) Initial image segmentation showing all segments tentatively identified as icebergs.
These frames, each one containing the bounding rectangle for its specified segment and the mini-raster representing the exact shape of the segment, can support quite flexible reasoning and image manipulation processes. Attention can be directed, in turn, to any single segment within the image, or to the image as a whole. The reasoning processes can check each tentatively-identified iceberg segment more closely to determine whether the initial identification is likely to be correct or not.
For example, if a segment has an average grey-level which is significantly below that expected for an iceberg, then it is unlikely to be an iceberg. To apply this rule to all segments, it is necessary to determine what average grey-level value should be expected for icebergs within that image. In order to do this we need to estimate the approximate global grey-level average for all of the icebergs currently depicted in the image. If we consider all of the interior iceberg pixels (ie. avoiding border pixels where the pixel grey-level may have been artificially reduced by mixed pixel effects) in the image and average the grey-level values of these pixels, this should give us a reasonable estimate of the global grey-level average. The result will be slightly biased, since we already suspect that some of these segments are not valid icebergs. However, if we assume that a high proportion of the segments are valid icebergs, this bias would not alter the result significantly. Each segment mini-raster is then accessed, in turn, and the average grey-level for all non-border pixels in the segment calculated, using the binary mask in the mini-raster to refer back to the appropriate pixels in the original SAR image. If this segment-based average is significantly below the global average (we have used a threshold value of 0.75 times the global average) then the segment is flagged as an invalid iceberg segment. This process was effective in identifying four invalid iceberg segments, which are shown coloured black in Figure 3(b).
The mini-rasters can also be used to refine the outlines of valid iceberg segments. The initial segmentation process, used in the iceberg analysis system, employs an edge detector based on a 3x3 mask and so iceberg edges cannot be located to better than plus or minus two pixels from the true edge. This results in iceberg areas for smaller icebergs, being calculated inaccurately. The solution to this problem is to reprocess all valid iceberg segments to define their edges more accurately, using a simple grey-level threshold technique also based on the global grey-level average. The reason this technique could not be used in the first place is that we cannot determine the global grey-level threshold until an initial segmentation and tentative iceberg identification has been carried out. However, the technique can be used, as a second stage process, to refine the iceberg outlines produced by the initial edge-based segmentation.
To do this, each segment accepted as a valid iceberg segment is considered, in turn, by the system. The mini-raster corresponding to the segment is overlaid on the original SAR image and each image pixel falling within, or just outside, the mini-raster's binary mask is compared with the global grey-level threshold. If it is brighter than the threshold it is included within a modified binary mask, but if it is darker than the threshold it is not included within the modified mask. This produces a new mini-raster which still represents the segment, but now with a refined boundary, some parts of which may lie within the original boundary and some parts of which may lie just outside it. The aim is to produce a new segment boundary which more accurately traces the actual boundary of the iceberg within the image, to an accuracy of plus-or-minus one pixel. The new mini-raster is now used to redefine the shape of the corresponding segment within the original segmented image. The results of this segment refinement technique can be seen by comparing the refined iceberg shapes shown in Figure 3(b) with the corresponding unrefined shapes shown in Figure 2(b). The refined shapes correlate more closely with the iceberg shapes which can be visually identified in the original SAR image portion, shown in Figures 2(a) and 3(a).
(a) (b)
Figure 3 - (a) SAR image portion as shown in figure 2(a). (b) Improved segmentation showing invalid segments, in black, and segments with refined shapes.
So far the mini-raster data structure described here has been used on a single application: the iceberg analysis system. Its use in this application proved advantageous in that it allowed us to represent spatial objects using a raster data structure, which is very natural in the remote sensing field. The data structure was easy to implement in IDL as a two-dimensional array data type. It enabled us to perform a range of image processing operations on specific spatial objects within the image, without having to apply these operations to the image as a whole. It proved particularly useful when we wanted to manipulate and modify specific spatial objects within an image on an individual basis. We were able to identify, extract and modify individual iceberg segments and then place these modified segments back into the image.
Future work on the mini-raster data structure will extend it to deal with spatial objects which may overlap each other in an image, since the current structure can only be used for non-overlapping objects. We will also investigate the development of a similar spatial data structure capable of representing spatial objects with fuzzy boundaries. As well, the potential of the mini-raster for helping to solve other remote sensing image analysis problems, such as identifying paddock boundaries in SPOT images, is being evaluated. Although the structure has been specifically designed to facilitate the computer-based analysis of remotely sensed images, it may also be suitable as a more general spatial data structure capable of supporting a wide range of spatial analysis tasks.
Williams, J.: Geographic Information from Space: Processing and Applications of Geocoded Satellite Images, Wiley: Chichester, 1995.
Research Systems: IDL Version 5.0 User Manual, Research Systems publishers, Boulder: Colorado, 1997.
Richards, J.A.: Remote Sensing Digital Image Analysis: An Introduction (2nd Edition), Springer-Verlag: Berlin, p294.
Williams, R.N. and Crowther, P.: Application of a technique, based on local image homogeneity, to delineate spatial objects in satellite images., to be presented at the International Geoscience and Remote Sensing Symposium (IGARSS'98), Seattle, July 1998.