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 between input and output 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).

Examples

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