Looking for an efficient mode filter in GLSL

Question

I would like to implement an image filter called a Mode Filter in GLSL for use in a WebGL application. A mode filter computes the mode (most frequent) value from the surrounding pixels and if there is a single value that is most frequent, sets the pixel colour to the mode, otherwise leaves it unchanged. The surrounding pixels is determined by the kernel size, typically being 9 or 25 pixels centred on the pixel in question.

I am a real beginner with shaders, GLSL and the intricacies of achieving performance and my current implementation seems to be particularly bad. I'm looking for some help finding a more efficient approach.

I put my current shader into shader toy at https://www.shadertoy.com/view/wsVSWw, I get under 10 fps! Note you need to select something for iChannel0 to see the effect.

Edit

I converted a counting sort algorithm to GLSL and grabbed a loop from a median filter, result is 30fps now, new version at https://www.shadertoy.com/view/tsVSDm

In my particular case, I'm working with a grayscale photo so I've only bothered with the red channel.

Here is shader as implemented for webgl, it has minor differences from the shadertoy version (for instance texture2D() instead of texture()):

    precision mediump float;
    varying vec2 v_coord;
    uniform sampler2D u_texture;
    uniform vec2 imageResolution;

    int histogram[256];

    void main() {

        vec2 pos = vec2(v_coord.x, 1.0 - v_coord.y);
        vec4 outColor = texture2D(u_texture, pos);

        gl_FragColor = outColor;

        /* the mode filter does not apply to semi-transparent pixels
           for performance reasons, we would need to mix pixels based
           on alpha to get the effective color for the mode calculation
           then remix to get the correct color with the current pixel's
           alpha.  This is both hairy and would add processing time
        */
        if (outColor.a < 1.0) {
            return;            
        }

        vec2 onePixel = vec2(1) / imageResolution;

        for (int i = 0; i<256; i++) {
            histogram[i] = 0;
        }

        int maxValue = 0;
        int offset = int(float(${kernelSize})/2.0);
        for (int yy = 0; yy < ${kernelSize}; yy ++) {
            for (int xx = 0; xx < ${kernelSize}; xx ++) {
                vec2 samplePos = pos + vec2(yy - offset, xx - offset) * onePixel;
                vec4 color = texture2D(u_texture, samplePos);
                if (color.a == 1.0) {
                    int red = int(color.r * 255.0);
                    for (int i = 0; i<256; i++) {
                        if (i == red) {
                            histogram[i]++;
                            maxValue = int(max(float(maxValue), float(histogram[i])));
                        }
                    }
                }
            }
        }

        /* the number of values that have the maximum mode value */
        int numModes = 0;

        /* the colour (index) of the maximum node value */
        int modeValue = 0;

        for (int i = 0; i<256; i++) {
            if (histogram[i] == maxValue) {
                numModes++;
                modeValue = i;
            }
        }

        if (numModes == 1) {
            outColor.r = float(modeValue) / 255.0;
        }

        outColor.g = outColor.r;
        outColor.b = outColor.r;

        gl_FragColor = outColor;
    }

prideout prideout · Accepted Answer · 2019-11-21T21:14:08

This is actually a really interesting problem.

The usual way to make these types of things faster is to use multiple passes. Instead of invoking a 3x3 kernel, you would first apply a 3x1 kernel then apply a 1x3 kernel to the result.

However a mode filter is not separable. I just now came up with a case where it would break down:

151
555
151

The middle pixel should become 5 but if you break it down into a h+v pass the result would be 1.

Having said that, I still think a multi-pass solution would help, if you can come up with one. For example, you could write the mode value into the RED channel and its count into the GREEN channel. This would let you combine multiple small-kernel passes to effectively achieve a large kernel size, although I think it would suffer from occasional errors, similar to my above example. To fight the errors maybe you could write the "second-most" mode value/count into BLUE and ALPHA.

Looking for an efficient mode filter in GLSL

1 Answers