Watershed algorithm: Difference between revisions

From Tygron Support wiki
Jump to navigation Jump to search
No edit summary
 
(41 intermediate revisions by 4 users not shown)
Line 1: Line 1:
The Watershed algorithm has two variants, one based on absolute height values of the [[Digital terrain model|DTM]] and one based on a [[Surface direction result type (Water Overlay)|Water Overlay's Surface Direction]] result type.
In the study of image processing, a watershed<ref>https://en.wikipedia.org/wiki/Watershed_%28image_processing%29</ref> is a transformation defined on a grayscale image. Some of the proposed algorithms use the principle of flooding water on a DEM to identify individual watersheds, separated by borders of higher altitude.
 
One of the problems that often occur when generated watersheds is over-segmentation. Over-segmentation occurs when the elevation data contains many local minima. To overcome this issue, the elevation data is often smoothed to remove local minima and generate larger watersheds.
 
Our watershed algorithm is used for a slightly different purpose, namely identifying the watershed areas for predefined waterways. More generally, one is interested into which waterway a set of rain drops will end up based on the terrain elevation and the starting location of the drops.
 
Since we support the calculation of rainfall using our [[Water_Module|water module]] and can generate water flow direction results, we have altered the watershed algorithm to use the flow direction instead of the terrain elevation as input. Given that the rainfall used is adequately large, it helps us reducing the amount of local minima and hopefully generate more realistic results based on rainfall simulation.
 
==Variants==
The Watershed algorithm has two variants, one based on absolute height values of the [[DTM]] and one based on a [[Surface avg direction result type (Water Overlay)|Water Overlay's Surface Direction]] result type.


==Data initialization==
==Data initialization==
The basic watershed algorithm has been adjusted to allow users to mark [[Waterway (Terrain Type)|waterways]] and [[Water surface (Terrain Type)|water surfaces]] as uniquely identified minimas present at the start of the algorithm.  
The basic watershed algorithm has been adjusted to allow users to mark areas and [[Waterway|waterways]] and [[Water bodies|water bodies]] as unique discharge areas, present at the start of the algorithm.  


Additionally, culverts can be considered connections between waterways that can propagate these minima areas to waterways that are not initially marked.  
Additionally, culverts that connect waterways can be taken into account to automatically expand to free water cells and override discharge area of water cell created for waterways and waterbodies.


Optionally, the direction of the flow through the culvert can be considered to limit the expansion of minima areas to other waterways. In such case only the waterways that flow towards a waterway marked as a minima are also marked with the same unique minima id.
Optionally, the direction of the flow through the culvert can be taken into account to limit the expansion of discharge areas to other waterways. In such case if waterway A flow to B, then A can be overridden by B when A is a free water cell or an additional discharge area created for a waterway or -body.
 
The type of cells are stored as the [[Base types result type (Watershed Overlay)|Base types result]].


==Watershed Algorithm==
==Watershed Algorithm==
# Setup label (applied once): Convert Input data to cell references, in 8 directions. Cells without a direction angle become a plateau with a unique id.
The watershed algorithm consists of multiple steps. Each step, all cells are evaluated at the same time. Some steps are applied once. Others are applied multiple times, hence loop, until none of the cells were changed during that step.
# Label plateaus (loop until stable): Calls without a reference to other are re-evaluated. Such a cell will reference the first neighboring cell that flow away from it.
# Fix self directions (only once): Neighboring cells that reference each other, are both set back to being a plateau. They can now be seen as a minima.
The steps are:
# Store directions as a result type.
# '''Setup directions''' ''(applied once)'': Convert Input data to cell references, in 8 directions. Cells without a direction angle are marked as a plateau, which is a state that will be evaluated in the next steps.
# Set Minima IDs (only once): For cells that are marked as a plateau, mark them now as minima with a unique id.
# '''Convert plateaus to directions''' ''(loop until stable)'': Cells without a reference to others are re-evaluated. Such a cell will reference the first neighboring cell that flow away from it.
# Propagate minima IDs (loop until stable): Union minima cells ids, by giving them both the lowest ids of the two.
# '''Fix self directions''' ''(only once)'': Neighboring cells that reference each other, are both set back to being a plateau. They can now be identified as a unique discharge area, depending on the selected options.
# Store minima as a result type.
# '''Store [[Direction result type (Watershed Overlay)|directions]] as a result type'''.
# Flood (loop until stable): Cells referencing a cell with a (minima) label are updated to that same label id.
# '''Add discharge areas for remaining plateaus''' ''(optional, only once)'': For cells that are marked as a plateau, mark them now as a discharge area with a unique id depending on the selected options.
# Fill (loop until stable): Assign a label to an unlabeled cell based on first found neighbor with a label. Optionally limit this step to cells that are not roads.
# '''Propagate the created discharge area''' ''(optional, loop until stable)'': In case two neighboring cells are both discharge areas, combine them by selecting the lowest ids of the two.
# '''Store [[Discharge areas result type (Watershed Overlay)|discharge areas]] as a result type''': These can now contain both the initial and the created ones.
# '''Flood''' ''(loop until stable)'': Cells referencing a cell with a discharge area id are updated to that same id.
# '''Fill''' ''(loop until stable)'': Assign a watershed to cells that neighbor a watershed and that do not yet belong to a watershed. Optionally [[Limit road (Watershed Overlay)|limit]] this step to cells that are not roads.
# '''Store [[Watersheds result type (Watershed Overlay)|watersheds]] and [[Base types result type (Watershed Overlay)|base types]] results'''.


==Notes==
==Notes==
* The watershed algorithm implementation is an adapted version of the algorithm proposed by Vitor et. al. <ref>Vitor, Giovani & Körbes, André & Lotufo, Roberto & Ferreira, Janito. (2010). Analysis of a Step-Based Watershed Algorithm Using CUDA. IJNCR. 1. 16-28. 10.4018/jncr.2010100102. </ref>.
* The watershed algorithm implementation is an adapted version of the algorithm proposed by Vitor et. al. <ref>Vitor, Giovani & Körbes, André & Lotufo, Roberto & Ferreira, Janito. (2010). Analysis of a Step-Based Watershed Algorithm Using CUDA. IJNCR. 1. 16-28. 10.4018/jncr.2010100102. </ref>.
* A plateau is a cell without a reference to other cells and without a unique label id. It can become either a:
* The algorithm uses 3 types of cells:
** border cell, which will reference cells directing away from it;
** discharge area cells, either initial or created by the algorithm;
** minima cell, which will receive a unique id.
** directional cells, either initial or calculated by the algorithm;
* Direction in the Fill step does not matter at this stage, because it would have been labeled otherwise. Cells can remained unlabeled when restrictions are put on the minima labeled.
** plateau cells, identified by have no direction or by neighboring cells referencing each other. It can become either a:
*** directional cell, which will reference cells directing away from it;
*** discharge area cell, which will receive a unique id.
* The cells that are updated during the Flood step depend in the direction as well on the selected options. If the creation of additional discharge areas was not allowed, certain sections will not belong to a watershed.
* Directions from previous steps are ignored in the Fill step. Instead, cells that do not belong to a watershed are updated to a neighboring watershed, unless the cell is a road and the option [[Limit road (Watershed Overlay)|Limit road]] is selected. When that setting is active, the watershed expansion in the fill step will not pass roads.


===Tips===
==Tips==
* When using a Water Overlay's Flow direction result as an input for the Watershed Overlay, it is important to consider what rain settings are used. Generally, you want select a rainfall big enough for local minima, due to small depressions in the terrain, to disappear. On the other side, the rainfall should not be too big for the marked ditches it should end up in.
* When using a Water Overlay's Flow direction result as an input for the Watershed Overlay, it is important to consider what rain settings are used. Generally, you want to select a rainfall big enough for local minima due to small depressions in the terrain to disappear. On the other side, the rainfall should not be too big for the marked ditches it should end up in.


===References===
==See also==
* [[Watershed Module Theory]]
 
==References==
<references/>
<references/>
===See also===

Latest revision as of 13:40, 2 February 2024

In the study of image processing, a watershed[1] is a transformation defined on a grayscale image. Some of the proposed algorithms use the principle of flooding water on a DEM to identify individual watersheds, separated by borders of higher altitude.

One of the problems that often occur when generated watersheds is over-segmentation. Over-segmentation occurs when the elevation data contains many local minima. To overcome this issue, the elevation data is often smoothed to remove local minima and generate larger watersheds.

Our watershed algorithm is used for a slightly different purpose, namely identifying the watershed areas for predefined waterways. More generally, one is interested into which waterway a set of rain drops will end up based on the terrain elevation and the starting location of the drops.

Since we support the calculation of rainfall using our water module and can generate water flow direction results, we have altered the watershed algorithm to use the flow direction instead of the terrain elevation as input. Given that the rainfall used is adequately large, it helps us reducing the amount of local minima and hopefully generate more realistic results based on rainfall simulation.

Variants

The Watershed algorithm has two variants, one based on absolute height values of the DTM and one based on a Water Overlay's Surface Direction result type.

Data initialization

The basic watershed algorithm has been adjusted to allow users to mark areas and waterways and water bodies as unique discharge areas, present at the start of the algorithm.

Additionally, culverts that connect waterways can be taken into account to automatically expand to free water cells and override discharge area of water cell created for waterways and waterbodies.

Optionally, the direction of the flow through the culvert can be taken into account to limit the expansion of discharge areas to other waterways. In such case if waterway A flow to B, then A can be overridden by B when A is a free water cell or an additional discharge area created for a waterway or -body.

The type of cells are stored as the Base types result.

Watershed Algorithm

The watershed algorithm consists of multiple steps. Each step, all cells are evaluated at the same time. Some steps are applied once. Others are applied multiple times, hence loop, until none of the cells were changed during that step.

The steps are:

  1. Setup directions (applied once): Convert Input data to cell references, in 8 directions. Cells without a direction angle are marked as a plateau, which is a state that will be evaluated in the next steps.
  2. Convert plateaus to directions (loop until stable): Cells without a reference to others are re-evaluated. Such a cell will reference the first neighboring cell that flow away from it.
  3. Fix self directions (only once): Neighboring cells that reference each other, are both set back to being a plateau. They can now be identified as a unique discharge area, depending on the selected options.
  4. Store directions as a result type.
  5. Add discharge areas for remaining plateaus (optional, only once): For cells that are marked as a plateau, mark them now as a discharge area with a unique id depending on the selected options.
  6. Propagate the created discharge area (optional, loop until stable): In case two neighboring cells are both discharge areas, combine them by selecting the lowest ids of the two.
  7. Store discharge areas as a result type: These can now contain both the initial and the created ones.
  8. Flood (loop until stable): Cells referencing a cell with a discharge area id are updated to that same id.
  9. Fill (loop until stable): Assign a watershed to cells that neighbor a watershed and that do not yet belong to a watershed. Optionally limit this step to cells that are not roads.
  10. Store watersheds and base types results.

Notes

  • The watershed algorithm implementation is an adapted version of the algorithm proposed by Vitor et. al. [2].
  • The algorithm uses 3 types of cells:
    • discharge area cells, either initial or created by the algorithm;
    • directional cells, either initial or calculated by the algorithm;
    • plateau cells, identified by have no direction or by neighboring cells referencing each other. It can become either a:
      • directional cell, which will reference cells directing away from it;
      • discharge area cell, which will receive a unique id.
  • The cells that are updated during the Flood step depend in the direction as well on the selected options. If the creation of additional discharge areas was not allowed, certain sections will not belong to a watershed.
  • Directions from previous steps are ignored in the Fill step. Instead, cells that do not belong to a watershed are updated to a neighboring watershed, unless the cell is a road and the option Limit road is selected. When that setting is active, the watershed expansion in the fill step will not pass roads.

Tips

  • When using a Water Overlay's Flow direction result as an input for the Watershed Overlay, it is important to consider what rain settings are used. Generally, you want to select a rainfall big enough for local minima due to small depressions in the terrain to disappear. On the other side, the rainfall should not be too big for the marked ditches it should end up in.

See also

References

  1. https://en.wikipedia.org/wiki/Watershed_%28image_processing%29
  2. Vitor, Giovani & Körbes, André & Lotufo, Roberto & Ferreira, Janito. (2010). Analysis of a Step-Based Watershed Algorithm Using CUDA. IJNCR. 1. 16-28. 10.4018/jncr.2010100102.