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

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