Hallo, ich frage mich, wie ich Peaks in einem Histogramm (oder von mir aus in einer Folge) suchen kann. Beispiel: 0 0 2 3 5 6 4 3 2 1 1 1 0 0 0 1 1 2 1 2 2 3 4 5 6 7 7 8 9 9 6 5 3 2 1 2 0 --> hier möchte ich gerne die Werte "6" und "9" haben, da sie die beiden "Stärksten" lokalen Maxima darstellen. Ableiten (also Differenz bilden) und nach den Übergängen "+" nach "-" suchen? Hat jemand ein Stichwort für ein Verfahren, nach dem ich suchen kann?
Hmm. Mathematisch oder Informatisch? Mathmatisch ist klar, erste und zweite Ableitung und dann lokale Extremstellen finden. Informatisch würde ich das so lösen:
1 | Gucken ob Wert größer 0 |
2 | Wenn ja{
|
3 | Vergleich mit tempörärem Speicher |
4 | Wenn größer{
|
5 | temporären Speicher ersetzen |
6 | } |
7 | } |
8 | Wenn nein{
|
9 | Temporärer Speicher größer 0? |
10 | Wenn ja{
|
11 | temporären Speicher ausgeben |
12 | } |
13 | temporären Speicher löschen (gleich 0 setzen) |
14 | } |
Ich hoffe du verstehst wie ich das meine. Mit freundlichen Grüßen, Valentin Buck
Braucht man dafür ein Verfahren? Man geht das Feld entlang, berechnet die Differenz und merkt sich die jeweils letzte. Ist die letzte >0, übergeht man alle ==0 und schaut sich dann die erste !=0 an. Falls <0: Maximum gefunden, sonst nur Sattelpunkt im Aufstieg, also aktuelle Diff. zu letzter machen und weiter wie oben.
@ Klaus Wachtler: Das habe ich versucht in Worte zu fassen! Ich hätte nie so einfach gedacht... ;-) Mit freundlichen Grüßen, Valentin Buck
Aber Vorsicht: Der erste und der letzte Punkt brauchen eine Sonderbehandlung!
hüstel ich glaube es ist ziemlich einfach. Ich will die beiden stärksten lokalen Maxima suchen:
1 | int max1 = 0; |
2 | int max2 = 0; |
3 | |
4 | int pos1 = 0; |
5 | int pos2 = 0; |
6 | |
7 | for (int i = 0; i < BINS; i++){ |
8 | int delta = f[i+1] - f[i]; |
9 | |
10 | if (delta < 0){ // lokales Maximum |
11 | if (f[i] > max1){ // neues globales Maximum |
12 | max2 = max1; |
13 | pos2 = pos1; |
14 | max1 = f[i]; |
15 | pos1 = i; |
16 | }
|
17 | else if (f[i] > max2){ // neues zweitgr. lok. Max. |
18 | max2 = f[i]; |
19 | pos2 = i; |
20 | }
|
21 | }
|
22 | |
23 | }
|
Ich glaube, so kann es wohl funktionieren.
... mit der Einschränkung natülich, dass ich BINS-1 nehmen muss um beim letzten Schritt nicht ins Leere zu laufen, aber das hat Karl Heinz ja bereits angesprochen.
Philipp schrieb: > Ich glaube, so kann es wohl funktionieren. Das denke ich nicht. Das ist ein bischen zu einfach überlegt. Aber probiers durch.
Hast Recht, ich muss wohl erst tiefpassfiltern oder so etwas, hier schlägt es z.B. fehl: 999 1001 999 1001 1050 1001 999 0 0 0 0 0 0 1000 0 0 0 0 Offensichtlich "will" ich hier gerne die Positionen mit 1050 und 1000 haben, bekomme aber natürlich 1001 und 1050, die ja beim Blick auf das Histogramm auf dem gleichen Berg liegen. Also muss ich sowas machen: Berg raufklettern, höchsten Punkt finden und dann erst wieder einen neuen höchsten Punkt suchen, wenn ich in einem Tal war.
Philipp schrieb: > Also muss ich sowas machen: Berg raufklettern, höchsten Punkt finden und > dann erst wieder einen neuen höchsten Punkt suchen, wenn ich in einem > Tal war. Jupp Das wäre auch mein Ansatz abwechselnd Maximum und Minimum suchen wobei das Problem eigentlich nur am Anfang besteht: Womit fängt man an? Sucht man ein Maximum oder ein Minimum (lässt sich aber lösen, indem man sich den/die nächsten Punkte ansieht, wie dort die 'Steigung' verläuft. Ist sie positiv dann gilt der erste Punkt schon als Minimum und man sucht ein Maximum. Ist sie negativ, dann gilt der erste Punkt schon als Maximum und man sucht ein Minimum. Steigung 0 gilt nicht, dann muss man eben den übernächsten Punkt betrachten, fff) Und dann gehts eigentlich immer so dahin
1 | schleife über alle Elemente {
|
2 | |
3 | if modus == maximum suchen |
4 | if steigung < 0 then |
5 | maximum gefunden |
6 | entscheiden ob man es aufheben will (nur die 2 Größten) |
7 | modus = minimum suchen |
8 | |
9 | else if modus == minimum suchen |
10 | if steigung > 0 then |
11 | modus = maximum suchen |
12 | } |
nur so als Codeskizze Der letzte Punkt bedarf noch einer Sonderbahandlung. Er könnte ja ein Maximum sein, obwohl es keinen Steigungswechsel mehr gibt. Einfach in die Funktion, die entscheidet, ob man ein Maximum aufheben will als "Maximum" einfliessen lassen. Wenn er tatsächlich ein Maximum ist, dann hebt ihn sich die Funktion dann schon auf.
Hm, also über die "Grundfunktion" bin ich mir ja durchaus im Klaren, allerdings gibt es ja den kleinen Haken dass z.B. bei 1 2 3 5 3 2 3 2 1 0 0 0 1 2 1 0 0 0 die "3" (Position 7) nicht als Maximum durchgehen soll, es ist ja offensichtlich nur "Messrauschen". Daher mein Gedanke, das Tiefpasszufiltern bzw. exponentiell zu Glätten oder sowas. Oder ich benutze sowas wie den "Floodfill"-Algorithmus --> ich "flute" meine Folgen bis zu einem gewissen Wert, dann bleiben nur noch einzelne Inseln übrig und ich suche dann nur noch das globale Maximum pro Insel. Hier also: Füllen bis "1" (ok, hier jetzt witzlos da die Zahlen ja recht nahe beisammen liegen): 1 2 3 5 3 2 3 2 1 1 1 1 1 2 1 1 1 1 Es bleiben also zwei Inseln übrig und ich finde die 5 und die 2. Natürlich würde das in diesem Beispiel auch mit "0" als Fluthöhe funktionieren, aber da meine Täler ja auch bei 5 oder 10 liegen können, brauche ich also einen Wert, der so groß wie möglich ist aber kleiner als meine erwarteten Spitzen. 50 70 50 400 200 300 100 10 20 80 100 50 50 Füllen bis z.B. 60: 60 70 60 100 200 300 100 60 60 80 100 60 60 ... und ich finde, wenn ich die beiden größten suche, 400 und 100, aber nicht die 300.
Thread beobachten
Seitenaufteilung abschaltenBitte 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.