# Image-processing algorithm on mobile device

I have written the following algorithm (for Android/NDK) to apply levels to a bitmap. The problem is that it is really very slow. On a fast device such as the SGSIII, it can take up to 4 seconds for an 8MP image. And on devices with ARMv6 takes ages (over 10 seconds). I know that can be speed up with NEON instructions, but I don't have such knowledge.

Is there any way to optimize it?

void applyLevels(unsigned int *rgb, const unsigned int width, const unsigned int height, const float exposure, const float brightness, const float contrast, const float saturation)
{
float R, G, B;

unsigned int pixelIndex = 0;

float exposureFactor   = powf(2.0f, exposure);
float brightnessFactor = brightness / 10.0f;
float contrastFactor   = contrast > 0.0f ? contrast : 0.0f;
float saturationFactor = 1.0f - saturation;

for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
const int pixelValue = buffer[pixelIndex];

R = ((pixelValue & 0xff0000) >> 16) / 255.0f;
G = ((pixelValue & 0xff00) >> 8) / 255.0f;
B = (pixelValue & 0xff) / 255.0f;

// Clamp values

R = R > 1.0f ? 1.0f : R < 0.0f ? 0.0f : R;
G = G > 1.0f ? 1.0f : G < 0.0f ? 0.0f : G;
B = B > 1.0f ? 1.0f : B < 0.0f ? 0.0f : B;

// Exposure

R *= exposureFactor;
G *= exposureFactor;
B *= exposureFactor;

// Contrast

R = (((R - 0.5f) * contrastFactor) + 0.5f);
G = (((G - 0.5f) * contrastFactor) + 0.5f);
B = (((B - 0.5f) * contrastFactor) + 0.5f);

// Saturation

float gray = (R * 0.3f) + (G * 0.59f) + (B * 0.11f);
R = (gray * saturationFactor) + R * saturation;
G = (gray * saturationFactor) + G * saturation;
B = (gray * saturationFactor) + B * saturation;

// Brightness

R += brightnessFactor;
G += brightnessFactor;
B += brightnessFactor;

// Clamp values

R = R > 1.0f ? 1.0f : R < 0.0f ? 0.0f : R;
G = G > 1.0f ? 1.0f : G < 0.0f ? 0.0f : G;
B = B > 1.0f ? 1.0f : B < 0.0f ? 0.0f : B;

// Store new pixel value

R *= 255.0f;
G *= 255.0f;
B *= 255.0f;

buffer[pixelIndex] = ((int)R << 16) | ((int)G << 8) | (int)B;

pixelIndex++;
}
}
}


• Just loop over the index.
• The first clamp is unnecessary. (X & 0xff) will always be between 0 and 255.
• Look at it algebraically. There are some expressions that do not depend on R, B, or B that you can extract from the loop.
• You can extract some common expressions and calculate them at the same time as grey.

.

void applyLevels(unsigned int *rgb, const unsigned int width, const unsigned int height, const float exposure, const float brightness, const float contrast, const float saturation)
{
const float exposureFactor   = powf(2.0f, exposure);
const float brightnessFactor = brightness / 10.0f;
const float contrastFactor   = contrast > 0.0f ? contrast : 0.0f;
const float saturationFactor = 1.0f - saturation;

const float f01 = exposureFactor / 255.0f * contrastFactor;
const float f02 = 0.5f * (1.0f - contrastFactor);

const unsigned int nPixel = width * height;
for(unsigned int pixelIndex = 0; pixelIndex < nPixel; ++pixelIndex)
{
const unsigned int pixelValue = rgb[pixelIndex];
float R = static_cast<float>((pixelValue >> 16) & 0xff);
float G = static_cast<float>((pixelValue >>  8) & 0xff);
float B = static_cast<float>((pixelValue      ) & 0xff);

R = R * f01 + f02;
G = G * f01 + f02;
B = B * f01 + f02;

const float f03 = ((R * 0.3f) + (G * 0.59f) + (B * 0.11f)) * saturationFactor + brightnessFactor;

R = (R * saturation + f03) * 255.0f;
G = (G * saturation + f03) * 255.0f;
B = (B * saturation + f03) * 255.0f;

R = R > 255.0f ? 255.0f : R < 0.0f ? 0.0f : R;
G = G > 255.0f ? 255.0f : G < 0.0f ? 0.0f : G;
B = B > 255.0f ? 255.0f : B < 0.0f ? 0.0f : B;

rgb[pixelIndex] =
(static_cast<unsigned int>(R) << 16) |
(static_cast<unsigned int>(G) <<  8) |
(static_cast<unsigned int>(B)      );
}
}


Other optimizations:

• Do you need an entire 8MP image? Can you downscale the image or even grab a portion?
• How often do you need to apply all four operations to an image? If it is common for some images to only require exposure and saturation then make separate functions.
• Convert the for to a parallel for and use neon and other intrinsics.
• Rather than doing the previous suggestion I would recommend using Renderscript. It will use your GPU if it can. If it uses the CPU it is automatically multithreaded.
• About the 8MP, the answer is yes. Users get very annoyed when they edit an image and it gets size reduced. Is like if you edit in Photoshop and after you realize Photoshop reduces your image metrics if you do any change to it. Second question, levels are applied by the user as they wish. I'll check on renderscript. – PerracoLabs Mar 27 '14 at 11:23

Depending on the content of the image, you might get an improvement with:

const int pixelPrevious = buffer ^ 1; // A value guaranteed to not match buffer.
for (unsigned int pixelIndex = 0; pixelIndex < limit; pixelIndex++)
{
const int pixelValue = buffer[pixelIndex];
if (pixelPrevious == pixelValue)
{
buffer[pixelIndex] = buffer[pixelIndex - 1];
continue;
}
pixelPrevious = pixelValue;


The idea is to skip the recalculation where consecutive pixel values are identical.

I expect that would improve performance iff consecutive pixel values are often identical in the image.

I know that can be speed up with NEON instructions, but I don't have such knowledge.

One of the things it says is,

It turns out that floating point operations are slow1 and an immediate improvement can be made by modifying the algorithm slightly to process integers instead of floats.

So, firstly, you might get better performance by multiplying everything by 255.

Second, it introduces how to use NEON.

Depending on your compiler, this advice might or might not have an effect. As a rule of thumb, let's try to give the compiler and the reader as many hints as possible and let's make things as simple as it can be.

unsigned int pixelIndex = 0;
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
some_function(pixelIndex);
pixelIndex++;
}
}


could be written with a single-loop, thus saving some comparisons and the update of 3 different variables :

const unsigned int limit = height*width; // your compiler should notice that this is const and does not need being re-evaluated at each iteration but let's give him a bigger hint.
for (unsigned int pixelIndex = 0; pixelIndex < limit; pixelIndex++)
{
some_function(pixelIndex);
}


You could define exposureFactor, brightnessFactor, contrastFactor and saturationFactor, gray as constants.

You could declare and define R, G, B inside the loop to limit their scope.

You could compute gray * saturationFactor only once if you were storing the result.

You could also try to limit the number of accesses to R,G,B by packing the evaluation. The drawback is that you might lose readibility by doing do.

At the end, my version of the code is

void applyLevels(unsigned int *rgb, const unsigned int width, const unsigned int height, const float exposure, const float brightness, const float contrast, const float saturation)
{
const float exposureFactor   = powf(2.0f, exposure);
const float brightnessFactor = brightness / 10.0f;
const float contrastFactor   = contrast > 0.0f ? contrast : 0.0f;
const float saturationFactor = 1.0f - saturation;

const unsigned int limit = height*width;
for (unsigned int pixelIndex = 0; pixelIndex < limit; pixelIndex++)
{
const int pixelValue = buffer[pixelIndex];

float R = ((pixelValue & 0xff0000) >> 16) / 255.0f;
float G = ((pixelValue & 0xff00) >> 8) / 255.0f;
float B = (pixelValue & 0xff) / 255.0f;

// Clamp values + exposure factor + contrast
R = (((R > 1.0f ? exposureFactor : R < 0.0f ? 0.0f : exposureFactor*R) - 0.5f) * contrastFactor) + 0.5f;
G = (((G > 1.0f ? exposureFactor : G < 0.0f ? 0.0f : exposureFactor*G) - 0.5f) * contrastFactor) + 0.5f;
B = (((B > 1.0f ? exposureFactor : B < 0.0f ? 0.0f : exposureFactor*B) - 0.5f) * contrastFactor) + 0.5f;

// Saturation + Brightness
const float graySaturFactorPlusBrightness = brightnessFactor + ((R * 0.3f) + (G * 0.59f) + (B * 0.11f)) * saturationFactor;
R = graySaturFactorPlusBrightness + R * saturation;
G = graySaturFactorPlusBrightness + G * saturation;
B = graySaturFactorPlusBrightness + B * saturation;

// Clamp values
R = R > 1.0f ? 255.0f : R < 0.0f ? 0.0f : 255.0f*R;
G = G > 1.0f ? 255.0f : G < 0.0f ? 0.0f : 255.0f*G;
B = B > 1.0f ? 255.0f : B < 0.0f ? 0.0f : 255.0f*B;

buffer[pixelIndex] = ((int)R << 16) | ((int)G << 8) | (int)B;
}
}


I am convinced it is slightly better than yours from a performance point of view but I'm not sure you'll be able to notice any actual difference in the run time.

• The first R > 1.0f expressions are always false, because they're a byte value (max 255) divided by 255.0f – ChrisW Mar 26 '14 at 22:48
• Pretty clever comment! Thanks for the idea. As you've added an answer yourself, I'll let you add it. – SylvainD Mar 27 '14 at 8:44

Try change float to double. There are some devices based on ARM architecture that works 40 times slower using floats.