2
MPP-based Crater Detection
and Registration of Planetary
Images
Because of the large variety of planetary sensors and spacecraft already col-lecting data and with many new and improved sensors being planned for future missions, planetary science needs to integrate numerous multimodal image sources and, as a consequence, accurate and robust registration al-gorithms are required. In this Chapter, we develop a new framework for crater detection based on marked point processes (MPP) that can be used for planetary image registration. MPPs were found effective for various ob-This chapter is based on the following publications and patent:
D. Solarna, A. Gotelli, J. Le Moigne, G. Moser and S. B. Serpico, "Crater Detection and Registration of Planetary Images Through Marked Point Processes, Multiscale Decom-position, and Region-Based Analysis", in IEEE Transactions on Geoscience and Remote Sensing, vol. 58, no. 9, pp. 6039-6058, Sept. 2020, doi: 10.1109/TGRS.2020.2970908. D. Solarna, G. Moser, J. Le Moigne, and S. B. Serpico, "Planetary crater detection and registration using marked point processes, multiple birth and death algorithms, and region-based analysis", Proceedings of the 2017 IEEE International Geoscience and Remote Sens-ing Symposium (IGARSS 2017), Fort Worth, Texas, USA, July 2017.
J. Le Moigne, D. Solarna, A. Gotelli, S. B. Serpico, G. Moser, "System and method of crater detection and registration using marked point processes, multiple birth and death methods and region-based analysis", United States Patent US 10,825,182, United States Patent and Trademark Office, November 3, 2020.
ject detection tasks in Earth observation, and a new MPP model is proposed here for detecting craters in planetary data. The resulting spatial features are exploited for registration, together with fitness functions based on the MPP energy, on the mean directed Hausdorff distance, and on the mutual infor-mation. Two different methods — one based on birth-death processes and region-of-interest analysis and the other based on graph cuts and decimated wavelets — are developed within the proposed framework. Experiments with a large set of images, including 13 thermal infrared and visible images of the Mars surface, 20 semi-simulated multitemporal pairs of images of the Mars surface, and a real multitemporal image pair of the Lunar surface, demon-strate the effectiveness of the proposed framework in terms of crater detection performance as well as for sub-pixel registration accuracy.
2.1 Introduction
The increasing number of images that have been collected by different plane-tary missions over the past few decades is a precious source of information for planetary science [17]. The characteristics of these multimodal data depend on the kind of sensor, the observation time, the acquisition geometry, etc. In this context, semi-automatic and efficient registration is a crucial first step in the subsequent analysis of these images, since it allows data acquired by different sensors or at different times to be compared and jointly used.
The first goal of this Chapter is to propose a new approach to semi-automatic registration of planetary images. Indeed, area-based and feature-based approaches to registration have been found effective when applied to multiple types of image [16]. In particular, when using feature-based ap-proaches, an effective spatial feature extraction (i.e., the extraction of spatial characteristics from the imaged scene) is a crucial step. Feature extraction in planetary images and co-registration of this type of images represent very time-consuming endeavors, possibly involving manual intervention by human experts. Efforts have been put on the development of automatic registration methods as well [18–20]. Indeed, the identification of spatial features on planetary surfaces is often a difficult task: the amount of available data is usually limited, planetary images generally present low contrast (being heav-ily affected by illumination, surface properties, and atmospheric state), and some spatial features can be barely visible [17]. Among the typical spatial
2.1. INTRODUCTION
structures that characterize planetary surfaces, craters are of primary impor-tance.
In the planetary science community, there is a growing interest in the automatic extraction of craters from planetary images. Indeed, catalogues of extracted craters have been generated, based on planetary image datasets and partly involving automated image analysis stages, and made publicly available [21–24]. Such catalogues are particularly important for planetary science studies, for instance to analyze the distribution of craters on the planets, their characteristics (e.g., delineation, diameter, depth, slope, circu-larity index, roughness index), and their morphology and degradation pro-cesses [25–28]. Methods to detect craters from planetary imagery and eval-uate the aforementioned characteristics have been extensively exploited to study the history of planets [24,29,30].
In this Chapter, crater detection is addressed in an unsupervised fash-ion using the theory of marked point processes (MPPs). The derived craters are also exploited to address the registration problem with planetary im-ages. MPPs represent a powerful family of stochastic geometry models for the spatial distribution of parameterized objects or structures in the im-age plane [31, 32]. They have been found effective in various applications to Earth observation (EO) and, in this Chapter, we propose a novel MPP model for planetary crater detection. Operatively, the problem is formalized as the minimization of a suitable energy function in the space of all admis-sible arrangements of craters in the scene [31]. The energy encodes the de-sired prior behavior of the crater configuration and its fitness with the input planetary data. Once the crater features have been extracted, feature-based and area-based registrations are performed by optimizing similarity functions that measure the fitness between two images to be registered [16]. These functions are based on metric-space (Hausdorff distance) [33], information-theoretic (mutual information) [34], and MPP energy concepts. Genetic [35] and generalized pattern search [36] algorithms are involved to address the related numerical minimization tasks.
Within this overall proposed methodology for crater detection and plan-etary image registration, two specific algorithms are developed. They share the same MPP energy and differ in the energy minimization strategy and in the formulations adopted to improve computational efficiency. In partic-ular, birth-and-death processes [31], graph cuts [37–39], decimated wavelet
transforms (DWT) [40,41], and region-of-interest (ROI) analysis [42] are in-corporated into the two methods.
The proposed framework and algorithms are experimentally validated with a large set of images, including 13 thermal infrared (TIR) and visible images of the Mars surface, 20 semi-simulated multitemporal pairs of images of the Mars surface, and a real multitemporal pair of the Lunar surface. The results demonstrate the effectiveness of the proposed approach as compared to previous techniques for both crater detection and image registration.
This chapter is organized as follows. A state-of-the-art survey is re-ported in Section 2.2. Section 2.3 presents the general developed framework, while the two specific proposed methods are described in Sections 2.4 and 2.5. Section 2.6 presents and discusses the experimental results. Finally, conclusions are drawn in Section 2.7.
2.2 Previous Work
The aim of this section is to survey previous works on crater detection, marked point processes, and feature-based image registration. Each sub-section addresses one of these topics.
2.2.1 Crater Detection in Planetary Images
The methods for crater detection can be divided into three broad categories: supervised algorithms requiring input pre-labeled data; unsupervised meth-ods using image processing techniques and possibly user interaction but no training data; and hybrid techniques mixing unsupervised and supervised concepts in a pipeline structure.
Focusing first on supervised methods, in [43] a continuously scalable template-matching algorithm was tested, while in [44] various supervised learning algorithms, including ensemble methods, support vector machines (SVM), and continuously scalable template models, were employed to derive crater detectors from ground-truth images. The SVM approach with normal-ized image patches provided detection and localization performance closest to that of human labelers and was found more accurate than boundary-based approaches such as the Hough transform (see below). A supervised boost-ing algorithm, built from the solution proposed in [45] for face recognition,
2.2. CRATER DETECTION IN PLANETARY IMAGES
was presented in [46]. In [47], in a saliency detection framework aimed at extracting lunar craters, speeded-up robust features (SURF) [48] were ex-tracted from lunar images in order to generate ROIs to be classified using an SVM classifier. Among recent works, the method developed in [49] made use of histogram of oriented gradient (HOG) features and SVM classification to extract small-scale craters.
Unsupervised techniques are generally based on the identification of cir-cular or elliptical shapes in the image by using edge information. A consol-idated approach is based on the generalized Hough transform (GHT) [50], which was used in [51–55]. In [56], Bandeira et al. developed a crater de-tection method based on the analysis of the probability volume created as a result of a template-matching procedure that approximated the craters as circular objects. Texture analysis and ellipse fitting were used in [57]. In [58], an unsupervised method was proposed for the extraction of elliptical objects, such as craters and rocks of compact shape (e.g., boulders), to be used for registration. The approach combined image filtering, Canny edge detection (Canny), watershed segmentation (Hanbury), and GHT (Ballard). In the context of saliency detection, the work in [59] combined ellipse fitting techniques and the mapping of salient crater edge features in the application to lunar and Mars images. Edge detection and Hough transforms were also applied to digital elevation models (DEM) collected over Mars in [60]. Simi-larly, watershed segmentation and mathematical morphology operators were applied in [26,28,61] to DEM data for crater detection and delineation.
Hybrid combinations of supervised and unsupervised techniques have also been proposed. For example, in [62], to automatically detect craters on Mars, edge detection, template matching, and supervised neural networks (NNs) were integrated, using the NN for the recognition of false positives. Another example can be found in [63], where mathematical morphology and supervised techniques were used to detect craters and distinguish between objects and false alarms, respectively. A more recent example of hybrid combination was proposed in [64], where: (i) an initial classifier was trained with few samples; (ii) the resulting classifier was used to extract a large set of candidate craters; and (iii) a DEM was used to discriminate between false and true positives and update the training pool.
Among other approaches, we recall those in [65] and [66]. The former was based on a convolutional neural network (CNN) while, in the latter, Haar-like
textural features were extracted from pairs of shaded/highlighted regions and used to train an SVM. Crater detection techniques based on deep learning and formulated through CNN architectures have been extensively explored in the last few years. In addition to [65], further examples are reported in [29] and [30], where CNNs were used to extract craters from planetary image data in the context of planetary science studies (for example to count the craters in a given area), or in [67], where CNNs were applied to DEM data and craters were modelled as circles.
2.2.2 Marked Point Processes for Object Detection
MPPs represent stochastic models of a collection of objects in an imaged scene. They provide elegant probabilistic formulations for the problem of detecting an arbitrary number of objects with possibly complicated spatial arrangements [31,32]. In EO, they have been found successful for the detec-tion of, for example, tree crowns [68], building outlines [69, 70], roads [71], boats [72], people [73], and flamingos [74]. In [75], a method was developed for incorporating strong prior shape information into an MPP model for the extraction of arbitrarily shaped objects from images.
MPPs formalize object detection as an energy minimization problem, where the energy function captures data likelihood and prior constraints ac-cording to the specific application [31]. The minimization task is a challeng-ing combinatorial problem for which advanced stochastic algorithms have been developed. Methods based on reversible jump Markov chain Monte Carlo (RJMCMC) samplers and simulated annealing were proven successful to get the maximum a posteriori estimator of the object distribution in the image [68]. They incorporate appropriate “kernels” that formalize local and global perturbations in the configuration of objects but often involve long computation times. An application of such an approach to crater detection can be found in [76]. Multiple birth-and-death (MBD) dynamics were also coupled with a simulated annealing scheme to perform multiple perturba-tions jointly and favor computational efficiency [70,72,73,77]. More recently, a semi-deterministic multiple birth-and-cut (MBC) algorithm, which com-bined a random birth process and a deterministic binary classifier based on graph cuts [38,39], without involving any annealing schedule, was also devel-oped [78–80].
2.2. IMAGE REGISTRATION WITH CONTOUR FEATURES
2.2.3 Image Registration with Contour Features
With a wide spectrum of applications to diverse categories of data, image registration has evolved into a complex and challenging problem for which many solution strategies have been proposed [16]. The growing availability of digital imagery in remote sensing, medicine, and numerous other areas has driven a substantial increase in research in image registration over the past 20 years. We refer the reader to [16] for a general review of remote sensing image registration. In this section, we focus on feature-based methods, which have been applied in remote sensing and are related to the work proposed here.
Contour-based registration techniques can be categorized with respect to the similarity measure they use. An approach is to apply binary correlation to edge points [81], even though these measures do not allow significant local distortions in the feature sets. The Hausdorff distance, which evaluates a match based on the greatest remaining outliers, was proven more accurate for registration. In [33], the authors presented an efficient way to compute this distance while, in [82], this approach was tested on Landsat images using the original formulation, which made use of a branch-and-bound algorithm, along with a Monte Carlo variation to accelerate the search. Another variation was a multilevel algorithm, which applied the Hausdorff distance with binary tree search to a pyramid of edge maps in order to compute a rough alignment and refined the registration to subpixel accuracy using tie-points [83].
One drawback of using the Hausdorff distance as a similarity measure is that computing the optimal alignment of two point sets is computationally intensive. In an attempt to alleviate this complexity, some researchers have considered alignment-based algorithms. These algorithms use alignments be-tween small subsets of points to generate potential aligning transformations, the best of which are then subjected to more detailed analysis (for early works see [84–86], while for more recent ones see [87–89].
For remote sensing applications, it is important for the distance measure to be robust, i.e., this measure should be insensitive to a significant num-ber of feature points from either set having no matching points in the other set. Examples of robust distance measures include the partial Hausdorff distance (PHD) [90], the mean directed Hausdorff distance (MDHD) [91], and the symmetric and absolute differences discussed in [92]. Other possible
frameworks are represented by the random sample consensus (RANSAC) al-gorithm [93] or by voting and accumulation schemes (like the aforementioned Hough transform) to find the most likely transformation within a set of po-tential matchings [94]. Further registration methods were proposed in [95] and [96], where a line segment extractor and a distribution of edge pixels along contour (DEPAC) descriptor were used, respectively.
2.3 Proposed Integrated Framework for Crater
Detection and Image Registration
2.3.1 Overview of the Proposed Framework
The proposed framework addresses jointly the problems of semi-automatic registration of pairs of planetary images collected by a passive sensor, and of detection of the craters in the imaged scene. These two goals are strictly interconnected, because contour features (the outlines of the craters) are used as primary features for the registration process.
First, to detect the craters, a novel MPP model for the distribution of craters in the image plane is proposed. Craters are geometrically modeled as ellipses, and an energy function that characterizes their expected prior behavior and their matching with the input data is developed. Then, the crater detection result is used as an input for the registration process. For this purpose, a two-step approach that optimizes the benefits of both crater features and area-based matching is considered. On one hand, area-based registration using mutual information (MI) has proven very accurate but often slow. In general, its computation time is proportional to the image size [16]. On the other hand, matching curvilinear features such as crater outlines can be performed in a computationally efficient manner, although the resulting registration error is often larger than when MI is used [16]. Our two-step approach is aimed at combining the accuracy of area-based MI-related methods and the efficiency of feature-based techniques.
In the first step, a preliminary registration transformation is determined by matching the curvilinear features extracted through crater detection. In-deed, from the perspective of feature-based registration, there is no need to extract all craters in the scene, yet it is necessary to detect some of them (especially the large ones) as precisely as possible. Hence, this step focuses
2.3. MARKED POINT PROCESSES
Figure 2.1: Block diagram of the proposed framework for crater detection and
planetary image registration.
especially on the detection of large craters to minimize the computational burden of the algorithm without compromising registration accuracy.
In the second step, a refined registration solution is computed by max-imizing MI in a neighborhood of the preliminary solution (Figure 2.1). The intuitive rationale is that, by starting from the preliminary feature-based so-lution, the area-based registration can be applied with a smaller search space, thus requiring shorter computation time, provided that the initial registra-tion error is small enough.
In the following sections, the individual components of the proposed framework are detailed. Section 2.3.2 briefly recalls key ideas of MPP model-ing, Section 2.3.3 introduces their usage for crater detection, and Section 2.3.4 explains how the detected craters are used for registration purposes.
2.3.2 Marked Point Processes
An MPP is an abstract random variable whose realizations are configurations of objects, each described by a marked point [58, 77]. Similar to Markovian modeling, the maximum-a-posteriori (MAP) criterion is expressed, under an MPP assumption, as the minimization of a suitable energy function [31]. Such energy is designed to take into account the interactions between the geometric objects and the way they fit the image.
A point process , defined over a compact subset K of R2, is a stochastic process whose realizations are finite sets {Ê1, . . . , Ên} of points in K, where
Êi collects the coordinates of the i-th point (Êi œ K; i = 1, 2, . . . , n). In
enriched with the association of a set of parameters, called marks [31]. Within an image analysis framework, such additional parameters can be used to characterize the geometric properties of an object attached to the point. This implies that each realization of an MPP represents a model for the spatial distribution of an arbitrary finite number of objects in the image plane [31, 32]. For example, to represent the distribution of disks in the image it would be enough to enrich each point with a radius. By adding two additional parameters, one could represent a distribution of ellipses (the three parameters would be the two axes and an orientation angle). Hence, any realization of a marked point process is a finite set of points in D = K ◊M, where K has the same meaning as before and M is the set in which the marks take values (M µ Rq≠2, qØ 3, so D µ Rq).
2.3.3 Proposed MPP Model for Craters in a Planetary
Image
Craters in a planetary image as an MPP of ellipses
This section focuses on the extraction of craters from one individual planetary image. We shall discuss in Section 2.3.4 how to use these concepts for the registration of a pair of images.
First, contours are extracted from the input planetary image using tech-niques such as the Sobel, Prewitt, Canny, etc., edge detectors (Canny). Let S be the pixel lattice (S µ Z2), C be the set of extracted contour pix-els (C µ S), and K be the smallest rectangle enclosing the pixel lattice S (S µ K µ R2). We model the set of craters in the scene as a distribution of ellipses in the image, modeled as an MPP . Each crater is geometrically represented as an ellipse and parameterized by a 5-tuple Ê = (›, ÷, a, b, „), where (›, ÷), a, b, and „ are the center, the major axis, the minor axis, and the orientation angle, respectively (see Figure 2.2). The 5-tuple Ê takes values in
D= K ◊[amin, amax]◊[bmin, bmax]◊[0, fi], where [amin, amax] and [bmin, bmax]
are the ranges of the major and the minor axes, respectively, and [0, fi] is the interval of the possible orientations. Given a second ellipse parametrized by the 5-tuple ÊÕ œ D, we write Ê ≥ ÊÕ to indicate that the two ellipses spatially overlap, and the percentage of their spatial intersection over their total area is larger than a threshold “. Each realization of the proposed MPP is a finite set {Ê1, . . . , Ên} of n such 5-tuples Êi = (›i, ÷i, ai, bi, „i), each
2.3. PROPOSED MPP MODEL
Figure 2.2: Example of a crater modeled as an ellipse with center (›, ÷), major
axis a, minor axis b, and orientation angle „.
representing an ellipse (Êi œ D; i = 1, 2, . . . , n). Hence, (›i, ÷i) is a point in
the realization of the corresponding point process, while ai, bi, and „i denote
the marks.
As mentioned in Section 2.3.2, the MAP criterion is formulated as the minimization of a posterior energy function U( |C) on the space of the pos-sible realizations of , to find the arrangement of ellipses that best fit the edge map C [69]. Stochastic minimization algorithms, with focus on the two specific methods that have been developed for the proposed framework, will be discussed in Sections 2.4 and 2.5. In this section, we focus on the de-sign of the energy function, noting that its minimization is computed with respect to not only the locations (›i, ÷i) and marks (ai, bi, „i) of the ellipses
(i = 1, 2, . . . , n) but also their number n. Hence, the number of detected craters is determined automatically as well.
Energy of the proposed MPP
Consistently with a Bayesian approach, the energy of the proposed MPP is made up of a likelihood term, which describes how each individual ellipse fits the contours, and a prior term, which characterizes the interactions among
pairs of ellipses, i.e.: U( |C) = n ÿ i=1 UL(C|Êi) + ÿ Êi≥Êj UP(Êi, Êj), (2.1)
where UL(C|Êi) and UP(Êi, Êj) are individual and pairwise energy
contribu-tions (i, j = 1, 2, . . . , n). The prior term characterizes the general aspect of the desired solution. A strong repulsion term is introduced whenever two ellipses have non-empty intersection: we set UP(Ê, ÊÕ) = +Œ if Ê ≥ ÊÕ and
UP(Ê, ÊÕ) = 0 otherwise (Ê, ÊÕ œ D). The rationale of this choice is twofold.
First, from a planetary science viewpoint, overlapping and near-overlapping craters are mostly present in saturation-cratered surfaces on planetary ob-jects or in cases where more recent craters are situated within older fea-tures [97,98]. Second, from an image processing viewpoint, the identification of a single crater in a small portion of space is sufficient for registration purposes. Moreover, this choice has been found effective in previous MPP models for EO [99], and favors the applicability of efficient energy minimiza-tion algorithms (e.g., MBC [78–80]).
The individual energy contribution of the proposed energy function is the sum of two terms, the first ([C]) measuring the spatial correlation between each ellipse and the extracted edges, and the second ([D]) taking into account their mutual distance (Ê œ D)1:
UL(C|Ê) = –1 A 1 ≠ ˆÊ˜ˆÊ fl Cfl C B ¸ ˚˙ ˝ [C] +–2dH(ˆÊ, C) a ¸ ˚˙ ˝ [D] , (2.2)
where ˆÊ is the set of border pixels of the ellipse Ê on the image plane, ˜ˆÊ is an annulus around the ellipse Ê (ˆÊ µ S, ˜ˆÊ µ S), dH(·) indicates
the Hausdorff distance, a is the major axis of Ê, and –1 and –2 are positive weight coefficients that determine the relative trade-off between terms [C] and [D].
The annulus ˜ˆÊ is centered around Ê and delimited by two more ellipses, inside and outside Ê, whose distances to Ê are directly proportional to the size of the ellipse itself.
2.3. PROPOSED MPP MODEL
Term [C] measures the similarity between the ellipse Ê and the con-tours C by computing a sort of correlation coefficient between the extracted edges and the ellipse model. It is written in terms of the set of pixels ˆÊ to compare the 5-tuple Ê with the contours on the pixel grid. It is inspired by similar correlation measures that have been used for feature matching in image registration [16]. In [58], it was found more effective for the application to crater detection than previous likelihood energy terms used in MPPs of ellipses for EO applications (e.g., see [68]). As compared to previous corre-lation measures [16], the denominator does not sum up to the whole set of contour pixels, but it is restricted to the subset defined by the annulus ˜ˆÊ. This choice is to favor that smaller and larger craters equally contribute to the total posterior energy of the entire realization. The (1 ≠ ·) formulation is used so that minimizing energy favors maximizing correlation.
Term [D] measures the spatial distance between an ellipse Ê and the contours C. A novel energy contribution is introduced here based on the Hausdorff distance. Informally, two sets are close in the Hausdorff distance if every point of each set is close to some point of the other set. More precisely, the Hausdorff distance is the greatest of all the distances from a point in one set to the closest point of the other set. If Z and W are non-empty finite subsets of a metric space endowed with the distance d(·), then the directed Hausdorff distance from Z to W is2 [90]:
dDH(Z, W ) = max
zœZ wminœWd(z, w), (2.3)
and the (undirected) Hausdorff distance between Z and W is:
dH(Z, W ) = max {dDH(Z, W ); dDH(W, Z)}. (2.4)
Such distance is especially appropriate to evaluate the fitting between two curves in the image plane. For example, let Z and W be the two in-tersecting curves in Figure 2.3, then their classical set distance d(Z, W ) = minzœZ,wœWd(z, w) vanishes, whereas dH(Z, W ) is nonzero and emphasizes
2If Z and W were infinite sets, the infimum and supremum (inf/sup) operators would be
used instead of the min/max operators — a situation that does not occur in the present application to sets of pixels, but that is relevant within the general definition of Hausdorff distance in a generic metric space.
Figure 2.3: Example of the Hausdorff distance between two curves Z and W in
the plane. Here, d(Z, W ) = 0, whereas dH(Z, W ) > 0.
the mismatch between Z and W : a desired property for crater detection. In our case, the Hausdorff distance is evaluated between the sets of pixel in the edge map C and in the border ˆÊ of ellipse Ê, using the Euclidean distance for d(·). The major axis a is used as a normalization coefficient to equalize terms computed on ellipses of very different sizes.
2.3.4 Planetary Image Registration using the Extracted
Craters
Two-step Registration
Let R(x, y) and I(x, y) be two planetary images to be registered, where x and
yindicate the spatial coordinates and R and I take on nonzero values in some
bounded subset of R2(i.e., R and I are compactly supported functions). It is convenient to model the two images as defined on a continuous-variable do-main of R2, although data are obviously recorded only on the corresponding pixel lattices.
Let the two images represent the same planetary surface and let them be aligned differently, as they may have been acquired at different times or from different viewpoints. Moreover, let us use R as the reference image and I as the input image to be transformed [16]. The transformation Tp : R2 æ R2
from the spatial coordinate system of the reference to that of the input image is chosen to be a rotation-scale-translation (RST) transformation [16], i.e.
2.3. IMAGE REGISTRATION USING CRATERS ((x, y) œ R2): Tp(x, y) = C kcos ◊ k sin ◊ tx ≠k sin ◊ k cos ◊ ty DS W U x y 1 T X V, (2.5)
where txand ty determine translations in the x and y directions, respectively
(tx, ty œ R), ◊ is the rotation angle (0 Æ ◊ < 2fi), k is the scaling factor
(k > 0), and p = (tx, ty, ◊, k) is the vector collecting all transformation
parameters; p takes values in the set P = R2◊ [0, 2fi) ◊ (0, +Œ). To register the two images, we look for the value of p œ P such that the transformed input image I(Tp(x, y)) (up to resampling on the corresponding pixel lattice)
best matches the reference image R(x, y) over its support. As described in Section 2.3.1, this task is accomplished in two steps.
In the first step, a preliminary solution ˜p is searched for using the de-tected craters. A metric J (p) (p œ P) that measures the misalignment between the curvilinear features in R and those in I(Tp(·)) is defined (see
next subsections), and ˜p is chosen by minimizing J (·). Specifically, craters detected according to the proposed MPP model can be used for either crater-to-contour matching or crater-to-crater matching. The formulations of J (·) used in these two cases are presented in the following subsections.
The solution ˜p is generally affected by the accuracy of the crater de-tection result. Hence, the registration error between R and the transformed image I(T˜p(·)) also depends on the crater detection accuracy. To ensure that a small registration error is attained, a second RST mapping Tp is
consid-ered, and the MI between the newly transformed image I(Tp(·)) and the
reference image R is maximized with respect to p in a neighborhood of ˜p. This yields the final solution pú. The initialization of this second step through the intermediate solution ˜p makes it possible to restrict the search space to a neighborhood of ˜p, thus mitigating the computational workload of the area-based computation of MI. More details on the computation and the use of MI for registration purposes can be found in [16].
In both steps, the unconstrained minimization of the related metrics (J and MI) can be addressed using common numerical techniques such as genetic algorithms [35], simulated annealing [100], or generalized pattern search [36].
Crater-to-Contour Matching
In this case, craters are detected in the sole reference image. The resulting craters are then matched to the edges of the input image. Let CR and CI
be the contour maps obtained by separately operating on the reference and input images, and let R = {ÊR
1, Ê2R, . . . , ÊRn} be the realization of the MPP
of ellipses that is obtained by minimizing the energy U(·|CR) with respect to
the contours of the reference image.
In the proposed framework, the likelihood energy defined above for the MPP represents a natural choice for a metric that measures the fitness be-tween an MPP realization and a contour map. In particular, let a transforma-tion Tp, p= (tx, ty, ◊, k), map the coordinate system of the reference to that
of the input image. Each ellipse ÊR
i = (›iR, ÷iR, aRi, bRi , „Ri ) in the reference
domain is mapped to the transformed ellipse 1Tp(›iR, ÷iR), kaRi , kbRi , „Ri + ◊
2 , which we shall more simply denote as Tp(ÊiR) (although with a little abuse
of notation; i = 1, 2, . . . , n). To match the transformed realization {Tp(ÊR1),
Tp(Ê2R), . . . , Tp(ÊnR)} to the contours CI of the input image, the following
metric is used (p œ P): J (p) = n ÿ i=1 UL Ë CI |Tp(ÊiR) È . (2.6) Crater-to-Crater Matching
In this case, a realization I = {ÊI
1, Ê2I, . . . , ÊmI} of the proposed MPP is also
determined for the input image by minimizing the energy U(·|CI), given the
contours CI. Consequently, the detected configurations of ellipses I and R are matched. However, the aforementioned likelihood energy evaluates
the fit between an MPP realization and a contour map, and not between two MPP realizations. In principle, a way to measure the fit between such realizations could be to compute directly some distance between the 5-tuples describing their ellipses. However, the expected number of craters in each image is not large, which could make this distance sensitive to small errors in the identification of craters’ locations and shapes. Therefore, a new metric is defined. The MDHD from the craters detected in the reference image to those detected in the input image is used as a classical feature-matching criterion [91]. With the same notations as in Section 2.3.3, given two finite
2.4. FIRST METHOD: MBD
subsets Z and W of a metric space, the MDHD from Z to W is:
dM DH(Z, W ) = 1 |Z| ÿ zœZ min wœWd(z, w). (2.7)
Hence, for the case of crater-to-crater registration, the following metric is used (p œ P): J (p) = dM DH S U n € i=1 ˆTp(ÊiR), m € j=1 ˆÊjI T V. (2.8)
which evaluates the MDHD from the borders of all transformed ellipses of the reference image (i.e., all transformed sets ˆTp(ÊiR), i = 1, 2, . . . , n) to the
borders of all ellipses of the input image (i.e., all sets ˆÊI
j, j = 1, 2, . . . , m).
2.4 First Method: Multiple Birth and Death
2.4.1 Overview of the First Proposed Method
As mentioned in Section 2.1, two specific methods are developed within the proposed framework. Their main differences lie in the minimization approach applied to the posterior energy and in the way such approach is integrated in the joint crater detection and registration process to favor computational efficiency. The key idea of the first method is to combine the MBD algorithm for MPP energy minimization [77] with ROI concepts. Depending on the reg-istration approach (i.e., crater-to-contour or crater-to-crater), the method is applied to detect craters from either the reference image or both the reference and input images (see Section 2.3.4).
MBD is a simulated annealing-type algorithm based on birth-and-death processes [101, 102]. It generates a Markov chain in the space of the possi-ble realizations of the MPP and, in the ideal case, ergodically converges to the minimum-energy distribution [103]. MBD may often exhibit long com-putation times, a common characteristic of algorithms based on simulated annealing concepts. In this proposed approach, it is integrated with region-based reasoning to speed up convergence and favor applicability to large planetary images.
Specifically, MBD is fed with an input birth map, i.e., a real-valued image defined on the same pixel lattice S, in which each pixel s œ S is assigned a score B(s) that approximately indicates the probability that a crater is centered on s. In the first proposed method, the birth map is defined according to the contour map C (from either the reference or the input image) and is used to define automatically a collection of ROIs where the search for craters is focused. This approach allows MBD to run on each individual ROI rather than on the whole image, thus reducing the computation time substantially. The set of ellipses resulting from the applications of MBD to all ROIs are finally aggregated into the output set of detected craters.
The generation of the birth map and of the ROI is discussed in Sec-tion 2.4.2, and the resulting formulaSec-tion of MBD is described in SecSec-tion 2.4.3. The first proposed method will be named “region-of-interest based MBD” (R-MBD) in the following.
2.4.2 Generation of the Birth Map and of the Regions
of Interest
First, given C, the GHT algorithm in [58] is used to identify candidate pixels where craters may be centered. A generalized Hough accumulator is defined, that aims at detecting pixels located midway between edge points in C with opposite gradient directions; details can be found in [58]. An example is shown in Figure 2.4 with regard to the contours extracted by the Canny edge detector from the Mars THEMIS image in Figure 2.4(a). The contours in this example refer to the largest craters in the scene.
As a second step, the connected components of the set of contour pixels C are identified using the 8-connectedness notion [104], and are used to refine the set of candidate crater centers in the accumulator. For each connected component, the first-order image moments (centroid) and the second-order image moments are computed [104]. The eigenvalues corresponding to the second-order moments are derived, and a circle with center on the centroid and radius equal to the maximum eigenvalue is drawn. The set of all such cir-cles derived from all connected components is used as a mask. If a candidate crater center from GHT lies outside all such circles, it is assumed to be due to GHT noise and is discarded. Finally, the remaining centers are clustered to reduce the number of candidates and determine the locations of probable
2.4. BIRTH MAP AND REGIONS OF INTEREST F igu re 2. 4: B irt h m ap an d R O I fr om a T HE M IS im age : (a) C an ny con tou rs su pe rim pos ed to th e in pu t im age ; (b ) re su lt of th e ge ne ral iz ed Hou gh ac cu m ul at or ;( c) ce nt roi ds ob tai ne d by cl us te rin g th e ac cu m ul at or ce nt er s; (d ) bi rt h m ap sh ow n by sh ad in g th e im age in pr op or tion to B (s ) (s œ S ); (e ) re gi on s of in te re st (r ed bo xe s) . A se con d ex am pl e fr om an HR SC im age is sh ow n in (f ).
crater centers in the image (Figure 2.4(c)). For this purpose, the K-means algorithm is applied to the set of candidate crater centers; the number K of desired clusters is chosen to be the number of the aforementioned connected components.
To ensure that the birth map is spatially smooth, a spatial circular Gaussian kernel is centered on each centroid and B(s) (s œ S) is defined to be proportional to the sum of these Gaussian contributions (Figure 2.4(d)). The standard deviation ‡ of the Gaussian kernel is set in proportion to the image size.
Desired properties for the ROIs are that: (i) each ROI contains con-tours and vice versa all (or almost all) contour pixels are contained in some ROI; (ii) craters are not split among distinct ROIs; and (iii) the ROIs have little or zero spatial overlap. These requirements are met by defining the ROIs according to the birth map. Operatively, B(s) is thresholded with a threshold · and the resulting set of pixels {s œ S : B(s) > ·} is split into its connected image component. Then, for each such component A(A µ S), the corresponding spatial centroid OA (first-order image moments) and the second-order image moments with the related eigenvalues are computed. The largest such eigenvalue ⁄A geometrically represents the major semi-axis of a spatial ellipse centered on OA that approximates A. A ROI is defined as the square centered on OA with side equal to (2⁄A+ amax), where the up-per bound amax on the ellipse axis (see Section 2.3.3) is used as a margin (Figure 2.4(e)).
It is worth noting that the accuracy of the identification of candidate crater centers and of the resulting birth map is not critical. The birth map has no impact on the convergence of MBD to a global energy minimum but only affects the speed of convergence by favoring birth in relevant locations [74], provided that ‡ is large enough so that B(s) is non-negligible on every pixel
s œ S. Further comments on these parameter tuning issues will be made in Section 2.6.6. Similarly, the accuracy in the identification of the ROIs around relevant craters does not influence the precision with which craters are detected, provided that the contour pixels are all included in the ROIs.
2.4. MBD FORMULATION
2.4.3 Multiple Birth-and-Death Formulation
The MBD formulation adopted in the first proposed method is summarized in Table 2.1 (see below). It is parameterized by an inverse temperature — and a discretization step ”, which are initialized to rather large values and evolve through the iterations according to geometric annealing schedules of reason Ÿ. Then, at each iteration, a birth and a death step are performed.
In the birth step, new ellipses are added to the current configuration according to the birth map and the current value of ”. Consistently with the simulated annealing strategy, ” decreases from large values on the first iterations, which makes it possible to give birth to many new ellipses, to smaller values on later iterations. In the adopted formulation of MBD, the number of ellipses that can be born on each iteration is limited by an upper bound nú, which is predefined according to the size of the image and the order of magnitude of the expected number of craters per unit surface area. This number may be evaluated based on planetary science studies by defin-ing a flux model for the population of impactdefin-ing bodies and a crater-count (or degradation-rate) model [98, 105]. This formulation allows limiting the computation time as it prevents the birth step to generate ellipses almost everywhere in the image because of a large discretization step ”.
The goal of the death step is to reduce (“kill”) the number of ellipses in the configuration returned by the birth step according to their energy contributions. The pairwise energy UP forbids overlapping ellipses and gives
no penalty otherwise. Therefore, on one hand, if two ellipses in the current configuration overlap, then one of them will deterministically be removed. In the adopted formulation, the ellipse with the larger likelihood energy UL is
deleted. On the other hand, if an ellipse Ê does not overlap with any other ellipse in the current configuration, then it is killed with a probability that depends on UL(C|Ê), —, and ” (see Table 2.1).
As the iteration progresses, — increases and ” decreases, which lets more ellipses die in the first iterations, while the configuration is intuitively frozen later on.
The algorithm is stopped if, at the same iteration, all newly born ellipses are also killed, and if the total number of such ellipses is below a threshold (here, equal to 5% of nú). More details on MBD can be found in [77].
Formulation of MBD for crater detection: is the current realization of the proposed MPP; C is the contour map; UL is the likelihood energy; [amin, amax],
[bmin, bmax], and [0, fi] are the ranges on the marks of the ellipses of the proposed MPP; B(s), s œ S is the birth map; — and ” are the parameters of MBD; Ÿ is the reason of their geometric annealing schedule; —0and ”0are their initial values; and nú is the maximum number of ellipses that can be born on each iteration.
Input: C, UL, B(s), s œ S, —0, ”0, Ÿ, nú
Initialize: — = —0, ” = ”0, = ÿ For each iteration:
• Birth Step:
– Sample a realization ú made of up to nú ellipses, whose centers are spatially distributed on the pixel lattice with probability Pbirth(s) = ” · B(s) (s œ S) and whose major axis, minor axis, and orienta-tion are sampled independently and with uniform distribuorienta-tions from [amin, amax], [bmin, bmax], and [0, fi], respectively.
– Update Ω fi ú • Death Step:
– Sort the ellipses in in order of decreasing likelihood energy UL(C|Ê)
(Ê œ ).
– Scan sequentially in the resulting order. For each ellipse Ê œ , if Ê overlaps with some other ellipse in , then remove Ê from . Otherwise if Ê does not overlap with any other ellipse in , then remove Ê from
with probability equal to:
Pdeath(Ê) = 1 + ” exp [—U”exp [—UL(C|Ê)] L(C|Ê)]
• Convergence Test:
– If all the ellipses that have been generated in the birth step are also
removed in the death step and if the total number of such ellipses is below a threshold (here, equal to 5% of nú), then the algorithm stops. Otherwise, update — Ω —/Ÿ and ” Ω Ÿ”and go to the birth step. Output: realization
2.5. SECOND METHOD: MBC
2.5 Second Method: Multiple Birth and Cut
2.5.1 Overview of the Second Proposed Method
The second proposed method integrates DWT and the MBC approach to MPP energy minimization [78–80]. MBC iteratively combines a birth process with the application of a graph cut algorithm to a case-specific graph. While it imposes some restrictions on the admissible values of the energy, it rep-resents an effective alternative to simulated annealing-type approaches [78]. In this proposed approach, it is combined with DWT to take advantage of multiscale information for both crater detection and registration purposes.
Utilizing DWT on a planetary image, a multiscale pyramidal decompo-sition, made of images of progressively smaller size and coarser resolution, is obtained [40]. Incorporating this multiscale decomposition into the proposed framework allows crater-detection and feature-based registration results to be preliminarily determined on the coarsest scale and then progressively refined along the finer scales. Specifically, DWT is applied keeping the outputs of the corresponding low-pass filters and discarding the high-pass components [40]. MBC is first applied to detect craters at the coarsest scale of the pyramid. We expect that such MBC run is fast because of the small image size, but that only large craters are detected because of the degraded spatial resolu-tion. While recursively moving to finer resolutions, MBC is applied again by suitably restricting its search space to identify further (and possibly smaller) craters in regions where craters were not detected at coarser resolutions.
Details on the multiscale formulation of the second proposed method are described in Section 2.5.2, while the key ideas of MBC are recalled in Section 2.5.3. The second proposed method will be named “wavelet-based MBC” (W-MBC) in the following.
2.5.2 Multiscale Crater Detection and Image
Registra-tion
Denoting as L the number of decomposition levels, DWT generates a pair {Rl}L
l=0 and {Il} L
l=0 of L-level multiscale pyramids by recursively applying
the corresponding low-pass filters to the reference and input images. Here,
R0 = R and I0 = I (finest scale), while RLand IL correspond to the coarsest
Figure 2.5: Wavelet decomposition: from finest to coarsest resolution.
First, crater detection through MBC and feature-based registration are performed at the L-th scale. Let ˜pL= (tL
x, tLy, ◊L, kL) be the resulting
trans-formation vector. Then, to proceed down the pyramid, each crater found at the L-th scale is projected to the (L ≠ 1)-th scale by multiplying each axis by two and resampling its center. Analogously, ˜pL is also projected one scale
down as ˜pL
¿ = (2tLx,2tLy, ◊L, kL) to acknowledge that the resolution of the
(L ≠ 1)-th scale is twice as fine as that of the L-th scale [40]. Hence, MBC and feature-based registration are applied at the (L ≠ 1)-th scale resulting in a new transformation vector ˜p(L≠ 1). In this case, the transformation vector is searched for in a neighborhood of the solution ˜pL
¿ coming from the coarser scale. The procedure is iterated along the pyramid until the 0-th level (i.e., the original scale) is reached and a corresponding transformation vector ˜p0is computed: this solution is the output of the feature-based registration step (i.e., ˜p = ˜p0). At the end of this multiscale crater-detection and feature-based registration, the area-feature-based registration step is applied as discussed in Section 2.3.4.
2.5.3 Multiple Birth-and-Cut Formulation
The adopted MBC formulation is summarized in Algorithm 2.2. MBC is ini-tialized with a random configuration of up to núellipses drawn independently with uniform distribution and constrained to be non-overlapping. Then,
sim-2.6. EXPERIMENTAL RESULTS
ilar to MBD, each iteration includes a birth step in which up to núnew ellipses are sampled but, unlike MBD, these new ellipses are not allowed to overlap and are drawn with uniform distribution. Rather than using a probabilistic death step, each iteration of MBC makes use of graph cuts to discriminate the ellipses to remove and those to preserve.
Graph cut algorithms are based on the min-flow / max-cut theorem and have been found very efficient for the minimization of the energies of Markov random fields and conditional random fields [38, 39]. In each iteration of MBC, a case-specific weighted undirected graph is constructed on the set of all current ellipses, either coming from the previous iteration or resulting from the birth step. Then, the “kill or let live” decision about these ellipses is cast as a binary labeling problem, which, in turn, is formulated as the minimization of a case-specific energy function E(·) and addressed using graph cuts [78–80]. It is possible to demonstrate that this technique converges to the global minimum of the energy function [80]. Operatively, the algorithm is stopped when the configuration of ellipses remains stable for a large number of iterations. Because of this choice, there generally is a trade-off between accuracy and computation time.
Details on MBC and on the consistency of its application to graph cuts, which makes it sure that the global minimum of E(·) is reached, can be found in [78]. In our approach, we only recall that a condition for the applicability of MBC is that the likelihood energy ULtakes values in the [0, 1] interval [78].
In the case of the proposed MPP model, it is straightforward to satisfy this condition by suitably setting the weights –1and –2(see Section 2.3.3). MBC requires the tuning of a single parameter, nú, which has been demonstrated in [78] to influence the convergence speed but not the accuracy.
2.6 Experimental Results
2.6.1 Datasets for Experiments
For the validation of the proposed framework, we used images taken from the NASA Planetary Data System (PDS) [106]. PDS is a database whose purpose is to “ensure the long-term usability of NASA data and to stimulate advanced research” [106]. In particular, the images used in this experimental validation were acquired by two Mars missions and a lunar mission: Mars Odyssey, Mars
Formulation of MBC for crater detection: is the current realization of the pro-posed MPP; D is the domain where each marked point takes values; C is the contour map; UL is the likelihood energy; and nú is the maximum number of
ellipses that can be born on each iteration. Input: C, UL, nú
Initialize: sample a realization composed of up to nú non-overlapping ellipses drawn independently and with uniform distribution from D.
For each iteration: • Birth Step:
– Sample a realization ú composed of up to núnon-overlapping ellipses drawn independently and with uniform distribution from D.
• Cut Step:
– Construct a graph whose nodes are the ellipses in fi ú and whose edges connect overlapping ellipses (i.e., Ê ≥ ÊÕ for Ê œ and ÊÕ œ ú or vice versa). Assign a binary label fÊ œ {0, 1} to every ellipse Ê œ
{ fi ú}.
– Use graph cuts to determine the binary labeling F = {fÊ}, (Ê œ { fi
ú}) that minimizes E(F), where cÊ = UL(C|Ê), V (0, 1) = +Œ, and V(0, 0) = V (1, 1) = V (1, 0) = 0. E(F) =ÿ Êœ cÊ(1 ≠ fÊ) + (1 ≠ cÊ)fÊ+ ÿ Êœ ú [cÊfÊ+ (1 ≠ cÊ)(1 ≠ fÊ)] + ÿ Ê≥ÊÕ V(fÊ, fÊÕ)
– If Ê œ and fÊ = 0, then remove Ê from . If Ê œ ú and fÊ = 1,
then remove Ê from ú.
– Update: Ω fi ú. • Convergence Test:
– If the realization of ellipses remains stable for a predefined large number
of iterations, then the algorithm stops. Output: realization
2.6. DATASETS FOR EXPERIMENTS
Express, and Lunar Reconnaissance Orbiter (LRO). Data from the Thermal Emission Imaging System (THEMIS), the High-Resolution Stereo Camera (HRSC), and the Lunar Reconnaissance Orbiter Camera (LROC) onboard Mars Odyssey, Mars Express, and LRO, respectively, were used.
First, to evaluate the performance of the developed crater detection methods, we used a dataset composed of 13 THEMIS and HRSC single-channel images. THEMIS is an imaging camera acquiring data in the visible wavelengths at the spatial resolution of 18m and in the infrared wavelengths at the spatial resolution of 100m, while HRSC acquires images with a resolu-tion between 10m and 30m. The sizes of the considered images ranged from (1581 ◊ 1827) to (2950 ◊ 5743).
Regarding the proposed approach to registration, the validation was conducted using both semi-synthetic and real data. The generation of the semi-synthetic data is illustrated in Figure 2.6. Given a real THEMIS or HRSC image, a rectangular region was cropped to be used as the reference image R. Then, the original THEMIS or HRSC image was geometrically warped according to a predefined transformation vector, zero-mean Gaussian noise was added, and the same rectangular region was cropped to become the input image I. Cropping was necessary to avoid artifacts and border effects in the resulting image pair. Then, once the proposed methods were applied to the pair {R, I} of images, the resulting transformation was applied to the entire image area without any more cropping. To obtain a comprehensive set of images and test the proposed registration approach, this procedure was applied with five different transformations to two images from each of the two sensors to obtain a set of 20 semi-synthetic image pairs. The advantage of performing this experiment with semi-simulated data is that, for each pair, the true RST transformation is known, which allows the registration error to be quantitatively computed.
Then, the proposed registration approach was also validated using a pair of real single-channel LROC images collected with the Narrow Angle Camera (NAC) at 1.5m resolution at different times over the same lunar surface region. Substantial differences in the overall illumination of the two images can also be noted (see Figure 2.7). On one hand, this second experiment allows the registration quality to be appreciated with real data as well; on the other hand, no reference “true” transformation is available in this case. Hence, quantitative error assessment is not possible.
Figure 2.6: Illustration of the semi-synthetic data generation.
Figure 2.7: Multitemporal pair of LROC images to be registered:
2.6. SET-UP FOR EXPERIMENTS
2.6.2 Parameter Setting and Experimental Set-up
The proposed framework addresses crater detection and registration from planetary images in a semi-automatic manner, i.e., full automation of the setting of all parameters of the proposed models and algorithms is not among the goals of the present work. This is also consistent with most applications of MPP modeling to object detection problems from EO imagery [72,74,77, 79, 80]. Accordingly, the parameters of the MPP-based methods were set based on the previous literature and experimentally by trial-and-error. The same comment holds regarding the parameters of the Canny edge detector [107] that was used to generate the contour maps. In the following, we describe how parameters were set within the experimental validation of the proposed techniques. A sensitivity analysis with respect to such choices will be reported in Section 2.6.6.
The proposed MPP model includes the two positive parameters –1 and
–2. They represent the relative weights between the correlation and the distance terms contributing to the likelihood energy. Given a contour map,
–1/–2 was determined so that the two contributions had the same average weight. In the case of R-MBD, setting this ratio is sufficient. In the case of W-MBC, given the value of the ratio –1/–2, the values of –1 and –2 were chosen so that UL took values in the [0, 1] range. Moreover, the radius r of
the annulus is directly proportional to the axes of the associated ellipse. The ranges [amin, amax] and [bmin, bmax] of the axes of the ellipses were set according to the expected size of the target craters as compared to the spatial resolutions of the THEMIS, HRSC, and LROC images. In particular, large craters are of higher importance for registration than small craters, so the focus was put especially on the detection of medium-to-large craters. This restriction was easily incorporated into the proposed framework by tuning
amin, amax, bmin, and bmax.
Regarding R-MBD, the parameters of the method are the initial values
—0 and ”0 of the inverse temperature — and of the discretization step ”,
and the reason Ÿ of their geometric annealing schedule. They were set at
—0 = 50, ”0 = 200, 000, and Ÿ = 0.97. These values were chosen according
to the MPP literature. More precisely, in [102], the implication of these choices with respect to the convergence properties of MBD were discussed, and this parameter setting for MBD was validated in most of the works
cited in Section 2.2.2. Given each input image, the standard deviation ‡ of the Gaussian filter was set to 70% of the maximum major axis of the target ellipses (i.e., ‡ = 0.7amax). The threshold · on the birth map was determined so that each resulting ROI is not larger than 40% of the image size.
Regarding W-MBC, L = 4 decomposition levels were used in the applica-tion of DWT as a trade-off between effectively exploiting multiscale informa-tion and not degrading spatial resoluinforma-tion in the output result. Daubechies wavelets of order 4 were used [40, 41]. The threshold “ on the percentage overlap among craters was set to 10%.
In the case of both methods, the number nú of ellipse to draw on each iteration was set to a maximum of 600.
2.6.3 Crater Detection Results
Ground truth data were generated by manually analyzing each of the 13 THEMIS and HRSC images and by identifying the corresponding craters. A quantitative assessment of the results obtained by the proposed methods was accomplished by computing the detection percentage D, the branching factor B, and the quality percentage Q:
D = TP TP + FN, B = FP TP, Q = TP TP + FP + FN, (2.9)
where TP (true positive) is the number of detected ellipses that correspond to ground truth craters; FP (false positive) is the number of detected ellipses that do not correspond to any ground truth crater; and FN (false negative) is the number of missed ground truth craters.
Table 2.3 quantitatively summarizes the results obtained by R-MBD and W-MBC on the dataset described in Section 2.6.1. The two methods exhib-ited similar performances in the applications to both THEMIS and HRSC images. They obtained high values of detection and quality percentages and were able to keep the branching factor to low values. In particular, W-MBC obtained no false positives at all, while R-MBD yielded a small but nonzero value of branching factor. R-MBD achieved higher values of detection and quality percentage, while W-MBC required a shorter time for convergence. Specifically, to converge on the considered set of images, R-MBD and
W-2.6. CRATER DETECTION RESULTS
Data Average timeper image
Detection Percentage (D) Branching Factor (B) Quality Percentage (Q) R-MBD MBCW- MBDR- MBCW- MBDR- MBCW- MBDR- MBC W-THEMIS 40 23 0.91 0.82 0.10 0 0.83 0.82 HRSC 45 35 0.89 0.74 0.06 0 0.85 0.74 Average 42 29 0.90 0.78 0.09 0 0.84 0.78
Table 2.3: Quantitative performance and computation time (in minutes) of the
proposed R-MBD and W-MBC methods when applied for crater detection to 13 THEMIS and HRSC images of the Mars surface.
MBC needed an average of 42 and 29 minutes per image, respectively (see Table 2.3). The experiments of both methods were run within a Matlab en-vironment on a quad-core i7 processor with 2.3GHz and 16GB of RAM. The two implementations were not parallelized on a graphical processing unit (GPU) or on any other high-performance computing (HPC) architecture. For additional details on the computation times of the two methods, we also refer to Section 2.6.6. The results of the proposed methods were compared to those obtained in [58], where GHT was combined with watershed seg-mentation, and with those achieved by the CNN-based technique presented in [65].
More in details, the method in [58] is based on the combination of several image processing techniques, including watershed segmentation and the gen-eralized Hough transform. First, the input image is filtered using a smoothing filter to reduce the noise. Then, a binary edge map is extracted using the Canny edge detection method, a non-maximum suppression algorithm, and an hysteresis thresholding. The watershed segmentation is then used to ex-tract closed contours from the binary edge map. The result is a binary image that shows boundaries of small features of regular shapes, such as craters. Subsequently, a generalized Hough accumulator is applied to such image to detect possible craters’ centers. Finally, using the detected centers as seed points, a watershed algorithm is applied to the gradient map output by the Canny edge detector to extract the final craters. Conversely, the method in [65] is based on a convolutional network. As for the previous case, the
Data PercentageDetection (D) Branching Factor (B) Quality Percentage (Q) Visible Images 0.73 0.24 0.62 TIR Images 0.78 0.14 0.70
Average on all Images 0.75 0.20 0.65
Table 2.4: Quantitative performance of the GHT-watershed method for crater
detection in [58], when applied to 21 THEMIS and HiRISE images [76]. input image is first pre-processed to remove the noise. Then, the resulting smoothed image is divided into small tiles of 15x15 pixels, and each tile is processed by a CNN composed of 2 convolutional layers without pooling and two fully connected layers. Both the convolutional layers are made of 20 4x4 filters that are applied to the entire input image with stride equal to 1. Moreover, the fully connected layers consists of 500 and 2 units, respectively. Concerning [58], the comparison is especially interesting in the case of R-MBD, because the technique in [58] is involved in the computation of the corresponding birth map (see Section 2.4.2). The performance measures were the same as here, and experiments were performed on two THEMIS datasets, one collected by the THEMIS TIR camera and the other by the THEMIS visible camera, and on a dataset acquired by the HiRISE (High Resolution Imaging Science Experiment) camera onboard the Mars Reconnaissance Or-biter [76]. A summary of the performances is shown in Table 2.4.
The proposed R-MBD and W-MBC algorithms obtained improved crater detection performance as compared to the method in [58]. The values of D and B point out that the developed methods were able to reduce the negative effect of the false positives while keeping high percentages with regard to the true positives. Indeed, the accuracy values of the proposed methods and of the technique in [58] are not strictly comparable because they were computed on different datasets, yet the large differences in all three performance figures suggest a substantial improvement in accuracy of R-MBD and W-MBC as compared to the previous GHT-watershed method.
The proposed method also outperformed the CNN-based technique in [65] in the application to the aforementioned THEMIS and HRSC imagery. In particular, the CNN was trained using the HRSC dataset made
avail-2.6. CRATER DETECTION RESULTS
Data PercentageDetection (D) Branching Factor (B) Quality Percentage (Q) THEMIS 0.78 0.86 0.47 HRSC 0.50 0 0.50 Average 0.62 0.46 0.48
Table 2.5: Quantitative performance of the CNN-based method in [65], when
applied to 13 THEMIS and HRSC images of the Mars surface.
able in [108] (please refer to [109] for the trained CNN model) and was applied for prediction to the THEMIS and HRSC images considered here. The prediction time, averaged over these images, was 2 minutes per image. Training time, which is usually long in the case of deep learning methods, was not taken into account here because the considered CNN had already been trained with the planetary image training set in [108], as mentioned above. Although this training set did not involve the same specific images used here for prediction, the previous CNN-based approach provided quite accurate results. This confirms the widely recognized learning and domain adaptation capabilities of deep neural networks in the present application as well. However, the proposed method provided more accurate detection performances (see Table 2.3 and Table 2.5), although it is unsupervised and, accordingly, does not need any training set. This result is interpreted as due to the effectiveness of the proposed MPP model for the spatial distribution of craters in the imaged scene and of the R-MBD and W-MBC algorithms for inference based on this model. Visual examples of the results obtained by applying the two proposed methods for the detection of craters on the Mars surface are shown in Figure 2.8.
It is worth mentioning that, thanks to the MPP-based algorithms, not only the edges of the craters were well detected, but also their geometrical properties were determined. An example in shown in Figure 2.9 with regard to R-MBD and similar results are provided by W-MBC as well. This leaves the door open for multiple applications of these crater detection algorithms, which include not only image registration but also crater dating based on their morphological appearance, and crater counting, which is used for esti-mating the age of planetary surfaces based on the assumption that impact craters accumulate at a constant rate [25,27,29,98].
Figure 2.8: Experimental results obtained by applying the proposed methods
to a THEMIS image. On the left, the results obtained by R-MBD; on the right the results obtained by W-MBC. The detected craters are shown in red.
Figure 2.9: Experimental results obtained by applying R-MBD to an HRSC
image. On the left, the extracted craters are shown in red, while the table on the right shows the geometric properties extracted from the image. Coordinates and
2.6. SEMI-SYNTHETIC REGISTRATION RESULTS
Data RMSE ofR-MBD RMSE ofW-MBC
Average on the 10 pairs of THEMIS images 0.31 0.54 Average on the 10 pairs of HRSC images 0.22 0.59
Average on all 20 pairs of images 0.26 0.57
Table 2.6: Quantitative performance assessment of R-MBD and W-MBC when
applied to the registration of the semi-synthetic dataset, as measured in terms of RMSE [pixels] averaged over the THEMIS, the HRSC, and all image pairs. The corresponding standard deviations were smaller than 0.06 [pixels] in all the cases.
With regard to the aforementioned state-of-the-art techniques used for comparison purposes, the GHT-watershed method does not provide geomet-rical properties of the craters as an output piece of information. The CNN-based method in [108] does extract such information, yet only limited to the position and radius of each crater, modeled as a circle. Hence, it does not determine the orientation and eccentricity of each detected crater.
2.6.4 Semi-Synthetic Registration Results
For each semi-synthetic image pair, given the corresponding true (“ground truth”) transformation vector pGT, the registration error of the proposed
methods can be evaluated quantitatively. As a standard way of assessing registration accuracy, the root mean square registration error (RMSE) in pixels between the true and the estimated transformations is used. Details on its computation can be found in [110].
The RSMEs obtained by R-MBD and W-MBC are reported in Table 2.6 after averaging over the 10 pairs of images coming from THEMIS data, the 10 pairs from HRSC data, and all 20 images. It is worth noting that the time needed for convergence is mainly due to the crater detection step. Matching the extracted craters in the first registration step and refining the result in the second step is not as computationally demanding as detecting the craters. Indeed, these matching and refinement steps required 5 and 10 minutes per image pair (averaged over all pairs considered for experiments), respectively. In the step of feature-based registration, R-MBD and W-MBC were applied with crater-to-crater and crater-to-contour matching, respectively.
