Optimizing the GIMP value invert plug-in

on 13 Jun 2006 by Mukund (@muks)

Value Invert is a GIMP plug-in which inverts the value channel in the HSV color space, of every pixel of a selected region in an image. In the GIMP 2.2 image menu, you can find it at Filters→Colors→Value Invert. In the development branch of GIMP (2.3) it has been moved to Colors→Value Invert.

There were many reasons why I was looking in the GIMP's plug-ins directory. A few moons ago, neo in #gimp had asked me to profile GIMP and optimize where necessary. I was also trying to revise MMX assembly programming and algorithms (being out of a job for the past 2 weeks), and hence wanted to find a place to do that. GIMP's color plug-ins are a good place to use MMX and I looked at Value Invert first.

The original implementation of Value Invert simply called an iteration function gimp_rgn_iterate2() which then called a callback function on every pixel with its RGB values. That callback then did a full RGB→HSV transform, then inverted the value (v = 255 - v), and did the HSV→RGB transform back to RGB color space. It was highly sub-optimal due to a function being called on a per-pixel basis, and also due to the use of full color space conversions when only the value channel needed to be modified. Graphics programs require to be fast, especially those used with large multi-megapixel images. The plug- in took 8 seconds to process an 8 mega-pixel photograph. So I set upon optimizing the plug-in.

First, the plug-in was changed to use gimp_pixel_rgns_process(). But it did not help much and any speed improvement was not apparent. The plug-in still took 8 seconds to process an 8 mega-pixel photograph. The reason for this was that while the new code did provide some minimal advantage, the time spent in the RGB→HSV→RGB transformations overshadowed it. The following was the original per-pixel code, where gimp_rgb_to_hsv_int() and gimp_hsv_to_rgb_int() are libgimpcolor functions which return results in their arguments:

    /* Data types are provided for reference */
    guchar *src;
    guchar *dest;
    int    v1, v2, v3;

    v1 = src[0];
    v2 = src[1];
    v3 = src[2];

    gimp_rgb_to_hsv_int (&v1, &v2, &v3);
    v3 = 255 - v3;
    gimp_hsv_to_rgb_int (&v1, &v2, &v3);

    dest[0] = v1;
    dest[1] = v2;
    dest[2] = v3;

In the new implementation, the RGB→HSV→RGB transformations were solved by progressing with variables r, g and b through the algorithms. In between the value component was inverted as required by the plug-in. The solved algorithm didn't even have to compute the hue and saturation channels. Components of these values were instead used (with the rest of the components solved out). The following is the new per-pixel code:

    /* Data types are provided for reference */
    guchar *src;
    guchar *dest;
    int    r, g, b;
    int    value, value2, min, delta;

    r = *src++;
    g = *src++;
    b = *src++;

    if (r > g)
      {
        value = MAX (r, b);
        min = MIN (g, b);
      }
    else
      {
        value = MAX (g, b);
        min = MIN (r, b);
      }

    delta = value - min;
    if ((value == 0) || (delta == 0))
      {
        r = 255 - value;
        g = 255 - value;
        b = 255 - value;
      }
    else
      {
        value2 = value / 2;

        if (r == value)
          {
            r = 255 - r;
            b = ((r * b) + value2) / value;
            g = ((r * g) + value2) / value;
          }
        else if (g == value)
          {
            g = 255 - g;
            r = ((g * r) + value2) / value;
            b = ((g * b) + value2) / value;
          }
        else
          {
            b = 255 - b;
            g = ((b * g) + value2) / value;
            r = ((b * r) + value2) / value;
          }
      }

    *dest++ = r;
    *dest++ = g;
    *dest++ = b;

The new algorithm doesn't even use floating-point, whereas the conversion functions use floating point (the _int suffix in their names is for the data type of the function arguments). So the verdict? The new algorithm takes 3 seconds compared to the old one which took 8 seconds on an 8 mega-pixel image. So the efficiency has more than doubled and almost tripled (empirically speaking).

All this in pure C without even using MMX. :) The code is in CVS now for anyone who wants to try it. Pizzas are queued for Michael Natterer and Sven Neumann for offering their many thoughts which improved the code.