8
\$\begingroup\$

I have the following class that processes a Bitmap to place a fisheye distortion on it. I've run my app through TraceView and found that virtually all the processing time is spent looping through the bitmap. One developer has suggested not using float as this will slow things down where graphics are concerned. Also, using math.pow() and ceil() are not necessary?

At the moment to place the effect by looping through the entire bitmap takes around 42 seconds, yes seconds:) I've tried replacing the floats with integers and that has reduced the time to 37 secs, but the effect is no longer present on the bitmap. The argument k is originally a float and sets the level of distortion (eg 0.0002F). If I pass an integer, then the effect doesn't work.

Can anyone point me in the right direction on how to optimize this process? Once I've optimized it I'd like to look into perhaps not looping through the entire bitmap and maybe putting a bounding box around the effect or using the algorithm below that determines whether a pixel is within the circle with a radius of 150.

class Filters{
    float xscale;
    float yscale;
    float xshift;
    float yshift;
    int [] s;
    private String TAG = "Filters";
    long getRadXStart = 0;
    long getRadXEnd = 0;
    long startSample = 0;
    long endSample = 0;
    public Filters(){

        Log.e(TAG, "***********inside filter constructor");
    }

    public Bitmap barrel (Bitmap input, float k){
        //Log.e(TAG, "***********INSIDE BARREL METHOD ");

        float centerX=input.getWidth()/2; //center of distortion
        float centerY=input.getHeight()/2;

        int width = input.getWidth(); //image bounds
        int height = input.getHeight();

        Bitmap dst = Bitmap.createBitmap(width, height,input.getConfig() ); //output pic
       // Log.e(TAG, "***********dst bitmap created ");
          xshift = calc_shift(0,centerX-1,centerX,k);

          float newcenterX = width-centerX;
          float xshift_2 = calc_shift(0,newcenterX-1,newcenterX,k);

          yshift = calc_shift(0,centerY-1,centerY,k);

          float newcenterY = height-centerY;
          float yshift_2 = calc_shift(0,newcenterY-1,newcenterY,k);

          xscale = (width-xshift-xshift_2)/width;
        //  Log.e(TAG, "***********xscale ="+xscale);
          yscale = (height-yshift-yshift_2)/height;
        //  Log.e(TAG, "***********yscale ="+yscale);
        //  Log.e(TAG, "***********filter.barrel() about to loop through bm");


          int origPixel;
          long startLoop = System.currentTimeMillis();
          for(int j=0;j<dst.getHeight();j++){
              for(int i=0;i<dst.getWidth();i++){
                 origPixel= input.getPixel(i,j);
                 getRadXStart = System.currentTimeMillis();
                float x = getRadialX((float)j,(float)i,centerX,centerY,k);
                getRadXEnd= System.currentTimeMillis();

                float y = getRadialY((float)j,(float)i,centerX,centerY,k);

                sampleImage(input,x,y);

                int color = ((s[1]&0x0ff)<<16)|((s[2]&0x0ff)<<8)|(s[3]&0x0ff);
    //            System.out.print(i+" "+j+" \\");

                if( Math.sqrt( Math.pow(i - centerX, 2) + ( Math.pow(j - centerY, 2) ) ) <= 150 ){
                dst.setPixel(i, j, color);
                }else{
                    dst.setPixel(i,j,origPixel);
                }
              }
            }

        return dst;
    }

    void sampleImage(Bitmap arr, float idx0, float idx1)
    {
         startSample = System.currentTimeMillis();
        s = new int [4];
      if(idx0<0 || idx1<0 || idx0>(arr.getHeight()-1) || idx1>(arr.getWidth()-1)){
        s[0]=0;
        s[1]=0;
        s[2]=0;
        s[3]=0;
        return;
      }

      float idx0_fl=(float) Math.floor(idx0);
      float idx0_cl=(float) Math.ceil(idx0);
      float idx1_fl=(float) Math.floor(idx1);
      float idx1_cl=(float) Math.ceil(idx1);

      int [] s1 = getARGB(arr,(int)idx0_fl,(int)idx1_fl);
      int [] s2 = getARGB(arr,(int)idx0_fl,(int)idx1_cl);
      int [] s3 = getARGB(arr,(int)idx0_cl,(int)idx1_cl);
      int [] s4 = getARGB(arr,(int)idx0_cl,(int)idx1_fl);

      float x = idx0 - idx0_fl;
      float y = idx1 - idx1_fl;

      s[0]= (int) (s1[0]*(1-x)*(1-y) + s2[0]*(1-x)*y + s3[0]*x*y + s4[0]*x*(1-y));
      s[1]= (int) (s1[1]*(1-x)*(1-y) + s2[1]*(1-x)*y + s3[1]*x*y + s4[1]*x*(1-y));
      s[2]= (int) (s1[2]*(1-x)*(1-y) + s2[2]*(1-x)*y + s3[2]*x*y + s4[2]*x*(1-y));
      s[3]= (int) (s1[3]*(1-x)*(1-y) + s2[3]*(1-x)*y + s3[3]*x*y + s4[3]*x*(1-y));

      endSample = System.currentTimeMillis();
    }

    int [] getARGB(Bitmap buf,int x, int y){

        int rgb = buf.getPixel(y, x); // Returns by default ARGB.
        int [] scalar = new int[4];
        scalar[0] = (rgb >>> 24) & 0xFF;
        scalar[1] = (rgb >>> 16) & 0xFF;
        scalar[2] = (rgb >>> 8) & 0xFF;
        scalar[3] = (rgb >>> 0) & 0xFF;
        return scalar;
    }

    float getRadialX(float x,float y,float cx,float cy,float k){

      x = (x*xscale+xshift);
      y = (y*yscale+yshift);
      float res = x+((x-cx)*k*((x-cx)*(x-cx)+(y-cy)*(y-cy)));
      return res;
    }

    float getRadialY(float x,float y,float cx,float cy,float k){

      x = (x*xscale+xshift);
      y = (y*yscale+yshift);
      float res = y+((y-cy)*k*((x-cx)*(x-cx)+(y-cy)*(y-cy)));
      return res;
    }

    float thresh = 1;

    float calc_shift(float x1,float x2,float cx,float k){

      float x3 = (float)(x1+(x2-x1)*0.5);
      float res1 = x1+((x1-cx)*k*((x1-cx)*(x1-cx)));
      float res3 = x3+((x3-cx)*k*((x3-cx)*(x3-cx)));

      if(res1>-thresh && res1 < thresh)
        return x1;
      if(res3<0){
        return calc_shift(x3,x2,cx,k);
      }
      else{
        return calc_shift(x1,x3,cx,k);
      }
    }



}// end of filters class
\$\endgroup\$
3
\$\begingroup\$

This line will eat a lot of performance:

if( Math.sqrt( Math.pow(i - centerX, 2) + ( Math.pow(j - centerY, 2) ) ) <= 150 )

First for simple squaring, write your own function:

float sqr(float x) { return x*x; }

Second and even more important, if you square the expressions on both sides (which is OK because both are positive), you don't need the expensive sqrt-Function on the left side. Simply write:

if( sqr(i - centerX) + sqr(j - centerY) <= 150*150 )

There are a lot of other little things, e.g.

float x3 = (float)(x1+(x2-x1)*0.5);

...could be...

float x3 = (x1+(x2-x1)*0.5f);

I don't know the details of the algorithm, e.g. if you could use ints in certain places, or if it would make sense to use a precalculated table for some values.

I tried to improve your version. Of course I couldn't test it...

import java.util.Arrays;

class Filters {
    float xscale;
    float yscale;
    float xshift;
    float yshift;
    int[] s = new int[4];
    int[] s1 = new int[4];
    int[] s2 = new int[4];
    int[] s3 = new int[4];
    int[] s4 = new int[4];
    private String TAG = "Filters";
    long getRadXStart = 0;
    long getRadXEnd = 0;
    long startSample = 0;
    long endSample = 0;
    float xr;
    float yr;

    public Filters() {
        //Log.e(TAG, "***********inside filter constructor");
    }

    public Bitmap barrel(Bitmap input, float k) {
        //Log.e(TAG, "***********INSIDE BARREL METHOD ");

        float centerX = input.getWidth() / 2; //center of distortion
        float centerY = input.getHeight() / 2;

        int width = input.getWidth(); //image bounds
        int height = input.getHeight();

        Bitmap dst = Bitmap.createBitmap(width, height, input.getConfig()); //output pic
        // Log.e(TAG, "***********dst bitmap created ");
        xshift = calc_shift(0, centerX - 1, centerX, k);

        float newcenterX = width - centerX;
        float xshift_2 = calc_shift(0, newcenterX - 1, newcenterX, k);

        yshift = calc_shift(0, centerY - 1, centerY, k);

        float newcenterY = height - centerY;
        float yshift_2 = calc_shift(0, newcenterY - 1, newcenterY, k);

        xscale = (width - xshift - xshift_2) / width;
        //  Log.e(TAG, "***********xscale ="+xscale);
        yscale = (height - yshift - yshift_2) / height;
        //  Log.e(TAG, "***********yscale ="+yscale);
        //  Log.e(TAG, "***********filter.barrel() about to loop through bm");


        int origPixel;
        long startLoop = System.currentTimeMillis();
        for (int j = 0; j < dst.getHeight(); j++) {
            for (int i = 0; i < dst.getWidth(); i++) {
                origPixel = input.getPixel(i, j);
                getRadXStart = System.currentTimeMillis();
                getRadialXY(j, i, centerX, centerY, k);
                getRadXEnd = System.currentTimeMillis();

                sampleImage(input, xr, yr);

                int color = ((s[1] & 0x0ff) << 16) | ((s[2] & 0x0ff) << 8) | (s[3] & 0x0ff);
                //            System.out.print(i+" "+j+" \\");

                dst.setPixel(i, j, 
                        (sqr(i - centerX) + sqr(j - centerY) <= 150 * 150) 
                        ? color
                        : origPixel);
            }
        }

        return dst;
    }

    float sqr(float x) {
        return x * x;
    }
    float cube(float x) {
        return x * x * x;
    }

    void sampleImage(Bitmap arr, float idx0, float idx1) {
        startSample = System.currentTimeMillis();
        Arrays.fill(s, 0);
        if (idx0 < 0 || idx1 < 0 || idx0 > (arr.getHeight() - 1) || idx1 > (arr.getWidth() - 1)) {
            return;
        }

        float idx0_fl = (float) Math.floor(idx0);
        float idx0_cl = (float) Math.ceil(idx0);
        float idx1_fl = (float) Math.floor(idx1);
        float idx1_cl = (float) Math.ceil(idx1);

        getARGB(s1, arr, (int) idx0_fl, (int) idx1_fl);
        getARGB(s2, arr, (int) idx0_fl, (int) idx1_cl);
        getARGB(s3, arr, (int) idx0_cl, (int) idx1_cl);
        getARGB(s4, arr, (int) idx0_cl, (int) idx1_fl);

        float x = idx0 - idx0_fl;
        float y = idx1 - idx1_fl;

        //reordered for less multiplications
        for(int i = 0; i < 4; i++) {
           s[i] = (int) (s1[i] + x*(s4[i]-s1[i]) + y *(s2[i]-s1[i] + x*(s1[i]-s2[i]+s3[i]-s4[i])));
        }

        endSample = System.currentTimeMillis();
    }

    void getARGB(int[] scalar, Bitmap buf, int x, int y) {
        int rgb = buf.getPixel(y, x); // Returns by default ARGB.
        scalar[0] = (rgb >>> 24) & 0xFF;
        scalar[1] = (rgb >>> 16) & 0xFF;
        scalar[2] = (rgb >>> 8) & 0xFF;
        scalar[3] = rgb & 0xFF;
    }

    void getRadialXY(float x, float y, float cx, float cy, float k) {
        x = (x * xscale + xshift);
        y = (y * yscale + yshift);
        float f = k * (sqr(x - cx) + sqr(y - cy));
        xr = x + ((x - cx) * f);
        yr = y + ((y - cy) * f);
    }
    float thresh = 1;

    float calc_shift(float x1, float x2, float cx, float k) {

        float x3 = x1 + (x2 - x1) * 0.5f;
        float res1 = x1 + cube(x1 - cx) * k ;

        if (-thresh < res1 && res1 < thresh) {
            return x1;
        }

        float res3 = x3 + cube(x3 - cx) * k;
        return (res3 < 0) 
            ? calc_shift(x3, x2, cx, k)
            : calc_shift(x1, x3, cx, k);
    }
}// end of filters class
\$\endgroup\$
3
  • \$\begingroup\$ Are you shure about sqrt(x^2 + y^2) == sqrt(x) + sqrt(y) ? \$\endgroup\$
    – oberfreak
    Nov 17 '11 at 12:52
  • \$\begingroup\$ Are you sure about sqr == sqrt? \$\endgroup\$
    – Landei
    Nov 17 '11 at 14:00
  • \$\begingroup\$ Sorry, my fault! \$\endgroup\$
    – oberfreak
    Nov 17 '11 at 14:09
2
\$\begingroup\$

You might want to consider working line-at-a-time rather than pixel-at-a-time. Looking at the documentation this would mean calling getPixels and setPixels rather than getPixel/setPixel. Each call to either of these functions must convert the (x, y) coordinates you specify to an offset into the buffer (eg. y * line_length + x), and if you do this for every pixel in a large image these multiplications can add up.

So something like...

int pixels[] = new int[width];

for (int y = 0; y<height; ++y)
{
   input.getPixels(pixels, 0, width, 0, y, width, 1);

   for (int x = 0; x<width; ++x)
   {
      // TODO: make modification on pixels[x]
   }

   dst.setPixels(pixels, 0, width, 0, y, width, 1);
}

Again, I make no guarantees that this will actually be faster, but it's something to try. The last time I messed around with image manipulation (working in C and with by-now-very-old PC hardware) I did notice that the per-line approach was much faster than computing the offset for a coordinate for every pixel.

I also agree with @Landei that x * x is better than pow(x, 2).

\$\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.