orem to find the center (p, q) of the ellipse using only 3 
points by estimation of tangents at each point. It allows a 
linear estimation of ellipse using only 3 points. 
4.1.1 Ellipse from three points Given 3 points Pi, P 2 , 
P 3 on an ellipse (see Figure 3) the center is computed as 
follows: 
• Tangents at these 3 points (U, t2, ¿3) are found. 
• Intersections of t\ with ¿2 (h) and ¿2 with ¿3 (h) are 
computed. 
• Midpoints of the segments [P1P2] and [P2P3} (Mi 
and M2) are found. 
• The intersection of the segments [/jMi] and [I2M2] 
gives the ellipse center (C). 
Figure 3: Use of Pascal’s theorem for estimating ellipse 
center with 3 points. 
When the center coordinates (p, q) are obtained the coordi 
nate system is shifted such as (p, q) become origin. Then, 
the Equation 3 can be applied to estimate the ellipse equa 
tion using 3 points. 
ax 2 + 2 bxy + cy 2 = 1 (3) 
4.1.2 Ellipse estimation with RANSAC In the previ 
ous section the ellipse estimation method was explained 
when we have three points on the ellipse. The problem is 
to obtain three points belonging to the ellipse within the 
noise (see Figure 4(a)). We used a RANSAC algorithm 
(Fischler and Bolles, 1981). It is composed of six steps: 
1. Pick randomly three points within the edges points. 
2. Estimate the ellipse parameters (see Section 4.1.1). 
3. Search how many edge points fit on the ellipse model 
(number of support points). 
4. If the number of support point is sufficiently great, we 
accept the model and exit the loop with success. We 
assume that the number of support point is sufficient 
when it is higher than a percentage of the estimated 
theoretical ellipse circumference. 
5. Repeat the steps 1 to 4, n times. 
6. If we arrive to this step, we declare a failure and there 
is no ellipse found. 
Suppose that the density ratio of inlier is 50% and the prob 
ability that the algorithm exit without finding a good fit is 
chosen 5%, then, the number of needed iterations (n) is 25. 
In ellipse estimation, in order to compute the needed tan 
gent on each edge point, a line is fitted to its neighbours 
on the linked edges. A neighborhood of 2 pixels is cho 
sen. Due to discretisation, it does not provide a good tan 
gent estimation when using pixel accuracy. This problem 
is shown in Figures 4(b) and 4(c). It causes more frequent 
failure and less accurate result. In order to cope with this 
problem, the edge points are delocalised to provide a sub 
pixel accuracy using the method developed in (Devernay, 
1995). 
Figure 5 shows an example of result obtained by this algo 
rithm. 
5 HYPOTHESIS VERIFICATION AND TEXTURE 
PATTERN RECOGNITION 
5.1 Ellipse Rectification 
Validation and recognition of road sign is performed by 
comparing the detected circular road sign with a set of ref 
erence ones (See Figure 7) . The inside texture of sign is 
used to measure the its similarity with all reference signs. 
Correlation coefficient seems to be particularly interesting 
for this purpose. However the detected signs are deformed 
to ellipse while the reference ones are circular. It make the 
correlation process difficult. In order to resolve the prob 
lem, we propose to rectify the texture of the detected sign 
to match the geometry of reference ones. The needed trans 
formation must transform an ellipse to a circle of a given 
radius. This is performed using an 8 parameters projec 
tive transformation. We suppose that the images are ap 
proximately horizontal or the orientation of the images are 
known so the transformation is unique. Figure 6 shows 
some examples of resampled road signs. 
5.2 Matching with texture DB 
After rectification, in order to match only the pixel inside 
the road sign, we generate a circular mask and we apply 
the ZMNCC (Zero Mean Normalized Cross Correlation) 
function to compute the similarity of detected and refer 
ence object (See Equation 4).