Image Processing and Geoinformatics Researching methods of reconstruction of three- dimensional crystal lattice from images of projections Shirokanev A.S., Samara State Aerospace University Kirsh D.V., Kupriyanov A.V. Samara State Aerospace University Image Processing Systems Institute, Russian Academy of Sciences Abstract. The paper presents the developed algorithms for the reconstruction of multiple crystal lattice sites. The study was conducted with a set of crystal lattices and the developed method of modeling a three-dimensional structure of ideal crystal lattice sites. The results of the reconstruction of three-dimensional structures of lattice sites are shown using different metrics comparison. Comparative characteristics of accuracy of the algorithms are given in the paper. Keywords: crystal lattice, Bravais lattice, unit cell, reconstruction algorithm, comparison metric, clustering algorithm Citation: Shirokanev A.S., Kirsh D.V., Kupriyanov A.V. Researching methods of reconstruction of three-dimensional crystal lattice from images of projections. Proceedings of Information Technology and Nanotechnology (ITNT-2015), CEUR Workshop Proceedings, 2015; 1490: 290-297. DOI: 10.18287/1613-0073-2015-1490-290-297 Introduction Nowadays, a great number of publications are devoted to reconstruction methods for three-dimensional structures [1-5]. In particular, an important stage in the study of the atomic structure of the matter is the development of mathematical methods for the reconstruction of the spatial structure of the matter on two-dimensional images obtained by electron microscopy [6, 7]. The development of these methods is crucial in the study of materials with ordered structure, called crystals [8]. The purpose of the work is to develop algorithms for the reconstruction of the crystal lattice and research the developed algorithms using image comparison metrics. Modeling an ideal crystal lattice A model crystal lattice can be described by the Bravais lattice. A comprehensive description of the Bravais lattice is a unit cell, represented in the form of three non- 290 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… coplanar translation vectors [9]. The main parameters adopted in crystallography, are the length of the translation vectors: a, b, and c, and the angles between the vectors: α, β, and γ. Additionally, we define the starting and ending indices: 𝐼0 , 𝐽0 , 𝐾0 , 𝐼1 , 𝐽1 , and K1 of sites on each axis as the input parameters for modeling a set of crystal lattices. To construct a model of a crystal lattice, we need to know the translation vectors [10]. The developed method allows us to compute the translation vectors by the parameters adopted in crystallography. The method allows us to specify the range of angles, in which the model of the lattice would be correct. Knowing the translation vectors, we can generate a set of points corresponding to the crystal lattice. We can do that by specifying the range of variation of integers: I 0 , J 0 , K 0 and I1 , J1 , K1 . From the geometry of a unit cell, the corners α, β, and  can take values from the ranges:    0,   ,    0,   ,    : cos    cos(   ),cos(   )    0,   . The limitation on the angle  can be represented as (1).   min  a1 , a2  , max  a1 , a2  , (1)   where a1  2             0,   , a2     . The condition (1) limits the angle  of the segment that allows us to generate a random lattice on the set parameters adopted in crystallography. The developed method makes it possible to generate a three-dimensional set of sites representing a Bravais lattice [9]. In practice, the method is useful for studying a large set of crystal lattices. The set of sites is generated automatically. Lattices, which the algorithm works poorly with, are also detected automatically. Algorithms of reconstruction of sets of sites of a crystal lattice. Back-projection algorithm – the reverse process to the algorithm for projecting a three-dimensional image on a plane. The reconstruction algorithm receives image projections and their position in the space as input parameters. The result of the algorithm is a three-dimensional image, which is a set of points in the space or, to put it mathematically, a finite set of points in a three-dimensional space [11]. The main task of the reconstruction algorithms – to restore an image, approximating the “total picture”. Reconstruction algorithm based on grid partitioning of a line The first back-projection algorithm based on grid partitioning of a straight line means that each line recoverable from a non-zero point of a preselected projection, is split into a grid. Grid points are projected onto the plane of the other projections. Then the number of projections, which the site falls in, are counted [11]. 291 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… If a three-dimensional point is projected onto a plane (by ignoring one component of the radius vector), then it can be reconstructed ambiguously (along the line). In other words, the inverse operator of the projection should be replaced by a functional of the following form (2).  1 0   0      x   A  0 0  x   C   , C   . 1  (2)  0 1   0    The basic logic of the algorithm can be described in the form of the equation (3). S  x   k : Rk k x   0  k  1,..., i  1, i  1,..., n , (3) where  k – projection operator, Rk – two-dimensional function (ray transform). We get a lot of points on the line for each point with non-zero intensity, which lies on the main projection, using the inverse operator (2). The continuous line is limited to the grid. This means that the varied variable belongs to the multitude of Dhn  hn Then the corresponding points are projected onto the planes of the other projections. In other words, the points of the line are substituted in the right side of formula (3). The algorithm has a number of drawbacks. The sampling of the line leads directly to the non-accuracy of the algorithm, and decreasing the sampling step affects the speed of the algorithm. Reconstruction algorithm based on minimizing distance The second algorithm eliminates these disadvantages. The construction of the algorithm is based on solving the problem of minimizing the distance between the point with non-zero intensity that lies on some projection and the line projected on the plane of the projection from the line recoverable from a non-zero point of some main projection [11]. This algorithm works with three-dimensional geometry. That means that all points on the projections should be previously converted into three-dimensional space, and all normal of the projections for them must be found. To find a recoverable point, one should carry out the following procedure: 1. Find the parameter using the formula (4).  n, zоп  n, nоп    zоп  z, nоп  t , (4)  nоп   n, nоп  2  2 where nоп – normal to the plane of the main projection, zоп – point on the main projection, n – plane normal to the projection of interest, z – point on the projection of interest. 292 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… 2. Find point x using the formula (5). x  nопt  zоп , (5) where nоп – normal to the plane of the support projections, zоп – point on the main projection, t – found by the formula (4). 3. Determine whether the point is recoverable. To do this, we use the condition (6). d 2  D 2  D2   x  z, x  z    n, x    2  h  , 2 (6) where x – recoverable point, z – point lying on the projection of interest, n – plane normal to the projection of interest. The result of the algorithm is a set of three-dimensional points of a recoverable set of the crystal lattice. The algorithm works with the points of non-zero intensity; that allows speeding up the recovery of the crystal lattice. Due to use of analytical computation of recoverable points, the algorithm has a higher accuracy than the first one. The recovered set represents a certain distribution of probabilities. Thus the set can undergo further filtration to obtain the final estimate of the original set. In this work, the filter based on the clustering algorithm distinguishing a “cloud” of points was used. Metrics of comparison of sets of spatial points The metric called Hausdorff distance (or Hausdorff metric) is well-known among many comparison metrics of sets [12]. Let E and F – non-empty compact subsets of R n . Hausdorff distance between E and F will be determined by the formula (7). H  E, F   max d  E, F  , d  F , E  , (7) where d  E, F   supinf d  x, y  . xX yY To compute the Hausdorff metric for finite sets, it is sufficient to run a computation by the formula (8).  H  E, F   max d  E, F  , d  F , E  ,  (8) where d  E, F   max min d  xi , y j  . i: xi E j :y j F Metric quaternion signals have been analyzed in addition to the Hausdorff metric [13]. The metric is based on finding polynomial coefficients, which are polynomial function of a hyper variable. The coefficients of the polynomial am can be found by using the least squares method. By solving the problem of minimizing the total error of the approximation, we obtain a system of linear quaternion equations, which can be solved directly using the Gauss method or reduced to solving a system of equations with real coefficients [13]. 293 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… A value that characterizes the measure of similarity between objects can be the result of a scalar multiplication of the coefficients of the polynomial of the reference and processed objects. It can be defined by the formula (9). M 1    am am*( э) . (9) m0 Researching reconstruction algorithms For the experiment, the set is projected onto the projection plane. Then the reconstruction algorithm is executed. The result set is compared to the reference using the metrics of comparison. By the results of the experiment, we can draw conclusions on the quality of the algorithm. Let’s define the “pseudo image” as the result of the back-projection algorithm. Each site of the recovered lattice has a pseudocolor, that is, a color corresponding to the number of projections, in which the site can be projected. [11] Figure 1 shows the results of the reconstruction using the first and the second algorithms by the example of the triclinic lattice. The blue color indicates a site that enters the two projections of the three, and red – all three projections. The result recovered with the first algorithm contains errors related to splitting the line. The second algorithm recovers the lattice sites much better. a) b) c) Fig. 1. – Comparing the work of the reconstruction algorithms: a) reference image; b) reconstructed image by the algorithm based on grid partitioning; c) reconstructed image by an algorithm based on minimizing the distance Clustering-based filter applied to the result demonstrates good performance in examples with grids with frequent congestions (clouds) of sites. Figure 2 shows the result of the clustering algorithm by the example of the triclinic lattice. 294 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… a) b) Fig. 2. – The result of processing the image by the filter based on the clustering algorithm: a) image reconstructed by the reconstruction algorithm; b) the processed image The analysis of the first two algorithms on all crystal system arrays using both metrics discussed in this paper is presented in the form of quantitative results of recovering the structure of lattice sites by each algorithm (Table 1). Table 1. Researching reconstruction algorithms Crystal system Hausdorff metric Metric quaternion signals primitive lattice The algorithm The algorithm is The algorithm The algorithm is based on grid based on finding based on grid based on finding partition the minimum partition the minimum distance distance Cubic 0.100 0.000 0.0007 0.0000 Tetragonal 0.100 0.000 0.0008 0.0000 Hexagonal 1.001 1.001 0.0008 0.0003 Trigonal 0.480 0.480 0.0007 0.0002 Orthorhombic 0.100 0.000 0.0010 0.0001 Monoclinic 1.870 0.751 0.0007 0.0003 Triclinic 0.110 0.107 0.0005 0.0002 Comparing the results of the first and second columns with the Hausdorff metric and the third and the fourth columns with the metric of quaternion signals of Table 1, we can be convinced that the second algorithm recovers the image more accurately than the first one. Both metrics generally show a lower value for the case of the second algorithm. This means that the image recovered by the second algorithm is more similar to the reference image. 295 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… The results of the research The studies have shown that the algorithm based on the minimization of the distance more accurately reconstructs the lattice structure than the algorithm based on the partitioning grid line. The reconstruction algorithms can be used for recovering three-dimensional models of crystal lattices. Modifications in the recovery procedures in some cases can increase the accuracy of the reconstruction of the object. Thus, the algorithms that operate with sets of sites work better than the algorithms that resort to approximations. Acknowledgements This work was partially supported by the Ministry of education and science of the Russian Federation in the framework of the implementation of the Program of increasing the competitiveness of SSAU among the world’s leading scientific and educational centers for 2013-2020 years; by the Russian Foundation for Basic Research grants (# 14-01-00369-a, # 14-07-97040-p_ povolzh'e_a, # 15-29-03823, # 15-29-07077); by the ONIT RAS program # 6 “Bioinformatics, modern information technologies and mathematical methods in medicine” 2015. References. 1. Kharitonov SI, Volotovskiy SG, Khonina SN, Kazanskiy NL. A differential method for calculating x-ray diffraction by crystals: scalar theory. Computer Optics, 2015; 39(4): 469-479. [in Russian] 2. Kotov AP, Fursov VA, Goshin YeV. Technology for fast 3d-scene reconstruction from stereo images. Computer Optics, 2015; 39(4): 600-605. [in Russian] 3. Fursov VA, Goshin YeV. Information technology for digital terrain model reconstruction from stereo images. Computer Optics, 2014; 38(2): 335-342. [in Russian] 4. Bessmeltsev VP, Bulushev ED. Fast image registration algorithm for automated inspection of laser micromachining. Computer Optics, 2014; 38(2): 343-350. [in Russian] 5. Kudinov IA, Pavlov OV, Kholopov IS. Implementation of an algorithm for determining the spatial coordinates and the angular orientation of an object based on reference marks, using information from a single camera. Computer Optics, 2015; 39(3): 413-419. [in Russian] 6. Rad LB, Feng H, Ye J, Pease RFW. Computational scanning electron microscopy. Proceedings of the 2013 international conference on frontiers of characterization and metrology for nanoelectronics, 2007; 512-517. 7. Frank J. Electron tomography. Albany: Springer Science+Business Media, 2006; 455 p. 8. Kupriyanov AV, Soifer VA. On the observability of the crystal lattice with the images of their projections. Computer Optics, 2012; 36(2): 249-256. [in Russian] 9. Egorov-Tismenko YuK. Crystallography and crystal chemistry. Moscow: KDU, 2005; 592 p. [in Russian] 10. Kupriyanov AV, Kirsh DV. Estimating the similarity measure of crystal lattices by coordinates of their nodes in three-dimensional space. Computer Optics, 2012; 36(4): 590- 595. [in Russian] 11. Shirokanev AS, Kupriyanov AV. Development methods of reconstruction of three- dimensional crystal lattice from images of projections. Advanced Information 296 Information Technology and Nanotechnology (ITNT-2015) Image Processing and Geoinformatics Shirokanev A.S., Kirsh D.V., Kupriyanov A.V… Technologies and Scientific Computing (PIT 2015), Proceedings of the International Scientific Conference. Samara Scientific Center of RAS, 2015; 2: 334-337. [in Russian] 12. Kronover RM. Fractals and chaos in dynamical systems. Fundamentals of the theory. Moscow: Postmarket, 2000; 92-94. [in Russian] 13. Rozhentsov AA, Bayev AA, Naumov AS. Estimation of parameters and recognition of images of three-dimensional objects with disordered readouts. Journal of Mari State Technical University. Radio engineering and information and communication systems, 2010; 2(1): 57-69. [in Russian] 297 Information Technology and Nanotechnology (ITNT-2015)