[II] Optimization Computation for 3-D Understanding of Images [II]: Ellipse Fitting 1. (1) 2. (2) (edge detection) (edge) (zero-crossing) Canny (Canny operator) (3) 1(a) [I] [II] [III] [IV ] E-mail sugaya@iim.ics.tut.ac.jp E-mail kanatani@suri.cs.okayama-u.ac.jp Yasuyuki SUGAYA, Member (Department of Information and Computer Sciences, Toyohashi University of Technology, Toyohashi-shi, 441-8580 Japan) and Kenichi KANATANI, Member (Graduate School of Natural Science and Technology, Okayama-shi, 700-8530 Japan). Vol. 92 No. 4 pp.301 306 2009 4 1(b) 1(c) Canny (4),(5) 1(c) 1(d) 1(d) 2 CG 3. Ax 2 +2Bxy+Cy 2 +2(Dx+Ey)f 0 +F f 2 0 =0 (1) f 0 (1) (x α, y α ), α = 1,..., N (1) α = 1,..., N Ax 2 α+2bx α y α +Cy 2 α+2(dx α +Ey α )f 0 +Ff 2 0 0 (2) A, B, C, D, E, F 3 A, B, C, D, E, F [II] 301
(a) (b) (c) Canny (d) 1 ( x α, y α ) 3 (x α, y α ) (a) A 2 + B 2 + C 2 + D 2 + E 2 + F 2 = 1 (3) u ξ α u (A, B, C, D, E, F ) (4) ξ α (x 2 α, 2x α y α, y 2 α, 2f 0 x α, 2f 0 y α, f 2 0 ) (5) 2 (b) CG (2) (u, ξ α ) 0, α = 1,..., N (6) a, b (a, b) F = 1, A + B = 1, A 2 + B 2 + C 2 + D 2 + E 2 + F 2 = 1 (3) u = 1 (1) ( 1) ( 1) u (x α, y α ) x α 302 Vol.92, No.4, 2009
(1) (conic) (1) (6) ( 2) 4. (6) u N (u, ξ α) 2 (least squares) 6 6 M LS M LS ξ α ξ α (7) (u, ξ α ) 2 = (u, ξ α ξ α u) = (u, M LS u) (8) u u M LS (8) (3) F = 1 A + B = 1 (8) (2),(9),(10),(11) 5. (1) 0 (8) α (u,ξ α )=Ax 2 α+2bx α y α +Cy 2 α+2(dx α +Ey α )f 0 +Ff 2 0 (9) 0 (x α, y α ) x, y 0 ( x α, ȳ α ) x α = x α + ɛ α, y α = ȳ α + η α (10) ɛ α, η α 0 σ 2 (9) ( x α, ȳ α ) (9) 0 (u, ξ α ) = 2(A x α + Bȳ α + Df 0 )ɛ α +2(B x α + Cȳ α + Ef 0 )η α + (11) (u, ξ α ) 0 4 ( (A x α +Bȳ α +Df 0 ) 2 +(B x α +Cȳ α +Ef 0 ) 2) σ 2 (12) ( 3) u 4σ 2 (u, V 0 [ξ α ]u) (13) 6 6 V 0 [ξ α ] x 2 α x α ȳ α 0 f 0 x α 0 0 x α ȳ α x 2 α + ȳ 2 α x α ȳ α f 0 ȳ α f 0 x α 0 V 0 [ξ α ] 0 x α ȳ α ȳα 2 0 f 0 ȳ α 0 f 0 x α f 0 ȳ α 0 f0 2 0 0 (14) 0 f 0 x α f 0 ȳ α 0 f0 2 0 0 0 0 0 0 0 (u, ξ α ) 0 4σ 2 (u, V 0 [ξ α ]u) (u, ξ α )/ 4(u, V 0 [ξ α ]u) 0 σ 2 J = 1 4 (u, ξ α ) 2 (u, V 0 [ξ α ]u) (15) ( 2) AC B 2 > 0 (7) ( 3) c c 2 [II] 303
(maximum likelihood estimation) V 0 [ξ α ] (14) ( x α, ȳ α ) (x α, y α ) (15) u u (15) (1) ( 4) (6) (15) Chojnacki (12) FNS 6. (15) ξ α N (u, ξ) = 0 u N ξ α ξ α (Euclidean distance) (Mahalanobis distance) ξ α ξ α ( 4) ξ α ξ α ξ α V [ξ α ] J = (ξ α ξ α, V [ξ α ] 5 (ξ α ξ α )) (16) ξ α ξ α ( ) 5 5 ( 5) (16) (u, ξ α ) = 0, α = 1,..., N (16) (15) V 0 [ξ α ] V [ξ α ] () (14) ξ α 7. Taubin (15) FNS (1) 4. Taubin (15) V 0 [ξ α ] N TB 1 N V 0 [ξ α ] (17) (15) J TB J TB = N 4 = N 4 (u, ξ α ) 2 (u, N TB u) = N 4 (u, M LS u) (u, N TB u) (u, ξ α ξ α u) (u, N TB u) (18) M LS (7) J TB (Rayleigh quotient) u ( 6) (generalized eigenvalue problem) M LS u = λn TB u (19) (10) (14) V 0 [ξ α ] 6 6 0 (17) N TB N TB ( 7) ξ α u, V 0 [ξ α ] ( ξ, u) = 0 4 ( 4) ξ α x α V 0 [ξ α ] 3 3 V 0 [x α ] ( 5) 5 0 (8) (1) ( 6) (19) N TB λ u ( 7) A 0 x (x, Ax) > 0 (8) 304 Vol.92, No.4, 2009
ξ α = ( V 0 [ξ α ] = z α f0 2 ( ), u = V 0 [z α ] 0 0 0 5 5 M LS Ñ TB M LS z α z α, z α z α z α, ) ( Ñ TB z 1 N v F ) (20) V 0 [z α ] (21) z α (22) (19) M LS v = λñ TBv, (v, z) + f 2 0 F = 0 (23) 1 (19) Ñ TB v 2 F Taubin 5 Taubin Taubin (13) Taubin 1990 (14) (16) 8. (1) u u û u û u ( 6) û V [û] = E[ u u ] (24) E[ ] KCR (KCR lower bound)) V [û] 4σ 2 M 5 (25) ( 8) σ 2 (a) u u O u^ u (b) 5 Taubin (11) 6 u û u u ( 8) A x (x, Ax) 0 (8) [II] 305
(a) (b) 7 (9) M M ξ α ξ α (u, V 0 [ ξ α ]u) (26) ξ α V 0 [ ξ α ] ξ α V 0 [ξ α ] (x α, y α ) u (25) O(σ 4 ) KCR 7 (9) 9. Taubin 2 (1),, [I], vol.92, no.3, pp.229 233, March 2009. (2) K. Kanatani, Geometric Computation for Machine Vision, Oxford University Press, Oxford, U.K. 1993. (3),,,, 2004. (4),,,, (D-II), vol.j85-d-ii, no.12, pp.1823 1831, Dec. 2002. (5),, 14 (SSII08), IN1-14, pp.1 6 June 2008. (6) A. Fitzgibbon, M. Pilu and P. B. Fisher, Direct least square fitting of ellipses, IEEE Trans. Pattern Anal. Mach. Intell., vol.21, no.5, pp.476 480, May 1999. (7),,, 1998. (8),,, 2005. (9) Y. Kanazawa and K. Kanatani, Optimal conic fitting and reliability evaluation, IEICE Trans. Inf. & Syst., vol.e79-d, no.9, pp.1323 1328, Sept. 1996. (10) K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice, Elsevier Science, Amsterdam, The Netherlands, 1996; Dover, New York, 2005. (11),,,,, no.2006-cvim-154-36, pp.339 346, May 2006. (12) W. Chojnacki, M.J. Brooks, A. van den Hengel and D. Gawley, On the fitting of surfaces to data with covariances, IEEE Trans. Pattern Anal. Mach. Intell., vol.22, no.11, pp.1294 1303, Nov. 2000. (13) 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. Pattern Anal. Mach. Intell., vol.13, no.11, pp.1115 1138, Nov. 1991. (14) N. Tagawa, T. Toriu, and T. Endoh, Un-biased linear algorithm for recovering three-dimensional motion from optical flow, IEICE Trans. Inf. & Syst., vol.e76-d, no.10, pp.1263 1275, Oct. 1993. (15) N. Tagawa, T. Toriu, and T. Endoh, Estimation of 3-D motion from optical flow with unbiased objective function, IEICE Trans. Inf. & Syst., vol.e77-d, no.10, pp.1148 1161, Oct. 1994. (16) N. Tagawa, T. Toriu, and T. Endoh, 3-D motion estimation from optical flow with low computational cost and small variance, IEICE Trans. Inf. & Syst., vol.e79-d, no.3, pp.230 241, March 1996. 20 10 29 20 11 17 8 13 47 54 IEEE 306 Vol.92, No.4, 2009