Multi-target detection with rotations

Tamir Bendory; Ti-Yen Lan; Nicholas F. Marshall; Iris Rukshin; Amit Singer

doi:10.3934/ipi.2022046

Article Contents

2023, Volume 17, Issue 2: 362-380. Doi: 10.3934/ipi.2022046

This issue Previous Article Time-harmonic diffuse optical tomography: Hölder stability of the derivatives of the optical properties of a medium at the boundary Next Article An efficient augmented Lagrangian method with semismooth Newton solver for total generalized variation

Multi-target detection with rotations

1.
School of Electrical Engineering, Tel Aviv University, Israel
2.
Program in Applied and Computational Mathematics, Princeton University, USA
3.
Department of Mathematics, Oregon State University, USA
4.
Program in Applied and Computational Mathematics and the Department of Mathematics, Princeton University, USA

^*Corresponding author: Nicholas F. Marshall
^*Corresponding author: Nicholas F. Marshall

Received: January 2022

Revised: August 2022

Early access: September 2022

Published: April 2023

Abstract / Introduction Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

We consider the multi-target detection problem of estimating a two-dimensional target image from a large noisy measurement image that contains many randomly rotated and translated copies of the target image. Motivated by single-particle cryo-electron microscopy, we focus on the low signal-to-noise regime, where it is difficult to estimate the locations and orientations of the target images in the measurement. Our approach uses autocorrelation analysis to estimate rotationally and translationally invariant features of the target image. We demonstrate that, regardless of the level of noise, our technique can be used to recover the target image when the measurement is sufficiently large.

Keywords:

Mathematics Subject Classification: Primary: 94A08, 62M10; Secondary: 92C55, 42A16.

Citation:

Full Text(HTML)

Figure 1. An example of the measurement $ M $ defined in (1) with (a) SNR = $ 10^2 $, (b) SNR = 1 and (c) SNR : = $ 10^{-2} $, where $ \text{SNR} = (\pi n^2\sigma^{2})^{-1} \sum_x F(x)^2 $

Download: Full-size image PowerPoint slide

Figure 2. An example of the 1-dimensional measurement $ M $ defined in (2) with $ \text{SNR} = \infty $ (left), $ \text{SNR} = 10^2 $ (middle), and $ \text{SNR} = 1 $ (right), where $ \text{SNR}: = {(2} n{)}^{-1} \sum_x F(x)^2/\sigma^2 $

Download: Full-size image PowerPoint slide

Figure 3. Relative error of bispectrum derived from measurement $ M $ using various number of samples $ p $ averaged over 10 trials. The error decreases as $ 1/\sqrt{p} $, as expected by the law of large numbers

Download: Full-size image PowerPoint slide

Figure 4. The projection of a $ 65 \times 65 $ image of a tiger onto the span of the first $ 600 $ Dirichlet Laplacian eigenfunctions on a disc

Download: Full-size image PowerPoint slide

Figure 5. Relative error in the binned invariant $ S_F $ summed over the bins and the reconstruction of $ F $ as a function of the number of micrographs for an image with $ n = 17 $ with SNR $ = 10^2 $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	E. Abbe, T. Bendory, W. Leeb, J. M. Pereira, N. Sharon and A. Singer, Multireference alignment is easier with an aperiodic translation distribution, IEEE Transactions on Information Theory, 65 (2018), 3565-3584. doi: 10.1109/TIT.2018.2889674.
[2]	E. Abbe, J. M. Pereira and A. Singer, Estimation in the group action channel, In 2018 IEEE International Symposium on Information Theory (ISIT), IEEE, 2018,561-565. doi: 10.1109/ISIT.2018.8437646.
[3]	C. Aguerrebere, M. Delbracio, A. Bartesaghi and G. Sapiro, Fundamental limits in multi-image alignment, IEEE Transactions on Signal Processing, 64 (2016), 5707-5722. doi: 10.1109/TSP.2016.2600517.
[4]	P. R. Baldwin and D. Lyumkis, Non-uniformity of projection distributions attenuates resolution in cryo-EM, Progress in Biophysics and Molecular Biology, 150 (2020), 160-183. doi: 10.1016/j.pbiomolbio.2019.09.002.
[5]	A. S. Bandeira, B. Blum-Smith, J. Kileel, A. Perry, J. Weed and A. S. Wein, Estimation under group actions: Recovering orbits from invariants, arXiv preprint, arXiv: 1712.10163, 2017.
[6]	T. Bendory, A. Bartesaghi and A. Singer, Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities, IEEE Signal Processing Magazine, 37 (2020), 58-76. doi: 10.1109/MSP.2019.2957822.
[7]	T. Bendory, N. Boumal, W. Leeb, E. Levin and A. Singer, Toward single particle reconstruction without particle picking: Breaking the detection limit, arXiv preprint, arXiv: 1810.00226, 2018. doi: 10.1101/431080.
[8]	T. Bendory, N. Boumal, W. Leeb, E. Levin and A. Singer, Multi-target detection with application to cryo-electron microscopy, Inverse Problems, 35 (2019), 104003. doi: 10.1088/1361-6420/ab2aec.
[9]	T. Bendory, N. Boumal, C. Ma, Z. Zhao and A. Singer, Bispectrum inversion with application to multireference alignment, IEEE Transactions on Signal Processing, 66 (2018), 1037-1050. doi: 10.1109/TSP.2017.2775591.
[10]	T. Bendory, A. Jaffe, W. Leeb, N. Sharon and A. Singer, Super-resolution multi-reference alignment, Information and Inference: A Journal of the IMA, 11 (2022), 533-555. doi: 10.1093/imaiai/iaab003.
[11]	J. Z. Chen and N. Grigorieff, SIGNATURE: A single-particle selection system for molecular electron microscopy, Journal of Structural Biology, 157 (2007), 168-173. doi: 10.1016/j.jsb.2006.06.001.
[12]	Z. Dou, Z. Fan and H. Zhou, Rates of estimation for high-dimensional multi-reference alignment, arXiv preprint, arXiv: 2205.01847, 2022.
[13]	A. Eldar, B. Landa and Y. Shkolnisky, KLT picker: Particle picking using data-driven optimal templates, Journal of Structural Biology, 210 (2020), 107473. doi: 10.1016/j.jsb.2020.107473.
[14]	J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State, Oxford University Press, 2006. doi: 10.1093/acprof:oso/9780195182187.001.0001.
[15]	T. Grant, A. Rohou and N. Grigorieff, cisTEM, user-friendly software for single-particle image processing, Elife, 7: e35383, 2018. doi: 10.7554/eLife.35383.
[16]	A. Heimowitz, J. Andén and A. Singer, Apple picker: Automatic particle picking, a low-effort cryo-EM framework, Journal of Structural Biology, 204 (2018), 215-227. doi: 10.1016/j.jsb.2018.08.012.
[17]	R. Henderson, The potential and limitations of neutrons, electrons and X-rays for atomic resolution microscopy of unstained biological molecules, Quarterly Reviews of Biophysics, 28 (1995), 171-193. doi: 10.1017/S003358350000305X.
[18]	S. Huang, M. Zehni, I. Dokmanić and Z. Zhao, Orthogonal matrix retrieval with spatial consensus for 3D unknown-view tomography, arXiv preprint, arXiv: 2207.02985, 2022.
[19]	Z. Kam, The reconstruction of structure from electron micrographs of randomly oriented particles, Journal of Theoretical Biology, 82 (1980), 15-39. doi: 10.1016/0022-5193(80)90088-0.
[20]	S. Kreymer and T. Bendory, Two-dimensional multi-target detection: An autocorrelation analysis approach, IEEE Transactions on Signal Processing, 70 (2022), 835-849. doi: 10.1109/TSP.2022.3147735.
[21]	S. Kreymer, A. Singer and T. Bendory, An approximate expectation-maximization for two-dimensional multi-target detection, IEEE Signal Processing Letters, 29 (2022), 1087-1091. doi: 10.1109/LSP.2022.3167335.
[22]	T.-Y. Lan, T. Bendory, N. Boumal and A. Singer, Multi-target detection with an arbitrary spacing distribution, IEEE Transactions on Signal Processing, 68 (2020), 1589-1601. doi: 10.1109/TSP.2020.2975943.
[23]	T.-Y. Lan, N. Boumal and A. Singer, Random conical tilt reconstruction without particle picking in cryo-electron microscopy, Acta Crystallographica Section A, 78 (2022), 294-301. doi: 10.1107/S2053273322005071.
[24]	E. Levin, T. Bendory, N. Boumal, J. Kileel and A. Singer, 3D ab initio modeling in cryo-EM by autocorrelation analysis, In 2018 IEEE 15th International Symposium on Biomedical Imaging (ISBI 2018), IEEE, 2018, 1569-1573. doi: 10.1109/ISBI.2018.8363873.
[25]	N. F. Marshall, T.-Y. Lan, T. Bendory and A. Singer, Image recovery from rotational and translational invariants, In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, 5780-5784. doi: 10.1109/ICASSP40776.2020.9053932.
[26]	A. Perry, J. Weed, A. S. Bandeira, P. Rigollet and A. Singer, The sample complexity of multireference alignment, SIAM Journal on Mathematics of Data Science, 1 (2019), 497-517. doi: 10.1137/18M1214317.
[27]	A. Punjani, J. L. Rubinstein, D. J. Fleet and M. A. Brubaker, cryoSPARC: Algorithms for rapid unsupervised cryo-EM structure determination, Nature Methods, 14 (2017), 290-296. doi: 10.1038/nmeth.4169.
[28]	M. Radermacher, T. Wagenknecht, A. Verschoor and J. Frank, Three-dimensional reconstruction from a single-exposure, random conical tilt series applied to the 50s ribosomal subunit of escherichia coli, Journal of Microscopy, 146 (1987), 113-136. doi: 10.1142/9789813234864_0013.
[29]	E. Romanov, T. Bendory and O. Ordentlich, Multi-reference alignment in high dimensions: Sample complexity and phase transition, SIAM Journal on Mathematics of Data Science, 3 (2021), 494-523. doi: 10.1137/20M1354994.
[30]	B. M. Sadler and G. B. Giannakis, Shift-and rotation-invariant object reconstruction using the bispectrum, JOSA A, 9 (1992), 57-69. doi: 10.1364/JOSAA.9.000057.
[31]	D. K. Saldin, H.-C. Poon, P. Schwander, M. Uddin and M. Schmidt, Reconstructing an icosahedral virus from single-particle diffraction experiments, Optics Express, 19 (2011), 17318-17335. doi: 10.1364/OE.19.017318.
[32]	D. K. Saldin, V. L. Shneerson, M. R. Howells, S. Marchesini, H. N. Chapman, M. Bogan, D. Shapiro, R. Kirian, U. Weierstall and K. Schmidt, et al., Structure of a single particle from scattering by many particles randomly oriented about an axis: Toward structure solution without crystallization?, New Journal of Physics, 12 (2010), 035014. doi: 10.1088/1367-2630/12/3/035014.
[33]	S. H. W. Scheres, RELION: Implementation of a bayesian approach to cryo-EM structure determination, Journal of Structural Biology, 180 (2012), 519-530. doi: 10.1016/j.jsb.2012.09.006.
[34]	S. H. W. Scheres, Semi-automated selection of cryo-EM particles in RELION-1.3, Journal of Structural Biology, 189 (2015), 114-122. doi: 10.1016/j.jsb.2014.11.010.
[35]	N. Sharon, J. Kileel, Y. Khoo, B. Landa and A. Singer, Method of moments for 3D single particle ab initio modeling with non-uniform distribution of viewing angles, Inverse Problems, 36 (2020), 044003. doi: 10.1088/1361-6420/ab6139.
[36]	G. Tang, L. Peng, P. R. Baldwin, D. S. Mann, W. Jiang, I. Rees and S. J. Ludtke, EMAN2: An extensible image processing suite for electron microscopy, Journal of Structural Biology, 157 (2007), 38-46. doi: 10.1016/j.jsb.2006.05.009.
[37]	J. Tukey, The spectral representation and transformation properties of the higher moments of stationary time series, Reprinted in The Collected Works of John W. Tukey, 1 (1953), 165-184.
[38]	T. Wagner, F. Merino, M. Stabrin, T. Moriya, C. Antoni, A. Apelbaum, P. Hagel, O. Sitsel, T. Raisch and D. Prumbaum, et al., SPHIRE-crYOLO is a fast and accurate fully automated particle picker for cryo-EM, Communications Biology, 2 (2019), 1-13. doi: 10.1038/s42003-019-0437-z.
[39]	F. Wang, H. Gong, G. Liu, M. Li, C. Yan, T. Xia, X. Li and J. Zeng, DeepPicker: A deep learning approach for fully automated particle picking in cryo-EM, Journal of Structural Biology, 195 (2016), 325-336. doi: 10.1016/j.jsb.2016.07.006.
[40]	R. Weber, A. Abas, S. Kreymer, T. Bendory, et al., Generalized autocorrelation analysis for multi-target detection, In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2022, 5907-5911.