Fill sinks
Algorithm
The Fill sinks operation removes local depressions from a DEM by replacing these local depressions by flat areas in the output DEM.
Process:
- Removal of depressions that consist of a single pixel (local pits, i.e. any pixel with a smaller height value than its 8 neighbouring pixels):
When a single pixel is encountered that has a smaller height value than all of its 8 neighbours (Fig. 1a);
- then the height value of this pixel will be increased to the smallest value of its 8 neighbour pixels (Fig. 1b).
Figure 1a: Find a sink that consists of a single pixel (pixel in red). |
|
Figure 1b: Assign to this pixel, the smallest value found among its 8 neighbour pixels (pixel in green). |
|
|
|
- Removal of depressions that consist of multiple pixels (i.e. any group of adjacent pixels where the pixels have smaller height values than all pixels that surround such a depression):
General process:
When a group of adjacent pixels is encountered where the pixels have smaller height values than all neighbours of this group;
- all pixels are determined that contribute to this depression; this is an iterative process, involving another 'ring' of neighbours when required,
- the outlet for this depression is determined,
- finally the height values of this depression will be increased to the smallest height value of a pixel
- that is adjacent to the outlet for this depression/sink, and
- that would contribute to the initial sink.
Detailed process:
- Scan the DEM, from top to bottom and from left to right, to find the first pixel that is part of a sink area (Fig. 2a).
In other words, find a pixel with lower or equal height value than all its 8 neighbours.
- Determine all pixels that contribute to this particular sink (Fig. 2b).
In other words, find the catchment area of this sink; iterative process evaluating height values of outward neighbours.
- Locate the outlet pixel for this sink and determine the value of the pixel just 'before' the outlet (Fig. 2c).
- For all pixels within the outer 'ring' of sink-catchment pixels (as found in the previous step), evaluate the values of their neighbouring pixels that are outside the ring of sink-catchment pixels.
- Determine the neighbour (outside the ring) with the smallest value; this is the outlet pixel.
Then:
- From the outlet pixel, evaluate the values of neigbouring pixels that are within the ring of sink-catchment pixels.
- Determine the neighbour (inside the ring) with the smallest value; this is the pixel before the outlet.
- Keep the height value of this pixel in mind.
- For all pixels that contribute to this sink and that have a value smaller than the value that was kept in mind in step 2c,
assign these pixels the height value found in step 2c (Fig. 2d).
In other words, sinks are 'filled up' so that flat areas are formed which will definitely have an outlet.
- Mark all pixels of the catchment that was currently handled, so that these pixels will not be scanned again.
- Continue scanning the DEM to find another initial sink.
Additional rules:
The height values of the following pixels will never be changed in the output map:
- pixels at the border of the map,
- pixels that have the undefined value,
- pixels that are adjacent to pixels with the undefined value.
Figures explaining the detailed process of filling depressions of multiple pixels:
Figure 2a: Find first sink (pixel in black). |
|
Figure 2b: Find all pixels that contribute to this sink (colored pixels). |
|
|
|
Figure 2c: Determine the outlet for this sink (pixel in black), and determine the pixel just before the outlet (pixel in blue). Keep the value of the pixel just before the outlet in mind (value 3). |
|
Figure 2d: To all pixels that contribute to this sink and which have a smaller value than the value kept in mind in 2c, assign the height value kept in mind in 2c (pixels in black). |
|
|
|
See also:
Fill sinks : functionality