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
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 ;))
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(inti=1;i<1000-5;i++){
2
// value to be deleted from window
3
unsignedshortvd=array[i-1];
4
// value to be added to window
5
unsignedshortva=array[i+4];
6
for(intj=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(intk=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)
