An equivalent definition of the histogram of forces: Theoretical and algorithmic implications

The relative position between two 2-D spatial regions is often represented quantitatively by a force histogram. In the case of raster data, force histograms are usually computed in O(KN√N)O(KN√N) time, where N is the number of pixels in the image and K is the number of directions in which forces are considered. When the regions are defined as fuzzy sets instead of crisp sets, the complexity also depends on the number M   of possible membership degrees. In this paper, we show that the force histogram can be defined in a completely different but equivalent way, one which leads to an O(NlogN) algorithm, with complexity independent of K and M. Moreover, the equivalent definition is better adapted to the solving of theoretical issues. We use it here to determine the behavior of the force histogram towards any invertible affine transformation.