Schnelles Histogramm

  • Allgemein

Es gibt 13 Antworten in diesem Thema. Der letzte Beitrag () ist von ~blaze~.

    Schnelles Histogramm

    Ich bin gerade dabei mir einen Histogrammalgorithmus zu basteln.
    Zur Info: Es können durchaus 100000 Single Messwerte zu verarbeiten sein.
    (Keine Bilddaten)

    Zuerst hatte ich halt zwei ineinanderliegende For Next Schleifen probiert.
    Ist natürlich zu langsam alle Messwerte für jede Klassierung neu "in die Hand" zu nehmen.

    Jetzt verwende ich gerade eine Funktion, die aus dem Messwert die Klassierung berechnet.

    Eine weitere Idee die ich habe wäre die Schrittweite zwischen den Messpunkten
    dynamisch zu verändern und bei jedem Durchlauf neu zu zeichnen. Irgendwann wären
    dann alle Messwerte erfasst. So könnte man jederzeit die Anzeige unterbrechen, da sich
    vielleicht an der Darstellung doch nichts mehr gravierendes ändert.

    Eine ähnliche Möglichkeit wäre über einen Zufallsgenerator die Messwerte auszuwählen.

    Hat sich hier schon mal jemand mit diesem Problem beschäftigt und hat noch eine
    bessere Idee?

    Ich hab nicht genau verstanden, was Du meinst.
    Bei mir gibt es 2 Sorten Histogramm-Algorithmen:
    1. 8 BitPerPixel Images, da wird der Bildwert als Index des Histogrammfeldes verswendet
    und
    2. der "klassische Weg", Anzahl der Histogrammklassen = ln(Anzahl der Werte), Klassenbreite so, dass Min / Max nahe dem äußeren Rand der äußersten "Scheiben" liegen. Hier ist es natürlich aufwändiger, die Scheibennummer zu berechnen.
    Wie ich das so sehe, ist die Geschwindigkeit Dein Problem.
    Ist es möglich, Deine Single-Daten iwie in Long zu konvertieren, da kannst Du wieder bit Bit-Shift-Methoden rangehen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Einem Histogramm ist es egal, woher die Daten kommen.
    Es geht darum, wie sie reinkommen.
    Bei 16-Bit-Daten kann man ein 256-stufiges Histogramm so berechnen:

    VB.NET-Quellcode

    1. For i = 0 To feld.Length - 1
    2. Histogramm(Feld(i) >> 8) += 1
    3. Next
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hi
    vmtl. sind jeweils Bereicheinschränkungen vorhanden. Unterteile doch die Werte immer in gleichgroße Schrittweiten ein und bau da so eine baumartige Struktur herum. Sobald die Werte nicht mehr gültig sind, löscht du die Baumstruktur und erzeugst eine neue (lässt sich übrigens auch wunderbar parallelisieren). Die Daten behältst du dazu erst mal in z.B. einer IList(Of T) und updatest alle paar Sekunden das letzte Segment in der dargestellten Baumstruktur und bildest jeweils eine neue auf der Datenbasis.
    Sinnvoll wäre übrigens auch, erst den alten Baum zu behalten und eine Annäherung darzustellen, wenn ein neuer Baum eingeführt wird. Wenn dann der neue Baum fertig ist, updatest du den Baum dann.

    Gruß
    ~blaze~

    Quasi, nur dass ein Durchschnittswert zwischengepuffert wird oder mehrere. Also sagen wir, du hast insgesamt 10 000 Werte in deiner Liste. Davon werden auf einmal nur 500 dargestellt. Wenn du jetzt deine Liste in 20-er Schritte unterteilst, hast du insgesamt eben 500 Werte. Da sich die Werte davor ja nicht ändern sollten, kannst du den Wert im Puffer behalten. Wenn du jetzt die Schrittweite ändern musst, z.B. von 500 Werten auf 1000, musst du den gepufferten Wert neu berechnen - und das kannst du elegant mit Multithreading bewerkstelligen. Sobald alle Berechnungen fertig sind, zeichnest du eben das Histogramm oder benötigte Ausschnitte neu. Das wäre jetzt ein einfacher Ansatz. Wenn du das jetzt Baumartig gestaltest, führst du die Unterteilung mit der Pufferung eben mehrfach durch. Sagen wir, du hast 10^6 Werte. Dann kannst du jetzt in einer Ebene schon mal 10 Werte zusammenrechnen und damit die 10^6 auf 10^5 Werte reduzieren, da man auf einem Bildschirm eh keine 10^6 Werte sieht. Diese 10^5 Werte kannst du erneut auf 500 Werte herunterbrechen usw.
    Durch die Pufferung musst du eben weniger Werte neuberechnen, wenn sie keine Relevanz aufweisen und kannst durch eine Interpolation zumindest schon mal einen Zwischenwert darstellen. Dazu könnte man sich einen guten Interpolationsalgorithmus überlegen, wenn das gewünscht ist. ;)
    Ich denk' außerdem, dass eine Skalierung der dargestellten Werte auf Integer bzw. Short sinnvoll wäre. Mit Gleitkommazahlen rechnet's sich nicht immer effizient. Wenn du die auf Short.MaxValue herunterrechnen kannst, ist es ggf. ebenfalls noch mal um einiges effizienter.

    Gruß
    ~blaze~

    Die dargestellten Klassierungs-Werte sind automatisch ohne Kommastellen.
    Jeder Abschnitt (Klassierung) ist ja einfach nur ein Zähler.
    D.h. Abschnitt Null geht meinetwegen von 0 bis 15.5
    Dann wird die Anzahl aller Messwerte die zwischen 0 und 15.5 liegen
    gezählt. Diese Anzahl ist dann der Betrag des nullten Abschnittes.
    Der nächste Abschnitt geht dann von 15.5 bis 31 usw.
    Das Aufaddieren geht also ganz einfach mit Integeraddition.

    Für die Darstellung will ich allerdings dann die Werte so
    normieren, dass der höchste Wert gerade noch im
    Anzeigebereich dargestellt wird. Das ist dann leider wieder eine
    zusätzliche Schleife mit einer Division.

    Im Prinzip sehr einfach:
    Long nehmen und Werte auf 2^32-1 normieren. Dann kannst du immer in 2^32-er Schritten addieren und danach durch die Anzahl teilen:

    VB.NET-Quellcode

    1. Dim value As Long = 0
    2. Dim items As IList(Of Integer) 'Die Werte, die auf 32768 normiert wurden
    3. For i As Integer = 0 To items.Count - 1
    4. value += items(i)
    5. Next
    6. value \= items.Length 'Durchschnittswert normiert auf 32768
    7. Dim hValue As Integer = CInt(ClientSize.Height * value \ 32768) 'dargestellte Hoehe

    Damit dürfte es relativ effizient sein, wenn du noch dieses Baumartige vorgehen statt dem Array wählst. Was genau ist das für eine Klassierung?

    Gruß
    ~blaze~

    War vielleicht etwas blöd gestellt. Für die Häufigkeitsverteilung würde es sich halt anbieten, quasi Environment.ProcessorCount viele Bäume parallel zu erzeugen und dann zu einem ganzen zusammenzufassen. Die Werte sind quasi zufällig oder? Da lässt sich keine Abschätzung der Tendenz der nachfolgenden Werte bestimmen, woraus man eine sinnvolle Unterteilung der Werte mit Abweichung, etc. herleiten könnte?
    Ist ja klar, je mehr Werte bereits in der Verteilung mit drin sind, desto geringer spielt ein einzelner Wert mit ein. Wenn du eine Unterteilung hättest, könntest du es gut abschätzen, ansonsten müsstest du immer durch die "Abstände" (15.5) teilen und herausfinden, welchem Index in der Verteilung der Wert zugehörig ist.
    Sagen wir, du kannst maximal 100 Einträge im Verteilungsarray haben, dann erzeugst du für jeden Thread einen Teilbereich des Quellarrays (mit den Messwerten), der geht ja dann von threadIndex * totalCount / threadCount bis zum darauffolgenden Threadbereichsanfang - 1 oder Arrayende. Wenn eine Einteilung der Messwerte möglich ist, passt du die Indizierung entsprechend den erwarteten Werten an. Jeder Thread hat ein eigenes Verteilungsarray, das er nach einem Delay an ein gemeinsames Array schreibt. Dazu könnte man z.B. die System.Diagnostics.StopWatch.GetTimeStamp()-Funktion verwenden.

    VB.NET-Quellcode

    1. Dim globalDistr() As Integer = _globalDistribution 'globale Verteilung
    2. Dim distr(globalDistr.Length - 1) As Integer 'Verteilung dieses Threads
    3. Dim values() As Integer 'Alle Werte
    4. Dim sourceIndex, destinationIndex As Integer 'Start- und End-Index dieses Threads
    5. Dim last, current As Long = System.Diagnostics.Stopwatch.GetTimeStamp()
    6. Dim delay As Long = Me.Delay * System.Diagnostics.Stopwatch.Frequency \ 1000 'Delay = Verzoegerung des Updates in Millisekunden
    7. For i As Integer = sourceIndex To destinationIndex Step stepsPerCheck
    8. 'einige Schritte auf einmal vornehmen
    9. For j As Integer = i To Math.Min(destinationIndex, i + stepsPerCheck - 1)
    10. distr(values(j) \ stepv) += 1 'den Wert zum zugehoerigen Bereich hinzufuegen. Statt stepv = 15.5 eben stepv = 31 waehlen und value << 2 nehmen
    11. Next
    12. current = System.Diagnostics.StopWatch.GetTimeStamp()
    14. If current >= last + delay Then
    15. last = current
    16. SyncLock globalDistr
    17. For j As Integer = 0 To globalDistr.Length -1
    18. globalDistr(j) += distr(j)
    19. Next
    20. UpdateValues() 'sollte den Invalidate-Vorgang ausfuehren. Die Threads fuehren ein Update ziemlich parallel aus, daher vorher ggf. abfragen
    21. End SyncLock
    22. Array.Clear(distr, 0, distr.Length)
    23. End if
    24. Next
    25. SyncLock globalDistr
    26. For j As Integer = 0 To globalDistr.Length -1
    27. globalDistr(j) += distr(j)
    28. Next
    29. UpdateValues() 'sollte den Invalidate-Vorgang ausfuehren. Die Threads fuehren ein Update ziemlich parallel aus, daher vorher ggf. abfragen
    30. End SyncLock

    Angemerkt sei übrigens, dass ein geringer Delay einen Flaschenhals bewirkt.

    Btw. sorry, hatte es am Anfang missverstanden.

    Gruß
    ~blaze~

    Danke, da hast du dir aber wirklich Mühe gemacht. :)

    Auf dem Heimweg hatte ich mir gerade überlegt, ob ich vielleicht
    mit Kanonen auf Spatzen schieße.

    Wenn ich einfach meine Messwertliste sortieren lasse und
    dann vor der grafischen Ausgabe einen gleitenden Durchschnitt
    drüber lege? Wieviele Werte ich zusammenfasse kann ich ja einstellen.

    Es geht ja nur um eine Visualisierung der Messwerte und nicht um
    eine qualitative Analyse.

    Kein Problem, ich hoff' ich habs dieses mal richtig gemacht. ;)

    Sortieren geht halt auf die Performance und letztendlich bringts dir fast nichts. Bei der Sortierung werden immer die Werte mit den Werten verglichen, aber in deinem Fall ist ja die Sortierung eigentlich nicht erforderlich, sondern nur die Zuordnung zu einer Gesamtzahl. Mit Sortierung dürfte es sogar langsamer laufen, als ohne. ;)
    Meine Lösung wäre in O(n) und das hinzufügen weiterer Werte in O(1), denk ich, da du ja nur den Index in der globalen Verteilung auswählen musst, der dem Bereich entspricht. Die mit Sortierung wäre wohl maximal in O(n log n) und da wäre halt immernoch das Problem, den Bereich auszuwählen, in dem die Werte einem Intervall angehören.

    Gruß
    ~blaze~