STM32F405 - DSP Medianfilter

OP #3609748
Hallo,

hat von euch schon mal jemand einen Medianfilter auf einen STM32F4 
programmiert?

Ich benötige diesen um aus einer Datenreihe Ausreißer zu entfernen.

Meinen derzeitigen Medianfilter habe ich mit for-schleifen gelöst.
mit einer Filterlänge von 5 Punkte.

kennt ihr eine DSP-Funktion des Cortex-M4 einen Median-Filter zu 
optimieren?

Mein Ziel ist es, eine bessere Performance zu erreichen.
Derzeit benötigt mein Medianfilter bei einer Datenlänge von ca. 
1000Punkte ungefähr 6ms.

LG Michael
Wenn man den Ist-Zustand nicht kennt, dann kann man keine brauchbaren 
Tipps zur Optimierung geben.

Beispiel für völlig unbrachbaren Tipp: :)
Du schreibst
>Derzeit benötigt mein Medianfilter bei einer Datenlänge von ca.
>1000Punkte ungefähr 6ms.

Dann schreib ich einfach: Verzehnfache deine Taktfrequenz, dann brauchst 
Du nur noch 0.6ms.
OP
:) Okay!
hier mein derzeitiger Programmcode:


static void MedianFilter(void)
{
    // TODO
    //

    static unsigned short z = 0, y = 0, x = 0, v = 0, min = 0, temp = 0;
    static unsigned short window[5];


    for(z = 2; z < (buffer_index - 2); z++)
    {
        for(y = 0; y < 5; y++)
        {
            window[y] = FilterData.D_Buf_CACHE[y+z];
        }

        for(x = 0; x < 3; x++)
        {
            min = x;
            for((v = x +1); v < 5; v++)
            {
                if(window[v] < window[min])
                    min = v;
            }
            temp = window[x];
            window[x] = window[min];
            window[min] = temp;
        }
        // get result --> middle element
        FilterData.D_MF_Buf[z - 2] = window[2];
    }
}

Fertige DSP - Funktionen gibt es ja anscheinend nicht, ähnliche wie bei 
den FIR-Filtern zum beispiel!

vielen Dank
Erster Gedanke: Muss der Filter nachträglich laufen oder ginge das auch 
direkt beim Eintreffen von genügend (Fenstergröße) Daten?
Zweiter Gedanke: Das Sortieren ist in dieser Form nicht nötig. Stichwort 
ist find-k-smallest-element / Blum-Floyd-Pratt-Rivest-Tarjan-Algorithmus 
1) was den Aufwand an dieser Stelle auf O(n) senken würde (bei dieser 
Fenstergröße eigentlich nicht nötig).
Dritter Gedanke: Warum braucht der jetzige Algorithmus so lange?
Grob überschlagen bei 1000 Elementen:
- 1000 * 5 Lesezugriffe auf das Ausgangsarray, 5000
- 1000 * 5 Schreibzugriffe auf das Fenster, 5000
- 1000 * (18 Schreib- und 6 Lesezugriffe und 9 Vergleiche), 33000
- 1000 * (1 Schreib- und Lesezugriff zum Zurückschreiben), 2000
Grob 45000 Operationen in 6 ms also 7.5 MHz...

1) http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
(wer mal Info oder ähnliches studiert (hat), wird wahrscheinlich mehr 
als einen der Autoren wiedererkennen ;))
Gast
Ich werfe mal etwas Wahrscheinlichkeit mit in die Auswertung.
Die Auswertung dauert also ca. 33 Cycles.
Bei
1
for(z = 2; z < (buffer_index - 2); z++)
2
    {
3
        for(y = 0; y < 5; y++)
4
        {
5
            window[y] = FilterData.D_Buf_CACHE[y+z];
6
        }
wird ja im Endeffekt Daten[y] bis Daten[y+4] untersucht. Beim nächsten 
Durchlauf untersucht man Daten[y+1] bis Daten[y+5]. Es wird also nur 
Datenpunkt Data[y] mit Data[y+5] ersetzt, der Rest bleibt erhalten.
Ist also der Datenpunkt Data[y] der herausfällt, nicht der Median, gibt 
es zwei Möglichkeiten: Er ist entweder größer als der Median oder 
kleiner. Trifft auf Data[y+5] das selbe zu (Also beide sind 
größer/kleiner als der Median) ändert sich der Median nicht.
Also:
1
 if((Data[y] > Median_alt) && (Data[y+5] > Median_alt))
2
       Median_neu = Median_alt;
Das selbe gilt auch für Data[y] < Median_alt

Fügt man also zusätzliche 4 Vergleiche zu den 33 Cycles der Auswertung, 
hat man 37 Cycles. Zu 40% (Bei statistischen Zahlen) trifft aber der 
Fall ein, dass Data[y] und Data[y+5] im selben Verhältnis zum Median 
stehen, wodurch sich der Durchlauf für diese Daten auf 4 Cycles 
reduziert.

Das ergibt im Durchschnitt:
0,4* 4 Cycles + 0,6 * 37 = 23,8 Cycles.

Man reduziert also die 45000 Cycles auf 35800 Cycles, also von 6ms auf 
4,77ms

Das wäre so meine Idee, ohne jetzt groß den Auswertealgorhithmus zu 
ändern :D
"Fieser" Trick:
Wenn die ersten 5 Werte sortiert sind, braucht bei den nächsten 5 Werten 
nur noch geschaut werden wo sich der neue einsortiert.
1
  for (int i = 1; i < 1000 - 5; i++) {
2
    // value to be deleted from window
3
    unsigned short vd = array[i - 1];
4
    // value to be added to window
5
    unsigned short va = array[i + 4];
6
    for (int j = 0; j < 5; j++) {
7
      if (window[j] == vd) {
8
        // total operations in k-loop: 5 + 5 comparisons + 4 read and 4 + 1 write operation
9
        for (int k = 0; k < 5; k++) {
10
          if (k == j) continue;
11
          if (va < window[k]) {
12
            // now insert va...
13
            //  d, v1, v2, v3, v4
14
            // v0,  d, v2, v3, v4
15
            // v0, v1,  d, v3, v4
16
            // v0, v1, v2,  d, v4
17
            // v0, v1, v2, v3, d            
18
          }
19
        }
20
        break;
21
      }
22
    }
23
  }
Das sollten, falls der Algorithmus so stimmt, dann 1000 * (5 + 5 + 5 + 4 
+ 5) = 1000 * 24 = 24000 Operationen sein
(da fehlen noch die Vergleiche, um die passenden Verschiebungen im 
Fenster zu erledigen)

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 12 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.