Volume Correlation

1. User level documentation - how to use this group of programs on a daily basis.
2. General Explanation - theory on partitions and why things are why they are
3. Programmer level documentation - in depth explanation of code, for ease of modification
4. Acknowledgements

1. User level documentation OR: How I Learned to Stop Worrying And Use 688 Lines Of Code

2. • Purpose
     The purpose of VolCorr and VCWH is to create control points to align two 3D double-tilt reconstructions of the same object created by SPIDER. Often, reconstructions of the same object after a 90 degree rotation have noticeable differences in the location of organelles, regions, etc. that can not be explained. This group of programs select regions in one reconstruction, and then search for and return the placement of the best fit of the region in the second reconstruction. The position of the searched for regions in each volume is output as a document file, VCOutput.bat. At the time of writing this, modification of a warp program is underway to perform the actual warping, using this information.
   • Assumptions/Caveats/Warnings
     
     1. The two reconstructions(volumes) to be compared must be of the same size. This should not be a problem considering the two volumes are of the same object.
     2. The volumes should be aligned in the same direction. There is a built in limitation of how far the program will search for the best fit region in the second volume. This limit is based on how many partitions are created(see 2.1 and 3.0 326-58). Alignment should be based on real life arrangement of the sample.
     3. Only translation is accounted for. If you have reason to believe that there is large scale rotation BETWEEN your volumes, consult Bimal's paper/program(see 4.0).
     4. This program searches and correlates REGIONS of space. This takes into accounts specific organelles, local regions, as well as background density. It selects the search region from the first volume, and finds the best fit of the entire region, within a certain distance. If you are trying to find certain objects or organelles, look at Bimal's paper/program(see 4.0).
     5. That all three files and test data are in the same folder. If not, you may have to type in file names accordingly different.
     6. Any other applicable limitations either of Bimal's work or Roseman's paper (see 4.0).
     
     
     
   • Directions For Daily Use
     What follows is a list of general steps on how to manipulate a reconstruction, to produce the best correlations and why. It is based only on my experience and therefore may include extra, or accidentally omit, steps that you might find useful. The entire purpose of steps (1.3.1 to 1.3.6)is to align the volumes correctly and remove random noise in each reconstruction.
     1. Obtain two(or more) 3D reconstructions of the same sample. There is no reason that I know of why they could not be single tilt, other than they contain less information.
     2. View the volumes, in their entirity, either with WEB or some other program. The purpose of this is to insure that the volumes are aligned in the same manner. If not, use RT 90 in SPIDER to align if at all possible. RT 90 preserves more information than other rotate commands.
     3. After you are sure that the volumes are aligned properly, use the Commands->Histogram option in WEB to view the histogram of each volume. Take note of the PERCENTAGE where the bell curve shape become too elongated on either end for each volume. It should be roughly the same for each. In my experience, the gold specks that are used in the samples drastically skew the histogram tails outward. This forces a limited number of grey scales to represent the full spread of density values. Resulting in the usable sample information contained in a very small amount of the grey scale, so that you can not see where the "noise" ends and the true information begins. This knowledge is used later.
     4. With the percentage values required to make each volume's histogram more "bell-curvy" open hc.bat.
     5. Change the name directly after[infile] to the full path name needed to find the first volume.
     6. Change after [outfile] to the name and location of where the "compressed" image will be made. This needs to be a different name than the source because a)SPIDER won't rewrite the source and b)the source will be used later.
     7. Change the values of x50,x51 to that the needed % values are in DECIMAL form, 58% = 0.58
     8. Run hc.bat from SPIDER
     9. View the new volumes in WEB. Select the points(slices) where the noise stops, and useful information begins. It is my experince that the most noise only occurs in the top or bottom slices, the sides are relatively usefull. If this is not the case for you, remove ANY large amounts of noise. This program is not designed to compare random noise. The amount of noisy slices removed from each volume should be equal. Equal because VolCorr requires volumes to be the same size, and if you remove uneven amounts, but still have the same size volumes, you are no longer comparing pixels correctly. This also typically removes the gold specks because they are usually found only in the noise region. A slight loss of useful data is allowable in order to remove more extreme data(gold specks and shadows).
     10. Using the SPIDER WIndow command, select the correct slices from the ORIGINAL (aligned, but not compressed) volumes, and save as new files. These new files are what will be compared. The reason you remove from the aligned, but not compressed file, is that you compare pure data. No noise AND no artifacts from thresholding.
     11. Because VolCorr is a procedure file, you must alter the file itself, no arguments allowed. In order to make that safer, ONLY CHANGE THINGS BETWEEN THE ----ALL INPUTS--- and ---END ALL INPUTS--- lines.
     12. The name/path after [secondary] is the file that the searched-for regions will come from.
     13. After [primary] is the file that the regions will be searched-in for. Which file is first or second is important because the output of VolCorr is where the points in [secondary] can be found in [primary]. This determines if you want to warp file 2 to look like file 1, or vise versa.
     14. The value after "x91 =" sets the minimum value for a pixel to be searched for. For example, if you run SPIDER's FS and set the "x91 =" value to the maximum valueof a volume, then no pixels will be searched for. A good rule of thumb is around 10% of the difference between the maximum and minimum. This value has a large effect on correlations, so if you're having problems forming reasonable correlations, examine this value.
     15. The next three variables determine the number of search regions. The number of divisions(regions) in a dimension determines how many spaces it creates in that dimension. Thus, all three multiplied together are how many regions there are in all. See Sec. 2.1 for more in depth explanation.
     16. The last three are used to determine the size of each search region. Similar to the number of regions, multiply these values together to find the volume of each region.
   
   
   
3. General Explanation - Partitions, Search Regions, and Jump Values (Oh My!)
   
   1. After many iterations of this program, I realized that a point-centric model was the most efficient way to determine and maintain the multiple spaces that are needed. The term point-centric pertains to the method of creating and locating the search regions in their respective partitions. The method determines the center of a search region or partition, and then expands from this central point, to create the space. This is instead of SPIDER's inherent system of defining the upper-left corner, then expanding from that. For variables x77-9 the term divisions is used. The easiest way of visualizing divisions is to imagine a cake. Each variable describes how many divisions in a particular dimension will be made. If x77 = 3, then there will be two cuts made. Resulting in three slices, or divisions, of cake in the X direction. This same thought process can be used for Y and Z dimensions as well. It follows that if there is 3,5,and 7 divisions in the X,Y, and Z dimensions that there will be 3*5*7=105 pieces of cake, or partitions. In order for the point-centric model to be useful, there must be one point, or voxel, that is the center of each partition. To insure this, there are tests to force each division, and therefor each partition, height to be an odd number. This central voxel of the partition is also the center point of a search region. Using the variables that are responsible for "cube size", the search cube is developed by expanding out from the center voxel. If x80 = 11, the X size of the search cube is (central point's x value minus five) to (central point's x value plus five). In this way, the point-centric method forces the search cube, and it's respective partition, to be co-centric.
   2. With the coordinates of the search region defined, it is copied out from the secondary volume and transformed into Fourier space. Then the respective partition is copied out of the primary volume and also changed into Fourier space. They are then compared to each other, and the distance between their best fit's are calculated. This distance is returnedas the output. A simple test is to compare a file to itself. The two points should be identical, as long as there is a minimum of white noise, and therefore a distnce of 0 returned.
4. Programmer level documentation

   What follows is a VERY rough, line-by-line account of what is going on, and why.

   VolCorr.bat

   • 42-85 The point-centric method requires everything to be odd, for one central voxel
   • 84-119 One of the primary assumptions is that the files are aligned correctly.
   • 121-135 Point centric: partition height = volume height/ # of divisions wanted, then make sure it's odd
   • 137-140 Calculate the center of the partition: partition height/2 the 0.5 insures the center
   • 142-171 Insure that the search cube isn't larger than it's partition
   • 173-176 For print out, just to know how much of the volume is included in the search cubes.
   • 178-181 Space between divisions:= (volume height - total partition height)/# of spaces between
   • 219 Start VolCorrWorkHorse, see top of VolCorr for variable explanation
   
   
   VCWH.bat
   WARNING due to the many incarnations of this program, some comments in VCWH may refer to similar things with different terminology than used in this ReadMe. The process is correct, but the objects affected may be different than how I describe them here. I wrote this ReadMe to be the diffinitive explanation, it SHOULD supersede any description in VCWH, but "caveat programmtor".
   • 12-14 CC stores results in the center of the image, need upper left of center window
   • 21-23 see 2.1, this is 0.5 of the search cube size, used to "expand out"
   • 26-43 similar to 142-171 above
   • 48-63 write to results file info needed to display movement
   • vectors
   • 67-72 one loop needed for each partition, or part of cake
   • 75-77 for progress display purposes
   • 79-87 using loop counters, selects the partition that will be searched in, from primary = # of divisions-1* size of partitions + space between partitions*spaces between
   • 89-92 location of corresponding search cube =corner of partition +center of partition- half the size of search cube
   • 94-99 to change print out to final points instead of vectors, x55=x52+x58
   • 101-106 select partition, from primary
   • 108-125 the actual theory is best described by others, see Roseman's paper
   • 127-131 WU=local.std.dev. returns in center, like CC, so need upper left
   • 133-137 before CC, must center the search cube in the partition
   • 139-144 select search cube from secondary
   • 146-324 see Roseman's paper
   • 326-358 this is what actually limits max. distance the search cube can be from the expected position
   • 365-372 looking for the highest points of correlation
   • 374-391 Prints out only the highest point of correlation for each partition/search cube. If more correlations are desired, place a mini-do loop around all, and change the "1" from UD S to the loop counter.
   • 393-end file clean up, end of XYZ do loops, doesn't actually delete output dir. Feel free to fix that.
   
   
   
5. Acknowledgements - Requiem For A ReadMe
   

   Heartfelt thanks to Dr. Joachim Frank and Dr. ArDean Leith, for giving me the chance to prove my mettle. With their help, I have proven how well a bioengineer with 3 programming classes can code.

   Alan Roseman whose paper found in Ultramicroscopy, Vol 94, Issues 3-4, (2003), 225-236) first developed and proved the efficacy of the algorithm.

   Bimal Rath, who first developed Roseman's paper into a viable SPIDER procedure file. His program is discussed here.

   VolCorr, VCWH, hc, and this ReadMe written by Jamie LeBarron. Please keep in mind, bad jokes are better than none at all. In regards to the length, I rated usefullness over compactness. 12/29/03