1 2 1 2 Taubin Ellipse Fitting by Hyperaccurate Least Squares Yuuki Iwamoto, 1 Prasanna Rangarajan 2 and Kenichi Kanatani 1 This paper presents a new method for fitting an ellipse to a point sequence extracted from images. The basic principle is the least squares, minimizing the algebraic distance. Exploiting the fact that the least-squares solution depends on the way the scale is normalized, we analyze the accuracy to high order terms with the scale normalization weight unspecified and determine the weight so that the second order bias is zero. We demonstrate by experiments that our method is superior to the Taubin method, which is also noniterative and known to be highly accurate. Although the highest accuracy is achieved by maximum likelihood, it requires iterations, which may not converge in the presence of large noise. In contrast, our method analytically computes a solution without iterations. 1 Department of Computer Science, Okayama University, Japan 2 Department of Electrical Engineering, Southern Methodist University, U.S.A. 1. 3 9 2,18 17,24,25 22 FS 4 HEIV 16 25 17 24 KCR 11 15 22 14,15 2. Ax 2 + 2Bxy + Cy 2 + 2f Dx + Ey + f 2 F = 1 f x, y 1 21,22 x α, y α, α = 1,..., 1 A,..., F 1 1 f = 6 1 c 29 Information Processing Society of Japan
J A,..., F J = 1 2 Ax 2 α + 2Bx α y α + Cyα 2 + 2f Dx α + Ey α + f 2 F 2 2 A = = F = F = 1 3 A + C = 1 4 A 2 + B 2 + C 2 + D 2 + E 2 + F 2 = 1 5 A 2 + B 2 + C 2 + D 2 + E 2 = 1 6 A 2 + 2B 2 + C 2 = 1 7 AC B 2 = 1 8 3 2 1 1,5,2, 4 1 7,2 5 119 6 28 7 3 3 8 1 4 6 6 u = A B C D E F 9 2 u, u = 1 1 Ax 2 + Bxy + Cy 2 + Dx + Ey + F = 1 A 2 + 4B 2 + C 2 + 4f 2 D2 + E 2 + f 4 F 2 = 2 Ax 2 + Bxy + Cy 2 + Dx + Ey + F = 1 A 2 + 4B 2 + C 2 + 4f 2 D2 + E 2 = 3 4 AC B 2 = AC B 2 < 1 a, b a, b 8 5 1 3. u 6 ξ ξ = x 2 2xy y 2 2f x 2f y f 2 11 1 u, ξ = 12 x α, y α ξ ξ α 1 J = 1 u, ξ α 2 = 1 u ξ α ξ α u = u, Mu 13 6 6 M M = 1 ξ α ξ α 14 13 u 2 1 u Mu = λu 15 λ λ u λ Mu λ 15 λ u 6 u u u = 1 8 6 5 8 u, u u u, u > u, u < 6 u, u > 6 M u, Mu > u u, u < λ < u u, u λ λ 2 c 29 Information Processing Society of Japan
u u 5 I 15 Mu = λu 16 M Taubin Taubin 23 TB 22 x 2 1 α x α y α f x α TB = 4 x α y α x 2 α + yα 2 x α y α f y α f x α x α y α yα 2 f y α f B x α f y α f 2 17 @ f x α f y α f 2 C A 15 4. x α, y α x α, ȳ α x α, y α ξ α ξ α = ξ α + 1ξ α + 2ξ α 18 ξ α, 1ξ α, 2ξ α x α, y α 1 2 11 x 2 1 α 2 x α ȳ α ȳ ξ α = 2 α, 1 ξ 2f B x α α = C @ 2f ȳ α A f 2 B @ 2 x α x α 2 x α y α + 2ȳ α x α 2ȳ α y α 2f x α 2f y α 1, 2 ξ α = C B A @ x 2 α 2 x α y α yα 2 14,15 2 ξ α 2 ξ α V [ξ α ] = E[ 1ξ α 1ξ α ] E[ ] x α, y α σ E[ x α ] = E[ y α ] =, E[ x 2 α] = E[ y 2 α] = σ 2, E[ x α y α ] = V [ξ α ] = E[ 1ξ α 1ξ α ] = σ 2 V [ξ α ] 2 1 C A 19 x 2 1 α x αȳ α f x α x αȳ α x 2 α + ȳα 2 x αȳ α f ȳ α f x α x V [ξ α ] = 4 αȳ α ȳ 2 α f ȳ α f B x α f ȳ α f 2 21 @ f x α f ȳ α f 2 C A V [ξ α ] σ 2 V [ξ α ] 21 17 Taubin TB = 1 V [ξ α ] 22 x α, ȳ α x α, y α 5. 18 14 M = 1 ξ α + 1 ξ α + 2 ξ α ξ α + 1 ξ α + 2 ξ α = + 1 M + 2 M + 23 3, 1M, 2M = 1 1M = 1 2 M = 1 ξ α ξ α, 24 ξα 1ξ α + 1ξ α ξ α, 25 ξα 2 ξ α + 1ξ α 1 ξ α + 2ξ α ξ α 16 u, λ u = ū + 1 u + 2 u +, λ = λ + 1 λ + 2 λ + 27 1, 2 1 2 23, 27 15 + 1 M + 2 M + ū + 1 u + 2 u + = λ + 1 λ + 2 λ + ū + 1 u + 2 u + 28 1 2 ū = λ ū 29 1 u + 1 M ū = λ 1 u + 1 λ ū 3 26 3 c 29 Information Processing Society of Japan
2u + 1M 1u + 2M ū = λ 2u + 1λ 1u + 2λ ū 31 12 ξ α, ū = 24 ū = 29 λ = 25 ū, 1 M ū = 3 ū 1λ = 3 1 u = 1 M ū 32 ū = ū P ū ū θ+ 1θ+ 2θ + 2 = 1 1 θ, 1 θ = 1 θ θ 32 31 2 λ 2λ = ū, 2M ū ū, 1 M 1 M ū ū, T ū = 33 ū, ū ū, ū T = 2M 1M 1M 34 2 2u ū ū 2 u ū 2 u = P ū 2 u = 2 u 35 31 32 2u = 2λ ū + 1M 1M ū 2M ū ū, T ū = ū, ū ū T ū 36 6. 32 u V [u] = E[ 1u 1u ] = E[ 1Mu 1Mu ] = 1 [ ] E ξ 2 α, u ξ α ξ β, u ξ β β=1 = 1 u, E[ ξ 2 α ξ β ]u ξ α ξ β 2 u, V [ξ α ]u ξ α ξ α, 37 = 1 ū, V [ξ α ]u ξ α ξ α 38 37 ξ α α E[ 1 ξ α 1 ξ β ] = δ αβ σ 2 V [ξ α ] δ αβ 37 V [u] Taubin V [u] 1 E[ 1 u] = 33 2 E[ 2u ] 34 T 26 E[ 2 M ] E[ 2 M ] = 1 ξα E[ 2 ξ α ] + E[ 1 ξ α 1 ξ α ] + E[ 2 ξ α ] ξ α ξα e 13 + V [ξ α ] + e 13 ξ α = σ 2 TB + 2S[ ξ c e 13] 2 22 ξ c, e 13 ξ c = 1 ξ α, e 13 = 1 1 4 S[ ] S[A] = A + A /2 E[ 1 M 1 M ] E[ 1M 1M ] tr[ V 2 [ξ α ]] ξ α ξ α + ξ α, ξα V [ξ α ] + 2S[V [ξ α ] ξα ξ α ] tr[ ] 39, 41 34 T E[T ] = σ 2 TB + 2S[ ξ c e 13] 1 2 +2S[V [ξ α ] ξα ξ α ] 39 41 tr[ V [ξ α ]] ξ α ξ α + ξ α, ξα V [ξ α ] 42 4 c 29 Information Processing Society of Japan
36 2u E[ 2 u ] = ū, E[T ]ū ū, ū ū E[T ]ū 7. 42 ξ c, ū =, ξ α, ū = E[T ]ū E[T ]ū = σ 2 TB ū + A + C ξ c 1 ξ 2 α, ξα V [ξ α ]ū +ū, V [ξ α ] ξα ξ α = I 2 E[ 2u ] E[ 2u ]= ū,e[t ]ūū E[T ]ū = I ūū E[T ]ū = E[T ]ū 45 I ūū = P ū = = 46 44, 45 2 E[ 2 u ] = σ 2 TB ū + A + C ξ c 1 ξ 2 α, ξα V [ξ α ]ū +ū, V [ξ α ] ξα ξ α 8. Taubin 44 ξ c, ū =, ξ α, ū = ū, E[T ]ū ū, E[T ]ū = σ 2 ū, TBū 1 ξ 2 α, ξα ū, V [ξ α ]ū = σ 2 ū, TB ū 1 2 tr[ ξα ξ α ]ū, V [ξ α ]ū = σ 2 ū, TB ū 1 tr[ ū, V 2 [ξ α ]ū ξ α ξ α ] 43 44 47 = σ 2 ū, TB ū σ2 tr[ ] 48 38 Taubin = TB Taubin 2 E[ 2 u ] = σ 2 q TB ū + A + C ξ c 1 2 +ū, V [ξ α ] ξα ξ α ξ α, ξα V [ξ α ]ū q = 1 tr[ ] 5 ū, TB ū 49 47 47 TBū q TBū 5 q < 1 Taubin 9. = TB + 2S[ ξ c e 13] 1 tr[ V [ξ 2 α ]] ξ α ξ α + ξ α, ξα V [ξ α ] +2S[V [ξ α ] ξα ξ α ] 42 E[T ] = σ 2 43 E[ 2 u ] = σ 2 ū, ū ū, ū ū = 52 51 ξ α, xα, ȳ α x α, y α 28 + 1 + 2 + 28 Oσ 2 1, 2 43 E[ 2u ] Oσ 4 2 1. 1a 1 31 1 5 x, y σ Taubin 49 51 5 c 29 Information Processing Society of Japan
u u u a b O 1 a 31 b σ =.5 1. 2. Taubin 3. 4. Chojnacki 4 FS 25 1b σ =.5 u ū u u ū u = P ūu 53 2a P ū I ūū ū 2b, c σ 1 B D B = 1 1 u a, D = 1 a=1 1 1 1 a=1 u a 2 54 u a a 2c KCR 12,14,15 D KCR = σ ξ ] tr[ α ξ α 55 ū, V [ξ α ]ū 15 17 Taubin TB 1 51 15 u = 1/λMu 56 14 M 2 λ 1 17 5 6 2 2 a b c a u ū u b, c 1a a b σ 1. 2. Taubin 3. 4. c KCR 5 λ λ u 2b Taubin 38 Taubin 2c Taubin 2 2b 38 15 2c 2b, c Taubin 3 155 Taubin Taubin 6 c 29 Information Processing Society of Japan
3 155 Taubin Taubin 11. 14,15 2 Taubin : C o. 215172 1 A. Albano, Representation of digitized contours in terms of conics and straight-line segments, Comput. Graphics Image Process., 3-1 1974-3, 23 33. 2,,,, 29-CVIM-166-5 29-3, 33 4. 3 F. J. Bookstein, Fitting conic sections to scattered data, Comput. Graphics Image Process., 9-1 1979-1, 56 71. 4 W. Chojnacki, M. J. Brooks, A. van den Hengel and D. Gawley, On the fitting of surfaces to data with covariances, IEEE Trans. Patt. Anal. Mach. Intell., 22-11 2-11, 1294 133. 5 D. B. Cooper and. Yalabik, On the computational cost of approximating and recognizing noise-perturbed straight lines and quadratic arcs in the plane, IEEE Trans. Computers, 25-1 1976-1, 12 132. 6 A. Fitzgibbon, M. Pilu and R. B. Fisher, Direct least square fitting of ellipses, IEEE Trans. Patt. Anal. Mach. Intell., 21-5 1999-5, 476 48. 7 W. Gander, H. Golub, and R. Strebel, Least-squares fitting of circles and ellipses, BIT, 34-4 1994-12, 558 578. 8 R. Gnanadesikan, Methods for Statistical Data Analysis of Multivariable Observations, Wiley, ew Yori,.Y., U.S.A. 1977. 9 K. Kanatani, Geometric Computation for Machine Vision, Oxford University Press, Oxford, U.K., 1993. 1,,, 1995. 11,,, 36-8 1995-8, 1865 1873. 12 K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice, Elsevier Science, Amsterdam, The etherlands, 1996; Dover, ew York, 25. 13, KCR,, 25-CVIM-147-8 25-1, 59 64. 14,,, 25-CVIM- 156-18 26-11, 147 154. 15 K. Kanatani, Statistical optimization for geometric fitting: Theoretical accuracy analysis and high order error analysis, Int. J. Comp. Vis. 8-2 28-11, 167 188. 16 Y. Leedan and P. Meer, Heteroscedastic regression in computer vision: Problems with bilinear constraint, Int. J. Comput. Vision., 37-2 2-6, 127 15. 17,,,,, 28-CVIM-162-1 28-3, 53 6. 18,,,, D-II, J85-D-II-12 22-12, 1823 1831. 19 K. A. Paton, Conic sections in chromosome analysis, Patt. Recog., 2-1 197-1, 39 4. 2 P. L. Rosin, A note on the least squares fitting of ellipses, Patt. Recog. Lett., 14-1 1993-1, 799-88. 21 [I],, 92-3 29-3, 229 233. 7 c 29 Information Processing Society of Japan
22 [II],, 92-4 29-4, 31 36. 23 G. Taubin, Estimation of planar curves, surfaces, and non-planar space curves defined by implicit equations with applications to edge and range image segmentation, IEEE Trans. Patt. Anal. Mach. Intell., 13-11 1991-11, 1115 1138. 24,,, 25-CVIM-151-15 25-11, 197 114. 25,,,, 26-CVIM-154-36 26-5, 339 346. E[ 1M 1M ] E[ 1M 1M ] = E[ 1 ξα 1 ξ 1 α + 1 ξ α ξ α = 1 2 = 1 2 + 1 ξ α ξ α = 1 2 ξβ 1 ξ β + 1 ξ β ξ β ] β=1 E[ ξ α 1 ξ α + 1 ξ α ξ α ξ β 1 ξ β + 1 ξ β ξ β ] E[ ξ α 1 ξ ξβ α 1 ξ β + ξ α 1 ξ α 1 ξ β ξ β + 1 ξ ξβ α ξ α 1 ξ β 1 ξ β ξ β ] E[ ξ α 1 ξ α, ξβ 1 ξ β + ξ α 1 ξ α, 1 ξ β ξ β + 1 ξ α ξ α, ξβ 1 ξ β + 1 ξ α ξ α, 1 ξ β ξ β ] = 1 E[ 1ξ 2 α, ξβ ξ α 1ξ β + 1ξ α, 1ξ β ξ α ξ β + ξ α, ξβ 1 ξ α 1 ξ β + 1 ξ α 1 ξ β, ξ α ξ β ] = 1 E[ ξ 2 α ξβ 1 ξ α 1 ξ β + tr[ 1 ξ β 1 ξ α ] ξ α ξ β = 1 2 + ξ α, ξβ 1ξ α 1ξ β + 1ξ α 1ξ ξα β ξ β ] ξα ξ β E[ 1 ξ α 1 ξ β ] + tr[ E[ 1 ξ β 1 ξ α ]] ξ α ξ β + ξ α, ξβ E[ 1 ξ α 1 ξ β ] + E[ 1ξ α 1 ξ β ] ξα ξ β 2 +δ αβ V [ξ α ] 2 2 ξα ξ β ξα ξ α δ αβ V [ξ α ]+tr[ δ αβ V [ξ α ]] ξ α ξ β + ξ α, ξβ δ αβ V [ξ α ] ξα ξ β V [ξ α ] + tr[ V [ξ α ]] ξ α ξ α + ξ α, ξα V [ξ α ] +V [ξ α ] ξα ξ α tr[ V [ξ α ]] ξ α ξ α + ξ α, ξα V [ξ α ] + 2S[V [ξ α ] ξα ξ α ] 57 8 c 29 Information Processing Society of Japan