Return to Question

1. Store all edge-pixels (pixels in black) in an array
2. clear the accumulator-array (you'll see the use of it later)
3. Loop through each array-entry in the "edge-pixels-array"
4. Loop through each array-entry again, check if the distance between the two coordinates (from step 3+4) is in between the min-radius and max-radius of my ellipse (min-radius and max-radius are just function parameters)

If this is true, then proceed with steps 5-14. 5. Calculate the center, orientation and the assumed length of the major axis (you can see the equations on the paper, but I don't think that they are necessary) 6. Loop through each array-entry a third time, check if the distance between this coordinate and the assumed center of the point is between the min-radius and the max-radius. It this is true, then proceed with steps 7.-9. 7. Calculate the length of minor axis using equations (if you need to look them up on the paper) 8. Add the assumed parameters of the ellipse to the accumulator-array (center, x-Width, y-Width, orientation) 9. Wait for the inner (3.) for loop to finish 10. Average all values in the accumulator-array to find the average parameters for the investigated ellipse 11. Save the average ellipse parameters 12. Remove the pixels within the detected ellipse (so you don't check the pixels twice...) 13. Clear accumulator-array 14. Wait for the outer two for loops to finish 15. Output the found ellipses

1. Store all edge-pixels (pixels in black) in an array

2. clear the accumulator-array (you'll see the use of it later)

3. Loop through each array-entry in the "edge-pixels-array"

4. Loop through each array-entry again, check if the distance between the two coordinates (from step 3+4) is in between the min-radius and max-radius of my ellipse (min-radius and max-radius are just function parameters)

   If this is true, then proceed with steps 5-14.

5. Calculate the center, orientation and the assumed length of the major axis (you can see the equations on the paper, but I don't think that they are necessary)

6. Loop through each array-entry a third time, check if the distance between this coordinate and the assumed center of the point is between the min-radius and the max-radius. It this is true, then proceed with steps 7.-9.

7. Calculate the length of minor axis using equations (if you need to look them up on the paper)

8. Add the assumed parameters of the ellipse to the accumulator-array (center, x-Width, y-Width, orientation)

9. Wait for the inner (3.) for loop to finish

10. Average all values in the accumulator-array to find the average parameters for the investigated ellipse

11. Save the average ellipse parameters

12. Remove the pixels within the detected ellipse (so you don't check the pixels twice...)

13. Clear accumulator-array

14. Wait for the outer two for loops to finish

15. Output the found ellipses

Note firsts:
The problem will take more then 2 minutes, so if you don't have much time I wouldn't recommend you to deal with the problem.

I found this paper on how to program "a new efficient ellipse detection method", so I thought why not just try it.
I programmed it in Python but my implementation is - in contrast to the title of the paper - really slow and needs for an 325x325 image (with 6000 black pixels), like this one here, with multiple circles/ellipses on the order of 30 minutes...

So I would please you to read through my code and tell me, where I can optimize things (and I think, that there are a lot of things to optimize)

First I think, that I'll briefly explain the 15 steps, which are listed in the paper, because I can understand, that no one wants to read the complete paper... (If I explained one step unclear then just take a quick look at the paper please):

The Steps: (how I understood them)

1. Store all edge-pixels (pixels in black) in an array
2. clear the accumulator-array (you'll see the use of it later)
3. Loop through each array-entry in the "edge-pixels-array"
4. Loop through each array-entry again, check if the distance between the two coordinates (from step 3+4) is in between the min-radius and max-radius of my ellipse (min-radius and max-radius are just function parameters)
   If this is true, then proceed with steps 5-14
5. Calculate the center, orientation and the assumed length of the major axis (you can see the equations on the paper, but I don't think, that they are necessary)
6. Loop through each array-entry a third time, check if the distance between this coordinate and the assumed center of the point is between the min-radius and the max-radius. It this is true, then proceed with Steps 7.-9.
7. Calculate the length of minor axis using equations (if you need to look them up on the paper)
8. Add the assumed parameters of the ellipse to the accumulator-array (center, x-Width, y-Width, orientation)
9. Wait for the inner (3.) for-loop to finish
10. Average all values in the accumulator-array to find the average parameters for the investigated ellipse
11. Save the average ellipse parameters
12. Remove the pixels within the detected ellipse (so you don't check the pixels twice...)
13. Clear accumulator-Array
14. Wait for the outer two for-loops to finish
15. Output the found ellipses

And here is my implementation with Python:

I would be glad, if someone could help me speedin' up the process because it takes really, really, really, really long.. :D

Edit 2:

Here is a Profile of the program, most time is spent in pow2(simply multiplies 2 values) and math.sqrt..

65082750 function calls (65080245 primitive calls) in 22.924 seconds  
Ordered by: internal time

ncalls      tottime  percall  cumtime  percall filename:lineno(function)  
1           17.666   17.666   22.724   22.724  ElipseDetection.py:16(detectEllipses)  
34239900    2.410    0.000    2.410    0.000   ElipseDetection.py:162(pow2)  
15660662    1.806    0.000    1.806    0.000   {built-in method math.sqrt}  
14612430/14612383    0.699    0.000    0.699   0.000 {built-in method builtins.len}  
488000      0.062    0.000    0.062    0.000     {method 'append' of 'list' objects}

The problem will take more than 2 minutes, so if you don't have much time I wouldn't recommend you to deal with the problem.

I found this paper on how to program "a new efficient ellipse detection method", so I thought why not just try it. I programmed it in Python but my implementation is - in contrast to the title of the paper - really slow and needs for an 325x325 image (with 6000 black pixels), like this one here, with multiple circles/ellipses on the order of 30 minutes...

Please read through my code and tell me where I can optimize things (and I think, that there are a lot of things to optimize).

I'll briefly explain the 15 steps, which are listed in the paper (if I explained one step unclear then just take a quick look at the paper):

The steps: (how I understood them)

1. Store all edge-pixels (pixels in black) in an array
2. clear the accumulator-array (you'll see the use of it later)
3. Loop through each array-entry in the "edge-pixels-array"
4. Loop through each array-entry again, check if the distance between the two coordinates (from step 3+4) is in between the min-radius and max-radius of my ellipse (min-radius and max-radius are just function parameters)

If this is true, then proceed with steps 5-14. 5. Calculate the center, orientation and the assumed length of the major axis (you can see the equations on the paper, but I don't think that they are necessary) 6. Loop through each array-entry a third time, check if the distance between this coordinate and the assumed center of the point is between the min-radius and the max-radius. It this is true, then proceed with steps 7.-9. 7. Calculate the length of minor axis using equations (if you need to look them up on the paper) 8. Add the assumed parameters of the ellipse to the accumulator-array (center, x-Width, y-Width, orientation) 9. Wait for the inner (3.) for loop to finish 10. Average all values in the accumulator-array to find the average parameters for the investigated ellipse 11. Save the average ellipse parameters 12. Remove the pixels within the detected ellipse (so you don't check the pixels twice...) 13. Clear accumulator-array 14. Wait for the outer two for loops to finish 15. Output the found ellipses

I would be glad if someone could help me speed up the process because it takes a really long time.

Here is a Profile of the program, with most time is spent in pow2  (simply multiplies 2 values) and math.sqrt:

65082750 function calls (65080245 primitive calls) in 22.924 seconds  
Ordered by: internal time

ncalls      tottime  percall  cumtime  percall filename:lineno(function)  
1           17.666   17.666   22.724   22.724  ElipseDetection.py:16(detectEllipses)  
34239900    2.410    0.000    2.410    0.000   ElipseDetection.py:162(pow2)  
15660662    1.806    0.000    1.806    0.000   {built-in method math.sqrt}  
14612430/14612383    0.699    0.000    0.699   0.000 {built-in method builtins.len}  
488000      0.062    0.000    0.062    0.000     {method 'append' of 'list' objects}

Edit 2:

Here is a Profile of the program, most time is spent in pow2(simply multiplies 2 values) and math.sqrt..

65082750 function calls (65080245 primitive calls) in 22.924 seconds  
Ordered by: internal time

ncalls      tottime  percall  cumtime  percall filename:lineno(function)  
1           17.666   17.666   22.724   22.724  ElipseDetection.py:16(detectEllipses)  
34239900    2.410    0.000    2.410    0.000   ElipseDetection.py:162(pow2)  
15660662    1.806    0.000    1.806    0.000   {built-in method math.sqrt}  
14612430/14612383    0.699    0.000    0.699   0.000 {built-in method builtins.len}  
488000      0.062    0.000    0.062    0.000     {method 'append' of 'list' objects}