[ANN] Sliding-Window Fast Local (Pearson) Correlation Coefficients

Package Announcements
, ,
1

Calculate the local (Pearson) correlation coefficients between a needle and all sliding windows of the same size within a haystack. The best match is where the coefficient is the largest. Find the needle even when your copy is scaled and translated. The implementation supports any dimension tensors of reals or complex values.

julia> using FastLocalCorrelationCoefficients

julia> haystack = rand(ComplexF32,2^5,2^5,2^5,2^5);

julia> needle = rand(1) .* haystack[7:8,1:2,5:6,2:3] .+ rand(1);

julia> c = flcc(haystack,needle);

julia> best_correlated(c)
CartesianIndex(7, 1, 5, 2)

When you need to search for many needles of the same size,

  haystack = rand(2^20);
  needle1 = rand(1) .* haystack[2:8] .+ rand(1);
  needle2 = rand(1) .* haystack[42:48] .+ rand(1);
  needle3 = rand(1) .* haystack[end-6:end] .+ rand(1);

you can preprocess the haystack to avoid redundant computations by precomputing all common information. Such preprocessing is not possible when using the direct method.

  precomp = flcc(haystack,size(needle1));

Then use it for much faster queries.

  best_correlated(flcc(precomp,needle1)) == 2
  best_correlated(flcc(precomp,needle2)) == 42
  best_correlated(flcc(precomp,needle3)) == 2^20-6

The computation is performed in the Fourier domain, so the complexity is O(n_H \log(n_H)), instead of O(n_H n_N), where n_H and n_N denote the number of entries in the haystack and needle, respectively.

Give it a try!

7 Likes