课件教案图像理解chapter matching

1、Efficient Matching Compare all features against all others Quadratic, impractical for most applications Indexing structure For individual image, or globally for all images Multi-dimensional search tree Hash table Vocabulary tree 4.1 Feature: Point and PatchesXuejin ChenReading: Szeliski Chap. 4 2222

2、384.1.2 Feature DescriptorWe know how to detect good points Feature DescriptorsWe know how to detect good pointsNext question: How to match them?Feature DescriptorsLots of possibilities (this is a popular research area)Simple option: match square windows around the point State of the art approach: S

3、IFTDavid Lowe, UBC ?Feature Descriptors Sum of Squared Difference (SSD) Normalized Cross-Correlation (NCC) For small motion: video stereo, tracking Time consuming and sensitive to noise, transforms.210( ()()iiiIIxx( ( )( ( )11iiifgf xfg xgn InvarianceSuppose we are comparing two images I1 and I2I2 m

4、ay be a transformed version of I1Find the same features regardless of the transformation - transformational invarianceMost feature methods are designed to be invariant to Translation, 2D rotation, scaleThey can usually also handleLimited 3D rotations (SIFT works up to about 60 degrees)Limited affine

5、 transformations (some are fully affine invariant)Limited illumination/contrast changesHow to Achieve InvarianceNeed both of the following:Make sure your detector is invariantHarris is invariant to translation and rotationScale is trickiercommon approach is to detect features at many scales using a

6、Gaussian pyramid (e.g., MOPS)More sophisticated methods find “the best scale” to represent each feature (e.g., SIFT)2. Design an invariant feature descriptorA descriptor captures the information in a region around the detected feature pointThe simplest descriptor: a square window of pixels Whats thi

7、s invariant to?Lets look at some better approachesFind dominant orientation of the image patchThis is given by x+, the eigenvector of H corresponding to + is the larger eigenvalueRotate the patch according to this angleRotation Invariance for Feature DescriptorsFigure by Matthew BrownTake 40 x40 squ

8、are window around detected featureScale to 1/5 size (using prefiltering) Rotate to horizontalSample 8x8 square window centered at featureIntensity normalize the window by subtracting the mean, dividing by the standard deviation in the windowMultiscale Oriented PatcheS descriptor8 pixels40 pixelsAdap

9、ted from slide by Matthew BrownIxIi)(Detections at Multiple ScalesBasic idea:Take 16x16 square window around detected featureCompute edge orientation (angle of the gradient - 90) for each pixelThrow out weak edges (threshold gradient magnitude)Create histogram of surviving edge orientationsScale Inv

10、ariant Feature TransformAdapted from slide by David Lowe02angle histogramSIFT DescriptorFull versionDivide the 16x16 window into a 4x4 grid of cells (2x2 case shown below)Compute an orientation histogram for each cell16 cells * 8 orientations = 128 dimensional descriptorAdapted from slide by David L

11、oweProperties of SIFTExtraordinarily robust matching techniqueCan handle changes in viewpointUp to about 60 degree out of plane rotationCan handle significant changes in illuminationSometimes even day vs. night (below)Fast and efficientcan run in real timeLots of code available Histogram of Oriented

12、 Gradients For object recognition Gradients Simplest 1,0,-1 proved best Orientation Binning 0-180, 0-360 Weighted by gradient magnitudes smoothing Block geometries R-HOG (rectangular) C-HOG (circle)PCA-SIFTKe and Sukthankar 2004 39 x 39 patch Image Gradient: Ix, Iy 39x39x2=3042 D vector 3D D vector

13、using principle component analysis Gradient Location-Orientation Histogram (GLOH) Log-polar binning structure instead of four quadrants 17 spatial bins * 16 orientation bins = 272 D PCA - 128 DMikolajczyk and Schmid 2005Best performance overallPerformance of Local Descriptor Comparison in GLOH SIFT

14、othersMikolajczyk and Schmid 2005Many New Descriptors Many newer techniques: tuning parameters. Trained from large database Class- or instance- specific features4.1.3 Feature MatchingGiven a feature in I1, find the best match in I2?Define distance function that compares two descriptorsAll the featur

15、es in I2, find the one with min distanceEfficient data structures and algorithmsdisFeature DistanceHow to define the difference between features f1, f2?Simple approach: SSD(f1, f2) Sum of square differences between entries of the two descriptorsGood scores to ambiguous (bad) matches I1I2f1f2Feature

16、DistanceHow to define the difference between features f1, f2?Better approach: ratio distance = SSD(f1, f2) / SSD(f1, f2)f2 is best SSD match to f1 in I2f2 is 2nd best SSD match to f1 in I2gives small values for ambiguous matchesI1I2f1f2f2Evaluating the ResultsHow can we measure the performance of a

17、feature matcher?5075200feature distanceTrue/False PositivesThe distance threshold affects performanceTrue positives = # of detected matches that are correctSuppose we want to maximize thesehow to choose threshold?False positives = # of detected matches that are incorrectSuppose we want to minimize t

18、hesehow to choose threshold?5075200feature distancefalse matchtrue matchThreshold Performance Evaluation TP: true positives number of correct matches; FN: false negatives matches that were not correctly detected; FP: false positives proposed matches that are incorrect; TN: true negatives non-matches

19、 that were correctly rejected.True/False Positive/Negative Black 1, 2: features Threshold solid circle Green 1: true positive Blue 1: false negative 3: false positive 4: true negative Threshold dashed circle Green 1: true positive Blue 1: true positive 3: false positive 4: false positivePerformance

20、Evaluation Unit rates: True positive rate (TPR) False positive rate (FPR) Positive predictive value (PPV) Accuracy (ACC)TPTPTPRTPFNPTPTNACCPNTPTPPPVTPFPPFPFPFPRFPTNNConfusion MatrixTP=18FP=4P=22FN=2TN=76N=78P=20N=80Total =100TPR=0.90FPR=0.05PPV=0.82ACC=0.94True matches True non-matchesPredicted matc

21、hes Predicted non-matchesIdeally, TPR = 1, FPR =018762080TPTNACCPN1822TPPPVTPFP0.7Evaluating the ResultsHow can we measure the performance of a feature matcher?011false positive ratetruepositiverate# true positives# matching features (positives)0.1# false positives# unmatched features (negatives)For

22、 a specific threshold T-1 0.7Evaluating the ResultsHow can we measure the performance of a feature matcher?011false positive ratetruepositiverate# true positives# matching features (positives)0.1# false positives# unmatched features (negatives)For a specific threshold T-2 0.7Evaluating the ResultsHo

23、w can we measure the performance of a feature matcher?011false positive ratetruepositiverate# true positives# matching features (positives)0.1# false positives# unmatched features (negatives)ROC curve (“Receiver Operator Characteristic”)ROC CurvesGenerated by counting # current/incorrect matches, fo

24、r different thresholdsWant to maximize area under the curve (AUC)Useful for comparing different feature matching methodsFor more info: Close to upper left corner Evaluating the ResultsPrecision-Recall Curve Precision = Positive predictive valueRecall = True positive rate TPTPRecallTPFNPTPTPPreTPFPPP

25、erformance Evaluation Give the distribution, look for the best threshold However, hard to have a clear distribution function Hard to set a best thresholdInter-space distance Distribution of positives and negatives Fixed threshold DB: FN; DC, DE: FP Nearest Neighbor DB: TP; DC: FP Nearest neighbor di

26、stance ratio (NNDR) Small d1/d2 DB: TP; DC, DE: TNThreshold will adapt to different regions of the feature space Trained from large database to get appropriate threshold(Mikolajczyk and Schmid 2005)Performance Evaluation(Mikolajczyk and Schmid 2005)Fixed thresholdPerformance Evaluation(Mikolajczyk a

27、nd Schmid 2005)Nearest neighborPerformance Evaluation(Mikolajczyk and Schmid 2005)NNDRFeature Space Nearest Neighbor Distance Ratio Adaptive threshold based on different regions in feature space Trained from database develop class- or instance-specific feature detectors that maximize discriminabilit

28、y from other classes Compare all features against all others Quadratic, impractical for most applicationsEfficient Matching?Efficient Matching Indexing structure For individual image, or globally for all images Multi-dimensional search tree Hash table Vocabulary tree Efficient Matching Multi-dimensi

29、onal hashing Map descriptor into fixed size buckets When matching, new feature is hashed into a bucket Search for nearby buckets to return potential candidates 123NHaar Wavelets 3D index by performing sum over the quadrants Normalize the 3 values by their expected standard deviations Training An exa

30、mple V_n two nearest bins (of 10) index 23 = 8 bins Query primary 3D bin, k nearest neighbors for further process MOPS, Brown, Szeliski, andWinder (2005)1Haar Wavelets V_n two nearest bins (of 10) index 23 = 8 binsMOPS, Brown, Szeliski, andWinder (2005)2345678nVnVnVnVnVnVnVnVHaar Wavelets Query prim

31、ary 3D bin, k nearest neighbors for further process MOPS, Brown, Szeliski, andWinder (2005)v1 v2 v3Locality Sensitive Hashing (LSH)More Structures Locality Sensitive Hashing Use unions of independently computed hashing functions to index the features Parameter-Sensitive Hashing More sensitive to the

32、 distribution of points in parameter space High-D vectors to binary codes Compared using Hamming distance Accommodate arbitrary kernel functionsPage 232, 233Gionis, Indyk, and Motwani 1999Shakhnarovich, et al,2003Torralba, Weiss, and Fergus 2008;Weiss, Torralba, and Fergus 2008;Kulis and Grauman 200

33、9;Raginsky and Lazebnik 2009KD Tree Multi-dimensional search tree Recursively divide multi-D feature space along alternating axis-aligned hyperplanes Choose the threshold along each axis so as to maximize some criterion (tree balance, maximum depth as small as possible) Query: nearby bins KD Tree(.2

34、2, .56)More complicated caseAdditional Data Structure Slicing Nene and Nayar, 1997 use a series of 1D binary searches on point list sorted along different dimensions to efficiently cull down a list of candidate points that lie within a hypercube of the query point Reweight the matches at different l

35、evels of the indexing tree Grauman and Darrell (2005) Less sensitive to discretization errors in tree construction Metric tree Nistr and Stewnius (2006) A small number of prototypes at each level in a hierarchy Visual words classical information retrieval, fast Indexing Structure Survey and comparis

36、on on indexing structures Muja and Lowe (2009) Kd tree works bestRapid computation of image feature correspondences remains a challenging open research problem!Verification and Densification Geometry alignment to verify Inliers and outliers RANSAC, Random sampling Will be discussed further in next s

37、ections 4.1.4 Feature Tracking4.1.4 Feature Tracking Detect and track: for video tracking applications Detect in one then search in others The expected amount of motion and appearance deformation between adjacent frames in expected to be small Subsequent frames SSD works well4.1.4 Feature Tracking0)

38、,() 1,(tyxItvyuxIframe tframe t+1) 1,(tvyux),(tyxvu4.1.4 Feature Tracking Subsequent frames SSD works well NCC is better if there is brightness change Hierarchical search strategy when search range is large: matches in lower resolution images to provide better initial guesses and speed up the search

39、image Iimage JGaussian pyramid of image It-1Gaussian pyramid of image Iimage Iimage It-1Coarse-to-fine optical flow estimationrun iterative L-Krun iterative L-Kwarp & upsample.4.1.4 Feature Tracking Long image sequence: large appearance change Whether to continue matching against the originally

40、detected patch or Re-sample each subsequent frame at the matching location Match and warp KLT tracker Fails when the original patch appearance changes such as foreshorteningRisk: features drift from its original locationKanadeLucasTomasi (KLT) tracker Affine motion model Compare patches in neighbori

41、ng frames using a translational model Use the location to initialize an affine registration between the patch in the current frame and the base frame The area around the predicted feature location is searched with an incremental registration algorithm (Shi and Tomasi 1994)Detect new features in regi

42、ons where the tracking has fail.OpenCV Examples calcOpticalFlowPyrLK()OpenCV Examples cvGoodFeatureToTrack()calcOpticalFlowPyrLK()A lot of Expansions Tracking combined with structure from motion Tie together the corners Tracking in video with large number of moving objects or points Special purpose

43、recognizer: Learning algorithms Train classifiers on sample patches and their affine deformation, fast and reliable, fast motion is supported Survey (Yilmaz, Javed, and Shah 2006)Page 236Real-time head tracking using the fast trained classifiers of Lepetit, Pilet, and Fua (2004) 2004 IEEE.Applicatio

44、n: Performance-driven animation Expression and head tracking Morph among a series of hand-drawn sketchesBuck, Finkelstein, Jacobs et al. (2000)Performance-Driven Animation An animator first extracts the eye and mouth regions of each sketch and draws control lines over each image Performance-Driven A

45、nimation An animator first extracts the eye and mouth regions of each sketch and draws control lines over each image At run time, a face-tracking system (Toyama 1998) determines the current location of these features. Performance-Driven Animation An animator first extracts the eye and mouth regions of each sketch