CSE 353: Computer Vision Lecture Notes Fall 24 PDF

CSE 353: Computer Vision Fall 24 1  Lec 5- Features Harris Corner Detector 2 Contents Why extract features? Characteristics of good features Corner Detection Basic Idea Math Interpreting the second moment matrix...

CSE 353: Computer Vision Fall 24 1  Lec 5- Features Harris Corner Detector 2 Contents Why extract features? Characteristics of good features Corner Detection Basic Idea Math Interpreting the second moment matrix Interpreting the eigenvalues Corner response function Harris detector: Steps Other corners 3 Why extract features? Motivation: panorama stitching We have two images – how do we combine them?  Why extract features? Motivation: panorama stitching We have two images – how do we combine them? Step 1: extract features Step 2: match features Step 2: match features Why extract features? Motivation: panorama stitching We have two images – how do we combine them? Step 1: extract features Step 2: match features Step 3: align images Characteristics of good features Repeatability/precision The same feature can be found in several images despite geometric and photometric transformations Saliency/matchability Each feature is distinctive Compactness and efficiency Many fewer features than image pixels Locality A feature occupies a relatively small area of the image; robust to clutter and occlusion Applications Feature points are used for: Image alignment 3D reconstruction Motion tracking Robot navigation Indexing and database retrieval Object recognition Finding Corners Key property: in the region around a corner, image gradient has two or more dominant directions Corners are repeatable and distinctive C.Harris and M.Stephens. "A Combined Corner and Edge Detector.“ Proceedings of the 4th Alvey Vision Conference, 1988 : pages 147-- 151. Corner Detection: Basic Idea We should easily recognize the point by looking through a small window Shifting a window in any direction should give a large change in intensity “flat” region: “edge”: “corner”: no change in no change along significant change all directions the edge direction in all directions Corner Detection: Math Change in appearance of window w(x,y) for the shift [u,v]: E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y Window Shifted Intensity function intensity Window function w(x,y) = or 1 in window, 0 Gaussian outside Source: R. Szeliski Corner Detection: Math Change in appearance of window w(x,y) for the shift [u,v]: E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y I(x, y) E(u, v) E(0,0) w(x, y) slide: S. Lazebnik Corner Detection: Math Change in appearance of window w(x,y) for the shift [u,v]: E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y I(x, y) E(u, v) E(3,2) w(x, y) slide: S. Lazebnik Corner Detection: Math Change in appearance of window w(x,y) for the shift [u,v]: E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y We want to find out how this function behaves for small shifts E(u, v) Corner Detection: Math Change in appearance of window w(x,y) for the shift [u,v]: E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y We want to find out how this function behaves for small shifts Local quadratic approximation of E(u,v) in the neighborhood of (0,0) is given by the second-order Taylor expansion: slide: S. Lazebnik Corner Detection: Math E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y Second-order Taylor expansion of E(u,v) about (0,0): Eu (u, v)   2w( x, y )I ( x  u, y  v)  I ( x, y )I x ( x  u, y  v) x, y Euu (u, v)   2w( x, y )I x ( x  u, y  v) I x ( x  u, y  v) x, y   2w( x, y )I ( x  u, y  v)  I ( x, y )I xx ( x  u, y  v) x, y Euv (u, v)   2w( x, y )I y ( x  u, y  v) I x ( x  u, y  v) x, y   2w( x, y )I ( x  u, y  v)  I ( x, y )I xy ( x  u, y  v) x, y Corner Detection: Math E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y Second-order Taylor expansion of E(u,v) about (0,0):  Eu (0,0) 1  Euu (0,0) Euv (0,0) u  E (u, v)  E (0,0)  [u v]   [u v]  v   v E ( 0,0)  2  uv E (0,0) Evv ( 0,0)   E (0,0)  0 Eu (0,0)  0 Ev (0,0)  0 Euu (0,0)   2 w( x, y )I x ( x, y ) I x ( x, y ) x, y E vv (0,0)   2 w( x, y )I y ( x, y ) I y ( x, y ) x, y Euv (0,0)   2 w( x, y )I x ( x, y ) I y ( x, y ) x, y slide: S. Lazebnik  Corner Detection: Math E (u, v)   w( x, y )  I ( x  u, y  v)  I ( x, y )  2 x, y  Eu (0,0) 1  Euu (0,0) Euv (0,0) u  E (0,0)  0 E (u, v)  E (0,0)  [u v]   [u v]  v  Eu (0,0)  0  v E ( 0,0)  2  uv E (0,0) Evv ( 0,0)   Ev (0,0)  0 Euu (0,0)   2 w( x, y )I x ( x, y ) I x ( x, y ) x, y E vv (0,0)   2 w( x, y )I y ( x, y ) I y ( x, y ) x, y Euv (0,0)   2 w( x, y )I x ( x, y ) I y ( x, y ) x, y Second-order Taylor expansion of E(u,v) about (0,0):    w( x, y) I x2 ( x, y )  w( x, y) I ( x, y) I ( x, y) u  x y E (u, v)  [u v] x, y x, y  w( x, y ) I x ( x, y ) I y ( x, y)  w( x, y) I ( x, y)  v  2 y x, y x, y  Corner Detection: Math The quadratic approximation simplifies to u  E (u, v)  [u v] M   v  where M is a second moment matrix computed from image derivatives:  I x2 IxI y  M   w( x, y )  2  x, y  I x I y I y  slide: S. Lazebnik Interpreting the second moment matrix The surface E(u,v) is locally approximated by a quadratic form. Let’s try to understand its shape. u  E (u, v)  [u v] M   v   I x2 IxI y  M   w( x, y )  2  x, y  I x I y I y  slide: S. Lazebnik Interpreting the second moment matrix Consider a horizontal “slice” of E(u, v): This is the equation of an ellipse. u  u  E (u, v)  [u v] M   v  [u v] M    const v   I x2 IxI y  M   w( x, y )  2  x, y  I x I y I y  slide: S. Lazebnik Interpreting the second moment matrix First, consider the axis-aligned case (gradients are either horizontal or vertical)  I 2 I x I y  1 0  M   w( x, y )  x 2    x, y  I x I y I y   0 2  If either λ is close to 0, then this is not a corner, so look for locations where both are large. slide: S. Lazebnik Interpreting the second moment matrix Consider a horizontal “slice” of E(u, v): E (u, v)  [u v] M u v  This is the equation of an ellipse: λ1 u + λ2 v = K 2 2   1 0 1 Diagonalization of M: M R   R  0 2  The axis lengths of the ellipse are determined by the eigenvalues and the orientation is determined by R direction of the fastest change direction of the slowest change (max)-1/2 (min)-1/2 slide: S. Lazebnik  Interpreting the eigenvalues Classification of image points using eigenvalues of M: 2 “Edge” 2 >> 1 “Corner” 1 and 2 are large,  1 ~  2; E increases in all directions 1 and 2 are small; E is almost constant in “Edge” “Flat” all directions 1 >> 2 region 1 slide: S. Lazebnik Corner response function R  det( M )   trace (M )  12   (1  2 ) 2 2 α: constant (0.04 to 0.06) “Edge” R0 R is negative with large magnitude for an edge |R| is small for a flat region |R| small “Flat” “Edge” region Rthreshol d slide: S. Lazebnik Harris Detector: Steps Take only the points of local maxima of R slide: S. Lazebnik Harris Detector: Steps slide: S. Lazebnik Other corners Questions 33