Abstract

We present an efficient and accurate algorithm for principal component analysis (PCA) of a large set of two-dimensional images and, for each image, the set of its uniform rotations in the plane and its reflection. The algorithm starts by expanding each image, originally given on a Cartesian grid, in the Fourier–Bessel basis for the disk. Because the images are essentially band limited in the Fourier domain, we use a sampling criterion to truncate the Fourier–Bessel expansion such that the maximum amount of information is preserved without the effect of aliasing. The constructed covariance matrix is invariant to rotation and reflection and has a special block diagonal structure. PCA is efficiently done for each block separately. This Fourier–Bessel-based PCA detects more meaningful eigenimages and has improved denoising capability compared to traditional PCA for a finite number of noisy images.

© 2013 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State (Oxford, 2006).
  2. M. van Heel and J. Frank, “Use of multivariate statistics in analysing the images of biological macromolecules,” Ultramicroscopy 6, 187–194 (1981).
    [CrossRef]
  3. R. Hilai and J. Rubinstein, “Recognition of rotated images by invariant Karhunen–Loéve expansion,” J. Opt. Soc. Am. A 11, 1610–1618 (1994).
    [CrossRef]
  4. P. Perona, “Deformable kernels for early vision,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 488–499 (1995).
    [CrossRef]
  5. M. Uenohara and T. Kanade, “Optimal approximation of uniformly rotated images: relationship between Karhunen–Loéve expansion and discrete cosine transform,” IEEE Trans. Image Process. 7, 116–119 (1998).
    [CrossRef]
  6. M. Jogan, E. Zagar, and A. Leonardis, “Karhunen–Loéve expansion of a set of rotated templates,” IEEE Trans. Image Process. 12, 817–825 (2003).
    [CrossRef]
  7. C. Ponce and A. Singer, “Computing steerable principal components of a large set of images and their rotations,” IEEE Trans. Image Process. 20, 3051–3062 (2011).
    [CrossRef]
  8. A. Klug and R. A. Crowther, “Three-dimensional image reconstruction from the viewpoint of information theory,” Nature 238, 435–440 (1972).
    [CrossRef]
  9. J. McMahon, “On the roots of the Bessel and certain related functions,” Ann. Math. 9, 23–30 (1894–1895).
    [CrossRef]
  10. S. Kritchman and B. Nadler, “Determining the number of components in a factor model from limited noisy data,” Chemom. Intell. Lab. Syst. 94, 1932 (2008).
    [CrossRef]
  11. A. Singer and H.-T. Wu, “Two-dimensional tomography from noisy projections taken at unknown random directions,” SIAM J. Imaging Sci. 6, 136–175 (2013).
    [CrossRef]
  12. Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
    [CrossRef]
  13. Z. Kam, “The reconstruction of structure from electron micrographs of randomly oriented particles,” J. Theor. Biol. 82, 15–39 (1980).
    [CrossRef]
  14. D. Slepian, “Prolate spheroidal wave functions, Fourier analysis, and uncertainty—IV: extensions to many dimensions, generalized prolate spheroidal wave functions,” Bell Syst. Tech. J. 43, 3009–3057 (1964).

2013 (1)

A. Singer and H.-T. Wu, “Two-dimensional tomography from noisy projections taken at unknown random directions,” SIAM J. Imaging Sci. 6, 136–175 (2013).
[CrossRef]

2011 (1)

C. Ponce and A. Singer, “Computing steerable principal components of a large set of images and their rotations,” IEEE Trans. Image Process. 20, 3051–3062 (2011).
[CrossRef]

2008 (1)

S. Kritchman and B. Nadler, “Determining the number of components in a factor model from limited noisy data,” Chemom. Intell. Lab. Syst. 94, 1932 (2008).
[CrossRef]

2004 (1)

Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
[CrossRef]

2003 (1)

M. Jogan, E. Zagar, and A. Leonardis, “Karhunen–Loéve expansion of a set of rotated templates,” IEEE Trans. Image Process. 12, 817–825 (2003).
[CrossRef]

1998 (1)

M. Uenohara and T. Kanade, “Optimal approximation of uniformly rotated images: relationship between Karhunen–Loéve expansion and discrete cosine transform,” IEEE Trans. Image Process. 7, 116–119 (1998).
[CrossRef]

1995 (1)

P. Perona, “Deformable kernels for early vision,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 488–499 (1995).
[CrossRef]

1994 (1)

1981 (1)

M. van Heel and J. Frank, “Use of multivariate statistics in analysing the images of biological macromolecules,” Ultramicroscopy 6, 187–194 (1981).
[CrossRef]

1980 (1)

Z. Kam, “The reconstruction of structure from electron micrographs of randomly oriented particles,” J. Theor. Biol. 82, 15–39 (1980).
[CrossRef]

1972 (1)

A. Klug and R. A. Crowther, “Three-dimensional image reconstruction from the viewpoint of information theory,” Nature 238, 435–440 (1972).
[CrossRef]

1964 (1)

D. Slepian, “Prolate spheroidal wave functions, Fourier analysis, and uncertainty—IV: extensions to many dimensions, generalized prolate spheroidal wave functions,” Bell Syst. Tech. J. 43, 3009–3057 (1964).

1894 (1)

J. McMahon, “On the roots of the Bessel and certain related functions,” Ann. Math. 9, 23–30 (1894–1895).
[CrossRef]

Bovik, A. C.

Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
[CrossRef]

Crowther, R. A.

A. Klug and R. A. Crowther, “Three-dimensional image reconstruction from the viewpoint of information theory,” Nature 238, 435–440 (1972).
[CrossRef]

Frank, J.

M. van Heel and J. Frank, “Use of multivariate statistics in analysing the images of biological macromolecules,” Ultramicroscopy 6, 187–194 (1981).
[CrossRef]

J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State (Oxford, 2006).

Hilai, R.

Jogan, M.

M. Jogan, E. Zagar, and A. Leonardis, “Karhunen–Loéve expansion of a set of rotated templates,” IEEE Trans. Image Process. 12, 817–825 (2003).
[CrossRef]

Kam, Z.

Z. Kam, “The reconstruction of structure from electron micrographs of randomly oriented particles,” J. Theor. Biol. 82, 15–39 (1980).
[CrossRef]

Kanade, T.

M. Uenohara and T. Kanade, “Optimal approximation of uniformly rotated images: relationship between Karhunen–Loéve expansion and discrete cosine transform,” IEEE Trans. Image Process. 7, 116–119 (1998).
[CrossRef]

Klug, A.

A. Klug and R. A. Crowther, “Three-dimensional image reconstruction from the viewpoint of information theory,” Nature 238, 435–440 (1972).
[CrossRef]

Kritchman, S.

S. Kritchman and B. Nadler, “Determining the number of components in a factor model from limited noisy data,” Chemom. Intell. Lab. Syst. 94, 1932 (2008).
[CrossRef]

Leonardis, A.

M. Jogan, E. Zagar, and A. Leonardis, “Karhunen–Loéve expansion of a set of rotated templates,” IEEE Trans. Image Process. 12, 817–825 (2003).
[CrossRef]

McMahon, J.

J. McMahon, “On the roots of the Bessel and certain related functions,” Ann. Math. 9, 23–30 (1894–1895).
[CrossRef]

Nadler, B.

S. Kritchman and B. Nadler, “Determining the number of components in a factor model from limited noisy data,” Chemom. Intell. Lab. Syst. 94, 1932 (2008).
[CrossRef]

Perona, P.

P. Perona, “Deformable kernels for early vision,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 488–499 (1995).
[CrossRef]

Ponce, C.

C. Ponce and A. Singer, “Computing steerable principal components of a large set of images and their rotations,” IEEE Trans. Image Process. 20, 3051–3062 (2011).
[CrossRef]

Rubinstein, J.

Sheikh, H. R.

Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
[CrossRef]

Simoncelli, E. P.

Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
[CrossRef]

Singer, A.

A. Singer and H.-T. Wu, “Two-dimensional tomography from noisy projections taken at unknown random directions,” SIAM J. Imaging Sci. 6, 136–175 (2013).
[CrossRef]

C. Ponce and A. Singer, “Computing steerable principal components of a large set of images and their rotations,” IEEE Trans. Image Process. 20, 3051–3062 (2011).
[CrossRef]

Slepian, D.

D. Slepian, “Prolate spheroidal wave functions, Fourier analysis, and uncertainty—IV: extensions to many dimensions, generalized prolate spheroidal wave functions,” Bell Syst. Tech. J. 43, 3009–3057 (1964).

Uenohara, M.

M. Uenohara and T. Kanade, “Optimal approximation of uniformly rotated images: relationship between Karhunen–Loéve expansion and discrete cosine transform,” IEEE Trans. Image Process. 7, 116–119 (1998).
[CrossRef]

van Heel, M.

M. van Heel and J. Frank, “Use of multivariate statistics in analysing the images of biological macromolecules,” Ultramicroscopy 6, 187–194 (1981).
[CrossRef]

Wang, Z.

Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
[CrossRef]

Wu, H.-T.

A. Singer and H.-T. Wu, “Two-dimensional tomography from noisy projections taken at unknown random directions,” SIAM J. Imaging Sci. 6, 136–175 (2013).
[CrossRef]

Zagar, E.

M. Jogan, E. Zagar, and A. Leonardis, “Karhunen–Loéve expansion of a set of rotated templates,” IEEE Trans. Image Process. 12, 817–825 (2003).
[CrossRef]

Ann. Math. (1)

J. McMahon, “On the roots of the Bessel and certain related functions,” Ann. Math. 9, 23–30 (1894–1895).
[CrossRef]

Bell Syst. Tech. J. (1)

D. Slepian, “Prolate spheroidal wave functions, Fourier analysis, and uncertainty—IV: extensions to many dimensions, generalized prolate spheroidal wave functions,” Bell Syst. Tech. J. 43, 3009–3057 (1964).

Chemom. Intell. Lab. Syst. (1)

S. Kritchman and B. Nadler, “Determining the number of components in a factor model from limited noisy data,” Chemom. Intell. Lab. Syst. 94, 1932 (2008).
[CrossRef]

IEEE Trans. Image Process. (4)

Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612(2004).
[CrossRef]

M. Uenohara and T. Kanade, “Optimal approximation of uniformly rotated images: relationship between Karhunen–Loéve expansion and discrete cosine transform,” IEEE Trans. Image Process. 7, 116–119 (1998).
[CrossRef]

M. Jogan, E. Zagar, and A. Leonardis, “Karhunen–Loéve expansion of a set of rotated templates,” IEEE Trans. Image Process. 12, 817–825 (2003).
[CrossRef]

C. Ponce and A. Singer, “Computing steerable principal components of a large set of images and their rotations,” IEEE Trans. Image Process. 20, 3051–3062 (2011).
[CrossRef]

IEEE Trans. Pattern Anal. Mach. Intell. (1)

P. Perona, “Deformable kernels for early vision,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 488–499 (1995).
[CrossRef]

J. Opt. Soc. Am. A (1)

J. Theor. Biol. (1)

Z. Kam, “The reconstruction of structure from electron micrographs of randomly oriented particles,” J. Theor. Biol. 82, 15–39 (1980).
[CrossRef]

Nature (1)

A. Klug and R. A. Crowther, “Three-dimensional image reconstruction from the viewpoint of information theory,” Nature 238, 435–440 (1972).
[CrossRef]

SIAM J. Imaging Sci. (1)

A. Singer and H.-T. Wu, “Two-dimensional tomography from noisy projections taken at unknown random directions,” SIAM J. Imaging Sci. 6, 136–175 (2013).
[CrossRef]

Ultramicroscopy (1)

M. van Heel and J. Frank, “Use of multivariate statistics in analysing the images of biological macromolecules,” Ultramicroscopy 6, 187–194 (1981).
[CrossRef]

Other (1)

J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State (Oxford, 2006).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1.
Fig. 1.

Eigenvalues of (ΨΨ)1, where Ψ is the truncated Fourier–Bessel transform for L=6 and L=60 pixels respectively. This is also the spectrum of transformed white noise images (see text). The eigenvalues are close to 1, indicating that the discretized Fourier–Bessel transform is approximately unitary and that white noise remains approximately white. For L=60, among the eigenvalues, only 18 are above 1.05 and 34 are below 0.95. For L=6, among the eigenvalues, there are 6 below 0.95.

Fig. 2.
Fig. 2.

Illustration of the block diagonal structure of the rotational invariant covariance matrix. The block size shrinks as the angular frequency k increases.

Fig. 3.
Fig. 3.

Simulated 70S ribosome projection images with different SNR.

Fig. 4.
Fig. 4.

Eigenimages for 104 simulated 70S ribosome projection images. Clean images: (a) FBsPCA, (b) traditional PCA, and (c) PTsPCA. Noisy images with SNR=(1/50): (d) FBsPCA, (e) traditional PCA, and (f) PTsPCA. Image size is 129×129 pixels and L=55 pixels.

Fig. 5.
Fig. 5.

Histogram of eigenvalues of C(k) (with k=0, 1, 20) for images consisting of white Gaussian noise with mean 0 and variance 1. The dashed lines correspond to the Marčenko–Pastur distribution. n=104, L=55 pixels and σ2=1.

Fig. 6.
Fig. 6.

Eigenvalues for C(0) and C(10) for simulated projection images with different SNRs.

Fig. 7.
Fig. 7.

Denoising by FBsPCA, PTsPCA, and PCA. n=104 and L=55 pixels. (a) clean image. (b) noisy image (SNR=(1/20)). (c) FBsPCA denoised. (d) PTsPCA denoised. (e) PCA denoised.

Tables (1)

Tables Icon

Table 1. Denoising Effect: FBsPCA, PTsPCA, and PCA

Equations (24)

Equations on this page are rendered with MathJax. Learn more.

ψkq(r,θ)={NkqJk(Rkqr)eikθ,r10r>1,
Jk(Rkq)=0.
02π01ψkq(ψkq)*rdrdθ=1.
Nk,q=1π|Jk+1(Rkq)|.
F(f)(k0,ϕ0)=02π0f(r,θ)e2πik0rcos(θϕ0)rdrdθ.
F(ψkq)(k0,ϕ0)=2π(1)q(i)kRkqJk(2πk0)(2πk0)2Rkq2eikϕ0.
eizcosθ=n=inJn(z)einθ.
Rkq2πL2,
Jk(Rkqr)2πRkqrcos(Rkqrkπ2π4)
Rkqπ2(k+2q12),
k+2q2L+12.
I˜i(r,θ)=k=2L2Lq=1pkak,qiψkq(r,θ),
ai=(ΨΨ)1ΨIi.
CA=ACA.
I˜iα(r,θ)=I˜i(r,θα)=k,qak,qieikαψkq(r,θ).
I˜ir(r,θ)=I˜i(r,πθ)=k,qak,qiψkq(r,πθ)
=k,qak,qiψkq(r,θ).
I˜mean(r,θ)=12ni=1n12π02π[I˜iα(r,θ)+I˜iα,r(r,θ)]dα.
I˜mean(r,θ)=q=1p0(1ni=1na0,qi)ψ0q(r,θ).
C=12ni=1n12π02π[(I˜iαI˜mean)(I˜iαI˜mean)+(I˜iα,rI˜mean)(I˜iα,rI˜mean))]dα.
a0,qia0,qi1ni=1na0,qi.
C(k,q),(k,q)
=14πni=1n02π[ak,qi(ak,qi)*+ak,qi(ak,qi)*]ei(kk)αdα=δk,k1ni=1nR{ak,qi(ak,qi)*}.
C=k=02LC(k),

Metrics