Conflict Resolution Techniques for Expert Systems Used to Classify Remotely Sensed Satellite Images

Pakiarajah, V., Crowther, P. and Hartnett, J
School of Computing University of Tasmania PO Box 1214 Launceston Tasmania Australia
E-mail: P.Crowther@utas.edu.au

Abstract

This paper investigates the potential benefits an inference capability can provide automated image classification tasks in remote sensing. Most current applications depend upon skilled image interpreters to provide adequate classifications of satellite images. This creates problems in that it takes time to classify images manually, skilled interpreters may not always be available and often manual classification can be subjective to the interpreter. This paper looks at automating the classification process through the application of knowledge based or expert system technology in an attempt to solve these problems.

This paper includes discussion on the implementation of three conflict resolution strategies, first in first serve, last in first serve and prioritisation. Prioritisation in particular is an important technique for resolving conflicts, as the setting of priority on rules requires the knowledge of a domain expert.

One other important aspect addressed in this paper is the time the system takes to produce a classified result. CLIPS is unable to process whole images and needs to do the processing pixel by pixel. Pixel by pixel reasoning can slow down processing noticeably. Each SPOT image is 894 x 896 pixels multiplied by 3, because SPOT images include three bands of information. This paper included investigation into different methods of implementation to solve the problem of slow processing.

1. Introduction

1.1 Background

One of the main benefits that an inference capability can provide remote sensing is an ability to resolve conflicts. Conflict can occur with satellite images when one band of information classifies a pixel as one type of object, say trees, and another band of information classifies that same pixel as another type of object, say water. Without the help of a skilled interpreter it is difficult to classify this pixel. Most spatial information systems and image processing packages do not provide the reasoning capabilities needed to make such decisions. However, expert systems technology provides many different conflict resolution strategies to help make these decisions.

This study is based on data from a major agricultural region in North West Tasmania. The Remotely sensed images used in this study were produced by the SPOT HRV (Systeme Probatoire d'Observation de la Terre, Haute Resolution Visible) satellite. It forms part of a larger remote sensing project which is investigating automated crop classification in the region (Barrett et al., 2000).

1.2 Inferencing

Humans solve problems by combining facts with knowledge. Using their general understanding of the problem they use the facts to derive a conclusion. This process is referred to as reasoning. Expert systems model the reasoning process of humans using a technique called inferencing (Durkin, 1994). An expert system's inference engine controls the application of knowledge from the knowledgeable. There are a number of different methods of reasoning and inferencing as discussed in Durkin (1994) and Giarratano and Riley (1998a).

Forward chaining is when the reasoning happens from the facts to the conclusion (Giarratano and Riley, 1998a). That is, the facts are entered into the system, which in the context of this study, are the data in SPOT images. The system then works through the knowledgeable looking for rules matching the data. The results of these matches lead to a classification of objects in the image.

1.3 Conflict Resolution

A classification conflict will occur when more than one rule is matched on the facts asserted. Conflict often occurs in classifying objects in a remotely sensed image due to areas of an image that have more than one type of classification, or are involved in more than one reasoning path by the inference engine. For example, a pixel on band 1 of a SPOT image may be classified as peas, but may also have the same characteristics as potatoes on another band. Resolution of such conflicts is one of the areas of remote sensing where expert system techniques can be of an advantage. A method an inference engine can use to resolve conflict is to set precedence on certain rules.

In a forward chaining system such as used in this study, there is no control strategy in place and the fired rule is entirely dependent on what is matched first. Lucas and Van Der Gaag (1991) state that from a user's point of view a system acts more intelligently if the system fires rules based on context rather than order, as likely solutions are explored before unlikely ones. Conflict resolution is a way of providing a control strategy to influence the classification of a pixel

There are many different conflict resolution strategies developed for forward chaining systems. The following are definitions of each as found in Lucas and Van Der Gaag (1991) and Durkin (1994).

First in First Serve - The rule applied will be the first rule that is matched.

Last in First Serve - The rule applied will be the last rule that is matched.

Prioritisation - The rule to apply will be selected based on priorities set on rules, with priority information usually provided by an expert or knowledge engineer.

Specificity - The rule applied is usually the most specific rule, or the rule that matches the most facts. This strategy cannot be used if the rules are equal in specificity.

Recency - The rule applied is the rule that matches the most recently derived facts.

Fired Rules Involves not applying rules that have already been used.

Line of Reasoning - Involves firing all rules with a separate line of reasoning.

1.4 IDL, C and CLIPS

IDL, C and CLIPS were used in this study. IDL (Interactive Data Language) was chosen as the image processing package used to display and manipulate remotely sensed images because it is provides tools for data analysis, visualisation, and cross- platform application development (Research Systems Inc, cited 1999). KAGES was also developed in IDL and because this study will be integrated with KAGES it was vital that IDL was used. One other advantage of IDL is that it can be called from external routines or IDL itself can call external functions written in C.

CLIPS was used as the expert system shell as it provides the capabilities needed to develop an effective knowledgeable with the forward chaining inference engine, that is used for image classification tasks. CLIPS can also be called from an external program and is able to call external functions itself. These functions and programs need to be written in C. One other advantage in using CLIPS is that KAGES already produces rules in CLIPS.

IDL and CLIPS cannot interact with each other directly which is why C was selected as a third tool. IDL is able to use the inferencing capabilities provided by CLIPS by using C as an interface.

The method chosen for integration was to allow IDL to initiate procedures. The was because KAGES, being written in IDL, already provides an effective user interface. The future incorporation of this study into KAGES will only be possible if IDL continued to control the processing of images. This method may also take less processing time as IDL is more efficient at handling image data than C. Having made a call to a C function, that function is then able to process the image by using CLIPS.

2. Conflict Resolution Methodologies

2.1 First in first serve

First in first serve is one of the more simpler conflict resolution strategies in use. It involves firing the first rule that matches the content of the working memory (Durkin, 1994) or the facts asserted. First in first serve is best used in simple applications where it will not cause any logical problems. For these reasons it was chosen as a strategy to be implemented in this study. It is also highly dependent on the ordering of rules. The rules used in this system are not complex in structure or in ordering. It is also not difficult to build the rules in the order required for them to fire correctly.

First in first serve means that the system will always give precedence to the first classification applied to a pixel. That is, as soon as a pixel is classified, no matter which band it is on, the system will accept that classification. For example, say a pixel on band 1 was classified as trees and on band 3 was classified as potatoes. If the band 1 label was the fact that was asserted first, the system will accept the pixel should be classified as trees. This means that earlier assertions will always take precedence over later ones in classifying pixels.

In addition to the system being dependent on the ordering of the rules it can also be dependent on the order the facts are asserted. In this application it is important in which order the band information is inserted. The implementation of first in first serve was done in two different ways. That is, implementing the strategy after each band was classified and implementing the classification and strategy together. Both implementations have advantages and disadvantages as illustrated in the next two sections.

2.1.1 Implementing first in first serve after classification

Through the use of rules produced by KAGES each band of information in a SPOT image is classified pixel by pixel. Each band can be classified separately but producing one final classified image results in unclassified areas due to conflicting labels assigned to pixels. Initially, first in first serve was implemented after the bands were classified separately.

A flag variable is used in the implementation of first in first serve. The flag is initially set to 0. Once the defrule passing is fired the flag is set to 1, which tells the inference engine that the pixel has been classified and a value has been passed back to the C program. This means that there is no need to test the other bands for their classification of the pixel. Without the use of the flag there would not be any conflict resolution because CLIPS will pass back every classification. The flag also stops the inference engine from firing any unnecessary rules, which helps to speed up processing.

The advantage of having the ability to apply first in first serve after classification is that it allows flexibility. That is, the user may already have classified multi-band images that they would like to apply conflict resolution strategies to. It also means that the image does not have to be classified every time the user wants to use first in first serve. It may also save time if the user had already classified images that contained conflict.

2.1.2 Implementation of classification and first in first serve combined

The main reason for implementing first in first serve with the classification was to speed up processing. Implementing first in first serve after classification meant having to classify the image first and then applying the conflict resolution strategy. This means the total time taken is the time to classify three bands of information separately, plus the time taken to apply the conflict resolution strategy. A more feasible option, time wise, is to pass CLIPS the original image to classify and add conflict resolution techniques (pixel by pixel) all at once.

2.2 Last in first serve

Last in first serve works on similar principles to first in first serve. It takes the last conclusion it comes to as the final conclusion or goal. It is also one of the simpler conflict resolution strategies used in applications that do not require heavy logical evaluations. It too is highly dependent on the ordering of rules and the order facts are asserted.

Within the context of this study, last in first serve means that later bands of information have precedence over earlier bands. CLIPS uses the order in which the facts are asserted to assess which rules should be placed on the agenda. The pixel intensity and band number for each band can be asserted in correct order. That is, band 0, band 1 and then band 2. Where first in first serve used the reverse order, i.e.. band 2, band 1 and then band 0. Asserting pixel information in correct order will mean that band 2 is the most recent fact, which will put the corresponding rule on the agenda. If band 2 is classified then that is the classification for that pixel, otherwise it will look at band 1 and so on.

2.3 Prioritisation

Prioritisation is a conflict resolution strategy that places emphasis on rules that are more important (Durkin, 1994). It is said that this strategy directs the inferencing to reason with information in order of importance (Durkin, 1994). User's tend to trust this kind of reasoning more than that which relies on ordering of rules, such as first in first serve or last in first serve.

If a satellite image produces conflict in classification, prioritisation is often an effective method of resolving the conflict. For example, say a pixel on one band is classified as trees and the same pixel on another band is classified as water. The rule classifying water can have higher precedence than the rule classifying trees, which will result in the pixel being classified as water. Prioritisation is not a hard reasoning process for humans to understand or perform, but it may be a difficult process for an inference engine to mimic without the correct control.

CLIPS provides a mechanism that allows user's to set priorities on certain rules. It is referred to as rule salience and is set using integer values (Giarrantano and Riley, 1998b). It allows integers between the values –10 000 and 10 000. Rules that do not have salience declared are considered to have a salience of 0. A salience of 0 does not mean that the rule has no salience but that it has a neutral salience that stands between –10 0000 and 10 000.

Research in the area has shown that water has precedence over trees, which have precedence over peas and potatoes. This is shown by the fact that water's salience value is higher than trees', which is higher than peas and so on. This will mean that it does not matter in what order the facts are asserted or in what order the rules are constructed. If a pixel is classified more than once, water will be fired before any of the other values strictly because it takes precedence.

3. Processing Speed

As mentioned in previous chapters, IDL is designed to process image data quickly and effectively. However, because of the integration with an expert system shell, CLIPS, the image data had to be processed pixel by pixel. IDL is able to process whole arrays of information at once but C is only able to process these array one element at a time. Each element in the array, which is a pixel of image data, has to be asserted as CLIPS facts before CLIPS can apply the inferencing. This resulted in slow image classification.

3.1 For Loops

A number of solutions were implemented in attempt to improve the processing speed. Table 1 illustrates the results of experimentation. Initial experimentation involved using for loops in IDL to process each pixel in the image. This involved calling an external C function on each pixel. However, the processing of just one row of information was excessive. IDL generally is designed to handle whole blocks of image data at one time and forcing it to process an image pixel by pixel slowed it down considerably.

Method	Processing Time (approx. minutes)
For Loop in IDL	-
Load constructs for each pixel	150
Load Constructs Only Once	14
Conflict Resolution on its Own	6
Classification and Conflict Resolution	11

Table 1: Processing speed results

For loops in C were chosen as the next implementation. For loops in C are generally much faster than in IDL. This implementation involved passing whole blocks of IDL image data directly to C. Once this solution was applied there was a distinguishable improvement in processing time. The system took approximately 50mins to process one band of information, making it 150mins for the entire image. Although this time was a great improvement on the first implementation it was still too slow. In addition to the time factor this solution was classified each band separately producing separate images for each band in the SPOT image.

3.2 CLIPS Improvements

The next solution to improving processing time was to change the last implementation slightly by initialising CLIPS and loading constructs only once before the image is classified. For the previous implementation C was processing each pixel by initialising CLIPS and loading constructs each time. As Table 1 illustrates this method improved processing time considerably. It was not the initialising CLIPS that slowed down the processing however, but the system loading constructs for each pixel.

The above three methods only looked at classifying each band separately and had not applied any conflict resolution strategies to produce a final classified image. These classified bands then needed to be put through a conflict resolution reasoning process. This was initially implemented by passing C all three classified bands and then asserting this information as facts for each band, pixel by pixel. CLIPS would then take these facts and apply a conflict resolution strategy. Once the inference produced a classification this result would be passed back to IDL.

As shown in Table 1, the application of a conflict resolution strategy did not take very much time. One of the reasons for this is all three bands of information were passed to C at once. This eliminated the need for a for loop in IDL to cycle through each band. Another reason is that the information only needed to be processed once because the bands were already classified. Each pixel of the image only needed to go through the reasoning process once, which contributed to the short processing time.

The steps taken to produce a final classified image are: the original SPOT image is put through a classification process, band by band. Then the classified image bands are fed through a conflict resolution strategy. In total, the production of the final image takes approximately 20mins. It would take less time if the user already had classified images to feed through the conflict resolution strategy.

3.3 Integration

The final implementation involved doing the classification and applying the conflict resolution strategy all at once. It is an almost exact combination of the last two methods. All three bands of original data is passed to the inference engine, which will take the pixel information, classify it and resolve any conflicts. As illustrated in Table 1 this showed a marked improvement in processing speed, compared to applying the classification and conflict resolution strategy separately. It took approximately 11mins using the combined approach, while separate classification and conflict resolution took approximately 20mins to produce a classified image.

Before implementing this method the hypothesis was that the time would be the same as when the conflict resolution method was applied on its own, that is, approximately 6mins. This was because up until then the only element that was affecting the time of processing was the way it was being implemented in IDL and C. However, the result showed that it was slower, that is, approximately 11mins. This shows that it is not just the processing capabilities of IDL and C that affect the speed. Having to do the classification and conflict resolution together meant the reasoning process was more complex than when they were separately. The additional time of around 5mins is the result of the more complex inferencing required to produce a classification.

There are other factors that can affect the processing speed including the speed of the machine the system is being run on. Other processes running at the same time can also affect the time it takes for the system to produce a classified result. The time factor will also become an issue if this system was to be implemented on other satellite images, such as a Landsat TM image. Landsat TM images include seven bands of information, which may more than double the image processing time of a SPOT image.

4. Results and Discussion

For testing, two SPOT images were run through the conflict resolution classification system. Both images were of the same area of Tasmania, one was produced in November and the other in December. All three conflict resolution strategies, that is, first in first serve, last in first serve and prioritisation, were applied to each of these images. This produced six different images to analyse for accuracy using the sampling grid.

Although KAGES provided rules for water, trees, peas and potato, only areas of water and trees were used to analyse accuracy in this study. The reason for this is that water and trees will not change from image to image, that is, the areas that are water and trees will remain the same on both the November and December images. Paddocks for peas and potatoes, however, change from season to season and even month to month. There is no way of knowing that the accuracy reading for these areas are correct.

Table 2 illustrates the results of accuracy testing on the six images produced. It includes the month the image was taken, the conflict resolution strategy applied and the accuracy results of these strategies on objects water and trees. The accuracy results are a percentage of correct classifications of trees or water. An average number of sampling points used for water and trees is 38 and 314, respectively. The reason for such a low number of points for water is that the area of water in the image is only small compared to areas of trees. As shown in Figures 1 to 3, water only covers the top right-hand part of the image where as tree areas can be found all over the image.

Image Conflict Resolution Strategy Accuracy (%)

November First In First Serve

water
25.0

trees
65.7

Last In First Serve

water
89.7

trees
72.1

Prioritisation

water
91.9

trees
65.7

December First In First Serve

water
57.9

trees
99.7

Last In First Serve

water
100

trees
96.2

Prioritisation

water
100

trees
99.7

Image	Conflict Resolution Strategy	Accuracy (%)
November	First In First Serve
	water	25.0
	trees	65.7
	Last In First Serve
	water	89.7
	trees	72.1
	Prioritisation
	water	91.9
	trees	65.7
December	First In First Serve
	water	57.9
	trees	99.7
	Last In First Serve
	water	100
	trees	96.2
	Prioritisation
	water	100
	trees	99.7

Table 2: Accuracy results (% correct) of applying conflict resolution methods

Figure 1 shows the classification produced by first in first serve strategy on the December image. Notice areas of water are covered by the classification of trees. First in first serve, however, is accurate in classifying areas of trees. Overall this conflict resolution method has not resolved conflicts effectively enough to be used in spatial analysis.

Last in first serve has been very accurate in classifying both water and trees in both the November and December (Figure 2) images. Last in first serve is better in classifying water better than first in first serve. The main reason for the good result in classifying water is that water is on a later band than trees, which means that the system will classify water before trees.

Although last in first serve has given an accurate result in classification of trees and water in this test, it is still a method that can not be relied on completely. The results of last in first serve still relies on the ordering of the facts asserted. Or in this case the order in which the band is asserted. If, for example, the user decided to use band 3 to classify trees and band 2 to classify water then last in first serve will yield inaccurate results similar to first in first serve.

Prioritisation has yielded the best accuracy results so far, as shown in Table 2. The results of applying the three conflict resolution strategies are shown in Figures 1 to 3. Results of prioritisation for December are shown in Figures 3. Prioritisation sets priorities on certain rules so that classifications with highest priority are applied before classifications of less priority. In both November and December images it has classified water and trees correctly. As mentioned in chapter four, water has priority over trees, which then has priority over paddocks. Information as to setting priority is usually supplied by a domain expert.

Legend

Figure 1: Results of classification with First In First Serve conflict resolution for December SPOT image

Legend

Figure 2: Results of classification with Last In First Serve conflict resolution for December SPOT image

Legend

Figure 3: Results of classification with Prioritisation conflict resolution for December SPOT image

Prioritisation has been shown to be the best conflict resolution strategy used in this study. It does not in any way rely on the order facts are asserted or the order in which the rules are fired to produce a classification. For this reason, there will be less misclassifications as in first in first serve because a domain expert has provided the information to set priorities. There will also be none of the uncertainty that last in first serve produces. The user is also more inclined to trust the classification produced by prioritisation. That is, the system is seen to act more intelligently if the system fires rules based on context rather than order (Lucas and Van Der Gaag, 1991).

5. Conclusions

There are many advantages to integrating knowledge based systems (or an inference capability) and spatial information systems. This study has produced an inference capability for a spatial knowledge acquisition system. A means of improving image processing speed has been discovered and the benefits of an effective conflict resolution strategy have been emphasised.

During this study it was discovered that slow image processing speed can hinder effective integration of knowledge based systems and spatial information systems. Five different methods of processing where implemented and the results showed different factors affecting processing. It is best to use for loops in C rather than IDL for pixel by pixel processing. Loading CLIPS constructs is also a factor that slows processing. Loading constructs once rather than for every pixel solves this problem.

It was also discovered that classifying each SPOT band separately then applying conflict resolution strategies was slower than classifying and applying conflict resolution strategies simultaneously. However, if the user already had classified SPOT band images, it may be the best option to apply conflict resolution strategies separately. It was also discovered that the complexity of the inferencing can also affect the speed of processing. Classifying and then applying conflict resolution strategies to a pixel requires a more complex inferencing than conducting either separately. However, the combination of classification and conflict resolution strategies was still the faster method of implementation. The complexity of the inferencing may become a factor in further studies when different strategies are investigated.

Accuracy tests were conducted on the images produced through application of conflict resolution strategies (i.e.. first in first serve, last in first serve and prioritisation). First in first serve and last in first serve are both strategies that rely on the ordering of expert system rules and asserted facts. For this reason they can not be relied upon to produce accurate results. Even if the strategy did produced accurate classifications there is no way of deciding whether the system was producing these results for the right reasons.

Prioritisation is a conflict resolution strategy that incorporates a domain expert's knowledge into the system's inferencing. Setting priority to rules produces a more intelligent inferencing, which does not rely on the ordering of rules or asserted facts. For this reason, prioritisation yielded the most accurate results. It is also said that users are more likely to trust this type of inferencing because it is a more intelligent method of inferencing (Lucas and Van Der Gaag, 1991).

An inference capability can be used to provide a human like reasoning process to classify remotely sensed data. The correct conflict resolution strategy can provide effective results.

Acknowledgments

This work was supported by a Horticultural Research and Development Council Grant. We would also like to thank Tony Gray of the School of Computing's Technical Services and Catherine Cormack of Research Systems Inc. for technical support and advice.

References

Barrett, R., Crowther, P., Laurence, R. And Lincolne, R. (2000) 'Agricultural Crop Identification Using Spot and Landsat Images In Tasmania' ,IAPRS, Vol. XXXIII, Amsterdam, 2000 (In Press)

Crowther, P. Knowledge acquisition from satellite images for geographic expert systems – show or tell?. International Conference on Modeling Geographical and Environmental Systems with Geographical Information Systems (Vol.2). 1998, pp.568 – 573.

Durkin, J. 1994. Expert Systems: Design and Development. Macmillan Publishing Company, New York.

Giarratano, J. and Riley, G. 1998a. Expert Systems: Principles and Programming. PWS Publishing Company, Boston.

Giarratano, J. and Riley, G. 1998b. CLIPS Reference Manual Volume II: Advanced Programming Guide. PWS Publishing Company, Boston.

Lucas, P. and Van Der Gaag, L. 1991. Principles of Expert Systems. Addison- Wesley Publishing Company Inc, Wokingham, England.

Research Systems, Inc. 1994. IDL User's Guide. Boulder, CO.