画像特徴（点、直線、領域）の検出と識別-3 Hough変換

1 2011/5/161 -3 Hough Hough 1962):2 Hough and 1972):2 2 Hough 1981):2 geometric hashing et al. 1988):2 2011/5/162(Xi, Yi)(X1, Y1) (Xn, Yn)(A B) yxb(A,B) a a-b xi, yi a, b a b y = ax + b a-b 2 y = ax + b = xcos + ysin x.

2 0 y < 0 < 0o 1 (x, y) xcos ysin 2011/5/163 xcosxcos ysinysin Xi, Yi 0 0 00, , 0 Hough 1. 2. 3. 4. tokensVo t e sHorizontal axis is , vertical is . tokensvotes tokensvotes 2011/5/164 Real World ExampleOriginalEdge DetectionFound LinesParameter Space Hough 2 2011/5/165 The Hough transformThe Hough transform The Hough transformThe Hough transform =xcos + ysin edge detection image segmentation simple algorithm noise tolerance unable to detect the exact positionof the line pixels high memory reuqirements -high computational cost Hough

3 Hough (x0y0) r (x0,y0) r 3 Hough (x0,y0) a b 5 5 Hough Hough Hough ( ) :222)()(rbyaxii : 2 Hough ),(baA sin;cosrybrxaii abHough Xi, Yi 3 Hough CenterX CenterY sin;cosryCenterYrxCenterXii Hough 2 Hough (a, b) iiyxab tantan 2 2011/5/166 Hough 6 -Hough (Vanishing point) 3 uu00uu11uu22 ( ) 2004 5 ECCV 3 OpenCV.

4 CvHoughLines2(src img graystoragecvHoughLines2 (src_img_gray, storage, CV_HOUGH_STANDARD, 1, CV_PI / 180, 50, 0, 0); 3 or A612 2011/5/167 Hough Hough HoughHough HoughHough CorrelationFor each translation, compute the correlation between the target and the translated query:Generalized Hough Transform dxxTgxfgTf)()()(, CorrelationFor each translation, compute the correlation between the target and the translated query:Generalized Hough Transform dxxTgxfgTf)()()(, 4 xi(Xi, Yi) (,) Hough 1. (Xj,Yj) j 2.)

5 S s) j R () (u, v) ))(sin()())(cos()( jjjjjjsrYvsrXu2011/5/168 // geometric HashingCompute invariants Hash-tableLi t f bj tList of objectsVerifyHash Table Feature ExtractionBasis geometric hashing Wolfson and Rigoutsos, geometric hashing , an Overview, 1997 4 1 Hash Table ),(),,(22),,{221ijijijijjiNYPPPPXP,PPPP ijijijijxyyxM i,j j,k }{)},{()}(),({()}

6 },{(iikijikijPPPYPPX ffffyxyx 2011/5/169 Basis geometric HashingWolfson and Rigoutsos, geometric hashing , an Overview, 1997 Hash Table Wolfson and Rigoutsos, geometric hashing , an Overview, 1997 Basis geometric Hashing413 Wolfson and Rigoutsos, geometric hashing , an Overview, 1997 2 Hash Table 52 Recognition of Objects Find Features Select Basis Parameterize Features Do hash table lookup Histogram number of matches per model (4,1)(1,4)(3,2)Histogram number of matches per model Recognition of ObjectsVerification Least Square Transform Recovery(find the rotation, and translation of the basis) geometric hashing 1.)

7 Hash Table 2. 2 3. Hash Table 4. 1 2011/5/1610 geometric hashing 5 6 1 geometric hashing 1. Hash Table 2. geometric hashing