A Method for Searching for Artificial Objects on Planetary Surfaces^†

Mark J. Carlotto and Michael C. Stein
The Analytic Sciences Corporation
55 Walkers Brook Drive
Reading, MA 01867 USA

---

Abstract

1. Introduction

2. Characterizing Natural Landscapes Using Fractal Geometry

Mandelbrot [13] has defined a fractal as an object whose Hausdorff-Besicovitch dimension is strictly greater than its topological dimension. For example, a fractal surface in 3-d space whose topological dimension is 2 would have a fractal dimension between 2 and 3. Fractals have been shown to be good models for diverse physical and biological phenomena such as the length of coastlines, stream flow volume, terrain surface area, volume of blood vessels and many more [13]. A reason is that natural phenomena often possess the property of being self-similar at different scales or resolutions. Self-similarity is defined by the relation

where M(X) represents any measurable property of the fractal (e.g., surface area), X represents a scale of measurement of the metric property, r is a scaling factor between zero and one, and (D) is a simple function of the fractal dimension that depends on the metric property. This equation states that the metric property computed at a reduced scale of measurement is equivalent to scaling the metric property of the fractal at the original scale. This implies that the metric property obeys a power law function of the scale of measurement

where K is a constant.

For the purpose of modeling landscapes, a class of statistical fractals known as fractional Brownian motion [14] has been used extensively. Fractional Brownian surfaces may be described by their second order difference statistics,

their surface area,

or their power spectral density,

where D = 3 - H . Eq. 3 states that the variance of the difference between any two points on the fractional Brownian surface a distance T apart increases at a constant power of the distance (since 0 < H < 1; Eq. 4 states that the surface area decreases as a constant power of the scale (since 2 < D < 3); Eq. 5 states that the power spectral density (power per unit frequency) varies as a power of the spatial frequency.

Mark and Aronson [15] analyzed 17 topographic data sets in the United States using variograms which plot variance versus distance as defined in Eq. 3. They found that most of the data sets could not adequately be characterized by a single fractal dimension, i.e., the logarithm of the variance was not linearly related to the logarithm of the distance over all distances or scales. Rather, the behavior of topography tended to be divided into scale ranges. Over small scales (< 0.6 km) many of the surfaces could be modeled as fractional Brownian surfaces with D around 2.2 - 2.3. Over larger scales, higher dimensions around 2.75 were noted while at still larger scales many surfaces exhibited periodicities. A similar result was noted by Clarke [16] who suggests that a combination of fractals, to model local behavior, and Fourier methods, to model longer-term variations, be used to describe topography. Locally, at least, fractals seem to be good models for topography. Clarke goes on to suggest that on planets like Mars where the types of processes that shape terrain over larger scales on Earth are for the most part absent, fractals may be adequate by themselves. For example, Woronow [17] shows that fractals can be used for classifying certain kinds of large scale Martian impact craters.

The above suggests a reason why the generation of realistic synthetic terrain using fractional Brownian motion has been so successful as demonstrated by Voss [18] and by Fournier et al [19]. Fig. 1 is a 3-d plot of a synthetic terrain surface (D = 2.1) produced by Voss' method for generating fractional Brownian surfaces using discrete Fourier synthesis. The method is based on passing the discrete Fourier transform of a 2-d white Gaussian noise field through a linear filter with transfer function proportional to 1/ (k ² + l² )^{4 - D} where k and l are the spatial frequencies in the x and y directions, and inverse transforming the result. Fig. 2 shows several views of this synthetic terrain surface. A Lambertian reflectance function was used to first create a shaded rendition of the terrain surface (left). The sun is south (solar azimuth  ₀ = 180°) at a zenith angle  ₀ = 45°. An oblique view was then generated by viewing the shaded rendition mapped onto the elevation surface via an oblique parallel projection (right). The image was computed from a view at an azimuth angle  ₁ = 180° and a zenith angle  ₁ = 60°. (Rendering techniques are described further in Appendix B.)

3. Detecting Manmade Objects

A major focus in artificial intelligence and machine vision has been on the problem of recognizing instances of known objects in imagery (see, for example Ballard and Brown [20].) The problem of recognizing an unknown object as an instance of a known object or class of known objects involves comparing features of the unknown object that can be computed from the available data to those of known objects and selecting the object with the best match.

The problem of recognizing unknown or unexpected objects, and the related problem of detecting man-made objects embedded in natural terrain are fundamentally different. One possible approach might be to try to determine the characteristics that are common to all man-made objects. For example, one thinks of man-made objects as having flat surfaces, sharp boundaries, and different brightness from the background. Unfortunately, due to lighting conditions, imaging geometry, and obscuration, the strong linear features that one might expect are often not there.

An alternative approach based on modeling the background has recently been proposed by Stein [21]. His approach does not rely on an explicit model for man-made objects (e.g., that they are rectangular in shape or brighter than the background); rather, it is based on the observation that man-made objects tend not to be self-similar in structure and so fractals should be poor models for man-made objects. The method is based on estimating the fractal dimension of the image intensity surface within a rectangular window that is about the size of the objects one would like to detect, along with the error that results from assuming fractal or self-similar behavior. The technique used to estimate the fractal dimension involves computing the surface area A(r) of the image intensity surface as a function of scale r (see Appendix A). The metric properties of self-similar sets scale according to a power law as noted in Eq. 4. The fractal dimension of the image intensity surface is estimated by performing a linear regression of log A(r) vs. logr . A measure of the degree to which the image intensity surface lacks self-similarity e is estimated by summing the residuals of the linear regression over scale, i.e.,

Surfaces that are not self-similar will not follow a power law relationship, hence the residuals in Eq. 6 will be large and so e will be large.

An entire image is processed by repeating the above process on a pixel-by-pixel basis within a "sliding window". Two images are produced: one is the local fractal dimension D(x, y) , i.e., the fractal dimension of the portion of the image intensity surface within the rectangular window centered at (x,y); the other is the local fractal model-fit image  (x, y). Fig. 3 shows an image of military vehicles embedded in natural terrain (a) along with the computed fractal dimension image (b) and fractal model fit error image (c) for R = 10 scales and a 21 by 21 window. For natural textures on earth, typical ranges can be used for thresholding the fractal dimension image in order to generate detections. At the upper end, terrestrial observations by Mark and Aronson [15] indicate that fractal dimensions over short scales are less than about 2.5. At the low

end, it has been observed that discontinuities in the image intensity surface (e.g., due to shadows, object boundaries, and obscuration) produce fractal dimension estimates that are below the topological dimension. Thus, for detecting man-made objects, regions whose fractal dimension is not greater than 2.0 and less than 2.5 are considered anomalous.

The fractal model fit is another independent measure of anomalous behavior. Unfortunately, since the fractal model fit error is a relative measure, absolute thresholds do not exist. If the relative frequency of occurrence of man-made objects is small however, the model fit image can be thresholded at a given false alarm rate (the probability that a man-made object may be detected when one is not actually present). The detection result (d) in Fig. 3 indicates possible man-made objects where the fractal dimension is not between 2.0 and 2.5, and where the fractal model fit error is greater than the 90th percentile. Three of four vehicles have been detected with two "false alarms". Lack of data like that compiled by Mark and Aronson limits the use of the fractal dimension for anomaly detection on Mars. For the imagery processed in the next section, the fractal dimension is used only to remove some object and shadow boundary effects by eliminating regions whose fractal dimension is less than 2.0. The unthresholded fractal model fit error image is used by itself in the remaining areas to indicate the degree to which the data lacks the self-similar behavior of terrain on a local basis.


Fig. 4 is a mosaic of parts of three Viking frames: 35A72, 35A73, and 35A74. A 1280 by 1024 pixel area is shown. This is the area in Cydonia that is currently under investigation by a number of  individuals [9-12]. The resolution is about 50 meters per pixel and the total area shown is approximately 3000 sq. km.

The result obtained by applying the anomaly detection technique to the imagery over this area is shown in Fig. 5. The image was produced by combining the fractal dimension and model fit images as described in the previous section and shows the top four detections. R = 10 scales and a 21 by 21 pixel analysis window were used. The analysis window thus covers an area about 1 sq. km and is near the upper scale limit for self-similarity based on Mark and Aronson's results for terrestrial landscapes. The "face" [9] was found to have the largest fractal model fit error which implies that it is the least natural object in this area. Close-ups of the face are shown in Fig. 6. A number of  objects in the "city" [11] also have large fractal model fit error. Close ups of one of those objects, the "fortress" [12] are shown in Fig. 7.†

As was seen earlier in the example in Fig. 3 the object detection technique may indicate the presence of a man-made object when there is no such object (false alarms) and may fail to detect a man-made object when one is there (missed detections). In Figs. 4 and 5, several features which appear to be natural seem to exhibit a certain degree of non-fractal behavior. On the other hand, several other unusual objects (e.g., the "cliff" [11] and the "D&M pyramid" [9]) do not appear to be anomalous by this technique.

As for the false alarms, it is certainly possible for nature to conspire to produce a structure that is not self-similar over short scales. In fact, this has been said of the face and the other nearby objects in Cydonia. It is also noted that there are many features on Mars as well as on the earth that exhibit aperiodic structure over short scales and are therefore not locally fractal.

In regard to the missed detections, it was observed earlier that images of fractal surfaces are also fractal. The converse is not necessary true however. If a man-made object is illuminated so that its 3-d structure does not induce significant shading and shadowing effects, structural information will be lost in the image formation process. The image of the object will look smoother than it really is and will thus appear less anomalous. In other words, the ability to discriminate anomalous objects from the background may be reduced at certain sun and viewing angles. This is illustrated in Fig. 8 which shows two images of the face (Viking frames 35A72 and 70A13) and surrounding terrain. In 35A72 where the sun is more than 15° lower than in 70A13, the ability to discriminate the face from the background is much greater.

To verify that the technique does not detect a plethora of natural objects, it was applied to the full Viking frame containing the above objects (35A72) as well as three other nearby frames: 35A70, 35A71, and 35A73. The strength of the strongest detection in 35A72, the "face", was 1.75, 1.88, and 4.31 times greater than the strongest detections in these three other frames, respectively. It is noted that the size of these objects (1-2 km) precludes a comparative analysis of terrestrial analogs (e.g., the Great Pyramid) using imagery such as Landsat or SPOT. It is also worth noting that it would be difficult, if not impossible to obtain images of facial profiles such as those carved on Mt. Rushmore since they were not meant to be viewed from above.

Finally, a result from Viking frame 70A10 is presented that suggests that there may be other objectson Mars worth investigating. Fig. 9 shows a 512 by 512 pixel region from 70A10. It is over 100 km from the Cydonia region in Fig. 4. Also shown in Fig. 9 is the fractal model fit error image obtained with the same parameters used earlier. Ignoring the bright areas caused by periodic noise in the data, a strong anomaly is present over an unusual rectangular structure having a circular depression and a tapered "access ramp". Nearby are a pyramidal object and sharp angular features etched into the surrounding terrain.


This paper has presented criteria for identifying objects of possible artificial origin on planetary surfaces, described a technique based on fractal geometry for detecting such objects in planetary imagery, and presented some preliminary results of applying the technique to Viking orbiter imagery. The results presented in this paper suggest there are a number of surface features on Mars that may not be natural. Although it is beyond the scope of this paper to speculate on their origin, the results warrant further investigation. In particular, higher resolution imagery must be collected by the planned U.S. Mars Observer. More importantly, current thinking in the SETI community [22-24] needs to be broadened to include a systematic search for ET artifacts in our solar system. The criteria and techniques discussed in this paper are a starting point for beginning an objective and systematic search for ET artifacts. It is well within the state-of-the-art to process the current Viking orbiter imagery archive (about 60,000 images). Estimated costs of the order of ten million dollars to process existing planetary imagery and create an automated system for screening future imagery is many orders of magnitude less than some of the more ambitious radio search projects that have been proposed.

To paraphrase Van Leeuwenhoek and Denton, perhaps they are not only "dancing in our lenses" but were, or are, at our very doorstep.


The authors wish to thank Keith Hartt for the 3-d surface reconstructions used in the paper.


The object detection technique [21] is briefly presented here so that others can independently verify the results presented in the paper. Given an image x(i, j) a series of grayscale erosions and dilations are computed

where  and  . These are used to compute the volume of a covering of the image intensity surface as a function of the scale parameter

To obtain an estimate of the surface area for an m x n rectangular patch centered at (i, j) thecovering volume at each pixel over a window of the same size is summed and divided by twice the scale parameter:

The fractal model is formally a linear regression model relating the logarithm of the surface area estimates A_r (i, j) to the logarithm of the scale parameter r

where E_r (i, j) is the residual of the linear fit at scale r (i.e. the difference between the actual value of the logarithm of the surface area and the value predicted by the linear model). D(i, j ) is the fractal dimension and is related to the slope of the linear regression of log A_r (i, j) onto log r . The fractal model fit error is the average of the squared residuals

where R is the number of scales.



The anomaly detection technique tacitly assumes that the self-similar structure of terrain is preserved through the imaging process. Pentland [22] and Kube and Pentland [23] have analyzed the properties of images of fractal surfaces and show that under certain conditions the image of a fractal Brownian surface is also fractal Brownian, and hence, self-similar.

The simplified model of the image formation process shown in Fig. B1 was used to verify experimentally that images of fractal surfaces are also fractal. The model ignores atmospheric effects and sensor degradation. It assumes a single point source (the sun), a Lambertian surface reflectance function, constant albedo, and an imaging sensor that is far enough away for a parallel projection to hold. These assumptions appear to be reasonable over small areas on Mars under limited illumination and viewing conditions [12]. A computational model of the image formation process can be divided into two parts: 1) computing a shaded rendition of the surface, and, 2) projecting the shaded surface onto the focal plane of the imaging sensor.

The shaded rendition i(x, y) is related to the elevation surface z(x, y) by the reflectance map R( p, q) where the gradients p =  z /  x and q =  z /  y are the partial derivatives of the elevation in the x and y directions. The reflectance map depends on the reflectance properties of the surface and on the position of the sun. The use of the reflectance map in computing shaded renditions of terrain is discussed by Horn [24]. The location of the sun in gradient space is (p₀ ,q₀ ) where p₀ = tan ₀ cos ₀ , q₀ = tan ₀ sin  ₀ and  ₀ and  ₀ are the azimuth and zenith angles of the sun.

The reflectance map for a Lambertian reflectance function is

Areas that face away from the sun, i.e., where the numerator is negative are assigned zero reflectance.

It is assumed that the imaging sensor is far enough away for a parallel projection to hold [28]. For oblique viewing along the x axis, the point (x,y) is mapped to the point (  ) where

and  ₁ is the zenith angle of the sensor. That is, the surface is foreshortened along the viewing direction (in this case along the x direction). For viewing from another azimuth, the surface is simply rotated so that the line-of-sight is along the x axis. Since for  ₁ > 0, obscuration can occur, the hidden surfaces must first be removed. Then, the shaded rendition i(x, y) is mapped onto the image plane via Eq. B2 and intermediate pixel locations are interpolated to obtain the projection i( ) . Fig. B2 summarizes the fractal properties of images of the fractional Brownian surface shown in Fig. 1. The stability of the fractal dimension and model fit error over a wide range of illumination and viewing conditions implies that images of natural terrain are also fractal. It does not imply however that images containing man-made objects will not also be self-similar. For example, at low solar zenith angles where shading effects are reduced it may be difficult to discriminate man-made objects from the natural background. This phenomenon was noted in Section 4.

1. F. D. Drake, "How can we detect radio transmissions from distant planetary systems?", in Interstellar Communication, A.G.W.Cameron (ed), W.A.Benjamin, New York, 1963.
2. J. Freeman and M. Lampton, "Interstellar archaeology and the prevalence of intelligence," Icarus, Vol 25, pp 368-369, 1975.
3. R. A. Freitas, "Extraterrestrial intelligence in the solar system: Resolving the Fermi Paradox," Journal of the British Interplanetary Society, Vol 36, pp 496-500, 1983.
4. G. Cocconi and P. Morrison, "Searching for interstellar communications," in Interstellar Communication, A.G.W. Cameron (ed), W.A.Benjamin, New York, 1963.
5. T. Denton, "Dancing in our lenses: Why there are not more technological civilizations," JBIS, Vol 37, pp 522-525.
6. R. A. Freitas, "If they are here, where are they? Observational and search considerations," Icarus, Vol 55, pp 337-343, 1983.
7. M. D. Papagiannis, "The importance of exploring the asteroid belt," Acta Astronautica, Vol10, No 10, pp 709-712, 1983.
8. G. V. Foster, "Non-human artifacts in the solar system," Spaceflight, Vol 14, pp 447-453, Dec. 1972.
9. V. DiPietro and G. Molenaar, Unusual Martian Surface Features, Mars Research, GlennDale, MD, 1982.
10. R. Pozos, The Face on Mars: Evidence for a Lost Civilization?, North Atlantic Books, Berkeley, CA, 1986.
11. R. Hoagland, The Monuments of Mars, North Atlantic Books, Berkeley, CA, 1987.
12. M. J. Carlotto, "Digital image analysis of unusual Martian surface features," Applied Optics, Vol 27, pp 1926-1933, 1988.
13. B. B. Mandelbrot, The Fractal Geometry of Nature, W.H.Freeman, New York, 1983.
14. B. B. Mandelbrot and J. Van Ness, "Fractional Brownian motions, fractional noises and applications," SIAM Review, Vol 10, No 4, pp 422-437, 1968.
15. D. M. Mark and P. B. Aronson, "Scale-dependent fractal dimensions of topographic surfaces: An empirical investigation, with applications in geomorphology and computer mapping," Mathematical Geology, Vol 16, No 7, 1984.
16. K. C. Clarke, "Scale-based simulation of topography," Proceedings 8th International Symposium on Computer-Assisted Cartography, Baltimore, MD, pp 680-688.
17. A. Woronow, "Morphometric consistency with the Hausdorff-Besicovitch dimension," Mathematical Geology, Vol 13, No 3, 1981.
18. R. F. Voss, "Random fractal forgeries," in Fundamental Algorithms in Computer Graphics (R.A.Earnshaw, ed), Springer-Verlag, Berlin, pp 805-835.
19. A. Fournier, D. Fussell, and L. Carpenter, "Computer rendering of stochastic models," Communications of the ACM, Vol 25, No 6, June 1982.
20. D. H. Ballard and C. M. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, NJ, 1982.
21. M. C. Stein, "Fractal image models and object detection," Society of Photo-optical Instrumentation Engineers, Vol 845, pp 293-300, 1987.
22. Possibility of Intelligent Life Elsewhere in the Universe, Report prepared for the Committee on Science and Technology U.S. House of Representatives, October, 1977 (revised).
23. M. D. Papagiannis, "Conclusions and recommendations from the joint session on strategies for the search for life in the universe," in Strategies for the Search for Life in the Universe, M.D.Papagiannis (ed), D.Reidel Publishing, Dordrecht, Holland, 1980.
24. M. D. Papagiannis, "The search for extraterrestrial life: recent developments. A report on IAU symposium 112," JBIS, Vol 38, pp 281-285, 1985.
25. A. P. Pentland, Fractal-based description of natural scenes," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 6, No 6, Nov. 1984.
26. P. Kube and A. Pentland, On the imaging of fractal surfaces," IEEE Trans. PAMI, Vol 10, No 5, Sept. 1988.
27. B. K. P. Horn, "Hill shading and the reflectance map," Proceedings of the IEEE, Vol 69, No 1, Jan. 1981.
28. J. D. Foley and A. Van Dam, Fundamentals of Interactive Computer Graphics, Addison- Wesley, Reading, MA, 1983.

Fig. 1 3-d plot of synthetic terrain produced by Voss' method for generating fractional Brownian surfaces (fractal dimension = 2.1)

Fig. 2 Orthographic view of shaded rendition of synthetic terrain (left) and an oblique parallel projection (right).

Fig. 3 Detection of man-made objects. (a) Original image (upper left) has four military vehicles embedded in a complex natural background. (b) Fractal dimension (upper right) and (c) fractal model fit (lower left) images indicate that man-made objects are different than the background. (d) Areas whose fractal dimension is outside of range 2 < D < 2.5 and whose model fit is greater than 90%-ile are shown (lower right).

Fig. 4 Mosaic of Viking orbiter frames 35A72, 73, and 74. Landmarks shown are the "face", the "city", the "D&M pyramid", and the "cliff".

Fig. 5 Detection results show four largest anomalies over the "face" and within the "city".

Fig. 6 Close ups of the "face": down-looking (left) and an oblique view near ground level on the sunlit side (right).

Fig. 7 Close ups of the "fortress" within the "city": down-looking (left) and an oblique view looking into the inner space (right).

Fig. 8 Effect of variable illumination on the detection of anomalous features. Part of 35A72 and fractal model fit error image (top left and right). Part of 70A13 and fractal model fit error image (bottom left and right). Note the difference in the number of false alarms between the right top and bottom images. Square "rings" are caused by noise in imagery.

Fig. 9 Analysis of part of 70A10 frame (top). Fractal model fit error image indicates strong anomaly over rectangular feature with central depression and v-shaped opening. Note pyramidal object and linear features above and to the right.

Fig. B1 Image formation model. Shaded rendition i(x,y) is a function of the reflectance properties of the surface and the position of the light source. An oblique view i(x',y') is generated by a parallel projection.

Fig. B2 Stability of fractal dimension and model fit as a function of sun zenith (top) and view zenith(bottom) angle.