Image Anal Stereol 2008;27:73-78 Original Research Paper A TESSELLATION MODEL FOR CRACK PATTERNS ON SURFACES Werner Nagel1, Joseph Mecke1, Joachim Ohser2 and Viola Weiss3 1Institut fu¨r Stochastik, Friedrich-Schiller-Universita¨t Jena, D-07737 Jena, Germany; 2Hochschule Darmstadt, FB Mathematik und Naturwissenschaften, Scho¨fferstr. 3, D-64295 Darmstadt, Germany; 3Fachhochschule Jena, FB Grundlagenwissenschaften, Carl-Zeiss-Promenade 2, D-07745 Jena, Germany e-mail: nagel@minet.uni-jena.de (Accepted March 7, 2008) ABSTRACT This paper presents a model of random tessellations that reflect several features of crack pattern. There are already several theoretical results derived which indicate that this model can be an appropriate reference model. Some potential applications are presented in a tentative statistical study. Keywords: crack pattern, random tessellations, spatial statistics, stochastic geometry. INTRODUCTION Several methods for developing models of crack structures – in 2 dimensions for cracks on surfaces or thin layers – are based on the idea of line segments that start to grow from points, and the individual growth stops when an already existing crack is reached. This yields a tessellation (mosaic). There is an important model, proposed by E. N. Gilbert and reported by Noble (1967), cf. also Cowan, http://www. maths.usyd.edu.au/u/richardc/unsolved.html. Another reference for this type of a tessellation is Gray et al. (1976), cf. Stoyan et al. (1995). Recently, the STIT model was introduced by Nagel and Weiss (2005). This new model can be relatively well treated theoretically, and a series of results and formulas were already found, cf. Nagel and Weiss (2004), Nagel and Weiss (2005), Mecke et al. (2006). This fact makes the model attractive for application at least as a reference model, in particular for the statistical analysis of crack pattern. Of course, it is a crucial question how good the model can be fitted to the data. In the present paper the STIT tessellation is briefly described and some properties and quantities are summarized. Several examples of potential applications are considered and as criteria for the goodness-of-fit the variability of the cell sizes is used as well as the linear contact distribution function for the cell boundaries, i.e., the cracks. DESCRIPTION OF THE MODEL Here we give a short sketch of the construction which was described in Nagel and Weiss (2005) in full detail, in arbitrary dimension and also for the non-isotropic case. We restrict it to the planar and isotropic case. By R2 we denote the euclidean plane. All the random tessellations considered in this paper are locally finite, i.e., any bounded subset of the plane intersects a finite number of cells only. Such random tessellations can be described as the random closed set (RACS) of its cell boundaries as well as a random ensemble of its polygonal cells, i.e., as a point process on the space of convex polygons. Let W ? R2 be a bounded rectangular window. The intuitive idea of the construction is the following: The window W has a random exponentially distributed ‘life time’. At the end of this time interval a random line is thrown onto W, which divides W into two new ‘cells’. These two cells have independent and exponentially distributed life times until they are divided further by random lines. After any division, exponentially distributed life times of the new cells begin. Special attention has to be paid to the adjustment of the parameters of these exponential distributions. In the isotropic case, these parameters are proportional to the perimeter of the respective cells such that smaller cells have a stochastically longer life than larger ones. This procedure of repeated cell division is stopped at the fixed time, say 1, and the state at this time is interpreted as a realization of the tessellation Y (W). Now we give a more formal and precise description in a condensed form. Readers who are not interested in the technical details can skip this paragraph. Let (ti,gi), i = 1,2,... be i.i.d. (independent and identically distributed) pairs of random variables ti that are exponentially distributed with parameter 1/2, and isotropic uniform random (IUR) lines gi on W; ti and gi independent. The perimeter of a convex polygon p is denoted by U(p). We define a set-valued process Y(t,W), t = 0, with Y(t,W) = 0/ for 73 Nagel W et al: Crack tessellations 0 < t < t ˜1 with t ˜1 = t 1/U(W). Then Y(t ˜1,W) = Wng ˜1 with g ˜1 = g 1, and Y(t,W) remains constant until the next update. The chord W Pi g ˜1 divides W into two polygons, q2 and q3 say. Their lives start at time t ˜1 and last t ˜2 = t 2jU^q2) and t ˜3 = t3/U(q3) respectively. Now consider a general polygon qi that is generated by the construction at a time t. It lives from t to t + t ˜ i with t ˜ i = ti/U(qi). At the end of its life it is divided by the line g ˜ i which has the distribution of g i restricted to the set [qi], which is the set of all lines that hit qi. The update at that time is Y(t + t ˜ i,W) = M Y(t,W) U (qiHg ˜ i). Thus t 1 , (1) V c-1 ) where Y = (Y1,Y2,...) is a sequence of i.i.d. random tessellations that are independent of Y and have the same distribution as Y. The rescaling factors c and c/(c- 1) are chosen such that La, the mean total length of edges per unit area, remains constant. If Y has the parameter La, then cY has the length intensity (1/c)La. It is easy to see that, e.g., random line tessellations or Voronoi tessellations are not STIT. It was shown in Nagel and Weiss (2005) that, up to the intensity La, the construction described above yields the only stationary and isotropic STIT tessellation. Hence, given the length intensity La and the directional distribution of the edges - in the isotropic case the uniform distribution on [0,p) -the distribution of a stationary tessellation is uniquely determined by the STIT property. We emphasize two further properties which we will make use of in the following. The definition of a stationary Poisson line process and of the corresponding tessellation can be found in the books on stochastic geometry, e.g., Matheron (1975), Serra (1982), Stoyan et al. (1995), Schneider and Weil (2000), Ohser and Mu¨cklich (2000). The following result can also be derived from Theorem 5-4-2 in Matheron (1975). There the stability with respect to the union of RACS is investigated which corresponds to the superposition - in contrast to iteration - of tessellations. But - roughly - if one considers the interior of a single cell, there is no difference whether superposition or iteration of tessellations is applied. This can be expressed more precisely in terms of the capacity functional. 74 Image Anal Stereol 2008;27:73-78 Lemma 1 The interior of the typical cell of the stationary and isotropic STIT tessellation with edge length intensity LA has the same distribution as the interior of the typical cell of the stationary and isotropic Poisson line tessellation with the same length intensity LA. The difference in the distributions of the two mentioned cells arises when the nodes on the boundaries are taken into account, see Lemma 3. It is easy to see that the STIT property of a tessellation Y transfers to intersections with lines. This yields Lemma 2 The intersection point process that is induced by the stationary and isotropic STIT tessellation Y with edge length intensity LA on any line is a stationary Poisson point process, and its intensity is 2LA/p. RELATIONS FOR MEAN VALUES A variety of mean values for general stationary random tessellations was studied systematically by Mecke (1984), cf. also Stoyan et al. (1995) and the references given therein. The properties of STIT tessellations mentioned in the previous paragraph yield several particular relations for those parameters. The following formulas have already been published, also for non-isotropic stationary STIT tessellations in Nagel and Weiss (2004). We summarize them briefly, since they provide a useful tool also for statistical purposes. As usual in the theory of tessellations, an edge is a line segment in Y between two nodes and without further nodes in its relative interior. We use the following notation for mean values. N01 = N02 – mean number of edges emanating from the typical node = mean number of cells which contain the typical node, N20 = N21 – mean number of nodes = mean number of edges on the boundary of the typical cell. We present the formulas together with well known results for Poisson line tessellations in order to compare both tessellations. We will use the upper index × to indicate that a symbol refers to the Poisson line tessellation Y×. The Poisson line tessellations have X-shaped nodes (crossings) only. Lemma 3 If Y is the stationary and isotropic STIT tessellation described above and Y× the stationary and isotropic Poisson line tessellation with the same intensity LA then p = 3 L = 23L (1) L (2) Ur. = 2 L p = U2, ^ A 2. (3) A2 = L p 2 A = A2, (4) N0 = p 2L2 A = 2N 0X, (5) N 1 = p 3L2 A = 2N1 , (6) N2 = p 1L2 A = N2, (7) N01=N02 = 3, N 0* = N 0* = 4, (8) N20 = N21 = 6, N20 = N21 = 4. In Mecke et al. (2006) results on the distribution of the length of line segments in STIT tessellations are derived. Besides the above mentioned edges also the line segments which occur in the construction as chords (or cracks) can be considered. LA – mean total edge length per unit area, edge length intensity, L – mean length of the typical edge, U2,A2 – mean perimeter and mean area, resp., of the typical cell, N0 – mean number of nodes per unit area, N1 – mean number of edge midpoints per unit area, N2 – mean number of cell centroids per unit area, APPLICATIONS AND TENTATIVE STATISTICAL STUDIES In order to assess how the model of a stationary and isotropic STIT tessellation is adapted to real patterns consider the four images in Figs. 2 to 5 from different applications. As a reference image we use the simulation in Fig. 1. 75 Nagel W et al: Crack tessellations Basically, goodness-of-fit tests for random tessellations can test the geometry of the individual cells – in our case the distribution of Poisson typical cells – but also test the mutual arrangement of the cells. The latter approach seems to be very complex. In order to obtain a first impression whether the STIT tessellation can be a candidate model one can check some qualitative – topological – features. One of them is the type of nodes. In a STIT tessellation occur T-nodes only, i.e., in each node meet exactly three edges, and two of them are collinear, see Fig. 6. In contrast to this, e.g., Poisson-Voronoi tessellations have Y-shaped nodes where three edges meet but there is no collinearity. Fig. 4. Simulated cracks in soil (H.-J. Vogel). Fig. 2. Majolika. Ceramic surface (Photo: G. Weil). Fig. 5. The pattern of the thick black lines – the connective tissue in a rat muscle – is studied here (I. Erz?en). Fig. 6. In STIT tessellations occur T-nodes only. Quantitative goodness-of-fit tests can be based on Lemma 1, i. e., on the fact that the interior of the typical cell is the same as for a Poisson line tessellation. Here we use as test criteria the coefficient of variation f of the area of the typical cell and furthermore the linear contact distribution function FC of the cells. As above, denote the random area of the typical cell of the STIT tessellation by A2. Since its distribution coincides with that one of a Poisson line tessellation, we can apply Fig. 3. Cracks in a titanium-nitride coating on the corresponding formulas which are given in Stoyan cemented carbide (R. Ohser-Wiedemann). et al. (1995). 76 Image Anal Stereol 2008;27:73-78 Table 1. Estimated values of the coefficient of variation for the area of the typical cell. For the stationary and isotropic case EA2 p/L2A and varA2 = (p2/2 - 1)p2 coefficient of variance of the area is 1)p2/L4A and hence the f \/varA2 EA2 p2 V 2 1 1.9836 For the simulations and the real structures the areas of the cells were measured. The estimated values of the coefficient f are listed in Table 1. It is obvious that the variability of the cell areas in all the samples is considerably smaller than the theoretical value for STIT tessellations. In particular, in the soil sample the cells are of almost the same size. For the titanium-nitride coating and the majolika data it can be worth to investigate more and larger samples, and also the anisotropy of the structure has to be taken into account, i.e., the comparison should not be made with the isotropic STIT tessellation but with an appropriate anisotropic one. In order to study contact distribution functions (for a definition see e.g., Ohser and Mu¨cklich (2000), Stoyan et al. (1995)) the set of all edge points of the tessellation has to be considered as a random closed set Y. Since the interior of the typical cell of the STIT tessellation is distributed as that one of a Poisson line tessellation it is known that the contact distribution functions are exponential ones. Here we consider the linear contact distribution function as a function of the length £ > 0 for horizontal segments sg. With the notion a = (2/p)La, we obtain for the isotropic case: FC(£) =P(Ynse=0/) = 1- e-ai and hence ln(1 -FC(£)) = -a£. Fig. 7. Logarithm of the linear contact distribution function: simulated image. Thus one can check for the samples whether the logarithm of the corresponding estimated function is approximately linear. Figs. 7, 8 and 9 show these estimates for the simulated image, the titanium-nitride coating and the majolika, respectively. A linear function with an estimated slope was drawn into each figure in order to allow a rough comparison. The deviations of the estimates from a linear function for the larger values of the length l are partly due to edge effects in the relatively small images. Also here, the work will be continued by considering larger samples and taking into account the anisotropy in the observed structures. Furthermore, the study will be extended to contact distributions which use other structuring elements. Since in applications the cell boundaries are not linear but curved, it seems to be more appropriate to use circles instead of linear segments or squares. _ _ _ 77 Nagel W et al: Crack tessellations Fig. 8. Logarithm of the linear contact distribution function: Titanium-nitride coating. Fig. 9. Logarithm of the linear contact distribution function: Majolika. CONCLUDING REMARKS As already mentioned the presented statistical results are tentative ones and they illustrate a work in progress. It is already obvious that some of the structures (soil, majolika) cannot be appropriately fitted by a STIT model. Therefore it is an aim to make the model more flexible, e.g., by endowing the STIT probability distribution with a density. In Nagel and Weiss (2005) the STIT tessellation model was developed for arbitrary dimension and arbitrary directional distributions of the cell facets. Thus, in particular, 3-dimensional crack structures as they can emerge e.g., in rocks can be studied. The STIT tessellation model is suitable for stereology since the STIT property of a stationary - and not necessarily isotropic - STIT tessellation in any dimension transfers to intersections with lower dimensional planes or lines. Since we have a complete characterization of STIT tessellations the relations between the section profiles and the higher dimensional structure is relatively easy to describe. ACKNOWLEDGMENT The authors thank the referees for their helpful comments and the valuable hints for future work. REFERENCES Gray NH, Anderson JD, Devine JD, Kwasnik JM (1976). Topological properties of random crack networks. Math Geol 8:617-26. Matheron G (1975). Random sets and integral geometry. New York, London: John Wiley & Sons. Mecke J (1984). Parametric representation of mean values for stationary random mosaics. Math Operationsfor Stat 15:437-42. Mecke J, Nagel W, Weiss V (2006). Length distributions of edges in planar stationary and isotropic STIT tessellations. Jenaer Schriften Math Inf, http://www. minet.uni-jena.de/preprints/nagel_06/. Also: (2007). J Contemp Math Anal 42:28-43 Nagel W, Weiss V (2004). Crack STIT tessellations -existence and uniqueness of tessellations that are stable with respect to iteration. Izvestija Nacionalnoj Akademii Nauk Armenii, Matematika 39:84-114. Also: J Contemp Math Anal 39:62-84. Nagel W, Weiss V (2005). The crack tessellations -characterization of the stationary random tessellations which are stable with respect to iteration. Adv Appl Prob (SGSA) 37:859-83. Nagel W, Weiss V (2008). Mean values for homogeneous STIT tessellations in 3D. Image Anal Stereol 27:29-37. Noble B (1967). Applications of Undergraduate Mathematics in Engineering. New York: Macmillan. Ohser J, Mu¨cklich F (2000). Statistical analysis of microstructures in materials science. Chichester: John Wiley & Sons. Schneider R, Weil W (2000). Stochastische Geometrie. Stuttgart, Leipzig: BG Teubner. Serra J (1982). Image Analysis and Mathematical Morphology. London: Academic Press. Stoyan D, Kendall WS, Mecke J (1995). Stochastic Geometry and its Applications. 2nd edn. Chichester: John Wiley & Sons. 78