This set of programs calculates a weighted visibility index for each point of the database. That is, how much of the area of a circle of a certain radius can an observer placed at each point in turn see? The approach used here implicitly weights the visibility of areas close to the observer more than areas further away.
LOS is a fast approximate line-of-sight (LOS) program intended for eventual migration to a parallel machine. It is under 1000 lines of C code. LOS calculates a visibility index for each point in an elevation grid. To calculate the visibility index for a point, LOS fires a small number of rays, such as 16, from the point out to the radius of interest. The validity of using only a small number of rays was demonstrated experimentally by [Ray, 1994]. A theoretical justification can be given as follows.
The possible target points within the radius of interest for this given observer form a set, S . Each point is either hidden or visible. The visibility index is the average number of visible points, that is, is a statistic of S , and by the law of large numbers a mean of a set can be determined by sampling a small number of observations. Since |S| is finite, problems such as infinite population variances, which would cause the sample means not to converge, do not occur. The only requirement is that whether a point is sampled must not be correlated with its value. This might happen if there were strong vertical features that ran exactly along lines of constant latitude or longitude. However, this has been observed only for clearly erroneous data.
Therefore we are comfortable with only certain angles being sampled. The next step is to sample only certain points in each direction, that is, when we get far enough out from the observer, we don't use every pixel. Every time we process another 16 pixels in this direction, we double the distance between pixels used. From one to 16 pixels away, we use every pixel. From 17 to 48 pixels away, we use every second pixel. From 49 to 112 pixels away from the observer, we use every fourth pixel, etc. This rule was chosen for its speed of execution. Asymptotically, if the line of sight has N pixels, then we use proportional to log(N) of them.
We devoted considerable effort to optimizing LOS . This was done specifically on a Sun IPC, though the techniques are generally applicable. They include using integers instead of floating numbers, comparing various compilers, and creating (with a preprocessor) a separate block of code for each different slope of the line of sight.
On a Sun IPC workstation, the execution time ranged from 24 CPU seconds for a 300x300 scene with a range of 50, up to 568 CPU seconds for a 1201x1201 scene with range of 100. As expected, the time varies linearly with the number of points examined.
The ability to enhance features, such as edges, in a photographic image is an unexpected property of LOS . We have done preliminary studies in this, and offer it as as area for future research. The idea is to consider each pixel's intensity as if it were elevation when calculating visibility indices. This can enhance even edges bordered by gradual intensity changes.