Image analysis II C9940 3-Dimensional Transmission Electron Microscopy S1007 Doing structural biology with the electron microscope April 4, 2016 Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis Outline Outline Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis http://www.ysbl.york.ac.uk/~cowtan/fourier/magic.html A quiz: A problem I had with my first attempt QUESTION: Where did that cross come from? Apodization: Smoothly bring the signal to zero near an edge Outline Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis Why are electrons useful? Wavelengths of various radiation types Visible light: >380nm X-rays (copper K): 0.154nm (1.54Å) Electrons (300kV): 0.002nm (0.02Å) How wavelength limits resolution 1/λ S O S: specimen origin O: diffraction origin 1/λ http://en.wikipedia.org NOTE: Not to scale. EM wavelength is ~80 smaller, and therefore 1/λ would be 80X bigger. X-ray EM X-ray NOTE 2: For practical purposes, the radius of the Ewald sphere is so large that we ignore its curvature. EM 1/λ NOTE 3: Electron lenses are terrible, and biological samples are fragile, so in practice we'll see on a tiny fraction of the data we could theoretically get. Resolution 1/λ NOTE 4: For more information, see DeRosier (2000) “Correction of high-resolution data for curvature of the Ewald sphere.” What we assume Preview: 3D reconstruction Preview: reconstruction 1 2 5 4 3 678 Outline Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis origin spatial frequency From Wikipedia From last week... This is an example of aliasing. An example using SPIDER https://youtu.be/6LzaPARy3uA?t=51 Outline Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis QUESTION: Why do we need to average the signal from many images? ANSWER: Our signal-to-noise is poor 200200ÅÅ aligned images 1-4 of 4096 total unaligned images 1-4 of 4096 total This is a simple 2D case, but the effects are analogous in 3D. What happens if we don't align our images? n=1 n=4 n=16 n=256 n=1024 n=4096 Signal-to-noise ratio increases with √n What happens as we include more particles? (P)review of 3D reconstruction: The parameters required Two translational:  Δx  Δy Three orientational (Euler angles):  phi (about z axis)  theta (about y)  psi (about new z) http://www.wadsworth.org These are determined in 2D. We'll concentrate on these 1st . How do find the relative translations between two images? Cross-correlation coefficient: Cross-correlation Image f Image g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 constant “normalization” Cross-correlation Image f Image g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Unnormalized CCC = + f2 g2 + f3 g3 + f4 g4 + f5 g5 + f6 g6 + f7 g7 + f8 g8 + f9 g9 + f10 g10 + f11 g11 + f12 g12 + f13 g13 + f14 g14 + f15 g15 + f16 g16 f1 g1 Cross-correlation Image f Image g Unnormalized CCC = + f2 g2 + f3 g3 + f4 g4 + f5 g5 + f6 g6 + f7 g7 + f8 g8 + f9 g9 + f10 g10 + f11 g11 + f12 g12 + f13 g13 + f14 g14 + f15 g15 + f16 g16 f1 g1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Cross-correlation coefficient Cross-correlation coefficient: If the alignment is perfect, the correlation value will be 1. What if the correlation isn't perfect? Cross-correlation Image f Image g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 What if the correlation isn't perfect? ANSWER: You try other shifts (perhaps all). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (2, 2) Cross-correlation map (2, 0) We would need to repeat this for all combinations of shifts. Cross-correlation function (CCF) Brute-force translational search is CPU-intensive BUT Fourier transforms can help us. Real space f(x) g(x) Some notation: Fourier space F(X) G(X) Cross-correlation function (CCF) Brute-force translational search is CPU-intensive BUT Fourier transforms can help us. Complex conjugate: If a Fourier coefficient F(X) has the form: a + bi The complex conjugate F*(X) has the form: a - bi F*(X) G(X) = F.T.(CCF) This gives us a map of all possible shifts. Cross-correlation function (CCF) Image f(x) Image g(x) F.T. F*(X) (complex conjugate) F.T. G(X) x = F.T. (CCF) The position of the peak gives us the shifts that give the best match, e.g., (8,-6). (8,-6) Well, that was an easy case. We only needed to do translational alignment. What about orientation alignment? Orientation alignment Image 1 Image 2 We take a series of rings from each image, unravel them, and compute a series of 1D cross-correlation functions. Shifts along these unraveled CCFs is equivalent to a rotation in Cartesian space. Noiseadded Reference image 0 3600 360 Polar representation Orientation alignment Image 1 Image 2 radius 1 radius 2 radius 3 radius 4 radius 1 radius 2 radius 3 radius 4 0 360 0 360 Orientation alignment radius 1 radius 2 radius 3 radius 4 0 360 0 360 Orientation alignment: After rotation Which do you perform first? Translational or orientation alignment? Translational and orientation alignment are interdependent SuperimposedImage 1 Image 2 SOLUTION: You try a set of reasonable shifts, and perform separate orientation alignments for each. Set of all new shifts of up to 2 pixels Set of all shifts of up to 1 pixel Translational and orientation alignment are interdependent Shifts of (0, +/-1, +/-2) pixels results in 25 orientation searches. Outline Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis How to apply the best shift and rotation? Shifts 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Suppose we shift the image in x & y. The new pixels will be weighted averages of the old pixels. The more the mix the pixels, the worse the result will be. original Δx=Δy=0.05px Δx=Δy=0.10px Δx=Δy=0.15px Δx=Δy=0.20px Δx=Δy=0.25px Δx=Δy=0.30px Δx=Δy=0.35px Δx=Δy=0.40px Δx=Δy=0.45px Effect of shifts Two more properties of Fourier transforms: Noise The Fourier transform of noise is noise “White” noise is evenly distributed in Fourier space • “White” means that each pixel is independent White noise Power spectrum origin Nyquist frequency spatial frequencyspatial frequency Effects of interpolation are resolution-dependent Image Power spectrum Profile OriginalShiftedby(0.5,0.5)px Rotation 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Suppose we rotate the image. The new pixels will be weighted averages of the old pixels. Rotation 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Suppose we rotate the image. New pixel #9 will be a weighted sum of old pixels 99, 1010, 1313, and 1414. Image Power spectrum Power spectrum profile OriginalShiftedby(0.5,0.5)pxRotatedby45º The degradation of the images means that we should minimize the number of interpolations. From two weeks ago... http://www.en.wikipedia.org Typical magnification: 50,000X Typical detector element: 15μm (pixel size on the camera scale) Pixel size on the specimen scale: 15 x 10-6 m/px / 50000 = 3.0 x 10-10 m/px = 3.0 Å/px In other words, the best resolution we can achieve (or, the finest oscillation we can detect) at 3.0 Å/px is 6.0 Å. It will be worse due to interpolation, so to be safe, a pixel should be 3X smaller than your target resolution. Different alignment strategies Reference-based alignment There's a problem with reference-based alignment: Model bias Model bias Reference Images of pure noise Averages of images of pure noise N = 128 N = 256 N = 512 N = 1024 N = 2048 original There are reference-free alignment schemes Reference-free alignment (SPIDER command AP SR) Single image picked randomly as reference Disadvantage: Alignment depends on the choice of random seed. Pyramidal/pairwise alignment Marco... Carrascosa (1996) Ultramicroscopy You have aligned images, but they don't all look the same. Outline Image analysis II Fourier transforms revisited Ducks and other animals Analogy to the Ewald sphere Aliasing Alignment Interpolation Multivariate data analysis A one-pixel image 1 1-pixel image http://isomorphism.es #Images Intensity A two-pixel image 1 2-pixel image 2 Pixel2 Pixel 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A 16-pixel image Now, we have a 16-dimensional problem. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Multivariate data analysis (MDA), or Multivariate statistical analysis (MSA) Suppose pixel 6 coincided with pixel 11, And pixel 7 coincided with pixel 10. Then, we're back to two variables, and a 2D problem. 1 2 3 4 9 10 11 125 6 7 8 13 14 15 16 Multivariate data analysis (MDA), or Multivariate statistical analysis (MSA) Our 16-pixel image can be reorganized into a 16-coordinate vector. Covariance of measurements x and y: - , where is the mean of x. A high covariance is a measure of the correlation between two variables. MDA: An example 8 classes of faces, 64x64 pixels With noise added From http://spider.wadsworth.org/spider_doc/spider/docs/techs/classification/tutorial.html Average: Principal component analysis (PCA) or Correspondence analysis (CA) For a 4096-pixel image, we will have a 4096x4096 covariance matrix. Row-reduction of the covariance matrix gives us “eigenvectors.” • The eigenvectors describe correlated variations in the data. • The eigenvectors have 4096 elements and can be converted back into images, called “eigenimages.” • The first eigenvectors will account for the most variation. The later eigenvectors may only describe noise. • Linear combinations of these images will give us approximations of the classes that make up the data. Eigenimages Reconstituted images Linear combinations of these images will give us approximations of the classes that make up the data. Average Eigenimage #1 Eigenimage #2 Eigenimage #3 c0 + c1 + c2 + c3 + ... A reminder of what our original images looked like Another example: worm hemoglobin Phantom images of worm hemoglobin PCA of worm hemoglobin Average: +c0 -c0 +c1 +c2 +c3 +c4 +c5 -c1 -c2 -c3 -c4 -c5 Next week: Classification & 3D Reconstruction