图像局部特证及其匹配的详细讲解

《图像局部特证及其匹配的详细讲解》由会员分享，可在线阅读，更多相关《图像局部特证及其匹配的详细讲解（74页珍藏版）》请在装配图网上搜索。

1、Matching with Invariant Features Example: Build a PanoramaM. Brown and D. G. Lowe. Recognising Panoramas. ICCV 2003How do we build panorama? We need to match (align) imagesMatching with FeaturesDetect feature points in both imagesMatching with FeaturesDetect feature points in both imagesFind corresp

2、onding pairsMatching with FeaturesDetect feature points in both imagesFind corresponding pairsUse these pairs to align imagesMatching with Features Problem 1: Detect the same point independently in both imagesno chance to match!We need a repeatable detectorMatching with Features Problem 2: For each

3、point correctly recognize the corresponding one?We need a reliable and distinctive descriptorMore motivation Feature points are used also for: Image alignment (homography, fundamental matrix) 3D reconstruction Motion tracking Object recognition Indexing and database retrieval Robot navigation otherC

4、ontents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale invariant Affine invariantAn introductory example:Harris corner detectorC.Harris, M.Stephens. “A Combined Corner and Edge Detector”. 1988The Basic Id

5、ea We should easily recognize the point by looking through a small window Shifting a window in any direction should give a large change in intensityHarris Detector: Basic Idea“flat” region:no change in all directions“edge”:no change along the edge direction“corner”:significant change in all directio

6、nsContents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale invariant Affine invariantHarris Detector: Mathematics2,( , )( , )(,)( , )x yE u vw x yI xu yvI x yChange of intensity for the shift u,v:Intensity

7、Shifted intensityWindow functionorWindow function w(x,y) =Gaussian1 in window, 0 outsideHarris Detector: Mathematics( , ),uE u vu vMv For small shifts u,v we have a bilinear approximation:22,( , )xxyx yxyyII IMw x yI IIwhere M is a 22 matrix computed from image derivatives:Harris Detector: Mathemati

8、cs( , ),uE u vu vMv Intensity change in shifting window: eigenvalue analysis1, 2 eigenvalues of Mdirection of the slowest changedirection of the fastest change(max)-1/2(min)-1/2Ellipse E(u,v) = constHarris Detector: Mathematics12“Corner”1 and 2 are large, 1 2;E increases in all directions1 and 2 are

9、 small;E is almost constant in all directions“Edge” 1 2“Edge” 2 1“Flat” regionClassification of image points using eigenvalues of M:Harris Detector: MathematicsMeasure of corner response:2dettraceRMkM1212dettraceMM (k empirical constant, k = 0.04-0.06)Harris Detector: Mathematics12“Corner”“Edge” “Ed

10、ge” “Flat” R depends only on eigenvalues of M R is large for a corner R is negative with large magnitude for an edge |R| is small for a flat regionR 0R 0R threshold) Take the points of local maxima of RHarris Detector: WorkflowHarris Detector: WorkflowCompute corner response RHarris Detector: Workfl

11、owFind points with large corner response: RthresholdHarris Detector: WorkflowTake only the points of local maxima of RHarris Detector: WorkflowHarris Detector: Summary Average intensity change in direction u,v can be expressed as a bilinear form: Describe a point in terms of eigenvalues of M:measure

12、 of corner response A good (corner) point should have a large intensity change in all directions, i.e. R should be large positive( , ),uE u vu vMv 21212Rk Contents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant

13、 Scale invariant Affine invariantHarris Detector: Some Properties Rotation invarianceEllipse rotates but its shape (i.e. eigenvalues) remains the sameCorner response R is invariant to image rotationHarris Detector: Some Properties Partial invariance to affine intensity change Only derivatives are us

14、ed = invariance to intensity shift I I + b Intensity scale: I a IRx (image coordinate)thresholdRx (image coordinate)Harris Detector: Some Properties But: non-invariant to image scale!All points will be classified as edgesCorner !Harris Detector: Some Properties Quality of Harris detector for differe

15、nt scale changesRepeatability rate:# correspondences# possible correspondencesC.Schmid et.al. “Evaluation of Interest Point Detectors”. IJCV 2000Contents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale inv

16、ariant Affine invariantWe want to:detect the same interest points regardless of image changesModels of Image Change Geometry Rotation Similarity (rotation + uniform scale) Affine (scale dependent on direction)valid for: orthographic camera, locally planar object Photometry Affine intensity change (I

17、 a I + b)Contents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale invariant Affine invariantRotation Invariant Detection Harris Corner DetectorC.Schmid et.al. “Evaluation of Interest Point Detectors”. IJCV

18、 2000Contents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale invariant Affine invariantScale Invariant Detection Consider regions (e.g. circles) of different sizes around a point Regions of corresponding

19、sizes will look the same in both imagesScale Invariant Detection The problem: how do we choose corresponding circles independently in each image?Scale Invariant Detection Solution: Design a function on the region (circle), which is “scale invariant” (the same for corresponding regions, even if they

20、are at different scales)Example: average intensity. For corresponding regions (even of different sizes) it will be the same.scale = 1/2 For a point in one image, we can consider it as a function of region size (circle radius) fregion sizeImage 1fregion sizeImage 2Scale Invariant Detection Common app

21、roach:scale = 1/2fregion sizeImage 1fregion sizeImage 2Take a local maximum of this functionObservation: region size, for which the maximum is achieved, should be invariant to image scale.s1s2Important: this scale invariant region size is found in each image independently!Scale Invariant Detection A

22、 “good” function for scale detection: has one stable sharp peakfregion sizebadfregion sizebadfregion sizeGood ! For usual images: a good function would be a one which responds to contrast (sharp local intensity change)Scale Invariant Detection Functions for determining scale222122( , ,)xyG x ye2( ,

23、,)( , ,)xxyyLGx yGx y( , ,)( , ,)DoGG x y kG x yKernel Imagef Kernels:where GaussianNote: both kernels are invariant to scale and rotation(Laplacian)(Difference of Gaussians)Scale Invariant Detection Compare to human vision: eyes responseShimon Ullman, Introduction to Computer and Human Vision Cours

24、e, Fall 2003Scale Invariant Detectors Harris-Laplacian1Find local maximum of: Harris corner detector in space (image coordinates) Laplacian in scale1 K.Mikolajczyk, C.Schmid. “Indexing Based on Scale Invariant Interest Points”. ICCV 20012 D.Lowe. “Distinctive Image Features from Scale-Invariant Keyp

25、oints”. Accepted to IJCV 2004scalexy Harris Laplacian SIFT (Lowe)2Find local maximum of: Difference of Gaussians in space and scalescalexy DoG DoG Scale Invariant DetectorsK.Mikolajczyk, C.Schmid. “Indexing Based on Scale Invariant Interest Points”. ICCV 2001 Experimental evaluation of detectors w.r

26、.t. scale changeRepeatability rate:# correspondences# possible correspondencesScale Invariant Detection: Summary Given: two images of the same scene with a large scale difference between them Goal: find the same interest points independently in each image Solution: search for maxima of suitable func

27、tions in scale and in space (over the image)Methods: 1.Harris-Laplacian Mikolajczyk, Schmid: maximize Laplacian over scale, Harris measure of corner response over the image2.SIFT Lowe: maximize Difference of Gaussians over scale and spaceContents Harris Corner Detector Description Analysis Detectors

28、 Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale invariant Affine invariantAffine Invariant Detection Above we considered:Similarity transform (rotation + uniform scale) Now we go on to:Affine transform (rotation + non-uniform scale)Affine Invariant Detection

29、 Take a local intensity extremum as initial point Go along every ray starting from this point and stop when extremum of function f is reachedT.Tuytelaars, L.V.Gool. “Wide Baseline Stereo Matching Based on Local, Affinely Invariant Regions”. BMVC 2000.010( )( )( )totI tIf tI tI dtfpoints along the ra

30、y We will obtain approximately corresponding regionsRemark: we search for scale in every directionAffine Invariant Detection The regions found may not exactly correspond, so we approximate them with ellipses Geometric Moments: 2( , )pqpqmx y f x y dxdyFact: moments mpq uniquely determine the functio

31、n fTaking f to be the characteristic function of a region (1 inside, 0 outside), moments of orders up to 2 allow to approximate the region by an ellipseThis ellipse will have the same moments of orders up to 2 as the original regionAffine Invariant DetectionqAp21TAA 121Tqq2region 2Tqq Covariance mat

32、rix of region points defines an ellipse:111Tpp1region 1Tpp ( p = x, yT is relative to the center of mass) Ellipses, computed for corresponding regions, also correspond!Affine Invariant Detection Algorithm summary (detection of affine invariant region): Start from a local intensity extremum point Go

33、in every direction until the point of extremum of some function f Curve connecting the points is the region boundary Compute geometric moments of orders up to 2 for this region Replace the region with ellipseT.Tuytelaars, L.V.Gool. “Wide Baseline Stereo Matching Based on Local, Affinely Invariant Re

34、gions”. BMVC 2000.Affine Invariant Detection Maximally Stable Extremal Regions Threshold image intensities: I I0 Extract connected components(“Extremal Regions”) Find a threshold when an extremalregion is “Maximally Stable”,i.e. local minimum of the relativegrowth of its square Approximate a region

35、with an ellipseJ.Matas et.al. “Distinguished Regions for Wide-baseline Stereo”. Research Report of CMP, 2001.Affine Invariant Detection : Summary Under affine transformation, we do not know in advance shapes of the corresponding regions Ellipse given by geometric covariance matrix of a region robust

36、ly approximates this region For corresponding regions ellipses also correspondMethods: 1.Search for extremum along rays Tuytelaars, Van Gool:2.Maximally Stable Extremal Regions Matas et.al.Contents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invari

37、ant Descriptors Rotation invariant Scale invariant Affine invariantPoint Descriptors We know how to detect points Next question: How to match them?Point descriptor should be:1. Invariant2. DistinctiveContents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Af

38、fine invariant Descriptors Rotation invariant Scale invariant Affine invariantDescriptors Invariant to Rotation Harris corner response measure:depends only on the eigenvalues of the matrix M22,( , )xxyx yxyyII IMw x yI IIC.Harris, M.Stephens. “A Combined Corner and Edge Detector”. 1988Descriptors In

39、variant to Rotation Image moments in polar coordinates( , )ki lklmr eI rdrdJ.Matas et.al. “Rotational Invariants for Wide-baseline Stereo”. Research Report of CMP, 2003Rotation in polar coordinates is translation of the angle: + 0This transformation changes only the phase of the moments, but not its

40、 magnitudeklmRotation invariant descriptor consists of magnitudes of moments:Matching is done by comparing vectors |mkl|k,lDescriptors Invariant to Rotation Find local orientationDominant direction of gradient Compute image derivatives relative to this orientation1 K.Mikolajczyk, C.Schmid. “Indexing

41、 Based on Scale Invariant Interest Points”. ICCV 20012 D.Lowe. “Distinctive Image Features from Scale-Invariant Keypoints”. Accepted to IJCV 2004Contents Harris Corner Detector Description Analysis Detectors Rotation invariant Scale invariant Affine invariant Descriptors Rotation invariant Scale inv

42、ariant Affine invariantDescriptors Invariant to Scale Use the scale determined by detector to compute descriptor in a normalized frameFor example: moments integrated over an adapted window derivatives adapted to scale: sIxContents Harris Corner Detector Description Analysis Detectors Rotation invari

43、ant Scale invariant Affine invariant Descriptors Rotation invariant Scale invariant Affine invariantAffine Invariant Descriptors Affine invariant color moments( , )( , )( , )abcpqabcpqregionmx y Rx y Gx y Bx y dxdyF.Mindru et.al. “Recognizing Color Patterns Irrespective of Viewpoint and Illumination

44、”. CVPR99Different combinations of these moments are fully affine invariantAlso invariant to affine transformation of intensity I a I + bAffine Invariant Descriptors Find affine normalized frameJ.Matas et.al. “Rotational Invariants for Wide-baseline Stereo”. Research Report of CMP, 20032Tqq 1Tpp AA1

45、1111TA AA21222TA Arotation Compute rotational invariant descriptor in this normalized frameSIFT Scale Invariant Feature Transform1 Empirically found2 to show very good performance, invariant to image rotation, scale, intensity change, and to moderate affine transformations1 D.Lowe. “Distinctive Imag

46、e Features from Scale-Invariant Keypoints”. Accepted to IJCV 20042 K.Mikolajczyk, C.Schmid. “A Performance Evaluation of Local Descriptors”. CVPR 2003Scale = 2.5Rotation = 450SIFT Scale Invariant Feature Transform Descriptor overview: Determine scale (by maximizing DoG in scale and in space), local

47、orientation as the dominant gradient direction.Use this scale and orientation to make all further computations invariant to scale and rotation. Compute gradient orientation histograms of several small windows (128 values for each point) Normalize the descriptor to make it invariant to intensity chan

48、geD.Lowe. “Distinctive Image Features from Scale-Invariant Keypoints”. Accepted to IJCV 2004Affine Invariant Texture DescriptorSegment the image into regions of different textures (by a non-invariant method)Compute matrix M (the same as in Harris detector) over these regionsThis matrix defines the e

49、llipseF.Schaffalitzky, A.Zisserman. “Viewpoint Invariant Texture Matching and Wide Baseline Stereo”. ICCV 200322,( , )xxyx yxyyII IMw x yI II,1xx y My Regions described by these ellipses are invariant under affine transformationsFind affine normalized frameCompute rotation invariant descriptorInvari

50、ance to Intensity Change Detectors mostly invariant to affine (linear) change in image intensity, because we are searching for maxima Descriptors Some are based on derivatives = invariant to intensity shift Some are normalized to tolerate intensity scale Generic method: pre-normalize intensity of a

51、region (eliminate shift and scale)Talk Resume Stable (repeatable) feature points can be detected regardless of image changes Scale: search for correct scale as maximum of appropriate function Affine: approximate regions with ellipses (this operation is affine invariant) Invariant and distinctive descriptors can be computed Invariant moments Normalizing with respect to scale and affine transformationHarris Detector: ScaleRmin= 0Rmin= 1500