Randomized-Hough-Ellipse-Detector

Implementation of Randomized Hough Ellipse Transform. This repository refers to the publication [1].
Multithreading version: RHET

Reference

[1]. Inverso, Samuel. "Ellipse detection using randomized Hough transform." 
     Final Project: introduction to computer vision (2002): 4005-4757.

Canny edge detecor

• Noise reduction
• Gradient calculation
• Non-maximum suppression
• Double threshold

Randomly pick three points

Use random.sample() to select three points; then, find the parameter of ellipse as a candidate by these points.

Determining Ellipse Center(p, q)

• Determine the equation of the line for each point where the line’s slope is the gradient at the point.
• Determine the intersection of the tangents passing throughpoint pairs (X1,X2) and (X2,X3).
• Calculate the bisector of the tangent intersection points. Thisis a line from the tangent’s intersection,t, to the midpoint of the twopoints,m.
• Find the bisectors intersection to give the ellipse’s center,O

Determining semimajor (a) and semiminor axis’ (b) )

• Shift the ellipse to origin. (Shift center (p, q) to (0, 0))
• Solve ellipse equation with the three points

Verifying the Ellipse Exists in the Image

• The sign of 4AC−B^2 determines the type of conic section:

1. positive --> Ellipse or Circle
2. zero --> Parabola
3. negative --> Hyperbola

• ellipse out of image

Constraint

• semi major axis bound
• semi minor axis bound
• flattening bound (customized)
• nucleus-cell ratio bound (customized)

Accumulating

• voting
• select the best result

Comparison with the original Hough ellipse transform

skimage.transform hough_ellipse

n = 337, time = 2.67 sec
n = 439, time = 5.1 sec
n = 644, time = 15.3 sec

randomized hough ellipse detector

time complexity: linear
n = 337, time = 0.7 sec
n = 439, time = 1.1 sec
n = 644, time = 1.5 sec