Add cross-correlation and auto-correlation (TheAlgorithms#4984)

AthinaSw · web-flow · commit 6a0c0585e453 · 2024-01-03T20:11:07.000+02:00
diff --git a/src/main/java/com/thealgorithms/maths/AutoCorrelation.java b/src/main/java/com/thealgorithms/maths/AutoCorrelation.java
@@ -0,0 +1,55 @@
+package com.thealgorithms.maths;
+
+/**
+ * Class for linear auto-correlation of a discrete signal
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 2.0
+ */
+
+public class AutoCorrelation {
+
+    /**
+     * Discrete linear auto-correlation function.
+     * Input and output signals have starting index 0.
+     *
+     * @param x The discrete signal
+     * @return The result of the auto-correlation of signals x. The result is also a signal.
+     */
+    public static double[] autoCorrelation(double[] x) {
+
+        /*
+        To find the auto-correlation of a discrete signal x, we perform cross-correlation between x signal and itself.
+        Here's an example:
+        x=[1,2,1,1]
+        y=[1,2,1,1]
+
+        i=0:      [1,2,1,1]
+            [1,2,1,1]               result[0]=1*1=1
+
+        i=1:       [1,2,1,1]
+               [1,2,1,1]            result[1]=1*1+2*1=3
+
+        i=2:       [1,2,1,1]
+                 [1,2,1,1]          result[2]=1*2+2*1+1*1=5
+
+        i=3:       [1,2,1,1]
+                   [1,2,1,1]        result[3]=1*1+2*2+1*1+1*1=7
+
+        i=4:       [1,2,1,1]
+                     [1,2,1,1]      result[4]=2*1+1*2+1*1=5
+
+        i=5:       [1,2,1,1]
+                       [1,2,1,1]    result[5]=1*1+1*2=3
+
+        i=1:       [1,2,1,1]
+                         [1,2,1,1]  result[6]=1*1=1
+
+        result=[1,3,5,7,5,3,1]
+
+
+         */
+
+        return CrossCorrelation.crossCorrelation(x, x);
+    }
+}
diff --git a/src/main/java/com/thealgorithms/maths/CrossCorrelation.java b/src/main/java/com/thealgorithms/maths/CrossCorrelation.java
@@ -0,0 +1,87 @@
+package com.thealgorithms.maths;
+
+/**
+ * Class for linear cross-correlation of two discrete signals
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 1.0
+ */
+
+public class CrossCorrelation {
+
+    /**
+     * Discrete linear cross-correlation function.
+     * Input and output signals have starting index 0.
+     *
+     * @param x The first discrete signal
+     * @param y The second discrete signal
+     * @return The result of the cross-correlation of signals x,y. The result is also a signal.
+     */
+    public static double[] crossCorrelation(double[] x, double[] y) {
+        // The result signal's length is the sum of the input signals' lengths minus 1
+        double[] result = new double[x.length + y.length - 1];
+        int N = result.length;
+
+        /*
+        To find the cross-correlation between 2 discrete signals x & y, we start by "placing" the second signal
+        y under the first signal x, shifted to the left so that the last value of y meets the first value of x
+        and for every new position (i++) of the result signal, we shift y signal one position to the right, until
+        the first y-value meets the last x-value. The result-value for each position is the sum of all x*y meeting
+        values.
+        Here's an example:
+        x=[1,2,1,1]
+        y=[1,1,2,1]
+
+        i=0:      [1,2,1,1]
+            [1,1,2,1]               result[0]=1*1=1
+
+        i=1:       [1,2,1,1]
+               [1,1,2,1]            result[1]=1*2+2*1=4
+
+        i=2:       [1,2,1,1]
+                 [1,1,2,1]          result[2]=1*1+2*2+1*1=6
+
+        i=3:       [1,2,1,1]
+                   [1,1,2,1]        result[3]=1*1+2*1+1*2+1*1=6
+
+        i=4:       [1,2,1,1]
+                     [1,1,2,1]      result[4]=2*1+1*1+1*2=5
+
+        i=5:       [1,2,1,1]
+                       [1,1,2,1]    result[5]=1*1+1*1=2
+
+        i=1:       [1,2,1,1]
+                         [1,1,2,1]  result[6]=1*1=1
+
+        result=[1,4,6,6,5,2,1]
+
+
+
+
+        To find the result[i] value for each i:0->N-1, the positions of x-signal in which the 2 signals meet
+        are calculated: kMin<=k<=kMax.
+        The variable 'yStart' indicates the starting index of y in each sum calculation.
+        The variable 'count' increases the index of y-signal by 1, to move to the next value.
+         */
+        int yStart = y.length;
+        for (int i = 0; i < N; i++) {
+            result[i] = 0;
+
+            int kMin = Math.max(i - (y.length - 1), 0);
+            int kMax = Math.min(i, x.length - 1);
+
+            if (i < y.length) {
+                yStart--;
+            }
+
+            int count = 0;
+            for (int k = kMin; k <= kMax; k++) {
+                result[i] += x[k] * y[yStart + count];
+                count++;
+            }
+        }
+
+        // The calculated cross-correlation of x & y signals is returned here.
+        return result;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java b/src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java
@@ -0,0 +1,37 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+/**
+ * Test class for AutoCorrelation class
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 2.0
+ */
+
+public class AutoCorrelationTest {
+
+    @ParameterizedTest
+    @CsvSource({"1;2;1;1, 1;3;5;7;5;3;1", "1;2;3, 3;8;14;8;3", "1.5;2.3;3.1;4.2, 6.3;14.31;23.6;34.79;23.6;14.31;6.3"})
+
+    public void testAutoCorrelationParameterized(String input, String expected) {
+        double[] array = convertStringToArray(input);
+        double[] expectedResult = convertStringToArray(expected);
+
+        double[] result = AutoCorrelation.autoCorrelation(array);
+
+        assertArrayEquals(expectedResult, result, 0.0001);
+    }
+
+    private double[] convertStringToArray(String input) {
+        String[] elements = input.split(";");
+        double[] result = new double[elements.length];
+        for (int i = 0; i < elements.length; i++) {
+            result[i] = Double.parseDouble(elements[i]);
+        }
+        return result;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/maths/CrossCorrelationTest.java b/src/test/java/com/thealgorithms/maths/CrossCorrelationTest.java
@@ -0,0 +1,37 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+/**
+ * Test class for CrossCorrelation class
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 2.0
+ */
+public class CrossCorrelationTest {
+
+    @ParameterizedTest
+    @CsvSource({"1;2;1;1, 1;1;2;1, 1;4;6;6;5;2;1", "1;2;3, 1;2;3;4;5, 5;14;26;20;14;8;3", "1;2;3;4;5, 1;2;3, 3;8;14;20;26;14;5", "1.5;2.3;3.1;4.2, 1.1;2.2;3.3, 4.95;10.89;16.94;23.21;12.65;4.62"})
+
+    public void testCrossCorrelationParameterized(String input1, String input2, String expected) {
+        double[] array1 = convertStringToArray(input1);
+        double[] array2 = convertStringToArray(input2);
+        double[] expectedResult = convertStringToArray(expected);
+
+        double[] result = CrossCorrelation.crossCorrelation(array1, array2);
+
+        assertArrayEquals(expectedResult, result, 0.0001);
+    }
+
+    private double[] convertStringToArray(String input) {
+        String[] elements = input.split(";");
+        double[] result = new double[elements.length];
+        for (int i = 0; i < elements.length; i++) {
+            result[i] = Double.parseDouble(elements[i]);
+        }
+        return result;
+    }
+}
