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.
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
"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.
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?
"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).
"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.
@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
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.
"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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.