Schnell Median-Filter in C / C++ für `UINT16` 2D-Array

Weiß jemand eine schnelle median-filter-Algorithmus für 16-bit (unsigned short) arrays in c++?

http://nomis80.org/ctmf.html

Dieser scheint Recht vielversprechend, aber es scheint nur zu arbeiten mit byte-arrays. Weiß jemand, wie es zu ändern, um die Arbeit mit shorts oder einen alternativen Algorithmus?

  • Haben Sie versucht, std::nth_element? Es ist O(n) gegenüber O(n log n) für ein quicksort.
  • Sie wollen nicht, dies zu ändern-Algorithmus, um es mit kurzarbeit, da die Laufzeit pro pixel ist proportional zu 2^n, wobei n die Anzahl der bits, die in der Datentyp verwendet wird. 256 8-bit-arrays ist schon schmerzhaft genug, Sie nicht wollen, zu gehen bis 65536 für 16-bit-arrays. Siehe meine Antwort für einen schnelleren Algorithmus, obwohl es ist O(log r) pro pixel anstelle von O(1).
  • Wenn Sie nicht wollen, zu tun, median-Filterung, die ist, was Sie tun, zum Beispiel in der Bildverarbeitung, wo Sie einen Mittelwert für jeden pixel, sondern wollen einfach nur, um eine zu finden, median, @smoken Kommentar relevant ist.
InformationsquelleAutor user1359341 | 2012-04-26
  1. 4

    Der Technik in der Papier stützt sich auf die Schaffung eines Histogramm mit 256 bins für eine 8-bit-pixel-Kanal. Konvertierung zu 16 bit pro Kanal würde erfordern ein Histogramm mit 65536 Ablagen und ein Histogramm erforderlich ist, für jede Spalte des Bildes. Aufblasen die Anforderungen an den Arbeitsspeicher von 256 macht dies zu einer weniger effizienten Algorithmus, insgesamt aber wahrscheinlich noch machbar mit der heutigen hardware.

    Mit dem vorgeschlagenen Optimierung der Zerschlagung der Histogramm in grob-und fein-Abschnitten sollten weitere Verringerung der Laufzeit Treffer nur 16x.

    Für kleine radius Werte, die ich glaube, Sie finden traditionelle Methoden der median-Filterung wird schneller.

    InformationsquelleAutor Mark Ransom
  2. 3

    Schnell Median Suche - Ein ANSI-C-Implementierung (PDF) ist etwas für C, es ist ein Papier mit dem Titel "Fast median Suche: eine ANSI-C-Implementierung". Der Autor behauptet, es ist O(log(n)), er bietet auch etwas code, vielleicht kann es dir helfen werde. Es ist nicht besser als dein vorgeschlagener code, aber vielleicht einen Blick Wert.

    • Das Papier verknüpft die Frage ist O(1) besser als O(log n).
    • Yep, aber diese ein, vielleicht gibt uns weitere Impulse, aber Sie sind auf jeden Fall Recht. Ich habe ein kleines edit, zur Klarstellung meiner intention.
    • O(1) bedeutet nicht automatisch, besser als O(log(n)) da ist immer eine Konstante der O-notation verbirgt. In diesem Fall werden die O(1) Algorithmus ist es viel langsamer als die O(log(n)) - Algorithmus (für andere als 2-bit-oder vielleicht 4-bit-Kanal-Werte). Der O(1) Papier-arbeiten mit Histogrammen, wodurch die Laufzeit pro pixel proportional zu 2^b, wobei b die Anzahl der bits pro Kanal, was bei 8-bit 256 16 bit 65536 (obwohl diese zahlen sind Konstanten, also O(1)). Dieser macht schnell die O(1) Algorithmus sehr langsam mehr bits, die Sie hinzufügen, um den Kanal-Werten.
    InformationsquelleAutor Sebastian Dressler
  3. 1

    Dieser Artikel beschreibt eine Methode für die median-Filterung von Bildern, die läuft in O(log r) Zeit pro pixel, wobei r wird die filter-radius, und funktioniert für alle Datentypen (sei es 8-bit-Integer oder Double):

    Schnell Median und Bilaterale Filterung

    • Ist es ein C / C++ Implementierung Wiess " - Methode überall?
    • Ich weiß es nicht. Wenn Sie sich über eine, bitte sagen Sie mir!
    InformationsquelleAutor HelloGoodbye
  4. 0

    Ich weiß, diese Frage ist etwas alt, aber ich habe auch interessiert in der median-Filterung. Wenn man die Arbeit mit Signalen oder Bildern, dann wird es eine große überschneidung von Daten für die Verarbeitung der Fenster. Dies kann in Anspruch genommen werden.

    Ich habe einige benchmark-code hier: 1D moving median-Filterung in C++

    Es ist template-basiert, so sollte es funktionieren mit den meisten POD-Datentypen.

    Laut meiner Ergebnisse std::nth_element hat schlechte Leistung für einen gleitenden median, als es muss die Art der Fenster jeweils die Werte.

    Jedoch, mit einem pool von Werten, die gehalten wird sortiert, die man durchführen kann, der median mit 3 Betrieb.

    1. Entfernen älteste Wert aus dem pool (ruft std::lower_bound)
    2. Einfügen neuer Wert in das Schwimmbad (ruft std::lower_bound)
    3. Speichern neuer Wert in der history-Puffer

    Der median ist nun der mittlere Wert in den pool.

    Ich hoffe, jemand findet diese interessante und trägt Ihre Ideen!

    InformationsquelleAutor Nick
  5. 0

    Siehe Gleichungen 4 und 5 in dem folgenden Papier. Die Komplexität ist O(N*W) wo W ist die Breite des filters und N ist die Anzahl der Proben.

    Sehen Rauschunterdrückung durch Vektor-Median-Filterung.

    InformationsquelleAutor RawMean
Schreibe einen Kommentar