Multidimensional overlap-add and overlap-save for correlation and convolution

When two signals or images to be correlated or convolved are of different sizes, overlap-add (OLA) and overlap-save (OLS) algorithms are often employed to reduce computational complexity. In this paper, we investigate the use of these algorithms for multidimensional correlations required in many image and video matching applications. In contrast to conventional wisdom, we show that OLA is more computationally efficient and OLS is more memory efficient. We present theoretical expressions for computational complexity for an arbitrary dimensionality and validate these expressions experimentally. We also discuss parameter selection from both memory and computational perspectives.