Фильтры "Среднее на пересечении" и "Среднее по квадрату"

[IvaniuS]

Картинки маленькие все (256х64) и я их конвертирую часто к <= 8bit т.е. чем меньше - тем лучше, просто хотел реализовать в общем смысле т.е. для всех изображений в 24bit режиме. Сейчас еще пробую сделать поиск конутра, это было бы намного лучше чем просто закрашивать пробелы, этими фильтрами.
В общем в интеренете предлагают 2 варианта решения этой задачи, какой быстрее пока не знаю сейчас буду проверять.
1:

#define PIX_SORT(a,b) { if ((a)>(b)) PIX_SWAP((a),(b)); }
#define PIX_SWAP(a,b) { elem_type temp=(a);(a)=(b);(b)=temp; }

elem_type opt_med9(elem_type * p)
{
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ;
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}
#undef PIX_SORT
#undef PIX_SWAP

2:

//Sort 1
for i := 1 to n - 1 do begin
    min := i;
    for j := i + 1 to n do
        if a[min] > a[j] then
            min := j;
    if min<>i then begin
        t := a[i];
        a[i] := a[min];
        a[min] := t;
    end;
end;
//Sort 2
const N = 255;
type TArray = array [1..N] of integer; 
procedure InsertSort(var x: TArray);
var
  i, j, buf: integer;
begin
  for i := 2 to N do
  begin
    buf := x[i];
    j := i - 1;
    while (j >= 1) and (x[j] > buf) do
    begin
      x[j + 1] := x[j];
      j := j - 1;
    end;
    x[j + 1] := buf;
  end;
end;
//Median
    SomeSort(arrtemp, count);
    median: = arrtemp[count div 2];

[ResourceSpace]

Какие формулы? Это же просто фильтр. Вам надо-то что? Повторить эти фильтры из XnView?

[IvaniuS]

Да просто повторить фильтры эти для изображения 24бит.
Очень хорошие фильтры, но интренете не нашел их к сожалению или подобных.

[Pavia]

BDA

Сообщение от BDA

Pavia, в оригинале (в XnView) фильтры называются Median Cross, Median Box, что тоже не очень помогает понять точный способ их действия.

Это совсем меняет алгоритм. Median - это средний элемент после сортировке. И в русской литературе обозначается как медиана.
А вот среднее обычно имеется в виду усреднённое.

IvaniuS
Есть несколько вариантов реализации. Фильтров медианы.
Как известно сортировка пузырьком имеет сложность O(N^2), есть другие методы сортировки у них сложность O(N*Log(N)).
Суть в том что если умножить на число пикселей, то алгоритм становиться очень медленным. Поэтому сортировку ограничивают 3-элементами!

Сортировку над 3 элементами можно сделать за 3 сравнения. Каждое сравнение это примерно 14 тактов.

if A<B then
  begin
    if B<C then M:=B
      else 
      if A<C then M:=C
        else M:=A;
  end else
  begin
    if A<C then M:=A
      else 
      if B<C then M:=C
         else M:=B;
  end;

Далее для 2-х мерного случая делают в 2 прохода. Вначале по вертикали по все картинке. Затем по горизонтали по все картинке. Это конечно не честная медиана. Зато код работает очень быстро. А по качеству не сильно уступает оригиналу. А если результат одинаковый так зачем переплачивать? Зачем трудиться над универсальным методом если он не пригодится? Ответ - незачем.

Что касается Cross - то это скорее всего идет речь о пересечении диагоналей.
Элементы берутся на диагоналях.

-----------------
Что касается честной медианы. И честной сортировки. Сортировку для 9 элементов 3х3 можно проделать честно, к примеру сортировка пузырьком. Что работает быстро. 9*(9-1)/2*20= 800 тактов на один пиксель картинке. Картинка будет обрабатываться менее 1 секунды.
Можно составить вспомогательную программу которая сделает сортировку за минимальное число сравнений.
Поиск медианы - алгоритм линейный O(N). Но есть одно но алгоритм выгоден для числа элементов более 100. Поэтому для фильтрации не годиться. Но для 9 тоже возможно быстрый алгоритм, давным давно видел статью с объяснениями.
Частный случай проще оптимизировать. Поэтому для 9 элементов легче подобрать, чем для произвольного.