Description of the Autocorrelation Plugin for ImageJ written by Markus Hasselblatt
<![if !supportLists]>· <![endif]>General Remarks
<![if !supportLists]>· <![endif]>Averaging Algorithm
<![if !supportLists]>· <![endif]>User choices
<![if !supportLists]>· <![endif]>Contacts
<![if !supportLists]>· <![endif]>Literature
Often, SPM micrographs contain repetative features. For instance, crystal lattices, or periodic arrays of microstructures yield multiple occurences of similar features in one image. This is also the case for many biological samples spread on a flat substrate.
Here, we present a novel approach to enhance the interpretation of such data based on the combination of linear correlation and bilinear bitmap rotation to average over multiple occurences of the same feature in one SPM micrograph. Essentially, our procedure is similar to summing up spectra in any kind of spectroscopy, or adding images acquired with electron microscopies.
Our novel data analysis employs a linear correlation procedure to identify areas within a bitmap that are similar to a preselected subregion of the bitmap. Areas found in this way are then incrementally rotated 360deg while the linear correlation between the rotated area and the initially selected region is calculated.
For each subregion, the bitmap rotated about the angle where this correlation had a maximum is used to calculate the average of bitmaps. This procedure can be used to successfully increase the signal to noise ratio of SPM data and gain more confidence in data analysis of repetitive features.
This flow chart illustration of the averaging algorithm visualizes its use:
The original bitmap (upper left) is used to visually identify a region of interest. This region of interest should contain a good representative of the repetitive feature for which an average is sought. Also, the region of interest should be aligned such that the center of rotation is in the middle of the selected area. A centered sample bitmap ensures that similar bitmaps can be correctly rotated in respect to this choice.
Once the sample bitmap, or kernel, is chosen, the algorithm will calculate the linear correlation coefficient for each sub-bitmap of the original image, which has the same dimensions. This yields a two-dimensional map of the correlation coefficient. Since sub-regions of the original bitmaps are compared, we have termed this map autocorrelation function (ACF).
The ACF for the bitmaps chosen in the flow chart is shown in the lower left. Note that white spots indicate high correlation and dark areas show little correlation as the coefficient range of -1 to +1 is mapped from black (equals -1) to white (equals +1). The ACF is then used to identify regions in the original bitmap, which are similar to the selected sample. This corresponds to the location of maxima of the ACF. Because the absolute value of the linear correlation coefficient has no statistical meaning, a threshold value has to be selected by the user at this point. It should be chosen such, that a reasonable sample of similar regions is selected in the original bitmap. Typically this will take some repeated trials.
As a threshold is chosen, the algorithm will find all maxima of the ACF, whose linear correlation coefficient is higher than the given value. Bitmaps corresponding to these maxima are then added to yield the kernel average (middle bottom of the flow chart). This is the minimal cycle of the averaging algorithm.
In addition, the rotation of bitmaps can be allowed before the average is calculated. In this case, bitmaps selected from maxima of the ATCF are rotated and the linear correlation between the kernel and the rotated bitmap is calculated. The angle of rotation maximizing this correlation is used to rotate the respective bitmap before averaging. However, only rotated bitmaps exceeding a second threshold value for linear correlation are used in the rotational average (middle of flow chart).
Proper use of the two threshold values ensures that similar patterns with different rotational alignment on the surface are caught in the ATCF even though their unrotated correlation is low. Typically, the threshold to choose possible matches is lower than the value selected for the rotational average.
As mentioned earlier, the center of rotation must coincide with the center of the selected kernel. Since this is done visually, errors are to be expected. To account for this, a displacement of a region corresponding to maxima of the ACF in a specified range may be used. Again, the bitmap maximizing the linear correlation with the sample kernel is used to calculate the average (middle-top of flow chart).
The right side of the flow chart shows typical images generated by the averaging algorithm. Rotated and unrotated kernel averages can be used to visually inspect the results. Averages from two independent sets of matching bitmaps have been used to compare the reproducibility of their results (Frank et al., Saxton et al.). The same has been done in this work and the difference between such averages was used for this purpose. An example of such a difference is shown in the lower right of the chart.
Finally, as a refinement (Saxton et al.),the kernel average obtained in a previous pass can be used to recalculate the ACF. Also, the rotational average can be used as a comparison for the selection of matching bitmaps for the calculation of a new rotational average.
In the following, a brief description of the settings to be chosen in the algorithm is presented.
After choosing a representative subregion of the bitmap to be analyzed, the macro is started by selecting Autocorrelation with the mouse. Immediately, the ACF will be calculated. The user will then be prompted for a threshold value to select maxima of the ACF in a window called “Set Cutoff”. The threshold is supplied in percent, where 100% means total correlation (ACF = 1) and 0% means anticorrelation (ACF = -1). Typically, values of 65-85% will yield good results depending on the type of image studied. Furthermore, the user can set four switches:
<![if !supportLists]>1. <![endif]>Use Average Kernel
Will cause the algorithm to recalculate the ACF using an average kernel instead of the initially selected region. This option requires the algorithm to have run at least one previous time.
<![if !supportLists]>2. <![endif]>Finished
Will cause the algorithm to finish after completing the following iteration.
<![if !supportLists]>3. <![endif]>Rotate Kernel
Will cause the algorithm to enter the rotation part of the algorithm, in which a rotation of bitmaps is taken in to account before averaging the kernel.
<![if !supportLists]>4. <![endif]>Save Crosses
Will save the crosses indicating the maxima found in bitmap. This is an option to be used for presentation purposes. Please note that this ALTERS your original data by adding crosses directly into the bitmap.
In case the option Rotate Kernel was chosen, the user is prompted for a second threshold value used to select bitmaps in the rotation part of the algorithm. This window is called “Set Rotation Threshold”. Again, the threshold is supplied in percent. To account for a poor selection of centers of rotation, a displacement constant can be supplied. This must be an odd number and will cause the rotation algorithm to calculate the rotation correlation for a set of bitmaps with the center within the range of displacement supplied. Furthermore, four additional switches can be set:
<![if !supportLists]>5. <![endif]>Check finely spaced set of angels
Will set the rotation increment to 0.5deg in stead of four degrees. This option allows the user to toggle between “high” angular resolution (long computing time) vs. “low” angular resolution (fast computing).
<![if !supportLists]>6. <![endif]>Actually, do NOT rotate
Will cause the algorithm to ignore the rotation part in case the user mistakenly set the switch “Rotate Kernel” in the window “Set Cutoff”.
<![if !supportLists]>7. <![endif]>Save time, show NO rotation
The algorithm will not display the rotated bitmaps as it is calculating the rotational ACF.
<![if !supportLists]>8. <![endif]>Use Rotation Average as Kernel
The equivalent of “Use Average Kernel” for the rotation.
Please note that I take no responsibility for results generated by this algorithm. This plugin is open-source. You are free to do anything you want with this source as long as I get credit for my work and you offer your changes to me and to Wayne Rasband, author of ImageJ, so we can possibly add them to the "official" version.
Markus Hasselblatt: email@example.com
Wayne Rasband: firstname.lastname@example.org
Frank, J. and Boublik, M. (1981). Computer Averaging of Electron Micrographs of 40s Ribosomal Subunits, Science 214: 1353.
Saxton, W. O. and Baumeister, W. (1982). The Correlation Averaging of a Regularly Arranged Bacterial Cell Envelope Protein, Journal of Microscopy 127: 127.