RandomizedHoughEllipseDetector

KO | EN

gitlite — search

#python #java #python3 #arduino #golang #machine-learning #rust #html #flask #javascript #seismology #nodejs

RandomizedHoughEllipseDetector

★ 17 Open GitHub ↗

find ellipse

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Randomized-Hough-Ellipse-Detector

Implementation of Randomized Hough Ellipse Transform. This repository refers to the publication [1].  
Multithreading version: [RHET](https://github.com/Po-Ting-lin/RandomizedHoughEllipse "Title")

### 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

![](https://raw.githubusercontent.com/Po-Ting-lin/RandomizedHoughEllipseDetector/master/image/findinghough.png)

### 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

![](https://raw.githubusercontent.com/Po-Ting-lin/RandomizedHoughEllipseDetector/master/image/hough.png)

### 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

![](https://raw.githubusercontent.com/Po-Ting-lin/RandomizedHoughEllipseDetector/master/image/Rhough.png)

RandomizedHoughEllipseDetector

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README