Image Anal Stereol 2002;21:191-198 Original Research Paper
TOPOLOGICAL LOCALISATION OF DEFECTS AT ATOMIC SCALE
Jean-Paul Jernot1, Patricia Jouannot-Chesney1, Christian Lantuejoul2, Gerard Nouet3 and Pierre Ruterana3
^SMRA, CRISMAT/ESCTM, 14050 Caen Cedex, France, 2ENSMP, Centre de Geostatistique, 77305 Fontainebleau, France, 3ISMRA, LERMAT, 14050 Caen Cedex, France e-mail: jemot@ismra.fr, jouannot@ismra.fr, lantu@cg.ensmp.fi-, nouet@ismra.fr, ruterana@ismra.fr (Accepted October 2, 2002)
ABSTRACT
The problem addressed in this paper is the detection of defects on atomic structures. The procedure proposed is in two steps. At first a tessellation is built starting from the atoms. It consists of a partition of the space into cells, and is used to define the neighbourhood relationships between the atoms. Then, the local contribution to a topological parameter, namely the Euler-Poincare characteristic, is defined and measured for each cell. Within a regular tessellation, made of identical cells, this local contribution is equal to zero. Any local deviation from regularity corresponds to a tessellation containing cells with non-zero contributions. This allows us to locate the defects from a topological criterion and opens the way to a fully automatic detection of interfaces at atomic scale. The procedure is applied in 2D space for the detection of edge dislocations, grain boundaries and twins from HREM models and images. A 3D example is also given to illustrate its generality.
Keywords: defects, Euler-Poincare characteristic, HREM images, interfaces, tessellations, topology.
INTRODUCTION
In materials science, it has long been recognised that topology offers a basic quantitative description of microstructures. Several examples of such a topological analysis can be found in the literature for sintering processes (Rhines, 1967; De Hoffe* al., 1972), grain growth (Smith, 1964; Rivier, 1986), multiphase grain structures (Cahn, 1966) or in relation with flow through porous media (Macdonald et al., 1986; Jouannot et al, 1995).
Topological descriptions have also been proposed for cellular structures: polycristalline materials, biological cells, foams, etc (Smith, 1952; Aboav, 1980; Rivier, 1985). The relations are mainly expressed as a function of the mean number of sides per cell and based on Euler's equation and the local equilibrium of cells under surface tension. They are verified only when the rules governing this local equilibrium are fulfilled i.e. not on random tessellations of the space or on periodic structures (except for regular stackings of hexagons or tetrakaidecahedra).
We propose here a description of the spatial cell's organisation valid for any kind of cellular structure. It is based on the measurement of a new parameter: the contribution of each cell to the Euler-Poincare characteristic of the space. This approach is general because no prerequisite (local equilibrium of cells,
geometrical unit, etc.) is needed. As far as grain boundaries between metal crystals are concerned, they have already been described as packings of polyhedral units (Ashby et al., 1978). The present analysis complements, from a topological point of view, this geometrical description.
In this article, the contributions of the cells to the Euler-Poincare characteristic of the space are used to locate the defects occurring on a regular tessellation. Then, on an atomic structure, the atoms belonging to a defect can be automatically selected using this topological criterion. To illustrate the method, edge dislocations or grain boundaries have been extracted from HREM images.
DEFINITIONS Euler-Poincare characteristic
In order to simplify the presentation, we limit ourselves to the 2D case. As will be seen in the last section, the extension to 3D space presents no major difficulties.
Consider a polygon; it is well known that it has the same number of vertices, V, and edges, E:
V = E.                             (1)
This equation is nothing but Euler's equation:
V - E + P = 1,                     (2)
191
JERNOT JP ET AL: Topological localisation of defects
where P, the number of faces, is equal to 1.
Consider now an aggregate of polygons. Their union satisfies the more general equation:
V - E + P = N,                    (3)
where V, E and P stand respectively for the number of vertices, edges and faces of the aggregate (see Fig. 1). N is called the Euler-Poincare characteristic (EPC) or connectivity number (Serra, 1982). It can be topologically interpreted as the number of connected components minus the number of their holes.
Fig. 1. Euler-Poincare characteristic of isolated or aggregated polygons.
Planar tessellations
A planar tessellation is defined as a family of compact and convex subsets (Zj) indexed by i e I and satisfying the following conditions:
i)   the union of all the Z; is equal to R2 .
ii)  each interior of Z; is non-empty.
iii) the interiors of Z; are pairwise disjoint.
iv) the number of Z; intersecting a bounded domain of R2is finite.
The elements Zj are the cells of the tessellation. Due to these conditions, any planar tessellation is made up of a countably infinite number of polygonal cells.
A facet F of the tessellation is defined as an intersection between cells. Its dimension, dimF, is equal to 0 for a point, 1 for a segment and 2 for a polygon; its order, ordF, is the total number of cells to which it belongs.
Local contribution of a cell to the EPC
Let X be a compact subset of R2 which has been intersected by a tessellation (Z; , i e I). Under some
mild assumptions on the shape of X, it has been proved (Jernot et al., 2001a) that the EPC of X can be written as:
N(X) = ^    (-l)2-dimFN(XnF),       (4) Fe<F
where T is the set of facets of the tessellation. The number 2 in the exponent is not fortuitous: it is simply the workspace dimension.
The local contribution of one cell to N(X) is defined by sharing the term N(XnF) uniformly between all the cells containing the facet F. Therefore the local contribution to the EPC of X with respect to the cell Z; (Jernot et al., 2001b) can be defined as:
/_i\ 2-dimF
N(XnF)>       (5)
Ci(X)=    2
ordF
FefF(Zj)
where (F(Zi) is the family of all facets contained in Zj.
The term 'local contribution' is justified by the fact that the EPC of X is the sum of all the contributions Q(X) associated with each cell Z;:
N(X) = £ qCX).
(6)
iel
In the case where X = Zj, the Eq. 5 simplifies and gives:
(_W d™F
c,(z,)=   £
Fe <F(Zj) which can be expanded as:
CW
ordF
1
(V)
F e (F0(Zj)  ordF ^           1
Fefl^Zj)
ordF
+
Fe(F2(Zi)
ordF
(8)
where (fd(Zj) denotes the set of facets of dimension d contained in Zj.
F2(Zj) has a unique element: the cell Zj itself. Facets of dimension 1 and 0 of Z; may not coincide with the edges and the vertices of the cell Zj as can be seen in Fig. 2.
192
Image Anal Stereol 2002;21:191-198
Fig. 2. The elements of ^(Zi) result from intersections between Z, and its neighbouring cells. (AC) is an edge of the cell Zi but is not a facet of the tessellation. B is not a vertex of the cell Z; but is a facet of the tessellation.
In all examples given in this paper, the facets of dimension 1 and 0 coincide respectively with the edges and the vertices of the cells. Moreover, we always have ordF = 1 for facets of dimension 2 and ordF = 2 for facets of dimension 1. Then, the previous equation can be simplified as:
c.(z.)= y   J - y i +1-   (9)
1    x'     *-*    ordV      ^   2 Ve Zj                 Ee Zj
This equation is illustrated in Fig. 3. One can see at once that the local contributions obtained depend on the cells surrounding Z; in the tessellation and bring a topological information that cannot be obtained from the mere number of edges of a cell. This point appears clearly in Fig. 8.
Fig. 3. Local contributions of one cell, Z,. to the EPC of several tessellations of the 2D space.
For a regular tessellation, made of identical cells, the contribution of each cell to the EPC of the space
is equal to 0 (if not, the EPC of R2 would be infinite instead of 1). This is not true if the tessellation is complex (e.g. Voronoi' partition or Penrose tilings). In that case, only the mean value of the cell contributions is equal to 0. For cellular structures in equilibrium under surface tension (Smith, 1952; Rivier, 1985), assuming ordV = 3 in Eq. 9 leads to C^Z;) = 0 if the number of vertices (or edges) of the cell is equal to 6.
If a deviation from regularity is ancountered in some cells of a regular tesselation, then their contributions are not zero. This difference is now used for detecting defects on crystallographic structures.
DETECTION OF DEFECTS ON CRYSTALLOGRAPHIC STRUCTURES
The structures of interest are directly related to HREM images. First, the procedure is explained on theoretical structures. Then, model structures derived from HREM images are studied. Finally, an example is given for an HREM image. In all cases, the projected atomic columns (white or black spots according to the experimental conditions) are referred to as 'atoms'.
Illustration of the method on theoretical structures
Consider the images of Fig. 4a which represent partially incoherent and coherent interfaces according to Smith (1952). Two zones where atoms are regularly arranged are observed on each image. The purpose of this exercise is to detect the transition between both zones.
The first step is to build a tessellation starting from the set of atoms. It must be pointed out that several tessellations can be designed from the same set. In a standard one, we can consider the Voronoi cell associated with each atom. Others are based on graphs: the cells are limited by edges between adjacent atoms, an adjacency relationship defining the graph. If the atoms are represented by spots, the cells can be defined as the zone of influence of each spot (Lantuejoul, 1978).
In the present case, we have used the Gabriel graph (Gabriel and Sokal, 1969): two atoms ai and &2 are said to be adjacent if the disk with diameter (a^) does not contain any other atom. This tessellation has turned out to be more stable than the Voronoi' partition.
The cells of Fig. 4b have been obtained using the Gabriel graph. Observe that only the cells located within the transition zone may have non-zero contributions. Then, the interface is localised from the set of atoms contained in cells with non-zero
193
JERNOT JP ET AL: Topological localisation of defects
contributions (Fig. 4c) but these cells depend on the tessellation design.
Edge dislocations
The analysis of the core structure of edge dislocations is usually carried out in three steps: i) observation of the sample along an appropriate zone axis ii) generation of atomic models using anisotropic elasticity, and iii) image simulation, followed by a
comparison between simulated and experimental images. An atomic model corresponding to the projection of an edge dislocation in GaN layers grown on (0001) sapphire and observed along the [0001] axis is shown in Fig. 5.
The local contribution of the cells is zero (6/3 - 6/2 + 1) except for the 5 and 7 sided ones whose values are respectively 1/6 and -1/6. These cells correspond to the core of the dislocation.
Fig. 4. Two schematic examples of interfaces between crystals, (a) atom locations, (b) tessellation associated with atom locations (Gabriel graph): the contributions of the white, light grey and dark grey cells are respectively zero, negative and positive, (c) the atoms that belong to cells with nonzero contributions are represented in black.
194
Image Anal Stereol 2002;21:191-198
Fig. 5. Example of edge threading dislocation in GaN (adapted from Potin et al, 2000). For the dislocation core, the sum of the contributions of the cells to the EPC of the space is zero.
Grain boundaries
This procedure can also be applied to grain boundaries which are based on periodic arrays of dislocations. A first example is given in Fig. 6: for E5, rotation of 36.87° around a <001> axis, the grain boundary built of one type of dislocation is perfectly planar. The set of cells with non-zero contributions is easily detected and defines the grain boundary plane.
is slightly rough. It corresponds to £11 which is described by a rotation of 50.48° around a <11> axis. Two variants A and B have been identified in silicon and germanium under different experimental conditions (Bourret and Bacmann, 1987; Putaux and Thibault-Desseaux, 1990). Again, a modification of the local contribution to the EPC allows us to accurately locate the grain boundary plane: the two configurations 211A and Z11B are clearly differentiated and, as in the preceding example, the contribution of each period is
In a second example (Fig. 7), the boundary plane      zero-
Fig. 6. Z5 tilt grain boundary in Cu (adapted from Grigoriadis et al., 1999). The disks and the circles correspond respectively to atoms at heights z = 0 and z = 1/2.
195
JERNOT JP ET AL: Topological localisation of defects
Fig. 7. Two examples of grain boundaries in silicon and germanium (adapted from Chen et al, 1999). {5 atom cell} and {7 atom cell} whose contributions are respectively +1/6 and —1/6 are grouped to form structural units with zero contribution.
Twins
The measurement can also be carried out in twins if a local modification of the cell contribution is observed. For instance, in the {111} twin of the face-centred cubic system there is only a modification of
the orientation of the cells without any change in their topology, so this approach is not appropriate. For the {1012} twin in the hexagonal system the situation is more favourable since the local topology is changed at the level of the twin plane (Fig. 8).
Fig. 8. Core defect inside a twin boundary from deformed a-Ti (adapted from Braisaz et al, 1996). On the bottom left figure, two different elementary features are clearly delineated: one for the grain boundary and one for the step.
196
Image Anal Stereol 2002;21:191-198
Contrary to the preceding examples, the number of the edges of the cells is constant even in the defect zone. Nevertheless, the twin plane is still localised from the contributions of the elementary triangular cells of the tessellation. Their values are equal to zero everywhere (3/6) - (3/2) + 1 except in the twin plane for which a structural unit is detected. This structural unit is made up of 10 cells whose contributions are -5/210 (5 cells), +2/210 (2 cells) and +7/210 (3 cells). The total contribution of the structural unit is then zero. Inside the twin plane, a step corresponding to the total contribution 8(-5/210) + 6(2/210) + 4(7/210) = 0 is observed. Then, even small atomic steps such as the step b2/2 associated with the twinning dislocation (Braisaz et ah, 1996) are localised.
EXTENSION TO 3D SPACE
The procedure developed may be applied in 3D space provided that 3D images are available. In 3D space, the local contribution to the EPC of X with respect to the cell Z; is defined as:
/   i \ 3 - dimF
ci(x)= Z ^^N(Xnp)-  (5'}
MQQ    °rdF
In the case where X = Zj, this equation simplifies and gives:
c.(z.) =- y   J   +  y — -
Ve Z ordV      E^z ordE Ve Zi              E£ Zi              ,    (9')
v-    1
since ordF = 1 for facets of dimension 3 and ordF = 2 for facets of dimension 2.
As in 2D space, a regular 3D stacking of identical cells leads to a contribution equal to zero for each cell. For instance, the contribution of each cell is -(8/8) + (12/4) -(6/2) + 1 in the case of a simple cubic stacking and -(24/4) + (36/3) - (14/2) + 1 for a compact stacking of tetrakaidecahedra. Any local topological modification of the tessellation will induce non-zero contributions in the vicinity of the defect.
A simple 3D interface can be given as an illustration: two crystals with simple cubic structures are translated 1/2, 1/2, 1/2 one from the other, so as to create tetrahedra and square-based pyramids in the interface zone. Then, the non-zero local contributions correspond to:
-(4/13 + 4/8) + (8/4 + 4/5) - (6/2) + 1 = -1/130 for the cubes sharing a face with the pyramids, -(5/13) + (4/4 + 4/5) - (5/2) + 1= -11/130 and
-(4/13) + (4/4 + 2/5) - (4/2) + 1= +12/130 respectively for the pyramids and for the tetrahedra. The association of these three cells generates the elementary topological unit of the interface.
CONCLUSIONS
In this article, a method has been proposed for detecting the interfaces of an atomic structure provided that the associated tessellation departs from a regular one. It is based on a new topological criterion and has been illustrated on several examples with a particular reference to HREM images.
Associated with an automatic extraction of atomic positions (Chaix, 1998), this opens the way to a fully automatic detection of interfaces at atomic scale but requires images with a good contrast and a sufficient magnification.
REFERENCES
Aboav DA (1980). The arrangement of cells in a net. Metallogr 13:43-58.
Ashby MF, Spaepen F, Williams S (1978). The structure of grain boundaries described as a packing of polyhedra. Acta Metall 26:1647-63.
Bourret A, Bacmann JJ (1987). Atomic structure of grain boundaries in semiconductors. Rev Phys Appl 22:563-8.
Braisaz T, Ruterana P, Nouet G, Serra A, Komninou Ph, Kehagias Th, Karakostas Th (1996). High-resolution
electron microscopy study of the (10 1 2) twin and defects analysis in deformed polycrystalline oc-titanium. Phil Mag Letters 74(5):331-8.
Cahn JW (1966). A model for connectivity in multiphase structures. Acta Metall 14: 477-80.
Chaix JM (1998). Extraction of atomic positions from HRTEM images of grain boundaries. Acta Stereol 17(3):321-6.
Chen J, Hairie A, Nouet G, Paumier E (1999). Relative stability of two structures of the X= 11 <011> tilt grain boundary in silicon and germanium by the tight-binding method. Materials Science Forum, Trans Tech Publications 294-296:227-30.
De Hoff RT, Aigeltinger EH, Craig KR (1972). Experimental determination of the topological properties of three-dimensional microstructures. J Microsc 95(1):69-91.
Gabriel KR, Sokal RR (1969). A new statistical approach to geographic variations analysis. Systematic Zoology 18:259-78.
Grigoriadis P, Karakostas Th, Komninou Ph, Pontikis V (1999). Low-energy configuration of the 2=5 (210) [001] tilt grain boundary in fee crystals. Materials Science Forum, Trans Tech Publications 294-296:177-80.
197
JERNOT JP ET AL: Topological localisation of defects
Jemot JP, Jouannot-Chesney P, Lantuejoul C (2001). Evaluating the Euler-Poincare characteristic of a set using a spatial tessellation. Image Anal Stereol 20(3): 149-52.
Jernot JP, Jouannot-Chesney P, Lantuejoul C (2001). Mesure de la caracteristique d'Euler-Poincare sur des images 2D ou 3D. Colloque VIM 2001. Recents Progres en Genie des Precedes. Ed. Lavoisier (Paris). 15/78: 187-94.
Jouannot P, Jemot JP, Guyon E (1995). Etude de la connexite de structures aleatoires. C R Acad Sei 321:425-30.
Lantuejoul C (1978). Doctoral dissertation: La squelettisation et son application aux mesures topologiques de mosai'ques polycristallines. ENSMP (Paris): 12.
Macdonald IF, Kaufmann P, Dullien FAL (1986). Quantitative image analysis of finite porous media (I and II). J Microsc 144(3):277-315.
Potin V, Ruterana P, Nouet G, Pond RC, Morkoc H (2000). Mosaic growth of GaN on (0001) sapphire: a high-resolution electron microscopy and crystallographic
study of threading dislocations from low-angle to high-angle grain boundaries. Phys Rev B 61(8):5587-99.
Putaux JL, Thibault-Desseaux J (1990). HREM characterization of structural changes in a deformed E=9 (122) grain boundary in silicon. J Phys Colloq 1:323-8.
Rhines FN (1967). Measurement of topological parameters. Proceedings of the 2nd International Congress for Stereology. Ed. Springer-Verlag (New York): 234-49.
Rivier N (1985). Statistical crystallography. Structure of random cellular networks. Phil Mag B 52(3):795-819.
Rivier N (1986). Structure of random cellular networks and their evolution. Physica D 23:129-37.
Serra (1982). Image analysis and mathematical morphology. London: Academic Press.
Smith CS (1952). Grain shapes and other metallurgical applications of topology. In Amer. Soc. For Metals, ed., Metal interfaces. Cleveland: 65-108.
Smith CS (1964). Some elementary principles of polycrystalline microstructure. Metallurgical Reviews 33(9):l-47.
198