=Paper=
{{Paper
|id=Vol-1490/paper35
|storemode=property
|title=Researching methods of reconstruction of three-dimensional crystal lattice from images of projections
|pdfUrl=https://ceur-ws.org/Vol-1490/paper35.pdf
|volume=Vol-1490
}}
==Researching methods of reconstruction of three-dimensional crystal lattice from images of projections==
https://ceur-ws.org/Vol-1490/paper35.pdf
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 .
xX yY
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)
m0
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)