7
\$\begingroup\$

I want to change all the pixels in an image to have the same value, in terms of the HSV colour space.

At the moment I'm running the following code:

private Bitmap changeVForAllPixels(Bitmap bitmap, float newV) 
{
    int width = bitmap.getWidth();
    int height = bitmap.getHeight();
    int[] rgbs = new int[width * height];

    bitmap.getPixels(rgbs, 0, width, 0, 0, width, height);

    for(int rgbi = 0; rgbi < rgbs.length; rgbi++)
    {
        float[] hsv = new float[3];
        Color.colorToHSV(rgbs[rgbi], hsv);
        hsv[2] = newV;
        rgbs[rgbi] = Color.HSVToColor(hsv);
    }

    return Bitmap.createBitmap(rgbs, width, height, Bitmap.Config.ARGB_8888);
}

I would like to know if there is a faster way, as this is taking in the range of 30 seconds to process a 1920 x 1080 pixels image on an LG D802 phone. I'd like to get it down to the 1 second range, or to know if that's not possible.

\$\endgroup\$
  • \$\begingroup\$ You might want to look into using OpenGL or OpenCL, I have heard about, but not actually seen people use the GPU to all the heavy lifting. If you succeed it should be much faster. \$\endgroup\$ – cybernard Aug 15 '15 at 0:35
5
\$\begingroup\$

Disclaimer: I am NOT familiar with Java, let alone the Android version. This may not compile or may be slower. I have no way to test this!


First of all, You deserve huge congratulations!!! Even I could read and understand what is going on! From the bottom of my heart: Thank you!

But still, there are a few points that scared me.

One of them is this:

int[] rgbs = new int[width * height];

Why rgbs? Sure, you are storing an RGB representation of a pixel in the form of an integer. So, why not just call it pixels?

Other variable that needs rewording is rgbi. Since it is an incrementer, it should be simply i. No need to complicate.


Based on http://developer.android.com/training/articles/perf-tips.html, you could use the for loop with 'cached' length, to try to speed up your code. I'm not sure if it will work.

It would look like this:

int length = pixels.length;
for(int i = 0; i < length; i++)
{
    float[] hsv = new float[3];
    Color.colorToHSV(pixels[i], hsv);
    hsv[2] = newV;
    pixels[i] = Color.HSVToColor(hsv);
}

You may ask: Why aren't you using for-each?

Since you are setting the value of the pixels again, it won't work. Based on https://stackoverflow.com/questions/15844443/why-java-foreach-doesnt-change-element-value, you couldn't write back the new value since it will create a copy. You could try to get a reference instead (possible in PHP), but I'm not sure if it works in Java.

Besides that, the page also says that for performance-critical loops, this is the best choice.


Your biggest bottleneck is this block:

float[] hsv = new float[3];
Color.colorToHSV(pixels[i], hsv);
hsv[2] = newV;
pixels[i] = Color.HSVToColor(hsv);

This is where everything happens! You could try to use memoization techniques to store already-calculated values. This will speed-up for images with less colors, like a photo of the sun/clean sky or a logo or similars. Photos with areas of colors that are equal or similar.

For images with lots of colors, like a photo of a landscape, it may still produce somewhat good results in RAM. Since there are 16777216 colors that can be generated using RGB values, this would be equivalent to storing 4 * 16777216 = 67108864 Bytes = 65536 KBytes = 64MBytes in your worst case scenario. Since your bitmaps are 1920 x 1080 pixels, you have 1920 * 1080 = 2073600 pixels * 4 = 6220800 bytes = 6075 KBytes ~= 5,9326171875 MBytes of information. So, you don't have to worry about your worst case scenario. As long as the newV doesn't change, all this data is re-usable to other images, being it even faster on the next ones.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Please show us exactly where in that document it recommends that "cached" condition. There's absolutely nothing cached about it. 1. The compiler probably calculates it once and inlines that value and even if it doesn't: accessing pixels.length is O(1) since it's just reading a value, nothing different than reading length. \$\endgroup\$ – Jeroen Vannevel Aug 14 '15 at 12:00
  • \$\begingroup\$ @JeroenVannevel take a look at developer.android.com/training/articles/perf-tips.html#Loops \$\endgroup\$ – Heslacher Aug 14 '15 at 12:05
  • \$\begingroup\$ @Heslacher Thank you, I was going to link that. What I'm using here, refering to the documentation, is the code on one(). \$\endgroup\$ – Ismael Miguel Aug 14 '15 at 12:06
4
\$\begingroup\$

This question was mentioned in The 2nd Monitor as one which could use some more input. I looked at it, and decided that the Android aspects are not where my expertise lies, but then, when I looked further, I found there are other things to consider too.

First up, I am going to assume that the android BitMap and Color classes can be loosely represented with the AWT BufferedImage and Color classes too. This is a stretch, I know, and it is something you need to take in to consideration when you read my answer. But, I assume the similarities are close enough for "engineering purposes".

Now, I took your code, and "redid" it in AWT constructs. It looks something like:

public class PlayHSV {

    // process every pixel and transform the Value to a fixed magnitude.
    private static void setHSV(final int[] pixels, final float value) {
        for (int i = 0; i < pixels.length; i++) {
            pixels[i] = transformAWT(pixels[i], value);
        }
    }

    // Using AWT tools to compute the HSV (HSB in AWT terms - B for Brightness)
    private static int transformAWT(final int color, final float bright) {
        float[] hsbvals = Color.RGBtoHSB((color >>> 16) & 0xff, (color >>> 8) & 0xff, color & 0xff, null);
        return Color.HSBtoRGB(hsbvals[0], hsbvals[1], bright);
    }

    // Main method to process input files to an output folder.
    // includes some detailed timing.
    public static void main(String[] args) throws IOException {

        File outdir = new File("output");
        outdir.mkdirs();

        for (String a : args) {
            long start = System.nanoTime();
            File file = new File(a);
            System.out.println("Processing " + file);

            BufferedImage image = loadImage(file);
            long loadtime = System.nanoTime();
            final int width = image.getWidth();
            final int height = image.getHeight();


            int[] pixels = image.getRGB(0, 0, width, height, null, 0, width);

            long pixtime = System.nanoTime();

            setHSV(pixels, 1.0f);

            long transtime = System.nanoTime();

            image.setRGB(0, 0, width, height, pixels, 0, width);

            long applytime = System.nanoTime();

            File ofile = new File(outdir, file.getName() + ".mod.jpg");
            ImageIO.write(image, "jpeg", ofile);

            long donetime = System.nanoTime();

            System.out.printf("Dimensions %d (%d x %d)\nTimes:\n  Load %.3fms\n  Pixelate %.3fms\n  "
                    + "Transform %.3fms\n  Apply %.3fms\n  Write %.3fms\n  Total %.3fms\n  PerMegapix %.5fms\n",
                            width * height,
                            width,
                            height,
                            millis(loadtime - start),
                            millis(pixtime - loadtime),
                            millis(transtime - pixtime),
                            millis(applytime - transtime),
                            millis(donetime - applytime),
                            millis(donetime - start),
                            millis(transtime - pixtime) / ((width * height) / (1024.0 * 1024.0)));

        }
    }

    private static BufferedImage loadImage(File file) throws IOException {
        return ImageIO.read(file);
    }
    private static double millis(long nanos) {
        return nanos / 1000000.0;
    }
}

Note that I have a main method which processes image files from the arguments, and reports on their timing of various stages. Specifically, I report the time to load the image, the time to extract the array of pixels, the time to transform the pixels, the time to write the transformed pixels back, and finally the time to write the image back to disk.

Note here, that the times for a large picture that I have on my computer, are long:

Processing /home/rolf/Pictures/Img20130710-115003_30_Rolf.jpg
Dimensions 36152320 (7360 x 4912)
Times:
  Load 1219.637ms
  Pixelate 1508.946ms
  Transform 1282.783ms
  Apply 1755.958ms
  Write 1199.912ms
  Total 6967.236ms
  PerMegapix 37.20635ms

That is a 36 megapixel image, and it takes 7.0 seconds to process. The transformation of those pixels takes 1.3 seconds at a rate of 37.2ms per megapixel.

A small file on the other hand, looks like:

Processing /home/rolf/Pictures/TooChatty.png
Dimensions 114798 (1007 x 114)
Times:
  Load 5.797ms
  Pixelate 8.461ms
  Transform 1.428ms
  Apply 5.066ms
  Write 9.737ms
  Total 30.489ms
  PerMegapix 13.04379ms

Again, though, note that the total time was 30ms, and the actual transformation time was only 1.5ms.

In your situation, you are not reading, or writing the file to disk, but you are extracting and re-applying full arrays of pixel values, and, in my estimates, that is about 75% or more of the time.

Or, put another way, and relating it back to your code, here's your method, and I will apply estimates of timing for that:

// the following 2 lines will take about 40% of the time
int[] rgbs = new int[width * height];
bitmap.getPixels(rgbs, 0, width, 0, 0, width, height);

// the for loop will take about 20% of the time.
for(int rgbi = 0; rgbi < rgbs.length; rgbi++)
{
    float[] hsv = new float[3];
    Color.colorToHSV(rgbs[rgbi], hsv);
    hsv[2] = newV;
    rgbs[rgbi] = Color.HSVToColor(hsv);
}

// the createBitmap will take about 40% of the time.
return Bitmap.createBitmap(rgbs, width, height, Bitmap.Config.ARGB_8888);

Now, those numbers are scary..... even if you do a no-operation transformation, you will save only 20% of your time...

That's the answer to your major question:

I would like to know if there is a faster way, as this is taking in the range of 30 seconds to process a 1920 x 1080 pixels image on an LG D802 phone. I'd like to get it down to the 1 second range, or to know if that's not possible.

No, it's not possible using the system you do, to get it down to 1 second.... of course, though, I strongly suggest you add some timing information to the Android version to check that the actual times are about what I say they will be.

On the other hand, there are 4 things I can recommend you consider when evaluating this issue:

  1. do you need to do the transfomation at all?

  2. is there a native implementation that can help - perhaps one which uses a lot of parallelism to process the data in different chunks? I am sorry I can't be more helpful in that aspect.

  3. Can you do things a pixel at a time instead of pulling the whole int array (I tried this in Java AWT, and it was slower....). I used this code:

    private static void transform(final BufferedImage image, final float value) {
        final int width = image.getWidth();
        final int height = image.getHeight();
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                image.setRGB(x, y, transformAWT(image.getRGB(x, y), value));
            }
        }
    }
    
  4. improve the performance of what you have.

That last point is an interesting one to consider. Can your for-loop be faster? There are a few things I would recommend.

Move the float[] hsv array outside the loop, and make it final. Reusing the same array may help prevent excessive collection of it. Try that, and see.

Convert the inner part of the loop to a function call. In android it may not make much of a difference but in Java, with JIT compilation, it may get compiled down faster/better as it is called more often. The inlined version will be just as good.

I then had a look at what the actual RGB->HSV and the reverse HSV->RGB transformation does, and I decided that by re-coding it, you can save some time by eliminating steps that the fixed-magnitude value allows. So, I re-coded the following to see if it would be faster, as it does less work. Consider the following (messy) code that does a fixed-v transform:

// Transform an input ARGB value to an ARGB color
// where the color is first transformed to HSV format,
// and then the V component is coerced to be the input value
// before transforming the HSV back to RGB. The Alpha component
// of the input value is copied to the output value.
public static final int transform(final int color, final float value) {

    // The following code is largely based on the following web-page
    // http://www.cs.rit.edu/~ncs/color/t_convert.html
    // It has been "tuned" to allow shorter-paths for the fixed-value transform.
    // additionally, it merges the to-HSV and from-HSV functions, and it skips some
    // redundant steps since the intermediate values are not always important.
    // In addition, it has been "ported" to Java, and variables renamed to be clearer, etc.

    if ((color & 0xffffff) == 0) {
        // black.
        return color;
    }

    final float r = toFloat(color >>> 16);
    final float g = toFloat(color >> 8);
    final float b = toFloat(color);
    final float max = max(r, g, b);
    final float min = min(r, g, b);

    final float delta = max - min;

    if (delta == 0.0f) {
        // grey - no saturation.
        int val = (int)(max * 255.0f);
        return val | (val << 8) | (val << 16);
    }

    final float saturation = delta / max;
    final float tempHue = r == max ? hue(0.0f, g, b, delta) : (g == max ? hue(2.0f, b, r, delta) : hue(4.0f, r, g, delta));
    final float hue = tempHue < 0 ? (tempHue + 6.0f) : tempHue;

    // Right, original color converted to hue, sat, and we have the passed-in value.
    // convert that back to an RGB.
    // note that hue is normally in degrees (0..360), but in the above result, it is in 6 sectors.... (0.0 to 6.0)

    final int sector = (int)hue;
    final float fractional = hue - sector;
    final float p = value * ( 1.0f - saturation );
    final float q = value * ( 1.0f - saturation * fractional );
    final float t = value * ( 1.0f - saturation * ( 1 - fractional ) );

    final int alpha = color & 0xff000000;

    switch (sector) {
    case 0:
        return toARGB(alpha, value, t, p);
    case 1:
        return toARGB(alpha, q, value, p);
    case 2:
        return toARGB(alpha, p, value, t);
    case 3:
        return toARGB(alpha, p, q, value);
    case 4:
        return toARGB(alpha, t, p, value);
    case 5:
        return toARGB(alpha, value, p, q);
    }

    throw new IllegalStateException("Unexpected sector " + sector);


}        

private static final int toARGB(final int alpha, final float r, final float g, final float b) {
    return alpha | (fromFloat(r) << 16) | (fromFloat(g) << 8) | fromFloat(b);
}

private static final int fromFloat(float r) {
    return (int)(r * 255.0f);
}

private static final float toFloat(int value) {
    return (value & 0xff) / 255.0f;
}

private static float hue(final float sectorBase, final float p, final float q, final float delta) {
    return sectorBase + (p - q) / delta;
}

private static final float min(final float a, final float b) {
    return a < b ? a : b;
}

private static final float min(final float r, final float g, final float b) {
    return min(r, min(g, b));
}

private static final float max(final float a, final float b) {
    return a > b ? a : b;
}

private static final float max(final float r, final float g, final float b) {
    return max(r, max(g, b));
}

The above code shaves about 25% off the transformation time... My results look like:

Processing /home/rolf/Pictures/Img20130710-115003_30_Rolf.jpg
Dimensions 36152320 (7360 x 4912)
Times:
  Load 1248.057ms
  Pixelate 1515.967ms
  Transform 1030.899ms
  Apply 1750.349ms
  Write 1203.219ms
  Total 6748.491ms
  PerMegapix 29.90059ms

It's debatable whether that code is worth it, but you may want to try it in your environment because it may compile a whole lot better (or worse....) on Android.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Background

You want to change the \$V\$ (value) in the HSV representation of the image. I have copied the relevant sections from the wikipedia page below:

C

HX

R1G1B1

mRGB

Mathematics

Now assume we change \$V\$ to \$V_{new}\$

\$S_{new} = S\$

\$\,C_{new} = C \cdot \frac{V_{new}}{V}\$

\$H'_{new} = H'\$

\$X_{new} = X \cdot \frac{V_{new}}{V}\$

\$(R_1, G_1, B_1)_{new} = (R_1, G_1, B_1) \cdot \frac{V_{new}}{V}\$

\$m_{new} = V_{new} - C_{new} = V \cdot \frac{V_{new}}{V} - C \cdot \frac{V_{new}}{V} = m \cdot \frac{V_{new}}{V}\$ \$(R,G,B)_{new} = (R_1,G_1,B_1)_{new} + m_{new} = (R,G,B) \cdot \frac{V_{new}}{V}\$

Code

Therefore, assuming you know the original value of \$V\$ you can simply scale the RGB values. \$V\$ can be computed as \$\mathrm{max}(R,G,B)\$. One caveat is that this will compute \$V\$ in the range of \$[0,255]\$ instead of \$[0,1]\$. Assuming \$V_{new}\$ is in the range of \$[0,1]\$ here is the code to update the RGB values:

newV *= 255.0f;
int length = pixels.length;
for(int i = 0; i < length; i++)
{
    int b = pixels[i] & 0xFF;
    pixels[i] >>= 2;
    int g = pixels[i] & 0xFF;
    pixels[i] >>= 2;
    int r = pixels[i] & 0xFF;
    pixels[i] >>= 2;
    int alpha = pixels[i] & 0xFF;

    // Find v (in the range of 0-255)
    int v = max(r, max(g, b));

    float scale = newV / v;
    r *= scale;
    g *= scale;
    b *= scale;

    pixels[i] = argb(alpha, r, g, b);        
}

Final thoughts

Of course if rolfl's timings are correct then this change will be insignificant. If this loop was the bottleneck then parallelization would be the answer.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.