Correlation and Epipolar GeometryCS664 Machine Vision Lecture #12October 16, 2001Lecturer: Professor R. ZabihScribe: Jeff Hoy I. Administrative·Assignment 2 posted on web, due 10/30/01·Quiz in lecture, 10/23/01·Individual presentations will take place some Wednesday in NovemberII. Matching Under Gain and BiasGoal: find disparity information in images where gain and bias is presentGain – Multiplicative transformationBias – Additive transformationPossible solution: add new gain and bias labels to disparity labels and solveProblem: Quickly becomes intractableBetter solution: Correlation of paired dataSimplest Example: no gain, no bias, no nearby discontinuities, some Gaussian noise: More complicated example: Allow gain and bias. Best-fit will still be a line, this timewith varied slope and non-zero y-intercept:If there is no correspondence between images, the graph will be random garbage.If the slope of the line is negative, the second image would be a photographic negative.Pearson’s Correlation Coefficient+1 = r = -1r > 0 represents positive slope, r < 0 represents negative slope, and r = 0 means randomgarbage (no correlation).Covarience: r is called the Normalized Coefficient. It is much like computing L2 distance. It isnon-robust on edges and it doesn’t tolerate outliers.III. Non-Parametric StatisticsDistribution-free, takes advantage of ordering informationGiven a set (xi, yi) in any non-Gaussian, “God Knows What” distribution, replacing thepixel intensities with their intensity rank creates a known distribution. Gain and biashave no effect upon this order. The ranking reduces the effect of outliers. It is not a great method for low-textureareas (few measures are).Spearman Correlation - Use Pearson’s Correlation but use intensity ranks rather thanactual intensities. This actually calculates:This is a non-robust measure, but that is acceptable because there are no significantoutliers in the ranks. It gives a perfect score to any monotonic function.Problem: slow. Can’t use dynamic programming tricks.Fix: Rank Transform – count the number of pixels that are darker in a given window. Do this for all pixels, then use correlation. This can be done fast.Kendall’s t - points (a, b) and (c, d) lie on monotonically increasing function. Theyare concordant if:(a < c ? b < d) V (a > c ? b > d)Kendall’s t counts the number of concordant pairs. More pairs indicates morecorrelation.Problem: same as before, slow.Census Transform – world’s fastest stereo computations, can be done in real timeusing specialized hardware.Idea: for each pixel, create a bit-string of comparisons to other pixels. 0 indicatesdarker, 1 otherwise. Then compare strings using Hamming Distance (XOR and count).Sparse vs. Dense Output – only compute disparities for a few important pixels. Othervalues can be determined from these.Why do this? May be faster and more accurate since looking at fewer pixels. Itmeasures correspondence only at “interesting” points: edges, corners, features.Problem: Can’t use dynamic programming. Also generally less accurate due to lessinformation, less robust. It can work well in certain situations.IV. Epipolar GeometryIf we had perfect information with a certain number of points, how many points wouldwe need?Consider two cameras C1 and C2, and three pixels P1, P2, and P3. The image of a rayfrom C1 to P1 will be the search space for P1 in C2View from C2The lines converge to hit camera 1. The point where the lines meet in C2 is called theEpipole – Image of C1’s center in C2. If both cameras are looking straight ahead thelines are parallel and the Epipole is at infinity.A scene point and C1 and C2 create an Epipolar PlaneEpipolar Line – Intersection of epipolar plane and imaging surface. All epipolarplanes intersect to create a pencil of planes.In stereo vision, epipolar lines are horizontal. Epopolar geometry can be represented inmatrix form – the Fundamental matrix and the Essential matrix.(To be continued in lecture 13)Relation of Epipolar Geometry to Sparse Correspondence – When trying tocompute motion, you can take a few points and solve for the Fundamental andEssential matrices. Then you have a sense of the relative motion of the