Contribution: circles and hough transform

280 views

François

Jan 9, 2013, 11:01:13 AM1/9/13
Hi,

On my spare time, I work on a code to implement a hough transform to detect circles. This is not implemented yet in skimage.
Is Skimage interested in this implementation? (I don't want to spend much more time to polish the code if there is no need)
If the answer is positive, it can be done in two steps:
* add a method to draw circles. The current "circle" method is for disks. We need circles (very easy to write). This is already done, but in pure python. I saw that drawing methods are implemented in cython. I have never used cython before, but it must be easy (I guess). I implemented two methods (Bresenham or midpoint circle and Andres), both are useful I think.
* write the hough algorithm for circle. Done for a Quick and dirty usage, but it's not suitable yet for integration (not safe).

I would prefer to send one patch per step. Even if I already tackled bugs in some projects, I never done this kind of contribution before ;)

François.

Stéfan van der Walt

Jan 9, 2013, 11:05:53 AM1/9/13
Hi François

On Wed, Jan 9, 2013 at 11:01 PM, François <francois...@gmail.com> wrote:
> Is Skimage interested in this implementation? (I don't want to spend much
> more time to polish the code if there is no need)

Definitely! I've also been thinking about a more general hough
transform that uses the Ax + By + Cxy + D definition of certain
curves, but never got around to it (there's an earlier mail about it
on the list).

> If the answer is positive, it can be done in two steps:
> * add a method to draw circles. The current "circle" method is for disks. We
> need circles (very easy to write). This is already done, but in pure python.
> I saw that drawing methods are implemented in cython. I have never used
> cython before, but it must be easy (I guess). I implemented two methods
> (Bresenham or midpoint circle and Andres), both are useful I think.
> * write the hough algorithm for circle. Done for a Quick and dirty usage,
> but it's not suitable yet for integration (not safe).

Both patches would be very welcome! Let us know if you need any help
getting started.

Regards
Stéfan

Jérôme Kieffer

Jan 9, 2013, 1:40:22 PM1/9/13
On Wed, 9 Jan 2013 08:01:13 -0800 (PST)
François <francois...@gmail.com> wrote:

> Is Skimage interested in this implementation? (I don't want to spend much
> more time to polish the code if there is no need)

Yes I am personally interested for my research...

> If the answer is positive, it can be done in two steps:
> * add a method to draw circles. The current "circle" method is for disks.
> We need circles (very easy to write).

Yes I am working only on circles (and other conics but this is another story).

Cheers,

--

François

Jan 12, 2013, 5:54:07 AM1/12/13

Le mercredi 9 janvier 2013 17:05:53 UTC+1, Stefan van der Walt a écrit :

Both patches would be very welcome!  Let us know if you need any help
getting started.

Thank. I discovered in master circle_perimeter(). This is actually the bresenham method. This PR is for Andres method.
https://github.com/scikit-image/scikit-image/pull/410

Since bresenham in already in master, I'm working on the hough transform. :)

François.

François

Feb 3, 2013, 2:03:59 PM2/3/13
Hi,

I have written the hough transform for circles in python and  have a good basis for peak detection.

I have few questions:
1/ in skimage/transform/hough_transform.py
Cython version of hough() is imported like this (below the python version)
59 # try to import and use the faster Cython version if it exists
60 try:
61     from ._hough_transform import _hough
62 except ImportError:
63     pass

Should I do the same for hough_circle()? or just implement the cython version?
I don't see why cython would not be available...

2/ For disambiguation, I suggest to rename hough to hough_line(). The same for peak detection.
Any comment on that?

Cheers,
François.

Stéfan van der Walt

Feb 3, 2013, 2:11:31 PM2/3/13
to scikit-image

Hi François

Yes, you may rely on Cython, so no need to code a pure Python version.

Renaming the function as suggested would break backward compatibility, so I suggest adding hough_line as an alias, and deprecating hough over two releases.

Regards
Stéfan

--
You received this message because you are subscribed to the Google Groups "scikit-image" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.

Stéfan van der Walt

Feb 3, 2013, 2:17:15 PM2/3/13
to scikit-image

Anders Klint

Feb 18, 2013, 5:48:14 AM2/18/13
Hi,

Any hopes of this making it into the 0.8 release?

Regards,
/Anders

Stéfan van der Walt

Feb 18, 2013, 6:20:02 AM2/18/13
On Mon, Feb 18, 2013 at 12:48 PM, Anders Klint <anders....@gmail.com> wrote:
> Any hopes of this making it into the 0.8 release?

Currently, that PR still lacks a gallery example, and there are some
can include it in the release.

Stéfan

François

Mar 6, 2013, 3:57:44 PM3/6/13
Hi,

FYI, I plan to work on the detection of ellipses quite soon. Stefan indicated to me a reference which seems fairly simple to implement.

Cheers,
François.

Austin Chungath

Jun 17, 2014, 2:28:04 PM6/17/14
Hi François,

I am trying out the ellipse hough transform as described in the following link:

The ellipse detection in the example takes about 15 seconds to give a result.

1. Is it possible to get the time taken for ellipse detection to under a second?
2. Are there any suggestions for improving the execution time?

Thanks,
Austin

François Boulogne

Jun 17, 2014, 5:29:41 PM6/17/14

> 1. Is it possible to get the time taken for ellipse detection to under
> a second?
> 2. Are there any suggestions for improving the execution time?
>
>
It's coded in cython, so it's pretty optimized and Johannes helped me on
that. I think it's pretty well optimized.

You are trying to find a point is a space with 5 dimensions, so it takes
times.
The time directly depends on the number of (let's say black) points in
your binary image. If you have a lot of points, you may try to reduce
the quantity. I never tried so far, but it probably works if you take
randomly a fraction of all your points. The peak in the 5D space will be
smaller and perhaps wider, but depending on the fraction, you may find a
compromise.

Best,

--
François Boulogne.
http://www.sciunto.org
GPG fingerprint: 25F6 C971 4875 A6C1 EDD1 75C8 1AA7 216E 32D5 F22F

Austin Chungath

Jun 18, 2014, 8:34:59 AM6/18/14
I will give a shot at random fraction of all points but I have a feeling that it's not going to get it under one second.
It makes sense why it's taking so much time.

Regards,
Austin

--
You received this message because you are subscribed to a topic in the Google Groups "scikit-image" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/scikit-image/yh_bI0hNIL8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to scikit-image...@googlegroups.com.