FirFilter (DSP) computes correlation, not convolution

[J-M-White]

In the reference for the FirFilter class, it states that it "represents an operator that convolves the input signal with a finite-impulse response filter kernel"; however, it seems to use OpenCV's filter2D function which instead correlates the input with the kernel.

To test this, you can use FirFilter to filter a Kronecker delta input. If it was computing the convolution, then the output would be the kernel of the filter. Instead, the output is the mirror image of the kernel. One workflow that can do this test is shown below, where the middle float is set to 1, while all the others are set to 0. I used a kernel of [1, 2].

I think the best fix would be to update the docs to clarify this distinction.

[glopesdev]

@J-M-White thanks for bringing this up, it is definitely an important point that deserves clarification. The OpenCV docs are themselves confusing since the first sentence also mentions convolution and only later they clarify that actually the operator computes the correlation.

I think the historical reason for this is the close relationship that exists between convolution and correlation, and specifically the implicit understanding that you can actually compute the convolution using a correlation operator (by flipping the kernel left-to-right). Indeed, if the filter kernel is centered and mirror-symmetric, the correlation kernel is also a convolution kernel, which is a very common property of several filter kernels, and also the property we leverage when designing the other DSP filters built on top of FirFilter in the package.

I think this detail is something we probably should preserve in the final corrected docs, but any feedback would be very much appreciated.

[J-M-White]

@glopesdev I absolutely agree - I would imagine that the vast majority of use cases for FirFilter are with linear phase, (anti-)symmetric FIR filters where the distinction isn't important.

I only came across this issue because I was using FirFilter to do matched filtering of a signal with an asymmetric kernel. Based on the description in the docs, I had "pre-flipped" my kernel to account for FirFilter performing a convolution. This ended up being incorrect.

As this is probably not a common issue (especially given that MatchTemplate also exists), I think that adding an extra line similar to the one in the OpenCV docs ("The function does actually compute correlation, not the convolution") would prevent others from making the same mistake as me in future.

[glopesdev]

@J-M-White this is apparently a common implementation trope:

• https://ai.stackexchange.com/a/22000
• https://glassboxmedicine.com/2019/07/26/convolution-vs-cross-correlation/

In fact, both TensorFlow and PyTorch also implement "convolution" operators as cross-correlation: https://medium.com/@stevechange/a-quick-journey-through-conv1d-functions-from-tensorflow-to-pytorch-passing-via-scipy-bf830b922b3e

Similar to OpenCV, in their documentation they also misleadingly claim that it does a convolution:

• tf.keras.layers.Conv1d
• torch.nn.Conv1d

An interesting realization coming from this is that convolutional neural networks might then be best described as "correlational neural networks", but I guess it doesn't sound so cool, and the claim is it doesn't really matter since learning algorithms will just as easily learn a flipped or straight kernel.

Given this, I think I will add the clarification as a remark, similar to all these cases, saying something to the effect of:

"This operator is implemented using cross-correlation. If kernels are symmetric, there is no difference between correlation and convolution. When using asymmetric kernels, note the kernel needs to be flipped to obtain a true convolution."