Fast formula for a "high contrast" curve

Question

My inner loop contains a calculation that profiling shows to be problematic.

The idea is to take a greyscale pixel x (0 <= x <= 1), and "increase its contrast". My requirements are fairly loose, just the following:

• for x < .5, 0 <= f(x) < x
• for x > .5, x < f(x) <= 1
• f(0) = 0
• f(x) = 1 - f(1 - x), i.e. it should be "symmetric"
• Preferably, the function should be smooth.

So the graph must look something like this:

.

I have two implementations (their results differ but both are conformant):

float cosContrastize(float i) {
    return .5 - cos(x * pi) / 2;
}

float mulContrastize(float i) {
    if (i < .5) return i * i * 2;
    i = 1 - i;
    return 1 - i * i * 2;
}

So I request either a microoptimization for one of these implementations, or an original, faster formula of your own.

Maybe one of you can even twiddle the bits ;)

Answer 1

Consider the following sigmoid-shaped functions (properly translated to the desired range):

• error function
• normal CDF
• tanh
• logit

I generated the above figure using MATLAB. If interested here's the code:

x = -3:.01:3;
plot(   x, 2*(x>=0)-1, ...
        x, erf(x), ...
        x, tanh(x), ...
        x, 2*normcdf(x)-1, ...
        x, 2*(1 ./ (1 + exp(-x)))-1, ...
        x, 2*((x-min(x))./range(x))-1  )
legend({'hard' 'erf' 'tanh' 'normcdf' 'logit' 'linear'})

Answer 2

Trivially you could simply threshold, but I imagine this is too dumb:

return i < 0.5 ? 0.0 : 1.0;

Since you mention 'increasing contrast' I assume the input values are luminance values. If so, and they are discrete (perhaps it's an 8-bit value), you could use a lookup table to do this quite quickly.

Your 'mulContrastize' looks reasonably quick. One optimization would be to use integer math. Let's say, again, your input values could actually be passed as an 8-bit unsigned value in [0..255]. (Again, possibly a fine assumption?) You could do something roughly like...

int mulContrastize(int i) {
  if (i < 128) return (i * i) >> 7; 
  // The shift is really: * 2 / 256
  i = 255 - i;
  return 255 - ((i * i) >> 7);

Answer 3

A piecewise interpolation can be fast and flexible. It requires only a few decisions followed by a multiplication and addition, and can approximate any curve. It also avoids the courseness that can be introduced by lookup tables (or the additional cost in two lookups followed by an interpolation to smooth this out), though the lut might work perfectly fine for your case.

With just a few segments, you can get a pretty good match. Here there will be courseness in the color gradients, which will be much harder to detect than courseness in the absolute colors.

As Eamon Nerbonne points out in the comments, segmentation can be optimized by "choos[ing] your segmentation points based on something like the second derivative to maximize detail", that is, where the slope is changing the most. Clearly, in my posted example, having three segments in the middle of the five segment case doesn't add much more detail.