Image analysis algorithm for detection and measurement of Martian sand grains

Several different methods in image analysis were proposed to acquire information on particles from images. An approach in principle based on sieve analysis is the granulometry method (Matheron 1967). The method uses a series of morphological opening or closing operations, and it provides only some information on the size of grains passing through the given structuring element. This technique does not allow studying the shape of grains. To obtain information on morphological parameters of individual particles, an image segmentation technique, enabling the detection of grain boundaries, must be applied (Fu and Mui 1981). This approach often allows the separation of overlapping or touching grains.

A granulometry technique with opening operations was employed to the MI images (Lira et al. 2010), yet it resulted solely in a rough estimation of granulometric curves.

The estimation of shape and size of Martian grains has been done manually in a number of publications (Weitz et al. 2006; Jerolmack et al. 2006; Yingst et al. 2008; Sullivan et al. 2008; Minitti et al. 2013; Yingst et al. 2013). Manual methods, however, are very time-consuming, tedious, and are not practical as the number of images steadily increases.

The work of Karunatillake et al. (2014) presents a semi-automatic method for segmenting the Martian images, especially those obtained by the MI instrument, using image processing techniques. This method is based on two procedures: binarization and watershed segmentation. The authors study the foreground (defined in their work as grains position closer to the imager) and background of an image separately. They use binarization technique to establish particles in the foreground, yet this technique does not allow separation of touching grains. If such particles are present in the foreground, binarization will not give a precise result. Due to the large number of operations, and the number of necessary parameters that must be established during the segmentation process the method is also quite complicated.

Therefore, a simple tool dedicated to analyzing Martian images is presented in this work. It is based on the PADM (Particle Detection and Measurement) algorithm, which enables fast detection and measurement of individual grains, and also provides statistical results. The PADM algorithm uses a set of image processing operations associated with filtering, segmentation and extraction. The algorithm was originally implemented into Wolfram Mathematica, but it can be implemented into any other environment, such as IDL or Matlab.

Although it is possible to establish automatic parameters for each group of Martian images, the accuracy of the results can be improved significantly with some human assessment. Therefore, the approach presented here is semi-automatic.

The algorithm employs segmentation techniques for object detection. Hence, in the initial step, it is necessary to determine the foreground and the background of studied images.

Images of deposits can be divided into four main groups according to the foreground-background relationship: a) grains can be brighter than their surroundings and smaller than the background irregularities (Fig. 1a), b) grains can be brighter than their surroundings and larger than the background irregularities (Fig. 1b), c) grains can be darker than their surroundings and smaller than the background irregularities (Fig. 1c), d) grains can be darker than their surroundings and larger than the background irregularities (Fig. 1d).

Almost all particles observed in the Martian images are bright. However, before using the algorithm, we have to decide whether objects we would like to detect are characterized by higher (Fig. 1a,b) or lower (Fig. 1c,d) values relative to their surroundings.

If the grains are smaller than the background irregularities (Fig. 1a,c), the background can be easily removed, but if grains are larger or similar to surface irregularities (Fig. 1b,d), then the background often cannot be subtracted without some reduction of the foreground. On Earth, even during a field experiment, we can easily take images of material placed on some plain background (Fig. 1c), for example on a piece of paper. However, many Martian sand grains are located on a deep layer of fine material, which creates non-uniform, noisy background (Fig. 1b). Furthermore, some Martian images do not display a clearly visible background, but instead contain many touching particles (Fig. 2). Since the irregularities associated with such a “background” are similar to the size of particles, this kind of images should be processed like those with a noisy background.

To distinguish between a plain and a noisy background, an initial automatic procedure, called background procedure (BG) is applied to the algorithm. It is based on calculating the volume of the studied image, f, after its filtering and binarization. The filtering is done by the top-hat transform THT _R (f) (for brighter grains) or the bottom-hat transform BHT _R (f) (for darker grains) with a structuring element in a form of a disk of a range R. Then the output image, f₁, is binarized with the threshold operator T_[α, β] with the lower and upper thresholds: α and β. The threshold operator converts the input image f₁ into a binary image whose pixels values are either 0 or 1. Next, the volume of the image f₂ is computed: \( {V}_{BF(R)}=\sum \limits_{p\in D}{f}_2(p) \), where p – the image pixel, D – the image domain. Finally, the calculated volume is normalized to the volume V of the input image f: V_N(R) = V_BF(R)/V, where: \( V=\sum \limits_{p\in D}f(p) \), V_N(R) is the normalized volume. The procedure starts from R = 1, and ends when it finds the first minimum of V_N(R), i.e. when R = M + 1, for which V_N(M) < V_N(M + 1) (where: M = 1,2, …, is much smaller than the size of grains). The BG procedure returns a logical value, which is true if the value of the first minimum of V_N(R) is larger than an empirically determined critical value for a given set of images. For the Martian and terrestrial images studied in this work, the Otsu’s threshold (Otsu 1979) was used, and the background was treated as noisy when the value of the first minimum of V_N(R) was larger than 0.06.

The PADM algorithm employs three different techniques of grain detection, as one of them may work better than another with a particular image. These three techniques are called after their main procedures: binarization, edge detection and watershed segmentation. For all images with removable background, all approaches can be used. If the reduction of the background is not possible but the grains are separated, often the most efficient technique is the edge detection. In cases with many touching particles, the marker-controlled segmentation processing sequence (watershed) can be applied.

All these techniques consist of four steps. Each step is described below and the scheme of the whole algorithm is presented (Fig. 3).

In the first step (filtering step), the background of an input image, f, is reduced or removed, and a filtered image g₁ is generated. If the BG procedure returns a logical value false, and the studied grains are brighter than their surroundings, the filtering employs the top-hat transform (THT _R (f)). If the grains are darker than their surroundings the bottom-hat transform (BHT _R (f)) is applied. Both transformations use a structuring element in the form of a disk of a range R, that is larger than the largest particles. If the background is noisy (the BG procedure returns a logical value true), the opening procedure, γ _R (f), is employed for objects whose values are larger than their surroundings or the negative of closing procedure \( {\overline{\phi}}_R(f) \) is employed for objects whose values are smaller than their surroundings. Both procedures use a structuring element in the form of a disk of a range R, similar or larger than the background irregularities.

In the second step (segmentation step), a segmentation technique is applied to the filtered image. The segmentation step is different for each of the techniques and described below in more detail. As an output of this step a segmented binary image g₂ is calculated.

The third step (selection step) is related to removing unwanted objects from the segmented image. The applied selection procedures allow removing border particles and extracting objects that satisfy specific criteria, such as size (determined by the image resolution and the diameter of grains) or circularity (which depends on the studied grains characteristics), which also leads to reduction of segmentation artifacts. In this step, the final output image g₃, consisting of detected objects, is generated.

In the final step, the basic statistical analysis of the detected objects can be easily performed. The diameter, length, width, circularity and elongation of each particle as well as the particle size-distribution can be obtained and analyzed.

The binarization approach is the simplest and fastest. The steps of this technique are shown for two types of material. The first one is made of small dark grains located on a plain background (Fig. 4), and the latter of large bright grains located on a noisy background (Fig. 5).

In this approach, in the segmentation step, the filtered image, g₁, is binarized with the threshold operator T_[α,β], and all potential holes in features are filled (FILL). Thus this step returns a segmented image g₂ = FILL[T_[α,β](g₁)]. The binarization of studied images works well with Otsu’s clustering threshold (Otsu 1979).

The edge detection approach can be used to detect separate grains with well-defined edges. In this work, for simplicity, the steps of this approach are shown only for the Martian material (Fig. 6). In the second step of this procedure, the Canny edge detection (ED) algorithm is applied to the filtered image g₁ (Canny 1986), with a filter range R similar to the grains size. Next, the thinning procedure (THIN) is used to thin the edges to one-pixel wide, and the computed outlines are filled. All artificial lines are removed using erosion ε _R and dilation δ _R procedures with a square structuring element of a range R = 1 px. This technique returns the segmented image g₂ = δ₁[ε₁[FILL[THIN[ED₉(g₁)]]]].

The marker-controlled watershed segmentation technique (Soille 2002; Iwanowski 2009) can be used for touching as well as separated particles. In the watershed segmentation, the pixel value in an image is treated in a similar way as the elevation value in a topographic map, and boundaries between particles are determined in a similar way as boundaries between ridges. The steps of this approach are also shown only for the Martian material (Fig. 7). In the segmentation step, the reduced image, g₁, can be sharpened (SH) over a radius R, generating an enhanced image g’₁ = SH _R (g₁). In the enhance image, the contours of the grains can be detected by the Canny edge detection algorithm and added to the sharpened image to enhance grain boundaries (Fig. 7c). Next, two parallel processing sequences: gradient filtering and binarization are applied. In the first sequence, gradient filtering (GF) with a kernel of pixel radius R = 1 is performed. Gradient filtering generates a filtered image corresponding to the magnitude of the input image gradients. This allows for contours detection in the image and produces a segmentation function, SF = GF _R [ED _R (g’₁) + g’₁] (Fig. 7d). In the second sequence, the enhanced image g’₁ is binarized. Then, all holes in the binarized image are filled (Fig. 7e). From this image, the distance transform (DT) is computed. The distance transform on the binary image connects each pixel with its distance to the nearest pixel whose value is 0. This output image is submitted to Gaussian filtering (GS) with a kernel of radius R. If the kernel radius is larger, the filtered image is smoother. The kernel of radius R = 15 px can be used for medium grains (in relation to the image resolution). For large grains, R can be up to 25 px, and for small grains (at the resolution limit) down to 1 px. Next, in the output image, the markers (MS) of the particles are found using extended maxima detection (MAX) (see e.g. Soille 2002), MS = MAX[GS _R [DT[FILL[T_[α,β](g’₁)]]]] (Fig. 7f). A marker is a point in the image, which indicates that in the given place a particle is located. The MS are employed to impose the segmentation function SF. The watershed transformation of the image, WS(g’₁), is done by the Meyer method (Meyer and Beucher 1990) with 8 closest neighbors. Finally, the output is binarized with Otsu’s threshold, producing the segmented image g₂ = T_[Otsu][WS(g’₁)] (Fig. 7g).

The median diameters of the detected grains as well as the parameters for all the approaches are presented in the Appendix in Table 5.

The PADM algorithm was tested in comparison with other semi-automated and manual image analyses as well as with sieve analysis.

The statistical results of a grayscale image representing generated circular particles of almost the same size in comparison with the ImageJ and Morphologi G3 are presented in Table 1.

The comparisons of the morphological parameters and cumulative size frequency distributions for the images of the terrestrial samples computed by Morphologi G3 system and PADM algorithm are presented in Table 2 and Fig. 8. Only grains larger than 0.1 mm and smaller than 1.8 mm in diameter were analyzed. As difference between the results obtained from the different PADM techniques was not larger than 5% for the studied samples, and Morphologi G3 system uses the binarization technique, only results from the PADM binarization approach are shown.

The Morphologi G3 system has some limitations. Firstly, using a 2.5× objective, the system cannot measures particles larger than 1 mm. The second important limitation is a small field of view of the microscope. In the case of coarse-grained samples, many images are required to obtain a sufficient number of grains. Also, the method does not distinguish touching particles, so that it is crucial to apply precise dispersion before analyzing. In all samples, the PADM algorithm detected more grains than Morphologi G3, and it also detected larger and smaller particles at the same time.

Despite many differences, sieve analysis and image analysis can be compared (Fernlund 1998). An example of a comparison between these two methods for the terrestrial samples is presented in Table 3 and Fig. 9. In both cases, the statistical parameters were obtained using Folk and Ward definitions (Folk and Ward 1957). In those analyses, only grains larger than 0.5 mm were studied and the results were used only for methodological purposes and are not representative for the studied sediments. As all the PADM techniques produce similar results, solely those from the binarization approach are shown.

As it can be seen, basalt sands are more difficult to study using sieve analysis than quartz sands since they are characterized by low roundness and fragile structure. To indicate this difficulty we can describe a grain by the best-fit ellipsoid with three parameters: a is the major axis, b is the intermediate axis, and c is the minor axis. In sieve analysis, the shape of a studied grain has a great impact on the result. It can be shown that a grain passing through a square opening of the size d has the intermediate axis b in between d and \( d\sqrt{2} \), and this value mainly depends on the minor axis c. If c is similar to b, we have the first extreme. If it is much smaller than b, we have the second extreme. As a result, we can assume that sieve analysis provides only some approximation of the intermediate axis of a grain, and it can, to some extent, be compared only to the width of the grain, W. Moreover, sieve analysis is destructive for fragile grains. The basalt sands in the samples GF and SO were characterized by sharp edges and were vulnerable for abrasion. After sieve analysis, in both cases destruction of larger grains was clearly visible. In case of GF, ca. 5% wt of the material was abraded. Also, in those cases during sieving many larger grains blocked openings, so that smaller grains were less likely to pass through a sieve. Therefore, the sieving process took more time than in the case of the BD sample. Next, sieve analysis normally gives the mass of material, not the number of grains. If we would like to establish which particles are the most frequently transported, then we will ask which class is the most numerous and not the most massive. These two parameters may not be related to the same class, especially as we have grains of various origins in the sample. In the case of GF sample, the most massive was class 0.7–1.0 mm, and the most numerous 0.5–0.7 mm. Finally, sieve analysis does not allow determining the shape of grains.

Using the PADM algorithm, 43 images taken by the Mars rovers: Spirit, Opportunity, and Curiosity, were analyzed. Particles truncated by an image or partly buried were omitted as their size and shape cannot be fully determined. Examples of detection are presented for six types of material: bright streak deposit (Fig. 10), spherules (Fig. 11), ripple crest sand (Fig. 12), fragments of larger grains (Fig. 13), dust aggregates (Fig. 14), and dune sand (Fig. 15). The first four images were taken in Meridiani Planum, the fifth in Gusev Crater, and the last one in Gale Crater. A comparison between the PADM results and those from a manual method for the presented samples of Meridiani Planum deposits are shown in Table 4. All the parameters used in the analyses with the PADM algorithm are presented in Appendix Table 5.

The errors of the method can be divided into two groups. The first group is associated with inaccuracies in the detection, e.g. undetected grains, badly segmented (e.g. over- or under-segmented) images. These errors can be reduced by manual correction to some extent. The detection inaccuracy can also be associated with non-grain features that are present in some of the images. For example, in the image from Spirit rover acquired on sol 79 (Fig. 14), there are some bright linear structures and one bright spot, which are detected by the algorithm. However, in such situations the manual correction is related to ca. 1% of the detected objects. Also for images containing numerous grains, the detection inaccuracy does not significantly influence the result, so that manual correction is not necessary (Fig. 10). The second group is related to a systematic error of the given technique. This error must be taken into consideration in any statistical analysis.

The binarization technique detects often smaller number of grains for a given image than the watershed but larger than the edge detection approach. The systematic error of this technique is related to the value of the threshold, and it is less than 5% in the grain size determination. In cases of images with some touching grains, the mean values (but usually not the median values) of the grain size can be overestimated, as some grains may not be separated (Fig. 10b). For images with a noisy background, the error associated with the shape determination can occur, and in such cases the mean circularity is often underestimated (Table 4). From all the presented approaches only binarization technique, due to its simplicity, works fine with low-resolution images (in which the size of the studied particles is only slightly above the image resolution).

The detection accuracy (the ratio of well detected grains to all detected grains) in the edge detection case is greater than in the binarization case. Yet, the number of grains detected by the edge detection approach is often smaller, as this technique detects only grains with well-distinguished edges. The statistical error of this technique depends on the size of the Gaussian kernel, and it is less than 4%. In addition, the edge detection procedure tends to shift the center of the contours towards the grain exterior. This leads to systematic error that is ca. 2% in the grain size. This approach is especially good for measuring the shape of grains.

The marker-controlled segmentation accuracy depends mainly on the precision of the markers determination. This approach detects the largest percent of grains. Yet, the detection accuracy is smaller than that obtained from the edge detection technique. The statistical error of this procedure is up to ca. 7% in the grain size. In cases of overlapping or touching grains, the contours are more difficult to determine using the watershed approach, and their circularity value is often underestimated (Table 4).

The accuracy of the fitting of the grain contours (as compared with the manual assessment) for the studied set of 43 Martian images with the best-fit procedure of the PADM algorithm ranges from 85% to 100%, with the average ca. 94%. (For two images the accuracy was not determined due to high number of small grains). Yet, the inaccuracies with contours’ fitting only slightly influence the statistical results of the size of the grains. Therefore, the detection accuracy does not influence the statistical analysis of the grain diameter more than the systematic error of the method.