10/19/2001 CS 461, Copyright G.D. HagerComputer Vision, Lectures 13,14Professor Hagerhttp://www.cs.jhu.edu/~hager10/19/2001 CS 461, Copyright G.D. HagerOutline for Today• Stereo geometry• Stereo matching• Stereo evaluation article10/19/2001 CS 461, Copyright G.D. HagerEPIPOLAR GEOMETRY: DERIVATIONPlPrTPr= R(Pl–T)(Pl– T) ·(T x Pl)= 0PrtR (T x Pl) = 0PrtE Pl = 0where E = R sk(T)0 -Tz Tysk(T) = Tz0 -Tx-Ty Tx0The matrix E is called the essentialmatrix and completely describes theepipolar geometry of the stereo pair10/19/2001 CS 461, Copyright G.D. HagerEPIPOLAR GEOMETRY: DERIVATIONPlPrTPr= R(Pl–T)prtE pl = 0Note that E is invariant to the scaleof the points, therefore we also havewhere p denotes the (metric) imageprojection of PNow if H denotes the internalcalibration, converting from metricto pixel coordinates, we have furtherthatrrtH-tE H-1rl= rrtF rl = 0where r denotes the pixel coordinatesof p. F is called the fundamental matrix10/19/2001 CS 461, Copyright G.D. HagerEPIPOLAR GEOMETRY: COMPUTATIONprtE pl = 0 or rrtFrl= 0Note that, given a correspondence, we can form a linearconstraint on E (or F). Both E and F are only unique upto scale, therefore we need 9-1 = 8 matches, then we canform a system of the formC e = 0 where e is the vector of 9 values in EUsing SVD, we can write C = U D VtE (or F) is the column of V corresponding to the least singularvalue of C.E (or F) is supposed to be rank deficient; to enforce this, wecan compute the SVD of E (or F), set the smallest singularvalue to 0, then multiply the components to get the corrected FWHY?10/19/2001 CS 461, Copyright G.D. HagerEPIPOLAR GEOMETRY: RECONSTRUCTIONprtE pl = 0 or rrtFrl= 0One additional useful fact is that we can use epipolar geometry for reconstruction.First, note that EtE involves only translation and thattr(EtE) = 2 ||T||2So, if we normalize by sqrt(tr(EtE)/2), we compute and new matrix E’ which has unit norm translation T’ up to sign.We can solve for T’ from E’ (or T from E for that matter)Now define wi= E’i x T’ and Ri = wi+ wjx wkThe three values of Ri for all combinations of 1,2,3 arethe rows of the rotation matrix.10/19/2001 CS 461, Copyright G.D. HagerEPIPOLAR GEOMETRY: STEREO CORRESPONCEprtE pl = 0 or rrtFrl= 0One of the important uses of epipolar geometry is thatit greatly reduces the complexity of stereo. Given a match in the left image, the appropriate place to look for a match in the right is along the corresponding epipolar line.Alternatively, it is possible to use epipolar structure to warpthe image to have parallel epipolar geometry, making stereosearch a trivial scan-line search.10/19/2001 CS 461, Copyright G.D. HagerUsing E to get Nonverged Stereo• From E we get R and T such that lp = lRrrp + lTk• Note that T is really the direction we’d like the camera baseline to point in.• Let Rx= T• Let Ry= (0,0,1) x T / |T x (0,0,1)|• Let Rz= Rxx Ry• Now, R = [Rx,Ry,Rz]’ takes point from the left camera to a nonverged camera system, so we have•newlR= R, newrR= R lRr – (note the book uses the transpose of this, i.e. the rotation of the frame rather than the points)10/19/2001 CS 461, Copyright G.D. HagerTHE FUNDAMENTAL MATRIX AND RECONSTRUCTIONprtE pl = 0 or rrtFrl= 0If we do not know the internal parameters, then the 8 point algorithm can only be used to compute F. Unfortunately, F has less structure; what we can showis that we can only reconstruct up to a projective transformation (but we won’t cover that).10/19/2001 CS 461, Copyright G.D. HagerEPIPOLAR GEOMETRY: RECTIFICATIONprtE pl = 0 or rrtFrl= 0Putting all this together, we get the following algorithm:1. Find 8 or more correspondences and compute E (note we need internal parameters to do this).2. Given E, compute T’ and R.3. Given T’ and R, compute rotations into a non-verged system4. Rectify the images using these rotations10/19/2001 CS 461, Copyright G.D. HagerRIGHT IMAGEPLANELEFT IMAGEPLANERIGHTFOCALPOINTLEFTFOCALPOINTBASELINEdFOCALLENGTHfBINOCULAR STEREO SYSTEM• Correspondence Problem is a key issue for binocular stereo --namely identify image features in respective images that correspond to exactly the same world object point.• Clearly localization of image features (e.g., edges) is of critical importance to 3D measurement accuracy. (2D topdown view)10/19/2001 CS 461, Copyright G.D. HagerComputing the Disparity Range• The first step in correspondence search is to compute the range of disparities to search– The horopter is the set of distances which have disparity zero (or very close to zero) for a verged system. Human stereo only takes place within the horopter.• We can assume a non-verged system. Therefore, we have–ul–ur= f b/z– substitute ur= ul+ ∇ d Æ δ d = f b/z– given a range zminto zmax, we calculate• ∇ dmin= f b / zmax• ∇ dmax= f b/ zmin• Thus, for each point ulin the left image, we will search points ul+ ∇dminto ul+ ∇ dmaxin the right.• Note we can turn this around and start at a point urand search from ur- ∇ dmaxto ur- ∇ dmin10/19/2001 CS 461, Copyright G.D. HagerMATCHING AND CORRESPONDENCE• Two major approaches– feature-based– region basedIn feature-based matching, the idea is to pick a feature type (e.g. edges), define a matching criteria (e.g. orientation and contrast sign), and then look for matches within a disparity range23222120)()()()(1rlrlrlrlccwoowmmwllwS−+−+−+−=10/19/2001 CS 461, Copyright G.D. HagerMATCHING AND CORRESPONDENCE• Two major approaches– feature-based– region basedIn region-based matching, theidea is to pick a region in the image and attempt to find the matching region in the second image by maximizing the some measure:1. normalized SSD2. SAD3. normalized cross-correlation10/19/2001 CS 461, Copyright G.D. HagerRegion Matching• For each pixel (i,j) of the left image and offset ∇ i,∇ j in disparity range– compute d(∇ i,∇ j) = ∑k,lψ(Il(i+k,j+l),Ir(i+k+∇ i,j+l+∇ j))– the disparity is the value (∇ i,∇ j) that minimizes d• The result of performing this search over every pixel is the disparity map.• Often, this map is computed at different scales, by performing reduction using a Gaussian pyramid10/19/2001 CS 461, Copyright G.D. HagerMatching Metrics• An obvious solution: minimize the sum of squares– think of R and R’ as a region and a candidate region in vector form– SSD = || R – R’ ||2= || R ||2–2 R . R’ + || R’ ||^2– Note that we