GitHub

Convolutions - similarity methods

DSP.conv — Function
conv(u, v; algorithm)

Convolution of two arrays. A convolution algorithm is automatically chosen among direct convolution, FFT, or FFT overlap-save, depending on the size of the input, unless explicitly specified with the algorithm keyword argument; see conv! for details.

source
conv(u,v,A)

2-D convolution of the matrix A with the 2-D separable kernel generated by the vector u and row-vector v. Uses 2-D FFT algorithm.

source
DSP.conv! — Function
conv!(out, u, v; algorithm=:auto)

Convolution of two arrays u and v with the result stored in out. out must be large enough to store the entire result; if it is even larger, the excess entries will be zeroed.

out, u, and v can be N-dimensional arrays, with arbitrary indexing offsets. If none of them has offset axes, size(out,d) ≥ size(u,d) + size(v,d) - 1 must hold. If both input and output have offset axes, firstindex(out,d) ≤ firstindex(u,d) + firstindex(v,d) and lastindex(out,d) ≥ lastindex(u,d) + lastindex(v,d) must hold (for d = 1,...,N). A mix of offset and non-offset axes is not permitted.

The algorithm keyword allows choosing the algorithm to use:

  • :direct: Evaluates the convolution sum in time domain.
  • :fft_simple: Evaluates the convolution as a product in the frequency domain.
  • :fft_overlapsave: Evaluates the convolution block-wise as a product in the frequency domain, overlapping the resulting blocks.
  • :fft: Selects the faster of :fft_simple and :fft_overlapsave (as estimated from the input size).
  • :fast: Selects the fastest of :direct, :fft_simple and :fft_overlapsave (as estimated from the input size).
  • :auto (default): Equivalent to :fast if the data type is known to be suitable for FFT-based computation, equivalent to :direct otherwise.
Warning

The choices made by :fft, :fast, and :auto are based on performance heuristics which may not result in the fastest algorithm in all cases. If best performance for a certain size/type combination is required, it is advised to do individual benchmarking and explicitly specify the desired algorithm.

source
DSP.deconv — Function
deconv(b,a) -> c

Construct vector c such that b = conv(a,c) + r. Equivalent to polynomial division.

source
DSP.xcorr — Function
xcorr(u; padmode::Symbol=:none, scaling::Symbol=:none)
xcorr(u, v; padmode::Symbol=:none, scaling::Symbol=:none)

With two arguments, compute the cross-correlation of two vectors, by calculating the similarity between u and v with various offsets of v. Delaying u relative to v will shift the result to the right. If one argument is provided, calculate xcorr(u, u; kwargs...).

The size of the output depends on the padmode keyword argument: with padmode = :none the length of the result will be length(u) + length(v) - 1, as with conv. With padmode = :longest, the shorter of the arguments will be padded so they are of equal length. This gives a result with length 2*max(length(u), length(v))-1, with the zero-lag condition at the center.

The keyword argument scaling can be provided. Possible arguments are the default :none and :biased. :biased is valid only if the vectors have the same length, or only one vector is provided, dividing the result by length(u).

Note

In this package, xcorr conjugates the second argument v, choosing the same convention as MATLAB's xcorr and scipy.signal.correlate. This differs from the inner product convention more prevalent in physics, that conjugates the first vector.

Examples

julia> xcorr([1,2,3],[1,2,3])
5-element Vector{Int64}:
  3
  8
 14
  8
  3
source