Get Bytes from an int to avoid bit shifting fun - Java (Median Filtering)

Question

Hi All,

I'm trying to perform a Median filter on an image in Java but it's terribly slow. Firstly, if any of you know of a standalone implementation I could use it would be fantastic if you could let me know. I'm implementing on Android, trying to replicate a small part of the JAI.

In my method I take each pixel, extract the R,G & B values using

r = pixel >> 16 & 0xFF

Or similar, find the median for the kernel and finish with

pixel = a | r <<16 | g << 8 | b

Is there any way I can grab the bytes from an int in such a way that this would be faster?

Kind regards,

Gavin

---

EDIT: Full code to help diagnose my low performance upon request

For the actual source file please go here that's where my implementation of medianFilter can be found.

width and height variables are for the size of dest and are available as class member variables. The pixels are linearized into a one dimensional array.

private void medianFilterSquare(int[] source, int[] dest, int rWidth,
     int rHeight, int radius) {
    // Source has been reflected into a border of size radius
    // This makes it radius * 2 pixels wider and taller than the dest
    int r,g,b;
    int destOffset, rOffset, kOffset;

    // The first offset into the source to calculate a median for
    // This corresponds to the first pixel in dest
    int rFirst = radius + (rWidth*radius);

    // We use a square kernel with the radius passed
    int neighbours = (radius+radius+1)*(radius+radius+1);

    int index;

    // Arrays to accumulate the values for median calculation
    int[] rs = new int[neighbours];
    int[] gs = new int[neighbours];
    int[] bs = new int[neighbours];

    // Declaring outside the loop helps speed? I'm sure this is done for me
    // by the compiler
    int pixel;

    // Iterate over the destination pixels
    for(int x = 0; x < height; x++){
     for(int y = 0; y < width; y++){
      // Offset into destination
      destOffset = x + (y * width);
      // Offset into source with border size radius
      rOffset = destOffset + rFirst + (y * (radius *2));

      index = 0;

      // Iterate over kernel
      for(int xk = -radius; xk < radius ; xk ++){
       for(int yk = -radius; yk < radius ; yk ++){
        kOffset = rOffset + (xk + (rWidth*yk));
        pixel = source[kOffset];
        // Color.red is equivalent to (pixel>>16) & 0xFF
        rs[index] = Color.red(pixel);
        gs[index] = Color.green(pixel);
        bs[index] = Color.blue(pixel);
        index++;
       } 
      }
      r = medianFilter(rs);
      g = medianFilter(gs);
      b = medianFilter(bs);

      dest[destOffset] = Color.rgb(r, g, b);
     }   
    }  
}

Answer 1

In addition to my comment, I have found code that performs a median filter in java.

Link Download

Answer 2

As others have said, it's possible that it's the bit in between which is causing the problem. One thing I would say (which may be obvious, but anyway) - don't just profile the application on a desktop VM and assume that the bottleneck will be in the same place. I wouldn't be at all surprised to find entirely different bottlenecks within Dalvik.

Is it possible for you to work with the values still shifted? For instance, if you were to just mask for different colours:

int r = pixel & 0xff0000;
int g = pixel & 0xff00;
int b = pixel & 0xff;

could you tweak your processing algorithm accordingly?

One final thought: I always find the precedence of shift operators confusing. I'd strongly recommend that from a readability point of view, you bracket them:

r = (pixel >> 16) & 0xFF;
pixel = a | (r <<16) | (g << 8) | b;

Irrelevant to performance, but if I were a maintainer I'd certainly appreciate it :)

Answer 3

The fastet way to get your r,g,b values should be

new byte[] {
  (byte)(value >>> 24),
  (byte)(value >>> 16),
  (byte)(value >>> 8),
  (byte)value
};

Answer 4

Concentrating on how to do the bit operations is a distraction. It only matters how you're doing these operations because you're needlessly processing the same pixel over and over.

You're calling median filter for every pixel three times, and you're getting multiple pixels around the pixel per pixel. Which means you're doing all that bit work for the same pixel multiple times. You have for loops nested four deep!

If your radius is 5, you're processing 121 pixels. Then you move down by one and process 121 pixels again, and you've already converted all but 11 of them! You do the same thing for every pixel down, then move to the right one pixel. For a radius of five, you're doing two orders of magnitude as many rgb conversions as you have to.

I'd suggest keeping your image in or converting your image to separate red, blue, and green arrays first.

---

If radius is large, you could keep the red, blue, and green sums as you move along, subtracting out the pixels from the top and adding in the pixels from the bottom as you crawl down the bitmap, but that would make the code a touch more complicated. Whether you add code to optimize further depends on your requirements.

---

Also, you have a bunch of little things that could be optimized. I'm not sure if the compiler is taking care of them or not. For instance, you could do some strength reduction. You don't need any of the multiplications you have in the lines that calculate neighbors, destOffset, rOffset, or kOffset. Addition is all you need for those if you refactor the code a bit.

Answer 5

You can occasionally get away with doing arithmetic on the red & blue components simultaneously in a single int:

int average(int rgb1, int rgb2)
{
    int rb = (((rgb1 & 0xFF00FF) + (rgb2 & 0xFF00FF)) >> 1) & 0xFF00FF;
    int g = (((rgb1 & 0xFF00) + (rgb2 & 0xFF00)) >> 1) & 0xFF00;
    return (rb | g);
}

because the red and blue components are separated by 8 bits, they don't interfere with each other.

I've never seen a significant (more than 5-10%) speedup from this though.