Automatic Detection of Circular Objects by Ellipse Growing Mitsuo OKABE, Kenichi KANATANI, and Naoya OHTA 1. [4], [5], [18], [19] [14], [17] [28], [32

Size: px

Start display at page:

Download "Automatic Detection of Circular Objects by Ellipse Growing Mitsuo OKABE, Kenichi KANATANI, and Naoya OHTA 1. [4], [5], [18], [19] [14], [17] [28], [32"

たいちしげまつ
4 years ago
Views:

1 Automatic Detection of Circular Objects by Ellipse Growing Mitsuo OKABE, Kenichi KANATANI, and Naoya OHTA 1. [4], [5], [18], [19] [14], [17] [28], [32] [6], [21], [27] Fujitsu Cadtech, Ltd., Oyama-shi, Japan Department of Information Technology, Okayama University, Okayama-shi, Japan Department of Computer Science, Gunma University, Kiryushi, Japan [2], [3], [7] [10], [22] [26], [31], [33] [39] D II Vol. J85 D II No. 12 pp

2 2002/12 Vol. J85 D II No. 12 edge detection voting for the center of the circle voting for the radius of the circle ellipse growth outlier detection ellipse fitting Does the edge segment mostly cover the ellipse? no yes search for the other segment end Fig. 1 1 Flowchart of the procedure. [2] 2 [30] LMedS [29] Sobel Fig. 2 2 The evolute of an ellipse and its singularities [11] 4 2 [1] [16] P k 2 P C r 3(a) C γr k k = 30, γ = 1/10 1/ r C

3 Fig. 3 (a) (b) (c) (a) P k 2. (b) C R e R2 /2s 2 cos φ R (c) δ (a) Voting around the center of the circle passing through P and the two points away from it by k pixels on both sides.

3 3 Fig. 3 (a) (b) (c) (a) P k 2. (b) C R e R2 /2s 2 cos φ R (c) δ (a) Voting around the center of the circle passing through P and the two points away from it by k pixels on both sides. (b) A pixel away from the estimated center C by distance R votes the value R with weight e R2 /2s 2 cos φ. (c) Fitting an ellipse to the longest edge segment inside the region within distance δ from the estimated ellipse. C P R [11] R 1 e R2 /2s 2 cos φ 2 φ P Sobel CP 3(b) s C R s 1/4 R ±1 e 1/2 R 1 ) e R2 /2s 2 C s cos φ 0 C δ 2 e x2 3(c) [12], [13], [15] 3 [18] Ax 2 +2Bxy+Cy 2 +2f(Dx+Ey)+f 2 F =0 (1) f AC B 2 > 0 (2) x Q x/f A B D x = y/f, Q = B C E (3) 1 D E F (1) [14], [16] (x, Qx) = 0 (4) (a, b) a, b

4 2002/12 Vol. J85 D II No. 12 δ Q (+), Q ( ) 1 S c c ( A S = B B C ), c = c = (c, S 1 c) F (5) 2 S λ 1, λ 2 ( D E u 1, u 2 3 1, 2 1 = 2 = c ( c/λ 1 ± δ/f) 2 c (6) ( c/λ 2 ± δ/f) 2 4 S (+), S ( ) ( ) S (±) = U 1 2 ) U (7) U u 1, u Q (+), Q ( ) Q (±) = ( S (±) S (±) S 1 c (S (±) S 1 c) F +(c, S 1 (S (±) S)S 1 c) (8) (4) δ (x, Q (+) x)(x, Q ( ) x) < 0 (9) (1) 2 δ = 4 (2) δ 1 δ = LMedS [29] ) 4 Fig. 4 Judging if the edge segment covers more than half of the ellipse. 4 (3) {x α }, α = 1,..., N Q m = O, S m = 1 {x α } Q (1) A, B,..., F (2) 3 S = med N (x α, Qx α ) 2 α=1 (10) P k Qx α 2 P k = diag(1, 1, 0) 1, 1, 0 Q x α [15] 4 S < S m Q m Q, S m S 10 S > = S m x α (x α, Qx α) 2 < 10Sm (11) P k Qx α 2 [29] σ σ S m Q 2.13σ e

(a) (b) (c) 5 (a) (b) (c) Fig. 5 Estimation of the center of the initial circle.

(c) Simple Hough transform. 0 100 200 300 400 R (a) 0 100 200 300 400 R 6 R (a) (b) Fig.

5 (a) (b) (c) 5 (a) (b) (c) Fig. 5 Estimation of the center of the initial circle. (a) The detected circle and the fitted ellipse. (b) Voting for the center. (c) Simple Hough transform R (a) R 6 R (a) (b) Fig. 6 The number of votes (ordinate) for the radius R of the initial circle (abscissa). (a) Proposed method. (b) Simple voting. (b) e γ (6) 1 = λ 1 (1 ± γ) 2, λ(±) 2 = λ 2 (1 ± γ) 2 (12) 1 ± γ γ = e e 4, e 1 e, e (10) e, e (11) 3. 5(a) 5(b) 5(c) 1 [11] 6(a) R 6(b) ±1 1 [11] 6(a) 0 7(a) 1827

6 2002/12 Vol. J85 D II No. 12 (a) (b) 7 Fig. 7 (a) (b)(1) (2) (3) (4) (a) The edge image used. (b) (1) The initial circle, (2) the hyperbola resulting from the ellipse growing, (3) the ellipse fitted by LMedS, and (4) the ellipse fitted after detecting another segment. δ = 10 7(b) (1) (2) (3) (4) 8 1, 2 4, CPU Pentium III 600MHz OS Linux [32] cm cm [17], [28], [32] (2) No [1],,, [2],,,, PRMU98-123, Nov [3] Y. C. Cheng and S. C. Lee, A new method for quadratic curve detection using K-RANSAC with acceleration techniques, Pattern Recognit., vol.28, no.5, pp , May [4] W. Chojnacki, M. J. Brooks, and A. van den Hen- 1828

7 論文楕円成長法による円形物体の自動検出図 8 当てはめ例上段はエッジ画像下段は初期円と当てはめた楕円を原画像に重ねたもの Fig. 8 Examples of ellipse ﬁtting: the edge images (upper rows); the initial circles and the ﬁtted ellipses superimposed on the original images (lower rows). 1829

2002/12 Vol. J85 D II No. 12 Fig. 9 9 Calibration of a turntable. gel, Rationalising the renormalisation method of Kanatani, J. Math. Imaging Vision, vol.14, no.1, pp.21 38, Feb. 2001. [5] W.

8 2002/12 Vol. J85 D II No. 12 Fig. 9 9 Calibration of a turntable. gel, Rationalising the renormalisation method of Kanatani, J. Math. Imaging Vision, vol.14, no.1, pp.21 38, Feb [5] 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 , Nov [6] D. B. Cooper and N. Yalabik, On the computational cost of approximating and recognizing nose-perturbed straight lines and quadratic arcs in the plane, IEEE Trans. Comput., vol.25, no.10, pp , Oct [7],,, θ-ρ, D-II, vol.j74-d-ii, no.9, pp , Sept [8] N. Guil and E. L. Zapata, Lower order circle and ellipse Hough transform, Pattern Recognit., vol.30, no.10, pp , Oct [9] C.-T. Ho and L.-H. Chen, A fast ellipse/circle detector using geometric symmetry, Pattern Recognit., vol.28, no.1, pp , Jan [10] C. L. Huang, Elliptical feature extraction via an improved Hough transform, Pattern Recognit. Lett., vol.10, no.2, pp , Feb [11] D. Ioannou, W. Huda, and A. F. Laine, Circle recognition through a 2D Hough Trnasform and radius histogramming, Image Vision Comput., vol.17, pp.15 26, Jan [12],,, vol.35, no.2, pp , Feb [13],,, [14] K. Kanatani, Geometric Computation for Machine Vision, Oxford University Press, Oxford, [15] K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice, Elsevier, Amsterdam, [16],,, [17] K. Kanatani and W. Liu, 3-D interpretation of conics and orthogonality, CVGIP: Image Understanding, vol.58, no.3, pp , Nov [18] Y. Kanazawa and K. Kanatani, Optimal conic fitting and reliability evaluation, IEICE Trans. Inf. & Syst., vol.e79-d, no.9, pp , Sept [19] Y. Leedan and P. Meer, Heteroscedastic regression in computer vision: Problems with bilinear constraint, Int. J. Comput. Vision, vol.37, no.2, pp , June [20] B. Matei and P. Meer, Reduction of bias in maximum likelihood ellipse fitting, Proc. 15th Int. Conf. Pattern Recognit., vol.3, pp , Barcelona, Spain, Sept [21],,,, D-II, vol.j84-d-ii, no.2, pp , Feb [22],,, D-II, vol.j81-d-ii, no.9, pp , Sept [23],,, Hough, D-II, vol.j72-d-ii, no.10, pp , Oct [24] D. Pao, H. F. Li, and R. Jayakumar, A decomposable parameter space for the detection of ellipses, Pattern Recognit., vol.14, no.12, pp , Dec [25] G. Roth and M. D. Levine, Extracting geometric primitives, CVGIP: Image Understanding, vol.58, no.1, pp.1 22, July [26] G. Roth and M. D. Levine, Geometric primitive extraction using a genetic alorithm IEEE Trans. Pattern Anal. & Mach. Intell., vol.16, no.9, pp , Sept [27] P. L. Rosin and G. A. W. West, Nonparametric segmentation of curves into various representations, IEEE Trans. Pattern Anal. & Mach. Intell., vol.17, no.12, pp , Dec [28] C. A. Rothwell, A. Zisserman, C. I. Marinos, D. A. Forsyth, and J. L. Mundy, Relative motion and pose from arbitrary plane curves, Image Vision Computing, vol.10, no.4, pp , May [29] P. J. Rousseeuw and A. M. Leroy, Robust Regression and Outlier Detection, Wiley, New York, [30], Hough,, vol.32, no.2, pp , Feb [31] S. Tsuji and F. Matsumoto, Detection of ellipses by 1830

9 a modified Hough transform, IEEE Trans. Comput., vol.27, no.8, pp , Aug [32],,,, 6, pp ,, June [33],,,, D-II, vol.j82-d-ii, no.12, pp , Dec [34],,,, Li-Lavin-Le Master, D-II, vol.j76-d-ii, no.12, pp , Dec [35],, Hough, D-II, vol.j73-d-ii, no.2, pp , Feb [36] W.-Y. Wu and M.-J. J. Wang, Elliptical object detection by using its geometric properties, Pattern Recognit., vol.26, no.10, pp , Oct [37],,,,, D-II, vol.j72-d-ii, no.7, pp , July [38] H. K. Yuen, J. Illingworth, and J. Kittler, Detecting partially occluded ellpises using the Hough transform, Image Vision Comput., vol.7, no.1, pp.31 37, Feb [39] J. H. Yoo and I. K. Seth, An ellipse detection method from the polar and pole definition of conics, Pattern Recognit., vol.26, no.2, pp , Feb (1), (3) f x y z Q r Q det Q = 1 det Q = 0 2 [14], [16] Q λ 1, λ 2, λ 3 u 1, u 2, u 3 λ 3 < 0 < λ 1 < = λ 2 [14] [ ] λ 2 λ 1 λ 1 λ 3 n = N u 2 ± u 3 (A 1) λ 2 λ 3 λ 2 λ 3 n 1 n 3 < = 0 d = λ 3 1 r. (A 2) x C = Z[Q 1 n] (A 3) Z[ ] Z 1 r C = dx C (n, x C ) (A 4) θ = cos 1 n 3 (A 5) IEEE N[ ]

(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 α,

(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 α, [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