Introduction
In prior work, we have developed computer algorithms for real-time novelty detection and rarity mapping for astrobiological and geological exploration (McGuire et al. Reference McGuire, Ormö, Diaz, Rodriguez, Gomez, Ritter, Oesker and Ontrup2004, Reference McGuire, Diaz, Ormö, Gomez, Rodriguez, Sebastian, Ritter, Haschke, Oesker and Ontrup2005a, Reference McGuire, Gomez, Rodriguez, Sebastian, Ormö, Diaz, Ritter, Oesker, Haschke and Ontrupb, Reference McGuire, Gross, Wendt, Bonnici, Souza-Egipsy, Ormö, Diaz-Martinez, Foing, Bose, Walter, Oesker, Ontrup, Haschke and Ritter2010; Bartolo et al. Reference Bartolo, McGuire, Camilleri, Spiteri, Borg, Farrugia, Ormö, Gomez-Elvira, Rodriguez-Manfredi, Diaz-Martinez, Ritter, Haschke, Oesker and Ontrup2007; Gross et al. Reference Gross, Wendt, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö and Diaz-Martinez2009, Reference Gross, Wendt, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö, Díaz-Martínez, Oesker, Ontrup, Haschke and Ritter2010; Wendt et al. Reference Wendt, Gross, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö, Díaz-Martínez, Oesker, Ontrup, Haschke and Ritter2009). These algorithms were tested at astrobiological field sites using mobile computing platforms originally (McGuire et al. Reference McGuire, Ormö, Diaz, Rodriguez, Gomez, Ritter, Oesker and Ontrup2004, Reference McGuire, Diaz, Ormö, Gomez, Rodriguez, Sebastian, Ritter, Haschke, Oesker and Ontrup2005a, Reference McGuire, Gomez, Rodriguez, Sebastian, Ormö, Diaz, Ritter, Oesker, Haschke and Ontrupb, Reference McGuire, Gross, Wendt, Bonnici, Souza-Egipsy, Ormö, Diaz-Martinez, Foing, Bose, Walter, Oesker, Ontrup, Haschke and Ritter2010) with a wearable computer connected to a digital video camera, but more recently (Bartolo et al. Reference Bartolo, McGuire, Camilleri, Spiteri, Borg, Farrugia, Ormö, Gomez-Elvira, Rodriguez-Manfredi, Diaz-Martinez, Ritter, Haschke, Oesker and Ontrup2007; Gross et al. Reference Gross, Wendt, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö and Diaz-Martinez2009, Reference Gross, Wendt, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö, Díaz-Martínez, Oesker, Ontrup, Haschke and Ritter2010; Wendt et al. Reference Wendt, Gross, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö, Díaz-Martínez, Oesker, Ontrup, Haschke and Ritter2009; McGuire et al. Reference McGuire, Gross, Wendt, Bonnici, Souza-Egipsy, Ormö, Diaz-Martinez, Foing, Bose, Walter, Oesker, Ontrup, Haschke and Ritter2010) with a phone camera connected wirelessly to a local or remote server computer. The image features used in the novelty detection and rarity mapping in prior work were based only upon RGB or HSI colour.
Nonetheless, even with image features limited to colour, the mobile exploration systems worked very robustly. Based on an analysis of the procedures governing the team's geologists when analysing an encountered outcrop, we developed a concept of ‘novelty detection’ for guiding the Cyborg Astrobiologist system in a first step towards mimicking the geologist's approach. Very simplified, the geologist's decisions when approaching an outcrop are based upon observations that may be useful to ‘tell the tale’ about the outcrop, i.e. relations between individual parts of the outcrop. This can, for instance, be contacts between different lithologies, alteration sequences, diagenetic variations or structures such as beddings or fractures. Commonly, such variations are, at a first distant glance of an outcrop, expressed as colour and/or texture variations. In, for instance, the case of colour variations, the geologist may decide that it is a certain colour that stands out from a more common background that should be given special attention, i.e. as ‘interest points’. The next step for the geologists is, thus, usually to investigate the contacts between these first-order ‘interest points’ and the background. When further advancing on the outcrop, new ‘interest points’ of more detailed scale are selected based upon the same principle in a somewhat iterative way. The ‘colour-only’ Cyborg Astrobiologist has, in our first tests, been employed in unvegetated, desert-like environments where it was able to identify novel or uncommon areas in image sequences, ranging from mostly white-coloured gypsum to mostly red-coloured ‘red bed’ sandstones. The system was able to identify, for example, bleached areas and hematite concretions in the red beds of Spain, and lichens of varying colours within the desert landscapes of Spain and Utah as being novel features (when first observed) of those landscapes (Gross et al. Reference Gross, Wendt, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö and Diaz-Martinez2009, Reference Gross, Wendt, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö, Díaz-Martínez, Oesker, Ontrup, Haschke and Ritter2010; Wendt et al. Reference Wendt, Gross, McGuire, Bonnici, Foing, Souza-Egipsy, Bose, Walter, Ormö, Díaz-Martínez, Oesker, Ontrup, Haschke and Ritter2009; McGuire et al. Reference McGuire, Gross, Wendt, Bonnici, Souza-Egipsy, Ormö, Diaz-Martinez, Foing, Bose, Walter, Oesker, Ontrup, Haschke and Ritter2010). However, another important factor in addition to colour variations in the decision-making of the geologist when approaching an outcrop is texture, the objective of this study.
Herein, using data acquired by the Astrobiology Phone-cam at a geological field site (Fig. 1), we test an image-comparison technique of Heidemann and Ritter (Reference Heidemann and Ritter2008a, Reference Heidemann and Ritterb), which uses image compression and is capable of (i) detecting novel (coloured) textures in a series of images as well as of (ii) alerting the user to the similarity of a new image to a previously observed texture. We first implemented this technique in 2010 (Bonnici et al. Reference Bonnici, Gross, McGuire, Ormö, Walter and Wendt2010), but did not test this software at a geological field site until now. Such a capability could be useful in giving more scientific autonomy to robotic planetary rovers (Volpe Reference Volpe2003; Fink et al. Reference Fink, Dohm, Tarbell, Hare and Baker2005, Castano et al. Reference Castano, Estlin, Gaines, Chouinard, Bomstein, Anderson, Burl, Thompson, Castano and Judd2007; Halatci et al. Reference Halatci, Brooks and Iagnemma2007, Reference Halatci, Brooks and Iagnemma2008), and perhaps in assisting human astronauts in their geological explorations. For example, suppose that a semi-autonomous planetary rover equipped with texture-based novelty detection is observing a long series of textures corresponding to hematite concretions embedded in mineral deposits. With texture-based novelty detection (Gulick et al. Reference Gulick, Morris, Ruzon and Roush2001, Reference Gulick, Hart, Shi and Siegel2004; Thompson et al. Reference Thompson, Allwood, Bekker, Cabrol, Estlin, Fuchs and Wagstaff2012), this rover would report, during stage 1 of its approach towards the outcrop, that a particular previously unobserved horizontally layered texture is novel, and hence merits further investigation. In stage 2, it would detect smaller spherical objects, possibly even of a different colour relative to the background, within the previously observed layers. Depending on the resolution of the camera, this process could continue iteratively, with further observations of onion-layering of the spherules and so forth. A certain amount of autonomous decision-making of the rover would, in this way, greatly reduce the amount of data to be transferred between the rover and the scientists.
Fig. 1. The Cyborg Astrobiologist using its image-comparison software with the Astrobiology Phone-cam to study lichens (left picture) and coal with cleats (right picture) at the geological field site (photos by K.R. Bruner).
Heidemann and Ritter's image-compression technique
Following Heidemann and Ritter (2008a, b), we ‘calculate the similarity of two images I 1, I 2 as:
$$ D_{{\rm SIM}} (I_1, I_2 ) = S(I_1 ) + S(I_2 ) - S(I_{12} ),$$where S(·) denotes the [(single-number) byte] size of a compressed image. I 12 is the ‘joint’ image obtained as juxtaposition of pixel arrays I 1 and I 2’. If the two images are very similar, then S(I 12) will be small and D SIM(I 1, I 2) will be large. If the two images are very different (due to textural and colour differences), then S(I 12) will be large and D SIM(I 1, I 2) will be small.
The juxtaposition in our implementation is left–right, but we have not compared our implementation to an up–down juxtaposition. Various image-compression programmes were investigated by Heidemann & Ritter (Reference Heidemann and Ritter2008a, Reference Heidemann and Ritterb), and their optimal image compressor for texture classification was gzip, which we have chosen as our image compressorFootnote 1. Gzip relies on Huffman entropy coding (Huffman Reference Huffman1952; see also Saravanan & Ponalagusamy Reference Saravanan and Ponalagusamy2010) and the Lempel–Ziv algorithm (Lempel & Ziv Reference Lempel and Ziv1977; see also Kärkkäinen et al. Reference Kärkkäinen, Kempa, Puglisi, Bonifaci, Demetrescu and Marchetti-Spaccamela2013). Huffman coding is based on how frequent the symbolsFootnote 2 are in a data stream, assigning shorter bit-length representations for more commonly used symbols. The Lempel–Ziv algorithm (LZ77) eliminates duplicate strings of symbols using ‘sliding-window compression’ (referring to the buffer window that records the previously observed symbols in the data stream)Footnote 3. Quoting Heidemann & Ritter (Reference Heidemann and Ritter2008b): ‘The Lempel–Ziv algorithm (LZ77) (Lempel & Ziv Reference Lempel and Ziv1977), which detects repeatedly occurring symbol sequences within the data, such that a dictionary can be established. A repeated symbol sequence can then be replaced by the symbol defined in the dictionary.’Footnote 4 The gzip algorithm outperforms (Heidemann & Ritter Reference Heidemann and Ritter2008b) the correlation technique and the histogram-based matching technique for the texture-classification, object-recognition and image-retrieval tasks.
By employing a simple image-compression technique such as Heidemann and Ritter's, we can avoid the complexities and ambiguities of more reductionist textural comparison techniques (i.e. Haralick et al. Reference Haralick, Shanmugam and Dinstein1973; Rao Reference Rao2012), wherein a significant number of different textural indicators (at different spatial scales and orientations) are computed and mapped for each image.
In order to simplify interpretation, we have taken the logarithm of D SIM and added a normalization factor, so that the maximal range of D SIM is 0–100% for the current database of images. We accomplish this by comparing the newest image to itself and setting the value obtained as the 100% similarity value. One would expect this value of D sim(I N,I N) to be slightly smaller than S(I N) since the two images being compared are the same, but the changes at the boundary (between the two identical juxtaposed images) introduce a discrepancy in the value of D sim(I N,I N).
Field tests
The Astrobiology Phone-cam system sends images wirelessly by Bluetooth to a nearby laptop computer, dynamically building an image library with examples from different terrain. The Phone-cam for this field test is a Samsung SGH-A767 with 1280×960 RGB colour images, and the laptop is a Dell Inspiron 9300. Each incoming image I N is processed by a compiled MATLAB code by the laptop using equation (1) to compute the similarity D SIM(I N, I J), with each previous image, I J. If D SIM(I N, I J) is less than a chosen threshold for all previous images I J (for all J<N), then the computer considers image I N as ‘novel’ and returns a text message to the Phone-cam by Bluetooth informing the explorer that the image is novel. If the image is novel, the explorer might decide to perform a more detailed analysis of the ground or rocky outcrop that image I N represents. If D SIM(I N, I J) is greater than the chosen threshold for one or more of the previous images I J, then the image I K, which has the highest similarity score (highest value of D SIM(I N, I K)), is returned to the phone camera via Bluetooth, juxtaposed with I N, in order for the user to assess the similarity visually. We have performed tests of this procedure for detecting novelty or similarity; a set of example images in the test sequence and their best-matching prior images are juxtaposed in Fig. 2. Image pairs such as in Fig. 2 are the visual information that the image-compression algorithm on the laptop computer outputs and then sends to the phone camera for inspection.
Fig. 2. Good matches: Incoming image I N is on the left, and best-matching image is on the right. Each image is about 0.5 m across. (a) Platy-rock texture (laminated shale); (b) yellow-sporing bodies of lichens; (c) coal bed.
Owing to its proximity to three of the authors (McGuire, Smosna and Bruner) at the time of the survey, we chose a geological field site near the northern end of the Morgantown Mall in Morgantown, West Virginia, USA. This mall is the former site of a coal mine, so there are several exposed geological cuts, including one of a coal bed. These rocksFootnote 5 comprise a part of West Virginia's coal measures, in particular the lowest section of the Pittsburgh Formation, and have a late Carboniferous age. The outcrop exposes a heterogeneous mix of coal, sandstone, shale, mudstone and limestone, typically occurring in beds of 30–150 cm thickness. The photographed coal is the Pittsburgh coal, about 3 m thick with well-developed cleats (fractures) and elemental sulphur on the face. The sandstone ranges from being thin-bedded to being massive with planar bedding and cross-bedding. The shale is characteristically thinly laminated. The mudstone shows a nodular character and locally contains ironstone concretions (composed of iron carbonate and iron silicate minerals). The limestone exhibits spherical weathering and solution features.
Our original plan was to use the Cyborg Astrobiologist's image-compression system at the geological field site, acquiring and analysing about 25 images in the 1.5 h battery lifetime of the laptop server computer (it takes an average of 3–4 min to analyse each image). However, at the field site, we decided to acquire 55 imagesFootnote 6 with the Astrobiology Phone-cam in 1 h, and then to analyse the images offline after the field work was completed. This offline analysisFootnote 7 lasted for about 4 h, longer than the battery life of the laptop. Therefore, this was not the ideal real-time test, but all the capabilities of the system were otherwise tested and more images could be analysed than during a real-time test.
Three of the 55 result images are shown in Fig. 2. Figure 2(a) shows the platy-rock texture on the left, and the best-matching of the prior images on the right. This is indeed a successful match. Likewise, it was a successful match for the yellow-sporing bodies of the lichens in Fig. 2(b), and for the coal bed in Fig. 2(c). Generally, for each image which was not novel, the computer successfully matched it best with another image of similar texture and/or colour statistics.
For those images which were novel, the computer either gave a low D SIM score (<39%) or matched it with a higher score with an image that even the human analyst would say is similar. See Fig. 3 for examples of the novel images and their best matches in the database. Figure 3(a) shows the low D SIM score for the novel platy texture with the best-match smooth iron-stained texture. Figure 3(b) shows the low D SIM score for the novel yellow-sporing bodies of the lichens with the best-match platy texture with red clast. And Fig. 3(c) shows the higher D SIM score for the novel coal bed with the best-match yellow-sporing bodies of the lichens. In Fig. 3(c), the score is likely to be higher because the substrate rock for the yellow lichen is black, much like a large part of the coal bed, and because the coal bed has some pale yellow colouring due to sulphur content.
Fig. 3. Novel images: Incoming image I N is on the left, and best-matching image is on the right. Each image is about 0.5 m across. (a) Novel platy-rock texture; (b) novel yellow-sporing bodies of lichens; (c) novel coal bed.
In Table 1, we estimate the number of images that are novel, similar or different, as judged by three members of our human teamFootnote 8, and the number of images that are novel but have high similarity scores, the number of images that are similar and the number of images that are similar with low similarity scores. A more detailed compilation of our results is shown in Table 2, listing for each of the 55 incoming images: (i) which prior image matched best, as well as (ii) notes about novelty and mismatching. The range of observed scores for matching images is generally about 39–50%. Lower scores generally signify novelty, although there are some novel images with scores above 39%, due to similarity to other geological units (see Table 1). The threshold of 39% between similarity and novelty was chosen after the experiment, and it is not a perfect threshold, but it is approximately the right value for these images.
Table 1. Summary of results.
Accuracy of Novelty detection: 9/14=64%.
Accuracy of Similarity detection: 31/34=91%.
Accuracy of Difference detection: 2/6=33%.
Overall accuracy: 42/54=78%.
Table 2. Detailed results.
Note: a new image database was created with the first image, which was image #264.
There are examples where the ∼48% score appears rather low (for instance, the pair 273/272, where the two images appear to the human observer identical, apart from a small vertical shift). We would expect that the algorithm should be able to detect this better: if the strategy is to compare horizontal scan line (pieces), then the vertical shift should leave many scan line similarities intact and a high value should result (but there might still be high sensitivity to rotation). Based upon prior tests, we believe that the reason the highest scores are not near 100% is because of the discontinuity between the juxtaposed images.
Discussion
The intent of our algorithm is to analyse a series of images made in a homogeneous environment (a common outcrop), which slightly changes over time. The scope here is to automatically detect sudden variations in the outcrop's visual appearance, for the purpose of minimizing interactions by the human scientists who are supervising the robotic rover from afar. We do not expect our current algorithm to be able to extrapolate to a new field site in order to identify lichens or coal or other coloured textures that were observed at a prior field site, for the following reasons:
First, these coloured textures would most likely have significant intrinsic variability in their colour or textural qualities from one site to the next. However, if the colour and textural qualities were the same or similar, then the similarity matching and novelty detection would work well.
Second, we have not controlled for lighting conditions or photometric angles of observation. We do not attempt such control in the present work, since our main objective is to test the similarity-matching and novelty-detection capabilities of the image comparison algorithm. Nonetheless, in a much more advanced system, real-time photometric and atmospheric correction could be added, similar to the post-processing correction system for the CRISM camera on the Mars Reconnaissance Orbiter (McGuire et al. Reference McGuire, Wolff, Smith, Arvidson, Murchie, Clancy, Roush, Cull, Lichtenberg, Wiseman, Green, Martin, Milliken, Cavender, Humm, Seelos, Seelos, Taylor, Ehlmann, Mustard, Pelkey, Titus, Hash and Malaret2008). We did not need such photometric or atmospheric control for the field tests completed here, since the lighting conditions were the same (overcast) throughout the one-hour field test.
Third, at the new field site, the colour and textural properties of the images may have different spatial scales than at the original field site. Careful control of the camera distance to the rock outcrop may lessen the differences in spatial scale of the coloured textures in the images from one field site to another. In the current field tests, we have only tested the system at a single image scale or resolution, given by the human operator locating the camera about 1 m away from the outcrop. This single-scale property of the images could be approximated on a Mars rover, for example by using an imaging camera held by the robotic arm at a fixed distance from the outcrop. We do not have plans currently to develop an algorithm that is capable of distinguishing between coloured textures at different spatial scales.
Fourth, this algorithm is an unsupervised algorithm; it does not need to know prior image classifications in order to identify novel or familiar coloured textures. The algorithm does not know that an image is one of lichen or a coal bed – it just can classify an image as familiar or novel, based upon similarity to previous images. So, the algorithm cannot really identify lichens or coal as being lichens or coal. The algorithm does not need to know what it is looking at ahead of time. The classifications were made by human geologists a couple of days after the field test. The intent of the algorithm is to allow the robotic astrobiologist to find those areas of a rocky outcrop that are similar to each other (for mapping purposes) and those areas of a rocky outcrop that are novel (for further investigation and/or sample acquisition).
These conditions exactly correspond to the requirements for an extraterrestrial robotic image-acquisition system, where many images are autonomously taken in a mostly homogeneous environment. Sudden changes or exceptions in the environment could be flagged and reported to the human scientists on Earth, effectively scanning the immense number of images for anomalies (possibly of astrobiological interest).
Conclusions and future
Our initial tests at a geological field site of this texture-based algorithm for image comparison show promise for both novelty detection and for similarity matching. The similarity matching was superb (91%), especially of images of the yellow lichens and of images of the coal bed. Our next step is for the Cyborg Astrobiologist to perform more extensive field testing of this algorithm with the Astrobiology Phone-cam at other geological/astrobiological field sites.
Testing with grey-scale cameras and multispectral cameras are possible extensions of this work. To simulate images taken by a rover, one could take videos and randomly select frames from the video. We also hope to speed up the algorithm so that it can analyse ∼100 images in a laptop-battery-limited real-time test of 1.5 h. This speed-up can be accomplished perhaps by using the cluster characteristics of the image database so that each image is only compared with one image of each cluster of the database. The speed-up could also be accomplished by eliminating the delays of Bluetooth transmission and developing an app for smartphones which acts directly on the smartphone as soon as the image is captured; this would at least reduce the bottleneck to one battery life rather than two, and carrying a spare phone battery is much easier than carrying around a spare laptop battery. Another extension of the system could be useful for offline analysis: allowing for an image to be segmented for texture with this compression algorithm. This could lead the Cyborg Astrobiologist to understand further the images, so that the software could be used by a Robotic Astrobiologist to zero in on novel astrobiological/geological areas of outcrops.
Acknowledgements
We thank Helge Ritter for suggesting the image-compression technique to us, and Tim Warner for help with identifying a field site in West Virginia. PCM acknowledges past support by a research fellowship from the Alexander von Humboldt Foundation, support from the Freie Universität Berlin, and computer resources for the preparation of this manuscript at the library of West Virginia University. CG acknowledges the Helmholtz Association through the research alliance ‘Planetary Evolution and Life’. The work by JO is supported by grants AYA2008-03467⁄ESP and AYA2011-24780/ESP from the Spanish Ministry of Economy and Competitiveness.
