www.mikrocontroller.net

Forum: PC-Programmierung Maxima in einem Histogramm suchen


Autor: Philipp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm.
Mathematisch oder Informatisch?

Mathmatisch ist klar, erste und zweite Ableitung und dann lokale 
Extremstellen finden.

Informatisch würde ich das so lösen:
Gucken ob Wert größer 0
Wenn ja{ 
   Vergleich mit tempörärem Speicher
   Wenn größer{
      temporären Speicher ersetzen
              }
   }
Wenn nein{
   Temporärer Speicher größer 0?
   Wenn ja{
      temporären Speicher ausgeben
          }
   temporären Speicher löschen (gleich 0 setzen)
   }

Ich hoffe du verstehst wie ich das meine.
Mit freundlichen Grüßen,
Valentin Buck

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Klaus Wachtler:
Das habe ich versucht in Worte zu fassen!
Ich hätte nie so einfach gedacht... ;-)

Mit freundlichen Grüßen,
Valentin Buck

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Aber Vorsicht:
Der erste und der letzte Punkt brauchen eine Sonderbehandlung!

Autor: Philipp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hüstel ich glaube es ist ziemlich einfach. Ich will die beiden 
stärksten lokalen Maxima suchen:

int max1 = 0;
int max2 = 0;

int pos1 = 0;
int pos2 = 0;

for (int i = 0; i < BINS; i++){
   int delta = f[i+1] - f[i];

   if (delta < 0){               // lokales Maximum
      if (f[i] > max1){          // neues globales Maximum
         max2 = max1;
         pos2 = pos1;
         max1 = f[i];
         pos1 = i;
      }
      else if (f[i] > max2){    // neues zweitgr. lok. Max.
         max2 = f[i];
         pos2 = i;
      }
   } 

}

Ich glaube, so kann es wohl funktionieren.

Autor: Philipp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... 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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Philipp schrieb:

> Ich glaube, so kann es wohl funktionieren.

Das denke ich nicht.
Das ist ein bischen zu einfach überlegt.

Aber probiers durch.

Autor: Philipp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
  schleife über alle Elemente {

    if modus == maximum suchen
       if steigung < 0 then
         maximum gefunden
         entscheiden ob man es aufheben will (nur die 2 Größten)
         modus = minimum suchen

    else if modus == minimum suchen
       if steigung > 0 then
         modus = maximum suchen
  }

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.

Autor: Philipp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.