Faster way to extract histogram from an image

Question

I'm looking for a faster way to extract histogram data from an image. I'm currently using this piece of code that needs about 1200ms for a 6mpx JPEG image:

        ImageReader imageReader = (ImageReader) iter.next();
        imageReader.setInput(is);
        BufferedImage image = imageReader.read(0);
        int height = image.getHeight();
        int width = image.getWidth();
        Raster raster = image.getRaster();
        int[][] bins = new int[3][256];

        for (int i = 0; i < width; i++) 
            for (int j = 0; j < height; j++) {
                bins[0][raster.getSample(i, j, 0)]++;
                bins[1][raster.getSample(i, j, 1)]++;
                bins[2][raster.getSample(i, j, 2)]++;

            }

Do you have any suggestions?

Answer 1

You're doing a lot of getSamples method calls and they're in turn doing calls and calls etc.

I work often with pictures and the typical trick to gain speed is to manipulate directly the underlying int[] (in this case your BufferedImage must be backed by an int[]).

The difference between accessing the int[] and doing, say, a getRGB can be gigantic. When I write gigantic, I mean by as much as two orders of magnitude (try doing a getRGB on OS X 10.4 vs int[x] and you'll see the perf gain).

Also, there's no call three times getSamples. I'd simply retrieve one int corresponding to your ARGB pixel and then bitshift to get the RGB bands (you're doing one histogram per R, G and B component right?).

You can gain access to the pixels array by doing something like this:

final int[] a = ((DataBufferInt) image.getRaster().getDataBuffer()).getData();

Also you can do what you want to do with a single loop, looping over all the pixels.

Instead of:

for ( int x = 0; x < width; x++ ) {
    for ( int y = 0; y < height; y++ ) {
        ....

You can do:

for ( int p = 0; p < width*height; p++ ) {

Now if you want to get into weirder optimizations, not as likely to prove effective you could:

• use loop unrolling (iterating over 6 million pixels is one of the rare case where it may help)

• invert the loop: for ( p = width*height - 1; p >= 0; p--)

Answer 2

You can use getSamples(int x, int y, int w, int h, int b, double[] dArray) method It's possible that this method have internal optimisations. Also, you can try to swap width and height.

for (int i = 0; i < width; i++) 
   for (int j = 0; j < height; j++) {
   }
}

And

for (int i = 0; i < height; i++) 
   for (int j = 0; j < width; j++) {
   }
}

Between this two variants performance difference will be huge. This is influence of the cpu cache