Fast Fourier Transform Based Force Histogram Computation for 3D Raster Data

Abstract

The force histogram is a quantitative representation of relative position between two objects. For 2D data, two algorithms are defined: a well-functioning line-based algorithm, and Fast Fourier Transform (FFT) based algorithm that has a high computational cost. The line-based algorithm has previously been extended to the 3D case, but found to be unstable, and affected by a variety of factors. This thesis presents an extension of the FFT-based algorithm to the 3D case along with an analysis that demonstrates that, with the exception of a few special cases, the computational time of the 3D FFT-based algorithm is less than the line-based version. In addition, the results included here shown that the FFT-based algorithm is independent of the number of directions, the types of forces, and the shapes of the objects (convex, concave, disjoint or overlapping).