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.
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: I0 , J0 , K0 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 (
The condition (
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”.
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].
(
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 (
1 0 0
1 x A 0 0 x C ,C . (
The basic logic of the algorithm can be described in the form of the equation (
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 (
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 (
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.
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 (
nоп 2 n, nоп 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.
(
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.
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
Rn . Hausdorff distance between E and F will be determined by the formula (
xX yY
To compute the Hausdorff metric for finite sets, it is sufficient to run a
computation by the formula (
H E, F maxd E, F , d F, E , where d E, F max min d xi , y j .
i:xiE j:y jF
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]. m0
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 (
M 1
amam*(э) . (
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.
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.
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). 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.
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.
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.