Minimum und Maximum aus Messreihe berechnen

[D. S. (datasheet)]

Hi,

ich habe einen Signalverlauf gesampled und ich hätte gern die beiden 
Extremwerte. In erster Näherung hab ich einfach den kleinsten und den 
größten Messwert der Reihe genommen. Ich möchte aber eigentlich noch 
genauer werden. Gibt es da einen Algorithmus für sowas?

Meine Gedanken:
Im Prinzip lässt sich ja der Anstieg für jedes Intervall berechnen.

index j = i+1
m = (y_j-y_i) / (x_j-x_i)

Wenn sich das Vorzeichen dreht, hab ich die beiden Punkte zwischen denen 
der Extremwert liegt.
Dann müsste ich ja aus dem Verhältnis zwischen dem vorherigen und dem 
nachfolgenden Anstieg (nur Betrag) bestimmen können, ob die X-Koordinate 
eher links oder eher rechts liegt.

Das sagt dann aber immer noch nichts über den Y-Wert aus.

Hat da jemand eine Idee?

viele Grüße
data

[Karl H. (kbuchegg)]

D. S. schrieb:
> Hi,
>
> ich habe einen Signalverlauf gesampled und ich hätte gern die beiden
> Extremwerte. In erster Näherung hab ich einfach den kleinsten und den
> größten Messwert der Reihe genommen.


Nicht 'erste Näherung'.
Das ist das, was deine Daten ohne weiteres Wissen und Annahmen hergeben.

Solange du keine Annahmen über den Signalverlauf (zb Sinusschwingung) 
treffen kannst, geben die Daten nicht mehr her.

[Reinhard Kern (Gast)]

D. S. schrieb:
> Wenn sich das Vorzeichen dreht, hab ich die beiden Punkte zwischen denen
> der Extremwert liegt.

Nein, hast du nicht. Die Steigungen gelten für ein Intervall, nicht für 
einen Punkt. An den beiden Intervallen sind 3 Punkte beteiligt - welchen 
beiden willst du die Steigung zuordnen? Jede Möglichkeit ist völlig 
willkürlich und hat mit der Realität nichts zu tun.

Gruss Reinhard

[Vlad T. (vlad_tepesch)]

Karl Heinz Buchegger schrieb:
> Nicht 'erste Näherung'.
> Das ist das, was deine Daten ohne weiteres Wissen und Annahmen hergeben.

naja, wenn man die nächsten Nachbarpunbkte auch kennt, könnte man ja ein 
Spline reinfitten und sich dort die Extremstelle berechnen.
Genauer, als einfach den Messwert zu nehmen, wird das schon sein.

[D. S. (datasheet)]

Vielen Dank Vlad!

Spline war genau der richtige Suchbegriff. Kannte ich irgendwie schon 
vom Linien zeichnen lassen, aber war für mich aber grad nicht greifbar.

Die Berechnung hat es ganz schön in sich. Da ich aber äquidistante 
Punkte habe, vereinfacht sich das ganze. Man benötigt nur die 
Y-Koordinaten.

Bsp.:

y0=30
y1=28
y2=27
y3=29

um die Werte zwischen y1 und y2 zu errechnen müssen die Koeffizienten 
der kubischen Funktion
y=ax^3+bx^2+cx+d

a = y3 - y2 - y0 + y1 = 0
b = y0 - y1 - a       = 2
c = y2 - y0           = -3
d = y1                = 28

wenn man x jetzt im Intervall [0,1] variiert, kriegt man den 
Kurvenverlauf zwischen y1 und y2.
So gesehen alles recht einfach.

Beim ausprobieren hab ich allerdings gemerkt, dass Reinhard leider recht 
hat. Der Wechsel des Anstiegs kein Garant für das Minimum im Intervall 
ist.
Da ist wohl die richtige Vorgehensweise:
- kleinsten Messwert herausfinden
- spline mit zwei Punkten links und einem Punkt rechts davon
- spline mit einem Punkt links und zwei Punkten rechts davon
- Minimum aus beiden splines

Danke euch
data [:-]

[Wolfgang (Gast)]

D. S. schrieb:
> - Minimum aus beiden splines

Damit greifst du willkürlich eines Punkt raus. Warum nimmst du nicht den 
Mittelwert. Warum sollte der wahre Signalverlauf dichter am Minimum als 
am Mittel liegen?
Um ein besseres Minimum zu bestimmen, müßte man mehr Wissen in die 
Interpolation stecken. Man könnte als Filter ein Modell des Prozesses 
laufen lassen, z.B. einen Zustandsschätzer in Form eines Kálmán-Filters.

[Klaus D. (kolisson)]

du kannst (wie gesagt wurde, vollkommen willkürlich)
. den MIN / MAX feststellen
.. den Median
... den absoluten Mittelwert
.... den gleitenden Mittelwert
..... die Nullstellen
...... und wohl noch mehr

was da dann herauskommt liegt definitiv im Auge des Betrachters.

Gruss Klaus

[Yalu X. (yalu) (Moderator)]

D. S. schrieb:
> Spline war genau der richtige Suchbegriff. Kannte ich irgendwie schon
> vom Linien zeichnen lassen, aber war für mich aber grad nicht greifbar.

Mal ganz ehrlich:

Splines, gleitende Mittelwerte u.ä. sind für Banker, Excel, Manager und
Powerpoint, also pure Augenwischerei ;-)

Du willst deine Messdaten aber nicht beschönigen, sondern fehlende
Zwischenwerte rekonstruieren. Deswegen brauchst du

Karl Heinz Buchegger schrieb:
> weiteres Wissen

über die Eigenschaften des Signals.

Ohne dieses kannst du die Zwischenwerte genauso gut würfeln. Mag sein,
dass Splines in vielen Fällen bessere Ergebnisse liefern als die lineare
Interpolation. Je nach Signalform können die Ergebnisse u.U. aber auch
schlechter sein.

Aber zum Glück hast du das zur Signalrekonstruktion benötigte Wissen
(vielleicht ohne es zu wissen ;-)):

D. S. schrieb:
> ich habe einen Signalverlauf gesampled

D. S. schrieb:
> äquidistante Punkte

Du hast also ein klassisches Abtastsystem mit einer gegebenen Abtastfre-
quenz. Ich gehe mal davon aus, dass du sichergestellt hast, dass das
Abtasttheorem erfüllt ist, dass also die höchste im Signal vorkommende
Frequenz kleiner als die halbe Abtastfrequenz ist.¹

Damit sind die Voraussetzungen gegeben, das Originalsignal vollständig
zu rekonstruieren. Das Zauberwort dafür heißt sin(x)/x-Interpolation.

Das Diagramm im Anhang zeigt deren Verhalten im Vegleich zur Interpola-
tion mit kubischen Splines. Das Eingangssignal ist im Beispiel die Über-
lagerung zweier Sinusschwingungen mit den Frequenzen 1,1 kHz und 2,4 kHz
und den Amplituden 0,5 und 1,0. Das Signal wird mit 5 kHz > 2 · 2,4 kHz
abgetastet, womit das Abtasttheorem erfüllt ist.

Während die Spline-Interpolation hier eher als Weichzeichner agiert,
gibt die sin(x)/x-Interpolation das Originalsignal messerscharf wieder.
Du kannst natürlich wesentlich mehr Zwischenpunkte berechnen als im
Diagramm dargestellt, um die Maxima genau zu treffen.

Die sin(x)/x-Interpolation ist zudem leicht zu programmieren, Literatur
dazu findest du im Netz zuhauf.

Praktisch jedes Digitaloszi hat so etwas übrigens eingebaut, weil dort
genau die gleiche Problematik vorliegt.

Wahrscheinlich gibt es auch ein Verfahren, das die Maxima direkt (ohne
den Umweg über die Zwischenpunkte) berechnet. Im Moment habe ich dazu
aber nichts im Kopf.

—————————————
¹) Wenn nicht, misst du sowieso Müll. Du solltest dich dann erst um eine
   geeignete Vorfilterung des Signals kümmern, bevor du die gesampelten
   Daten in irgeneiner Form weiterverarbeitest.

[Arc N. (arc)]

D. S. schrieb:
> Beim ausprobieren hab ich allerdings gemerkt, dass Reinhard leider recht
> hat. Der Wechsel des Anstiegs kein Garant für das Minimum im Intervall
> ist.
> Da ist wohl die richtige Vorgehensweise:
> - kleinsten Messwert herausfinden
> - spline mit zwei Punkten links und einem Punkt rechts davon
> - spline mit einem Punkt links und zwei Punkten rechts davon
> - Minimum aus beiden splines
>
> Danke euch
> data [:-]

Etwas vereinfacht...
Das globale Maximum ist definiert als f(y) >= f(x) für alle x.
Lokales Maximum f(y) >= f(x) wenn |x - y| < epsilon. bzw.
f'(x) = 0 und f''(x) != 0
Wendepunkt: f''(x) = 0, f'''(x) != 0

Kalman wurde schon genannt, Partikel-Filter wäre eine andere Variante.
Je nach Daten könnten auch andere Spline-Basisfunktionen sinnvoll sein 
oder monotone kubische Splines.
Aber solange niemand weiß, um was für Daten/welche Signale es geht, wird 
niemand sagen können, ob die bislang vorgeschlagenen Sachen sinnvoll 
sind oder nicht.

[D. S. (datasheet)]

Hallo Yalu,

danke für Deinen ausführlichen Beitrag. Ist ja echt beeindruckend was 
sin(x)/x kann.
Nyquist-Shannon kenn ich, ignoriere ich, messe trotzdem keinen Mist ;-)
Ich habe im Prinzip eine Lade- und Entladekurve eines Kondensators. 
Dieses periodische Signal taste ich mit fast der Erregerfrequenz ab und 
bekomme so den Kurvenverlauf.

Hier mal eine Messreihe:

0,0
0,2
-1,0
-1,0
-0,4
-0,2
0,1
-0,1
-0,1
0,3
0,0
0,0
0,1
0,1
-0,1
0,2
-0,1
-0,9
-67,9
-97,5
-90,6
-75,7
-61,6
-48,9
-39,1
-31,2
-24,1
-19,9
-15,2
-12,1
-9,6
-7,4
-5,8
-4,5
-3,5
-2,7
-1,7
-1,2
-1,1
-0,8
-0,1
-0,3
-0,1
0,0
0,2
0,1
-0,1
0,2
0,1
0,3
0,1
0,5
66,8
93,8
86,4
72,5
59,2
48,3
39,2
31,8
25,4
20,8
16,7
13,7
11,0
8,8
7,2
5,9
4,6
3,8
3,2
2,6
2,2
1,8
1,6
1,3
1,0
0,9
0,8
0,6
0,5
0,3
0,5
0,3
0,3
0,3
0,2
0,3
0,1
0,4
0,5
-0,1
0,1
0,1
0,0
0,3
0,1
0,3
0,4

Im Anhang die vier Punkte um das Maximum herum und das was Spline daraus 
gemacht hat.
So gesehen, sicherlich nicht schlecht, aber vielleicht auch noch 
verbesserungswürdig.
Höchster Messwert: 93,8
Spline Maximum:    96,4
und passt optisch ganz gut. (Sagt der BWLer in mir g)

[Klaus D. (kolisson)]

@Autor: Yalu X. (yalu) (Moderator)
ich fand deinen Beitrag und die Grafik dazu super.

danke von
Klaus de Lisson

[Frank M. (aktenasche)]

D. S. schrieb:
> Nyquist-Shannon kenn ich, ignoriere ich

ich musste spontan lachen :D

> Ich habe im Prinzip eine Lade- und Entladekurve eines Kondensators.

wenn du das weisst, wieso bestimmst du dann nicht die zeitkonstante?

> Dieses periodische Signal taste ich mit fast der Erregerfrequenz ab und
> bekomme so den Kurvenverlauf.

d.h. du schickst in irgendetwas 20kHz rein und tastest mit fast 20kHz 
ab? siehe obiges gelächter.

solang du keine genaue beschreibung abgibst, ist jede antwort imho 
sinnfrei. was hast du für messgeräte? was misst du? was willst du 
wissen?

wenn du ein oszi hast und tatsächlich nur maximale/minimale werte haben 
willst: ich würde mit dem trigger solang rumwursteln bis ich habe was 
ich will. modernere oszis haben afaik spike detektoren.

[Klaus W. (mfgkw)]

Yalu X. schrieb:
> Splines, gleitende Mittelwerte u.ä. sind für Banker, Excel, Manager und
> Powerpoint, also pure Augenwischerei ;-)

Mach dir nicht die Maschinenbauer zum Feind; sie bauen dein nächstes 
Auto, deine Herz-Lungen-Maschine und einiges mehr!
Ohne Splines geht da nicht viel.

Yalu X. schrieb:
> ... Das Zauberwort dafür heißt sin(x)/x-Interpolation. ...

Der Zauber funktioniert sehr gut, wenn man keine Meßfehler hat und unter 
den Voraussetzungen deines Beispiels (Shannon knapp erfüllt). Dann sieht 
es beeindruckend aus (Werte des tatsächlichen Verlaufs, die weit über 
die Meßwerte hinausgehen, werden tatsächlich rekonstruiert) - das muß 
aber nicht in jedem Fall so sein.
Besonders wenn du deine Meßwerte noch etwas verfälschst (und nicht wie 
bei dir beschönigend genau auf die exakte Kurve gelegt), ist es auch 
beeindruckend, aber nicht mehr beeindruckend gut.
Genau dann machst du nämlich Augenwischerei: es entsteht ein fiktiver 
Verlauf mit enormen Ausschlägen, der mit der Realität nicht im 
Mindestens etwas zu tun hat.

Zudem sind Splines nicht gleich Splines. Eben wenn man über den 
tatsächlichen Verlauf zwischen den Stützstellen nicht viel weiß, ist es 
seriöser, keine Ausschläge hinein zu interpretieren.
Dann fallen mir B-Splines ein - damit kann man sehr gutmütige Verläufe 
erreichen.

Natürlich ist jede Art von Interpolation oder Ausgleich 
Kaffesatzleserei, aber Ausschläge weit jenseits der Messwerte sind kaum 
seriös, wenn sie von ungenauen Meßwerten angefacht werden können.

[so siehts aus (Gast)]

und außerdem gehört der THread ins Forum: Digitale Signalverarbeitung / 
DSP

[Yalu X. (yalu) (Moderator)]

D. S. schrieb:
> Nyquist-Shannon kenn ich, ignoriere ich, messe trotzdem keinen Mist ;-)

Ok, in diesem Fall bringt sin(x)/x wahrscheinlich nicht das gewünschte
Ergebnis.

> Ich habe im Prinzip eine Lade- und Entladekurve eines Kondensators.

Wenn das nicht nur im Prinzip, sondern tatsächlich so ist, kannst du ja
den theoretischen Signalverlauf ermitteln, der dann wahrscheinlich noch
ein paar unbekannte Parameter enthält. Diese Parameter bestimmst du,
indem du den theoretischen Signalverlauf mit geringstmöglichen Fehlern
in den tatsächlichen Signalverlauf hineinfittest. Damit kannst du dann
die Funktionswerte an beliebigen Stellen berechnen.

Solche Approximationsverfahren auf Basis einer physikalisch fundierten
Funktion haben zwei Vorteile:

- Sie geben die Physik des Systems richtig wieder. Das erhöht die
  Chance, auch in atypischen Fällen noch brauchbare Ergebnisse liefern
  zu können.

- Sie sind relativ unempfindlich gegenüber Messrauschen, da in die
  berechneten Ergebnisse nicht nur ein paar, sondern alle Messwerte
  eingehen.

Voraussetzung ist natürlich, dass man die zugrundeliegende Physik in der
Formel für den Signalverlauf richtig erfasst hat.

> Hier mal eine Messreihe:
> ...

Das sieht aus wie ein Rechtecksignal, das mit einem Bandpass 2. Ordnung
gefiltert wurde. Könnte das zu deinem System, das wir nicht kennen,
passen?

Ich habe mal angenommen, es würde sich um einen Tiefpass mit einem
nachgeschalteten Hochpass handeln. Sind τ1 und τ2 deren Zeitkonstanten,
ergibt sich jeweils ab der steigenden Flanke des Rechtecksignals fol-
gender Signalverlauf:

$$y=\begin{cases} K_1\cdot(\mathrm e^{-\frac t{\tau_2}}-\mathrm e^{-\frac t{\tau_1}}) & \text{falls }\tau_2\neq\tau_1 \\ K_2\cdot t\cdot\mathrm e^{-\frac t{\tau}} & \text{falls }\tau_2=\tau_1=\tau \end{cases}$$

(Edit: Da waren noch ein paar Tippfehler in den Formeln. Jetzt sollten
       sie behoben sein)

K1 und K2 sind dabei Skalierungsparameter.

Ich habe von deinen Daten mal einen Ausschnitt genommen und manuell
versucht, diese Funktion hineinzufitten. Für

  τ1 = 0,717
  τ2 = 4,77
  K1 = 154

und einer Verschiebung  entlang der x-Achse um 7,45 ergibt sich das
Bild im Anhang. Ich würde sagen, das passt ganz ordentlich, zumal man
das per Computer sicher noch etwas besser hinbekommt.


Klaus Wachtler schrieb:
>> Splines, gleitende Mittelwerte u.ä. sind für Banker, Excel, Manager und
>> Powerpoint, also pure Augenwischerei ;-)
>
> Mach dir nicht die Maschinenbauer zum Feind; sie bauen dein nächstes
> Auto, deine Herz-Lungen-Maschine und einiges mehr!

Ich habe ja deswegen auch einen Smiley dahintergesetzt :)

Ein gewissenhaft arbeitender Ingenieur, der eine Spline-Interpolation
verwendet, wird ja auch mathematisch begründen können, warum er genau
diese Methode und keine andere gewählt hat. Der BWLer hingegen urteilt
i.Allg. subjektiv und jeden Tag anders. Anders sieht es natürlich aus,
wenn Spline-Funktionen tatsächlich nur für's Auge eingesetzt werden,
bspw. bei Autokarosserien. Da darf dann auch subjektiv entschieden
werden.

> Der Zauber funktioniert sehr gut, wenn man keine Meßfehler hat und unter
> den Voraussetzungen deines Beispiels (Shannon knapp erfüllt).

Natürlich funktioniert der Zauber genauso gut, wenn Shannon nicht nur
knapp erfüllt ist. Nur funktionieren dann andere Methoden nicht mehr so
schlecht :)

Was die Messfehler betrifft: Der Fehler der interpolierten Daten liegt
bei der sin(x)/x-Interpolation in der Größenordnung der Messfehler. Da
ist sie nicht besser und nicht schlechter als andere Interpolationsver-
fahren.

Unempfindlicher gegenüber Messfehler sind i.Allg. Approximationen, da
dort Fehler bis zu einem gewissen Grad herausgemittelt werden können.
Dazu muss man aber das betrachtete System genauer kennen, um den theo-
retischen Signalverlauf ermitteln zu können (s.o.).


so siehts aus schrieb:
> und außerdem gehört der THread ins Forum: Digitale Signalverarbeitung /
> DSP

Ja, dort passt er besser hinein.

[D. S. (datasheet)]

Frank Meier schrieb:
> D. S. schrieb:
>> Nyquist-Shannon kenn ich, ignoriere ich
>
> ich musste spontan lachen :D
So war es auch gemeint

>> Ich habe im Prinzip eine Lade- und Entladekurve eines Kondensators.
> wenn du das weisst, wieso bestimmst du dann nicht die zeitkonstante?
Weil sich die Lade- und Entladekurven der verschiedenen Messungen nicht 
großartig voneinander unterscheiden. Das Minimum, Maximum allerdings 
schon

>> Dieses periodische Signal taste ich mit fast der Erregerfrequenz ab und
>> bekomme so den Kurvenverlauf.
> d.h. du schickst in irgendetwas 20kHz rein und tastest mit fast 20kHz
> ab? siehe obiges gelächter.
Lach' nur nicht zu laut, nicht dass Du Dich noch verschluckst.
Bei periodischen Kurvenverläufen ist das schon OK so. Wenn sich die 
Werte verändern, Audio o.ä. ist das natürlich fatal.

> solang du keine genaue beschreibung abgibst, ist jede antwort imho
> sinnfrei. was hast du für messgeräte? was misst du? was willst du
> wissen?
Ich hab den Signalverlauf so wie er ist in digitaler Form im PC. Ich 
möchte, möglichst automatisch, d.h. nicht mit 
Tabellenkalkulationsprogramm o.ä. eine Kurve so lange reinfitten bis es 
passt. Sondern erkennen wie stark die Extremwerte einbrechen.
Ich suche also nicht nur nach der Möglichkeit die Funktion auszuwerten, 
sondern auch nach einer Routine (deshalb auch das Forum PC 
Programmierung) die mir diese Kurve bewertet.

[Wolfgang (Gast)]

D. S. schrieb:
> Ich hab den Signalverlauf so wie er ist in digitaler Form im PC. Ich
> möchte, möglichst automatisch, d.h. nicht mit
> Tabellenkalkulationsprogramm o.ä. eine Kurve so lange reinfitten bis es
> passt.

Und was hindert dich daran, das Modell im PC zu rechnen. Ganz einfach 
wird es, falls sich nur die Amplitude und nicht die beiden 
Zeitkonstanten ändern. Um das zu entscheiden, müßte man mehr über deinen 
Prozess wissen.