Oberon space
General Category => Общий раздел => Тема начата: valexey_u от Апрель 25, 2013, 12:55:19 pm
-
Коль уж завелось обсуждения этих алгоритмов, и чтобы не путать тему о самих алгоритмах и тему бенчмарка разных ЯП (и их реализаций) на одном и том же алгоритме (что обсуждается вот в этой теме: Blur на разных ЯП (http://oberspace.dyndns.org/index.php/topic,484.0.html)), завожу новую тему.
Напомню задачу - нужно получить быстрый алгоритм сильно размывающий картинку.
Тема берет свое начало тут: http://oberspace.dyndns.org/index.php/topic,480.msg15695.html#msg15695
Вот два готовых к употреблению алгоритма. Один наш, который мы, с Надей реализовали на хакатоне (на С++), и другой Сергея Губанова, который реализовал на C#:
Наш:
#include <iostream>
#include <ctime>
const int width = 640;
const int height = 480;
const size_t blurRange = 13;
enum Color {
RED = 0,
GREEN,
BLUE
};
int index(int x, int y, Color color) {
return width*y*3+x*3+color;
}
template <size_t N>
struct ring_buffer {
float buf[N];
size_t head;
size_t size;
ring_buffer():head(0), size(0) {memset(buf, 0, sizeof(buf));}
void push_back(float v) {
if (++head >= N) {head=0;}
if (size<N) size++;
buf[head]=v;
}
float back() {return buf[head];}
float front() {return buf[head!=N-1?head+1:0];}
};
int main()
{
volatile unsigned char* volatile in = new unsigned char[width*height*3];
volatile unsigned char* volatile out = new unsigned char[width*height*3];
time_t begin;
time(&begin);
const int frames = 1000;
for (int nn=0; nn<frames; nn++) {
for (int y=blurRange; y<height-blurRange; y++) {
float red = 0;
float green = 0;
float blue = 0;
ring_buffer<blurRange*2> redRows ;
ring_buffer<blurRange*2> blueRows;
ring_buffer<blurRange*2> greenRows;
for (int x=blurRange; x<width-blurRange; x++) {
float vr = 0;
float vg = 0;
float vb = 0;
for (int y1 = y-blurRange; y1<y+blurRange; y1++) {
vr += in[index(x,y1,RED) ];
vg += in[index(x,y1,GREEN)];
vb += in[index(x,y1,BLUE) ];
}
vr = vr/(blurRange*blurRange*4.0);
vg = vg/(blurRange*blurRange*4.0);
vb = vb/(blurRange*blurRange*4.0);
auto front_r = redRows.front();
red += vr - redRows.front();
green += vg - greenRows.front();
blue += vb - blueRows.front();
redRows.push_back(vr);
blueRows.push_back(vb);
greenRows.push_back(vg);
out[index(x,y,RED) ] = red*(blurRange*2.0/redRows.size);
out[index(x,y,GREEN)] = green*(blurRange*2.0/greenRows.size);
out[index(x,y,BLUE) ] = blue*(blurRange*2.0/blueRows.size);
}
}
}
time_t end;
time(&end);
auto seconds = difftime(end, begin);
std::cout << float(frames)/seconds << " " << seconds << std::endl;
return 0;
}
Сергея:
// Note! Need add reference to: WindowsBase, PresentationCore, System.Xaml
namespace Blur
{
class Program
{
private const int W = 640;
private const int H = 480;
private static System.Windows.Media.PixelFormat pixelFormat = System.Windows.Media.PixelFormats.Bgr24;
static void Main (string[] args)
{
byte[] a;
if (Load("input.jpg", out a))
{
const int N = 7;
byte[] b = new byte[a.Length];
System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
timer.Start();
BlurX2(a, b, N);
timer.Stop();
double dt = timer.Elapsed.TotalSeconds;
System.Console.WriteLine("N={0}, R={1}, time = {2} seconds, FPS = {3}", N, 2*N, dt, 1.0/dt);
Save("output-R" + (2*N) + ".jpg", a);
System.Console.WriteLine("Ok");
System.Console.ReadLine();
}
}
public static unsafe void BlurX2 (byte[] A, byte[] B, int N)
{
const int dy = 3*W;
const int dx = 3;
fixed (byte* a = &A[0])
{
fixed (byte* b = &B[0])
{
for (int n = 0; n < N; n++)
{
for (int y = dy; y < dy*(H-1); y+=dy)
{
for (int x = dx; x < dx*(W-1); x+=dx)
{
int offset = y + x;
b[offset+0] = (byte)((a[offset-dy+0] + a[offset+dy+0] + a[offset-dx+0] + a[offset+dx+0]) / 4);
b[offset+1] = (byte)((a[offset-dy+1] + a[offset+dy+1] + a[offset-dx+1] + a[offset+dx+1]) / 4);
b[offset+2] = (byte)((a[offset-dy+2] + a[offset+dy+2] + a[offset-dx+2] + a[offset+dx+2]) / 4);
}
}
for (int y = dy; y < dy*(H-1); y+=dy)
{
for (int x = dx; x < dx*(W-1); x+=dx)
{
int offset = y + x;
a[offset+0] = (byte)((b[offset-dy+0] + b[offset+dy+0] + b[offset-dx+0] + b[offset+dx+0]) / 4);
a[offset+1] = (byte)((b[offset-dy+1] + b[offset+dy+1] + b[offset-dx+1] + b[offset+dx+1]) / 4);
a[offset+2] = (byte)((b[offset-dy+2] + b[offset+dy+2] + b[offset-dx+2] + b[offset+dx+2]) / 4);
}
}
}
}
}
}
public static bool Load (string fileName, out byte[] buffer)
{
buffer = null;
using (System.IO.FileStream s = new System.IO.FileStream(fileName, System.IO.FileMode.Open, System.IO.FileAccess.Read, System.IO.FileShare.Read))
{
System.Windows.Media.Imaging.BitmapDecoder d = System.Windows.Media.Imaging.BitmapDecoder.Create(s,
System.Windows.Media.Imaging.BitmapCreateOptions.PreservePixelFormat,
System.Windows.Media.Imaging.BitmapCacheOption.Default);
System.Windows.Media.Imaging.BitmapFrame f = d.Frames[0];
if (f.PixelWidth != W)
{
System.Console.WriteLine("Unexpected width={0}, expected={1}", f.PixelWidth, W);
}
else if (f.PixelHeight != H)
{
System.Console.WriteLine("Unexpected height={0}, expected={1}", f.PixelHeight, H);
}
else if (f.Format != pixelFormat)
{
System.Console.WriteLine("Unexpected pixel format={0}, expected={1}", f.Format, pixelFormat);
}
else
{
buffer = new byte[W * H * 3];
f.CopyPixels(buffer, W * 3, 0);
}
}
return (buffer != null);
}
public static void Save (string fileName, byte[] buffer)
{
System.Windows.Media.Imaging.BitmapSource bm = System.Windows.Media.Imaging.BitmapSource.Create(
W, H, 300, 300, pixelFormat, null, buffer, W * 3);
using (System.IO.FileStream s = new System.IO.FileStream(fileName, System.IO.FileMode.Create))
{
System.Windows.Media.Imaging.JpegBitmapEncoder e = new System.Windows.Media.Imaging.JpegBitmapEncoder();
e.Frames.Add(System.Windows.Media.Imaging.BitmapFrame.Create(bm));
e.Save(s);
}
}
}
}
Пояснения к алгоритму Сергея (подробней тут (http://oberspace.dyndns.org/index.php/topic,484.msg15826.html#msg15826)):
Сделал цвета однобайтовыми, делаю блюр в трёх каналах, загружаю из картинки.
На i7 2600K уже с учётом трёх каналов:
N=5, R=10, time = 0.0140209 seconds, FPS = 71.3220977255383
N=6, R=12, time = 0.0166911 seconds, FPS = 59.912168760597
N=7, R=14, time = 0.0194411 seconds, FPS = 51.4374186645817
N=8, R=16, time = 0.0224343 seconds, FPS = 44.5746022831111
R - радиус размытия, N - количество фаз (за одну фазу делается два прохода, R = 2*N)
Иллюстрация работы этого алгоритма:
До обработки:
(http://cdn.imghack.se/images/260b05230b0d667920447393c9818ea2.jpg)
После обработки с N=6 (R=12):
(http://cdn.imghack.se/images/d2cdfad9b004c0464db73c1f9063005f.jpg)
Литература которую нужно таки как-то проработать http://web.archive.org/web/20060718054020/http://www.acm.uiuc.edu/siggraph/workshops/wjarosz_convolution_2001.pdf (сслыка предоставлена Dddizer'ом).:
Также я постараюсь сегодня-завтра прогнать эту картинку через наш алгоритм, чтобы стало ясно насколько похожие результаты получаются.
-
Может, стоит попробовать алгоритмы с использованием OpenCL и, в добавок, на APL-подобных языках?
-
Может, стоит попробовать алгоритмы с использованием OpenCL и, в добавок, на APL-подобных языках?
Попробуйте, нам это очень интересно будет )))
-
Может, стоит попробовать алгоритмы с использованием OpenCL и, в добавок, на APL-подобных языках?
Про APL ничего не скажу. А про OpenCL есть вопрос - когда одно приложение активно что-то на OpenCL считает, как это сказывается на других приложениях также активно использующих GPU/видюху? Просто наше приложение, VirtuaLens, как понимаешь, должно работать так, чтобы другому приложению оставалось достаточно ресурсов для полноценной работы. То есть мы обрабатываем изображение, а какой-нибудь skype это дело кодирует в h264 (возможно с помощью GPU), отправляет, декодирует, отображает и много чего еще делает.
Исходя из этих же соображений мы не имеем права раскидывать наши алгоритмы по нескольким ядрам.
-
Исходя из этих же соображений мы не имеем права раскидывать наши алгоритмы по нескольким ядрам.
А ежели придётся запускать эту прогу на нетбуке с одноядерным атомом? )))
Вообще тут надо использовать информацию о том, что поменялось в кадре, и неизменившиеся места просто брать из предыдущего размытого кадра, и размывать только изменившиеся области кадра -- это должно дать большой выигрыш на видеопотоках со статическим фоном...
-
Исходя из этих же соображений мы не имеем права раскидывать наши алгоритмы по нескольким ядрам.
А ежели придётся запускать эту прогу на нетбуке с одноядерным атомом? )))
А такие еще существуют? Из последнего что я видел, атомы были двуядерные уже.
Впрочем, это все не важно, PerC SDK требует i3..i7. Так что мы ориентируемся на ультрабуки.
Вообще тут надо использовать информацию о том, что поменялось в кадре, и неизменившиеся места просто брать из предыдущего размытого кадра, и размывать только изменившиеся области кадра -- это должно дать большой выигрыш на видеопотоках со статическим фоном...
Ты только что описал кусок h264 :-) И я не уверен что это даст выигрыш по производительности.
-
Запрограммировал алгоритм Алексея и Нади (так на сколько я его вообще понял, ну и творчески переосмыслил его).
Мой алгоритм - V1,
Алгоритм Алексея и Нади - V2
version=V1: N=4, R=8, time = 0.0110607 seconds, FPS = 90
version=V2: N=4, R=8, time = 0.0132383 seconds, FPS = 75
version=V1: N=6, R=12, time = 0.0163261 seconds, FPS = 61
version=V2: N=6, R=12, time = 0.0170063 seconds, FPS = 58
При одинаковых радиусах алгоритм V1 работает быстрее, однако алгоритм V2 заблюривает картинку ну очень сильно (поэтому большие радиусы ему не нужны).
Однако, я бы даже сказал, что алгоритм V2 не заблюривает, а портит картинку и ничего общего с расфокусировкой линзы не имеет. На выходе не расфокусировка линзы, а просто размазня какая-то.
// Note! Need add reference to: WindowsBase, PresentationCore, System.Xaml
namespace Blur
{
class Program
{
enum Version
{
V1,
V2
}
static Version version = Version.V1;
const int N = 6;
const int R = 2 * N;
private const int W = 640;
private const int H = 480;
private static System.Windows.Media.PixelFormat pixelFormat = System.Windows.Media.PixelFormats.Bgr24;
static void Main (string[] args)
{
byte[] a;
if (Load("input.jpg", out a))
{
byte[] tmp = new byte[a.Length];
System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
timer.Start();
if (version == Version.V1)
{
BlurV1(a, tmp);
}
else if (version == Version.V2)
{
BlurV2(a, tmp);
a = tmp;
}
timer.Stop();
double dt = timer.Elapsed.TotalSeconds;
System.Console.WriteLine("version={0}: N={1}, R={2}, time = {3} seconds, FPS = {4}", version, N, R, dt, (int)(1.0/dt));
Save("output-" + version + "-R" + R + ".jpg", a);
System.Console.ReadLine();
}
}
public static unsafe void BlurV1 (byte[] A, byte[] B)
{
const int dy = 3*W;
const int dx = 3;
fixed (byte* a = &A[0])
{
fixed (byte* b = &B[0])
{
for (int n = 0; n < N; n++)
{
for (int y = dy; y < dy*(H-1); y+=dy)
{
for (int x = dx; x < dx*(W-1); x+=dx)
{
int offset = y + x;
b[offset+0] = (byte)((a[offset-dy+0] + a[offset+dy+0] + a[offset-dx+0] + a[offset+dx+0]) >> 2);
b[offset+1] = (byte)((a[offset-dy+1] + a[offset+dy+1] + a[offset-dx+1] + a[offset+dx+1]) >> 2);
b[offset+2] = (byte)((a[offset-dy+2] + a[offset+dy+2] + a[offset-dx+2] + a[offset+dx+2]) >> 2);
}
}
for (int y = dy; y < dy*(H-1); y+=dy)
{
for (int x = dx; x < dx*(W-1); x+=dx)
{
int offset = y + x;
a[offset+0] = (byte)((b[offset-dy+0] + b[offset+dy+0] + b[offset-dx+0] + b[offset+dx+0]) >> 2);
a[offset+1] = (byte)((b[offset-dy+1] + b[offset+dy+1] + b[offset-dx+1] + b[offset+dx+1]) >> 2);
a[offset+2] = (byte)((b[offset-dy+2] + b[offset+dy+2] + b[offset-dx+2] + b[offset+dx+2]) >> 2);
}
}
}
}
}
}
public static unsafe void BlurV2 (byte[] input, byte[] output)
{
const int dy = 3 * W;
const int dx = 3;
int area = (2 * R + 1) * (2 * R + 1);
int c0;
int c1;
int c2;
int* sum0 = stackalloc int[H];
int* sum1 = stackalloc int[H];
int* sum2 = stackalloc int[H];
fixed (byte* a = &input[0])
{
fixed (byte* b = &output[0])
{
for (int X = dx*R; X < dx*(W-R); X+=dx)
{
for (int y = R; y < (H-R); y++)
{
int Y = dy*y;
c0 = 0;
c1 = 0;
c2 = 0;
int min = Y + X - dx*R;
int max = Y + X + dx*R;
for (int offset = min; offset <= max; offset += dx)
{
c0 += a[offset + 0];
c1 += a[offset + 1];
c2 += a[offset + 2];
}
sum0[y] = c0;
sum1[y] = c1;
sum2[y] = c2;
}
c0 = 0;
c1 = 0;
c2 = 0;
for (int yy = 0; yy <= 2*R; yy++)
{
c0 += sum0[yy];
c1 += sum1[yy];
c2 += sum2[yy];
}
for (int y = R; y < (H-R); y++)
{
int offset = X + dy*y;
c0 += (sum0[y + R] - sum0[y - R]);
c1 += (sum1[y + R] - sum1[y - R]);
c2 += (sum2[y + R] - sum2[y - R]);
b[offset + 0] = (byte)(c0 / area);
b[offset + 1] = (byte)(c1 / area);
b[offset + 2] = (byte)(c2 / area);
}
}
}
}
}
public static bool Load (string fileName, out byte[] buffer)
{
buffer = null;
using (System.IO.FileStream s = new System.IO.FileStream(fileName, System.IO.FileMode.Open, System.IO.FileAccess.Read, System.IO.FileShare.Read))
{
System.Windows.Media.Imaging.BitmapDecoder d = System.Windows.Media.Imaging.BitmapDecoder.Create(s,
System.Windows.Media.Imaging.BitmapCreateOptions.PreservePixelFormat,
System.Windows.Media.Imaging.BitmapCacheOption.Default);
System.Windows.Media.Imaging.BitmapFrame f = d.Frames[0];
if (f.PixelWidth != W)
{
System.Console.WriteLine("Unexpected width={0}, expected={1}", f.PixelWidth, W);
}
else if (f.PixelHeight != H)
{
System.Console.WriteLine("Unexpected height={0}, expected={1}", f.PixelHeight, H);
}
else if (f.Format != pixelFormat)
{
System.Console.WriteLine("Unexpected pixel format={0}, expected={1}", f.Format, pixelFormat);
}
else
{
buffer = new byte[W * H * 3];
f.CopyPixels(buffer, W * 3, 0);
}
}
return (buffer != null);
}
public static void Save (string fileName, byte[] buffer)
{
System.Windows.Media.Imaging.BitmapSource bm = System.Windows.Media.Imaging.BitmapSource.Create(
W, H, 300, 300, pixelFormat, null, buffer, W * 3);
using (System.IO.FileStream s = new System.IO.FileStream(fileName, System.IO.FileMode.Create))
{
System.Windows.Media.Imaging.JpegBitmapEncoder e = new System.Windows.Media.Imaging.JpegBitmapEncoder();
e.Frames.Add(System.Windows.Media.Imaging.BitmapFrame.Create(bm));
e.Save(s);
}
}
}
}
Прилагаю картинки для сравнения
-
Однако, я бы даже сказал, что алгоритм V2 не заблюривает, а портит картинку и ничего общего с расфокусировкой линзы не имеет. На выходе не расфокусировка линзы, а просто размазня какая-то.
так и должно быть при увеличении размера ядра свертки - в отличие от вашего варианта... который ведет к эффекту радиально симметрии ущербного неизменного ядра 3x3
-
Однако, я бы даже сказал, что алгоритм V2 не заблюривает, а портит картинку и ничего общего с расфокусировкой линзы не имеет. На выходе не расфокусировка линзы, а просто размазня какая-то.
Самое странное, что ты не прав. Оптика не дает гаусса, она дает именно что плоскую вершину у PSF (http://en.wikipedia.org/wiki/Point_spread_function) (в случае идеальной оптики). Единственное отступление от оптики в нашем с Надей фильтре - то, что у нас форма PSF не круглая, а квадратная (впрочем в реальной оптике она тоже далеко не всегда круглая).
Я же писал в своем отчете (http://valexey.blogspot.com/2013/04/hackday25-virtualens.html), откуда взялась идея самого проекта VirtuaLens - она взялась после того, как я поигрался с обратной сверткой и проработал серию статей. И, соответственно, после этой серии статей у меня было очень четкое понимание что такое расфокусировка на самом деле.
Собственно про PSF оптики, и про то как на самом деле выглядит расфокусировка можно прочесть (и посмотреть) тут: http://habrahabr.ru/post/147828/ (начиная со слов "Про боке").
Гаусс эмулирует на самом деле не расфокусировку, а равномерный смаз во все стороны в случае дрожания объектива, либо объекта съемки.
-
Гаусс эмулирует на самом деле не расфокусировку, а равномерный смаз во все стороны в случае дрожания объектива, либо объекта съемки.
Либо искажение ("дрожание", ога) среды в которой свет распространяется - например воздуха. Соответственно это будет заметно в случае больших расстояний от объектива до объекта съемки. Ну, например думаю в НН это должно быть хорошо видно при попытке съемки нижней части города из находясь при этом в парке Швейцария, у обрыва. Ну или от Кремля.
-
Вот наглядный пример настоящей расфокусировки:
(http://cdn.imghack.se/images/3c96a71df357b6d98b7b1a4425e5ae84.png) (http://cdn.imghack.se/images/3c96a71df357b6d98b7b1a4425e5ae84.png)
-
Ну, например думаю в НН это должно быть хорошо видно при попытке съемки нижней части города из находясь при этом в парке Швейцария, у обрыва. Ну или от Кремля.
Сабжи в студию
-
Ну, например думаю в НН это должно быть хорошо видно при попытке съемки нижней части города из находясь при этом в парке Швейцария, у обрыва. Ну или от Кремля.
Сабжи в студию
Кстати, еще лучше это должно быть видно (то есть виден гаусс) при попытке сфотографировать звезды.
-
Поэкспериментировал.
Взял то что было под рукой, сфотографировал ночью несколько ярких источников света в фокусе и без. Вот что получилось:
Исходник в фокусе:
(http://cdn.imghack.se/images/4d8cfdbc447646725a3bac26a205793f.jpg)
Реальная расфокусировка:
(http://cdn.imghack.se/images/f1eeb200332f7523b0af7a09a14ed7b0.jpg)
Результат обработки нашим алгоритмом (R=12):
(http://cdn.imghack.se/images/41f0445687b4e216cdfd2a70fc933061.jpg)
Результат обработки алгоритмом Сергея (R=12):
(http://cdn.imghack.se/images/c45f2775880c4182d21db16e28d90f67.jpg)
Ну и результат обработки алгоритмом Сергея при R=24:
(http://cdn.imghack.se/images/1c8334ac43222add19bf6ae1f379bd5b.jpg)
-
Ну, например думаю в НН это должно быть хорошо видно при попытке съемки нижней части города из находясь при этом в парке Швейцария, у обрыва. Ну или от Кремля.
Сабжи в студию
Есть оно у меня. Правда там подшарплено в фотошопе, но не везде, справа муть можно увидеть.
Ссылка на превью:
http://photokaravan.com/Member/Губанов%20Сергей%20Юрьевич/MyContestPhotos/eee73fae-0a9e-46d3-9f25-1d48d536cffd
там же можно посмотреть полную версия (около 10 Мб).
-
Ссылка на превью:
http://photokaravan.com/Member/Губанов%20Сергей%20Юрьевич/MyContestPhotos/eee73fae-0a9e-46d3-9f25-1d48d536cffd
403 - Forbidden: Access is denied.
You do not have permission to view this directory or page using the credentials that you supplied.
-
403 - Forbidden: Access is denied.
You do not have permission to view this directory or page using the credentials that you supplied.
А, ясно, вот так лучше наверное будет:
http://photokaravan.com/Contest/From-the-sky/eee73fae-0a9e-46d3-9f25-1d48d536cffd
Там же кстати много других фоток с сильно удалёнными объектами:
http://photokaravan.com/Contest/From-the-sky
-
Там же кстати много других фоток с сильно удалёнными объектами
Спасибо. Но мне больше интересно было посмотреть на сам город. А то вы начали между собой описывать места, и мне резко захотелось увидеть их самому. А ещё фоток, более летних, нет?
-
Там же кстати много других фоток с сильно удалёнными объектами
Спасибо. Но мне больше интересно было посмотреть на сам город. А то вы начали между собой описывать места, и мне резко захотелось увидеть их самому. А ещё фоток, более летних, нет?
Ну в принципе-то есть, дело только в не очень хорошем их качестве. А вообще в гугле есть много фоток по запросу: "фотографии нижнего новгорода".