Автор Тема: Blur на разных ЯП.  (Прочитано 48730 раз)

DddIzer

  • Гость
Re: Blur на разных ЯП.
« Ответ #60 : Апрель 26, 2013, 01:54:40 pm »
Евгений.
  :( Извините.. буду знать.

DddIzer

  • Гость
Re: Blur на разных ЯП.
« Ответ #61 : Апрель 26, 2013, 02:02:30 pm »
Непонятно, как такой соус может проканать -- ведь решения на других языках тут предлагались вовсе не в условиях хакатоновского стресса.

Вот это и обидно.. если Блероманию.. можно списать  хакатоновый стресс.. и  идею фикс... , то х..ню от кучи здоровых  мужиков у которых есть время разобраться.. - нет.. но это имхо..Впрочем, хотя уровень  средний харбровских статей около плинтуса.. лично мне не охота вносить свой СОЗНАТЕЛЬНЫЙ вклад в увеличении энтропии.. Кроме того есть небольшая вероятность что можно напороться на специалиста.. - который скажет - "ну и уроды..."

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #62 : Апрель 26, 2013, 02:09:57 pm »
Непонятно, как такой соус может проканать -- ведь решения на других языках тут предлагались вовсе не в условиях хакатоновского стресса.

Вот это и обидно.. если Блероманию.. можно списать  хакатоновый стресс.. и  идею фикс... , то х..ню от кучи здоровых  мужиков у которых есть время разобраться.. - нет.. но это имхо..Впрочем, хотя уровень  средний харбровских статей около плинтуса.. лично мне не охота вносить свой СОЗНАТЕЛЬНЫЙ вклад в увеличении энтропии.. Кроме того есть небольшая вероятность что можно напороться на специалиста.. - который скажет - "ну и уроды..."

Еще раз - мы эмулируем разработку и реализацию алгоритма в условиях хакатона. В этой теме (вот конкретно в этой) не ведется дискуссия о качестве самого алгоритма. Мы тут лишь смотрим как разные ЯП себя ведут на наивнейшем и кривейшем алгоритме размытия. Всё.

Если говорить о алгоритме, то в общем то Надя еще в начале недели нашла алгоритм (но не реализацию) который реализует размытие любой силы за O(W*H) (то есть от силы размытия не зависит, зависит только от размеров картинки). И я теперь себя чувствую дебилом, ибо я же ЗНАЮ эти методики, и там в общем то ничего нового для меня по сути нет. По идее, мог бы и прямо на хакатоне додуматься до такого. Так что свое ускорение в 10 раз мы скорее всего уже получили :-)
Y = λf.(λx.f (x x)) (λx.f (x x))

DddIzer

  • Гость
Re: Blur на разных ЯП.
« Ответ #63 : Апрель 26, 2013, 02:44:45 pm »
Еще раз - мы эмулируем разработку и реализацию алгоритма в условиях хакатона.
Делайте что хотите... только уж определитесь.. бенчмарки вы собираетеь отсылать или что еще.. и непонятно.. нафиг условиях хакотона моделировать бенчмарки... ;) - короче,
 я не ПРОТИВ , я за то что бы усе было достойно и непротиворечиво...

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Blur на разных ЯП.
« Ответ #64 : Апрель 26, 2013, 03:01:36 pm »
вопрос с какого перепоя Блером называется свертка с ядром ({0,1,0},{1,0,1},{0,1,0})/4 а не  ({1,1,1},{1,0,1},{1,1,1})/8... с какого будуна апликация сверток (повторение свертки N раз) ведет напрямую к увеличению ее радиуса  (по факту ширине окна усреднения).

Почему я беру именно ({0,1,0},{1,0,1},{0,1,0})/4 объясняется очень просто.

Изображение можно "разгладить" до
0) среднего значения;
1) линейного градиента;
2) полинома второй степени по x и y;
3) третей степени;
и т. д.

Случай (0) не очень интересен. Минимальное нетривиальное "разглаживание" есть разглаживание до линейного градиента, то есть зануление вторых и более высоких производных. Двумерный разностный лапласиан:

Lf[y, x] = f[y-1, x] + f[y+1, x] + f[y, x-1] + f[y, x+1] - 4*f[y, x];

Зануляем Lf[y, x] = 0, получаем итерационную схему

f -> h:

h[y, x] = (f[y-1, x] + f[y+1, x] + f[y, x-1] + f[y, x+1]) / 4;

Если эту схему гонять много раз, то картинка будет превращаться в линейный градиент.

Можно взять квадрат оператора лапласа:

LLf[y, x] = f[-2 + y, x] + 2 f[-1 + y, -1 + x] - 8 f[-1 + y, x] + 2 f[-1 + y, 1 + x] + f[y, -2 + x] - 8 f[y, -1 + x] + 20 f[y, x] - 8 f[y, 1 + x] + f[y, 2 + x] + 2 f[1 + y, -1 + x] - 8 f[1 + y, x] + 2 f[1 + y, 1 + x] + f[2 + y, x];

занулив его

LLf[y, x] = 0

получить другую итерационную схему:

h[y, x] = (-f[-2 + y, x] - 2 f[-1 + y, -1 + x] + 8 f[-1 + y, x] - 2 f[-1 + y, 1 + x] - f[y, -2 + x] + 8 f[y, -1 + x] + 8 f[y, 1 + x] - f[y, 2 + x] - 2 f[1 + y, -1 + x] + 8 f[1 + y, x] - 2 f[1 + y, 1 + x] - f[2 + y, x]) / 20;

Если эту схему гонять много раз, то картинка будет превращаться в "кубический градиент".

Как-то так...

DddIzer

  • Гость
Re: Blur на разных ЯП.
« Ответ #65 : Апрель 26, 2013, 03:07:41 pm »

Почему я беру именно ({0,1,0},{1,0,1},{0,1,0})/4 объясняется очень просто.

Если эту схему гонять много раз, то картинка будет превращаться в "кубический градиент".

Как-то так...
  почему не вариант Б - с 8 единицами как более аккуратное прилближение... кстати , если посмотрите на ссылку.. то там на картинке видно, что при N=6 (для нормального ядра УЖЕ получается практически гауссово размытие.. т.е. больше 6 раз прогонять свертку на ядре 3x3 - смысла нет)

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #66 : Апрель 26, 2013, 03:34:51 pm »
это если на передний план смотреть...

DddIzer

  • Гость
Re: Blur на разных ЯП.
« Ответ #67 : Апрель 26, 2013, 03:41:59 pm »
это если на передний план смотреть...
а зачем нам туда смотреть.. мы должны смотреть(искажать) назад(задний план)... то что попало в фокус камеры (передний план) должно передаваться без искажений (или с минимальными)...

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #68 : Апрель 26, 2013, 04:18:00 pm »
Вот моя версия КП/ББ. На моём компе на N=13 работает две минуты.
MODULE WorkBlur;
IMPORT Log, Kernel, SYSTEM;

CONST W = 640; H = 480; (* размер кадра в пикселях *)
w = (W - 1) * 3; h = H -1; (* размер области кадра на обработке *)
F = 1000; (* кол-во кадров *)

PROCEDURE Do*(N : INTEGER);
VAR a1, a2 : POINTER TO ARRAY OF BYTE;
len : INTEGER;
f, n, x, y : INTEGER;
m, t, l, r, b : INTEGER;
time : LONGINT;
BEGIN
time := Kernel.Time();
len := W * H * 3;
NEW( a1, len );
NEW( a2, len );
f := 0;
WHILE f < F DO

n := 0;
WHILE n < N DO                                   (* x, y *)
t := 3;                                            (* 1, 0 *)
l := w - 3; m := l + 3; r := l + 6; (* 0, 1 ; 1, 1 ; 2, 1 *)
b := r + w;                                      (* 1, 2 *)

y := 1;
WHILE y < h DO
x := 3;
WHILE x < w DO
a2[m] := SHORT(SHORT(SYSTEM.LSH((a1[t] + a1[b] + a1[l] + a1[r]), -2)));
t := t + 1; l := l + 1; m := m + 1; r := r + 1; b := b + 1;
x := x + 1
(*INC(t); INC(l); INC(m); INC(r); INC(b);
INC(x)*)
END;
t := t + 6; l := l + 6; m := m + 6; r := r + 6; b := b + 6;
y := y + 1
(*INC(y)*)
END;

(*<-->*)

t := 3;
l := w - 3; m := l + 3; r := l + 6;
b := r + w;

y := 1;
WHILE y < h DO
x := 3;
WHILE x < w DO
a1[m] := SHORT(SHORT(SYSTEM.LSH((a2[t] + a2[b] + a2[l] + a2[r]), -2)));
t := t + 1; l := l + 1; m := m + 1; r := r + 1; b := b + 1;
x := x + 1
END;
t := t + 6; l := l + 6; m := m + 6; r := r + 6; b := b + 6;
y := y + 1
END;

n := n + 1
END;
f := f + 1
END;
Log.Int(SHORT(Kernel.Time() - time))
END Do;

END WorkBlur.
« Последнее редактирование: Апрель 26, 2013, 04:20:14 pm от Valery Solovey »

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #69 : Апрель 26, 2013, 06:28:39 pm »
Пока писал версию для двумерного массива, понял, что неправильно соптимизировал версию для одномерного.
Второй заход:
для N=13
одномерный массив - больше 1.5 минуты
двумерный - больше 3 минут

MODULE WorkBlur;
IMPORT Log, Kernel, SYSTEM;

CONST W = 640; H = 480; (* размер кадра в пикселях *)
ln = 1;
clr = 3;
w = (W - 1) * clr; h = H -1; (* размер области кадра на обработке *)
w2 = W * clr;
shift = -2;
F = 1000; (* кол-во кадров *)

PROCEDURE Do*(N : INTEGER);
VAR a1, a2 : POINTER TO ARRAY OF BYTE;
len : INTEGER;
f, n, x, y : INTEGER;
m : INTEGER;
time : LONGINT;
BEGIN
time := Kernel.Time();
len := W * H * clr;
NEW( a1, len );
NEW( a2, len );
f := 0;
WHILE f < F DO

n := 0;
WHILE n < N DO
m := w + 6;

y := 1;
WHILE y < h DO
x := 3;
WHILE x < w DO
a2[m] := SHORT(SHORT(SYSTEM.LSH(a1[m - w2] + a1[m - clr] + a1[m + clr] + a1[m + w2], shift)));
m := m + 1;
x := x + 1
END;
m := m + 6;
y := y + 1
END;

(*<-->*)

m := w + 6;

y := 1;
WHILE y < h DO
x := 3;
WHILE x < w DO
a1[m] := SHORT(SHORT(SYSTEM.LSH(a2[m - w2] + a2[m - clr] + a2[m + clr] + a2[m + w2], shift)));
m := m + 1;
x := x + 1
END;
m := m + 6;
y := y + 1
END;

n := n + 1
END;
f := f + 1
END;
Log.Int(SHORT(Kernel.Time() - time))
END Do;

PROCEDURE Do2*(N : INTEGER);
VAR  a1, a2 : POINTER TO ARRAY OF ARRAY OF BYTE;
len : INTEGER;
f, n, x, y : INTEGER;
time : LONGINT;
BEGIN
time := Kernel.Time();
NEW( a1, H, W * 3 );
NEW( a2, H, W * 3 );
f := 0;

WHILE f < F DO

n := 0;
WHILE n < N DO
y := 1;
WHILE y < h DO
x := 3;
WHILE x < w DO
a2[y, x] := SHORT(SHORT(SYSTEM.LSH(a1[y - ln, x] + a1[y, x - clr] + a1[y, x + clr] + a1[y + ln, x], shift)));
x := x + 1
END;
y := y + 1
END;

y := 1;
WHILE y < h DO
x := 3;
WHILE x < w DO
a1[y, x] := SHORT(SHORT(SYSTEM.LSH(a2[y - ln, x] + a2[y, x - clr] + a2[y, x + clr] + a2[y + ln, x], shift)));
x := x + 1
END;
y := y + 1
END;

n := n + 1
END;
f := f + 1
END;
Log.Int(SHORT(Kernel.Time() - time))
END Do2;

END WorkBlur.

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #70 : Апрель 26, 2013, 06:37:42 pm »
Пока писал версию для двумерного массива, понял, что неправильно соптимизировал версию для одномерного.
Второй заход:
для N=13
одномерный массив - больше 1.5 минуты
двумерный - больше 3 минут

Круто! А какие характеристики ноута?
Y = λf.(λx.f (x x)) (λx.f (x x))

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #71 : Апрель 26, 2013, 06:42:20 pm »
я это на большом компе запускал.

Проц. i3 3220. Остальное значение не имеет, мне кажется.

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #72 : Апрель 26, 2013, 06:48:25 pm »
я это на большом компе запускал.

Проц. i3 3220. Остальное значение не имеет, мне кажется.
Всё равно круто :-) (вообще говоря, тут еще шустрость памяти играет роль)

Доберусь до того ультрабука - затестю.

PS. И надо будет таки научиться работать с картинками в ББ (прочитать с диска, отобразить, записать на диск)
Y = λf.(λx.f (x x)) (λx.f (x x))

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #73 : Апрель 26, 2013, 07:09:38 pm »
Про память я уже подзабыл.
Помню, что Кингстон, тайминги 11.
Частота, возможно 1600


Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #74 : Апрель 26, 2013, 08:22:19 pm »
нетбук асус 1215b.
Проц. AMD® APU E450 1.65GHz (dual core)
Память DDR3, одноканальная.

Провёл несколько тестов на одномерных массивах. Постепенно "отпускал" комп. от режима энергопотребления к максимальной производительности.
 658 - 783 - 385 - 385 (секунды)