Surface Blur and Median

[josho]

The article buried the lead, so here's your TLDR summary:

- GIMP & Photoshop use the same O(n²) algorithm

- GIMP's implementation is single threaded, while photoshop's is multithreaded and therefore performs much faster on modern multi-core CPUs

- Photopea uses a different algorithm with O(n) characteristics

- O(n) in a single threaded javascript is faster than O(n²) in parallel C/C++ for large values of n

- For photo editing, we used to work with relatively small photos, so algorithm choice didn't matter so much. But with modern digital cameras algorithm choice matters as we are seeing photo filters now working with larger values of n (pixel radius in this case).

Therefore, choosing the right algorithm matters.

[IvanK_net]

Not exactly. I wanted to avoid too much scientific notation.

- GIMP uses Θ(n * r²) algorithm

- Photoshop uses Θ(n * r) algorithm

- r<=10: Photopea uses Θ(n * r) algorithm

- r> 10: Photopea uses Θ(n) algorithm with a large linear coefficient

For r<=10 Photopea and Photoshop use the same algorithm. PP is slower not only because of Javascript, but also because of multithreading in PS.

[soamv]

Ok, but is it actually computing the same thing? Are the blurred images from photopea and photoshop identical? The article mentions always doing no more than N*10 steps -- is this an approximation algorithm?

[IvanK_net]

Photopea and Gimp do compute the same thing (Surface Blur by definition). However, in Photoshop, the results at the radius >= 50px are slightly different. I have a suspicion, that Photoshop uses an approximation algorithm.

N*10 algorithm has an overhead, it needs a little more time (and memory) per pixel, but it does not depend on the radius. It is an exact algorithm (no approximation).

[initram]

I can't speak to the actual algorithm, but Photoshop also does various types of color space conversions unless you explicitly set it not to. I didn't see anywhere in the article where that was mentioned, or whether Photopea does those same conversions.

[GrantS]

Since it's not mentioned in the article, this is also called bilateral filtering [1]. The external links section of the Wikipedia article lists some famous SIGGRAPH papers describing fast implementations, and there is some code available [2].

[1] https://en.wikipedia.org/wiki/Bilateral_filter

[2] http://people.csail.mit.edu/sparis/bf/

[jacobolus]

Note that Sylvain Paris now works for Adobe’s Advanced Technology Lab.

As far as I can tell the reason that Adobe can’t replace their current Photoshop bilateral filter implementation (which is now 15 years old or something) with a better one is that the precise pixel-level details would be slightly different, potentially affecting someone’s existing workflow.

This stuff should really be done using one of the fast GPU algorithms.

[droithomme]

Cool stuff, congrats.

I really like your idea of having a "willitwork" page that dynamically lists the specific deficiencies in the user's browser. So many web applications just silently fail. This is way better. Every web application should have a willitwork page.

[greydius]

It sounds like a good idea, but every time I've seen this implemented it's been as a simple whitelist lookup against user agent. This has two problems. First, user agent is... unreliable. Second, people that use less common systems are erroneously told the page won't work. (I've lost count of the number of times a website has told me that my operating system isn't supported yet the page works fine. What does my os have to do with a web page anyway?)

[MOARDONGZPLZ]

Is there a typical number of radius pixels people use? I'm not a photographer, so I can't really say.

Below 10px, your tool is the worst, from 10-30px, GIMP is awful, Photoshop is the best. Above 30px, your tool is the best. However, Photoshop doesn't seem to fall too far behind in actual seconds even as you approach 100px.

So do photo editing people typically use a smaller radius or larger radius, or does it just depend?

[IvanK_net]

Below 10px radius, all programs take under 0.5 seconds, so you don't even notice the difference.

The picture in an example was made with a radius about 12px. But Photoshop and GIMP allow larger radii, so I think large radii are used sometimes, too.

BTW. it really surprised me, that Adobe Photoshop uses such a simple algorithm, while faster (and slightly more complex) algorithms exist for quite a long time.

[makapuf]

I guess it depends on the resolution. To remove a given scratch of a given absolute size in cm, if your photo has twice the resolution you will need twice the pixels so twice the pixel size.

[bcrescimanno]

I don't do photo work; but, I went and played with the tool and, at least for the photo provided, anything above 10px really started taking the photo into the "Uncanny Valley" territory.

[kuya_noel]

here's a cool median filtering algorithm (extensible to bilateral filtering/surface blur) which exhibits O(log r) performance: http://www.shellandslate.com/download/fastmedian_5506.pdf http://www.shellandslate.com/download/medianslides.pdf

also related are adobe's local laplacian filters: http://people.csail.mit.edu/hasinoff/pubs/ParisEtAl11-lapfil...

at recent SIGGRAPHs, they showed off the halide DSL which can optimize filtering/schedule of image processing kernels for CPUs/GPUs.

also pretty cool related algorithms are domain transform edge aware filters: http://www.inf.ufrgs.br/~eslgastal/DomainTransform/ if you use open cv, they're in 3.0 called DTFilter

[markbnj]

Am I the only one surprised by the gap between GIMP and Photoshop in calculating the surface blur example?

[IvanK_net]

I was very surprised, that GIMP uses a naive algorithm for computing the surface blur. It is like Selection Sort for sorting.

I have seen much faster Surface Blur for GIMP available as a plugin. I am wondering, why it wasn't added as the default method.

[criley2]

Not really. Photoshop is an expensive closed source application designed for professional use. GIMP is open source and the cross-over between professional users and open source GIMP coders is likely next to nil. Meaning that any significant production performance issues are pretty invisible to GIMP.

In my experience with the art/design mac/photoshop crowd, something like GIMP only earns blank stares.

[andybak]

Mods: in this case - aterrible decision to change the post title. Please allow us to salvage articles with titles that provide no context.

[billconan]

very cool!