WorksComputer Science
Selecting cells in a raster database for maximal impact intervention in the presence of spatial interaction: Computational complexity of a Multiple vs. a Single Flow Direction Method
Abstract
To minimize the sediment flowing to the outlet of a river catchment with minimal effort or cost, it is important to select the best areas to perform a certain intervention, e.g., afforestation. CAMF (Cellular Automata based heuristic for Minimizing Flow) is a method that performs this selection process iteratively in a raster geodatabase environment. To simulate the flow paths, the original CAMF uses a Single Flow Direction (SFD) algorithm. However, SFD fails to reflect the real nature of flow transport, especially in areas with low relief. This paper describes and analyzes the integration of a Multiple Flow Direction (MFD) algorithm in CAMF, in order to provide a more realistic flow simulation. We compare the computational complexity of CAMF-SFD and CAMF-MFD and we discuss the scalability w.r.t. the number of cells involved. We evaluate the behavior of both variants for sediment yield minimization by afforestation in two catchments with different properties.
CRediT authorship contribution statement
Grethell Castillo-Reyes: Study, Conceptualization, Design, Software development, Analysis and interpretation of results, Writing. René Estrella: Generation of data, Analysis and interpretation of results, Review. Karen Gabriels: Generation of data. Jos Van Orshoven: Conceptualization, Supervision, Analysis and interpretation of results. Floris Abrams: Generation of data, Review. Dirk Roose: Conceptualization, Design, Methodology, Supervision, Analysis and interpretation of results, Review, Writing.
Introduction
Among the main issues analyzed in Spatial Decision Support Systems, land use planning is of vital importance. It comprises the management and modification of the natural environment, focusing on developing effective strategies for land conservation and urbanization [25]. It allows to select potential sites to carry out a certain action, taking into account criteria related to the use of the land depending on the application.
Sediment delivery to rivers reduces channel and reservoir capacity and also leads to water quality problems and biodiversity decline because of suspended mineral and organic substances [9]. These issues are particularly undesirable in regions where the river is used for drinking or irrigation water provision or for electricity production.
Afforestation has proven to be effective to reduce sediment production and delivery and to alleviate the associated water quality problem [6, 20, 17, 33]. It is known to decrease runoff and protect the soil surface against the ability of raindrops and runoff to detach and transport sediments [2, 22]. A main question at the beginning of any afforestation project is to identify the most suitable sites to plant the trees. The discrimination between suitable and unsuitable areas for afforestation typically depends on several criteria adopted by forest planners, which can range from on-site and off-site environmental concerns to maximizing financial profits.
This spatial optimization problem can be formulated as a mathematical programming model that can be solved exactly, but typically requires a high amount of computational resources [13]. While this approach has been used for many years in e.g., forest planning [36], the size of the problems that can be handled in a practical way remains limited [31]. Therefore, as an alternative, Vanegas [28]; Vanegas et al. [29, 32] proposed a Cellular Automata based heuristic for Minimizing Flow (CAMF) to locate the sites within a river catchment that should be afforested in order to minimize the amount of sediment that reaches the outlet. Although finding the optimal solution cannot be guaranteed in general for an heuristic method, they proved theoretically that CAMF obtains the optimal solution for a small raster under certain conditions. To simulate sediment transport CAMF uses a simple spatially distributed model, which is computationally efficient in order to be used in an optimization context.
A key issue in sediment flow simulation with CAMF is the spatial interaction (SI) among cells in the raster datasets, representing the catchment. SI refers to the fact that changes in the state of a location can have an impact on the state of neighboring or even distant locations [15, 34]. In the case of CAMF, SI refers to the phenomenon that afforestation of a cell leads to changes of its characteristics that in turn affect the amount of sediment flowing from that cell into its downstream neighbor cells and eventually the sediment yield of the catchment.
The original implementation of CAMF uses a Single Flow Direction (SFD) model, which assumes that flow leaving a cell is delivered entirely to the neighbor at the lowest altitude. Despite the advantage of simplicity of SFD models, it has been suggested that they fail to reflect the real nature of surface transport processes [24, 37]. Quinn et al. [24] proposed a Multiple Flow Direction (MFD) model, which are based on the assumption that flow is distributed to one or more of the neighboring downslope cells. This model can represent sediment flow pathways more appropriately than SFD. With SFD even a tiny elevation difference between two neighboring cells can have a large effect, since it might determine which cell receives all outgoing flow. Comparatively, small elevation differences have a less important effect in an MFD algorithm, since cells with slight differences in elevation receive about the same amount of flow.
In this paper, we develop and analyze the MFD variant of CAMF (CAMF-MFD) and we show why the computational cost substantially increases. Several experiments were carried out using different data-sets, with the aim of comparing the behaviour and performance of the two variants of CAMF.
This paper is organized as follows. Section 2 provides a general description of CAMF, the calculation of the sediment accumulation matrix and the main steps followed by CAMF to select the best areas for afforestation. It also describes particular characteristics of CAMF-SFD and its reformulation to use a MFD method. Section 3 presents the case studies used for experiments. In Section 4 the results of experiments are discussed and Section 5 presents some conclusions.
CAMF method for minimizing sediment flow
Using a rasterized database representing a river catchment, the CAMF method [28, 29, 32] selects cells, such that performing a certain action in these cells leads to the maximum reduction of the sediment yield, i.e. the amount of sediment in the outlet, denoted by . The cells are selected from a list of candidate cells, since the action can be performed only in cells corresponding to some land use types. Because of SI, cells are selected iteratively. In each iteration, CAMF computes for every candidate cell the sediment yield reduction, denoted by , that will be achieved if the action is performed in that cell. The candidate cells are ranked based on their values. The action is performed in the cell(s) with the maximum . Although the core structure of CAMF can be applied for different sorts of flow, until now CAMF has been used exclusively for afforestation planning. Therefore we will now describe CAMF in the context of afforestation.
The input data required by CAMF consist of several raster data-sets, each of them representing one characteristic of the area under study:
Digital Elevation Model (DEM) to compute the gradients and the flow direction matrix to determine the flow paths that sediment follows within a catchment.
Land-use types map or coverage map to identify the cells on which action can be taken.
Initial local sediment production () before and after afforestation, for each cell.
The user also specifies the number of cells to be selected or the required amount of .
We now present more details of the two main processes in CAMF: (1) the computation of the base flow, i.e., the initial sediment accumulation matrix, denoted by , see § 2.1-§ 2.3, and (2) the iterative process for the identification of the best cells to perform a certain action (e.g., afforestation) in order to minimize the flow reaching the outlet, see § 2.4.
Sediment Accumulation
The matrices storing the local sediment production before and after afforestation are denoted respectively by and , while , denote the local sediment production in cell . The Sediment Accumulation matrix gives for each cell the total amount of sediment , i.e., plus the sediment received by that cell from its up-slope neighbours.
The amount of sediment that leaves cell , denoted by , is a function of . Currently CAMF uses a piece-wise linear convex function [30], depending on three parameters: retention capacity , saturation threshold and flow factor , where if the cell is not yet afforested and if the cell is afforested.
If is below its retention capacity , no sediment leaves the cell. If , a fraction of leaves the cell. If is above the saturation threshold , the exceeding amount of sediment is fully delivered from the cell.
Hence is modeled by
The amount of sediment transported between cells and , denoted by , is calculated as
with the amount of sediment that leaves cell , calculated using Eq. (1) and the fraction of sediment flowing from cell to cell .
In case of afforestation, the parameters determining the piece-wise linear convex function change when the land use of a cell is converted from its initial state (not afforested) to its new state (afforested), see Figure 1. Afforestation decreases local sediment production and flow factor, i.e., and , whereas it increases retention capacity and saturation threshold, i.e., and . Therefore, CAMF requires two input data-sets for locally produced sediment, flow factor, retention capacity and saturation threshold, representing the catchment respectively under the original land cover (initial situation) and with every candidate cell assumed as afforested. Hence, the selection of a cell conditions the amount of sediment delivered by this cell and also conditions the amount of sediment flowing into the cells lying on the flow path(s) between this cell and the outlet(s).

Figure 1. Piece-wise linear convex functions to compute the amount of sediment that leaves a cell. : sediment accumulation; : amount of sediment leaving the cell. Case (red curve): the cell is not afforested and (blue curve): the cell is afforested; : retention capacity before and after afforestation; : saturation threshold before and after afforestation.
CAMF-SFD
In the original version of CAMF (Vanegas, [28]; Vanegas et al. [29, 32]), sediment flow simulation is based on a SFD model, i.e., flow leaving a cell is assumed to be delivered entirely to the neighbouring cell(s) at lowest altitude.
In particular, the Eight-Direction (D8) algorithm (O’Callaghan and Mark, [21]) is used: a cell flows to cell (one of its eight neighbors), with determined by
where is the elevation for cell , see Figure 2. If for all , cell does not flow to a neighbor.

Figure 2. Cell and its eight neighbors.
The flow direction in CAMF-SFD can be represented as a tree that expresses the flow connectivity of the cells (Figure 3), where each node corresponds to a raster cell, see Figure 3b, with the root node corresponding to the outlet of the catchment and the child-parent relationship representing the sediment flow direction according to the steepest descent pathway. To compute the sediment accumulation matrix , the cells must be processed in the right order, i.e., the tree must be traversed depth-first.
Figure 3. (a): Fragment of a flow direction matrix, where cell 4 represents the outlet, black arrows represent flow direction and gray arrows denote the branches of the corresponding tree representation; (b): Corresponding tree representation.
As mentioned above and explained in detail in § 2.4, in the optimization iteration a single candidate cell will be (tentatively) afforested to compute the corresponding . In this case, the must not be recomputed completely, but only the values for cells on the path between cells and the root of the tree.
CAMF-MFD
However, the SFD method fails to reflect the reality of surface transport processes [24, 37]. In the MFD variant of CAMF we use the Fractional Deterministic Eight-Neighbor (FD8) model [24], but this can easily be replaced by another MFD model, e.g. the algorithm [27] and the Digital Elevation MOdel Networks (DEMON) [5].

Figure 4. Difference in simulation of flow in CAMF-SFD and CAMF-MFD
In the FD8 model [24], the proportion of sediment delivered to each down-slope neighboring cell is given by
with the fraction of sediment delivered from cell to its neighbor cell ; the number of down-slope neighboring cells; the gradient between cell and neighbor cell ; contour length: 0.5 cell size for a cardinal neighbour and 0.354 cell size for a diagonal neighbour.
In CAMF-MFD the spatial interaction and the cell connectivity is represented as a graph, instead as a tree. To construct this graph, Algorithm 1 computes for all the cells an adjacency list with ancestors and successors, based on the flow direction matrix (Figure 5a, Figure 5b). The ancestors of cell drain into cell and the successors of receive flow from . Several methods to compute the matrix using a graph have been proposed, see e.g. [23, 18]. However, processing the graph is very memory and compute intensive for large data-sets. In the minimization process in CAMF, we compute the matrix many times. Therefore, in a pre-processing step Algorithm 2 sorts the cells by a topological sorting algorithm [19], as in Anand et al. [1], so that for each ancestor–successor pair, the ancestor always appears before its successor in the sorted list (Figure 5c). The computation of is then performed cell per cell in the order given by the sorted list, from left to right, see Algorithm 3.
Figure 5. Representation of flow direction in CAMF-MFD. (a) Input raster flow direction matrix ; (b) Adjacency list representing the spatial interaction graph; (c) Topologically sorted list of cells.
As in the case of SFD, must not be completely recomputed when a single candidate cell is (tentatively) afforested to compute the corresponding . However, in case of MFD, for all cells on all paths between cell and the outlet must be recomputed, which corresponds to a substantially larger part of the matrix compared to the single path used in SFD. Also, recomputing for only these cells requires to store and process the complete graph. Experiments indicated that this is very expensive. Therefore, when cell is (tentatively) afforested, is recomputed for all cells in the sorted list between cell and the outlet.
Minimizing sediment yield at the outlet
Each iteration of the CAMF algorithm consists of the following three steps:
Each candidate cell not yet selected in previous iterations is tentatively selected and the matrix is recomputed
Algorithm 1 Create an adjacency list from flow direction matrix
Input: MFD matrix
Create data structure to store adjacency list
for each cell of do
for each neighbor of do
if drains into then
2. Add as successor of in
3. Add as ancestor of in
end if
end for
end for
Output: Adjacency list
Algorithm 2 Sort the adjacency list
Input: Adjacency list
Create data structure to contain the sorted list
Create data structure to store cells without incoming ancestors
for each cell in without ancestors do
3. Store in
end for
while is non-empty do
4. Get cell from
5. Remove cell from
6. Add to
for each cell in with as ancestor do
7. Remove from ancestors of in
if has no other ancestors then
8. Add to
end if
end for
end while
Output: Sorted list
to evaluate the effect of selecting this cell. In section 2.1 we indicated that when a cell is selected for afforestation the amount of sediment delivered to its neighbours decreases. This decrease is propagated to the outlet and results in a decrease in and thus an increase in the .
Let be the in the base flow; the if cell would be afforested in iteration ; the total if cell would be afforested in iteration . Then
Algorithm 3 Compute Sediment Accumulation
Input: Sorted list , adjacency list , local sediment production , flow factor , retention capacity , saturation threshold , with indicating the values before afforestation () or after afforestation ()
Create data structure to store the sediment accumulation for every cell
for each cell in do
for each ancestor of in do
if then
else
if and then
else
if then
end if
end if
end if
end for
end for
Output: Sediment accumulation
Cells are ranked in descending order according to their value.
The cell(s) with the maximal value are added to the set of cells selected for afforestation.
The iterative procedure ends when the number of selected cells reaches a user-specified value (see Algorithm 4). Note that this stop criterion can easily be replaced by a test on achieving a user-specified .
Algorithm 3 for computing has a linear temporal complexity in the number of cells. In the worst case, Algorithm 4 has a quadratic temporal complexity in function of the number of cells, since the number of candidate cells can be of the order of the number of cells. In addition, most probably only one cell is selected per iteration. Hence, the total temporal complexity of CAMF-MFD is proportional to the total number of cells in the data-set, the number of candidate cells and the number of cells selected for afforestation.
Case studies
Tabacay catchment
The first case study deals with the Tabacay river basin in Ecuador. It is a relevant region for afforestation since the Tabacay river provides drinking water to the city of Azogues. The area of the Tabacay catchment is 6 639 ,
Algorithm 4 Determine the cells to be selected
Input: Number of cells to be selected
Create data structure to store cells to be selected
while size of do
for each candidate cell not yet selected do
Compute SA matrix and by simulating the afforestation of cell
end for
Rank cells according to
Put cell(s) with highest in solution set
end while
Output: Set of selected cells
with altitude from 2 482 to 3 731 above sea level. Agriculture and pasture cover 2 400 (39% of the total area) (Wijels and Van Orshoven, 2009). The widespread agricultural land use, even on steep slopes, leads to large amounts of sediment produced and transported towards the river, which results in severe land, river and reservoir degradation.
A raster geo-database representing the Tabacay catchment with a resolution of is used, containing 122 830 cells, of which 73 471 are active cells (with actual values). Only part of the cells under agriculture and pasture are considered as candidate cells, i.e., cells that can be selected for afforestation (27 246 cells).
The initial sediment production map was computed using the Revised Universal Soil Loss Equation (RUSLE), Eq. (6) proposed by Renard et al. [26].
where : annual soil loss (); : rainfall erosivity factor (); : soil erodibility factor (); : slope length and slope steepness factors; : cover management factor; : support practice factor.
The values and were obtained from Cisneros Espinosa et al. [3]. The equation introduced by Wischmeier [38] was used to calculate the -factor from soil granulometric fractions, see Table 1. The -factor map was generated by assigning the C-values presented in Table 2, taken from Estrella [10], to the land cover map (Figure 7a). The -factor map was computed from the DEM using a SAGA-GIS tool (Conrad, [4]), based on the slope and specific catchment area, following the approach of Desmet and Govers [8]. The -factor map and the initial sediment production are shown in Figure 7b, Figure 7c.
| Soil Type | Soil Texture | K-factor |
| Umbric Leptosol | Sandy clay loam | 0.0397 |
| Umbric Andosol | Loam | 0.0373 |
| Dystric Cambisol | Loam | 0.0376 |
| Ferralic Cambisol | Clay loam | 0.0253 |
| Calcaric Regosol | Sandy loam | 0.0452 |
| Calcaric Cambisol | Sandy clay loam | 0.0290 |
| Eutric Cambisol | Silt loam | 0.0518 |
| Eutric Regosol | Sandy loam | 0.0521 |
Table 1. K-factor calculated for each soil type in Tabacay catchment [10].
Figure 7. (a): Land cover map of the Tabacay catchment; (b): -factor map used to compute the initial local sediment production map ; (c): Initial local sediment production map () calculated by means of RUSLE using Eq. (6).
| Land cover type | C-factor |
| Agriculture | 0.2 |
| Forest | 0.001 |
| Lake | 0 |
| Bush | 0.003 |
| Pasture | 0.003 |
| Wetlands non-afforested | 0.003 |
| Other features | 0.003 |
Table 2. C-factor values assigned to each land use type in Tabacay catchment [10].
The initial flow factor map in Eq. (1) was computed by a linear transformation of the original topographic slope map using min-max normalization [16]. The values of the other parameters of Eq. (1), i.e., , , , , and , listed in Table 3, are taken from Estrella [10]. Note that Estrella [10] used a slightly different initial local sediment production map , since the -factor was computed differently.
| Parameter | Initial value (before afforestation) | Second value (after afforestation) |
| Sediment production | Calculated by RUSLE, Figure 7c | |
| Retention capacity | ||
| Saturation threshold | ||
| Flow Factor | Normalized slope from DEM |
Table 3. Parameter values used in the experiments with CAMF-SFD and CAMF-MFD for the Tabacay data-set.

Figure 6. Digital Elevation Model of the Tabacay catchment and its location in Ecuador [11].
Additionally, two smaller regions around the outlet of the catchment were cropped from the original data-set, to evaluate the scalability of both CAMF variants. Figure 8a, Figure 8b show the corresponding fragments of the initial local sediment production map .
Figure 8. Maps cropped from the initial local sediment production map () in the Tabacay catchment. (a): of the original; (b): of the original.
Maarkebeek catchment
The second case study deals with the Maarkebeek river basin (Belgium) with an area of , with altitudes from to , i.e. a rather flat area, containing mostly agricultural area, dominated by arable land, with urbanized and afforested Gabriels et al. [14]. The Maarkebeek geo-database with a resolution of contains 129 097 active cells, of which 53 792 are candidate cells for afforestation (cells under agriculture and pasture), see the DEM in Figure 9. Since the Maarkebeek data-set is larger than the Tabacay data-set the computational cost is substantially higher.

Figure 9. Digital Elevation Model of the Maarkebeek catchment in Belgium [14].
As in Tabacay catchment, the initial local sediment production map (Figure 11) was generated by means of RUSLE, Eq. (6). The values , , the -factor associated to each soil type (Table 4) and the -factor assigned to each land use type (Table 5), were obtained from Deproost et al. [7]. The LS-factor map was computed using the same tool as for the Tabacay catchment. The values for , , , , and in Table 6 were calibrated such that in the base flow for the SFD model is close to the value given in [7].
| Soil Texture | K-factor |
| Silty sand | 0.02 |
| Light sandy loam | 0.025 |
| Sand loam | 0.4 |
| Clay | 0.042 |
Table 4. K-factor calculated for each soil type in Maarkebeek catchment.
| Land cover type | C-factor |
| Lake and Infrastructure | 0 |
| Grass, shrubs (by the side of the road) | 0.001 |
| Forest | 0.01 |
| Agricultural, pasture and arable land | 0.37 |
Table 5. C-factor values assigned to each land use type in Maarkebeek catchment.
| Parameter | Initial value (before afforestation) | Second value (after afforestation) |
| Sediment production | Calculated by RUSLE, Figure 11 | |
| Retention capacity | ||
| Saturation threshold | ||
| Flow Factor | Normalized slope from DEM |
Table 6. Parameter values used in the experiments with CAMF-SFD and CAMF-MFD for the Maarkebeek data-set.
Figure 11. Initial local sediment production map () of Maarkebeek catchment calculated by means of RUSLE using Eq. (6).
Results
All experiments have been performed on a Xeon E5-2697 v3 CPU (2.6 GHz) with 28 cores (2 sockets, each with 14 cores) and 128 GB memory, with Ubuntu Bionic Linux (18.044.15.0-147-generic x86 64 kernel) as Operating

Figure 10. Land cover map of the Maarkebeek river catchment [14].
System. Although we have performed the experiments on Linux, the implementation of CAMF in C++ can be used under Linux/Unix and Windows.
Sediment yield reduction with CAMF-SFD and CAMF-MFD
Figure 12 shows for the Tabacay catchment the SA matrices for the base flow, computed with CAMF-SFD and CAMF-MFD. With MFD, the maximum is lower.
Figure 12. Representation of () for the base flow in Tabacay catchment. (a): CAMF-SFD and (b): CAMF-MFD.
Table 7 shows that, for a given percentage of afforested cells, CAMF-MFD predicts lower values than CAMF-SFD, but the ratio over , denoted by “% ”, is higher. Indeed, MFD increases the SI among cells and more cells are involved in the distribution of sediment. Therefore more cells retain (part of the) sediment and less sediment flows to the outlet. Further, in both cases, the cells selected first (up to 5%) contribute most to the and the extra gain decreases with increasing number of afforested cells. By afforesting 20% of the candidate cells the maximum attainable is nearly reached, as indicated by the horizontal lines in Figure 13a. Due to the values that we assigned to , , , , and , we observed that after afforesting the required number of cells, the value increases, which indeed is in agreement with the fact that afforestation is an effective means in this regard [6, 17, 20].
| Base flow () SFD | Base flow () MFD | # Afforested cells | () SFD | () MFD | % SFD | % MFD |
| 22 209 | 13 691 | 5% = 1 362 | 5 326.60 | 4 227.82 | 23.98 | 30.88 |
| 22 209 | 13 691 | 10% = 2 724 | 5 803.09 | 4 855.23 | 26.13 | 35.46 |
| 22 209 | 13 691 | 20% = 5 448 | 6 034.20 | 5 256.75 | 27.17 | 38.40 |
| 22 209 | 13 691 | 30% = 8 172 | 6 136.12 | 5 358.93 | 27.63 | 39.14 |
Table 7. and obtained with CAMF-SFD and CAMF-MFD for the Tabacay data-set. Afforestation of up to 30% of the candidate cells.
Figure 13. Evolution of the () for Tabacay data-set using CAMF-SFD and CAMF-MFD. (a): Absolute reduction. Horizontal lines: maximum attainable by afforesting all candidate cells; (b): Relative reduction.
Figure 13a shows the in function of the number of cells selected for afforestation. The extra gain in per 1000 selected cells decreases, and becomes very small after afforesting 3000 cells, confirming that CAMF first selects the cells leading to the highest . We observe that the MFD model predicts a larger relative by afforesting the first 1000 cells than the SFD model by afforesting 8000 cells, which is a significant observation, considering that we expect that it reflects more closely the reality.
Figure 14 shows the selected cells by CAMF-MFD for afforestation of up to 30% of the candidate cells in the Tabacay catchment. Note that the first cells selected (5% and 10%) are concentrated in areas with high sediment production, as already observed for CAMF-SFD [29, 12]. For example, the 11 candidate cells i
Figure 14. Areas selected by CAMF-MFD for afforestation in Tabacay catchment. (a): 5% of total candidate cells; (b): 10% of total candidate cells; (c): 20% of total candidate cells; (d): 30% of total candidate cells.
with were selected in the first 25 iterations.
The results for the Maarkebeek catchment are presented in Table 8 and Figure 15a, Figure 15b. We observe some differences with the results for Tabacay: (1) the MFD model predicts a larger in the base flow than the SFD model. (2) When only 5% of the cells is afforested, the is close to the maximum attainable value for the SFD model, while Figure 15a shows that this is not the case for the MFD model. (3) If less than 2% of the candidate cells is selected, the SFD model predicts a larger relative value than MFD. On the other hand, also in this case the first cells selected are concentrated in areas with high sediment production.
| Base flow | # Afforested cells | % | ||||
| SFD | MFD | SFD | MFD | SFD | MFD | |
| 7 392 | 9 747 | 1% = 538 | 1 753.77 | 2 087.95 | 23.72 | 21.42 |
| 7 392 | 9 747 | 2% = 1 076 | 2 479.67 | 3 277.11 | 33.54 | 33.62 |
| 7 392 | 9 747 | 3% = 1 614 | 2 697.88 | 4 038.57 | 36.50 | 41.43 |
| 7 392 | 9 747 | 4% = 2 152 | 2 750.32 | 4 534.70 | 37.21 | 46.52 |
| 7 392 | 9 747 | 5% = 2 687 | 2 773.61 | 4 825.48 | 37.52 | 49.50 |
Table 8. and obtained with CAMF-SFD and CAMF-MFD for the Maarkebeek data-set. Afforestation of up to 5% of the candidate cells.
Figure 15. Evolution of the () for Maarkebeek data-set using CAMF-SFD and CAMF-MFD. (a): Absolute reduction. Horizontal lines: maximum attainable by afforesting all candidate cells; (b): Relative reduction.
Scalability and computational cost of CAMF-MFD
We study the scalability of the CAMP-SFD and CAMF-MFD algorithms by measuring the execution times for the Tabacay data-sets. The sequential execution times are shown in Table 9.
| Data-set | Small | Intermediate | Ratio 1 | Original | Ratio 2 |
| Dimensions | 89 × 87 | 178 × 173 | 355 × 346 | ||
| # cells | 7 743 | 30 794 | 3.98 | 122 830 | 15.86 |
| # active cells | 5 475 | 22 494 | 4.11 | 73 471 | 13.42 |
| # candidate cells | 2 259 | 9 859 | 4.36 | 27 246 | 12.06 |
| CPU time (s) SFD | CPU time (s) MFD | CPU time (s) SFD | CPU time (s) MFD | Ratio SFD | |
| Ratio MFD | CPU time (s) SFD | CPU time (s) MFD | Ratio SFD | Ratio MFD | |
| Base Flow SA | 0.003 | 0.018 | 0.006 | 0.023 | 2.19 |
| 1.28 | 0.009 | 0.028 | 3.45 | 1.56 | |
| 1 iteration | 0.476 | 1.373 | 9.658 | 26.669 | 20.28 |
| 19.43 | 110.819 | 651.202 | 232.72 | 474.33 |
Table 9. CPU times for the calculation of the matrix in the initial situation and for one iteration, using the Tabacay data-set. Small and intermediate data-sets correspond to and of the original respectively; Ratio 1: ratio of intermediate to small data-set; Ratio 2: ratio of original to small data-set.
The base flow is computed by calculating the matrix. Hence, the number of operations is proportional to the number of active cells. While the number of cells increases by a factor of 4 and 13 from the small to the intermediate and the original data-set, the execution times grow much slower. On current computers, execution times are mainly determined by the cost of data access, from main memory to caches and processor. Note that calculating uses a very irregular data access pattern. Probably caching works more effectively for larger data-sets. Of course, the execution time of CAMF-MFD is higher than of CAMF-SFD due to the increased among cells. To tentatively afforest each (not yet selected) candidate cell in each iteration of CAMF, the matrix is recomputed. As mentioned in § 2.4, this requires to recompute the values for cells appearing after cell in the sorted list . Thus the number of operations in one iteration is approximately larger than the time to compute the base flow, with the number of candidate cells. However, the ratio of the execution times for one iteration and for the computation of the base flow is much smaller for the small and intermediate data-sets, while for CAMF-MFD with the original data-set the ratio is . This again shows that the number of operations is a poor indicator of the execution time on current computers.
In the optimal implementation of CAMF-SFD ([10]), the flow connectivity of the cells is represented as a tree where the root corresponds to the outlet of the catchment and child nodes deliver sediment to their parents. Note
that, in this case, only the cells on the path between cell and the outlet (one branch of the tree) must be recomputed.
But this optimization is not implemented in CAMF-MFD. However, with MFD, the SI among cells increases and the data structure used to model the flow paths becomes a graph, significantly more complex than the tree in CAMF-SFD, which leads to a substantial increase in the computational cost of the algorithm.
Conclusions
The raster-based CAMF method selects optimal sites for implementing an action, e.g., afforestation, to minimize sediment delivery at the outlet of a river catchment. Sediment transport among cells is modeled by a piece-wise linear function, parameterized by retention capacity, saturation threshold and a flow factor. The original CAMF uses a SFD method for flow simulation. We described and analyzed the integration in CAMF of a MFD method, in which sediment leaving a cell flows in all down-slope directions, allowing more realistic flow simulations.
The various algorithmic steps are presented in detail, highlighting the increased complexity of the sediment transport simulation in the MFD variant. The CAMF-MFD implementation in C++ is applied for afforestation planning in two river catchments: Tabacay catchment in Ecuador and Maarkebeek catchment in Flanders, Belgium.
The results show that CAMF-MFD iteratively selects, from a large set of candidate cells and in the presence of spatial interaction, those cells for which the marginal contribution of afforestation to the sediment yield reduction is highest. A major characteristic of the selected cells is that they lie in regions with a high local sediment production. CAMF-MFD predicts a lower sediment yield at the outlet of the catchment than CAMF-SFD for the Tabacay catchment with large elevation differences, while the opposite is true for the flat Maarkebeek catchment. When a rather large number of cells is afforested, MFD predicts a larger relative sediment yield reduction, due to the retention capacity of the many cells on the path between the afforested cell and the outlet.
CAMF-MFD has a substantially larger computational cost than CAMF-SFD, since updating the sediment accumulation matrix after afforesting a single cell is much more expensive in CAMF-MFD than in CAMF-SFD. Therefore the execution time of each iteration in the sediment minimization process is much larger in CAMF-MFD. Hence there is a clear need to exploit parallelization and to reduce the cost of each iteration and also the number of iterations. This topic is addressed in a forthcoming paper, where we show that execution time can substantially be reduced.
Acknowledgments
The authors would like to acknowledge the VLIR-UOS projects “Networks 2019 Phase 2 Cuba ICT” (grant for PhD research of G. Castillo Reyes) and “Global Minds KU Leuven” (Short term Research Stay of R. Estrella).
Code availability section
Name of the code/library: A-CAMF
Developer: Grethell Castillo Reyes
Contact: Department of Computer Science, Celestijnenlaan 200A box 2402, 3001 Leuven, Belgium; Data Representation and Analysis Center, San Antonio de los Baños Km 2½, University of Informatic Sciences, Cuba.
Email: link [email protected], [email protected]. Tel.: +32496998509
Year First Available: 2022
Hardware requirements: Code was tested on a a Xeon E5-2697 v3 CPU (2.6 GHz) with 28 cores and 128 GB memory
Program language: C++
Software required: Geographic Data Abstraction Library (GDAL). Source code available at the link: https://gdal.org/download.html. For Unix systems it is also available at the repositories with the name libgdal-dev.
Program size: 153 KB
The source codes are available for downloading at the link: https://gitlab.kuleuven.be/u0123674/acamf
References
- [1]Anand, S.K., Hooshyar, M., Porporato, A., 2020. Linear layout of multiple flow-direction networks for landscape-evolution simulations. Environmental Modelling & Software 133, 104804. URL: https://www.sciencedirect.com/science/article/pii/S1364815220305934, doi:https://doi.org/10.1016/j.envsoft.2020.104804.
- [2]B.-M. Vought, L., Pinay, G., Fulglsang, A., Ruffinoni, C., 1995. Structure and function of buffer strips from a water quality perspective in agricultural landscapes. Landscape and Urban Planning 31, 323–331. URL: https://www.sciencedirect.com/science/article/pii/016920469401057F, doi:https://doi.org/10.1016/0169-2046(94)01057-F.
- [3]Cisneros Espinosa, P.J., Gabriëls, D., Van Meirvenne, M., 1999. Mapping of soil erosion risk zones in a part of the watershed of rio Paute (Ecuador). URL: http://lib.ugent.be/catalog/rug01:000500575.
- [4]Conrad, O., 2003. Tool LS Factor. URL: https://saga-gis.sourceforge.io/saga_tool_doc/8.0.1/ta_hydrology_22.html. Accessed: 2022-01-11.
- [5]Costa-Cabral, M.C., Burges, S.J., 1994. Digital Elevation Model Networks (DEMON): A model of flow over hillslopes for computation of contributing and dispersal areas. Water Resources Research 30, 1681–1692. URL: https://agupubs.onlinelibrary.wiley.com/doi/abs/10.1029/93WR03512, doi:https://doi.org/10.1029/93WR03512.
- [6]Costin, A., 1980. Runoff and soil and nutrient losses from an improved pasture at ginninderra, southern tablelands, new south wales. Crop & Pasture Science 31, 533–546.DOI
- [7]Deproost, P., Renders, D., Wauw, J., Ransbeeck, N., Verstraeten, G., 2018. Herkalibratie van WaTEM/SEDEM met het DHMV-II als hoogte- model omgevingvlaanderen.be Eindrapport. Technical Report. KU Leuven. Belgium.
- [8]Desmet, P., Govers, G., 1996. A GIS procedure for automatically calculating the USLE LS Factor on topographically complex landscape units. Journal of Soil and Water Conservation 51, 427–433.DOI
- [9]Drzewiecki, W., Mularz, S.C., 2008. Simulation of water soil erosion effects on sediment delivery to dobcz yce reservoir.
- [10]Estrella, R., 2015. Where to afforest? Single and multiple criteria evaluation methods for spatio-temporal decision support, with application to afforestation. Ph.D. thesis. Faculty of Bioscience Engineering, KU Leuven. URL: https://lirias.kuleuven.be/retrieve/345463.
- [11]Estrella, R., Catrysse, D., Van Orshoven, J., 2014a. Comparison of three ideal point-based multi-criteria decision methods for afforestation planning. Forests 5, 3222–3240. URL: https://www.mdpi.com/1999-4907/5/12/3222, doi:10.3390/f5123222.DOI
- [12]Estrella, R., Vanegas, P., Catrysse, D., Van Orshoven, J., 2014b. Trading off accuracy and computational efficiency of an afforestation site location method for minimizing sediment yield in a river catchment, Rückemann, Claus-Peter. International Academy, Research, and Industry Association (IARIA). pp. 94–100. URL: https://lirias.kuleuven.be/retrieve/267799.
- [13]Fischer, D.T., Church, R.L., 2003. Clustering and Compactness in Reserve Site Selection: An Extension of the Biodiversity Management Area Selection Model. Forest Science 49, 555–565. URL: https://doi.org/10.1093/forestscience/49.4.555, doi:10.1093/forestscience/49.4.555.
- [14]Gabriels, K., Willems, P., Van orshoven, J., 2022. An iterative runoff propagation approach to identify priority locations for land cover change minimizing downstream river flood hazard. Landscape and Urban Planning 218, 104262. URL: https://www.sciencedirect.com/science/article/pii/S0169204621002255, doi:https://doi.org/10.1016/j.landurbplan.2021.104262.
- [15]Gersmehl, P., 1970. Spatial interaction. Journal of Geography 69, 522–530. URL: https://doi.org/10.1080/00221347008981861, doi:10.1080/00221347008981861.
- [16]Han, J., Kamber, M., Pei, J., 2012. Data Preprocessing, in: Han, J., Kamber, M., Pei, J. (Eds.), Data Mining. Third Edition ed.. Morgan Kaufmann, Boston. The Morgan Kaufmann Series in Data Management Systems, pp. 83–124. URL: https://www.sciencedirect.com/science/article/pii/B9780123814791000034, doi:https://doi.org/10.1016/B978-0-12-381479-1.00003-4.
- [17]Heil, G., Muys, B., Hansen, K., 2007. Environmental Effects of Afforestation in North-Western Europe – From Field Observations to Decision Support. doi:10.1007/1-4020-4568-9.DOI
- [18]Jiang, L., Tang, G., Liu, X., Song, X., Yang, J., Liu, K., 2013. Parallel contributing area calculation with granularity control on massive grid terrain datasets. Computers & Geosciences 60, 70–80. URL: https://www.sciencedirect.com/science/article/pii/S0098300413001921, doi:https://doi.org/10.1016/j.cageo.2013.07.003.
- [19]Kahn, A.B., 1962. Topological sorting of large networks. Commun. ACM 5, 558–562. URL: http://doi.acm.org/10.1145/368996.369025, doi:10.1145/368996.369025.DOI
- [20]Nearing, M., Jetten, V., Baffaut, C., Cerdan, O., Couturier, A., Hernandez, M., Le Bissonnais, Y., Nichols, M., Nunes, J., Renschler, C., Souchère, V., van Oost, K., 2005. Modeling response of soil erosion and runoff to changes in precipitation and cover. CATENA 61, 131–154. URL: https://www.sciencedirect.com/science/article/pii/S0341816205000512, doi:https://doi.org/10.1016/j.catena.2005.03.007. Soil Erosion under Climate Change: Rates, Implications and Feedbacks.
- [21]O’Callaghan, J.F., Mark, D.M., 1984. The extraction of drainage networks from Digital Elevation Data. Computer Vision, Graphics, and Image Processing 28, 323 – 344. URL: http://www.sciencedirect.com/science/article/pii/S0734189X84800110, doi:https://doi.org/10.1016/S0734-189X(84)80011-0.
- [22]Piégay, H., Walling, D., Landon, N., He, Q., Liébault, F., Petiot, R., 2013. Contemporary changes in sediment yield in an alpine montane basin due to afforestation (the upper-drôme in France). Catena , 183–212doi:10.1016/S0341-8162(03)00118-8.
- [23]Qin, C.Z., Zhan, L., 2012. Parallelizing flow-accumulation calculations on graphics processing units—from iterative dem preprocessing algorithm to recursive multiple-flow-direction algorithm. Computers & Geosciences 43, 7–16. URL: https://www.sciencedirect.com/science/article/pii/S0098300412000787, doi:https://doi.org/10.1016/j.cageo.2012.02.022.
- [24]Quinn, P., Beven, K., Chevallier, P., Planchon, O., 1991. The prediction of hillslope flow paths for distributed hydrological modelling using digital terrain models. Hydrological Processes 5, 59–79. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/hyp.3360050106, doi:10.1002/hyp.3360050106.DOI
- [25]Randolph, J., 2012. Environmental Land Use Planning and Management. Island Press. URL: https://books.google.be/books?id=Kf83YgEACAAJ.
- [26]Renard, K.G., Foster, G.R., Weesies, G.A., Porter, J.P., 1991. RUSLE: Revised Universal Soil Loss Equation. Journal of Soil and Water Conservation 46, 30–33. URL: https://www.jswconline.org/content/46/1/30.DOI
- [27]Tarboton, D.G., 1997. A new method for the determination of flow directions and upslope areas in grid Digital Elevation Models. Water Resources Research 33, 309–319. URL: https://agupubs.onlinelibrary.wiley.com/doi/abs/10.1029/96WR03137, doi:https://doi.org/10.1029/96WR03137.
- [28]Vanegas, P., 2010. A spatially explicit approach to the site location problem in raster maps with application to afforestation. Ph.D. thesis. KU Leuven, Belgium.
- [29]Vanegas, P., Catrysse, D., Orshoven, J., 2012. Allocating reforestation areas for sediment flow minimization: an integer programming formulation and a heuristic solution method. Optimization and Engineering 13, 247–269.DOI
- [30]Vanegas, P., Catrysse, D., Van Orshoven, J., 2009. Compactness and Flow Minimization Requirements in Reforestation Initiatives: An Integer Programming (IP) Formulation, in: Gervasi, O., Taniar, D., Murgante, B., Lagana, A., Mun, Y., Gavrilova, M.L. (Eds.), Computational Science and Its Applications – ICCSA 2009, Springer Berlin Heidelberg, Berlin, Heidelberg. pp. 132–147.DOI
- [31]Vanegas, P., Catrysse, D., Van Orshoven, J., 2011. A multiple criteria heuristic solution method for locating near to optimal contiguous and compact sites in raster maps, in: Geocomputation, sustainability and environmental planning. 1st ed.. Springer. volume 348, pp. 35–56.DOI
- [32]Vanegas, P., Catrysse, D., Wijffels, A., Van Orshoven, J., 2014. Compactness and flow minimization requirements in reforestation initiatives: A heuristic solution method. Annals of Operations Research 219, 433–456.
- [33]Vanwalleghem, T., 2017. Soil Erosion and Conservation. John Wiley & Sons, Ltd. pp. 1–10. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/9781118786352.wbieg0381, doi:https://doi.org/10.1002/9781118786352.wbieg0381.
- [34]Wang, J., 2017. Economic Geography: Spatial Interaction. John Wiley & Sons, Ltd. pp. 1–4. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/9781118786352.wbieg0641, doi:https://doi.org/10.1002/9781118786352.wbieg0641.
- [36]Williams, J.C., Revelle, C.S., 1997. Applying mathematical programming to reserve selection. Environmental Modeling & Assessment 2, 167–175.DOI
- [37]Wilson, J., Gallant, J., 2000. Terrain Analysis: Principles and Applications. Earth sciences: Geography, Wiley. URL: https://books.google.be/books?id=1311_4-zvy4C.
- [38]Wischmeier, W.H., 1978. Predicting rainfall erosion losses : a guide to conservation planning , 58 p. : ill., maps ; 26 cm. —USDAURL: https://handle.nal.usda.gov/10113/CAT79706928.



