6 Conclusions and future work
6.1 Summary of results
In section 5 we have gone through a series of steps, each introducing new improvements to the original R2 algorithm proposed by Franklin et al. We now review these steps and compare them to the original algorithm as well as two configurations of the radar algorithm. We evaluate the performance of the algorithms by using both the Alta and Larvik terrains. On both terrains we select 45observation points according to the recipe in section 4, resulting in a total of90test cases.
The results of the test are shown in figure 6.1 and table 6.1. In table 6.2 we have conducted an expected error ratio (EER) analysis, as described in section 4.3. Most of the algorithms in the test should be familiar by now, but a few need some clarification. Thelo-variants of hybrid and radar are run using three times as many lines of sight (LOSs) as R2. Thehi-variant of hybrid is unconstrained, but does not evaluate more than ten times as many LOSs as R2 on any of the test cases. Thehi-variant of radar is run with twelve times as many LOSs as R2.R2 nearis the original R2 algorithm.
Our improvements started with the generalized R2 algorithm using the weighted- and linear estimators.
The EER analysis in table 6.2 shows that these reduce the error of R2 with at least56%and78%, respectively. Table 6.1 shows that the weighted variant of R2 is measurably slower than the original.
However, this difference is normally considered significant, as it has a t-test p-value of0.089. The linear variant of R2 is clearly slower than the original, seemingly inflicting a30%increase in running time.
Comparing the generalized R2 variants to radar, we see that both the weighted- and the linear versions have higher accuracy than radar in theloconfiguration. This in spite of the fact that radar in this configuration evaluates three times as many LOSs. Thehiversion of radar is better than both R2 variants, but this is hardly a fair comparison, since radar here evaluates twelve times as many LOSs.
The next step we made was analyzing the uniform variant of R2, which allowed us to increase the accuracy by increasing the running time. This led to the hybrid algorithm which works by estimating the boundary of the viewshed using R2 linear, before training the estimator further on an adjustable
Algorithm Median rel. err. 1st quartile 3rd quartile Mean run. time XDraw interpolated 4.5×10−3 3.1×10−3 6.9×10−3 35.4ms
Radar low 5.0×10−4 3.4×10−4 8.1×10−4 729.1ms Radar high 1.5×10−4 1.1×10−4 2.5×10−4 2458.2ms
R2 near 1.1×10−3 6.7×10−4 1.5×10−3 105.6ms
R2 weight 4.3×10−4 2.7×10−4 5.8×10−4 107.1ms R2 linear 2.2×10−4 1.5×10−4 3.2×10−4 138.5ms Hybrid low 6.7×10−6 1.9×10−6 1.3×10−5 408.2ms
Hybrid high 0 0 9.5×10−7 1025.4ms
Table 6.1 Alta and Larvik combined performance test. The low variants of hybrid and radar are run with three times as many LOSs as R2. The high variant of hybrid is unconstrained, but typically does not evaluate more than seven times as many LOSs as R2. The high variant of radar is run with twelve times as many LOSs as R2.
number of extra LOSs through points on the estimated boundary. As we can see from the plot, these algorithms have accuracy that lie orders of magnitude ahead of the others. Looking at the EER analysis we see that hybrid lo produces less than0.82%of the error of R2 near. This is an astonishing result given the comparably small increase in running time. Applying the EER method to the running time, we find that hybrid lo increases the running time by less than a factor4.0. This seems reasonable as it evaluates three times as many LOSs, in addition to the overhead of estimating the viewshed boundary. Compared to the weighted- and linear variants of R2, hybrid lo reduces the error by more than98%and95.9%, respectively.
Thehi variant of hybrid runs without constraints, but as we can see the running times are still acceptable. Using the EER technique on the running time, we see that this variant increases the running time with less than a factor 11.1. In table 6.1 we see that the hybrid algorithm in this configuration classifies the majority of viewsheds correctly. The EER analysis is therefore of limited interest, since no algorithm can do better than0error. We do see, however, that hybrid hi makes less than0.083%,0.20%and0.39%of the error of R2 near, -weighted and -linear, respectively.
Following up on the discussions and examples from section 4 we know that these results are not necessarily universal for all terrain types. We have also seen examples that indicate that this might not be the case. At the end of section 5 we saw that R2 linear and hybrid did not perform as well on the South Korea data set, as they have done in our other tests. It should, however, be noted that the improvement was still significant by a margin. We can therefore only claim the above results to hold on real world terrain data sets with relatively high resolution and that are reasonably smooth. Our proposed algorithms seem to be significantly better on terrains with lower resolutions as well, but with a smaller gain in accuracy.
1e-07 1e-06 1e-05 0.0001 0.001 0.01 0.1
Hybrid_hi Hybrid_lo R2_linear R2_near R2_weight Radar_hi Radar_lo XDraw_int
Figure 6.1 The relative error of various algorithms on the combined Alta and Larvik test set. R2 near is the original R2 algorithm.
R2 near Radar lo R2 weight R2 linear Radar hi R2 weight 4.4×10−1 9.0×10−1
R2 linear 2.2×10−1 4.5×10−1 5.2×10−1
Hybrid lo 8.2×10−3 1.6×10−3 2.0×10−2 4.1×10−2 5.2×10−2 Hybrid hi 8.3×10−4 1.5×10−4 2.0×10−3 3.9×10−3 5.4×10−3
Table 6.2 EER analysis of the proposed algorithms. The cell in columniand rowjcontains the EER of algorithmsiandjwith99%confidence. Blank cells indicate that the test to show that algorithmiis significantly better than algorithmjfailed.
6.2 Conclusions
The motivation for this thesis was to investigate viewshed algorithms that are suitable for being used as part of a larger algorithm for planning military operations. We saw in section 2 that we need to establish the boundary of the viewshed with reasonable accuracy, as the boundary is essential in attack and observation maneuvers. It is also likely that we have to evaluate a large number of viewsheds, so the algorithms need to be reasonably fast to be usable.
In section 4 we discussed how to evaluate the performance of such algorithms, specifically the importance of using relevant test cases. Using these techniques we established that the R2 algorithm originally proposed by Franklin et al. in [FRM94], gives reasonably good performance both in terms of accuracy and speed for our needs. Adding the weighted- or linear estimator proposed in section 5, we get even higher accuracy with no to modest increases in running time.
Should the R2 algorithm be too slow, then the interpolated variant of XDraw should be chosen, as this is much faster, albeit with a significant drop in accuracy. In case we have running time to spare, the hybrid algorithm gives us the flexibility to boost the accuracy, spending the remaining running time.
We have therefore filled the full specter of algorithms in terms of speed and accuracy. Ranging from the fast but inaccurate XDraw, via R2 with the weighted estimator, to the hybrid algorithm, we can obtain good accuracy for any amount of running time. Regardless of what the needs are in the planning algorithm, one of these three candidates should therefore be usable.