Programmiertechnik max finden zwei arrays

[Rolf b]

Wenn ich mir die diskrete Kreuzkorrelation in der Wikipedia angucke, wird da einfach das Produkt der Messwerte zu den Zeitpunkten t und t+δ aufsummiert, um ein Maß für die Korrelation zu bekommen. Allerdings kann nicht sagen, wirklich verstanden zu haben, was mir der Artikel und sein Umfeld sagen wollen, da ist zu viel an Fachbegriffen und Hintergrundtheorie als bekannt vorausgesetzt.

Wie auch immer - es sieht so aus als würde die Kreuzkorrelation ein Maß für die Übereinstimmung liefern, und man muss den Kreuzkorrelationswert maximieren, um die beste Überdeckung zu finden. Das bedeutet, mehrere Verschiebungen auszuprobieren und die beste auszuwählen - und bei einem Messbereich von 1000 Punkten klingt das sehr aufwändig. Du kannst nicht alle möglichen Verschiebungen ausprobieren.

Gunnars Vorschlag mit dem Median ist mir nicht ganz klar - du hast Messwerte zu bestimmten Zeitpunkten, und der Median der Zeitintervalle wäre im Wesentlichen die Mitte des Intervalls. Der Median der gemessenen Werte hilft Dir meiner Meinung nach nicht. Was Dir aber helfen dürfte, wäre eine Vorab-Analyse, in welchen Intervallen $rot und $blau von null verschieden sind. Die Differenz vom Mittelpunkt dieser beiden Intervalle nimmst Du als Ausgangswert für δ. In dem von Dir gelieferten Bild wäre diese Differenz bereits 0 - hast Du da schon normiert? Oder sind deine Messungen so geartet, dass das immer der Fall ist?

Wieauchimmer - Wenn Du zwei Arrays hast mit je X Einträgen, die den Messwert zum Zeitpunkt $$t_i$$ beschreiben, dann kannst Du Dir eine Funktion schreiben, die die Kreuzkorrelation der beiden Tabellen mit einer gegebenen Verschiebung bestimmt. Grundannahme für die folgende Funktion ist, dass $rot und $blau den gleichen count haben (sprich: über das gleiche Intervall aufgezeichnet wurden)

function korreliere($rot, $blau, $delta)
{
   // Negatives Delta: $rot und $blau vertauschen und mit -$delta arbeiten.
   if ($delta < 0)
      return korreliere($blau, $rot, -$delta);

   // Zugriff erfolgt bei $blau auf Position $i+$delta, deshalb $delta positionen vor dem Ende von
   // $blau aufhören. Wenn $rot um mehr als $delta Werte kürzer ist als $blau (sollte nicht seinm
   // aber sicher ist sicher), noch früher aufhören.
   $bMax = min(count($rot), count($blau) - $delta);

   $corr = 0;
   // Kreuzkorrelation mit Verschiebung $delta bestimmmen
   for ($i=0; $i<$bMax; $i++)
      $corr += $rot[$i]*$blau[$i+$delta];

   return $corr;
}

Nun fängst Du an zu probieren. Erstmal mit großen Verschiebungen und dann näherst Du Dich an. Von oben hast Du ein Basis-Delta (oder Du nimmst 0).

Ich würde einen Wert $span festlegen, der eine Zweierpotenz darstellt und etwa ein Viertel deiner Messintervalle darstellt. Dann bestimmst Du die Kreuzkorrelationen für $delta = $basisDelta-2*$span, $basisDelta-$span, $basisDelta, $basisDelta+$span und $basisDelta+2*$span und hältst fest, für welches $delta die größte Korrelation herausgekommen ist. Das ist dein neues Basis-Delta.

Nun halbierst Du $span und wiederholst die Nummer, bis $span eine bestimmte Schwelle unterschreitet. Das kann 1 sein, aber eventuell kannst Du schon vorher aufhören, wenn Dir eine Näherung genügt.

Bei 1000 Messpunkten könntest Du also mit $span=256 starten, halbierst Dich über 128, 64, 32, 16, 8, 4 und 2 bis zur 1 hinunter (9 Span-Werte) und berechnest pro Stufe 5 Korrelationen. Insgesamt 45 Korrelationsberechnungen, und du hast einen Delta-Raum von -512 bis +512 abgetastet.

Um die Korrelationsberechnung zu beschleunigen, kannst Du auch mit einer vergröberten Auflösung arbeiten. Du bestimmst den Mittelwert von je 8 Messwerten (oder 4 oder 16) und erzeugst so zwei Arrays $grobrot und $grobblau, die deutlich kleiner sind. D.h. die Korrelationsschleife ist kürzer, und der $span beginnt bei einer kleineren Zweierpotenz (mit dem Effekt, dass Du weniger Halbierungsstufen hast).

Das Delta, dass du am Ende herausbekommst, musst Du dann natürlich mit deiner Aggregationsstufe wieder multiplizieren. Vielleicht reicht das schon völlig hin. Wenn nicht, machst Du noch eine Fein-Überlappung mit den Ausgangsarrays, kannst aber jetzt mit einem viel kleineren $span beginnen.

Rolf