Ultramicroscopy 128 (2013) 42–54
Contents lists available at SciVerse ScienceDirect
Ultramicroscopy
journal homepage: www.elsevier.com/locate/ultramic
Geometric reconstruction methods for electron tomography AndreasAlpersa,n,RichardJ.Gardnerb,StefanKo ̈niga,RobertS.Penningtonc,1,ChrisB.Boothroydd,
Lothar Houben d, Rafal E. Dunin-Borkowski d, Kees Joost Batenburg e
a Zentrum Mathematik, Technische Universita ̈t Mu ̈nchen, D-85747 Garching bei Mu ̈nchen, Germany
b Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA
c Center for Electron Nanoscopy, Technical University of Denmark, DK-2800 Kongens Lyngby, Denmark
d Ernst Ruska-Centre for Microscopy and Spectroscopy with Electrons and Peter Gru ̈nberg Institute, Forschungszentrum Ju ̈lich, D-52425 Ju ̈lich, Germany
e Centrum Wiskunde & Informatica, NL-1098XG, Amsterdam, The Netherlands and Vision Lab, Department of Physics, University of Antwerp, B-2610 Wilrijk, Belgium
article info
Article history:
Received 25 May 2012
Received in revised form
7 January 2013
Accepted 19 January 2013 Available online 1 February 2013
Keywords:
Electron tomography Reconstruction algorithms Convexity
Homogeneity
InAs nanowires
1. Introduction
Missing wedge artefacts and non-linear projection intensities due to diffraction effects are known to cause severe difficulties in electron tomography (ET) reconstructions obtained by standard methods. This has been reported, e.g., in [1–8]. Nevertheless, standard methods, such as filtered backprojection, algebraic reconstruction techniques, and simultaneous iterative reconstruc- tion techniques [9,10], are still widely used due to an apparent lack of alternatives [11,12].
However, alternatives exist in the mathematical literature. Geometric tomography [13], for instance, is concerned in part with the tomographic reconstruction of homogeneous (i.e., geometric) objects. Similarly, discrete tomography [14,15] usually deals with objects for which atomicity is a constraint or objects that exhibit a small number of attenuation coefficients. In many applications, certain prior knowledge about the shape of the structure of interest is available. For example, when reconstructing nanorods,
n Corresponding author. Tel.: þ49 89 289 16866.
E-mail addresses: alpers@ma.tum.de, awalpers@yahoo.de (A. Alpers),
Richard.Gardner@wwu.edu (R.J. Gardner), koenig@ma.tum.de (S. Ko ̈nig), robert.pennington@uni-ulm.de (R.S. Pennington),
ChrisBoothroyd@cantab.net (C.B. Boothroyd), l.houben@fz-juelich.de (L. Houben), rdb@fz-juelich.de (R.E. Dunin-Borkowski),
Joost.Batenburg@cwi.nl (K. Joost Batenburg).
1 Now at: Institut fu ̈r Experimentelle Physik, Universita ̈t Ulm, D-89081 Ulm,
Germany.
0304-3991/$ – see front matter & 2013 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.ultramic.2013.01.002
abstract
Electron tomography is becoming an increasingly important tool in materials science for studying the three-dimensional morphologies and chemical compositions of nanostructures. The image quality obtained by many current algorithms is seriously affected by the problems of missing wedge artefacts and non-linear projection intensities due to diffraction effects. The former refers to the fact that data cannot be acquired over the full 1801 tilt range; the latter implies that for some orientations, crystalline structures can show strong contrast changes. To overcome these problems we introduce and discuss several algorithms from the mathematical fields of geometric and discrete tomography. The algorithms incorporate geometric prior knowledge (mainly convexity and homogeneity), which also in principle considerably reduces the number of tilt angles required. Results are discussed for the reconstruction of an InAs nanowire.
& 2013 Elsevier B.V. All rights reserved.
nanowires or certain types of nanoparticles, one can typically assume that the structures are convex. (A subset K of points in the plane is convex if for any two points in K the line segment join- ing these two points lies completely within K; see Fig. 2.) In particular, in our experimental application of reconstructing an InAs nanowire from high-angle annular dark-field scanning transmission electron microscopy (HAADF STEM) data, it is known that the object is comprised of cross-sections that are mostly close to regular hexagons; see [16,17].
Here we demonstrate the use of geometric prior knowledge to overcome the problems of missing wedge and non-linear projec- tion intensities due to diffraction effects by introducing four algorithms. For now, we use their abbreviated names; they are introduced in the next section. One of the algorithms (2n-GON) appears here for the first time and uses the strongest geometric prior knowledge available in our setup, namely that the slices contain nearly regular hexagons. Two algorithms, GKXR and MPW, are introduced here for the first time in the ET context and another algorithm (DART) is applied here for the first time to the reconstruction of a nanowire. As a fifth method, we discuss the BART algorithm, which was introduced in the 1970s and performs very well on homogeneous objects. BART has been implemented in the open-source software SNARK09 [18] and we provide commands and parameters that yield high quality reconstructions in our context.
The idea of using geometric prior knowledge in ET appears already in [19,20]. In particular, [20] is, to the best of our knowledge, the only paper in ET that discusses geometric 2D
slice-by-slice reconstruction methods, all of which are variants of the unfiltered backprojection (U-FBP) algorithm. Our work takes these investigations a step further and introduces alternative reconstruction methods, some of which are mathematically proven to converge towards the solution as the number of noisy measurements tends to infinity. We compare these methods (including U-FBP and the standard method SIRT as sixth and seventh algorithms, respectively) and show that these methods perform differently depending on the experimental setup and type of noise present in the data.
The geometric reconstruction algorithms use prior knowledge to address the problem of the missing wedge and non-linear projection intensities. We show that reconstructions that are accurate (mean of the reconstructions is close to the true object) and precise (reconstructions have small variance) can be obtained by using data from considerably fewer tilt angles than in conven- tional tomography. This has practical consequences, because rapid data acquisition allows time resolved studies and imaging of beam-sensitive samples.
As already mentioned, we investigate here only the use of geometric prior knowledge. Other types of prior knowledge might be related to the sparsity of the signal that represents the image gradient [21,22], or it might be assumed that the object is a realization of a random process with a given probability distribu- tion [23,24]. For further applications of special-purpose recon- struction methods in a crystallographic context, see [15,23,25,26].
2. Algorithms
In this section we briefly describe the simultaneous iterative reconstruction technique (SIRT), the binary algebraic reconstruc- tion technique (BART), the discrete algebraic reconstruction tech- nique (DART), the Gardner–Kiderlen X-ray (GKXR) algorithm, unfiltered backprojection (U-FBP), the modified Prince–Willsky algorithm (MPW), and 2n-GON. Further details on SIRT, BART, DART, GKXR, and MPW can be found in [20,27–31]. Our results are based on Matlab implementations of these algorithms; BART is part of the open-source software SNARK09 [18].
We consider only 2D versions of each algorithm, so that 3D reconstructions are obtained by 2D slice-by-slice reconstructions. Alternative reconstruction principles exist. For 3D and 2.5D approaches employing generalized Kaiser–Bessel window func- tions (blobs) for not necessarily homogeneous or convex objects, see [32,33]. We assume in this paper an acquisition geometry with a single tilt axis and a limited angular range.
The algorithms require different input data. While SIRT, BART, DART, and GKXR take the projections as input, only the shadows are used in U-FBP, MPW, and 2n-GON. Note that following (non- mathematical) standard convention, projection refers to the mea- sured intensity data (i.e., line integrals), while shadow denotes their support (i.e., the detector pixel locations that record non- zero intensities). It can therefore be expected that U-FBP, MPW, and 2n-GON are rather insensitive to intensity-affecting noise if the signal can still be distinguished from the background. Also note that the object’s shadows represent binary data, which initially need to be extracted from the projection data. In this paper we achieve this by applying a suitable threshold and filter to the projection data; see Sections 3.2 and 4.2. For more advanced variants, such as edge enhancement, see [20].
Another difference between the algorithms is that they use different types of prior knowledge. Most of the algorithms exploit the object’s convexity or homogeneity. However, 2n-GON uses the additional assumption that the object is nearly a regular 2n- gon. A summary is given in Table 1.
Table 1
Overview of algorithms.
Algorithm Tomographic data
Projection Shadow Convexity
SIRT | – – BART | – – DART | – – GKXR | – | U-FBP – | | MPW – | | 2n-GON – | |
2.1. Pixel-based reconstruction methods
A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
43
Prior knowledge
Other
–
Homogeneity Homogeneity Homogeneity Homogeneity Homogeneity
Close to a regular 2n-gon
The first three methods discussed in this paper aim to reconstruct the individual pixel values of an image representing the object.
2.1.1. Simultaneous iterative reconstruction technique (SIRT)
In this paper we describe and employ an additive variant of SIRT [10, Section 7]. The additive SIRT algorithm (from now on referred to as the SIRT algorithm) is a standard technique for reconstructing grayscale images from tomographic data. When reconstructing homogeneous objects, an additional segmentation step is required that yields a binary image. We recall that SIRT is an iterative reconstruction algorithm that computes an approx- imate solution of the linear system Ax1⁄4b, where the vector xARn contains the gray level (also referred to as pixel value) for each pixel, the vector b A Rm contains the measured projection data, and the matrix A 1⁄4 ðaij Þ A Rmn represents the projection operation (i.e., computing the product Ax yields the projections correspond- ing to the image x). If no exact solution of this system exists, SIRT computes a solution for which the norm of the difference JAxbJ (referred to as projection error) between the computed projection and the measured data is minimal with respect to a weighted L2 norm, i.e., a weighted least-squares solution (see [27,34] for details). In contrast to other popular iterative algorithms, such as ART (algebraic reconstruction technique [9, Chapter 11]), the SIRT algorithm computes the projections for all angles in each iteration. Then the difference between these projections and the measured projection data is computed. Subsequently, each image pixel value is updated by adding a weighted average of the projection difference for all lines that intersect this pixel. In other words:
xðk þ 1Þ 1⁄4 xðkÞ lCAT DðAxðkÞ bÞ,
where C 1⁄4 diagð1=c , …,1=cnÞARnn
with
D1⁄4diag ð1=d1,…,1=dmÞARmm with di 1⁄4 nj 1⁄4 1 aij; the para-
and meter lAR is the relaxation parameter of the algorithm (for
1
our particular choice, see Sections 3.2 and 4.2).
2.1.2. Binary algebraic reconstruction technique (BART)
The BART algorithm was introduced by Herman [28]. Along with other methods, BART is implemented in the open-source software SNARK09 [18]. The general idea is to enforce binary constraints on the solution x during the iterations of a chosen ART routine. In a second step, the solution is filtered to exclude isolated pixels. A complete code that can be read into SNARK09 (either manually or as an input file) to obtain the BART recon- structions discussed in this paper is provided in Appendix A (Table A1).
c 1⁄4 Pm a Pj i1⁄41 ij
44 A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
2.1.3. Discrete algebraic reconstruction technique (DART)
The DART algorithm, which has recently been proposed as a reconstruction algorithm for electron tomography [26,29] is another algebraic method, in which a set of fixed pixels is updated in each iteration, reflecting the position of the boun- dary in the current reconstruction. The variant described here does not apply any subsequent filtering. For simplicity, we describe the DART algorithm for the specific purpose of recon- structing a binary image. The general algorithm can deal with more than two gray levels. More on DART can be found in [35–38].
Here, we focus on reconstructing a single object of homo- geneous composition, resulting in a binary image reconstruction problem. The DART algorithm uses a continuous algebraic recon- struction method, such as SIRT, as a subroutine. From this point on, we will refer to this continuous method as the algebraic reconstruction method (ARM). After an initial gray level recon- struction has been computed using the ARM, this gray level reconstruction is segmented by global thresholding with thresh- old r=2, where the gray level r of the object is assumed to be prior knowledge. In practice, an appropriate value of r can often be obtained by first computing a SIRT reconstruction and then taking the average gray level over a region deeply in the interior of the object. One of the principal assumptions behind the DART algorithm is that errors in this segmentation are typically located near the boundary of the structure of interest. Indeed, when reconstructing a homogeneous object that is large with respect to the image pixel size, pixels that are deeply inside the interior of the object (e.g., a nanoparticle) are usually segmented correctly, while the segmentation of the boundary can be highly inaccurate, in particular when the ARM reconstruction suffers from missing wedge artefacts. The boundary can be computed from the initial segmentation as the set of pixels for which not all neighboring pixels belong to the same segmentation class. After the segmen- tation step, the set of pixels is separated into three subsets: the interior pixels I, the background pixels B, and the boundary pixels F. Prior knowledge about the gray level r of the object and of the gray level of the background (here assumed to be 0) is now incorporated by solving the following constrained reconstruction problem, again using the ARM:
solve Ax 1⁄4 b, subject to
xi1⁄40 foriAB, xi1⁄4r foriAI:
In this reconstruction problem, all interior pixels and background pixels are fixed to their respective gray levels and pixel values are only allowed to change for boundary pixels. This constraint strongly reduces the number of unknowns in the equation system, while the number of equations (i.e., the number of entries in b) remains unaltered. If the initial segmentation is of sufficient quality, the reconstruction of the boundary will significantly improve compared to the initial ARM reconstruction.
The resulting reconstruction is again segmented, resulting in a new partition of the image into interior, background, and bound- ary pixels. As new pixels can be added to the boundary, pixels whose values were fixed in the previous step can now become boundary pixels and vice versa. The procedure of alternating segmentation and reconstruction steps is then iterated until a pre-defined convergence criterion is reached.
A well-known limitation of DART is that the result can depend sensitively on the choice of gray levels and this choice may not be correct based on the first SIRT iterations. Sophisticated algorithms for choosing the correct gray levels can be found in [39,40].
2.2. Object-based reconstruction methods
The second category of reconstruction methods that we con- sider in this paper is object based in the sense that the routines aim to determine a small number of parameters that completely describe the object (in our case, the vertices of polytopes).
2.2.1. Gardner-Kiderlen X-ray (GKXR)
The Gardner–Kiderlen X-ray algorithm [30] is a recent devel- opment from the field of geometric tomography. It arose from theoretical work [41] in which it was shown that there are certain sets of four directions in 2D such that the exact projections of a 2D convex object in these directions determine it uniquely among all 2D convex shapes. For example, directions specified by the four vectors (0,1), (1,0), (2,1), and (1,2) constitute such a set [42]. The GKXR algorithm is based on the simple observation that given a sufficiently dense set of lines meeting a convex set K, the convex hull of all the points at which the lines intersect the boundary of K will form a convex polygon that approximates K well. The algorithm attempts to find this polygon for the set of projection measurement lines.
Fig. 1 shows a schematic diagram of the basis of the algorithm. The unknown object is the oval K, assumed to lie inside the circle. For clarity, only a single projection, taken in the direction u, is considered in Fig. 1, although in practice projections in four different directions are used. For each projection direction u, detector pixels are located at the equally spaced points t1,…,tk on the axis in the orthogonal direction v. The dotted lines through these points represent measurement lines. A pair of points (in Fig. 1, one red and one blue, shown in purple if they coincide; for interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.) is placed randomly on each of the 4k measurement lines. Since the geometry of the measurement lines is known, the position of each point can be described by a single real variable giving the location of the point on the measurement line. Therefore the position of all of the points can be described by a single vector variable z with 8k real components.
An initial guess for K is obtained by forming the convex hull of all 8k points, except those for which a pair coincides, i.e., the purple points. This is the convex polygon labeled P1⁄2z in Fig. 1. The convex hull is computed using a standard algorithm as a sub- routine. The reason for ignoring the purple points in taking the convex hull is that if a measurement line does not meet K, there must be some mechanism to eliminate the pair of points that lies on that line. In practice, a threshold is set so that a pair of points is
Fig. 1. Illustration showing the basic principles behind the GKXR algorithm.
A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54 45
Fig. 2. Left to right: A convex set K in the plane; a set L which is not convex; the support function of K in one direction u; support function values in many directions describing the convex set K.
Fig. 3. Left: A convex set K and three exact measurements of its support function. Middle: An incorrect support function measurement leading to inconsistent data. Right: An incorrect support function measurement cutting away a big part of K.
eliminated if they become too close in the iterative optimization procedure to be described next.
In order to improve the initial guess, the positions of the pairs of points on the measurement lines must be adjusted. This is effected by computing the sum, over all measurement lines, of the squares of the differences between the measured projection value for K and the corresponding projection value of P1⁄2z. This least squares sum is the objective function in an optimization problem with 8k real variables and an optimization routine is used to drive the value of the objective function down to a minimum. The output of the algorithm is the convex polygon Pk 1⁄4 P1⁄2z corre- sponding to the optimal vector z of these real variables.
In [30] it is shown that for any finite set of directions for which the corresponding exact projections determine a convex object uniquely, the output Pk converges to K as k-1, even when the measurements are affected by Gaussian noise of fixed variance. Moreover, this remains true even if the optimization problem is not solved exactly, but only within an error ek 40, provided ek-0 as k-1; see [30, p. 337]. In practice, the optimization problem involved is heavily non-linear. The fmincon function from Matlab’s Optimization Toolbox was used, along with simulated annealing to improve performance.
2.2.2. Unfiltered backprojection (U-FBP)
U-FBP, as described here, can be viewed as a geometric method. The idea is to backproject the object’s shadows (yielding a strip for each shadow) and to return the intersection of all of these strips. The returned object is then necessarily a convex polygon. This, in general, cannot be guaranteed for other common U-FBP variants that backproject projections instead of shadows.
2.2.3. Modified Prince–Willsky (MPW)
The modified Prince–Willsky algorithm [31], a modification of the algorithm in [43], reconstructs a convex object K from its support function hK. The function hK takes a direction (unit vector u) as input and returns a number that corresponds to the extent of K in direction u. To be precise
hK ðuÞ 1⁄4 max uT x, xAK
where uTx denotes the inner product of u and x.
Fig. 2 also indicates that K is completely determined by its
support function values in all directions (this can be shown mathematically; see [13, Section 0.6]). Good approximations can
already be obtained using a finite number of (suitably chosen) directions.
The support function values of K in the two directions perpendicular to the projection direction can be easily deter- mined from the data, because they correspond to the minimal (respectively, maximal) coordinates of the pixels in the data that record non-zero intensities. As data are available for many tilt angles, support function measurements are collected for different u vectors. These serve as input to the algorithm.
So far, the algorithm is very similar to U-FBP. However, U-FBP tries to find an object that fits the noisy measurements perfectly. As with most inverse problems, this is usually not the best strategy. Fig. 3 illustrates the fact that noise may lead to incon- sistencies in the data.
The MPW algorithm is designed to deal with noise. More precisely, for (Gaussian) noise affected measurements h1, . . . ,hn of the support function of K in a finite number of directions u1,…,un, the MPW algorithm solves a (linearly) constrained least-squares problem to obtain values y1,…,yn, which are the support function values of the best-approximating set Kn.
With mild restrictions, the output of the algorithm converges as the number of shadows, affected by Gaussian noise of fixed variance, approaches infinity [44]. The implementation of MPW is somewhat more demanding than U-FBP, because a subroutine for solving quadratic programs is required (we use the Xpress solver). The set Kn, in our implementation, is obtained as an intersection of halfspaces Kn 1⁄4 Tni 1⁄4 1fx : uTi xryig via U-FBP. Additional MPW variants are discussed in [31].
2.2.4. 2n-GON
Again, shadows are taken as input data. We aim to reconstruct an object K that is known to be close to a regular 2n-gon, where nZ3 is known in advance. (In our experimental application, n1⁄43.) If the assumptions are not fulfilled then the algorithm should exit without reconstruction.
The length of the shadow of K for a given tilt angle y is commonly referred to as the width of K orthogonal to y. Of course, this quantity can easily be computed from the input data. It is easy to see that if K is a regular 2n-gon, then the width of K, as a function of yA1⁄201,1801Þ, has exactly n local minima, correspond- ing to the tilt angles that project K along an edge direction of K. These n minima are thus (180/n)1 apart and if they can be determined, then unfiltered backprojection (as implemented in U-FBP) from the corresponding n directions yields the regular
46 A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
2n-gon K. Note that the shadows from two such edge directions of a regular 2n-gon K determine the minimum width and center of K and hence K itself. Also note that two such shadows are typically available from the data, because standard electron microscopes allow [01,1201) tilt ranges.
The procedure also works when K is only close to a regular 2n-gon, as follows. Again, the idea is to apply unfiltered back- projection for the directions orthogonal to the tilt angles deter- mined by some n minima of the width function of K that are only approximately (180/n)1 apart. As before, some of the data for edge projecting directions might not be available if the data are not acquired over the full [01,1801) tilt range. If this is the case, then one needs to impose some assumptions on the missing data; see Fig. 4(a), in which the hexagon and the parallelogram are indis- tinguishable from data in the (very limited) [01,701) tilt range shown. Another limitation of the 2n-GON approach is that we need to assume that the noise level in the (shadow) data is sufficiently low to allow determination of the minima of the width function.
Here is a precise description of our implementation. We assume that data are available over a 1⁄201,o1Þ tilt range, where o is fixed (typically o 140). We initially determine the local minima in 1⁄201,o1Þ of a polynomial curve of degree at least kZ2n that best fits (in the least-squares sense) the measured widths. We found in simulations that values of k around 2nþ5 give good and stable results. Fig. 4(b) shows measured widths of a hexagon together with its best fitting polynomial curve.
Suppose there are m Z 2 minima t1 r t2 r r tm , in degrees, within the 1⁄201,o1Þ range (otherwise, we stop without reconstruc- tion). Unfiltered backprojection from S1⁄4ft1,…,tmg yields a (pos- sibly degenerate) 2m-gon, which, for o 1⁄4 180, approximates K. If oo180, we proceed as follows. Let
R1⁄4fiAf1,…,m1g : 180=n10r9tiþ1ti9r180=nþ10g:
If R 1⁄4 |, we stop without reconstruction. If 9R9 1⁄4 n1, we recon- struct from the angles in R. Otherwise, 1 r 9R9 1⁄4 r o n1 and we define a1⁄4maxfRg, b1⁄4aþ1, and T 1⁄4ft01,…,t0nrg, where t0i 1⁄4tbþ180i=n, i1⁄41,…,nr. If there is an angle in T that is not in the [01,1801) range, we exit without reconstruction. Otherwise, we reconstruct from S [ T. Here if t0i is outside the tilt range, we use unfiltered backprojection of the shadows for the angles ta and tb to obtain a parallelogram and set the shadow for t0i to be equal in length to that for tb, using the center of the parallelogram to position it correctly.
We remark that this implementation reduces in the regular 2n-gon case to the method described at the beginning of this subsection. Note that 2n-gon can also be applied to data from a
small number of tilt angles, since the best fitting polynomial curve may still approximate the local minima, although these minima might not be present in the data. We test this, among other things, in the next two sections. A theoretical analysis, however, remains outside the scope of this paper, as tolerable deviations from a regular 2n-gon depend on several parameters such as the relative position of the missing wedge, the amount of noise in the data, the number of available projections, and the diameter of the 2n-gon.
It is worth mentioning that as well as measuring widths orthogonal to y, we can also measure widths parallel to y, provided that projection data (and not only shadows) are avail- able. We shall not discuss the performance of this variant here.
3. Experimental application
We consider the task of reconstructing a nanowire from HAADF STEM data. Nanowires, small wires that are tens of nanometers in diameter and micrometers in length, are promising building blocks for future electronic and optical devices; see [45,46]. They are typically grown from a substrate and much research effort is being focused on understanding and controlling their growth mechanisms [16]. Electron tomography, as in var- ious materials science applications, is rapidly developing into a powerful 3D imaging tool for studying these effects at the nanoscale [47,48].
With current technology, the tomographic data acquisition time for 140 projections of a single nanowire is about 2 h when performed manually. This is currently a bottleneck preventing many in situ experiments on short time scales and the imaging of multiple nanowires. Automated acquisition can lower this time, but a further reduction, which could be achieved if the required number of tilt angles can be reduced, is of paramount importance. Computation times for the reconstruction of a single 512512 slice range from a few seconds to 3min (for GKXR) on a standard PC.
The particular nanowire in our experimental application is grown from pure InAs. Such nanowires are usually convex, or nearly so, in cross-sections perpendicular to the growth direction. In fact, most of these cross-sections for InAs nanowires are close to regular hexagons [17].
3.1. Experiment
An HAADF STEM image series of an InAs nanowire was acquired using a probe-aberration-corrected FEI Titan 80–300 microscope operated at 300kV with a probe convergence
Fig. 4. (a) A regular hexagon (lightly shaded) and the parallelogram determined by width data from angles indicated by the arrows; (b) measured width as obtained from the HAADF STEM data (red) and best fitting (in the least-squares sense) polynomial curve of degree 11 (black). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
semi-angle of 18mrad and an inner detector semi-angle of 100 mrad. The images were acquired over a total angular range of 1391 with a 11 tilt increment. The original 2048 2048 pixel images, representing the projections for 2048 slices, were then binned by a factor of 4 to reduce noise in the reconstruction. The resolution after binning corresponds to a pixel size of 0.84 nm
0.84 nm.
Fig. 5(a–c) shows a bright-field transmission electron micro-
scopy (TEM) image and two HAADF STEM images, respectively, of the InAs nanowire specimen. An effect of non-linear projection intensities within a particular slice is visible in Fig. 5(d,e), as the measured projections (red graphs) do not exactly match the projections of the best-fitting shapes of the nanowire for this slice (black graphs). Twinning in the growth direction produces the ‘‘bee stripe’’ patterns visible in Fig. 5(b,c).
3.2. Parameters for the algorithms
The relaxation parameter l for SIRT and DART was set to 1. The SIRT algorithm was run for 50 iterations, based directly on the measured intensity values in the projection data. Afterwards, the reconstruction was thresholded at a value of 0.5, where 0 repre- sents the background and 1 represents the gray level of the nanowire. Each run of the DART algorithm consisted of 25 SIRT iterations to compute the starting solution, followed by 25 DART iterations, each of which included 10 SIRT iterations on the set of free pixels (i.e., the pixels near the boundary). The SIRT iterations within each DART iteration only take a fraction of the time of a complete SIRT iteration, as they are only applied to the free pixels. As for SIRT, DART employs a threshold at 0.5. A fixed fraction of 0.85 was used, meaning that 85% of all non-boundary pixels (selected randomly) are kept fixed in each DART step; the fixed fraction can be adapted to a specific noise level for more accurate results. We refer to [29] for details.
The BART parameters, along with the code, are provided in Appendix A, Table A1.
For reconstructions with GKXR, the projection in each direc- tion was measured at 40 equally spaced positions along an axis orthogonal to the direction and passing through the center of a
circular window known to contain the object to be reconstructed (i.e., k1⁄440 in Fig. 1). Simulated annealing was used, with a fixed cooling schedule. The projection data was pre-processed by a simple smoothing algorithm from digital signal processing, an averaging filter based on the IIR (infinite impulse response) design (see, for example, [49, Chapter 8]). More specifically, if the non-zero 512 projection measurements for a certain direction are y1,…,ym, a smoothed set of measurements y01,…,y0m is produced by recursively defining
y0i 1⁄4 ðyi þ y0i1 Þ=2
for i 1⁄4 1, . . . ,m, where we set y0 1⁄4 0. This smoothing procedure was iterated 50 times to obtain the smoothed data for input into the algorithm.
The algorithms U-FBP, MPW, and 2n-GON require shadows as input. Let My denote the 512 512 matrix containing (row-wise) the projections of the nanowire slices for viewing angle y. For this particular data set, we binarize the median filtered My (with a 1 3 window) using threshold T 1⁄4 0, which is followed by a morphological opening [50, Chapter 15] with Matlab’s structuring element strel(’diamond’, 2). This morphological opening takes neighboring slices into account; the reconstruction of the object, however, proceeds slice by slice.
3.3. Experimental results
A full discussion of our results is only possible in connection with the simulations presented in the next section, particularly because there are no data for this nanowire obtained by an independent imaging method. However, we can make some general remarks.
(i) It appears that the nanowire consists of two parts, the top part slightly narrower and rotated by about 301 around the axis of the bottom part. The bottom part seems to consist of alternating twins, each around 40 nm thick, while one twin orientation dominates the top 80 nm. Except for the twinning (much less visible in GKXR and 2n-GON), these structures can
A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54 47
1 0.8 0.6 0.4 0.2 0
e1 0.8 0.6 0.4 0.2 0
0 20 40 60 80 100120140160
Position in profile (nm)
Fig. 5. Nanowire data: (a) bright-field TEM image of the InAs nanowire specimen used for tomography; (b,c) aligned binned HAADF STEM images taken from the tilt series of the wire at angles of 101 and 401, respectively (slice 220 is indicated by the white line; the tilt axis is in the vertical direction through the center of the image); (d,e) measured projections of slice 220 (non-linear projection intensities) shown in red and ideal projections of slice 220 (linear projection intensities) shown in black, at angles of 101 and 401, respectively. (The ideal projections were estimated from our reconstructions.) (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
0 20 40 60 80 100120140160
Position in profile (nm)
Intensity (scaled) Intensity (scaled)
48 A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
Fig. 6. Reconstruction of the nanowire using different algorithms. Top-to-bottom and frontal views are shown in the first and second row, respectively. GKXR requires only four projections; U-FBP, MPW, and 2n-GON reconstruct from shadows. A few of the top slices of the BART reconstruction are missing, because we put no effort into recovering the correct factor that relates the line integrals and the actual measured intensities. Slices are missing in the 2n-GON reconstruction if the algorithm detects that there is no hexagon in the corresponding slice. Nanowire orientations and their top-to-bottom views might vary as the 3D viewing points for the individual images have been manually selected. The 301 rotation of the end of the wire relative to the main part is more readily discernible in the frontal views (lower row) than in the top-to-bottom views (upper row). Images have been rendered using the Amira software with the isosurface operation and the compactify option, but no explicit smoothing was applied.
be found in each of the seven reconstructions. However, the region around the frontal vertical edge of the reconstructions lies in the missing wedge and so might contain artefacts. Perhaps the most reliable indication of the presence of twinning is the fine periodic structure that appears along the left- and right-most vertical edges of the reconstructions. This periodic structure is too fine to be resolved by our current implementation of GKXR.
(ii) BART and DART, followed by SIRT, appear to give the best (most accurate and precise) results. Note, however, that the software (Amira) that renders the 3D images in Fig. 6 smooths out isolated pixels due to the surface mesh that is built into the isosurface operation. Therefore these images might look smoother than those produced by these three algorithms without this post-processing. This is not the case for the other four algorithms, because they do not return objects containing isolated pixels. An explanation for the fuzzy boundary returned by GKXR is given in Section 4.3.
(iii) It seems possible to infer useful geometric parameters about the facet structure (diameters, angles, etc.) from GKXR, U-FBP, MPW, and 2n-GON, which use fewer data (shadows or fewer projections, as appropriate). See also Section 4.4.
(iv) Algorithms U-FBP, MPW, and 2n-GON need segmentation of the shadows, while SIRT, BART, and DART need segmentation of the reconstruction. Depending on the reliability of the mea- sured intensities, one type of segmentation (possibly involving filtering and thresholding) might be favorable over another.
(v) It should be possible to improve the performance of GKXR by replacing the pre-processing via IIR with a least-squares fit to the projection data of a piecewise linear concave curve. Further improvement of the reconstruction quality of each of the presented algorithms might be achieved by incorpor- ating the fact that the slices of the object are not independent from each other. The reconstruction from GKXR, for instance, might benefit from post-processing, such as a simple aver- aging process to smooth out the differences between con- secutive slices.
4. Computer simulations
We tested the algorithms with four phantoms (i.e., simulated objects) under varying magnitudes of noise. As phantoms we used
two regular hexagons, a slightly irregular hexagon, and a regular octagon. They are shown in Fig. 7 and henceforth are referred to as Phantoms 1–4.
To compare phantoms and reconstructions we need to quantify the degree to which two shapes differ. (This is a central problem in computer vision.) Here we use two metrics that are frequently encountered in the literature, the sym- metric difference metric and the Hausdorff metric. The sym- metric difference distance between finite sets A and B of pixels (in our case, subsets of f1,…,512gf1,…,512g) is defined by
dSðA,BÞ 1⁄4 9ðA\BÞ [ ðB\AÞ9,
i.e., dSðA,BÞ counts the number of mismatching pixels. The
corresponding Hausdorff distance is defined by dH ðA,BÞ 1⁄4 maxðdðA,BÞ,dðB,AÞÞ,
where
dðA,BÞ 1⁄4 max minJabJ1 1⁄4
aAA bAB
and 9 9 denotes the usual absolute value of a real number. (We chose the L1 norm for computational convenience; other choices are possible.) In other words, for dðA,BÞ we identify the pixel aAA that is farthest from any pixel in B and return the distance from a to its nearest neighbor in B. Taking the maximum of dðA,BÞ and dðB,AÞ makes dH symmetric in its arguments. Thus, roughly speaking, dHðA,BÞ measures the extent to which each pixel of A lies near some pixel of B and vice versa.
Now, let P denote the set of pixels of a phantom and R the set of pixels of a reconstruction. We refer to dSðP,RÞ and dHðP,RÞ, or dS and dH for short, as reconstruction errors (measured in the symmetric difference metric and Hausdorff metric, respectively).
The Hausdorff and symmetric difference metrics have different and somewhat complementary characters. While the Hausdorff metric is sensitive to single pixel outliers but robust to boundary perturbations, the symmetric difference metric is robust to single pixel outliers but sensitive to boundary perturbations (cf. Fig. 7, particularly the DART reconstructions). However, as for any metric, two sets are equal if and only if they have zero distance.
max
ða1,a2ÞAA ðb1,b2ÞAB
maxð9a1b19,9a2b29Þ
min
A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54 49
Fig. 7. Phantoms and reconstructions I. Column 1: Phantoms 1–4 (from top to bottom). Subsequent columns show difference images between a phantom and a typical reconstruction with S140,10 at 50-noise obtained by SIRT (Column 2), BART (Column 3), DART (Column 4), GKXR (Column 5), U-FBP (Column 6), MPW (Column 7), and 2n-GON (Column 8). Color scheme for difference images: White pixels belong to the phantom (P) and the reconstruction (R), red pixels to R\P, and blue pixels to P\R. These are 192 192 pixel images in which the 160 pixel boundary has been cropped. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
Fig. 8. Simulation results presented as mean reconstruction errors measured in the symmetric difference metric: (a) S180,1, (b) S140,1, (c) S180,10, (d) S140,10. Bar colors indicate noise level, green for 0- and yellow for 50-noise. Black error bars represent standard deviation. GKXR requires only four projections; U-FBP, MPW, and 2n-GON reconstruct from shadows. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
50 A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
Fig. 9. Simulation results presented as mean reconstruction errors measured in the Hausdorff metric: (a) S180,1, (b) S140,1, (c) S180,10, (d) S140,10. Bar colors indicate noise level, green for 0- and yellow for 50-noise. Black error bars represent standard deviation. GKXR requires only four projections; U-FBP, MPW, and 2n-GON reconstruct from shadows. (For clarity, we do not show the bars of the SIRT and DART results for S140,10 with 50-noise if they extend beyond the value 15; their actual values range between 20 and 160.) (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
4.1. Data generation
To avoid the ‘‘inverse crime’’ [51, Section 5.3] of using the same model for generating the data for testing the algorithms as the one used in their design, we generate the projections from higher resolution versions of the phantoms (cf. [52,53]). More specifically, from 2048 2048 pixel versions of the phantoms we generate the projections and bin them by a factor of 4. We thus aim at reconstructing the 512 512 pixel versions of the phan- toms as shown in Fig. 7. No further scaling of the projection values is introduced, i.e., the projection values give the number of pixels of the phantom that lie on the corresponding line. (Our implementation employs the Matlab command imrotate using the bilinear and crop option.) Comparing our results to those obtained from projection data generated by SNARK09 [18], we could not find significant differences. This could be expected, because our projections (before binning) are generated from suitably high resolution phantoms. The noise model that is described next is applied to the projections generated from the high resolution phantoms.
Taking a simplistic approach, we simulate Gaussian noise. Hence, we specify noise by one parameter s. We draw indepen- dent and identically distributed zero-mean, s2-variance normal
random variables pði,jÞ for each projection angle i and projection pixel j that has non-zero intensity. The pði,jÞ’s are added to the intensities of the corresponding projection pixels; negative inten- sities are set to zero. This approach simulates additive Gaussian noise on the non-zero intensities. The underlying assumption in our noise model of adding noise only to pixels with non-negative intensities is that statistical noise effects affect the recorded signal but still allow detection of the object’s shadows. At least for our HAADF STEM data of the nanowire, this seems to be a plausible model. In our simulations we consider the 0-noise (i.e., s 1⁄4 0, noise-free) and 50-noise (s 1⁄4 50) cases. Here 50-noise seems to be in agreement with the intensity variations present in the experimental data in Section 3.
4.2. Parameters for the algorithms
For our algorithms, the parameters used for all simulations were the same as for the nanowire slice reconstruction described in Section 3.2. The pre-processing of the data was simplified in the sense that for GKXR the pre-processing procedure to smooth the data was not used in the 0-noise case and for U-FBP, MPW, and 2n-GON the input shadows were obtained directly by thresh- olding the projections with T 1⁄4 0.
A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54 51
Fig. 10. Simulation results for Phantom 2 with S140,1 including 200-noise, presented as mean reconstruction errors measured in (a) the symmetric difference metric and (b) the Hausdorff metric. Bar colors indicate noise level, green for 0-, yellow for 50-, and red for 200-noise. Black error bars represent standard deviation. GKXR requires only four projections; U-FBP, MPW, and 2n-GON reconstruct from shadows. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
4.3. Simulation results
We employed the following four sets of tilt angles: S180,1 1⁄4 f11,21,31, . . . ,1801g, S140,1 1⁄4 f11,21,31, . . . ,1401g, S180,10 1⁄4 f11,111,211, . . . ,1711g, and S140,10 1⁄4 f11,111,211, . . . ,1311g. Here a tilt angle y corresponds to a clockwise rotation of angle y around the vertical (0,1)-direction. While S140,1 corresponds to our experimental setting, we included the other sets of tilt angles to compare the performances of the algorithms with respect to the missing wedge and the total number of available tilt angles. For the main simulations reported in Figs. 8 and 9, reconstructions with GKXR were always performed using the four angles {11, 281, 911, 1181}, chosen to be nearest to a theoretically ideal set within the range 1–1401, namely angles corresponding to the vectors (0,1), (1,2), (1,0), and (2,1) (cf. Section 2.2.1).
For each algorithm, each set of tilt angles, and each noise level we performed 100 reconstructions. The mean reconstruction errors dS and dH together with their standard deviations are shown in Figs. 8 and 9, respectively.
We first discuss typical difference images of reconstructions of each phantom, shown in Columns 2–8 of Fig. 7, obtained from SIRT, BART, DART, GKXR, U-FBP, MPW, and 2n-GON with tilt angles S140,10 at 50-noise. Note that this means reconstruction from only 14 projections, 10 times fewer than is typically employed in ET (the S140,1 case). White pixels in the color scheme of our difference images correspond to correctly reconstructed pixels, red pixels belong to the reconstruction but not the phantom, and blue pixels belong to the phantom but have not been reconstructed. The reconstruction errors (dS ;dH ) for Phan- toms 1–4, respectively, are:
The fuzziness of the object boundary in the BART and, particu- larly, the DART reconstruction is a common phenomenon for pixel-based reconstruction methods that do not employ filters.
We now turn to a discussion of Figs. 8–10. We refer to 0-noise and 50-noise as moderate noise levels, while x-noise with x Z 200 is a high noise level. At high noise levels, the reconstruction quality, except perhaps for MPW and 2n-GON, becomes very poor. Therefore Figs. 8 and 9 only display results for moderate noise levels. Typical results for high noise levels are presented in Fig. 10 and discussed in (viii) below.
The simulations for S140,1 at 50-noise resemble the experi- mental conditions of the nanowire reconstruction presented in the previous section; the corresponding simulation results are depicted by the yellow bars in Figs. 8(b) and 9(b). Experimental conditions with a reduced number of tilt angles would be represented by S140,10 at 50-noise. The key inferences from the simulations can be summarized as follows.
(i) For available projections over the whole 1801 tilt range (as in the S180,1 and S180,10-case) and moderate noise levels, we find that all algorithms yield good (accurate and precise) results (usually with dH r 5 and dS r 1000).
(ii) BART, DART, and 2n-GON give the best results in the S140,1 case at moderate noise levels (the 50-noise case resembles the experimental setup).
(iii) 2n-GON performs well, even with missing wedge and few available projection directions. However, the object needs to be close to a regular 2n-gon, otherwise caution is required (see the results for Phantom 3).
(iv) In many cases, BART and DART give the best results. Particularly with DART, the quality of the reconstruction deteriorates significantly if fewer projections are available and if the noise level increases.
(v) According to the simulations, the GKXR algorithm is among the better-performing algorithms in the missing wedge case at moderate noise (see Figs. 8(d) and 9(d)) and its out- standing feature is that it requires projection data only from four directions. To test the effect of changing the four directions used, we performed the same simulations with angles {211,411,611,811}, all contained in a narrow 601 range. The results were worse, but not dramatically so. For example, for Phantom 1 at 50-noise, the mean ðdS ; dH Þ errors rose to (1,227.83;8.48), compared to (925.84;6.94) for angles {11,281,911,1181}. However, the nanowire reconstruc- tion in Fig. 6 seems the worst produced by the algorithms used. To some extent, this is due to the fuzzy nature of the boundary depicted there. In fact, while the mean and standard deviations of the errors reported for GKXR in Figs. 8(b) and 9(b) are fairly small, the distance between
SIRT: BART: DART: GKXR: U-FBP: MPW: 2n-GON:
(1,482;13) (523;3) (873;16) (693;4) (1,285;12) (1,282;12) (215;2)
(1,562;15) (513;3) (697;14) (1,174;7) (922;10) (905;10) (386;3)
(1,367;13) (1,594;16); (491;4) (494;4); (843;7) (955;8); (933;6) (670;5); (1,258;11) (1,022;10); (1,227;11) (948;10); (653;4) (146;1).
The difference images illustrate several characteristics of the different algorithms. For instance, the algorithms that are specifically designed to reconstruct from only a few directions, GKXR and 2n-GON, yield small errors, both in the symmetric difference metric and the Hausdorff metric. (Recall that GKXR uses only four projections.) On the other hand, the effect of the missing wedge can be seen in the 2n-GON and MPW recon- structions, as these algorithms reconstruct from shadows. The 2n-GON algorithm cannot fully compensate for the missing wedge, because Phantom 3 deviates from a regular structure.
52 A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
neighboring slices of the nanowire reconstruction can be significant. This is caused by the inherent stochastic nature of the algorithm, which uses simulated annealing. Possible improvements have been discussed in Section 3.2.
(vi) The problems for MPW and U-FBP are caused by the missing wedge, because data are simply missing from the shadows (see Fig. 4(a)). If essential object features do not lie in the missing wedge, then good reconstruction results can be obtained even at high noise levels. In fact, MPW is among the better-performing algorithms if data are acquired over a 1801 angular range. The U-FBP algorithm never outperforms MPW by a significant margin and in most cases the results for MPW are clearly superior to those reported for U-FBP. Inspection of the reconstructions shows that U-FBP tends to cut off the corners of the object, while MPW returns the correct shape up to a systematic overestimation. See also (viii).
(vii) SIRT is known for its noise suppressing features. It performs much better in highly limited data scenarios than transfor- mation based techniques such as filtered backprojection [10, Chapter 7]. These findings are confirmed in our simulations. To avoid overloading the figures, however, we chose not to present the corresponding poorer results for those scenarios that we obtained by filtered backprojection. While SIRT gives rather good results as measured by the Hausdorff metric for 1801 angular range (S180,1, S180,10) at moderate noise levels, we observe from Figs. 8 and 9 that the algorithm is typically outperformed by the other algorithms in the missing wedge case (S140,1, S140,10).
(viii) The reconstruction quality of all of the algorithms deterio- rates at high noise levels. Fig. 10 indicates that U-FBP, MPW, and 2n-GON seem to be less affected. (We show only results for Phantom 2 and S140,1; the other cases are similar.) This finding is somewhat expected, since these algorithms work with shadow data.
(ix) There is a notable discrepancy between the performance of 2n-GON and GKXR in the S140,1 simulations with 50-noise and their performance, much worse in the case of GKXR, in the nanowire reconstructions shown in Fig. 6. Possible reasons for this discrepancy were given in (iii) and (v). A detailed assessment, however, remains for future research.
4.4. Determination of faceting
A typical experimental aim when imaging geometric objects is to determine their faceting including minor facets and surface protrusion and roughness. Fig. 11 shows two more complex phantoms along with reconstructions obtained by SIRT, BART,
DART, GKXR, U-FBP, MPW, and 2n-GON, respectively. We refer to these as Phantoms 5 and 6; reconstructions for demonstration purposes have been performed for S140,10 at 50-noise (the data generation was described in Section 4.1).
The reconstruction errors ðdS;dHÞ for Phantoms 5 and 6 are, respectively: For SIRT, (1,501;13) and (1,742;12); for BART, (460;3) and (692;9); for DART, (842;11) and (769;14); for GKXR, (934;5) and (1,744;11); for U-FBP, (852;10) and (1,199;8); for MPW, (791;10) and (1,243;8); and for 2n-GON, (379;5), and (1,443;12).
The results in Fig. 11 can be summarized as follows.
SIRT: Minor facets of Phantom 6 are not reconstructed; the boundaries are very fuzzy; additional imaging tools for edge extraction are required to evaluate facet angles; the inner angles of the major facets are reconstructed with an accuracy of about 121.
BART: All minor facets are reconstructed; artefacts in the missing wedge region might be misclassified as minor facets; additional imaging tools for edge extraction are required to evaluate facet angles; the inner angles of the major facets are reconstructed with an accuracy of about 21.
DART: Several minor facets are reconstructed; a few minor facets in the missing wedge region are not resolved; bound- aries can be fuzzy and additional imaging tools for edge extraction are required to evaluate facet angles; assuming that only isolated pixels are removed, we find that the inner angles of the major facets are reconstructed with an accuracy of about 61.
GKXR: Few minor facets are reconstructed; the inner angles of the major facets are reconstructed with an accuracy of about 81 (cf. Fig. 7).
U-FBP and MPW: Minor facets of Phantom 6 are not recon- structed; the inner angles of the major facets outside the missing wedge are reconstructed with an accuracy of about 21; artificial major facets appear in the missing wedge of Phantom 5.
2n-GON: Minor facets of Phantom 6 and two minor facets of Phantom 5, are not reconstructed; the inner angles of the major facets are reconstructed with an accuracy of about 1.51.
These results demonstrate the potential of the geometric approach. A detailed study, however, must be left for future research, since the reconstruction quality depends on several parameters, such as the particular type of noise, the misalignment of the projections, and the relative position of the object and the missing wedge.
As a final comment, we remark that a large L2-norm of the residual Axb can be seen as an indicator that the reconstruction
Fig. 11. Phantoms and reconstructions II. Column 1: Phantoms 5 (top) and 6 (bottom). Different images between a phantom and a typical reconstruction with S140,10 at 50-noise obtained by SIRT (Column 2), BART (Column 3), DART (Column 4), GKXR (Column 5), U-FBP (Column 6), MPW (Column 7), and 2n-GON (Column 8). Color scheme for difference images: White pixels belong to the phantom (P) and the reconstruction (R), red pixels to R\P, and blue pixels to P\R. These are 192 192 pixel images in which the 160 pixel boundary has been cropped. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)
cannot be trusted (notation as in Section 2.1.1). For the GKXR, MPW, and 2n-GON reconstructions in Fig. 11, for instance, we find that JAxbJ is at least three times larger for Phantom 6 than for Phantom 5.
5. Conclusion
We have applied five algorithms from the mathematical fields of geometric and discrete tomography to reconstruct homoge- neous objects from electron tomography data. Our results demon-
[2] H. Friedrich, M.R. McCartney, P.R. Buseck, Comparison of intensity distribu- tions in tomograms from BF TEM, ADF TEM, HAADF STEM, and calculated tilt series, Ultramicroscopy 106 (2005) 18–27.
[3] A.H. Janssen, C.-M. Yang, Y. Wang, F. Schu ̈th, A.J. Koster, K.P. de Jong, Localization of small metal (oxide) particles in SBA-15 using bright-field electron tomography, Journal of Physical Chemistry B 107 (2003) 10552–10556.
[4] P.A. Midgley, R.E. Dunin-Borkowski, Electron tomography and holography in materials science, Nature Materials 8 (2009) 271–280.
[5] P.A. Midgley, M. Weyland, 3D electron microscopy in the physical sciences: the development of Z-contrast and EFTEM tomography, Ultramicroscopy 96 (2003) 413–431.
[6] G. Mo ̈bus, R.C. Doole, B.J. Inkson, Spectroscopic electron tomography, Ultra- microscopy 96 (2003) 433–451.
A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54 53
stratethatthechoiceofreconstructionalgorithmshouldbebased [7]R.S.Pennington,S.Ko ̈nig,A.Alpers,C.B.Boothroyd,R.E.Dunin-Borkowski,
on the specific reconstruction task at hand. None of the algo- rithms considered is better for all reconstruction tasks than the others. The main features of the algorithms that we intro- duced here in the ET context can be summarized as follows: BART and DART reconstruct homogeneous objects from projections; GKXR reconstructs convex objects from only four projections; MPW reconstructs convex objects from shadows and compen- sates for noise; and 2n-GON reconstructs objects that are close to regular 2n-gons from (possibly few) noisy shadows.
Acknowledgments
The first and third author were supported by DFG grant AL 1431/1-1 and GR 993/10-1, respectively. The second author was supported in part by NSF grants DMS-0603307 and DMS- 1103612. The eighth author acknowledges financial support by the NWO (the Netherlands Organisation for Scientific Research), project number 639.072.005. We thank Gabor T. Herman for valuable discussions related to SNARK09 and BART. The GKXR algorithm, with simulated projections of convex polygons and ellipses, was implemented by Mark Lockwood and modified to accept real-world data by Kyle Rader, both working while under- graduates at Western Washington University. We thank L. Fro ̈berg for growing and providing the nanowire specimen. Ran Davidi and Michael Ritter are acknowledged for technical support.
Appendix A. SNARK09 commands for BART
See Table A1.
Table A1
SNARK09 code (input file) for the BART algorithm. Left: main routine. Right: filtering routine. Seven copies of the filtering routine should be placed between the ‘‘ * ’’ and ‘‘END’’ of the main routine.
Reconstruction of an InAs nanowire using geometric and algebraic tomogra-
phy, Journal of Physics: Conference Series 326 (2011) 012045.
[8] X. Xu, Y. Peng, Z. Saghi, R. Gay, B.J. Inkson, G. Mo ̈bus, 3D reconstruction of SPM probes by electron tomography, Journal of Physics: Conference Series 61
(2007) 810–814.
[9] G.T. Herman, Fundamentals of computerized tomography: image reconstruc-
tion from projections, in: Advances in Pattern Recognition, 2nd edition,
Springer, London, 2009.
[10] A.C. Kak, M. Slaney, Principles of computerized tomographic imaging, in:
Classics in Applied Mathematics, vol. 33, Society for Industrial and Applied
Mathematics (SIAM), Philadelphia, PA, 2001 Reprint of the 1988 original. [11] X. Pan, E.Y. Sidky, M. Vannier, Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? Inverse Pro-
blems 25 (2009) 123009.
[12] J.-J. Fernandez, Computational methods for electron tomography, Micron 43
(2012) 1010–1030.
[13] R.J. Gardner, Geometric tomography, Encyclopedia of Mathematics and its
Applications, vol. 58, 2nd edition, Cambridge University Press, New York,
2006.
[14] G.T. Herman, A. Kuba (Eds.), Discrete Tomography: Foundations, Algorithms,
and Applications, Applied and Numerical Harmonic Analysis, Birkha ̈user
Boston Inc., Boston, MA, 1999.
[15] G.T. Herman, A. Kuba (Eds.), Advances in discrete tomography and its
applications, in: Applied and Numerical Harmonic Analysis, Birkha ̈user
Boston Inc., Boston, MA, 2007.
[16] K.A. Dick, A review of nanowire growth promoted by alloys and non-alloying
elements with emphasis on Au-assisted III–V nanowires, Progress in Crystal
Growth and Characterization of Materials 54 (2008) 138–173. [17]J.B.Wagner,N.Sko ̈ld,L.R.Wallenberg,L.Samuelson,Growthandsegregation of GaAs-AlxIn1 xP core-shell nanowires, Journal of Crystal Growth 312 (2010)
1755–1760.
[18] R. Davidi, G.T. Herman, J. Klukowska, SNARK09: a programming system for
the reconstruction of 2D images from 1D projections /http://www.dig.cs.gc.
cuny.edu/software/snark09S, 2009 [Online accessed 10-August-2012].
[19] T.C. Petersen, S.P. Ringer, Electron tomography using a geometric surface- tangent algorithm: application to atom probe specimen morphology, Journal
of Applied Physics 105 (2009) 103518.
[20] Z. Saghi, X. Xu, G. Mo ̈bus, Electron tomography of regularly shaped nanos-
tructures under non-linear image acquisition, Journal of Microscopy 232
(2008) 186–195.
[21] B. Goris, W. van den Broek, K.J. Batenburg, H.H. Mezerji, S. Bals, Electron
tomography based on a total variation minimization reconstruction techni-
que, Ultramicroscopy 113 (2012) 120–130.
[22] Z. Saghi, D.J. Holland, R. Leary, A. Falqui, G. Bertoni, A.J. Sederman,
L.F. Gladden, P.A. Midgley, Three-dimensional morphology of iron oxide nanoparticles with reactive concave surfaces. A compressed sensing- electron tomography (CS-ET) approach, Nano Letters 11 (2011) 4666–4673.
[23] A. Alpers, H.F. Poulsen, E. Knudsen, G.T. Herman, A discrete tomography algorithm for improving the quality of 3DXRD grain maps, Journal of Applied Crystallography 39 (2006) 582–588.
[24] B.M. Carvalho, G.T. Herman, S. Matej, C. Salzberg, E. Vardi, Binary tomography for triplane cardiography, in: A. Kuba, M. Samal, A. Todd-Pokropek (Eds.), Information Processing in Medical Imaging, vol. 1613, Springer, Berlin, 1999, pp. 29–41.
[25] S. van Aert, K.J. Batenburg, M.D. Rossell, R. Erni, G. van Tendeloo, Three- dimensional atomic imaging of crystalline nanoparticles, Nature 470 (2011) 374–377.
[26] K.J. Batenburg, S. Bals, J. Sijbers, C. Kuebel, P.A. Midgley, J.C. Hernandez, U. Kaiser, E.R. Encina, E.A. Coronado, G. van Tendeloo, 3D imaging of nanomaterials by discrete tomography, Ultramicroscopy 109 (2009) 730–740.
[27] P. Gilbert, Iterative methods for the three-dimensional reconstruction of an object from projections, Journal of Theoretical Biology 36 (1972) 105–117.
[28] G.T. Herman, Reconstruction of binary patterns from a few projections, in: A. Gu ̈nther, B. Levrat, H. Lipps (Eds.), International Computing Symposium 1973, North-Holland Publ. Co., Amsterdam, 1974, pp. 371–378.
[29] K.J. Batenburg, J. Sijbers, DART: a practical reconstruction algorithm for discrete tomography, IEEE Transactions on Image Processing 20 (2011) 2542–2553.
[30] R.J. Gardner, M. Kiderlen, A solution to Hammer’s X-ray reconstruction problem, Advances in Mathematics 214 (2007) 323–343.
STOP ITERATION 1
BASIS PIXEL
EXECUTE CONTINUE ALP1 SMOOTH Smoothing of BART recon
2 1 1 1
1
BASIS BLOBS
EXECUTE CONTINUE ALB1 CONTOUR Contouring of smooth BART recon 0.5 0 1 0
[1] P. Ercius, M. Weyland, D.A. Muller, L.M. Gignac, Three-dimensional imaging of nanovoids in copper interconnects using incoherent bright field tomogra- phy, Applied Physics Letters 88 (2006) 243116.
PICTURE TEST PROJECTION REAL MODE LOWER1⁄40.0
MODE UPPER1⁄41.0
STOP ITERATION 5
EXECUTE AVERAGE ART CONTOUR BART on hexagon image
0.5 0 1
1
ART3 relaxation constant 0.3 CONSTRAINT BART *1 END
References
54 A. Alpers et al. / Ultramicroscopy 128 (2013) 42–54
[31] R.J. Gardner, M. Kiderlen, A new algorithm for 3D reconstruction from support functions, IEEE Transactions on Pattern Analysis and Machine Intelligence 31 (2009) 556–562.
[32] R. Marabini, G.T. Herman, J.M. Carazo, 3D reconstruction in electron micro- scopy using ART with smooth spherically symmetric volume elements (blobs), Ultramicroscopy 72 (1998) 53–65.
[33] T. Obi, S. Matej, R.M. Lewitt, G.T Herman, 2.5-D simultaneous multislice reconstruction by series expansion methods from Fourier-rebinned PET data, IEEE Transactions on Medical Imaging 19 (2000) 474–484.
[34] J. Gregor, T. Benson, Computational analysis and improvement of SIRT, IEEE Transactions on Medical Imaging 27 (2008) 918–924.
[35] S. Bals, K.J. Batenburg, D. Liang, O. Lebedev, G. van Tendeloo, A. Aerts, J.A. Martens, C.E.A. Kirschhock, Quantitative three-dimensional modeling of Zeotile through discrete electron tomography, Journal of the American Chemical Society 131 (2009) 4769–4773.
[36] S. Bals, K.J. Batenburg, J. Verbeeck, J. Sijbers, G. van Tendeloo, Quantitative 3D reconstruction of catalyst particles for bamboo-like carbon-nanotubes, Nano Letters 7 (2007) 3669–3674.
[37] E. Biermans, L. Molina, K.J. Batenburg, S. Bals, G. van Tendeloo, Measuring porosity at the nanoscale by quantitative electron tomography, Nano Letters 10 (2010) 5014–5019.
[38] F. Leroux, M. Gysemans, S. Bals, K.J. Batenburg, J. Snauwaert, T. Verbiest, C. van Haesendonck, G. van Tendeloo, 3D characterization of helical silver nanochains mediated by protein assemblies, Advances in Materials 22 (2010) 2193–2197.
[39] K.J. Batenburg, W. van Aarle, J. Sijbers, A semi-automatic algorithm for grey level estimation in tomography, Pattern Recognition Letters 32 (2011) 1395–1405.
[40] W. van Aarle, K.J. Batenburg, J. Sijbers, Automatic parameter estimation for the discrete algebraic reconstruction technique (DART), IEEE Transactions on Image Processing 21 (11) (2012) 4608–4621.
[41] R.J. Gardner, P. McMullen, On Hammer’s X-ray problem, Journal of the London Mathematical Society 21 (2) (1980) 171–175.
[42] R. Gardner, P. Gritzmann, Discrete tomography: determination of finite sets by X-rays, Transactions of the American Mathematical Society 349 (1997) 2271–2295.
[43] J.L. Prince, A.S. Willsky, Estimating convex sets from noisy support line measurements, IEEE Transactions on Pattern Analysis and Machine Intelli- gence 12 (1990) 377–389.
[44] R.J. Gardner, M. Kiderlen, P. Milanfar, Convergence of algorithms for recon- structing convex bodies and directional measures, Annals of Statistics 34 (2006) 1331–1374.
[45] Y. Lia, F. Qian, J. Xiang, C.M. Lieber, Nanowire electronic and optoelectronic devices, Materials Today 9 (2006) 18–27.
[46] S. Mokkapati, C. Jagadish, III–V compound SC for optoelectronic devices, Materials Today 12 (2009) 22–32.
[47] J. Banhart, Advanced tomographic methods in materials research and engineering, in: Monographs on the Physics and Chemistry of Materials, Oxford University Press, Oxford, 2008.
[48] G. Mo ̈bus, B.J. Inkson, Nanoscale tomography in materials science, Materials Today 10 (2007) 18–25.
[49] R.G. Lyons, Understanding Digital Signal Processing, Prentice Hall, Upper Saddle River, NJ, 2001.
[50] R. Klette, A. Rosenfeld, Digital Geometry, Morgan Kaufmann, San Francisco, CA, 2004.
[51] D. Colton, R. Kress, Inverse acoustic and electromagnetic scattering theory, in: Applied Mathematical Sciences, vol. 93, Springer, Berlin, 1992.
[52] J. Kaipio, E. Somersalo, Statistical inverse problems: discretization model reduction and inverse crimes, Journal of Computational and Applied Mathe- matics 198 (2007) 493–504.
[53] A. Alpers, G.T. Herman, H.F. Poulsen, S. Schmidt, Phase retrieval for super- posed signals from multiple binary objects, Journal of Optical Society of America A 27 (2010) 1927–1937.