Looking for fast image distortion algorithms

Question

I am trying to implement an application which uses shpere distortion filter. I am using an the algorithm from here which changes pixels location by getPixel() and setpixel() methods. My problem is it is too slow for Android devices and there are applications which implements same sphere(and others) filter way faster than my approach. ( for example Picsay Pro app) Could anyone share or give direction to find or implement fast distortion algorithms.

Actual filter that implements the algorithm:

public boolean sphereFilter(Bitmap b, boolean bSmoothing)
{   
    int nWidth = b.getWidth();
    int nHeight = b.getHeight();

    Point  [][] pt = new Point[nWidth][nHeight];
    Point mid = new Point();
    mid.x = nWidth/2;
    mid.y = nHeight/2;

    double theta, radius;
    double newX, newY;

    for (int x = 0; x < nWidth; ++x)
        for (int y = 0; y < nHeight; ++y)
        {
            pt[x][y]= new Point();
        }

    for (int x = 0; x < nWidth; ++x)
        for (int y = 0; y < nHeight; ++y)
        {
            int trueX = x - mid.x;
            int trueY = y - mid.y;
            theta = Math.atan2((trueY),(trueX));

            radius = Math.sqrt(trueX*trueX + trueY*trueY);

            double newRadius = radius * radius/(Math.max(mid.x, mid.y));

            newX = mid.x + (newRadius * Math.cos(theta));

            if (newX > 0 && newX < nWidth)
            {
                pt[x][y].x = (int) newX;
            }
            else
            {
                pt[x][y].x = 0;
                pt[x][y].y = 0;
            }

            newY = mid.y + (newRadius * Math.sin(theta));

            if (newY > 0 && newY < nHeight && newX > 0 && newX < nWidth)
            {                   
                pt[x][ y].y = (int) newY;
            }
            else
            {
                pt[x][y].x = pt[x][y].y = 0;
            }
        }
    offsetFilterAbs(b, pt);
    return true;
}

The code that replaces the calculated pixels' positions.

public boolean offsetFilterAbs(Bitmap b, Point[][] offset )
{
        int nWidth = b.getWidth();
        int nHeight = b.getHeight();

        int xOffset, yOffset;

        for(int y=0;y < nHeight;++y)
        {
            for(int x=0; x < nWidth; ++x )
            {   
                xOffset = offset[x][y].x;
                yOffset = offset[x][y].y;

                if (yOffset >= 0 && yOffset < nHeight && xOffset >= 0 && xOffset < nWidth)
                {
                    b.setPixel(x, y, b.getPixel(xOffset, yOffset));
                }                   
            }               
        }

    return true;
}

Iowa

possible duplicate of Image Warping - Bulge Effect Algorithm – Inessential

Yes, it's pretty much a duplicate, but note that the accepted answer to that question is not really the one you want here -- what you want is the GLSL shader. – Bellabelladonna

@BlueRaja, I am currently using same algorithm with the one on your link already and it is still too slow for android devices – Iowa

@Iowa Please edit your question. The sentence ". I am using an the algorithm from here " is incomplete ... Where is "here"? – Jayson

@Jerry: Both of those answers are equivalent – Inessential

@BlueRaja: They're equivalent mathematically, but given his mention of speed, he undoubtedly wants to use the shader. – Bellabelladonna

@ belisarius you are right, sorry about that. I have added the code that i have ported from codeproject link. – Iowa

Answer 1

I am currently using same algorithm with the one on your link already and it is still too slow for android devices

From my link in the comments above:

Given
r = Sqrt((x - 0.5)^2 + (y - 0.5)^2)
a = ArcTan2(y - 0.5, x - 0.5)
n = Bulge factor (default = 1)

Set
x' = r^n * Cos(a) + 0.5 
y' = r^n * Sin(a) + 0.5 

(Remember that, in this equation, x and y span from 0 to 1. If your dimensions span from 0 to w, replace 0.5 with w/2)

Using a bit of math, we can see that

Cos(a) = Cos(ArcTan2(y - 0.5, x - 0.5))
       = (x - 0.5)/r
Sin(a) = Sin(ArcTan2(y - 0.5, x - 0.5))
       = (y - 0.5)/r

This makes the final resulting equation

r = (x - 0.5)^2 + (y - 0.5)^2
n = Bulge factor (default = 0)

Set
x' = r^n * (x - 0.5) + 0.5
y' = r^n * (y - 0.5) + 0.5

(I removed the square-root since we take the result to a real-power anyways... so really to make this equivalent we should use n/2 instead of n, but since we are defining "bulge-factor," we can just leave out the extra division)

With only a handful of multiplications and a single real-exponentiation, this is probably the fastest you can hope to get.

Inessential

+1 I'm not going to answer this one because my Android-fu is nil. But perhaps the OP should try some basic profiling on his code and see which ones are the dominant time consumers. Or perhaps the elimination of the superfluous trig ops is enough. – Jayson

@ belisarius i have tried profiling my code and both functions(calculating the new x,y positions and replacing them) takes about 2000ms for each which is too poor compared to "Picsay Pro". – Iowa

@Iowa Picsay Pro probably does this using OpenGL... and without creating thousands of unnecessary Point objects. – Inessential

You are right about Point objects, in my defence i just ported the code from original link. – Iowa