Difference between revisions of "ALGORITHMS"

From MyDewetra World
Jump to: navigation, search
(→‎Algorithms description)
 
(47 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
[[File:example7.jpg|right|100px|caption]]
 
[[GFMS | [Home]]]
 
[[GFMS | [Home]]]
 
----
 
----
  
−
''Note: this section provides a concise description of the algorithms deployed by GFMS partners. <br>
 
−
For a more comprehensive documentation the reader is referred to the '''GFMS Product Description Documentation (PDD)'''.''
 
  
−
='''HASARD (LIST)'''=
+
'''GFM''' 's flood products are based on an ''ensemble approach'' integrating three robust, cutting edge algorithms developed independently by three leading research teams. <br>
−
LIST’s HASARD mapping algorithm enables an automatic and reliable spaceborne Synthetic Aperture Radar-based (SAR) mapping of terrestrial water bodies (Matgen et al., 2011, Giustarini et al., 2015, Chini et al., 2017). The application was initially designed to enable an ‘on demand’ mapping of water bodies to support emergency response and disaster risk reduction at large scale. In addition, its latest evolution now allows for an ‘always on’ systematic monitoring of flood and water extent variations at high spatial and temporal resolution (Chini et al., 2020). The most recent version of the algorithm can be applied to process multi-temporal stacks of SAR images and used to update water and flood extent maps in NRT as new images are acquired, pre-processed and added to the data cube. The algorithm can also be used to re-process collections of SAR images to generate a record of historic flood and water extent maps (Chini et al., 2020). One characteristic of this approach is that it exploits at the same time contextual information through region growing and multi-temporal information through change detection. […] <br>
+
The motivation for choosing such a methodology is to substantially improve accuracy of the derived Sentinel-1 flood and water extent maps and to build a high degree of redundancy into the production service.  
−
'''Key points'''<br>
 
−
HASARD is based on a scientifically validated and patented technology enabling a systematic, automatic and high-accuracy monitoring of water bodies using Sentinel-1 data. The algorithm uses a highly innovative sequence of hierarchical image splitting, statistical modelling and region growing to delineate and classify areas that changed their flooding-related backscatter response between two image acquisitions from the same orbits. <br>
 
−
'''Uncertainty'''<br>
 
−
The LIST algorithm for probabilistic flood mapping is based on Bayesian inference. Following the procedure introduced in Giustarini et al. (2016), the probability of each pixel in any newly acquired SAR image being flooded given its measured backscatter value is estimated in NRT. The approach is based [...]<br>
 
−
'''References'''<br>
 
−
(Matgen et al., 2011, Giustarini et al., 2015, Chini et al., 2017).
 
  
−
='''S-1FS (DLR)'''=
+
As stated elsewhere, the data processing architecture underlying the different scientific algorithms is based on the [https://en.wikipedia.org/wiki/Data_cube ''data cube''] concept, whereby SAR images are geocoded, gridded and stored as analysis ready data (ARD) in an existing spatio-temporal SAR [https://en.wikipedia.org/wiki/Data_cube ''data cube'']. <br>
−
This Sentinel-1 Flood Service (S-1FS) is part of DLR’s operational multi-sensor flood monitoring system, which consists in addition of automatic flood processing chains based on TerraSAR-X, Sentinel-2 and Landsat-8 data. Currently, DLR’s Sentinel-1-based flood mapping approach is integrated within a fully automatic processing chain which consists of automatic data ingestion, pre-processing of the Sentinel-1 data, computation and adaption of global auxiliary data (digital elevation models, topographic indices, low backscatter exclusion mask as well as reference water mask), classification of the flood extent, and dissemination of the crisis information, e.g. via a web-client. The processing chain can be easily transferred into the envisaged GFM system as described in the following.  
+
By using a data cube, where the temporal and spatial dimensions are treated alike, each Sentinel-1 image can be compared with the entire backscatter history, allowing to implement different sorts of change detection algorithms in a rather straightforward manner. Importantly, the entire backscatter time series can be analysed for each pixel. Therefore, model training and calibration may be carried out systematically for each pixel. <br>
−
For the unsupervised initialization of the flood and water extent classification in pre-processed intensity Sentinel-1 data a parametric tile-based thresholding procedure is applied by labelling all pixels with a backscatter value lower than a threshold to the class “water”. This method has been originally developed for flood mapping using TerraSAR-X and TanDEM-X data by Martinis et al. (2009, 2015), and has been adapted to the systematic data stream of the Sentinel-1 mission by Twele et al. (2016).<br>
+
The advantages of working with data cubes are:
−
'''Key points'''<br>
+
*'''(a)''' algorithms are better able to handle land surface heterogeneity;
−
The key strength of this algorithm is the automatic identification of flooded areas in the SAR data using hierarchical tile-based thresholding and the optimization of the classification by combining various information sources using fuzzy-logic theory and region growing. <br>
+
*'''(b)''' uncertainties can be better specified;
−
'''Uncertainty'''<br>
+
*'''(c)''' regions where open water cannot be detected for physical reasons (e.g. dense vegetation, urban areas, deserts), can be determined a priori,
−
The fuzzy-logic based water class membership assignment is a part of a flood classification refinement step described in Martinis et al. (2015) and Twele et al. (2016). It aims to exclude water-lookalikes and to reduce underestimations from initial classification by constructing a fuzzy set that consists of (a) the backscatter level, (b) the elevation of an image element in comparison to the mean elevation of the initially derived water areas, (c) topographic slope information, and (d) the size of an individual flood object; degree of an element’s membership to the class water is determined by standard S and Z membership [...] <br>
+
*'''(d)''' historic water extent maps can be derived, essentially as a by-product of the model calibration, which may serve as a reference for distinguishing between floods and the normal seasonal water extent.
−
'''References'''<br>
 
−
Martinis et al. (2009, 2015)
 
  
−
='''Sentinel-1 flood mapping (TU Wien)'''=
+
The (internal) availability of three separate flood and water extent maps tackles, by readily identifying them, the shortcomings a single algorithm, by itself, might be suffering of in specific circumstances and/or part of the world due to many well-known factors like topography or environmental conditions.  
−
The TU Wien Sentinel-1 flood mapping algorithm is a fully automatic, pixel-based flood extent mapping workflow which exploits time series of historical backscatter measurements. The backscatter time series are used twice: first to establish a pixel-wise backscatter distribution during non-flooded conditions and second to estimate a water backscatter distribution by collecting backscatter values from open water bodies at different locations. Based on these two distributions, it is possible to derive the posterior probability of corresponding to water or non-water by means of Bayesian Inference. Applying the Bayes Decision Rule finally leads to a class allocation for each pixel and implicitly allows establishing an uncertainty measure.<br>
 
−
'''Key points''' <br>
 
−
This algorithm fully exploits the entire Sentinel-1 signal history within the data cube, realized by a set of a-priori computed statistical parameters layers that provide a highly accurate characterization of Earth’s land surface at pixel level, as well as of the incidence angle dependency in respect to the Sentinel-1 mission. With those parameters as input, and with the mathematical legacy of Bayes, the water delineation procedure can be designed computationally relatively slim and is hence most suitable for global operations in NRT. <br>
 
−
'''Uncertainty''' <br>
 
−
TU Wien’s S-1 flood mapping algorithm exploits the time series of historical backscatter measurements to generate model parameters for permanent water bodies and for each individual location on land. More specifically, the model parameter database comprises of the backscatter distribution of each land pixel under unflooded conditions, as well as the backscatter distribution of permanent water bodies at various incidence angles. In order to classify a pixel of incoming pre-processed Sentinel-1 scene as flooded or non-flooded, the posterior probability of the actual backscatter value belonging to each class is computed. The maximum posterior probability is used to classify the pixel based on Bayes Decision Rule, where the  […]
 
−
<br>
 
−
'''References'''<br>
 
−
YYYYZZZZ
 
  
−
='''Ensemble flood algorithm'''=
+
For these very reasons, Users have access to [[S-1_Observed_Flood_Extent | '' '''consensus flood maps''']] '' where a pixel is marked as ''flooded'' when at least two algorithms classify it as water. <br>
−
The three algorithms will run in parallel and have access to the same pre-processed Sentinel-1 input data. Next, the three generated flood and water extent maps are systematically combined into a single product (i.e. “consensus map”). To generate the combined product, each pixel is attributed the ratio of the number of classifications as flooded to the number of algorithms that were applied. A number of 1 would mean that all three algorithms agreed on its classification as flooded. The final classification is straightforward and based on a majority decision, i.e. a pixel is accepted as flooded when at least two algorithms classify it as water. As a result, all other pixels of the Sentinel-1 footprint and not included in a pre-computed exclusion mask are classified as unflooded. In the unlikely scenario that one or two algorithms fail to produce a result, the results of a single algorithm will be used to compute the final map. In case of a split decision between two algorithms, preference will be given to the algorithm that produced the highest CSI score during the quality assurance procedure.
+
Accordingly, the implemented quality assurance procedures (see <span style=background:yellow>'''INSERT REFERENCE'''</span>) allow for differentiating between classification errors that can be attributed to shortcomings of individual algorithms and errors that are inherent to the SAR sensing instruments and their difficulty to capture the appearance or disappearance of surface water in particular situations.
−
'''Key points''' <br>
 
−
The ensemble algorithm integrates the results of three leading edge classification algorithms into a single product. It combines in a single approach the most advanced processing steps currently used in the field of SAR-based flood and water extent mapping (i.e. parameter optimization based on time series analysis at local and regional scale, region growing, combination of SAR intensity and ancillary data such as topography, etc.). The consensus product substantially improves the robustness and accuracy of the final product, in addition to building a high degree of redundancy into the production service. <br>
 
−
'''Uncertainty''' <br>
 
−
The ensemble uncertainty algorithm expresses the level of trust in the final, harmonized classification, based on equally weighted contributions from all three flood extent detection algorithms. Given differences in the expression of uncertainty in each of the individual processes, the motivation behind the ensemble uncertainty algorithm is to generate a single, easily interpretable classification uncertainty value for end users as a practical measure of confidence in the flood map product.
 
−
First, uncertainty information from each of the individual algorithms is expressed in the same numerical range [0, 100] to ensure comparability and to facilitate further harmonization. In particular, probabilistic values from the LIST algorithm and fuzzy membership values from the DLR algorithm are first converted into classification uncertainty and next multiplied by a factor of 100. For DLR algorithm, since fuzzy membership values are only assigned to water pixels, all unflooded pixels are assigned a value of 0. The conversion of these probabilistic (resp. fuzzy membership) values is carried out as U = Wi * (100 - Pi) + (1 - Wi) * Pi, where [...] <br>
 
−
'''References'''<br>
 
−
???
 
  
−
----
+
===Algorithms description===
−
[[GFMS | [Home]]]
+
A detailed description of the three algorithms and examples of applications in an operational context is provided in the '''PDD''', this sections and the following links provide their keypoints <br>
 +
 
 +
All the three algorithms make use of historical time series of SAR intensity data and use topography-derived indices to refine the initial classification of water bodies. However, differences appear in the ways historical time series of intensity data are finally used to parameterize the retrieval algorithms and the way ancillary data such as topography data are used in the production system. <br>
 +
Other differences relate to the inclusion of a region growing step or not, the scale at which the thresholds are determined and applied to each pixel’s backscatter value and other nuances in the way the retrieval algorithms are setup.
 +
 
 +
The most relevant features of the algorithms are summarized in the table below.
 +
 
 +
{| class="wikitable" style="margin: auto;"
 +
!
 +
!Hasard <br> [[File:list.jpg|centre|50px]]
 +
!Algorithm2 <br> [[File:tuw.jpg|centre|20px]]
 +
!Algorithm3 <br> [[File:dlr.jpg|centre|30px]]
 +
|-
 +
|style="width: 20%" | '''Application domain'''
 +
|style="width: 25%" |Water and flood extent mapping (pixel-based)
 +
|style="width: 25%" |NRT Water and flood extent mapping
 +
|style="width: 25%" |Pixel-based water and flood extent mapping
 +
|-
 +
|'''Input remote sensing data'''
 +
|Pair of SAR intensity images acquired from same orbit (any sensor) and model parameters derived from historical time series
 +
|Single-temporal SAR intensity data
 +
|Single SAR acquisition and model parameters derived from historical time series
 +
|-
 +
|'''Auxiliary data'''
 +
|HAND index map, exclusion layer, reference water layer, water and flood extent map computed at previous time step
 +
|HAND index exclusion map, reference water extent, DEM, optional: low backscatter exclusion mask based on S-1 time-series data
 +
|HAND index, exclusion mask, reference water map for generating the fresh flooded areas
 +
|-
 +
|'''Characteristic features'''
 +
|Scene-specific statistical modelling of backscatter distributions, systematic updating of water bodies maps using combination of change detection and region growing
 +
|Hierarchical automatic tile-based thresholding, fuzzy logic-based post classification and region growing
 +
|Classification based on backscatter probability distribution by exploiting the historical time series with consideration of backscatter seasonality.
 +
|-
 +
|'''Exploitation of time series of SAR observations'''
 +
|Yes
 +
|No, the integration of a low backscatter exclusion mask based on S-1 time-series data (produced offline) can be integrated optionally
 +
|Yes, parametrisation through multi-year time series
 +
|-
 +
|'''Exploitation of textual information through region growing'''
 +
|Yes
 +
|Yes
 +
|No
 +
|-
 +
|'''Automation'''
 +
|High
 +
|High
 +
|High
 +
|-
 +
|'''Initialization'''
 +
|Statistical modelling of backscatter distributions attributed to water / no water and change / no change classes (per tile)
 +
|Hierarchical automatic tile-based thresholding using statistical modelling of class distributions
 +
|Generation of backscatter probability distribution from historical time series measurements
 +
|-
 +
|'''Post-classification steps'''
 +
|Masking of exclusion areas, distinction between water and flood extent using reference water layer
 +
|Masking of exclusion areas, distinction between water and flood extent using reference water layer
 +
|Noise reduction, Mask the exclusion areas, extraction fresh flood area compared with reference water map
 +
|-
 +
|'''Water probability mask generated'''
 +
|Yes (based on Bayesian inference)
 +
|Yes (based on fuzzy logic)
 +
|Yes (based on the Bayesian posterior probability)
 +
|-
 +
|'''Outstanding/differentiating features'''
 +
|Hierarchical split-based approach enabling re-calibration of parameters in NRT based on most recent pair of S-1 images
 +
|Fuzzy logic-based approach enabling a post classification and region growing taking advantage of topography-derived indices in addition to SAR backscatter
 +
|Exploiting per-pixel full Sentinel-1 signal history in data cube; enabling a very fast and scalable production of flood and water extent maps through pre-computed global parameters at high quality
 +
|-
 +
|'''Additional information'''
 +
|[[HASARD | further details on HASARD]]
 +
|[[ALGORITHM2 | further details on Algorithm2]]
 +
|[[ALGORITHM3 | further details on Algorithm3]]
 +
|-
 +
|}

Latest revision as of 10:45, 25 March 2021

caption

[Home]


GFM 's flood products are based on an ensemble approach integrating three robust, cutting edge algorithms developed independently by three leading research teams.
The motivation for choosing such a methodology is to substantially improve accuracy of the derived Sentinel-1 flood and water extent maps and to build a high degree of redundancy into the production service.

As stated elsewhere, the data processing architecture underlying the different scientific algorithms is based on the data cube concept, whereby SAR images are geocoded, gridded and stored as analysis ready data (ARD) in an existing spatio-temporal SAR data cube.
By using a data cube, where the temporal and spatial dimensions are treated alike, each Sentinel-1 image can be compared with the entire backscatter history, allowing to implement different sorts of change detection algorithms in a rather straightforward manner. Importantly, the entire backscatter time series can be analysed for each pixel. Therefore, model training and calibration may be carried out systematically for each pixel.
The advantages of working with data cubes are:

  • (a) algorithms are better able to handle land surface heterogeneity;
  • (b) uncertainties can be better specified;
  • (c) regions where open water cannot be detected for physical reasons (e.g. dense vegetation, urban areas, deserts), can be determined a priori,
  • (d) historic water extent maps can be derived, essentially as a by-product of the model calibration, which may serve as a reference for distinguishing between floods and the normal seasonal water extent.

The (internal) availability of three separate flood and water extent maps tackles, by readily identifying them, the shortcomings a single algorithm, by itself, might be suffering of in specific circumstances and/or part of the world due to many well-known factors like topography or environmental conditions.

For these very reasons, Users have access to consensus flood maps where a pixel is marked as flooded when at least two algorithms classify it as water.
Accordingly, the implemented quality assurance procedures (see INSERT REFERENCE) allow for differentiating between classification errors that can be attributed to shortcomings of individual algorithms and errors that are inherent to the SAR sensing instruments and their difficulty to capture the appearance or disappearance of surface water in particular situations.

Algorithms description

A detailed description of the three algorithms and examples of applications in an operational context is provided in the PDD, this sections and the following links provide their keypoints

All the three algorithms make use of historical time series of SAR intensity data and use topography-derived indices to refine the initial classification of water bodies. However, differences appear in the ways historical time series of intensity data are finally used to parameterize the retrieval algorithms and the way ancillary data such as topography data are used in the production system.
Other differences relate to the inclusion of a region growing step or not, the scale at which the thresholds are determined and applied to each pixel’s backscatter value and other nuances in the way the retrieval algorithms are setup.

The most relevant features of the algorithms are summarized in the table below.

Hasard
List.jpg
 Algorithm2
Tuw.jpg
 Algorithm3
Dlr.jpg
Application domain Water and flood extent mapping (pixel-based) NRT Water and flood extent mapping Pixel-based water and flood extent mapping
Input remote sensing data Pair of SAR intensity images acquired from same orbit (any sensor) and model parameters derived from historical time series Single-temporal SAR intensity data Single SAR acquisition and model parameters derived from historical time series
Auxiliary data HAND index map, exclusion layer, reference water layer, water and flood extent map computed at previous time step HAND index exclusion map, reference water extent, DEM, optional: low backscatter exclusion mask based on S-1 time-series data HAND index, exclusion mask, reference water map for generating the fresh flooded areas
Characteristic features Scene-specific statistical modelling of backscatter distributions, systematic updating of water bodies maps using combination of change detection and region growing Hierarchical automatic tile-based thresholding, fuzzy logic-based post classification and region growing Classification based on backscatter probability distribution by exploiting the historical time series with consideration of backscatter seasonality.
Exploitation of time series of SAR observations Yes No, the integration of a low backscatter exclusion mask based on S-1 time-series data (produced offline) can be integrated optionally Yes, parametrisation through multi-year time series
Exploitation of textual information through region growing Yes Yes No
Automation High High High
Initialization Statistical modelling of backscatter distributions attributed to water / no water and change / no change classes (per tile) Hierarchical automatic tile-based thresholding using statistical modelling of class distributions Generation of backscatter probability distribution from historical time series measurements
Post-classification steps Masking of exclusion areas, distinction between water and flood extent using reference water layer Masking of exclusion areas, distinction between water and flood extent using reference water layer Noise reduction, Mask the exclusion areas, extraction fresh flood area compared with reference water map
Water probability mask generated Yes (based on Bayesian inference) Yes (based on fuzzy logic) Yes (based on the Bayesian posterior probability)
Outstanding/differentiating features Hierarchical split-based approach enabling re-calibration of parameters in NRT based on most recent pair of S-1 images Fuzzy logic-based approach enabling a post classification and region growing taking advantage of topography-derived indices in addition to SAR backscatter Exploiting per-pixel full Sentinel-1 signal history in data cube; enabling a very fast and scalable production of flood and water extent maps through pre-computed global parameters at high quality
Additional information further details on HASARD further details on Algorithm2 further details on Algorithm3
Retrieved from "https://wikisrv.cimafoundation.org/index.php?title=ALGORITHMS&oldid=1305"