CS664 Lecture #20: Epipolar geometry, edge detectionEstimating epipolar geometryHomogeneous coordinatesAdvantagesCamera projection matrixEstimating the essential matrixDetecting edges or featuresEdge detectionDetecting EdgesThe GradientFinite DifferencesDiscrete GradientEstimating Discrete GradientDiscrete LaplacianProblems With Local DetectorsRegions of Support3x3 Mean Filter ExampleBorder PixelsWeighted Average Filter Gaussian FilterGaussian Versus Mean FilterConvolutionBack to Edges: DerivativesDerivatives and ConvolutionsDerivatives Using ConvolutionLinear OperatorsArea of Support for 2D OperatorsGradient MagnitudeEdge Detection by SubtractionWhat Does This Do?CS664 Lecture #20: Epipolar geometry, edge detection2Estimating epipolar geometry Assume for the moment that all intrinsic parameters are known Essential Matrix E captures the geometry– Mapping from a point to its epipolar line• i.e., tells you where that point might be!– For a point x with corresponding point x’ on the other image, xTEx’ = 0• Using homogeneous coordinates When intrinsic parameters are unknown, we have the Fundamental Matrix F3Homogeneous coordinates Identify a point in the image plane with ray passing through that point (pixel)– (x,y) ≡ (α x, α y, α) for non-zero α– (X,Y,Z) ≡ (X/Z,Y/Z,1) for non-zero Z4Advantages Many non-linear operations become linear in homogeneous coordinates– Example: (X,Y,Z) projects to (fX/Z,fY/Z)2D point 3D point3x4 camera projection5Camera projection matrix6Estimating the essential matrix– Estimate E from 5 or more correspondences• More correspondences make this easier• 8 point algorithm to find F − Longuet-Higgins, 1981– Can use RANSAC or Least Median Squares• RANSAC can tolerate more outliers• LMedS is parameter-free7Detecting edges or features To perform various sparse image operations we need features– Operations: registration, recognition, etc.– Features: edges, corners, “interest points” Feature detector desiderata– Efficient– Sparse, but not too sparse– Invariant!• Affine changes in intensity (easy)• Changes in point of view (hard)8Edge detection Classical problem in vision– Good handout from Dan Huttenlocher now on course web page Easiest to think about (draw) if we try to find edges in a 1D signal Two obvious approaches– Large first derivative– Zero second derivative (inflection point) Two classes of edge detectors– Canny style, or Marr-Hildreth style9Detecting Edges Seek sudden changes in intensity– Various derivatives of image Idealized continuous image I(x,y) Gradient (first derivative), vector valued∇I = (∂I/∂x, ∂I/∂y) Squared gradient magnitude⎟⎜∇I⎟⎜2 = (∂I/∂x)2+ (∂I/∂y)2– Avoid computing square root Laplacian (second derivative)∇2I = ∂2I/∂x2+ ∂2I/∂y210The Gradient Direction of most rapid change Gradient direction is atan(∂I/∂y,∂I/∂x)– Normal to edge Strength of edge given by grad magnitude– Often use squared magnitude to avoid computing square roots∇I = (∂I/∂x, 0)∇I = (0, ∂I/∂y)∇I = (∂I/∂x, ∂I/∂y)11 Images are digitized– Idealized continuous underlying function I(x,y) realized as discrete values on a grid I[u,v] Approximations to derivatives (1D)dF/dx ≈ F[u+1] – F[u]d2F/dx2≈ F[u-1] – 2F[u] + F[u+1] Second derivative symmetric about edgeFinite Differences101010111101-1 1 -1 10 10-11 10-2 2 -2 11 -9 -1 -11 12 -2dF: edge at extremumd2F: edge at zero crossing12 Partial derivatives are estimated at boundaries between adjacent pixels– E.g., pixel and next one in x,y directions Yields estimates at different points in each direction if use x,y directions Generally use 45° directions to solve this– Magnitude fine, but gradient orientation needs to be rotated to correspond to axes Discrete Gradient001121211212322313Estimating Discrete Gradient Gradient at u,v with 45° axes– Down-right: ∂I/∂x’ ≈ I[u+1,v+1]-I[u,v]– Down-left: ∂I/∂y’ ≈ I[u,v+1]-I[u+1,v] Handle image border, e.g., no changeu,vu+1,v+1u+1,vu,v+16677211172272676110-14651-10000000-5-4-100650-5000510026171116 72 5012600025100I∂I/∂x’ ∂I/∂y’ ⎟⎜∇I⎟⎜214Discrete Laplacian Laplacian at u,v∂2I/∂x2= I[u-1,v]-2I[u,v]+I[u+1,v]∂2I/∂y2= I[u,v-1]-2I[u,v]+I[u,v+1]∇2I is sum of directional second derivatives:I[u-1,v]+I[u+1,v]+I[u,v-1]+I[u,v+1]-4I[u,v] Can view as 3x3 mask or stencil– Value at u,v given by sum of product with I Grid yields poor rotational symmetry– Weighted sum of two masks1-41111-4111 1-20111444415Problems With Local Detectors 1D example illustrates effect of noise (variation) on local measures16Regions of Support Desirable to have edge detectors that operate over interval or region Low pass filtering of an image– Combining certain neighboring pixel values to produce “less variable” image– Often referred to as “smoothing” or as “blurring” the image Simple idea: mean filter – average values over w by h neighborhoodM[u,v] = (1/wh) ΣiΣjF[u+i-(w-1)/2, v+j-(h-1)/2]173x3 Mean Filter Example000000000000000000000 0 0 90 90 90 90 90 0 00 0 0 90 90 90 90 90 0 000 0 90 90 90 90 90 0 0000900 90 90 90 0 000 0 90 90 90 90 90 0 000000000000090 00000000000000000??????????? 0 10 20 30 30 30 20 10 ?? 0 20 40 60 60 60 40 20 ?? 0 30 60 90 90 90 60 30 ?? 0 30 50 80 80 90 60 30 ?? 0 30 50 80 80 90 60 30 ?? 0 20 30 50 50 60 40 20 ?? 1020303030302010 ??1010 1000000???????????M[u,v] = (1/9) ΣiΣjF[u+i-1, v+j-1]18Border Pixels As usual with image operations the border cases need to be handled somehow– Produce smaller image by summing only when entire w by h window fits inside image– Sum only value inside image but produce full size image• In effect summing zeroes outside image– Assume value outside image some non-zero value• E.g., reflected copy of the image No right answer, reflection often least bad19Weighted Average Filter  Sum of product with weights HG[u,v] = ΣiΣjH[i,j]F[u+i-(w-1)/2, v+j-(h-1)/2] Mean filter simply has H[I,j]=1/wh– Uniform weighting Note that entries of H should sum to 1– Otherwise performs overall scaling of the image• Consider 3x3 mask of 1’s instead of 1/9’s When averaging generally give central pixel most weight20Gaussian Filter Gaussian in two-dimensions Weights center more Falls off smoothly Integrates to 1 Larger σ