Median Sketch (GPU)

[Rick Brewster]

This is a GPU effect plugin I've been tinkering with for the last year or so. It's based on the P² Quantile Estimator algorithm as described in these 4 blogs posts: Part 1  Part 2  Part 3  Part 4

 

This effect will show up in Effects -> Artistic -> Median Sketch. I'm planning to include this in Paint.NET v5.1 once it is released, but for now you can enjoy it as a plugin!

 

Download: MedianSketch.zip 

 

Source Code is also available.

 

My initial goal was to port Effects -> Noise -> Median to the GPU, as @BoltBait wanted it for use in the effects he was porting to PDN 5.0 and the new GPU effects system. However, this fell apart quickly because shaders cannot allocate the block of memory needed to grab an arbitrary number of samples, sort them, and then pick the middle (median) value. (Not only is it not possible, it would need an ungodly amount of memory since every pixel executes in parallel to the other pixels.)

 

Instead I needed a median approximation algorithm, one that uses a small fixed amount of memory, operating on a "stream" of values where you don't/can't know or store all of the samples at once. I eventually found it in the blog posts linked to above. After a lot of experimentation, I was finally able to get it to work and to produce results that were almost identical to the regular median effect. However, it also required an INSANE amount of time to execute: compared to the CPU-based Median effect, this GPU-based approximation could easily take 100x longer to execute ... on a GeForce 4090!

 

Things became much more manageable once I dialed down the number of samples and the rendering passes ("iterations"). It also produced a more artistic effect akin to some kind of coarse-grained brush stroke painting.

 

You can think of this algorithm as taking a Monte Carlo approach to calculating a median. Instead of using all the pixels in the given radius, only a random subset of those pixels are used. Visually it reminds me a lot of how some newer games, like Cyperpunk 2077 and Alan Wake 2, do some of their path-traced rendering, especially for reflections (esp. Alan Wake 2's intentionally distorted mirrors). Instead of rendering all pixels at full fidelity, which is prohibitive for performance reasons, only some of the pixels are rendered and then the rest are guessed/interpolated/extrapolated.

 

A high-end GPU is not required, but you will appreciate this effect more -- especially at the highest values for Radius and Iterations -- if you have a modern discrete GPU such as a GeForce 1060, AMD Radeon RX 580, or newer.

 

Here's an example using a stock photo by Ali Pazani:

Here's another example using a picture of a Ferrari. First screenshot is the original, then using Median Sketch at default settings, and then with the Percentile set to maximum:

 

 

Another example of how this can create a brush stroke-y art effect:

 

 

[user.by]

I like much, also you can blury background in same time.