FitCircle circle-fitting class

[Michael Doube]

Hi all

I've been working on a Java port of some MATLAB scripts that fit circles
to data.  I originally started it to find a good method to work out
radii of curvature, and it's grown (since Monday) to be something that
might be useful to other people.

The algorithms are described in detail by Nikolai Chernov on his page,
http://www.math.uab.edu/~chernov/cl/MATLABcircle.html

It includes Chernov's Hyper non-biased algebraic (non iterative, fast
and accurate) circle fitting method and a couple of the geometric methods.

The class is designed to be generic, and I've written an example testing
plugin, here: http://doube.org/files/Test_Circle.java

If you'd like to check it out, I've posted an initial, mostly-working
version at http://doube.org/files/FitCircle.java

It's also in my git repo, http://github.com/mdoube/BoneJ/tree/master.

Cheers,

Mike

[Johan Henriksson-2]

I see that you have one that searches all of (a,b,R). how do these
compare to the classic algorithms based on hough transform?

/Johan

Michael Doube wrote:

> Hi all
>
> I've been working on a Java port of some MATLAB scripts that fit
> circles to data.  I originally started it to find a good method to
> work out radii of curvature, and it's grown (since Monday) to be
> something that might be useful to other people.
>
> The algorithms are described in detail by Nikolai Chernov on his page,
> http://www.math.uab.edu/~chernov/cl/MATLABcircle.html
>
> It includes Chernov's Hyper non-biased algebraic (non iterative, fast
> and accurate) circle fitting method and a couple of the geometric
> methods.
>
> The class is designed to be generic, and I've written an example
> testing plugin, here: http://doube.org/files/Test_Circle.java
>
> If you'd like to check it out, I've posted an initial, mostly-working
> version at http://doube.org/files/FitCircle.java
>
> It's also in my git repo, http://github.com/mdoube/BoneJ/tree/master.
>
> Cheers,
>
> Mike

--
--
------------------------------------------------
Johan Henriksson
MSc Engineering
PhD student, Karolinska Institutet
http://mahogny.areta.org http://www.endrov.net

[Michael Doube]

Hi Johan

 From the practical standpoint rather than than the mathematical
perspective:

the Hough transform finds shapes within data; e.g. you supply an image
and the Hough transform finds the shape (line, circle...) in it - there
is an ImageJ plugin for this here:
http://rsbweb.nih.gov/ij/plugins/hough-circles.html

My FitCircle class finds the single best-fit circle for a set of (x, y)
points.  So if you have n coordinates in a 2D array (double[n][2]; I
have displacement from a mean axis vs axis distance) you can call e.g.
FitCircle.hyperStable(coordinates), which returns the centre and radius
of the best fitting circle.

Chernov has written a huge, detailed manual on the methods which you can
read here: http://www.math.uab.edu/~chernov/cl/book.pdf .  I'm still
suspicious that my Taubin fits are buggy as they break when supplied
with samples from an arc of less than 2*PI radians. So far, the Hyper
fits are doing well in terms of stability and speed.

Mike

Johan Henriksson wrote:

> I see that you have one that searches all of (a,b,R). how do these
> compare to the classic algorithms based on hough transform?
>
> /Johan
>
> Michael Doube wrote:
>> Hi all
>>
>> I've been working on a Java port of some MATLAB scripts that fit
>> circles to data.  I originally started it to find a good method to
>> work out radii of curvature, and it's grown (since Monday) to be
>> something that might be useful to other people.
>>
>> The algorithms are described in detail by Nikolai Chernov on his page,
>> http://www.math.uab.edu/~chernov/cl/MATLABcircle.html
>>
>> It includes Chernov's Hyper non-biased algebraic (non iterative, fast
>> and accurate) circle fitting method and a couple of the geometric
>> methods.
>>
>> The class is designed to be generic, and I've written an example
>> testing plugin, here: http://doube.org/files/Test_Circle.java
>>
>> If you'd like to check it out, I've posted an initial, mostly-working
>> version at http://doube.org/files/FitCircle.java
>>
>> It's also in my git repo, http://github.com/mdoube/BoneJ/tree/master.
>>
>> Cheers,
>>
>> Mike
>
>

[Joachim Wesner]

Hi list,

this all is most interesting! Is there also a robust "L0-norm" algorithm?

To elaborate a bit: L2-norm would be the "usual" approach that minimizes
thes sum of squared error. L1-norm would minimize the sum of absolute error
(and so gives less weight to outliers)
L0-norm would simply count the number of outliers (for real noisy data 0
should not really be zero here, but a small number)

(I know that distinction from a seemingly unrelated field, so-called phase
unrwapping, where a L0-norm really makes sense and is preferred if
possible)

The idea of L->0-norm fit would be that it can fit robustly almost perfect
circles with "breakouts", as what I exactly have. (I also would like to be
able to fit ellipses instead of circles
(due to aspect ratio not exactly one) or even with that main axes not in x
and y)

Any hint highly appreciated!

BTW, I do not really like using any solution based on the Hough-transform,
which I see as a brute-force approach with a shiny new name (My biased
view). Yes, I know that there are now some
"fast" versions, where I do not yet have any experience!

Joachim Wesner



                                                                           
             Michael Doube                                                
             <m.doube@IMPERIAL                                            
             .AC.UK>                                                    An
             Gesendet von:              [hidden email]                
             ImageJ Interest                                         Kopie
             Group                                                        
             <[hidden email].                                       Thema
             GOV>                       Re: FitCircle circle-fitting class
                                                                           
                                                                           
             11.09.2009 11:17                                              
                                                                           
                                                                           
              Bitte antworten                                              
                    an                                                    
              ImageJ Interest                                              
                   Group                                                  
             <[hidden email].                                            
                   GOV>                                                    
                                                                           
                                                                           




Hi Johan

 From the practical standpoint rather than than the mathematical
perspective:

the Hough transform finds shapes within data; e.g. you supply an image
and the Hough transform finds the shape (line, circle...) in it - there
is an ImageJ plugin for this here:
http://rsbweb.nih.gov/ij/plugins/hough-circles.html

My FitCircle class finds the single best-fit circle for a set of (x, y)
points.  So if you have n coordinates in a 2D array (double[n][2]; I
have displacement from a mean axis vs axis distance) you can call e.g.
FitCircle.hyperStable(coordinates), which returns the centre and radius
of the best fitting circle.

Chernov has written a huge, detailed manual on the methods which you can
read here: http://www.math.uab.edu/~chernov/cl/book.pdf .  I'm still
suspicious that my Taubin fits are buggy as they break when supplied
with samples from an arc of less than 2*PI radians. So far, the Hyper
fits are doing well in terms of stability and speed.

Mike

Johan Henriksson wrote:

> I see that you have one that searches all of (a,b,R). how do these
> compare to the classic algorithms based on hough transform?
>
> /Johan
>
> Michael Doube wrote:
>> Hi all
>>
>> I've been working on a Java port of some MATLAB scripts that fit
>> circles to data.  I originally started it to find a good method to
>> work out radii of curvature, and it's grown (since Monday) to be
>> something that might be useful to other people.
>>
>> The algorithms are described in detail by Nikolai Chernov on his page,
>> http://www.math.uab.edu/~chernov/cl/MATLABcircle.html
>>
>> It includes Chernov's Hyper non-biased algebraic (non iterative, fast
>> and accurate) circle fitting method and a couple of the geometric
>> methods.
>>
>> The class is designed to be generic, and I've written an example
>> testing plugin, here: http://doube.org/files/Test_Circle.java
>>
>> If you'd like to check it out, I've posted an initial, mostly-working
>> version at http://doube.org/files/FitCircle.java
>>
>> It's also in my git repo, http://github.com/mdoube/BoneJ/tree/master.
>>
>> Cheers,
>>
>> Mike
>
>

______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________

[David Webster]

Aren't Hough Transforms the only practical way to multiple shape instances,
instances in very noisy data, and occluded shape instances?

David Webster

On Fri, Sep 11, 2009 at 3:06 AM, Joachim Wesner <
[hidden email]> wrote:

> Hi list,
>
> this all is most interesting! Is there also a robust "L0-norm" algorithm?
>
> To elaborate a bit: L2-norm would be the "usual" approach that minimizes
> thes sum of squared error. L1-norm would minimize the sum of absolute error
> (and so gives less weight to outliers)
> L0-norm would simply count the number of outliers (for real noisy data 0
> should not really be zero here, but a small number)
>
> (I know that distinction from a seemingly unrelated field, so-called phase
> unrwapping, where a L0-norm really makes sense and is preferred if
> possible)
>
> The idea of L->0-norm fit would be that it can fit robustly almost perfect
> circles with "breakouts", as what I exactly have. (I also would like to be
> able to fit ellipses instead of circles
> (due to aspect ratio not exactly one) or even with that main axes not in x
> and y)
>
> Any hint highly appreciated!
>
> BTW, I do not really like using any solution based on the Hough-transform,
> which I see as a brute-force approach with a shiny new name (My biased
> view). Yes, I know that there are now some
> "fast" versions, where I do not yet have any experience!
>
> Joachim Wesner
>
>
>
>
>             Michael Doube
>             <m.doube@IMPERIAL
>             .AC.UK <http://ac.uk/>>
>              An
>             Gesendet von:              [hidden email]
>             ImageJ Interest                                         Kopie
>             Group
>             <[hidden email].                                       Thema
>             GOV>                       Re: FitCircle circle-fitting class
>
>
>             11.09.2009 11:17
>
>
>              Bitte antworten
>                    an
>              ImageJ Interest
>                   Group
>             <[hidden email].
>                   GOV>
>
>
>
>
>
>
> Hi Johan
>
>  From the practical standpoint rather than than the mathematical
> perspective:
>
> the Hough transform finds shapes within data; e.g. you supply an image
> and the Hough transform finds the shape (line, circle...) in it - there
> is an ImageJ plugin for this here:
> http://rsbweb.nih.gov/ij/plugins/hough-circles.html
>
> My FitCircle class finds the single best-fit circle for a set of (x, y)
> points.  So if you have n coordinates in a 2D array (double[n][2]; I
> have displacement from a mean axis vs axis distance) you can call e.g.
> FitCircle.hyperStable(coordinates), which returns the centre and radius
> of the best fitting circle.
>
> Chernov has written a huge, detailed manual on the methods which you can
> read here: http://www.math.uab.edu/~chernov/cl/book.pdf .  I'm still
> suspicious that my Taubin fits are buggy as they break when supplied
> with samples from an arc of less than 2*PI radians. So far, the Hyper
> fits are doing well in terms of stability and speed.
>
> Mike
>
> Johan Henriksson wrote:
> > I see that you have one that searches all of (a,b,R). how do these
> > compare to the classic algorithms based on hough transform?
> >
> > /Johan
> >
> > Michael Doube wrote:
> >> Hi all
> >>
> >> I've been working on a Java port of some MATLAB scripts that fit
> >> circles to data.  I originally started it to find a good method to
> >> work out radii of curvature, and it's grown (since Monday) to be
> >> something that might be useful to other people.
> >>
> >> The algorithms are described in detail by Nikolai Chernov on his page,
> >> http://www.math.uab.edu/~chernov/cl/MATLABcircle.html
> >>
> >> It includes Chernov's Hyper non-biased algebraic (non iterative, fast
> >> and accurate) circle fitting method and a couple of the geometric
> >> methods.
> >>
> >> The class is designed to be generic, and I've written an example
> >> testing plugin, here: http://doube.org/files/Test_Circle.java
> >>
> >> If you'd like to check it out, I've posted an initial, mostly-working
> >> version at http://doube.org/files/FitCircle.java
> >>
> >> It's also in my git repo, http://github.com/mdoube/BoneJ/tree/master.
> >>
> >> Cheers,
> >>
> >> Mike
> >
> >
>
>
>
> ______________________________________________________________________
> This email has been scanned by the MessageLabs Email Security System.
> For more information please visit http://www.messagelabs.com/email
> ______________________________________________________________________
>

[Kenneth Sloan]

>>
>>
>> On Sep 11, 2009, at 4:17 , Michael Doube wrote:
>>
>>> Hi Johan
>>>
>>> From the practical standpoint rather than than the mathematical  
>>> perspective:
>>>
>>> the Hough transform finds shapes within data; e.g. you supply an  
>>> image and the Hough transform finds the shape (line, circle...) in  
>>> it - there is an ImageJ plugin for this here: http://rsbweb.nih.gov/ij/plugins/hough-circles.html
>>
>> Strictly speaking, THE Hough transform finds lines.  Other "Hough-
>> like" transforms can be built using the basic ideas of:
>>
>> a) a quantized parameter space
>> b) a voting procedure which turns edge-elements into a set of  
>> parameters
>> c) peak finding in the quantized parameter space.
>>
>> Shapes such as circles and ellipses are relatively easy to put into  
>> this framework, usually involving a paramter space of Translation,  
>> Orientation, and Scale.  Circles don't need Orientation.
>>
>> Arbitrary shapes can be handled by the "Generalized Hough  
>> Transform".  Here, you need a discrete model of the shape, which  
>> can be used to build a table that implements the voting rule (for  
>> each edge-element, which parameter settings might have generated  
>> that edge-element).
>>
>> The Hough transform, the Hough-like transforms, and the Generalized  
>> Hough Transform are 3 distinct concepts.
>>
>>
>>>
>>> My FitCircle class finds the single best-fit circle for a set of  
>>> (x, y) points.  So if you have n coordinates in a 2D array (double
>>> [n][2]; I have displacement from a mean axis vs axis distance) you  
>>> can call e.g. FitCircle.hyperStable(coordinates), which returns  
>>> the centre and radius of the best fitting circle.
>>>
>>> Chernov has written a huge, detailed manual on the methods which  
>>> you can read here:http://www.math.uab.edu/~chernov/cl/book.pdf .  
>>> I'm still suspicious that my Taubin fits are buggy as they break  
>>> when supplied with samples from an arc of less than 2*PI radians.  
>>> So far, the Hyper fits are doing well in terms of stability and  
>>> speed.
>>>>>
>>
>> Here, we see the strength of a Hough-like transform - typically it  
>> can do a superior job of identifying an occluded shape.  
>> Recognizing the correct circle from a small arc of that circle is  
>> easy for a Hough-like circle fitter - but problematic for other  
>> approaches.
>>
>

--
Kenneth  
Sloan                                                                [hidden email]
Computer and Information Sciences                        [phone]
University of Alabama at Birmingham              FAX [phone]
Birmingham, AL 35294-1170                http://www.cis.uab.edu/sloan/