Histogram Matching in Renderscript

Question

In order to align the intensity values of two grayscale Images (as a first step for further processing) I wrote a Java method that:

1. converts the bitmaps of the two images into two int[] arrays containing the bitmap's intensities (I just take the red component here, since it's grayscale, i.e. r=g=b ).

   public static int[] bmpToData(Bitmap bmp){
   int width = bmp.getWidth();
   int height = bmp.getHeight();
   int anzpixel = width*height;
   int [] pixels = new int[anzpixel];
   int [] data = new int[anzpixel];  
   bmp.getPixels(pixels, 0, width, 0, 0, width, height);
   for (int i = 0 ; i < anzpixel ; i++) {
   int p = pixels[i];
   int r = (p & 0xff0000) >> 16;
   //int g = (p & 0xff00) >> 8;
   //int b = p & 0xff;
   data[i] = r;
   }
   return data;
   }
   

2. aligns the cumulated intensity distributions of Bitmap 2 to that of Bitmap 1

       //aligns the intensity distribution of a grayscale picture moving    (given by int[] //data2) the the intensity distribution of a reference picture fixed (given by // int[] data1)
   public static int[] histMatch(int[] data1, int[] data2){
   
      int anzpixel = data1.length;
      int[] histogram_fixed = new int[256];
      int[] histogram_moving = new int[256];
      int[] cumhist_fixed = new int[256];
      int[] cumhist_moving = new int[256];
      int i=0;
      int j=0;
   
      //read intensities of fixed und moving in histogram
      for (int n = 0; n < anzpixel; n++) {
         histogram_fixed[data1[n]]++;
         histogram_moving[data2[n]]++;
      }
   
      // calc cumulated distributions
      cumhist_fixed[0]=histogram_fixed[0];
      cumhist_moving[0]=histogram_moving[0];
      for ( i=1; i < 256; ++i ) {
         cumhist_fixed[i] = cumhist_fixed[i-1]+histogram_fixed[i];
         cumhist_moving[i] = cumhist_moving[i-1]+histogram_moving [i];
      }
   
      // look-up-table lut[]. For each quantile i of the moving picture search     the 
      // value j of the fixed picture where the quantile is the same as that of moving   
      int[] lut = new int[anzpixel];
      j=0;
      for ( i=0; i < 256; ++i ){
         while(cumhist_fixed[j]< cumhist_moving[i]){
            j++;
         }
   
         // check, whether the distance to the next-lower intensity is even lower, and if so, take this value
         if ((j!=0) && ((cumhist_fixed[j-1]- cumhist_fixed[i]) < (cumhist_fixed[j]- cumhist_fixed[i]))){
            lut[i]= (j-1);
         }
         else {
            lut[i]= (j);
         }
      }
   
      // apply the lut[] to moving picture.
      i=0;
      for (int n = 0; n < anzpixel; n++) {
         data2[n]=(int) lut[data2[n]];
      }
      return data2;
   }
   

3. converts the int[] arrays back to Bitmap.

   public static Bitmap dataToBitmap(int[] data, int width, int heigth) {
    int index=0;
    Bitmap bmp = Bitmap.createBitmap(width, heigth, Bitmap.Config.ARGB_8888);
    for (int x = 0; x < width; x++) {
     for (int y = 0; y < heigth; y++) {
        index=y*width+x;
        int c = data[index];
        bmp.setPixel(x,y,Color.rgb(c, c, c));
        }
    }
    return bmp;
   }
   

While the core procedure 2) is straightforward and fast, the conversion steps 1) and 3) are rather inefficient. It would be more than cool to do the whole thing in Renderscript. But, honestly, I am completely lost in doing so because of missing documentation and, while there are many impressing examples on what Renderscript COULD perform, I don't see a way to benefit from these possibilities (no books, no docu). Any advice is highly appreciated!

Answer 1

As a starting point, use Android Studio to "Import Sample..." and select Basic Render Script. This will give you a working project that we will now modify.

First, let's add more Allocation references to MainActivity. We will use them to communicate image data, histograms and the LUT between Java and Renderscript.

private Allocation mInAllocation;
private Allocation mInAllocation2;
private Allocation[] mOutAllocations;
private Allocation mHistogramAllocation;
private Allocation mHistogramAllocation2;
private Allocation mLUTAllocation;

Then in onCreate() load another image, which you will also need to add to /res/drawables/.

    mBitmapIn2 = loadBitmap(R.drawable.cat_480x400);

In createScript() create additional allocations:

    mInAllocation2 = Allocation.createFromBitmap(mRS, mBitmapIn2);
    mHistogramAllocation = Allocation.createSized(mRS, Element.U32(mRS), 256);
    mHistogramAllocation2 = Allocation.createSized(mRS, Element.U32(mRS), 256);
    mLUTAllocation = Allocation.createSized(mRS, Element.U32(mRS), 256);

And now the main part (in RenderScriptTask):

            /*
             * Invoke histogram kernel for both images
             */
            mScript.bind_histogram(mHistogramAllocation);
            mScript.forEach_compute_histogram(mInAllocation);

            mScript.bind_histogram(mHistogramAllocation2);
            mScript.forEach_compute_histogram(mInAllocation2);


            /*
             * Variables copied verbatim from your code.
             */
            int []histogram_fixed = new int[256];
            int []histogram_moving = new int[256];
            int[] cumhist_fixed = new int[256];
            int[] cumhist_moving = new int[256];
            int i=0;
            int j=0;

            // copy computed histograms to Java side
            mHistogramAllocation.copyTo(histogram_fixed);
            mHistogramAllocation2.copyTo(histogram_moving);

            // your code again...
            // calc cumulated distributions
            cumhist_fixed[0]=histogram_fixed[0];
            cumhist_moving[0]=histogram_moving[0];

            for ( i=1; i < 256; ++i ) {
                cumhist_fixed[i] = cumhist_fixed[i-1]+histogram_fixed[i];
                cumhist_moving[i] = cumhist_moving[i-1]+histogram_moving [i];
            }

            // look-up-table lut[]. For each quantile i of the moving picture search     the
            // value j of the fixed picture where the quantile is the same as that of moving
            int[] lut = new int[256];
            j=0;
            for ( i=0; i < 256; ++i ){
                while(cumhist_fixed[j]< cumhist_moving[i]){
                    j++;
                }

                // check, whether the distance to the next-lower intensity is even lower, and if so, take this value
                if ((j!=0) && ((cumhist_fixed[j-1]- cumhist_fixed[i]) < (cumhist_fixed[j]- cumhist_fixed[i]))){
                    lut[i]= (j-1);
                }
                else {
                    lut[i]= (j);
                }
            }

            // copy the LUT to Renderscript side
            mLUTAllocation.copyFrom(lut);
            mScript.bind_LUT(mLUTAllocation);

            // Apply LUT to the destination image
            mScript.forEach_apply_histogram(mInAllocation2, mInAllocation2);


            /*
             * Copy to bitmap and invalidate image view
             */
            //mOutAllocations[index].copyTo(mBitmapsOut[index]);

            // copy back to Bitmap in preparation for viewing the results
            mInAllocation2.copyTo((mBitmapsOut[index]));

Couple notes:

• In your part of the code I also fixed LUT allocation size - only 256 locations are needed,
• As you can see, I left the computation of cumulative histogram and LUT on Java side. These are rather difficult to efficiently parallelize due to data dependencies and small scale of the calculations, but considering the latter I don't think it's a problem.

Finally, the Renderscript code. The only non-obvious part is the use of rsAtomicInc() to increase values in histogram bins - this is necessary due to potentially many threads attempting to increase the same bin concurrently.

#pragma version(1)
#pragma rs java_package_name(com.example.android.basicrenderscript)
#pragma rs_fp_relaxed

int32_t *histogram;
int32_t *LUT;

void __attribute__((kernel)) compute_histogram(uchar4 in)
{
    volatile int32_t *addr = &histogram[in.r];
    rsAtomicInc(addr);
}

uchar4 __attribute__((kernel)) apply_histogram(uchar4 in)
{
    uchar val = LUT[in.r];
    uchar4 result;
    result.r = result.g = result.b = val;
    result.a = in.a;

    return(result);
}