Image analysis II C9940 3-Dimensional Transmission Electron Microscopy S1007 Doing structural biology with the electron microscope March 16, 2015 Outline Image analysis II Fourier transforms revisited Digitization Alignment Multivariate data analysis Outline Image analysis II Fourier transforms revisited Digitization Alignment Multivariate data analysis Fourier transforms: Definition f: function (1D) which we are transforming x: real-space coordinate i: √-1 k: spatial frequency F(k): Fourier coefficient at frequency k – complex, of the form a + bi Fourier transforms: Definition Euler's Formula: Fourier transforms: Definition ba +i a b Amplitude, A: Phase, Ф: Ф A Fourier transforms: plot of cosine of x x f(x) Fourier transforms: plot of step function The higher the spatial frequencies (i.e., higher resolution) that are included, the more faithful the representation of the original function will be. http://cnx.org Fourier transforms: plot of sawtooth function http://mathworld.wolfram.com How do we calculate the Fourier coefficients? Fourier transforms: Definition ba +i a b Amplitude, A: Phase, Ф: Ф A Why aren't we calculating the cosine terms? Fourier transforms: Sawtooth function Fourier transforms: plot of a Gaussian Xx f(x) F(X) Outline Image analysis II Fourier transforms revisited Digitization Alignment Multivariate data analysis Digitization in 2D Digitization in 1D: Sampling Digitization: Is our sampling good enough? Here, our sampling is good enough. Digitization in 1D: Bad sampling What's the best resolution we can get from a given sampling rate? A 4-pixel “image” 1 2 3 4 In other words, what is the most rapid oscillation we can detect? What's the best resolution we can get from a given sampling rate? In other words, what is the most rapid oscillation we can detect? ANSWER: Alternating light and dark pixels. A 4-pixel “image” The period of this finest oscillation is 2 pixels. The spatial frequency of this oscillation is 0.5 px-1 . The finest detectable oscillation is what is known as “Nyquist frequency.” The edge of the Fourier transform corresponds to Nyquist frequency. The period of this finest oscillation is 2 pixels. The spatial frequency of this oscillation is 0.5 px-1 . The finest detectable oscillation is what is known as “Nyquist frequency.” The edge of the Fourier transform corresponds to Nyquist frequency. origin spatial frequencyspatial frequency Nyquist frequency Nyquist frequency What do we mean by pixel size? 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. Interpolation 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. 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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. Outline Image analysis II Fourier transforms revisited Digitization Alignment Multivariate data analysis (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. How do find the relative translations between two images? Cross-correlation coefficient: Translational alignment 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 Cross-correlation coefficient Cross-correlation coefficient: If the alignment is perfect, the correlation value will be 1. What if the correlation isn't perfect? Translational alignment 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). 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. Real space f(x) g(x) Some notation: Fourier space F(X) G(X) Cross-correlation function (CCF) Image f(x) Image g(x) F.T. F*(X) (complex conjugate) F.T. G(X) x = CCF The position of the peak gives us the shifts that give the best match, e.g., (8,-6). (8,-6) 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. 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 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. Different alignment schemes 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 Digitization Alignment Multivariate data analysis Multivariate data analysis (MDA), or Multivariate statistical analysis (MSA) 1 1-pixel image http://isomorphism.es #Images Intensity Multivariate data analysis (MDA), or Multivariate statistical analysis (MSA) 1 2-pixel image 2 Pixel2 Pixel 1 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) 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 64 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 + ... 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 Some simple 1D transforms: a 1D lattice Some simple 1D transforms: a box http://cnx.org Some simple 1D transforms: a Gaussian Some simple 1D transforms: a sharp point (Dirac delta function) http://en.labs.wikimedia.org/wiki/Basic_Physics_of_Nuclear_Medicine/Fourier_Methods Some simple 2D Fourier transforms: a row of points Some simple 2D Fourier transforms: a 2D lattice Some simple 2D Fourier transforms: a sharp disc Some simple 2D Fourier transforms: a series of lines