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.
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 ;)
