The Variation of Viewshed Analysis Result Caused

The Variation of Viewshed Analysis Result Caused
by Different Implementations

Cuo-Pin Cheng and Tian-Yuan Shih
Department of Cvil Engineering
Nayional Chiao- Tung University
1001 Ta-Hsueh Road, Hsin-Chu, Taiwan
E-mail: tyshih@cc.nctu.edu.tw

Abstract
Viewshed analysis can be applied to the design of a forest fire watchtower, the selection of scenic spots, the evaluation of visual impact caused by construction, and others. A number of algorithms can be applied to the line-of-sight computation,. Baaed on the program designed, there can be further variations between the viewsheds computed from different implementations. This study investigated the viewshed utilities in ARC/INFO 6.0, and GRASS 4.1. A selfdeveloped package was also utilized for comparison. The number of pixels of differing value and the correlation coefficient are used as the similarity measures. The location where the variation are likely to occur is also identified .

Introduction
With a given terrain and a viewing point, the viewshed is the area observed from this viewing location versus that which is invisible. The viewshed operation has been implemented as an analysis tool for digital elevation models (DEM) in many GIS packages. Fisher (1993) evaluated the viewshed operation from both the algorithm and the software implementation aspects. Viewshed is the collection of the results from a number of line-of-sight (LOS elevations (Wang, et al., 1996). Three items in the LOS algorithm, which may be defined differently, are identified in Fisher (1993).

How the elevation is inferred: grid, triangular constraint, grid constraint ,or stepped;
How the viewer and target locations are defined: point to point, cell to point, point to cell, or cell to cell;
How the elevations are compared: height, gradient, or inter height.

Other factors, such as the compiler, or DEM representation (byte,inter, or real), may cause differences as well. As an overall combined result, the implementations in seven GIS packages are evaluated and inconsistencies are reported. In the conclusion, Fisher (1993) stated that " rather the viewshed is a fundamentally uncertain phenomenon within a GIS, and is simply not repeatable across a spectrum of systems." While the exact algotrithms are not documented in most implementations in the GIS packages, Fisher (1993) stated that " users have a right to know the algorithm used in any one version of the viewshed operation."

In the current study, an implementation of the viewshed operation, named as Viewshed , is conducted based on a known algorithm. Two GIS implementations, namely Arc/Info (visibility) (ESRI, 1991) and GRASS (r.los) n(USACERL, 1991), are applied to for comparison. The differences as well as the similarities, of these three implementations are evaluated based on numerical experiments. The locations where the differences are likely to occur are also identified.

The Algorithm Implemented
In the operation " how the elevation is inferred :, two sub-stages can be identified,

how the location of the line of sight is defined, and
the interpolation to obtain the elevation .

**Table 1: The Azimuth and the P-factor**
(P0, the initial value ; PK, the K-th value of P, dx, the x-distance from viewpoint to the target; dy, the y-distance from viewpoint to the target)
Azimuth	0-45	45-90	90-135	135-180	180-225	225-270	270-315	315-360
P0=	+2dx-dy	+2dy-dx	-2dy-dx	+2dx+dy	-2dx+dy	-2dy+dx	+2dy+dx	-2dx-dy
If P_K <0	Y_K+1	X_k+1	X_k+1	Y_K-1	Y_K-1	X_K-1	X_K-1	Y_K+1
P_K+1=P_k	+2dx	+2dy	-2dy	+2dx	-2dx	-2dy	+2dy	-2dx
Else	X_k+1 y_k+1	X_k+1 y_k+1	X_k+1 y_k-1	X_k+1 y_k-1	X_k-1 y_k-1	X_k-1 y_k-1	X_k-1 y_k+1	X_k-1 y_k+1
P_K+1=P_k	+2dx-2dy	+2dy-dx	-2dy-dx	+2dx+2dy	-2dx+2dy	-2dy+2dx	+2dy+2dx	-2dx-2dy

The selected algorithm for implementation in this study is based on the Bresenham's Line-Drawing Algorithm (Heran & Baker, 1997) to define the location of the line of sight. A parameter P is defined according to the azimuth computed from the starting point ( the viewing point) and the end point ( the target point ). The definition of P is listed in Table 1.

Taking the case in which the azimuth lies in 00 and 450 , the initial defination of P is P0=2dx-dy. If P0< 0, the coordinates of the next grid is (x0, y0+1), and the next P is P1=P0+2dx. If P0> 0 ' the coordinates of the next grid is (x0 +1, y0 +1) and P1=P0+2dx-2dy. The elevation of the passing grid is taken as the elevation of the elevation on the line. In other words, the nearest neighbor scheme is applied for the elevation interpolation. Gradient is computed to evaluate the visibility. Only the center of the viewing and target grid is considered during the LOS evaluation.

Algorithm Bresenham__ Method (G,e);

Input: G ( a Digital Elevation Model representated as m by n grid cells, for each cell c, (i,j) is the x-y directional identifiers, and z is the elevation ), e(view point in G).

Output: V( ViewShed , represented as a matrix of Boolean variables corresponding to G, for each element, it is set to true if it is visible by e and false otherwise).

begin

for each cell c in G except e do
compute the slope sc from e to c; {define the line of sight}
initialize V (i, j) as true;
repeat
compute the coordinates of a sampling point p along the
line of sight using Algorithm Bresenham_ Line_Drawing;
{p is located at the center of a grid cell}
find z from g=G (i,j) corresponding to p;
compute the slope sp from e to p;
if sp>sc ] then set V (i, j) to false;
until length_of_e_to_p=length_of_e_to_c
or V (i, j)=false

end

Test Data
The DEM file associated with four 1/5000 scale map sheets is used for the experience. The test araea is located in Northern Taiwan. Each grid in the DEM represents a 40m by 40m area on the ground. In total, there are 126*137 grid points. The highest elevation is 736.618m and 5.050m is the lowest. The average height is 353.175m and the average slope is 24.7200. As shown in Table 2 and Figure 1, five view points are selected .

Figure 1: The Test Area
(Lower-left: (333240,277320) ' Upper-Right (338240, 2779760) '
+indicates the Veiwpoint)

**Table 2: The Coordinates of Veiwpoints**
Viewpoint	X	Y	Z	Remarks
1	336480	2776560	736.618	The Heighest
2	336880	2777720	676.721	random
3	334040	2775160	508.082	random
4	337720	2775440	597.729	random
5	334840	2779440	577.828	random

The Numerical Experiments and Evaluation
The viewsheds computed with VeiwShed, ARC/INFO, and GRASS are shown in Figure 2. The differences of these viewsheds computed from the same viewing point are displayed in Figure 3. The numbers of visible cells, which is related to the area of the viewshed , is listed in Table 3, while the numbers of differences are summarized in Table 4. It can be seen that the shapes of the viewsheds computed from the same viewing point are generally alike. However, the degree of similarity from viewing points 1 and 5 presented larger variation.

**Table 3: The Number of Visible Cells**
Viewpoint	ViewShed	Arc/Info	GRASS
1	3894	4192	4383
2	3041	3337	3516
3	2353	2534	2583
4	2304	2401	2545
5	3265	3339	3572

Figure 2: The Viewsheds
(From top to bottom, Viewshed, ARC/INFO GRASS From left to right, viewpoint 1 to 5)

Figure 3: The Viewshed Differences
(From top to bottom, Viewshed vs ARC/INFO, Viewshed vs GRASS, ARC/INFO vs GRASS From left to right, viewpoint 1 to 5)

**Table 4: The number of Different Cells from Different Viewshed Implementation**
Viewpoint	ViewShed vs ARC/INFO	ViesShed vs GRASS	ARC/INFO vs. GRASS
1	628	933	399
2	718	637	421
3	358	273	219
4	351	325	256
5	576	425	447

The similarity of viewsheds is further measured with the correlation coefficients . The correlation coefficients of different Viewshed implementations are computed and listed in Table 5.

**Table 5: The Correlation Coefficients of Different Viewshed Implementations**
Viewpoint	Viewshed vs. ARC/INFO	ViewShed vs GRASS	ARC/INFO vs GRASS
1	0.899665	0.902239	0.938515
2	0.863382	0.883755	0.923855
3	0.915551	0.936868	0.949815
4	0.913894	0.923599	0.940137
5	0.892239	0.923975	0.919973

Two profiles along the line of sigh are extracted for evaluation (Figure 4 and 5). It is found that variation occurs frequently in the area where the gradient of the terrain changes.

Concluding Remarks
Despite the appeals for documenting the implemented GIS operations made in early literatures such as Fisher (1993), the algorithms applied for the GIS operation are still generally not documented. Based on a simple algorithm, a viewshed implementation is performed in this study. From the comparative study of the numerical experiments, the variation of Viewshed between different implementations is confirmed again, although the similarity between them is high. The variation differs from viewing point to viewing point for the same DEM. It is also found that the variation is likely to occur where the slop of the terrain changes frequently

References

ESRI, 1991. ARC/INFO User's Guide 6.0, Readlands, CA.
Fisher, P. F., 1993. Algorithm and Implementation Uncertainty in Viewshed Analysis, International Journal of Geographical Information Systems, 7:33-347
Heran, D. and Baker, M. P., 1997. Computer Graphics, C. Edition, Prentice Hall, Inc. New Jersey.
USACERL, 1991. GRASS 4.0 User Manual.
Wang, J., G. J. Robinson and White, K., 1996. A Fast Solution to Local Viewshed Computation Using Grid-Based Digital Models. Photogrammetric Engineering and Remote Sensing, 62(10) : 1157-1164.

Figure 4: The line-of-sight(1)

Figure 5: The line-of-sight(2)

Page 1 of 1