Caihong Zhang | Wei Xue* | Ying Xin
OPEN ACCESS
Forests are critical to the ecological balance of the earth. However, natural disasters and manmade damages are posing a severe threat to forest resources, calling for effective means of forest management and protection (M&P). Therefore, this paper designs and applies an intelligent patrol algorithm for forest M&P based on cutting-edge techniques like the global positioning system (GPS). Firstly, the information of forest road and the forest road network were obtained with the aid of the GPS. Next, the Dijkstra’s algorithm was adopted to identify the shortest patrol path for the M&P personnel and realize the intelligent patrol algorithm, in the light of the key points in forest M&P and the responsible areas of the M&P personnel. Together, the forest road network, M&P route planning and intelligent patrol form an effective framework for high-quality forest M&P. The research results shed new light on the protection of forest resources.
intelligent patrol algorithm, global positioning system (GPS), Dijkstra’s algorithm, forest management and protection (M&P)
Forest management and protection (M&P) is one of the top priorities in environmental protection. In most places, the personnel in charge of forest M&P must patrol the forest across hills and valleys. This M&P strategy is relatively backward and inefficient. Some areas of the forest might be overlooked, while some might be patrolled repeatedly. Against this backdrop, it is highly necessary to improve the precision, coverage and communication of forest M&P.
The smart forest (Figure 1) provides a viable way to enhance the effectiveness of forest M&P. This emerging model integrates various information technologies, ranging from information processing to global positioning system (GPS) [1].
Figure 1. The architecture of smart forest
The smart forest aims to realize the following functions: supervise the process of forest M&P, evaluate the performance of forest M&P, identify manmade damages of natural forest in time, and minimize the damages caused by natural disasters (e.g. forest fire, pests and diseases).
Considering the above, this paper designs and applies an intelligent patrol algorithm for forest M&P based on various state-of-the-art techniques, namely, the GPS, the support vector machine (SVM), the Hilditch thinning algorithm and the Dijkstra’s algorithm, aiming to achieve effective M&P of forest resources.
Natural forest has a huge biomass and various functions, and provides most of the forest resources on the earth. It is critical to the stability of environment and climate, thanks to its strong self-recovery ability and high species diversity [2]. The natural forest must be well managed and protected to ensure ecological security, cope with climate change and maintain the social stability of forest areas.
The GPS technology has long been applied in forest M&P. For example, Hole et al. [3] measured the range of forest with the GPS and aerial photography, and predicted the growth of forest resources by the k-nearest neighbors algorithm (k-NN). Naesset et al. [4] adopted differential GPS (DGPS) receiver to obtain ground data, and accurately estimated tree height based on the ground data and remote sensing data. Tang et al. [5] conducted a DGPS study in the forest area of the northeastern US, and evaluated the influence of canopy, terrain, distance and other factors on GPS accuracy.
Edson et al. [6] explored the accuracy and reliability of GPS in different forest environments, and disclosed how the number of measuring points affects the GPS accuracy in Oregon forest region. Using a dual-frequency GPS receiver, Yang et al. [7] classified forest areas through static mapping in dense forest, identified the exact boundaries and range of each forest area, and calculated the forest resource in different ranges. Li et al. [8] relied on the GPS to measure and correct the deviation of the forest boundaries and corners to a level below 0.03%.
Dios et al. [9] employed real-time DGPS to quickly determine the location of forest fire, and immediately report the fire to the ground station. Ballari et al. [10] used helicopters, drones or light fixed-wing aircrafts to fly around forest fires, record the fire locations with the aid of the GPS, and processed the recorded data after landing to identify the boundaries of the fire scene. He et al. [11] digitized the lighting information based on GPS lightning sensor and geographical information system (GIS), and established the distribution model of lightning-induced forest fires.
Using the GPS, Zhao et al. [12] determined the location range of a sample plot, and set up a new sample plot; the area of the new sample plot was calculated according to its geographic location and four corner signs; the total amount and dynamic change of forest resources are estimated in an accurate manner. Cox et al. [13] probes deep into the diseases and pests in forests, and used the GPS to identify the location, distribution and other information about such disasters.
Judging by their functions, the roads in forest generally fall into three categories: common forest roads, fire prevention channels and harvesting vehicle channels. The road information can be extracted in four steps. Firstly, the grids and vectors of forest roads are obtained through sample training. Next, the eigenvalues of the roads in road images are determined through calculation. After that, the candidate roads are identified based on road eigenvalues. Finally, the false targets are eliminated from the candidate roads based on the road shapes, producing the final roads. The workflow of road information extraction algorithm is shown in Figure 2.
In the above process, the useful road information can be extracted from the processed road images, creating the image features of each road. Based on these features, the road extraction model can be trained to acquire the ability of road recognition. Then, the path opening in different directions can be identified in the processed road images, eliminating the directionality of each road feature. The shapes of candidate roads can be obtained by counting the statistical feature of path opening in different directions. Figure 3 shows the effect of processing different eigenvalues in a remote sensing image.
In traditional technology of road recognition, the road images taken as training samples are recognized by the classifier, with the aim to minimize the classification error of training samples. If the sample size is small, however, the classifier with good recognition ability of training samples does not necessarily have good prediction effect in test samples. Considering the complexity of road extraction and the narrow sample coverage, the SVM was selected as the training model.
Through the SVM training, the main information of forest roads can be obtained. Then, the road features were enhanced by methods like mathematical morphology, without sacrificing the integrity of the road information. In this paper, the Hilditch thinning algorithm [14] is adopted to extract the road centerline, and the cutting algorithm and short line elimination are implemented to remove redundant derived components. In this way, the directional extension of each road was optimized. Next, the road information was vectorized to represent different computer images with points, lines, surfaces, curves and polygons.
To sum up, the authors firstly segmented the original remote sensing image to identify the area of the road network, then modified the road continuity based on the features of mathematical morphology, and finally vectorized each road according to line and curve features. Figure 4 provides an example of the extracted forest road vector image.
Figure 2. The workflow of road information extraction algorithm
Figure 3. The effect of processing different eigenvalues in a remote sensing image
Figure 4. An example of the extracted forest road vector image
3.2 Road network model
The modelling of road network is to reconstruct the topological relationship of the extracted road vector data. The road network is the basis of navigation and route planning. It is generally described as a line-node network [15], in which each line segment is a road passing in one direction and each node is an intersection, a road end or a point where the road attribute changes.
Different parts of the road network should be described by different geometric models. Considering the numerous intersections in forest roads, this paper selects the spider road network model to illustrate four parts of forest roads: straight segment, road end, T-junction and intersection (Figures 5-8).
Figure 5. Geometric model of straight segment
Figure 6. Geometric model of road end
Figure 7. Geometric model of T-junction
Figure 8. Geometric model of intersection
The road network model could be constructed by three different methods, namely, adjacency matrix, adjacency list and cross-linked list. The adjacency matrix is simple and intuitive, but consumes too much storage space for a network with sparse edges. By contrast, the cross-linked list method is suitable for storing sparse matrix. In the light of the features of forest roads, the adjacency list method was adopted to set up the road network model.
3.3 Route planning for forest M&P
Currently, the M&P personnel generally patrol the forest along a fixed route. The effect of forest M&P solely relies on the rationality of that route. If the route is not reasonable, many problems may arise, such as inadequate coverage of the forest, and repeated patrol in certain areas.
To solve the problem, the authors attempted to establish daily M&P routes for the personnel, and develop an auxiliary map for them to achieve the maximum coverage of the responsible forest areas. The important areas that need to be patrolled were defined as the key M&P points, and given special consideration in the route planning.
One of the keys to forest M&P is to identify the shortest path from the start point to the end point. The Dijkstra’s algorithm [16] is a typical single-source shortest path algorithm, which is widely used to calculate the shortest path from one point to other points. Thus, this algorithm was introduced to plan the shortest path for forest M&P.
Let G=(V, E) be a weighted digraph, where V is the set of nodes, and E is the set of edges. The node set V can be divided into two subsets, the subset of nodes (R) whose shortest path is known, and the subset of nodes (O) with unknown shortest path. During the routing process, the nodes in O are added to R in ascending order of the shortest path length.
The Dijkstra’s algorithm can be implemented in the following steps:
Step 1. Initially, R only contains the original points, and the distance of start point b is zero. Let o be a fixed point in subset O. If there is an edge from b to o, then <o, b> has a normal weight. Otherwise, the weight of < o, b > is positive infinity.
Step 2. From subset O, select the node s with the minimum distance to b, and add s to subset R.
Step 3. Taking s as the new middle node, the distance of each node in O is changed. If the distance from b to o via s is less than the original distance, then the distance value of o is changed to the sum of the distance of s plus the weight on the edge.
Step 4. Repeat Steps 2 and 3 until all the nodes have been added subset R contains all nodes.
Figure 9 offers an example of forest M&P map produced through the above process.
Figure 9. An example of forest M&P map
4.1 Data processing and precision analysis of the GPS
The GPS has two navigation modes: single-mode navigation and dual-mode navigation. In our navigation tests, the two navigation modes were respectively tested under two weather conditions, namely, clear weather and low cloud cover. 10 groups of invalid data were removed from the first test (dual mode, clear weather), 19 groups form the second test (dual mode, low cloud cover), 66 groups from the third test (signal mode, clear weather) and 71 groups from the fourth test (single mode, low cloud cover). The GPS accuracy is positively correlated with the number of positioning satellites. As shown in Table 1, the number of GPS satellites is about 10 and 11 for the single mode and dual mode.
Table 1. The test conditions
|
Mode |
Test batch |
Number of samples |
The mean number of satellites |
|
Dual mode |
1 |
8,627 |
11.28 |
|
Dual mode |
2 |
17,763 |
11.16 |
|
Single mode |
3 |
8,762 |
10.75 |
|
Single mode |
4 |
17,965 |
10.73 |
The signal intensity of GPS satellite is measured by signal-to-noise ratio (SNR). The SNR can be calculated by $10 \log _{10}\left(P_{S} / P_{N}\right)$, where $P_S$ and $P_N$ are the effective power of signal and noise, respectively. The higher the SNR, the better the receiving rate, communication quality and reliability of the network. The mean and variance of the signal intensity of GPS satellites are compared in Table 2 below. It can be seen that the two groups have similar signal intensities.
Table 2. Comparison of signal intensities
|
Group |
Mode |
Test batch |
Number of samples |
Mean signal intensity |
Variance of signal intensity |
|
1 |
Dual mode |
1 |
8627 |
36.37 |
82.71 |
|
Dual mode |
2 |
17763 |
36.65 |
52.83 |
|
|
Single mode |
3 |
8762 |
35.59 |
24.81 |
|
|
Single mode |
4 |
17965 |
34.88 |
77.72 |
|
|
2 |
Dual mode |
1 |
8627 |
36.27 |
59.72 |
|
Dual mode |
2 |
17763 |
35.92 |
83.21 |
|
|
Single mode |
3 |
8762 |
35.81 |
33.96 |
|
|
Single mode |
4 |
17965 |
35.64 |
75.89 |
The position dilution of precision (PDOP) falls into the range of 0.5-99.9. The PDOP is the root sign value of the sum of squared errors in terms of latitude, longitude and elevation. The PDOP integrated position accuracy of the GPS is shown in Table 3, where the low mean PDOP reflects the good stability of the GPS in measurement.
Table 3. PDOP integrated position accuracy of the GPS
|
Mode |
Test batch |
Number of samples |
Mean PDOP |
Variance of PDOP |
|
Dual mode |
1 |
8,627 |
1.582 |
0.211 |
|
Dual mode |
2 |
17,763 |
1.697 |
0.209 |
|
Single mode |
3 |
8,762 |
1.579 |
0.286 |
|
Single mode |
4 |
17,965 |
1.656 |
0.319 |
4.2 Practical application design
This subsection mainly applies our research results in actual forest M&P. Specifically, the responsible areas (Figure 10) were established for the M&P personnel based on the GPS. When the M&P personnel are patrolling in the responsible area, the patrol distance and time will be accumulated and processed in real time. The responsible area for each M&P person was determined according to the distribution of forest resources and the difficulty of the M&P. The boundaries of each responsible area were adjusted according to the processed remote sensing image. Together, the responsible areas of all M&P personnel cover all the key points in forest M&P, providing a reference for the supervision of the M&P operations.
Figure 10. Responsible areas for the M&P personnel
The M&P route planning is of great importance to the effectiveness of forest M&P. If the route is reasonable, the M&P personnel can complete the patrol task over the specified distance within the required time. Based on our model, the M&P route can be planned for the routine patrol of the M&P personnel, according to the remote sensing image and the division of responsible areas. Following this route, the M&P personnel will cover all the key points without any repetition.
Based on the optimal path, the effective M&P distance can be calculated. The total distance S can be computed by:
$S=\sum_{i=0}^{n} s_{i}$
where, $S_i$ is the distance of the i-th acquisition; n is the number of acquisitions.
$S_{i}=\sqrt{\left(x_{n+1}-x_{n}\right)^{2}+\left(y_{n+1}-y_{n}\right)^{2}}$
where, $\left(x_{n}, y_{n}\right)$ is the geodetic coordinate of the n-th acquisition. The maximum effective distance of single acquisition can be denoted as $S_{\max }$.
The effective M&P time can also be derived from the optimal path. The total effective time T can be computed by:
$T=\sum_{i=1}^{n}\left(T_{i}^{\prime}-T_{i}\right)$
where, $T_{i}$ and $T_{i}^{\prime}$ are the start time and end time of an effective distance, respectively.
This paper mainly improves the effectiveness of forest M&P through comprehensive application of the GPS, satellite remote sensing and other technologies. Based on the GPS, the information of forest road was extracted, and the road network model was established for the forest area. Then, the M&P route was planned according to the key points of forest M&P, and responsibility areas of the M&P personnel. Based on the road network model, the Dijkstra’s algorithm was adopted to optimize the M&P route for forest patrollers. The research results provide new insights into the protection of forest resources.
Heilongjiang Natural Science Foundation Project (E2016002); Central University Basic Research Business Expenses Special Fund(2572015CB05)
[1] Roy, S., Bose, R., Sarddar, D. (2016). Self-servicing energy efficient routing strategy for smart forest. Brazilian Journal of Science and Technology, 3(1): 13. https://doi.org/10.1186/s40552-016-0026-3
[2] Dettki, H., Esseen, P.A. (1998). Epiphytic macrolichens in managed and natural forest landscapes: A comparison at two spatial scales. Ecography, 21(6): 613-624. https://doi.org/10.1111/j.1600-0587.1998.tb00554.x
[3] Holmström, H., Nilsson, M., Ståhl, G. (2001). Simultaneous estimations of forest parameters using aerial photograph interpreted data and the k nearest neighbour method. Scandinavian Journal of Forest Research, 16(1): 67-78. https://doi.org/10.1080/028275801300004424
[4] Næsset, E. (2002). Determination of mean tree height of forest stands by digital photogrammetry. Scandinavian Journal of Forest Research, 17(5): 446-459. https://doi.org/10.1080/028275802320435469
[5] Tang, J., Bolstad, P.V., Ewers, B.E., Desai, A.R., Davis, K.J., Carey, E.V. (2006). Sap flux–upscaled canopy transpiration, stomatal conductance, and water use efficiency in an old growth forest in the Great Lakes region of the United States. Journal of Geophysical Research: Biogeosciences, 111(G2). https://doi.org/10.1029/2005JG000083
[6] Edson, C., Wing, M.G. (2012). Tree location measurement accuracy with a mapping-grade GPS receiver under forest canopy. Forest Science, 58(6): 567-576. https://doi.org/10.5849/forsci.11-015
[7] Luo, Y., Zhu, J., Wang, Z., Fu, Q., Lu, D. (2005). An application of CBERS data in the forest resources investigation of Guizhou Province. Journal of Nanjing Forestry University, 29(2): 92-94.
[8] Weilin, L., Buo, X., Yu, L. (2000). Applications of RS, GPS and GIS to Forest Management in China. Journal of Forestry Research, 11(1): 69-71. https://doi.org/10.1007/BF02855502
[9] Martinez-de Dios, J.R., Arrue, B.C., Ollero, A., Merino, L., Gómez-Rodríguez, F. (2008). Computer vision techniques for forest fire perception. Image and Vision Computing, 26(4): 550-562. https://doi.org/10.1016/j.imavis.2007.07.002
[10] Ballari, D., Wachowicz, M., Bregt, A.K., Manso-Callejo, M. (2012). A mobility constraint model to infer sensor behaviour in forest fire risk monitoring. Computers, Environment and Urban Systems, 36(1): 81-95. https://doi.org/10.1016/j.compenvurbsys.2011.06.004
[11] He, C., Zhang, S.Y., Chen, F., Sun, Y. (2013). Forest fire division by using MODIS data based on the temporal-spatial variation law. Spectroscopy and Spectral Analysis, 33(9): 2472-2477. https://doi.org/10.3964/j.issn.1000-0593(2013)09-2472-06
[12] Zhao, P., Zhao, Z., Hao, H. (2011). Study on carbon density and its dynamic change of forest types in Huanglong Mountain Forestry Region. Journal of Northwest A & F University-Natural Science Edition, 39(7): 77-96.
[13] Cox, R.M., Lemieux, G., Lodin, M. (1996). The assessment and condition of Fundy white birches in relation to ambient exposure to acid marine fogs. Canadian Journal of Forest Research, 26(4): 682-688. https://doi.org/10.1139/x26-078
[14] Naseri, M., Heidari, S., Gheibi, R., Gong, L.H., Rajii, M. A., Sadri, A. (2017). A novel quantum binary images thinning algorithm: A quantum version of the Hilditch's algorithm. Optik, 131: 678-686. https://doi.org/10.1016/j.ijleo.2016.11.124
[15] Bhavathrathan, B.K., Patil, G.R. (2018). Algorithm to compute urban road network resilience. Transportation Research Record, 2672(48): 104-115. https://doi.org/10.1177/0361198118793329
[16] Backhouse, R., Fokkinga, M. (2001). The associativity of equivalence and the Towers of Hanoi problem. Information Processing Letters, 77(2-4): 71-76. https://doi.org/10.1016/S0020-0190(00)00205-2
