An Adaptive GIS Tool For Image Characterisation

Abstract

GIS systems often rely on low-level, pixel-based representations of satellite scenes. The purpose of this paper is to show the advantages of using an intermediate representation incorporating multiple criteria in scene characterisation, as well as a framework for monitoring changes over time based on features of interest. A Conceptual Spaces framework, in conjunction with navigation-based skeletonisation are employed for this purpose. We evaluate our system on satellite images of rivers and lakes.

Introduction

from several geographical information systems. Thus, a sub-symbolic representation would provide a platform encouraging GIS interoperability. At the same time, this approach does not su®er from the pitfalls of ontology-driven GIS applications. A major potential use of the monitoring of inland water features is the °uctuation of water levels and the erosion of the coastline occurring over a period of time. A direct application of this monitoring is the measurement of the e®ects of global warming in speci¯c areas of interest. The correlation between descriptive attributes (pollution levels, etc) and position (skeleton of river) is the key to successfully characterising a river [ 3 ]. E®ective river segment characterisation is the ¯rst step to their categorisation and identi¯cation. The collection of several descriptive attributes concerning their shape facilitates this categorisation process. Common examples are pollution levels and the development of river bank deterioration. In addition, a structural representation of a river within an image can further facilitate the enrichment of this representation with attributes speci¯c to the application. The proposed graph representation as applied to river networks combines the advantages of both vector and polygon representations in terms of the included spatial information. The method employed in this paper has the potential of acting as a representation framework for such information. 2

Characterisation as Navigation

In [ 18 ], the need for a new technique of computing the skeleton of an object is examined. The tight coupling between the generation of the skeletal points and the higher-level representation of the skeletal line is proposed. A novel skeletonisation algorithm is presented that draws on techniques developed for mobile robot mapping and navigation and o®ers a number of advantages over existing skeletonisation methods. First, because the algorithm works by hopping from one landmark position in the image to another, it has to visit far fewer pixels to ¯nd a skeleton compared to conventional algorithms. Second, unlike other techniques, the exploratory nature of the algorithm allows it to identify junctions and endpoints on the °y, which facilitates later high-level symbolic processing. Finally, the method is more generic than others, in the sense that it can be adjusted to compute skeletons containing a variety of di®erent sorts of morphological information. Although much e®ort has been put into developing skeletonisation algorithms, no attempt up to now has been made to treat skeletonisation as a problem of navigation. However, it turns out that methods for mobile robot mapping and navigation, such as those presented in [ 10, 9, 8 ], can be transferred to skeletonisation. The conceptual challenge here is to think of a robot's environment as analogous to an object in a segmented image, with the robot itself located at a pixel inside that object. The problem of skeletonisation is then analogous to that of exploring and mapping the environment by navigating inside it while remaining on the skeletal line. These features of the algorithm make it particularly suitable to object characterisation, based on features or attributes of interest.

Including Morphological and Structural Information

Skeletonisation on its own is not su±cient to describe a shape in a satisfactory way. The reason for this is that similar shapes can have very di®erent skeletons, while very di®erent shapes can have similar skeletons. Hence, additional information is included, with the intention of capturing the morphology of the object contour. Various techniques have been proposed for accomplishing this. The two most important in°uences on the author's work have been Blum's Medial Axis Transform [ 2 ] and the Shock Graph [ 22 ]. In [ 2 ], the shortest distance from every point belonging to the skeleton to the object contour is encoded. The reconstruction of the original shape from its skeleton is possible in this manner. Shock graphs [ 22 ] go one step further and keep a record of the rate of change of the minimum distance to the contour along the skeleton. In this fashion, each segment of the skeleton is assigned a status. By creating these categories, a symbolic representation of the shape can be formed. The development of the algorithm took place with the aim of using the data it yields for high-level representation. In pursuit of this, it features two major advantages. First, the navigation process is not continuous. It consists of hops from one skeletal point to another. The data produced will therefore be more easily processed by highlevel representation frameworks, such as those proposed in [ 20, 5, 13 ]. Second, this technique allows for the computation of any kind of morphological information, including those presented in [ 2, 22 ], since the data encoded on the skeletal points is being added on the °y. Finally, unlike other related work [ 24 ], structural information of vital importance for logical reasoning in object recognition, such as junctions and end points, is extracted with no post-processing. 2.2

The Algorithm in Detail

As mentioned in Section 2, the crucial issue is to think of an analogy between the movement of a pixel inside an object with the motion of a robot inside a room. The aim for the pixel is to explore and navigate inside the object whilst staying on a path corresponding to the skeletal line. In order to achieve this, the pixel-robot has virtual sensors, which yield information about the distance to the boundaries. The sensors are emulated by checking a circular area around the pixel-robot for points that belong to the boundary. In this way, touch-points on the boundary can be extracted. The aim of the pixel-robot is to maintain a path along which there are only two touch-points. If there are fewer than two, the robot adjusts its position, the radius of the circular area, or both. If there are more than two touch-points, that means there is a junction and the robot explores all the possible branches. The real-world equivalent of this topic has already been studied in the context of Kuipers' Spatial Semantic Hierarchy [ 8 ]. What is more, the close connection between mapping and the skeleton has been explored in [ 10, 9 ]. In the present author's work, an attempt is made to adapt these ideas to the context of a digitised image. The roaming pixel checks a circle around it for touch points with the contour. If two touch points are found, then the pixel jumps a distance equal to the normal distance between the current centre and the cord connecting those two touch points. For object segments whose width remains constant, the algorithm performs no hops and the output is similar to that of standard skeletonisation algorithms. However, the more the object's width varies along the skeletal line, the greater these hops will be. Hence, the algorithm is better suited to naturalistic shapes. Special mention should be made of the sub-cases of the two touch-point case. At every stage, the algorithm retains a memory of the last skeletal pixel traversed, and calculates the angle formed by that pixel, the current pixel, and the next pixel. This in turn a®ects the decision of whether the pixel-robot is going to move forwards or backwards. There is also a special provision for the cases where the movement of the pixelrobot makes the sensors lose touch with one of the surfaces, and confuse it with a newly seen surface. This would clearly yield an incorrect skeleton, since only two of the total of three touch points would be sensed.

A very common problem among skeletonisation algorithms, and one that is not straightforwardly overcome, is the generation of many spurious branches. Moreover, small variations in the contour of an object can have rather drastic consequences in the shape of its skeleton. Consequently, branch pruning is often used as a method of deleting these branches [ 4 ]. The advantage of navigationbased skeletonisation is that by adjusting sensitivity parameters these spurious branches can be limited to a minimum, or completely eliminated. In e®ect, this feature of the algorithm renders it more suitable for the skeletonisation of complex shapes, where these branches become a source of great confusion and usually have no structural signi¯cance. This comparative advantage is illustrated in ¯gures 1 and 2. The navigation-based skeleton (¯gure 2) produces no spurious branches at all. In contrast, the divergence-based thinning algorithm [ 4 ] generates several of them (¯gure 1). 3

Characterising River Networks

Characterisation involves monitoring speci¯c characteristics of the scene that are important to the user. In the particular case of river characterisation [ 23, 16 ], both structure and shape are indispensable elements in the description of di®erent river segments. Rivers are structured shapes, with branches and forks, but nonetheless exhibit considerable variation in the morphology of di®erent segments. For this work, the Conceptual Spaces framework [ 5 ] is used. A Conceptual Space is a metric space in which entities are characterised by a number of quality dimensions. Quality dimensions can be closely tied to the raw input or de¯ned in more abstract terms. In this respect, the goal of our system is to not just consider a single descriptor, but several of them.

The local topology of a river system plays a prime role in the successful characterisation of that region. Structural information can be highly informative to the end of identifying segments and sources. Once the topology of the river network has been determined, a more detailed characterisation of the river segments can be accomplished by bringing morphology into the picture. Lastly, in addition to the morphological attributes that can potentially be recorded by navigation-based skeletonisation, graphs based on navigational skeleton representations allow for other non-morphological attributes to be considered. These could include sediment, nutrients, toxicants, and heat. Such a characterisation technique can also be used to classify water features. The most signi¯cant advantage of having an adaptable skeletonisation system is the capability to vary the collected attributes to best describe or identify a given feature. The best case scenario is where the variation of one single attribute is su±cient to distinguish between features of interest. Even though this is usually not the case, the mere fact that the attributes can be adapted facilitates the classi¯cation process. In ¯gure 3 to ¯gure 5, examples of the application of the algorithm to real satellite images can be seen. The topology is recorded on the °y, while morphology or additional thematic data can be included or added according to the speci¯c application. In the skeletons extracted from these examples, nodes corresponding to junctions appear as black, while nodes corresponding to end-points appear as grey. Measuring and quantifying changes in time series images is a topic of considerable importance in the GIS community [ 15, 6, 12 ]. The developed representation system is applied to a series of satellite images depicting the same area, taken over large time intervals. We claim that an attributed graph representation is su±cient to successfully describe the changes that have taken e®ect to the water features present in the images. In turn, this method can potentially be used to measure the consequences of global warming to lakes, ponds and rivers around the world. Time intervals could range from a few months or days in the case of e.g. °oods, to decades in the case of the e®ects of global warming. Conceptual Spaces can prove very powerful when one attempts to describe similarity [ 7, 1 ] . To each conceptual space corresponds a similarity metric. In this way, a degree of similarity can be determined when comparing knoxels - or points in the n-dimensional metric space - belonging to di®erent objects. This metric is tailored to the nature of the conceptual space itself. Since our low-level representation yields skeletons, we selected graph matching as the similarity metric of choice. When it comes to the problem of inexact graph matching, one must ask what kind of application this matching will serve, in order to ¯nd the most suitable approach. Probably the ¯rst inexact graph matching algorihm is the one proposed by [ 14 ], an improvement of which is also used in the widely popular SubDue software. In our case, the Approximate Graph Matcher [ 21 ] seemed attributes, average radius along the skeleton, and branch angle. In the images depicting a lake in Kazakhstan (¯gure 6), we can see that the greatest structural changes have taken e®ect during the past 10 years. This can be corroborated by an inspection of the time series images. The recession of water levels during the decade 1980-1990 has caused greater alterations to the shape of the lake, and hence the landscape. In the case of two attributes, a two-dimensional conceptual space containing the results of table 1, can be used in conjunction with Principal Components Analysis (PCA)to produce maps of change. The presented data were collected from three sets of time series images over identical time intervals.

Figure 7 shows what this analysis can show for the three time series, similar to the one in ¯gure 6 depicting a lake in Kazakhstan. In ¯gure 7 (left), points corresponding to change between 1970 to 1980 have been highlighted as grey, while the rest as black. Figure 7 (right) indicates how PCA assists in forming groups of points (depicted as di®erent shades of grey). In this example, three groups can be separated by the two principal components. In cases with large numbers of measured attributes, and hence many dimensions, such grouping of data can be useful in extracting patterns of change. 5

Conclusion

This paper demonstrated the applicability of the system presented in previous chapters to the challenging problem of river characterisation based on real satellite images. By providing an intermediate representation of river networks, the system contributes to the ¯eld of GIS, where lower level representations are the norm. The advantages of this higher-level representation are adaptability and interoperability. Second, the capabilities of the conceptual space framework employed in this paper are more evidently utilised by measuring and classifying changes in time series satellite images. The multi-attribute approach to river characterisation provides a platform that can successfully describe morphological as well as topological changes to river networks. Moreover, PCA is able to classify these changes and provides the user with an informative measure of monitored alterations. These two functions render the system a useful GIS tool that can be used to characterise river networks or classify water feature alterations over a period of time. In addition, this paper showed that the design choices made can produce an adaptable and versatile GIS tool.

References

1. Ola Ahlqvist . Using uncertain conceptual spaces to translate between land cover categories . International Journal of Geographical Information Science , 19 ( 7 ): 831 { 857 , 2005 .

2. Harry Blum . A Transformation for Extracting New Descriptors of Shape . In Weiant Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form , pages 362 { 380 . MIT Press, Cambridge, 1967 .

3. J.B. Dalton , D.J. Bove , and C.S. Mladinich . Remote sensing characterization of the animas river watershed, southwestern colorado, by aviris imaging spectroscopy . Scienti¯c Investigations Report 5203 , U.S. Geological Survey, 2004 .

4. P. Dimitrov , C. Phillips , and K. Siddiqi . Robust and e±cient skeletal graphs . pages 417{423 , 2000 .

5. Peter GaÄrdenfors. Conceptual Spaces: The Geometry of Thought . MIT Press, Cambridge, MA, USA, 2000 .

6. Rie Honda , Shuai Wang, Tokio Kikuchi , and Osamu Konishi . Mining of moving objects from time-series images and its application to satellite weather imagery . J. Intell. Inf. Syst. , 19 ( 1 ): 79 { 93 , 2002 .

7. Werner Kuhn and Martin Raubal . Semantic reference systems . International Journal of Geographical Information Science , 17 : 405 { 409 , 2003 .

8. Benjamin Kuipers . The spatial semantic hierarchy . Arti¯cial Intelligence , 119 ( 1- 2 ): 191 { 233 , 2000 .

9. Benjamin Kuipers and Yung-Tai Byun . A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations . Robotics and Autonomous Systems , 8 ( 1 -2): 47 { 63 , 1991 .

10. Tod S. Levitt and Benjamin Kuipers . Navigation and mapping in large scale space . AI Magazine , 9 ( 2 ): 25 { 43 , 1988 .

11. Paul A. Longley , Michael F. Goodchild , David J. Maguire , and David W. Rhind . Geographic Information Systems and Science . John Wiley & Sons Ltd., West Sussex , England, 2nd edition , 2005 .

12. D. M. Mark . Geographic information science: Critical issues in an emerging crossdisciplinary research domain . Journal of the Urban and Regional Information Systems Association , 12 ( 1 ): 45 { 54 , 2000 .

13. Richard C. Meathrel and Antony Galton . A hierarchy of boundary-based shape descriptors . In IJCAI , pages 1359 { 1364 , 2001 .

14. N. Nilsson . Principles of Arti¯cial Intelligence . Symbolic Computation . Springer, 1982 . NIL n 82:1 1 .Ex.

15. S. Ogata , K. Kirimoto , and M. Ide . Time series image analysis of dalian, china by remote sensing . In SICE 2002. Proceedings of the 41st SICE Annual Conference , volume 4 , pages 2099 { 2101 , August 2002 .

16. Melissa Parsons , Martin C. Thoms , and R. H. Norris . Development of a standardised approach to river habitat assessment in australia . Environmental Monitoring and Assessment , 98 ( 1 ): 109 { 130 , 2004 .

17. F.F. Sabins . Remote Sensing Principles and Interpretation. 2nd edition , 1987 .

18. Georgios Sakellariou , Murray Shanahan, and Benjamin Kuipers . Skeletonisation as mobile robot navigation . In Proceedings of Towards Autonomous Robotic Systems (TAROS-04) , pages 149 { 155 , September 2004 .

19. Paulo Santos , Brandon Bennett, and Georgios Sakellariou . Supervaluation semantics for an inland water feature ontology . In Leslie Pack Kaelbling and Allessandro Sa ±otti, editors, Proceedings of the 19th International Joint Conference on Arti¯cial Intelligence (IJCAI-05) , pages 564 { 569 , Edinburgh , 2005 . Professional Book Center.

20. M. Shanahan . A logical account of perception incorporating feedback and expectation . In KR , 2002 .

21. Dennis Shasha , Jason T. L. Wang , and Rosalba Giugno . Algorithmics and applications of tree and graph searching . In PODS '02: Proceedings of the twenty-¯rst ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages 39 { 52 , New York, NY, USA, 2002 . ACM Press.

22. Kaleem Siddiqi , Ali Shokoufandeh, Sven J. Dickinson , and Steven W. Zucker . Shock graphs and shape matching . In ICCV , pages 222 { 229 , 1998 .

23. J.R. Thomson , M.P. Taylor , K.A. Fryirs , and G.J. Brierley . A geomorphological framework for river characterization and habitat assessment . Aquatic Conservation: Marine and Freshwater Ecosystems , 11 ( 5 ): 373 { 389 , 2001 .

24. S. Vidal , E. Bardinet, G. Malandain, S. Damas , and N. Capilla . Object representation and comparison inferred from its medial axis . In ICPR '00: Proceedings of the International Conference on Pattern Recognition , pages 712 { 715 , 2000 .