Коль уж завелось обсуждения этих алгоритмов, и чтобы не путать тему о самих алгоритмах и тему бенчмарка разных ЯП (и их реализаций) на
одном и том же алгоритме (что обсуждается вот в этой теме:
Blur на разных ЯП), завожу новую тему.
Напомню задачу - нужно получить быстрый алгоритм сильно размывающий картинку.
Тема берет свое начало тут:
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);
}
}
}
}
Пояснения к алгоритму Сергея (подробней
тут):
Сделал цвета однобайтовыми, делаю блюр в трёх каналах, загружаю из картинки.
На 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)
Иллюстрация работы этого алгоритма:
До обработки:
После обработки с N=6 (R=12):
Литература которую нужно таки как-то проработать
http://web.archive.org/web/20060718054020/http://www.acm.uiuc.edu/siggraph/workshops/wjarosz_convolution_2001.pdf (сслыка предоставлена Dddizer'ом).:
Также я постараюсь сегодня-завтра прогнать эту картинку через наш алгоритм, чтобы стало ясно насколько похожие результаты получаются.