Convolution

Convolution (see wikipedia) is used in the GeoDms to calculate a Neighbourhood Potential using an input grid with n*m elements and a kernel of k*j elements, see the description of the Potential function.

The GeoDms utilizes the IPP 7.0 library convolution functions ippsConv_16s_Sfs, ippsConv_32f, ippsConv_64f in the OperPot.cpp code unit as default implementation for potential calculations. These functions perform an FFT on both their input arrays of size N, then multiply the spectra element-wise and then reverse-FFT the product to generate the requested result. The IPP 7.0 library also utilizes multiple cores when present and available. This results in a O(N*log(N)) operation, whereas the classical naive implementation with four nested loops (still available as potentialSlow for comparison) requires O(n*m*k*j) operations.

To make this possible, the 2D n * m grid and k * j grid are translated to two uniform signals of N = (n+k−1) * (m+j−1) elements each with appropriate zero-padding.

The resulting grid can sometimes contain small round-off errors resulting from different frequencies that have to cancel-out, especially in empty zero-valued regions sometimes very small values occur, sometimes even negative when all input is non-negative. In order to remove these undesired artifacts, a smoothing post-processing is performed by default that resets to zero all values that are nearer to zero than $\sqrt{\sum\limits_i(v_i^2) \over 1000000000.0}$. The raw variants (potentialRaw64 and potentialRawPacked) do not perform this post-processing.

note: polygon convolution (Minkowski sum)

Convolution also has a boolean analogue for polygons: polygon convolution, also known as the Minkowski sum. It is the convolution of mappings of F² → Bool, represented by polygons that indicate the boundary of the closed subset(s) of F² that are mapped onto TRUE, where addition is replaced by the or operation. The convolution operator, here represented as , then has type (F²→Bool*) × (F²→Bool) → (F²→Bool), and for each q ∈ F² and M_a, M_b ∈ F² → Bool:

(M_a*M_b)q := ⋁_{p ∈ F²} : M_a(p) ∧ M_b(q−p)

Further let P_i := δ**M_i, it seems that δ(M_a*M_b) = δ**M_a * M_b ∧ M_a * δ**M_b similar to the differential of the product of two functions.

ToDo

Investigate FFTW as substitute for IPPS 7.0

• http://www.fftw.org/fftw-paper-ieee.pdf