Original image | ELSD result |

The preprint of the article published at ECCV2012 A parameterless line segment and elliptical arc
detector with enhanced ellipse fitting. The source code of ELSD can be
found here. Note that a **newer improved version** of the algorithm is available here.

It might be useful to test online our detector, before downloading and
compiling it. A demo where users can upload their images and test ELSD
is available here demo (user: demo, pass: demo).

Check out the result of ELSD
applied on a real video (frame size: 638x360, average execution time
0.7s/frame).

For any questions or remarks, please contact the corresponding author at
vpatrauc at gmail dot com.

**ELSD**

- parameterless Ellipse and Line Segment Detector;
- works with grey-scale images (no edge detector needed);
- grounded on the
*a contrario theory*[1], it controls statistically the number of false positives; extends LSD [2]; - it offers a better precision due to enhanced ellipse fitting.

The main steps of ELSD are:

**1. Hypothesis selection:**- - heuristic, but free of
*critical*parameters in order to avoid false negatives. **2. Validation:**- - parameterless, grounded on
*a contrario*theory; controls the number of false positives. **3. Model selection:**- - parameterless; follows Ockham’s razor principle.

- A. Region grow
- - starting from a seed pixel, gather recursively neighbour pixels with similar gradient orientation.

- B. Curve grow
- - gather recursively neighbour regions that follow a convex, roughly smooth contour.

- C. Fitting:
- - pixels gathered in steps A and B respectively, are used to estimate the line segment and the elliptical hypotheses
- region => rectangle fit => line segment hypothesis;
- curve => circular/elliptical ring fit => circle/ellipse hypothesis.

- - The tangent to the conic in a point
*p*is also the polar of the point_{i}*p*w.r.t. the conic [4]._{i}

- The algebraic distance error and the gradient orientation error can be simultaneously minimised through a non-iterative procedure. This improves the accuracy, especially when pixels are sampled along incomplete circles/ellipses.

- Model of unstructured data:
- - field of gradients whose orientations can be considered i.i.d. random variables => Gaussian white noise image;

- Degree of structuredness:
- - the number of
*σ-aligned*pixels contained in a hypothesis. For a line segment, a pixel is said to be*σ-aligned*if its gradient orientation is orthogonal to the line segment, up to a precision σ (see left figure below). Similarly, for circle/ellipse case, a pixel is*σ-aligned*if its gradient orientation is orthogonal to the tangent to the circle/ellipse in that point (see middle and right figures bellow).

- Validation test:
- - accept as
**meaningful hypotheses**only those too structured to appear by chance in unstructured data. If a hypothesis contains too many aligned points, it is not likely for it to be observed in noise; thus it is meaningful.

The**Number of False Alarms (NFA)**is the essential quantity used to assess the validity of a hypothesis, and is given by:

NFA=*N*⋅Β(*l*,*k*,σ), where

*N*- number of hypotheses (*n*line segments,^{5}*n*circular arcs,^{6}*n*elliptical arcs, for an^{8}*n*x*n*image);

*l*- number of pixels in hypothesis;

*k*- number of aligned pixels in hypothesis;

Β(*l*,*k*,σ) - binomial tail = ∑^{l}_{i=k}C^{l}_{i}σ^{i}(1-σ)^{l-i}.

A hypothesis is considered**meaningful**iif it satisfies the validation test**NFA ≤ ε**.

Ockham's razor principle recommends to

- choose the best geometric interpretation for the data,
- but penalize complexity.

Image size: 445 x 304 pixels, ELSD execution time: 1s | |||

Image size: 640 x 480 pixels, ELSD execution time: 0.4s | |||

Image size: 442 x 450 pixels, ELSD execution time: 0.6s | |||

Image size: 1600 x 1200 pixels, ELSD execution time: 1.3s | |||

Image size: 1600 x 1200 pixels, ELSD execution time: 3.1s | |||

Image size: 612 x 563 pixels, ELSD execution time: 0.1s |

[2] Grompone von Gioi, R., Jakubowicz, J., Morel, J.M., Randall, G.: LSD: A fast line segment detector with a false detection control. PAMI 32, 722-732 (2010)

[3] Pătrăucean, V.: Detection and identification of elliptical structure arrangements in images: Theory and algorithms. PhD thesis. University of Toulouse, France, http://ethesis.inp-toulouse.fr/archive/00001847/

[4] Hartley, R.I., Zisserman, A. : Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press (2004)

[5] Etemadi, A.: Robust segmentation of edge data. In: Int. Conf. on Image Processing and its Applications. 311-314 (1992)