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

The Analytic Sciences Corporation

55 Walkers Brook Drive

Reading, MA 01867 USA

The focus of the search for extra-terrestrial intelligence (SETI) has been to look outside our solar system at radio frequencies for signs of intelligent life. Such a strategy is consistent with current information which suggests that it is unlikely that intelligent life could have evolved on the other planets in our solar system. Our knowledge to date cannot, however, rule out the possibility that extra-terrestrials or their probes may have reached this solar system. If so, they may have altered planetary surfaces in ways that are detectable through remote sensing. An alternative strategy is proposed which involves extending SETI to include a systematic search for anomalous, i.e., possible non-natural objects on planetary surfaces. An approach for detecting anomalous objects in planetary imagery based on the fractal modeling of terrain is described. Fractals have been successfully used to model a wide range of physical and biological phenomena, including natural terrain. This success is due, in part, to a property of fractals known as self-similarity, i.e., fractals look the same, in some sense, across a range of scales or resolutions. The anomaly detection technique described in this paper is based on identifying areas in terrain that lack self-similarity. Preliminary results of applying the technique to Viking orbiter imagery suggest that certain objects on the Martian surface currently under investigation may not be natural.

The search for extra-terrestrial intelligence at radio frequencies began with project Ozma [1] and has, as of yet, produced no evidence for their existence. The success of such an endeavor requires that: 1) there are advanced technological civilizations in the galaxy that are either communicating with one another or trying to communicate with us, 2) we are able to detect their signals, and 3) we will be able to decipher the message when we receive it.

The Drake equation [2] has been a starting point for speculating on the number of technological civilizations in the galaxy. At one extreme, some say that we are the only advanced civilization in the galaxy since if there were others we would know about them. This is known as the Fermi Paradox due to a question asked by Enrico Fermi in the 1940s. At the other extreme, others have estimated upwards of billions of advanced technological civilizations in the galaxy. Evidence in favor of either extreme is scarce. Estimates derived from the Drake equation depend on parameter values which are obviously based on our very limited experience in contacting extra-terrestrials (ETs). Freitas [3] argues that the Fermi Paradox cannot be proven. In any case, the consensus is that the number of advanced civilizations is somewhere in between the two extremes and is sufficient to warrant some kind of search.

Many believe that the best channel for ET communications is at 1420 MHz, the frequency at which atomic hydrogen radiates [4]. Even with this as a starting point, as the bandwidth of spectrum analyzers decreases and the angular resolution of radiotelescopes increases, the number of frequencies and directions that we must search will continue to increase. Most feel that the lack of success is due to the very limited portion of the "search space" covered to date. Others believe that we do not yet have the technology to detect and decipher ET radio transmissions or may be looking for a signal that is simply not there [5].

An alternative strategy has been put forth more recently that involves searching for ET probes or artifacts. Freitas [6] has proposed that we search for messenger probes in the vicinity of the earth. Based on the argument that intelligent life has the natural tendency to expand into and occupy space, and requires raw materials to support such expansion, e.g., for building space colonies, Papagiannis [7] argues that if ETs are in our solar system, they may be in the asteroid belt. Using arguments similar to those based on Drake equation, Foster [8] estimates frequencies of visitations by ETs or their messenger probes and goes on to suggest the possibility that past encounters may have left behind artifacts or indirect evidence (e.g., deranged planetary terrain).

This last idea is the point of departure for this paper, that there may be artifacts that have already been imaged by probes such as the Viking Orbiter. For example, there has been considerable interest recently in a collection of unusual surface features in the Cydonia region of Mars [9-12]. Is there a way to objectively assess these and other surface features so that future missions such as the Mars Observer can gather more data?

In order to carry out an objective search for artificial features, detection criteria must be established. Current SETI strategies have been criticized on epistemological grounds, i.e., we are looking for what we think is out there [5]. Since we do not really know what we are looking for, it is not possible to define in a direct way what is "artificial". However, one can attempt to define what is natural and proceed to measure the "naturalness" of unknown features. Artificial features are then identified as those farthest from "natural" in some sense.

The contributions of this paper are: 1) to attempt to define objective criteria for identifying possible artificial objects, 2) to describe a technique based on fractal geometry for detecting such objects, 3) to present some preliminary results of applying the technique to Viking orbiter imagery that suggest that certain unusual Martian surface features may not be natural, and 4) to outline a strategy for continuing the search as part of on-going planetary exploration programs.

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

(1)

where

(2)

where

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,

(3)

their surface area,

(4)

or their power spectral density,

(5)

where

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

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 (

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

(6)

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

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

(A1)

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

(A2)

To obtain an estimate of the surface area for an

(A3)

The fractal model is formally a linear regression model relating the logarithm of the surface area estimates

(A4)

log A_{r}
(i, j) =[2 - D(i, j)]log r + Er (i, j)

where

(A5)

where

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

The reflectance map for a Lambertian reflectance function is

(B1)

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 (

(B2)

and

- 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.
- J. Freeman and M. Lampton, "Interstellar archaeology and the prevalence of intelligence," Icarus, Vol 25, pp 368-369, 1975.
- 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.
- G. Cocconi and P. Morrison, "Searching for interstellar communications," in Interstellar Communication, A.G.W. Cameron (ed), W.A.Benjamin, New York, 1963.
- T. Denton, "Dancing in our lenses: Why there are not more technological civilizations," JBIS, Vol 37, pp 522-525.
- R. A. Freitas, "If they are here, where are they? Observational and search considerations," Icarus, Vol 55, pp 337-343, 1983.
- M. D. Papagiannis, "The importance of exploring the asteroid belt," Acta Astronautica, Vol10, No 10, pp 709-712, 1983.
- G. V. Foster, "Non-human artifacts in the solar system," Spaceflight, Vol 14, pp 447-453, Dec. 1972.
- V. DiPietro and G. Molenaar, Unusual Martian Surface Features, Mars Research, GlennDale, MD, 1982.
- R. Pozos, The Face on Mars: Evidence for a Lost Civilization?, North Atlantic Books, Berkeley, CA, 1986.
- R. Hoagland, The Monuments of Mars, North Atlantic Books, Berkeley, CA, 1987.
- M. J. Carlotto, "Digital image analysis of unusual Martian surface features," Applied Optics, Vol 27, pp 1926-1933, 1988.
- B. B. Mandelbrot, The Fractal Geometry of Nature, W.H.Freeman, New York, 1983.
- B. B. Mandelbrot and J. Van Ness, "Fractional Brownian motions, fractional noises and applications," SIAM Review, Vol 10, No 4, pp 422-437, 1968.
- 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.
- K. C. Clarke, "Scale-based simulation of topography," Proceedings 8th International Symposium on Computer-Assisted Cartography, Baltimore, MD, pp 680-688.
- A. Woronow, "Morphometric consistency with the Hausdorff-Besicovitch dimension," Mathematical Geology, Vol 13, No 3, 1981.
- R. F. Voss, "Random fractal forgeries," in Fundamental Algorithms in Computer Graphics (R.A.Earnshaw, ed), Springer-Verlag, Berlin, pp 805-835.
- A. Fournier, D. Fussell, and L. Carpenter, "Computer rendering of stochastic models," Communications of the ACM, Vol 25, No 6, June 1982.
- D. H. Ballard and C. M. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, NJ, 1982.
- M. C. Stein, "Fractal image models and object detection," Society of Photo-optical Instrumentation Engineers, Vol 845, pp 293-300, 1987.
- 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).
- 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.
- M. D. Papagiannis, "The search for extraterrestrial life: recent developments. A report on IAU symposium 112," JBIS, Vol 38, pp 281-285, 1985.
- A. P. Pentland, Fractal-based description of natural scenes," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 6, No 6, Nov. 1984.
- P. Kube and A. Pentland, On the imaging of fractal surfaces," IEEE Trans. PAMI, Vol 10, No 5, Sept. 1988.
- B. K. P. Horn, "Hill shading and the reflectance map," Proceedings of the IEEE, Vol 69, No 1, Jan. 1981.
- 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.

† Corrected and revised version of original paper published in the Journal of the British Interplanetary Society, Vol. 43, pp 209-216, 1990.

† Descriptive terms such as the "city" and "fortress" have been used by various investigators for the sake of convenience and consistency. They do not imply an endorsement of particular interpretations of these objects.