Медіанний фільтр (Median Filter)

Програми для ARDUINO DUE
Аватар користувача
radioman
Site Admin
Повідомлень: 104
З нами з: 28 вересня 2020, 12:01
Дякував (ла): 6 разів
Подякували: 2 рази

Медіанний фільтр (Median Filter)

Повідомлення radioman »

У проекті IB металошукача на ARDUINO DUE для фільтрації значення VDI було використано медіанний фільтр (Filter size > 3), але він не коректно працює із "піками" з іншим знаком ніж основний сигнал.
pawa запропонував свій варіант медіанного фільтра:

Код: Виділити все

/* https://radioman.com.ua */

int MedianFilter(int[] window)
{               
    //Sortuvannya
    for (int i = 0; i < window.Length - 1; i++)
    {
        for (int j = 0; j < window.Length - 1 - i; j++)
        {
            if (window[j] > window[j + 1])
            {
                int tmp = window[j];
                window[j] = window[j + 1];
                window[j + 1] = tmp;
            }
        }
    }
	
    //Povernennya seredn`ogo
    int index = window.Length / 2;
    if ((window.Length & 0x01) == 1){
        return window[index];
    }else{
        return (window[index] + window[index - 1]) / 2;
    }
}
При адаптації до ARDUINO, зіткнувся з тим, що відсутня функція window.Length котра дає нам кількість елементів масиву (хоча для даного завдання довжину масиву краще задати змінною), тому для збереження універсальності було використано оператор sizeof (window), котрий дає нам довжину масиву в байтах. Для того, щоб отримати розмір масиву, необхідно розділити довжину масиву на кількість байтів одного елемента (так як у нас тип масиву "int", довжина одного елемента 4 байти).
Наступною перепоною було те, що у функцію не можна передати масив, а лише посилання на нього. Таким чином функція працює, і модифікує (!), з основним масивом. Для уникнення змін в основному масиві, прийшлось зробити його копіювання в допоміжний вже у самій функції.

В результаті отримано наступний коод медіанного фільтра:

Код: Виділити все

/* медіана pawa */
/* https://radioman.com.ua */

int window[] = {12, 2, 4, 8, 10, 6};                                            // тестовий масив
int newArray[sizeof (window) >> 2];                                             // копія тестового масиву
unsigned long time1;                                                            // значення лічильника "micros" перед початком виконання функції
unsigned long time2;                                                            // значення лічильника "micros" після виконання функції
unsigned long time0;                                                            // час виконання функції
int intWDI;                                                                     // медіана

void setup() {
  Serial.begin(115200);
}
void loop()

{
  time1 = micros();
  //intWDI = MedianFilter(window, sizeof (window) / sizeof(int));               // отримання медіани
  //intWDI = MedianFilter(window, sizeof (window)/4);                           // те саме, sizeof(int)=4
  intWDI = MedianFilter(window, sizeof (window) >> 2);                          // те саме, ділення 4 можна виконати зсувом вправо на 2
  time2 = micros();
  time0 = time2 - time1;

  //Serial.print("WDI = "); Serial.println(intWDI);                             // вивід в монітор медіани
  Serial.print("Time = "); Serial.print(time0); Serial.println(" mks");         // вивід в монітор часу виконання функції
}
/* функція розрахунку медіани*/

int MedianFilter(int *window, int intArrSize)                                   // аргументами функції є посилання на масив та довжина масиву
{
  // копіювання масиву
  byte c;
  for (c = 0; c < intArrSize; c++)
  {
    newArray[c] = window[c];
  }

  //"бульбашкове" сортування
  for (int i = 0; i < intArrSize - 1; i++)
  {
    for (int j = 0; j < intArrSize - 1 - i; j++)
    {
      if (newArray[j] > newArray[j + 1])
      {
        int tmp = newArray[j];
        newArray[j] = newArray[j + 1];
        newArray[j + 1] = tmp;
      }
    }
  }

  //повернення середнього
  int index = intArrSize / 2;
  if ((intArrSize & 0x01) == 1) {
    return newArray[index];
  } else {
    int WDI = (newArray[index] + newArray[index - 1]) / 2;
    //int WDI = intArrSize;
    //int WDI = window[index];
    return WDI;
  }
}
PS. Даний код потребує вдосконалення. Виконується на ARDUINO DUE за 9 мікросекунд (без копіювання масиву - за 3). Можна його протестувати з іншими алгоритмами сортування. Копіювання масиву значно сповільнює роботу - 1 мікросекунда на кожен елемент; кращим був би алгоритм з масивом в самій функції і надсиланням до неї лише нового значення (початковий масив з нулів, масив сортується, надходять значення по одному, запам'ятовується індекс кожного нового значення і проводиться заміна найдавнішнього; тобто у відсортовому масиві замінюється лише одне значення, а не сортується кожен раз копія всього масиву).
pawa
Повідомлень: 75
З нами з: 28 вересня 2020, 20:26
Дякував (ла): 1 раз
Подякували: 5 разів

Re: Медіанний фільтр (Median Filter)

Повідомлення pawa »

Копіювання масиву - це погано. Якщо копіювати, то одразу під час сортування.
І так - масиви передаються за посиланням.
Аватар користувача
radioman
Site Admin
Повідомлень: 104
З нами з: 28 вересня 2020, 12:01
Дякував (ла): 6 разів
Подякували: 2 рази

Re: Медіанний фільтр (Median Filter)

Повідомлення radioman »

Скопіювати масив із одночасним сортуванням складно, кількість операцій знищить всю "економію". Вважається, що для масивів з 10-ма та менше елементів, найкращим є алгоритм сортування включенням ( Insertion sort):

Код: Виділити все

/* https://radioman.com.ua/viewtopic.php?p=140#p140 */
// сортування включенням( Insertion sort)

  int counter = 0;
  for (int i = 1; i < intArrSize; i++) {
    for (int j = i; j > 0 && newArray[j - 1] > newArray[j]; j--) {
      counter++;
      int tmp = newArray[j - 1];
      newArray[j - 1] = newArray[j];
      newArray[j] = tmp;
    }
  }
При заміні бульбашкового (Bubble sort) алгоритму на сортування включенням масиву з 6 елементів виграш становить 2 мікросекунди (7 мікросекунд замість 9; отже, виграш суттєвий, так як 6 мікросекунд триває копіювання масиву).

PS.В частково впорядкованому масиві його швидкодія повинна бути ще більшою, хоча часткове сортування при копіюванні масиву з наступним сортуванням за бульбашковим алгоритмом дало незначний приріст швидкодії (біля 0.5 мікросекунди).
Так як код часткового сортування при копіюванні масиву ще не повністю протестований (виникали баги) я його поки що не приводжу; але навряд чи це потрібно - саме сортування відбувається за 1 мікросекунду.
pawa
Повідомлень: 75
З нами з: 28 вересня 2020, 20:26
Дякував (ла): 1 раз
Подякували: 5 разів

Re: Медіанний фільтр (Median Filter)

Повідомлення pawa »

Усі звертання до масиву треба замінити на звертання за покажчиками.
Аватар користувача
radioman
Site Admin
Повідомлень: 104
З нами з: 28 вересня 2020, 12:01
Дякував (ла): 6 разів
Подякували: 2 рази

Re: Медіанний фільтр (Median Filter)

Повідомлення radioman »

Код :?: 8-)
Я зекономив ще одну мікросекунду (хоча очікував кращий результат - все таки пряме копіювання ділянок пам'яті :roll: ) копіюванням масиву до виклику функції:

Код: Виділити все

memcpy(newArray, window, sizeof (window));
intWDI = MedianFilter(newArray, sizeof (window) >> 2); 
І у самій функції вже опрацьовується готова копія:

Код: Виділити все

/* функція розрахунку медіани*/

int MedianFilter(int *newArray, int intArrSize)
...
pawa
Повідомлень: 75
З нами з: 28 вересня 2020, 20:26
Дякував (ла): 1 раз
Подякували: 5 разів

Re: Медіанний фільтр (Median Filter)

Повідомлення pawa »

radioman писав: 26 січня 2021, 22:18Код :?: 8-)
Так:

Код: Виділити все

  int counter = 0;
  for (int i = 1; i < intArrSize; i++) {
    for (int j = i; j > 0 && *(newArray + j - 1) > *(newArray + j); j--) {
      counter++;
      int tmp = *(newArray + j - 1);
      *(newArray + j - 1) = *(newArray + j);
      *(newArray + j) = tmp;
    }
  }
Або ось так

Код: Виділити все

  int counter = 0;
  for (int i = 1; i < intArrSize; i++) {
    for (int j = i; j > 0 && *(newArray + j - 1) > *(newArray + j); j--) {
      counter++;
      *(newArray + j - 1) ^= *(newArray + j);
      *(newArray + j) ^= *(newArray + j - 1);
      *(newArray + j - 1) ^= *(newArray + j);
    }
  }
Аватар користувача
radioman
Site Admin
Повідомлень: 104
З нами з: 28 вересня 2020, 12:01
Дякував (ла): 6 разів
Подякували: 2 рази

Re: Медіанний фільтр (Median Filter)

Повідомлення radioman »

Хороша робота :)
Час виконання стабільно 4 мікросекунди. Другий варіант, в окремих випадках, виконується за 3 мікросекунди. :o Перевірю ще чи не модифікується масив :roll:
pawa
Повідомлень: 75
З нами з: 28 вересня 2020, 20:26
Дякував (ла): 1 раз
Подякували: 5 разів

Re: Медіанний фільтр (Median Filter)

Повідомлення pawa »

Можна ще дещо скоротити час виконання..

Код: Виділити все

 
  int counter = 0;
  for (int i = 1; i < intArrSize; i++) {
    for (int j = i; j > 0; j--) {
      counter++;
      int *ptr1 = newArray + j;
      int *ptr2 = ptr1 - 1;
      if (*ptr2 > *ptr1){
        int tmp = *ptr1;
        *ptr1 = *ptr2;
        *ptr2 = tmp;
      }
    }
  }
  
Код не перевіряв, тому може бути десь помилка!
Аватар користувача
radioman
Site Admin
Повідомлень: 104
З нами з: 28 вересня 2020, 12:01
Дякував (ла): 6 разів
Подякували: 2 рази

Re: Медіанний фільтр (Median Filter)

Повідомлення radioman »

Нашвидкоруч перевірив. Працює правильно (на 6 елементах), але повільний: 7-8 мікросекунд в залежності від розташування елементів в масиві.
pawa
Повідомлень: 75
З нами з: 28 вересня 2020, 20:26
Дякував (ла): 1 раз
Подякували: 5 разів

Re: Медіанний фільтр (Median Filter)

Повідомлення pawa »

Зрозуміло, значить оптимізація працює краще на попередній код.
Відповісти