Combining Appearanceand Topology for WideBaseline MatchingDennis Tell and Stefan CarlssonPresented by: Josh WillsImage Point Correspondencesn Critical foundation for many vision applications® 3-D reconstruction, object detection/recognition, etcn Trivial problem for the human visual systemn Extremely difficult problem computationallyCorrespondencesn Correspondences are pairsof points (one from theleft image and one fromthe right image) thatcorrespond to the samereal world point.n They are oftenrepresented by point-linepairs in a set of images.Difficulties in matchingn Many matches are only available via higher levelreasoning® This perceived match “disappears” locallyn Matches may rely on previous knowledge of objects® We understand what a given object would look like fromvarying viewpoints and lighting conditionsPrevious Workn Invariant descriptors® Schmid and Mohr - Affine invariant descriptors® Belongie - shape contextsn Intensity profiles® Tell and Carlssonn Robust model estimation® Torr - RANSACPresentation Outlinen Common approach to matchingn Intensity Profilesn Topological Constraintsn Resultsn DiscussionCommon approach to matchingn Locate interest points® Harris cornersn Attach a descriptor to each point and compute a measureof similarity for each pair of points® Normalized correlation on intensityn Choose candidate matches® Maximum similarity or Hungariann Validate matches using robust estimation® RANSAC for homography or fundamental matrixInterest Pointsn Many of the pixels in animage are redundant.n Computation is expensiveso we want a set of pointsthat are “interesting”n The types of points we arelooking for are thosecentered in rank 1 or 2neighborhoodsHarris Corner Detectorn For each point, compute “corner-ness” for an image patchcentered on that point:n Where k is routinely 0.04n Keep all points above some threshold® When trace is large there is an edge (rank 1)® When determinant is large there is an edge or corner (rank 1 or 2)Point Descriptorsn Local v. Relationaln Local point descriptors attempt to capture the appearanceof a small patch of the image centered on a given point.® Gray values® Filter responsesn With relational point descriptors, a point is characterizedby its relation to the other points in the scene.® Shape contextsGray value point descriptorsn The gray values in a smallneighborhood centered on apoint may be strung out as afeature vector for that point.n These vectors may becompared using SSD or crosscorrelationsn These descriptors allow forvery efficient comparison ofpoints, but have littleinvariance to changes betweenthe two imagesFilter-based point descriptorsn A set of oriented filters areapplied to each image and theresponse of each filter at agiven point results in anothertype of feature vector.n This allows for moreinvariance to absolute intensityand a degree of rotationalinvariance is possible bycyclically rotating the featurevectors.Shape contextsn The points are classified bytheir positional relation to theother points in the image.n Log polar histograms arecentered on each point and thechi-squared score for each pairis computed.n There is a degree ofaffine/rotational invariance inusing this point descriptorValidating Point Matchesn Due to the difference of appearance in the two images andthe limitations of the point matching approaches,mismatches are all but guaranteed.n One method for sifting out these mismatches is to fit animage relation model to the data and see which matchesare consistent with the estimated model.n Robust estimation is used to stifle the effect of outliers onthe model estimation.Robust Estimationn What set of modelparameters best“explains” the data?n Here, what a and b valuesin the equation for a lineresult in the best fit to thispoint set which is knownhave outliers?Least Squaresn Try to minimize thesquared error for each ofthe points in the point setn Very fast and efficientn Highly influenced byoutliers - notice the effectof the outlier on the rightRANSAC - Random Sample Consensusn Find the parameters that resultsin the largest number of“inliers” - points that fit themodeln Repeatedly choose samples ofthe minimal size, recover theappropriate model, and countinliersn P.H.S. Torr brought this tocomputer visionEstimation for image relationsn This same approach isapplied to the estimationof the image relation.n Here we seen theapplication of ahomography that wascomputed via RANSAC.n The outliers are shown inred.Homographyn Circular order-preservingtransformation® Similarity: anglepreserving® Affine: parallel-linepreservingn Also the space oftransformations that arepossible with perspectiveeffects on a planeDescription of the Approachn Extract interest points with Harris corner detectorn For each intra-image pair of points, extract the intensity profilejoining themn Compare each inter-image pair of profiles’ Fourier feature vectorsand add votes for the endpoints of similar profilesn Perform String matching to ensure one-to-one matching and topreserve cyclic ordern Using RANSAC, eliminate more outliers and find homographyand/or fundamental matrixPlanar Assumptionn For intensity profiles to bereliable and for thepreservation of cyclicorder, image regions mustbe related by ahomography.n This requires that theregions correspond toreal-world planar objects.Intensity Profilesn Invariant to affinetransformations if the profile ison a planar surface.n For many perspectivetransformations, there is anaffine approximation that isclose for a given 1D line.n The only difference will be achange in scale an possiblysome high frequency variation.Fourier Feature Vectorsn These features are chosen primarily for their scaleinvariance and invariance to high-frequency noise.n Choose N for N/2 sin and cos basis functionsIntensity Profile Matchingn Matches constitute votes for the correspondences of thevertices of the intensity profilesDrawbacks of the OriginalMethodn Biased voting - points with “common” intensityprofiles may receive superfluous votes forcorrespondences in the vote matrixn Only local information - matches that areambiguous using only local information may beunique when considering relational data.Biased votingn The point p would have 4 votes for a match with itself,but it would have 6 votes for a match with q.n This can be solved by enforcing a one-to-one constrainton the votes.Local and Topological featuresn Another drawback of the original paper is that it doesn’t use some