Forum: Digitale Signalverarbeitung / DSP / Machine Learning Verständnisfrage zu Korrelation


von DSP-Anfänger (Gast)


Lesenswert?

Hallo Leute,
da mich das Thema digitale Signalverarbeitung sehr interessiert, lese 
ich mich grade in die ganze Sache ein.
Des öfteren habe ich schon den Begriff "Korrelation" gelesen. Das 
scheint mir eine ganz besondere Hexerei zu sein; laut Wikipedia kann man 
da Signale oder Bilder wieder herstellen, auch wenn die völlig 
verrauscht sind.
Ist das richtig?
Kann mir mal einer erklären, wie sowas softwaretechnisch denn ungefähr 
gemacht wird? Nicht, dass ich es jetzt implementieren möchte (hab eh 
keinen DSP zur Hand), reine Neugier.

von Mark B. (markbrandis)


Lesenswert?

Das Zauberwort heißt lineare Faltung:


Wie man's macht: Eine Funktion spiegeln, über die andere drüberschieben, 
multiplizieren und addieren. So ergibt zum Beispiel ein Rechteck linear 
gefaltet mit sich selbst ein Dreieck (sobald die Rechtecke sich 
überlappen, wächst der Flächeninhalt unter der Kurve linear bis zu einem 
Maximum, um danach ebenso linear wieder abzufallen).

Siehe auch hier - 
https://ces.karlsruhe.de/culm/culm/culm1/mathematik/signalanalyse/korrelation.htm

von Georg A. (Gast)


Lesenswert?

"laut Wikipedia kann man da Signale oder Bilder wieder herstellen, auch 
wenn die völlig verrauscht sind."

"Wiederherstellen" ist es eigentlich nicht, "Finden" ist besser, aber 
auch nur halb. Die Korrelation liefert für jedes Eingangssample ein 
Ausgangssample, dessen Grösse ein Mass dafür ist, ob um die Stelle herum 
eine Ähnlichkeit mit dem "Suchmuster" vorhanden ist. Das Prinzip ist, 
dass sich Rauschen über viele Samples gut rausmittelt, aber mit dem 
Suchmuster übereinstimmende Auslenkung wegen der Multiplikation immer 
positiv aufaddiert wird. Im Ergebnis hat man dann etwas Gerausche und 
(hoffentlich) einen grossen Peak an der Stelle, das das Suchmuster 
mittig  draufsitzt. Notfalls muss man das Korrelationsergebnis nochmal 
etwas filtern, um den Peak erkennbarer zu machen. Damit das aber sauber 
funktioniert, muss das Suchmuster auch bestimmte Eigenschaften haben, 
sonst kann es mehrere Peaks geben.

Allerdings ist die Korrelation auch kein Wundermittel, sie hilft nur gut 
bei Rauschen. Andere Effekte, die auch bei der Funkübertragung entstehen 
können, machen die Korrelation kaputt. Typische Beispiele wären da 
Phasenverschiebung oder Sampleratenunterschiede. Die muss man vorher 
korrigieren, sonst geht nix.

von DSP-Anfänger (Gast)


Lesenswert?

Danke @Georg und Mark.

Frage: kann man sowas auch auf einem ARM machen, oder ist die dazu 
nötige Rechenleistung derart gross, dass man einen DSP braucht?

Ausserdem: wäre es z.B. rein theoretisch möglich, damit eine 
Spracherkennung zu realisieren? man nimmt vorher einige Samples der 
Sprache auf; z.B. irgend ein Wort, und speichert das.
Dann wird ein Mikrophon an den Controller angeschlossen und das 
Audiosignal digitalisiert. Könnte man dann durch Korrelation dieses 
vorher gesampelte Wort auffinden?

(reines Gedankenexperiment, was ich hier mache! nicht, dass ich eine 
Spracherkennung machen will, das war nur so ein Gedanke).

Hat einer mal ein konkretes Beispiel, wo eine solche Korrelation 
verwendet wird?

von Georg A. (Gast)


Lesenswert?

"oder ist die dazu nötige Rechenleistung derart gross, dass man einen 
DSP braucht?"

Das kommt nur darauf an, wie gross dein Suchmuster ist und über welchen 
Bereich du suchen willst ;) Wenn dein Suchmuster s Samples hat und der 
Gesamtbereich n, müssen n*s Multiplikationen und fast genausoviel 
Additionen durchgeführt werden. Es lohnt sich also, wenn die CPU einen 
MUL-Befehl (noch besser MUL+ADD) hat und das nicht umständlich 
zusammengestückelt werden muss...

"rein theoretisch möglich, damit eine Spracherkennung zu realisieren?"

Nicht direkt, weil du die Worte nicht samplegenau sprechen/reproduzieren 
kannst. Man kann aber aus den Originalsamples erstmal Eigenschaften 
(Lautstärke, Frequenzverteilung, ...) in gröberen Zeitschritten 
berechnen und dann eine Korrelation darüber machen.

"Hat einer mal ein konkretes Beispiel, wo eine solche Korrelation
verwendet wird?"

Da gibts viele. In der Bilderkennung kann man es brauchen, aber zB. auch 
in der Übertragungstechnik. Prominentes Beispiel wäre GPS. Das Signal 
wird da über eine recht lange Korrelation gefunden, daher kann es im 
Rauschen ziemlich untergehen. Bei diversen Funksystemen erfolgt eine 
initiale Synchronisierung auch über das Finden von bestimmten Sequenzen 
(Preambeln/Syncs). Man kann dann sogar innerhalb gewisser Grenzen aus 
der "Verwaschung" des Peaks Frequenz- oder Sampleratenoffsets bestimmen, 
die als Basis für einen genaueren Sync dienen (aka Kanalschätzung).

von Tommi (Gast)


Lesenswert?

"Hat einer mal ein konkretes Beispiel, wo eine solche Korrelation
verwendet wird?

Mit Hilfe von Korrelationstechniken wird in der 
Photonenkorrelations-Spektroskopie die Grösse von Nanopartikeln in 
verdünnten Proben ermittelt. Man bestrahlt eine zu untersuchende Probe 
mit einem Laser und detektiert das resultierende Streulicht. Dieses 
fluktuiert aufgrund der Positionsfluktuationen der Teilchen (Brownsche 
Molekularbewegung). Mittels der gemessenen 
Intensitäts-Korrelationsfunktionen kann der Diffusionskoeffizient und 
somit auch der Radius der einzelen Partikel bestimmt werden.

von DSP-Anfänger (Gast)


Lesenswert?

@Georg
>>"rein theoretisch möglich, damit eine Spracherkennung zu realisieren?"

> Nicht direkt, weil du die Worte nicht samplegenau sprechen/reproduzieren
> kannst.

Hmm, du sagst aber

>  In der Bilderkennung kann man es brauchen

Aber die Bilder kann man ja auch nicht immer gleich exakt machen!
Ich weiss das, weil die Firma, in der ich arbeite, unter anderem ein 
besonderes Bilderkennungsgerät entwickelt und herstellt (ich hab aber 
damit nicht viel zu tun, weil ich noch in der Ausbildung zum 
Elektroniker stecke bzw. in wenigen Monaten erst fertig bin).
Ist denn eine Korrelation noch möglich, wenn sich das zu korrelierende 
Bild in einigen Pixeln unterscheidet?

Kannst du mir mal einen Code zeigen, der irgendwas korreliert? Die 
Thematik ist ungemein faszinierend.

Noch ne Frage:
Im Wikipedia-Artikel zur Korrelation wird ein Beispiel mit ein paar 
Bildern gezeigt, die Korreliert werden. Schön und gut, es funktioniert, 
aber das Resultat der Korrelation ist ja wieder ein Bild, das mehr oder 
weniger rauscht. Wie kann denn jetzt der Rechner anhand dieses 
korrelierten Bildes erkennen, ob es das Ausgangsbild darin enthalten 
war, oder nicht?

Siehe hier: http://de.wikipedia.org/wiki/Korrelation und noch besser 
erklärt hier: http://de.wikipedia.org/wiki/Code_Division_Multiple_Access

und hier das Bild, von welchem ich rede: 
http://upload.wikimedia.org/wikipedia/commons/7/76/Corr_outpurp.png

Gruss

von Mark B. (markbrandis)


Lesenswert?

DSP-Anfänger schrieb:
> Danke @Georg und Mark.
>
> Frage: kann man sowas auch auf einem ARM machen, oder ist die dazu
> nötige Rechenleistung derart gross, dass man einen DSP braucht?

Die Sache beim DSP ist die, dass er eben speziell für Algorithmen der 
Signalverarbeitung optimiert ist:

-Harvard-Architektur: Dadurch kann man z.B. die Koeffizienten eines 
Filters im Programmspeicher ablegen und die Signalwerte im 
Datenspeicher. Somit kann man jeweils einen Wert aus den getrennten 
Speicherbereichen im gleichen Takt holen.

-Multiplizieren und auf einen bestehenden Wert draufaddieren 
(akkumulieren), was man z.B. für digitale Filter braucht

-Bitreverse Adressierung: Diese wird für die schnelle 
Fouriertransformation (FFT) verwendet

u.a.

Natürlich kann man auch auf jedem beliebigen einfachen Mikrocontroller 
eine FFT rechnen oder ein Signal tiefpassfiltern. Aber die Performance 
ist eben nicht dieselbe, mit Echtzeitbearbeitung ist dann recht schnell 
Schluss.

von Georg A. (Gast)


Lesenswert?

"Aber die Bilder kann man ja auch nicht immer gleich exakt machen!"

Kommt auf die zu erkennenden Details an. Die Korrelation stört sich 
weniger dran, wenn Suchmuster und Originalbild tiefpassgefiltert werden, 
allerdings wird dann auch der Peak verbreitert. Die normale Korrelation 
kann man auch für 2D machen (das ist das Beispiel mit den Bildern), 
allerdings kommt da noch hinzu, dass Rotationen auch nicht vorhanden 
sein dürfen.

"Wie kann denn jetzt der Rechner anhand dieses
korrelierten Bildes erkennen, ob es das Ausgangsbild darin enthalten
war, oder nicht?"

2D-Tiefpass drüber (sollte man bei nicht speziell für die Korrelation 
definierten Mustern sowieso machen) und zB. Berechnung des Mittelwerts 
und des Maximumwerts, evtl. noch mit Betrachtung der Energie beim 
Mittelwert (also Werte quadrieren, addieren und dann Wurzel). Wenn das 
Maximum xx% über dem Mittelwert liegt, gibt es einen Treffer.

Das Beispiel bei CDMA ist übrigens nur zur Verdeutlichung, weil der 
Mensch 2D-Bilder besser wiedererkennt, als ein lineares 1D-Bild mit 
mehreren 100 Punkten... Der Korrelationsmechanismus im Hirn ist zwar 
ungeschlagen, was mögliche Verzerrungen/Transformationen angeht, dafür 
braucht er aber erkennbare 2D-Objekte ;)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.