Expected classes in the images.
Some multi-sensor data fusion applications to humanitarian mine action are presented in this chapter. Data fusion techniques may be useful to two main humanitarian mine action types: close range antipersonnel mine detection and remote sensing mined area reduction. Close range antipersonnel mine detection refers to detecting surface and subsurface anomalies that may be related to the presence of mines (e.g., detection of differences in dielectric constant, thus in the type of material, using a ground-penetrating radar) and/or detection of explosive materials. Area reduction refers to identifying the mine-free areas out of the mine-suspected areas. Data fusion for these two applications is discussed here.
In case of both humanitarian mine action types, efficient modelling and fusion of extracted features can increase the overall performance of single-sensor based processing. Yet, a wide variety of scenarios and conditions typically exists between different minefields and within a minefield itself. Therefore, a high-quality performance of humanitarian mine action tools can only be obtained using multi-sensor and data fusion approaches. In addition, as the sensors used are, actually, detectors of different anomalies that may be related to mines (and not of mines themselves), combinations of these complementary pieces of information might improve the detection and classification results. Finally, in order to consider the inter- and intra-minefield variability, uncertainty, partial knowledge and ambiguity, knowledge-based theories prove to be useful, such as belief functions in the framework of the Dempster-Shafer evidence theory (Shafer, 1976; Smets, 1994; Smets & Kennes, 1994) or possibilistic and fuzzy theory (Dubois & Prade 2006; Zadeh, 1965). We focus on the latter in this chapter. Namely, as the possibilistic and fuzzy theory allows for the flexibility in the choice of combination operators, we exploit this fact in order to account for the different characteristics of the sensors to be combined.
For close range detection, modeling and fusion of extracted features are shown, based on the possibilistic and fuzzy theory. The approaches are discussed for the case of using real data coming from three complementary sensors (ground-penetrating radar - GPR, infrared sensor – IR, and metal detector - MD), collected within the Dutch project HOM-2000. These results are obtained within two Belgian humanitarian demining projects, HUDEM and BEMAT. In case of mined area reduction, a multi-sensor data fusion method based on fuzzy logic is presented and discussed in the case of using real data of synthetic-aperture radar and multi-spectral sensors, gathered within the EU project on space and airborne mined area reduction tools (SMART). The influence of various knowledge sources on the performance of the overall system is demonstrated too.
2. Fuzzy and possibilistic fusion
In the framework of fuzzy sets and possibility theory (Zadeh, 1965; Dubois & Prade, 2004), the modeling step consists in defining a membership function to each class or hypothesis in each source, or a possibility distribution over the set of hypotheses in each source. Such models explicitly represent imprecision in the information, as well as possible ambiguity between classes or decisions.
For the combination step in the fusion process, the advantages of fuzzy sets and possibilities rely in the variety of combination operators, which may deal with heterogeneous information (Dubois & Prade, 1985). Among the main operators, we find t-norms, t-conorms, mean operators, symmetrical sums, and operators taking into account conflict between sources or reliability of the sources.
We can classify these operators with respect to their behaviour (conjunctive, disjunctive, compromise (Dubois & Prade, 1985)), the possible control of this behaviour, their properties and their decisiveness, which proved to be useful for several applications (Bloch, 1996). On the contrary to other data fusion theories (e.g., Bayesian or Dempster-Shafer combination), fuzzy sets provide a great flexibility in the choice of the operator, that can be adapted to any particular situation. The theory of belief functions has also been endowed with a similar flexibility in some recent works (Denoeux, 2008).
An advantage of this approach is that it is able to combine heterogeneous information, which is usually the case in multi-source fusion (as in both examples given in the chapter), and to avoid to define a more or less arbitrary and questionable metric between pieces of information issued from these images, since each piece of information is converted in membership functions or possibility distributions over the same decision space.
Decision is usually taken from the maximum of membership or possibility values after the combination step. Constraints can be added to this decision, typically for checking for the reliability of the decision (is the obtained value high enough?) or for the discrimination power of the fusion (is the difference between the two highest values high enough?).
A main difference between fuzzy classification and possibilistic classification is that classes are generally considered as fuzzy sets in the first case and as crisp ones in the second case. In the following sections, we illustrate these two types of modelling.
In Section 3, we consider the first application (close-range detection), where the decision classes are crisp ones. We model the uncertainty and imprecision in the features as possibility distributions of the set of classes. Then in Section 4, we go one step further by modeling the imprecision attached to the measurements themselves, or the derived possibility values, leading to more robustness.
In Section 5, we consider the second application (mined area reduction), and model the classes (here landcover classes) as fuzzy sets, accounting for the imprecision attached to the images and the definition of classes.
3. Possibilistic approach to close-range detection
We define the problem of close-range detection in the context of humanitarian demining as the assignment of some measures (provided by different sensors) to one of two classes: mines or friendly objects. In this section, we summarize previous results (Milisavljević & Bloch, 2003; Milisavljević & Bloch, 2008) obtained using possibilistic models, by considering the two classes as crisp ones. A number of measures are extracted from the data of the sensors used:
the area and the shape (elongation and ellipse fitting) of the object observed using the IR sensor,
the size of the metallic area in MD data,
the propagation velocity (i.e., the type of material), the burial depth of the object observed using GPR, and the ratio between object size and its scattering function.
3.1. Possibilistic modelling of the measures
In the frame of the possibility theory, we model information provided by these measures in terms of possibility distributions. We have two spaces for each function: the set of hypotheses, which is the same for each function, and the feature space, which depends on the measurements from which the function is derived. Each function for one hypothesis is therefore not a value but a function over the feature space (a function of depth value, of shape measure, etc.). The specific shape of the functions and their parameters are derived from the knowledge, indicating their general behaviour.
IR measures. Elongation and ellipse fitting measures provide information mainly on shape regularity (Milisavljević & Bloch, 2003; Milisavljević & Bloch, 2008). The possibility degrees of being a regular-shaped mine (MR), derived from these two measures, are denoted by 1I (MR) and 2I (MR), while 1I (MI) and 2I (MI) represent the possibility degrees of being an irregular-shaped mine (MI). Possibility degrees of being a regular-shaped non-dangerous (friendly) object (FR) and irregularly shaped friendly object (FI) are denoted by 1I (FR) and 1I (FI) for elongation and by 2I (FR) and 2I (FI) for ellipse fitting measure.
In case of elongation, we find r1 as the ratio between minimum and maximum distance of bordering pixels from the center of gravity (on thresholded images) and r2 as the ratio of minor and major axis obtained from second moment calculation (Haralick & Shapiro, 1992; Milisavljević & Bloch, 2003). Then we define:
Regarding ellipse fitting, we calculate A oe as the part of object area that belongs to the fitted ellipse as well, A o is the object area, and A e is the ellipse area. Using these values, the following possibility degrees are derived (the subtraction of 5 pixels is related to the limit case - minimum 5 points needed to define an ellipse):
Finally, the area directly provides a degree 3I (M) (where M=MRMI) of being a mine - since the range of possible anti-personnel (AP) mine sizes is approximately known, the degree of possibility of being a mine is derived as a function of the measured size:
where a I is the actual object area on the IR image, while the approximate range of expectable mine areas is between a1 and a2. For AP mine detection, we set a1 = 15 cm2 and a2 = 225 cm2 (Milisavljević & Bloch, 2003; Fischer et al., 2007). Friendly objects can be of any size, meaning that the measured size is uninformative about the possibility of being a friendly object (F=FRFI):
MD measures. Under some conditions (Thonnard & Milisavljević, 1999; Das, 2006; Milisavljević & Bloch, 2008), it is possible to extract the object shape and area as seen by MD, as well as the burial depth. In reality, it can be difficult to adjust the sensitivity so that all the low-metal content mines are detected without causing the data saturation for high-metal content objects. In addition, in order to speed up the scanning time in large minefields, the data gathering resolution in the cross-scanning direction can be very poor. Thus, the MD information consists typically of only one measure, which is the width of the region in the scanning direction, w [cm]. As friendly objects can contain metal of any size, we define:
For most of AP mines, the range of the expected sizes of metal in mines is between 5 cm and 15 cm), so we can assign possibilities to mines as:
GPR measures. All three GPR measures provide information about mines (Milisavljević et al., 2003).
Regarding burial depth information (D), friendly objects can be found at any depth. On the contrary, mainly due to their activation principles, there exists a maximum depth (Dmax, typically 25 cm) up to which AP mines can be found. Therefore, possibility distributions for mines, 1G (M), and friendly objects, 1G (F), for this measure can be modeled as follows:
In case of the ratio d/k between object size seen in the scanning direction, d, and its scattering function, k (which is directly related to the object shape (Capineri et al., 1998)), friendly objects can have any value of this measure. For mines, there is a range of values that mines can have, and outside that range, the object is quite certainly not a mine:
where m d is the d/k value at which the possibility distribution reaches its maximum value (here, m d = 700, chosen based on (Capineri et al., 1998)), and p is the width of the exponential function (here, p = 400).
The third GPR measure, propagation velocity, v, can provide information about object identity. For this measure, we extract depth information on a different way than in the case of the burial depth measure 0 and we preserve the sign of the extracted depth. This information indicates whether a potential object is above the surface, in which case the extracted propagation velocity should be close to c = 3108 m/s, the propagation velocity in vacuum. If the sign indicates that the object is below the soil surface, the value of v should be around the values for the corresponding medium, e.g., from 5.5107 m/s to 1.73108 m/s (Capineri et al., 1998) in case of sand:
with v t being the most typical velocity for the medium (for sand, it is 0.5 (5.5107 +1.73108) = 1.14108 m/s, and for air, it is equal to c), and h is the width of the exponential function (here, h = 6107 m/s). Again, friendly objects can have any value of the velocity:
Note that all these functions have formal expressions that have been chosen in order to achieve suitable shapes and behaviours. However, other functions sharing the same properties could be used as well and we experienced that a fine tuning is not necessary.
3.2. Combination of possibility degrees
The combination is performed in two steps: the first one applies to all measures derived from one sensor, while the second one combines results obtained in the first step for all three sensors. Here, only the combination rules related to mines are considered. The issue of combination rules for friendly objects is discussed in detail in (Milisavljević & Bloch, 2008).
Let us first discuss the first step for each sensor. For IR, since mines can be regular or irregular, the information about regularity on the level of each shape measure is combined using a disjunctive operator:
The choice of the maximum (smallest disjunction and idempotent operator) as a t-conorm is related to the fact that the measures cannot be considered as completely independent from each other, so there is no reason to reinforce the measures by using a larger t-conorm, and the idempotent one is preferable in such situations. These two shape constraints should be both satisfied to have a high degree of possibility of being a mine (Milisavljević & Bloch, 2008). Thus, they are combined in a conjunctive way (here using a product). Finally, the object is possibly a mine if it has a size in the expected range, or if it is not in the expected range, but satisfies the shape constraint, hence the final combination for IR is:
In case of MD, as there is just one measure used, there is no first combination step and the possibility degrees obtained using (7) and (8) are directly used.
Regarding GPR, it is possible to have a mine if the object is at shallow depths and its dimensions resemble a mine and the extracted propagation velocity is appropriate for the medium. Therefore, the combination of the obtained possibilities for mines is performed using a t-norm, expressing the conjunction of all criteria. Here the product t-norm is used:
Finally, since the final possibility should be high if at least one sensor provides a high possibility and since it is better to assign a friendly object to the mine class than to miss a mine, the second combination step is performed using the algebraic sum, which is chosen for its strong disjunctive behaviour:
The final decision can be simply obtained by thresholding the fusion result for M and providing the corresponding possibility degree as the confidence degree. As presented in (Milisavljević & Bloch, 2008), an alternative for the final decision making is to derive the combination rule for F as well, compare the final values for M and F and derive an adequate decision rule.
4. Fuzzy approach to close-range detection
In this section, we propose to introduce the fuzziness in the proposed approach. Fuzziness may be indeed attached to the measurements. An example where classes are prone to fuzziness is presented in the next section.
4.1. Fuzzy modelling of the measures
In our previous work (Section 3), all measures derived from the sensor data were considered as crisp numbers. However, they may suffer from imprecision, due to the procedures used to extract these measures. As a typical example, a threshold is applied on the IR images and measured are derived from the resulting binary regions. Although the threshold values are chosen with care, varying them by a few units may lead to variations in the derived measures.
As an original feature of the present work, we propose to model this imprecision in the fuzzy set framework and consider all measures as fuzzy numbers and not crisp ones. We detail the modeling step in this section, while introducing the fuzzy numbers in the fusion methods will be described in the next one.
The imprecision can be introduced at several levels, directly on the measures, or on the derived possibility values.
Modeling the measures as fuzzy numbers. Let us consider for instance the elongation measures. The location of the bordering pixels and the center of gravity may be subject to imprecision (for example, depending on the threshold). Let a be the minimum distance and b the maximum distance. We could estimate the typical imprecision (e.g. 2 pixels), e.g., by varying the threshold and measuring the induced variation on a and b. This could then define the 0.5-cut of a fuzzy number representing a (respectively b), as illustrated in Figure 1.
We can choose simple shapes for membership functions, such as triangles, which are sufficient to represent the imprecision and only require two values to be defined: the actual measured value (a0) in this example, and the typical imprecision ε. In this example, this leads to the following definition of the fuzzy number representing a:
Note that we should restrict the support to admissible values for the considered measure. For instance if the measure has to be in [0, 1], then the support of the fuzzy number should be included in [0, 1]. Otherwise we could have values with non-zero membership values (i.e. considered as possible), while they are actually not admissible.
A similar model can be estimated for b, leading to a fuzzy number µ b .
Then r1 can be derived using the extension principle (Zadeh, 1975).
Let us recall the extension principle in the case of an operation applying on fuzzy numbers. Let µ 1 and µ 2 be the membership functions defining two fuzzy numbers (i.e., functions from the real line into [0, 1], such that all α-cuts are closed intervals, and having a unique modal value). Let be an operation between two numbers to be extended to fuzzy numbers. The resulting fuzzy number µ is defined as:
Other extensions principles can be defined, using for instance the product instead of the minimum (Dubois & Prade, 1980).
In our particular case, we can derive a fuzzy model for r1 from µ a and µ b as follows:
Alternatively, we can directly model r1 as a fuzzy number. Indeed, the variations of a and b depending on the thresholds are probably correlated (for instance if a increases because the region has been expanded by the thresholding, then b increases too), and this is not taken into account in the previous model.
We reason in a similar way for all measured quantities, in order to obtain fuzzy numbers for all of them.
Summarizing, a general procedure for modeling a fuzzy number corresponding to a measure x derived from sensor data is as follows:
Let x0 the actually measured value.
Let ε x the typical imprecision on this measure.
Define a fuzzy number µ x as a triangular fuzzy set on the real line with support [x0 - ε x , x0 +ε x ] and modal value x0.
If needed, reduce the support to guarantee its inclusion in the set of admissible values for x.
This model is simple but robust enough. The most important feature is the ability to account for imprecision. The shape of the membership function does not need to be precisely estimated.
Introducing imprecision directly in the possibility values. An alternative way for introducing the imprecision is to model directly the possibility values as fuzzy numbers. This approach avoids frequent calls to the extension principle and leads to simpler modeling and faster computation.
Based on the imprecision estimated for each measure, it is easy to estimate the derived imprecision on the possibility values, even in a rough way (again this will be sufficient to achieve a good robustness). For instance the imprecision on π1I (MR) will be of the same order of magnitude as the imprecision on r1 and r2. So this possibility degree can be directly modeled as a fuzzy number of triangular shape with min(r1, r2) as modal value and a support of length 2ε, where ε is derived from the variability on r1 and r2 when the threshold value is varied, as explained above. For other possibility values, the imprecision should be computed by applying the same functions as for the measures (e.g. exponential, cosh, etc.).
Then the modeling steps are as follows:
Compute the modal values for each possibility exactly as in Subsection 3.1.
Introduce imprecision by defining triangular shaped membership functions, using these modal values and the typical imprecision attached to each measure derived from the data.
4.2. Fusion based on fuzzy input
For the fusion step, we propose to rely on the same approach as in Subsection 3.2, but extending it to account for fuzzy input values. Then all π and m values become fuzzy values, by using the extension principle, and their combination as well.
For instance, if r1 and r2 are fuzzy numbers defined by membership functions
Note that with this definition, the minimum of two fuzzy numbers is not necessarily one of the two initial fuzzy numbers, as illustrated in Figure 2.
However, a nice and useful property of this operation is that the support of the result is always included in the union of the supports of the two fuzzy numbers. In this particular example, where a possibility degree is derived from the minimum of two values in [0, 1], we get a fuzzy possibility degree, having a support in [0, 1], which is consistent.
Let us now consider Eq. 2. For computing 1 minus a fuzzy value, we will consider a membership function defining the crisp value 1 as follows: µ1(1) = 1, µ1(λ) = 0 λ ≠ 1. Then Eq. 2 can be extended using the extension principle applied to µ1 and π1I (MR). Here it takes the following simple form:
All other combinations can be defined in a similar way.
The same decision rules can be applied as in the original model (summarized in Subsection 3.3). Decision consists of both an answer on whether the considered object is a mine or a friendly object, and a confidence value. Here this confidence value can either be kept fuzzy or a crisp value can be obtained by defuzzifying the resulting possibility value (which are fuzzy numbers), for instance by using the center of gravity of these fuzzy quantities. Let µ the membership function of a resulting value, having a support [λ1, λ2]. Its defuzzification using the center of gravity is expressed as:
Alternative methods are possible as well (e.g. taking the value having the highest membership value, etc.).
Note that a defuzzification step could be performed at any stage of the process. Considering fuzziness all through the process avoids taking crisp decisions on the possibility values at too early stages, but also leads to heavier computation.
5. Fuzzy approach to remote sensing mined area reduction
5.1. SMART system
The goal of area reduction is to determine which mine-suspected areas do not contain mines. This task is recognized as a mine action activity that should result in reduction in time and resources. Several well-known methods are in use to perform area reduction, especially using mechanical means. Most of the time, these expensive methods change and damage the environment and the ecosystem. In order to avoid this, some approaches have been developed that acquire the necessary information remotely, from air or space, using appropriate sensors associated with context information collected from the field and integrated in a geographical information system (GIS). One of these projects is the SMART project (Yvinec, 2005), funded by the European Commission/DG/INFSO and applied to Croatia. The aim of this project is to provide the human analyst with the SMART system. This system is GIS-based, augmented with dedicated tools and methods designed to use multispectral and radar data in order to assist in human analyst’s interpretation of the possibly mined scene during the area reduction process. The usefulness of such image processing tools in helping photo-interpretation is in the possibility to process automatically a large amount of data and help a visual analysis (SMART consortium, 2004). The use of SMART includes a field survey and an archive analysis in order to collect knowledge about the site, a satellite data collection, a flight campaign to record the data and the exploitation of the SMART tools by an operator to detect indicators of presence or absence of mine-suspected areas. With the help of a data fusion module based on belief functions and fuzzy sets, the operator prepares thematic maps synthesizing all the knowledge gathered with these indicators. These maps of indicators can be transformed into risk maps showing how dangerous an area may be according to the location of known indicators and into priority maps indicating which areas designed to help the mined area reduction process.
Figure 3 illustrates the global SMART approach. We focus here on the fusion step, which provides an intermediary result in SMART, consisting in improved land-cover classification maps, along with confidence values. This result is exploited by the deminers together with the final result.
5.2. Data and their specificities in SMART
The available images include SAR, multispectral, high resolution optical and satellite data. SAR data were collected with the E-SAR system of the German Aerospace Centre (DLR) in fully polarimetric P- and L-band and in vv-polarization (waves are vertically transmitted and received) X- and C-band. Multispectral Daedalus data were collected with a spatial resolution of 1 m and in 12 channels, ranging from visible blue to thermal infrared. SAR and Daedalus data were geocoded. DLR also provided a complete set of RMK photographic aerial views recorded with a colored infrared film at a resolution of 3 cm. This non-geocoded data set is used as evidence to control the processing tools and for qualitative interpretation by photo-interpreters. Finally, geocoded KVR-1000 black-and-white satellite images with a resolution of 2 m, recorded before the war in Croatia, were purchased in order to assess the changes in the landscape due to the war.
The legend (expected classes in the images), derived based on the existing and gathered knowledge about the mined areas, is given in Table 1. Ground truth was provided as a set of regions (training regions and validation regions). In the fusion module, training regions are used for estimating the parameters of some of the proposed methods; validation regions are used for the evaluation of the results.
|1||Abandoned agricultural land|
|2||Agricultural land in use|
|6||Trees and shrubs|
|Data type||Type of result|
|SAR||Classification with confidence images per class|
|SAR & Daedalus||Detection of hedges, trees, shadows, rivers, with confidence degrees, sometimes discounted|
|Daedalus||Supervised classification, result as a decision image|
|Daedalus||Region-based classification with confidence images per class|
|Daedalus||Belief function classification with confidence images per class|
|SAR & Daedalus||Binary detection of roads|
|SAR||River detection (binary)|
|Daedalus & KVR||Change detection (binary image)|
5.3. Fuzzy fusion approach in SMART
The computations here are performed at pixel level. A final regularization step is then applied. Different fusion strategies have been developed (Bloch et al., 2007) and we present here the most promising one, a fuzzy approach.
In this approach, we choose for each class the best classifiers, based on the confusion matrix for each classifier or detector, by comparing the diagonal elements in all matrices for each class. Then, for each class, we combine the best classifiers with a maximum operator (possibly with some weights). Finally, the decision is made according to a maximum rule. This approach is very fast. It uses only a part of the information, which could also be a drawback if this part is not chosen appropriately. Some weights have to be tuned, which may need some user interaction in some cases. Although it may sound somewhat ad hoc, it is interesting to show what we can get by using the best parts of all classifiers.
After this first combination step, the next step which follows is knowledge inclusion. It is one of the main powers of our algorithms with respect to the commercial ones. This aspect has led to a lot of work in SMART, at different levels. Note that knowledge on the classifiers, their behaviors, etc. is already included in the previous steps. At this step, we use only the pieces of knowledge that directly provide information on the landcover classification. Other pieces of knowledge such as mine reports, etc. are not directly related to classes of interest, but rather to the dangerous areas, and are thus included in the danger map construction, which follows the fusion. Several pieces of knowledge proved to be very useful at this step. For example, some detectors are available for roads and rivers, which provide areas or lines that surely belong to these classes. There is almost no confusion, but some parts can be missing. These detections can be imposed on the classification results. As for roads, additional knowledge is used, namely on the width of the roads (based on observations from the field missions). Since the detectors provide only lines, they are dilated by the appropriate size, taking into account both the actual road width and the resolution of the images. Another type of knowledge is also very useful: the detection of changes between images taken during the project and KVR images obtained earlier. The results of the change detection processing provide mainly information about class 1, since they exhibit the fields which were previously cultivated, and which are now abandoned. These results do not show all regions belonging to class 1, but the detected areas surely belong to that class, so these results can also be imposed to the classification results.
The final step is regularization, as it is very unlikely that isolated pixels of one class can appear in another class. Several local filters were tested, such as a majority filter, a median filter, or morphological filters, applied on the decision image. A Markovian regularization approach on local neighborhoods was tested too.
The results of this fusion in its basic version are already very good (Bloch et al., 2007), due to the fact that not all information provided by the classifiers is used, but only the best part of them. Further improvements are obtained by knowledge inclusion and regularization.
Two main humanitarian action types, close-range antipersonnel mine detection and remote sensing mined area reduction, are very sensitive tasks as they both deal with human lives, which puts high demands to the quality of the sensors involved, their efficiency, robustness, detection rate... Due to the variety of situations in which mines and minefields can be found, referring to different types of terrain, of mines, of mine laying, of weather conditions etc., it is hardly possible that one sensor can cover all these situations while reaching the high detection performance needed. Thus, a solution is being sought in multi-sensor fusion systems. Taking into account that typically there is a good knowledge about these two problems, while it is difficult or even impossible to come up with some statistically relevant training data, due to a high variability of the conditions in which mines and minefields can be found, knowledge-based theories are useful. Among these theories, possibilistic and fuzzy theory provides additional advantages, discussed in this chapter, such as different fusion operators depending on the information and its characteristics. This flexibility turns out to be very helpful for the two humanitarian action types due to different characteristics of the measures and sensors that are combined.
The application of fuzzy and possibility theory to humanitarian mine action presented in this chapter also covers a wide range of possible cases, starting from crisp classes (mines/friendly objects), where we have some uncertainty/imprecision in deriving a class from the measures, modelled as possibility discributions (Section 3), via the case when measures themselves are prone to imprecision so fuzzy measures are introduced in the possibilistic model (Section 4), up to the case where classes are fuzzy so we apply a fuzzy model (Section 5).
Although the presented modeling is related to sensors used in some of our projects (which are also sensors that are typically used for these problems worldwide), it is flexible enough to be easily adapted to new pieces of information about the types of objects and their characteristics, as well as to new sensors.