STM32F405 - DSP Medianfilter

Michael Höller schrieb:
> Meinen derzeitigen Medianfilter habe ich mit for-schleifen gelöst.

Dass da irgendwo ne Schleife ist, sollte klar sein.
Wenn etwas optimiert werden soll, brauchen wir den code. Ansonsten 
findet man sogar auf dieser Seite Implementierungen in c

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.

:) 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 ;))

"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)

vielen Dank für Eure Denkanstöße,

werde jetzt einmal ein paar Vorschläge testen!

Danke!!!
Michael.