Normierte Kreuzkorrelation

[Degush]

Hey,

für ein Projekt möchte ich die Kreuzkorrelation zweier Bildblöcke berechnen. Der Algorithmus um diese zu berechnen sieht allerdings ziemlich langsam aus.
Außerdem werden die Werte im Zähler und im Nenner selbst bei kleinen Bildbereichen bei weitem die Kapazität von einem Integer, wahrscheinlich sogar von einem long, überschreiten. Ich möchte nicht auf einen superlangsamen BigInteger umsteigen. Mit etwas Genauigkeitsverlust könnte man natürlich einfach die letzten paar Stellen abschneiden - aber ich frage mich, ob das nicht eleganter zu lösen ist.

Wenn man einen Bildblock f1 mit mehreren verschiedenen Bildblöcken f2 vergleicht, kann man zumindest den linken Teil des Termes unter den Wurzel durch eine Konstante ersetzen.
Aber wie kann man den Algorithmus praxistauglich machen?

MfG,
Malte

 

[Marco13]

Wie wär's mit double?
Unabhängig davon sehen solche Formeln meistens komplizierter aus, als sie sind (weil sie nicht von Informatikern sondern von Mathematikern aufgeschrieben - oder von Informatikern, die irgendeinen Komplex haben). Man müßte halt wissen, das die ganzen delta, f und so sind...

 

[Bleiglanz]

Man könnte eventuell die berechneten $f_1$ und $f_2$ Werte in einen Cache legen, damit man sie in Zähler und Nenner nicht immer wieder berechnen musst, ansonsten sieht man da auf anhieb nichts zum Optimieren.

Und: die Doppelsummen an sich sind ja harmlos, wenn $n=1000$ und $m=1000$, dann musst du eben eine Million mal die Summanden (sprich f_1, f_2) ausrechnen und dann summieren.

So schlimm ist das auch nicht, hängt alles von den beiden Fkt ab.

 

[JohannisderKaeufer]

Mit der Praxistauglichkeit hat sich wie ich sehe schonmal jemand beschäftigt und ist zu diesem Ergebnis gekommen. Die Benchmarks sehen für mein dafürhalten recht gut aus.

http://kogs-www.informatik.uni-hamburg.de/~seppke/content/wise0809/fast-ncc.pdf

 

[Degush]

Wie wär's mit double?
Unabhängig davon sehen solche Formeln meistens komplizierter aus, als sie sind (weil sie nicht von Informatikern sondern von Mathematikern aufgeschrieben - oder von Informatikern, die irgendeinen Komplex haben). Man müßte halt wissen, das die ganzen delta, f und so sind...

Inhaltlich ist das kein Problem. Praktisch können Werte im z.B. Nenner auch gerne mal (2 hoch 32) hoch 3², also >180 Stellen erreichen , wenn man einen 3x3 Bildblock analysiert.

Man könnte eventuell die berechneten $f_1$ und $f_2$ Werte in einen Cache legen, damit man sie in Zähler und Nenner nicht immer wieder berechnen musst, ansonsten sieht man da auf anhieb nichts zum Optimieren.

Und: die Doppelsummen an sich sind ja harmlos, wenn $n=1000$ und $m=1000$, dann musst du eben eine Million mal die Summanden (sprich f_1, f_2) ausrechnen und dann summieren.

So schlimm ist das auch nicht, hängt alles von den beiden Fkt ab.

Zumindest die Werte im Nenner werde ich in einen Cache legen können. Aber Pixel können 2³² verschiedene Werte annehmen (ARGB codiert), wenn ich das Bild nicht in Graustufen umrechnen möchte.
Und wenn, mal angenommen, n = 3 und m = 3 ist, dann geht der anzunehmende Wertebereich immer noch bis 9 * (2³²)², also 9 * (2 hoch 64), was im ungünstigen Fall selbst ein long an seine Kapazitäten bringt.
Wahrscheinlich werde ich das Bild wieder auf seine Intensität reduzieren müssen, also auf Grauwerte herunterrechnen.

Mit der Praxistauglichkeit hat sich wie ich sehe schonmal jemand beschäftigt und ist zu diesem Ergebnis gekommen. Die Benchmarks sehen für mein dafürhalten recht gut aus.

Das sieht ganz interessant aus. Dann werde ich mich wohl oder übel mit Fourier Transformationen und den Beschleunigungsalgorithmen auseinander seztzen müssen -.-
Besonders ausführlich ist da leider nichts beschrieben. Aber danke!

 

[Marco13]

Inhaltlich ist das kein Problem. Praktisch können Werte im z.B. Nenner auch gerne mal (2 hoch 32) hoch 3², also >180 Stellen erreichen , wenn man einen 3x3 Bildblock analysiert.

Sicher erstmal die Sachen lesen, die von den Leuten stammen, die sich offenbar schon intensiver damit beschäftigt haben, aber double reicht bis ~ 1.79 x 10^308, das würde ja reichen...
(Und für größere Blöcke: Meine erste Einlassung bezog sich u.A. darauf, dass man da vermutlich einiges "rauskürzen" könnte, wenn man's etwas übersichtlicher auufschreiben würde...)