2

I have created a method which performs a sobel edge detection. I use the Camera yuv byte array to perform the detection on. Now my problem is that I only get 5fps or something, which is really low. I know it can be done faster because there are other apps on the market who are able to do it at good fps on good quality. I pass images in a 800x400 resolution. Can anyone check if my algorithm can be made shorter or more performant? I already put the algorithm in native code but there seems to be no difference in fps.

public void process() { progress=0; index = 0; // calculate size // pixel index size = width*(height-2) - 2; // pixel loop while (size>0) { // get Y matrix values from YUV ay = input[index]; by = input[index+1]; cy = input[index+2]; gy = input[index+doubleWidth]; hy = input[index+doubleWidth+1]; iy = input[index+doubleWidth+2]; // get X matrix values from YUV ax = input[index]; cx = input[index+2]; dx = input[index+width]; fx = input[index+width+2]; gx = input[index+doubleWidth]; ix = input[index+doubleWidth+2]; // 1 2 1 // 0 0 0 // -1 -2 -1 sumy = ay + (by*2) + cy - gy - (2*hy) - iy; // -1 0 1 // -2 0 2 // -1 0 1 sumx = -ax + cx -(2*dx) + (2*fx) - gx + ix; total[index] = (int) Math.sqrt(sumx*sumx+sumy*sumy); // Math.atan2(sumx,sumy); if(max < total[index]) max = total[index]; // sum = - a -(2*b) - c + g + (2*h) + i; if (total[index] <0) total[index] = 0; // clamp to 255 if (total[index] >255) total[index] = 0; sum = (int) (total[index]); output[index] = 0xff000000 | (sum << 16) | (sum << 8) | sum; size--; // next index++; } //ratio = max/255; }

Thx in Advance ! greetings

Improve this question

2 Answers 2

Reset to default
2

So I have two things:

  1. I would consider loosing the Math.sqrt() expression: If you are only interested in edge detection, I see no need for the this, as the sqrt function is monotonic and it is really costly to calculate.
  2. I would consider another algorithm, especially I have had good results with a seperated convolution-filter: http://www.songho.ca/dsp/convolution/convolution.html#separable_convolution as this might bring down the number of arithmetic floating-point operations (which is probably your bottleneck).

I hope this helps, or at least sparks some inspiration. Good luck.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2
  • If you are using your algorithm in real-time, call it less often, maybe every ~20 frames instead of every frame.
  • Do more work per iteration, 800x400 in your algorithm is 318,398 iterations. Each iteration is pulling from the input array in a (to the processor) random way which causes issues with caching. Try pulling ay, ay2, by, by2, cy, cy2 and do twice the calculations per loop, you'll notice that the variables in the next iteration will relate to the previous. ay is now ay2 etc...

Here's a rewrite of your algo, doing twice the work per iteration. It saves a bit in redundant memory access, and ignores square root mentioned in another answer.

public void process() { progress=0; index = 0; // calculate size // pixel index size = width*(height-2) - 2; // do FIRST iteration outside of loop // grab input avoid redundant memory accesses ay = ax = input[index]; by = ay2 = ax2 = input[index+1]; cy = by2 = cx = input[index+2]; cy2 = cx2 = input[index+3]; gy = gx = input[index+doubleWidth]; hy = gy2 = gx2 = input[index+doubleWidth+1]; iy = hy2 = ix = input[index+doubleWidth+2]; iy2 = ix2 = input[index+doubleWidth+3]; dx = input[index+width]; dx2 = input[index+width+1]; fx = input[index+width+2]; fx2 = input[index+width+3]; // sumy = ay + (by*2) + cy - gy - (2*hy) - iy; sumy2 = ay2 + (by2*2) + cy2 - gy2 - (2*hy2) - iy2; sumx = -ax + cx -(2*dx) + (2*fx) - gx + ix; sumx2 = -ax2 + cx2 -(2*dx2) + (2*fx2) - gx2 + ix2; // ignore the square root total[index] = fastSqrt(sumx*sumx+sumy*sumy); total[index+1] = fastSqrt(sumx2*sumx2+sumy2*sumy2); max = Math.max(max, Math.max(total[index], total[index+1])); // skip the test for negative value it can never happen if(total[index] > 255) total[index] = 0; if(total[index+1] > 255) total[index+1] = 0; sum = (int) (total[index]); sum2 = (int) (total[index+1]); output[index] = 0xff000000 | (sum << 16) | (sum << 8) | sum; output[index+1] = 0xff000000 | (sum2 << 16) | (sum2 << 8) | sum2; size -= 2; index += 2; while (size>0) { // grab input avoid redundant memory accesses ay = ax = cy; by = ay2 = ax2 = cy2; cy = by2 = cs = input[index+2]; cy2 = cx2 = input[index+3]; gy = gx = iy; hy = gy2 = gx2 = iy2; iy = hy2 = ix = input[index+doubleWidth+2]; iy2 = ix2 = input[index+doubleWidth+3]; dx = fx; dx2 = fx2; fx = input[index+width+2]; fx2 = input[index+width+3]; // sumy = ay + (by*2) + cy - gy - (2*hy) - iy; sumy2 = ay2 + (by2*2) + cy2 - gy2 - (2*hy2) - iy2; sumx = -ax + cx -(2*dx) + (2*fx) - gx + ix; sumx2 = -ax2 + cx2 -(2*dx2) + (2*fx2) - gx2 + ix2; // ignore the square root total[index] = fastSqrt(sumx*sumx+sumy*sumy); total[index+1] = fastSqrt(sumx2*sumx2+sumy2*sumy2); max = Math.max(max, Math.max(total[index], total[index+1])); // skip the test for negative value it can never happen if(total[index] >= 65536) total[index] = 0; if(total[index+1] >= 65536) total[index+1] = 0; sum = (int) (total[index]); sum2 = (int) (total[index+1]); output[index] = 0xff000000 | (sum << 16) | (sum << 8) | sum; output[index+1] = 0xff000000 | (sum2 << 16) | (sum2 << 8) | sum2; size -= 2; index += 2; } } // some faster integer only implementation of square root. public static int fastSqrt(int x) { }

Please note, the above code was not tested, it was written inside the browser window and may contain syntax errors.

EDIT You could try using a fast integer only square root function to avoid the Math.sqrt. http://atoms.alife.co.uk/sqrt/index.html

Improve this answer

4 Comments

THX ALOT LastCoder. Never thought about assigning more data per loop at once, that IS the key to performance here. Its running 3 fps faster now. I readded the Sqrt method because it gives me the nice Sobel Effect. It's also on wikipedia. I don't know how else I can recreate the sobel effect without using the Sqrt function
@user1083398 - try a fast java integer only square root implementation, you may find it to be ~3x faster than Math.sqrt. You might also want to consider multi-threading if your hardware supports multiple cores you could run the loop on two threads each processing half of the image.
"If you are using your algorithm in real-time, call it less often, maybe every ~20 frames instead of every frame." Wouldn't I be getting 20 frames the same image then if I only decode once every 20 frames?
@user1083398 - I was thinking you could use the edge finding image as an overlay on top of the real image, and you'd only update that overlay every ~20 frames. Since I don't know exactly what your doing I can only speak hypothetically...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.