Заметка

Реализация медианного фильтра на QLUA

  1  

В статье рассмотрены различные варианты сортировки массивов, сортировка является неотьемлемой частью вычисления медианы

Введение

Мне всегда не нравился QUIK тем, что в нем нельзя было писать собственные индикаторы, если быть точнее, можно, но результаты реализация индикатора вряд ли бы отвечала заявленным требованиям, так как скрипты на qpile запускаются по таймеру, а не по событию. Я не считаю язык qpile ущербным или не пригодным для реализации, по мнению некоторых робостроителей, сложных алгоритмов. Всякий алгоритм можно реализовать на любом языке программирования, вопрос только в уровне затрат на реализацию, наличие или отсутствие нужных функций и процедур.
С появлением в QUIK QLUA все заиграло для меня яркими красками.
В заметке хочу рассмотреть вопросы реализации медианного фильтра на QLUA.

Постановка задачи

Медианный фильтр используются для уменьшения уровня шума. Алгоритм рассчета фильтра достаточно прост и доступен широким массам. Одним из пунктов рассчета медианы — является сортировка подмассива. Вот на этом и остановимся подробнее.

 Сортировка массива

Что такого сложного в сортировке на первый взгляд? Алгоритмов сортировки великое множество, их эффективность оценивается по быстродействию. Рассмотрим несколько алгоритмов сортировки и попытаемся их сравнить. Здесь не будем рассматривать вопросы создания индикаторов на qlua, только сортировка и больше ничего.

  Встроенный алгоритм сортировки

Рассмотрим первый вариант расчета медианного фильтра:

Settings=
{
  Name = "_Median", 
  period = 12, 
  line = 
  { {
   Name = "Median", 
   Color = RGB(255, 0, 0), 
   Type = TYPE_LINE, Width = 2 } } } 
function Init() 
 return 1 
end

function OnCalculate(index) 
  if index < Settings.period then 
    return nil 
  else 
    local ind = 1 
    local cash = {}
    for i = index-Settings.period+1, index do 
         cash[ind] = C(i)
         ind = ind + 1
   end 
   table.sort(cash)
   return cash[math.floor(Settings.period/2)]
 end 
end

 
Здесь сортировка выполняется стандартной процедурой table.sort , один из её недостатков — не устойчивая сортировка (меняет местами элементы массива с одинаковыми значениями)

Сортировка "пузырьком"

Изменим предыдущий пример, заменив table.sort(cash) на следующий набор команд:

local tmp = 0
for i = 1, Settings.period-1 do 
  for j = 1, Settings.period-1 do 
    if cash[j] > cash[j+1] then
        tmp = cash[j]
        cash[j] = cash[j+1]
        cash[j+1] = tmp
     end
 end
end
 
Данный метод не особо "шустрый", но ничего страшного, нам он нужен для сравнения

Быстрая сортировка

Один из популярных алгоритмов сортировки массивов, приведем весь код индикатора:

Settings=
{
   Name = "_Median2", 
   period = 12, 
   line = 
      { {
      Name = "Median2", 
      Color = RGB(255, 0, 0), 
      Type = TYPE_LINE, Width = 2 } } } 
function Init() 
   return 1 
end

function asort(ar1, low, high)
   local wsp = 0
   local i=low
   local j=high

   local m=ar1[math.floor((i+j) / 2)] -- Взятие среднего опорного элемента
   repeat
      while ar1[i]<m do 
         i = i + 1 -- изменить порядок сортировки можно
      end
      while ar1[j]>m do 
         j = j — 1 -- поменяв >< в этих двух строках 
      end
      if i<=j then 
         wsp=ar1[i]
         ar1[i]=ar1[j]
         ar1[j]=wsp
         i = i + 1
         j = j — 1
      end;
   until i>j

   if low<j then 
      ar1 = asort(ar1, low, j)
   end
   if i<high then 
      ar1 = asort(ar1, i, high)
   end
   return ar1
end


function qSort(ar)
   return asort(ar, 1, Settings.period)
end

function OnCalculate(index) 
   if index < Settings.period then 
      return nil 
   else 
      local ind = 1 
      local cash = {}
      for i = index-Settings.period+1, index do 
      cash[ind] = C(i)
      ind = ind + 1
   end 
   cash = qSort(cash)
  return cash[math.floor(Settings.period/2)]
end
end

 Здесь метод быстрой сортировки реализован на основе рекурсии

Авторский метод сортировки

Не скромно, но похожей реализации медианного фильтра не встречал. У всех рассмотренных методов сортировки один общий недостаток: при появлении нового значения цены все алгоритмы берут последние N отсчетов цены (N — параметр фильтрации) и сортируют их, то есть на каждом шаге выполняется сортировка массива данных, при этом на предыдущем отсчете N-1 значений уже были отсортированы.
Суть предлагаемого метода:
1) при появлении нового тика сразу сортируем массив и запоминаем его
2) при появлении следующего тика 
  2.1) удалим N+1 отсчет (считая новый тик отсчетом номер один) в отсортированном массиве 
  2.2) добавим к отсортированному массиву новый тик
  2.3) сортируем получившийся массив, для сортировки достаточно осуществить один проход, например, {1, 2, 5, 6, 4}, здесь {1, 2, 5, 6} часть массива, которая была отсортирована на предыдущем тике, добавили новый элемент {6} — нужен один проход, чтобы отсортировать исходный массив.
Код:

Settings=
{
    Name = "_Median3", 
    period = 12, 
    line = 
        { {
        Name = "Median3", 
        Color = RGB(255, 0, 0), 
        Type = TYPE_LINE, Width = 2 } } } 
function Init()
    m_cach = {}
    m_index = {}
    last_ind = 0
    return 1 
end

function qSort1(arr,arr_ind) 
    if #arr > 1 then
        local ind = #arr
        local tmp = 0
        local tmp_i = 0
        local cycle = false
        repeat
        if (ind > 1) then
            if (arr[ind] < arr[ind-1]) then
                tmp = arr[ind-1]
                tmp_i = arr_ind[ind-1]
                arr[ind-1] = arr[ind]
                arr_ind[ind-1] = arr_ind[ind]
                arr[ind] = tmp
                arr_ind[ind] = tmp_i
                ind = ind — 1
            else
                cycle = true
            end
        else
            cycle = true
        end
    until cycle
    end
    return arr, arr_ind
end

function min_arr (_arr)
    local min_index = _arr[1]
    local min_i = 1
    for i = 2,#_arr do
        if min_index > _arr[i] then
            min_index = _arr[i]
            min_i = i
        end
    end
    return min_i
end

function find_index (_arr,index1)
    local ind = 1
    while _arr[ind]~=index1 do
        ind = ind +1
    end
    return ind
end

function OnCalculate(index) 
    if index <= Settings.period then 
        if index == 1 then
            m_cach = {}
            m_index = {}
            last_ind = 0
        end
        table.insert(m_cach,C(index))
        table.insert(m_index,index)
        m_cach, m_index = qSort1(m_cach,m_index)
        last_ind = index
        return nil 
    else 
        if (last_ind == index) then
            local ind = find_index(m_index,index)
            table.remove(m_cach,ind)
            table.remove(m_index,ind)
        else
            local min_index = min_arr(m_index)
            table.remove(m_cach,min_index)
            table.remove(m_index,min_index)
        end
        table.insert(m_cach,C(index))
        table.insert(m_index,index)
        m_cach,m_index = qSort1(m_cach,m_index)
        last_ind = index
        return m_cach[math.floor(Settings.period/2)]
    end
end

Результаты

 Для сравнения медианных фильтров, использующих разные алгоритмы сортировки используем тиковый график цен на акции Сбербанка на 04.03.2014  с окном фильтрации в 200 тиков:
  • встроенный алгоритм сортировки — 35 сек
  • сортировка пузырьком — 485 сек
  • быстрая сортировка — 39 сек
  • авторская сортировка — 7 сек
Медиана с сортировкой пузырьком показала худшее время — все очевидно, время сортировки пропорционально квадрату n (n — размерность массива), быстрая сортировка — хорошо, но реализован на рекурсии, что кушает ресурсы + многократное копирование массива в памяти...Преимущество авторской сортировки очевидны — сортировка заточена под предметную область.

Буду рад, если кому-то мои результаты будут полезны.

Медианный фильтр с окном 12
Прикрепленные файлы

·   median3.rar

Комментарии

Николай Камынин — 7 апреля 2014 г.

amandra,
Увы, сортировка "авторским методом" искажает свойства фильтра.
Строго говоря, фильтр перестает быть медианным.

0 +

amandra — 7 апреля 2014 г.

Николай Камынин, поясните

0 +

oktb — 8 апреля 2014 г.

Добрый день.
Ув. amandra, можно попросить Вас выложить скомпилированный под Квик файл .lcua
Спасибо большое.

0 +

orekton — 9 апреля 2014 г.

oktb, файл прикрепили к заметке.

0 +

oktb — 10 апреля 2014 г.

Спасибо.

0 +

Николай Камынин — 11 апреля 2014 г.

amandra,
Изначально фильтрация происходит во времени.
Соответствующее временное окно сдвигается во времени путем удаления крайнего левого отсчета и добавлением нового.
Если же удалять и добавлять отсчет в отсортированном массиве, то фильтрация происходит не по времени, а по амплитуде. При этом будет замещаться либо минимальный либо максимальный отсчет, который в реальности не располагается крайним слева по времени.
Таким образом, получаем фильтр с другими, чем у медианного фильтра свойствами.

0 +

amandra — 11 апреля 2014 г.

Николай Камынин,
1) все верно, но удаляется не первый элемент в отсортированном массиве, а первый по времени, поэтому храниться не только исходно окно, которое сортируется, а так же индексы, чтобы удалять последний по времени, а не амплитуде. С помощью функции find_index и определяется какую позицию в отсортированном массиве нужно удалить.
2) ошибка у меня есть, как минимум одна - для нечетных значений окна нужно иначе вычислять медиану

0 +

Николай Камынин — 11 апреля 2014 г.

Вообще-то,медианный фильтр - это робастная оценка среднего.
Очень удобная для расчета стат данных, но малоэффективна для торгов на бирже.

0 +

Николай Камынин — 11 апреля 2014 г.

amandra,
тогда фильтр не искажается,
но к сортировке добавляется поиск по индексу и возможный выигрыш по-времени расчета не очевиден.

0 +

Николай Камынин — 11 апреля 2014 г.

amandra,
Из описания Вашего алгоритма не видно, что Вы используете начальную индексацию для удаления:
" 2.1) удалим N+1 отсчет (считая новый тик отсчетом номер один) в отсортированном массиве "

0 +

Николай Камынин — 11 апреля 2014 г.

amandra,
если использовать отсортированный массив, то надо новый отсчет не добавлять в отсортированный, а замещать им крайний левый.

0 +

Николай Камынин — 11 апреля 2014 г.

если удалять и добавлять, то появляются операции перемещения всех элементов на один. Кроме того, необходимо в два раза большую память для данных.
Короче говоря, "овчинка выделки не стоит".

0 +

Написать комментарий

Чтобы написать комментарий, необходимо авторизоваться.

Написать администратору