Advanced Search
Article Contents
Article Contents

Simultaneous reconstruction and segmentation with the Mumford-Shah functional for electron tomography

  • * Corresponding author: Ming Jiang

    * Corresponding author: Ming Jiang
This work was partially supported by the National Basic Research Program of China (973 Program) (2015CB351803), National Research and Development Program of China (2016YFA0500401), the National Science Foundation of China (61520106004, 81370203, 81461148026), Sino-German Center (GZ 1025), U.S. National Science Foundation under grants (DMS1311558, DMS1712207 to E.T. Quinto), and Microsoft Research of Asia.
Abstract / Introduction Full Text(HTML) Figure(6) / Table(5) Related Papers Cited by
  • Electron micrography (EM) is a detection method for determining the structure of macromolecular complexes and biological specimens. However, some restrictions in the EM system, including poor signal-to-noise, limited range of tilt angles, only a sub-region subject to electron exposure and unintentional movements of the specimen, make the reconstruction procedure severely ill-posed. Because of these limitations, there may be severe artifacts in reconstructed images. In this paper, we first design an algorithm that can quickly calculate the radiological paths. Then we combine an iterative reconstruction algorithm using the Mumford-Shah model with an artifact reduction strategy. The combined method can not only regularize the ill-posedness and provide the reconstruction and segmentation simultaneously but also smooth additional artifacts due to the limited data. Also we improved the algorithm used for the calculation of radiological paths to accelerate the reconstruction. The proposed algorithm was translated into OpenCL programs and kernel functions to asynchronously and in parallel update the reconstructed image along rays by GPUs. We tested the method on both simulated and real EM data. The results show that our artifact reduced Mumford-Shah algorithm can reduce the noise and artifacts while preserving and enhancing the edges in the reconstructed image.

    Mathematics Subject Classification: Primary: 15A29, 47A52; Secondary: 68U10.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Illustration of the calculation of 2d radiological paths. The variable $\varphi$ is the angle of inclination and $(ia, ib)$ is the index of the pixel. The variable $L$ is the intersection length of a ray with two vertical gridlines and $w$ is the proportion between intersection length of current pixel and $L$. The current pixel intercepted by the ray is $(ia, ib)$. $w>1$ in Algorithm. 1 corresponds to the left figure where the next pixel intercepted by the ray is $(ia, ib+1)$ and $w <1$ corresponds to the right figure where the next pixel is $(ia, ib+1)$. The proportion $w$ is calculated alternatively in Algorithm. 1 including only a few addition or subtraction operations and $w$ is used to decide whether the next pixel intercepted by the ray corresponds to the case in the left figure or the right figure

    Figure 2.  Illustration of the calculation of 3d radiological paths. $w_{x}$ and $w_{y}$ are the proportion of the projected ray in $zx-plane$ and $zy-plane$ respectively. $w_{x}$ and $w_{y}$ are calculated by algorithm. 1. $L'$ is the constant length of the ray between the plane $iz = ic$ and $iz = ic+1$. The current voxel intercepted by the ray is $(ia, ib, ic)$. $w_{x} <w_{y}$ in Algorithm. 2 corresponds to case that the next two voxels intercepted by the ray are $(ia+1, ib, ic)$ and $(ia+1, ib+1, ic)$. $w_{x}\geq w_{y}$ corresponds to case that the next two voxels are $(ia, ib+1, ic)$ and $(ia+1, ib+1, ic)$. $w_{x}$ and $w_{y}$ are used to decide which voxels are intercepted by the ray after the current voxel $(ia, ib, ic)$

    Figure 3.  Reconstructions of 3D Shepp-Logan phantom using the alternating minimization scheme described in Algorithm 3 and artifact reduction strategy in Sec. 2.3. The size of Shepp-Logan phantom is $300\times 300\times 300$ and two slices are shown in (a)~(e). (a)(b) are slices of original phantom. (a) corresponds to the red line in (b) and (b) to the red line in (a). Euler angles are used to generate projections: rotation $\phi$ changes between $-60^{\circ}$ and $60^{\circ}$ at $1^{\circ}$ intervals for each measurement, azimuthal angle $\theta$ is fixed at $0^{\circ}$ and in-plane rotation $\psi$ at $165^{\circ}$. (c)+(d) and (e)+(f) show the reconstruction image and segmentations without the artifact reduction strategy and (g)+(h) and (i)+(j), with a cutoff $\kappa_{\sigma}$ in the operator $\mathcal{K}_{\sigma}$ defined in (14). We chose the parameter $\sigma = \Phi /4$. While streak artifacts near $\pm 60^{\circ}$ in (c)+(d) and streak artifacts in (e)+(f) can be observed, the implementation of the artifact reduction strategy smooths some artifacts in (g)+(h) and (i)+(j)

    Figure 4.  Reconstructions and segmentations of the Shepp-Logan phantom $f^{\dagger}$ from noisy Radon data. Left column: reconstruction $f^{MS}$ from noisy data $\mathcal{R}f^{\dagger} + \delta N(0, 1)$ using the artifact reduced Mumford-Shah algorithm ($\alpha = 2, \beta = 0.0002, \varepsilon = 0.0001 $); middle column: The reconstructed edge indicator function $v$; right column: reconstructions from same noisy data using WBP method in TOM software toolbox. For stronger noise it is more difficult to reconstruct the low contrast regions for both methods. From the comparison between the left and right column, we can see that our reconstruction method with Mumford -Shah functional can depress the noise compared to WBP method while the edges are preserved. If an edge is detected in $v$, the reconstruction $f^{MS}$ has a sharp edge

    Figure 5.  Reconstructions of cryo-specimen using the alternating minimization scheme described in Algorithm 3 and artifact reduction strategy in Sec. 2.3. Left column is the reconstructed images, the middle column is the edge sets with our algorithm, and the right column is the reconstructed images with WBP algorithm in TOM toolbox. The images in the red block are zoomed in and put in the top right corner. The edges in the middle column are enhanced in the left column compared to the WBP reconstructions in the right column. Compared to the results of WBP in right column, the results in the left show the effect of noise reduction while the edges are preserved

    Figure 6.  Density maps and ResMap of the reconstructed images of WBP method and our method. The mean resolution of WBP is 17.17Å while the mean resolution of our reconstruction with alternative minimization algorithm is 15.07Å

    Table Algorithm 1.  Fast calculation of 2D radiological paths

    input $ray$ in 2D;
    Initialize $w,ia,ib$;
     | Show Table
    DownLoad: CSV

    Table Algorithm 2.  Fast calculation of 3D radiological paths

    input $w_{x}, w_{y}$;
     | Show Table
    DownLoad: CSV

    Table Algorithm 3.  Alternate Minimization of $AT_{\mathcal{R}, \varepsilon}(\mathbf{f}, \mathbf{v}) $

    $f^0 = 0$ or a-priori image;
    $v^0 = 1$;
     | Show Table
    DownLoad: CSV

    Table Algorithm 4.  Image Minimization with Steepest Descent Method

    $\mathbf{f}^0 =$ current image;
    $\mathbf{v} =$ current edge;
    $\mathbf{d}^0 = \mathcal{R}^*(\mathcal{K}_{\sigma}( \mathbf{g}) - \mathcal{R}_{\Phi}(\mathbf{f}^0)) + \alpha \text{div}(\mathbf{v}^2 \nabla \mathbf{f}^0)$;
     | Show Table
    DownLoad: CSV

    Table Algorithm 5.  Edge Minimization with Steepest Descent Method

    $\mathbf{f} =$ current image
    $\mathbf{v}^{0} =$ current edge;
     | Show Table
    DownLoad: CSV
  • [1] L. Ambrosio and V. M. Tortorelli, On the approximation of free discontinuity problems, Boll. Un. Mat. Ital. B, 6 (1992), 105-123. 
    [2] S. BonettiniM. Prato and S. Rebegoldi, A cyclic block coordinate descent method with generalized gradient projections, Appl. Math. Comput., 286 (2016), 288-300.  doi: 10.1016/j.amc.2016.04.031.
    [3] S. Bonettini, Inexact block coordinate descent methods with application to non-negative matrix factorization, IMA Journal of Numerical Analysis, 31 (2011), 1431-1452.  doi: 10.1093/imanum/drq024.
    [4] D. Fanelli and O. Öktem. Electron tomography: A short overview with an emphasis on the absorption potential model for the forward problem, Inverse Problems, 24 (2008), 013001, 51 pp. doi: 10.1088/0266-5611/24/1/013001.
    [5] J. Frikel and E. T. Quinto, Characterization and reduction of artifacts in limited angle tomography, Inverse Problems, 29 (2013), 2091-2128.  doi: 10.1088/0266-5611/29/12/125007.
    [6] A. FujimotoT. Tanaka and K. Iwata, Arts: Accelerated ray-tracing system, IEEE Computer Graphics and Applications, 6 (1986), 16-26. 
    [7] A. Zampighi Guido, S. Cataldo, M. Zampighi Lorenzo, W. Michael, M. Wright Ernest and C. Brecha Nicholas, Conical tomography of a ribbon synapse: Structural evidence for vesicle fusion, Plos One, 6 (2011), e16944.
    [8] G, T. Herman and J. Frank, Computational Methods for Three-Dimensional Microscopy Reconstruction, Springer New York, 2014.
    [9] X. HuangL. SunS. JiT. ZhaoW. ZhangJ. XuJ. ZhangY. WangX. WangC. Franzini-ArmstrongM. Zheng and H. Cheng, Kissing and nanotunneling mediate intermitochondrial communication in the heart, Proceedings of the National Academy of Sciences of the United States of America, 110 (2013), 2846-2851. 
    [10] M. Jiang, P. Maass, and T. Page, Regularizing properties of the mumford-shah functional for imaging applications, Inverse Problems, 30 (2014), 035007, 17 pp. doi: 10.1088/0266-5611/30/3/035007.
    [11] Y. M. JungS. H. Kang and J. Shen, Multiphase image segmentation via modica-mortola phase transition, SIAM Journal on Applied Mathematics, 67 (2007), 1213-1232.  doi: 10.1137/060662708.
    [12] E. Klann, A mumford-shah-like method for limited data tomography with an application to electron tomography, SIAM Journal on Imaging Sciences, 4 (2011), 1029-1048.  doi: 10.1137/100817371.
    [13] J. KlukowskaD. Ran and G. T. Herman, Snark09 a software package for reconstruction of 2d images from 1d projections, Computer Methods and Programs in Biomedicine, 110 (2013), 424-440. 
    [14] A. KucukelbirF. J. Sigworth and H. D. Tagare, Quantifying the local resolution of cryo-em density maps, Nature Methods, 11 (2014), 63-65. 
    [15] S. LanzavecchiaF. CanteleP. L. BellonL. ZampighiM. KremanE. Wright and G. A. Zampighi, Conical tomography of freeze-fracture replicas: A method for the study of integral membrane proteins inserted in phospholipid bilayers, Journal of Structural Biology, 149 (2005), 87-98. 
    [16] Y. Li and J. Kim, Multiphase image segmentation using a phase-field model, Computers and Mathematics with Applications, 62 (2011), 737-745.  doi: 10.1016/j.camwa.2011.05.054.
    [17] Y. K. Liu, H. Y. Song and B. $\rm{\ddot{Z}}$alik, A general multi-step algorithm for voxel traversing along a line, In Computer Graphics Forum, (2008), 73–80.
    [18] G. Luo, M. Jiang and P. Maass, Fpga acceleration by asynchronous parallelization for simultaneous image reconstruction and segmentation based on the mumford-shah regularization, 2015.
    [19] R. MarabiniE. RietzelR. SchroederG. T. Herman and J. M. Carazo, Three-dimensional reconstruction from reduced sets of very noisy images acquired following a single-axis tilt schema: Application of a new three-dimensional reconstruction algorithm and objective comparison with weighted backprojection, Journal of Structural Biology, 120 (1998), 363-371. 
    [20] L. Modica and S. Mortola, Un esempio di $γ$-convergenza, Bollettino Della Unione Matematica Italiana B, 14 (1977), 285-299. 
    [21] D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational-problems, Communications on Pure and Applied Mathematics, 42 (1989), 577-685. 
    [22] A. Munshi, The opencl specification, In 2009 IEEE Hot Chips 21 Symposium (HCS), (2009), 1–314.
    [23] S. NickellF. FörsterA. LinaroudisW. Del NetF. BeckR. HegerlW. Baumeister and J. M. Plitzko, Tom software toolbox: acquisition and analysis for electron tomography, Journal of Structural Biology, 149 (2005), 227-234. 
    [24] O. Öktem, Mathematics of electron tomography, Handbook of Mathematical Methods in Imaging, Springer New York, New York, NY, (2015), 937–1031.
    [25] E. T. QuintoU. Skoglund and O. Oktem, Electron lambda-tomography, Proceedings of the National Academy of Sciences of the United States of America, 106 (2009), 21842-7. 
    [26] M. Radermacher, Weighted back-projection methods, Electron Tomography: Methods for Three-Dimensional Visualization of Structures in the Cell, Springer New York, New York, NY, (2006), 245–273.
    [27] R. Ramlau and W. Ring, Regularization of ill-posed mumford shah models with perimeter penalization, Inverse Problems, 26 (2010), 115001, 25pp. doi: 10.1088/0266-5611/26/11/115001.
    [28] L. Reimer, Transmission Electron Microscopy: Physics of Image Formation and Microanalysis, Springer-Verlag, 1989.
    [29] H. RullgårdL.-G. ÖfverstedtS. MasichB. Daneholt and O. Öktem, Simulation of transmission electron microscope images of biological specimens, Journal of Microscopy, 243 (2011), 234-256. 
    [30] W. ShangF. LuT. SunJ. XuL. L. LiY. WangG. WangL. ChenX. Wang and M. B. Cannell, Imaging ca2+ nanosparks in heart with a new targeted biosensor, Circulation Research, 114 (2014), 412-420. 
    [31] R. L. Siddon, Fast calculation of the exact radiological path for a three-dimensional ct array, Medical Physics, 12 (1985), 252-255. 
    [32] J. E. StoneD. Gohara and G. Shi, Opencl: A parallel programming standard for heterogeneous computing systems, Computing in Science and Engineering, 12 (2010), 66-72. 
    [33] E. SundermannF. JacobsM. ChristiaensB. De Sutter and I. Lemahieu, A fast algorithm to calculate the exact radiological path through a pixel or voxel space, Journal of Computing and Information Technology, 6 (1998), 89-94. 
    [34] A. R. Webb, Statistical Pattern Recognition. 2nd ed, 2002. doi: 10.1002/0470854774.
    [35] S. J. Wright, Coordinate descent algorithms, Math. Program., 151 (2015), Ser. B, 3-34.  doi: 10.1007/s10107-015-0892-3.
    [36] B. $\rm{\ddot{Z}}$alikG. Clapworthy and ${\rm{\ddot{C}}}$. Oblon${\rm{\ddot{s}}}$ek, An efficient code-based voxel-traversing algorithm, Computer Graphics Forum, 16 (1997), 119-128. 
  • 加载中




Article Metrics

HTML views(1732) PDF downloads(233) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint