0

I have an array with 600x600 integer values. The values represents a circle. For example: 0 is outside, >=1 is inside the circle. Here is a short example:

0000110000000
0001111000000
0011111200000
0112112110000
1111111111000
0111411110000
0011131100000
0000110000000
0000000000000
0000000000000

The position and the size of the circle in the array differs. Now, I am looking for a fast algorithm to find the center and the radius of the circle. Fast because I have to process many arrays.

LU RD
  • 34,438
  • 5
  • 88
  • 296
Klaus.Meier
  • 57
  • 5
  • The example you gave doesn't have a middle or a radius in normal terms, – Paul Michael Nov 22 '16 at 10:39
  • See [Midpoint circle algorithm](https://en.wikipedia.org/wiki/Midpoint_circle_algorithm#Optimization). – LU RD Nov 22 '16 at 10:43
  • You need to address what you mean by middle and radius first before you start looking for an algorithm. As it depends if you want to have an integer or a double as the values for center and radius. How you deal with fractions and how much fuzziness you allow etc. There are several algorithms that do this but all of them come with assumptions. – Paul Michael Nov 22 '16 at 10:49
  • 2
    You could use the [Circle Hough Transform](https://en.wikipedia.org/wiki/Circle_Hough_Transform). – LU RD Nov 22 '16 at 12:23
  • Agreed with @LURD - if this is a fuzzy problem then the hough circle transform is probably the best answer. It is implemented in OpenCV, which saves a lot of work. – J... Nov 22 '16 at 12:36
  • Thank you. I will hve a look at OpenCV – Klaus.Meier Nov 22 '16 at 16:23
  • See : [How to detect simple geometric shapes using OpenCV](http://stackoverflow.com/q/11424002/327083) – J... Nov 22 '16 at 18:47
  • And the port : https://github.com/Laex/Delphi-OpenCV – J... Nov 22 '16 at 18:49

2 Answers2

1

Superimpose a grid, walk it, (small matrices: every row and column, large matrices every Xth row and column) and find the points where the change (0 -> >=1 or vice versa) happens.

If your grid is symetrical and dense enough, the average of these points is equal to the center.

The average distance ( sqrt(sqr(x-xm)+sqr(y-ym))) of the found points and the center is a measure for the radius.

Walking rows alone might be enough for larger datasets, and you scan only Xth line. If you work with real images, you might have to cater for noise, and variations in brightness.

Marco van de Voort
  • 25,628
  • 5
  • 56
  • 89
0

It is possible to do it faster. Actually according to your sample it does not matter (and we must not estimate) if there is a circle or a square.

Assuming that there is a two-dimention 0-based array the radius will be simply the the count of non-zero (not empty) rows (or columns) divided by 2.

Algo.

  1. Find the number of the non-zero rows and their first (top) index. Divide this number by two and add the number of zero rows with indexes less then the lowest non-zero row. Now you know the radius and y coordinate.

  2. Find the first(left) non-zero column and add the radius to its index. Now you have the x coordinate.

In the provided example.

  1. The number of non-zero rows is 8. The radius is 8 / 2 = 4. There are 0 rows to the top before the non-zero rows (in other words the ID of the first non-zero row is 0). So the y coordinate is 0 + 4 = 4.
  2. There are 0 empty columns to the left from the first non-zero column (or the ID of the first non-zero column is 0). The x coordinate will be 4 + 0 = 4.

To know if the column is zero you can use some function like this:

IsEmpty := true;
for i := 0 to High(Column) do
if Column[i] > 0 then
  begin
    IsEmpty := false;
    Break;
  end;
asd-tm
  • 3,381
  • 2
  • 24
  • 41
  • Scanning rows, then columns is two passes. a (slightly less since you probably abort on non zero). – Marco van de Voort Nov 23 '16 at 15:58
  • @MarcovandeVoort You do not scan all the rows and all the columns. You scan only the rows until the first emplty row after non-zero is found and you scan columns only until the first non-zero row is found. I mean you break the primary (external) loop (not shown in my answer) when the necessary row or colum is found. In the given example there will be only 9 rows scan with (5;4;3;2;1;2;3;5;13) iterations and 1 column scan with 5 iterations. That will give us 43 iterations of comparison operations only. Is that too much? So actually this algo gives less then 1 pass in the given array. – asd-tm Nov 24 '16 at 06:16