Lecture 5 Notes: TTC and FOR MontiVision Demos, Vanishing Point, Use of VPs in Camera Calibration

6.801/6.866: Machine Vision, Lecture 5 1 Lecture 5: TTC and FOR Montivision Demos, Vanishing Point, Use of VPs in Camera Calibration In this lecture, we’ll continue going over vanishing points in machine vision, as well as introduce how we can use brightness estimates to obtain estimates of a surface’s orientation. We’ll introduce this idea with Lambertian surfaces, but we can discuss how this can generalize to many other types of surfaces as well. 1.1 Robust Line Estimation and Sampling We’ll start by covering some of the topics discussed during lecture. 1.1.1 Line Intersection Least-Squares Helpful when considering multiple lines at a time - this optimization problem is given by: X min (x cos θi + y sin θi − ρ)2 x,y 1.1.2 (1) i Dealing with Outliers Many of the approaches we’ve covered thus far are centered around the idea of making estimates from data. But recall that the data gathered by sensors can be noisy, and can be corrupted from phenomena such as crosstalk. Because of this noise, it is advantageous to distinguish and filter outliers from the inliers in our dataset, especially when we make estimates using Least-Squares. A good choice of algorithm for dealing with outliers is RANSAC, or Random Sample Consensus [1]. This algorithm is essentially an iterative and stochastic variation of Least-Squares. By randomly selecting points from an existing dataset to fit lines and evaluate the fit, we can iteratively find line fits that minimize the least-squares error while distinguishing inliers from outliers. 1 Figure 1: Pseudocode for the RANSAC Algorithm. 1.1.3 Reprojection and Rectification These two problems are highly important in mapmaking, and help for solving the equations: Rr = r0 (2) T r=R r (3) Where r is the vector from the Center of Projection (COP) to the image plane. 1.1.4 Resampling Resampling is also a valuable application in many facets of computer vision and robotics, especially if we seek to run any kind of interpolation or subsampling algorithms. Some approaches for this: • Nearest Neighbor: This is a class of methods in which we interpolate based off of the values of neighboring points. This can be done spatially (e.g. by looking at adjacent pixels) as well as other image properties such as brightness and color. A common algorithm used here is K-Nearest Neighbors (KNN), in which interpolation is done based off of the K-nearest points in the desired space. • Bilinear Interpolation: An extension of linear interpolation used for functions in two-dimensional grids/of two variables (e.g. (x, y) or (i, j))) [2], such as the brightness or motion in images. • Bicubic Interpolation: Similar to bilinear interpolation, bicubic interpolation is an extension of cubic interpolation of functions in two-dimensional grids/of two variables (e.g. (x, y) or (i, j))) [3], such as the brightness or motion in images. Bicubic interpolation tends to perform much better than bilinear interpolation, though at the cost of additional computational resources. 1.2 Magnification with TTC • For the Montivision demo, note the following for the bars: – A → x-dimension for motion estimation problem – B → y-dimension for motion estimation problem – C→ 1 Time to Contact • Recall from the previous lectures that the percent change of size in the world is the percent change of size in the image. We can derive this through perspective projection. The equation for this is: s S = f Z (4) Where s is the size in the image plane and S is the size in the world. Differentiating with respect to time gives us (using the chain rule): d ds dZ (sZ = f S) → Z +s =0 dt dt dt 2 (5) Rearranging terms: dz dt ds = − dt Z S (6) Recall that the intuition here is that the rate of change of size is the same in the image and the world. 1.2.1 Perspective Projection and Vanishing Points Let’s begin by defining a few terms. Some of these will be a review, but these review terms connect to new terms that we’ll introduce shortly: • vanishing points: These are the points in the image plane (or extended out from the image plane) that parallel lines in the world converge to. • Center of Projection (COP): This is where in the camera/sensor (not in the image plane) where incident projected light rays converge. An analog to the COP for human vision systems is your eyes. NOTE: COP and vanishing points are oftentimes different. • Principle Point: The orthogonal projection of the Center of Projection (COP) onto the image plane. • f : Similar to the focal length we’ve seen in other perspective projection examples, this f is the perpendicular distance from the COP to the image plane. Recall that a common problem we can solve with the use of vanishing points is finding the Center of Projection (COP). Solving this problem in 3D has 3 degrees of freedom, so consequently we’ll try to solve it using three equations. Intuitively, this problem of finding the Center of Projection can be thought of as finding the intersection of three spheres, each of which have two vanishing points along their diameters. Note that three spheres can intersect in up to two places - in this case we have defined the physically-feasible solution, and therefore the solution of interest, to be the solution above the image plane (the other solution will be a mirror image of this solution and can be found below the image plane). Application of this problem: This problem comes up frequently in photogrammetry, in that simply having two locations as your vanishing points isn’t enough to uniquely identify your location on a sphere. 1.2.2 Lines in 2D and 3D Next, let’s briefly review how we can parameterize lines in 2D and 3D: • 2D: (2 Degrees of Freedom) – y = mx + c – ax + by + c = 0 – sin θx − cos θy + ρ = 0 Δ – If n̂ = (− sin θ, cos θ)T , then n̂ · r = ρ. • 3D: (3 Degrees of Freedom) – n̂ = ρ – aX + bY + cZ + d = 0 1.2.3 Application: Multilateration (MLAT) This problem comes up when we estimate either our position or the position of other objects based off of Time of Arrival [4]. One specific application of this problem is localizing ourselves using distances/Time of Arrival of wifi access points inside buildings/other locations without access to GPS. Like the other problems we’ve looked at, this problem can be solved by finding the intersection of 3 spheres. Let’s begin with: ||r − ri ||2 = pi ∀ i ∈ {1, · · · , N } 3 (7) Next, let’s square both sides of this equation and rewrite the left-hand side with dot products: ||r − ri ||22 = (r − ri )T (r − ri ) = p2i = r · r − 2r · ri + ri · ri = (8) pi2 (9) Recall from Bezout’s Theorem that this means that are 8 possible solutions here, since we have three equations of second-order polynomials. To get rid of the 2nd order terms, we simply subtract the equations: r · r − 2r · ri + ri · ri = ρ2i − r · r − 2r · rj + rj · rj = ρ2j (10) ∀ i, j ∈ {1, 2, 3}, i 6= j (11) Subtracting these pairs of equations yields a linear equation in R: 2r(rj − ri ) = (ρ2j − ρ2i ) − (Rj2 − Ri2 ) (12) Δ (Where the scalar Rj2 = rj · rj .) Putting these equations together, this is equivalent to finding the intersection of three different spheres: ⎡ ⎤ ⎡ 2 ⎤ (r2 − r1 )T (ρ2 − ρ21 ) − (R22 − R12 ) 1 ⎢ ⎥ ⎣ r3 − r2 )T ⎦ r = ⎣(ρ23 − ρ22 ) − (R32 − R22 )⎦ 2 T (ρ21 − ρ23 ) − (R12 − R32 ) r 1 − r3 ) (13) However, even though we’ve eliminated the second-order terms from these three equations, we still have two solutions. Recall from linear algebra equations don’t have a unique solution when there is redundancy or linear dependence between the equations. If we add up the rows on the right-hand side of the previous equation, we get 0, which indicates that the matrix on the left-hand side is singular: ⎡ ⎤ (r2 − r1 )T Δ ⎢ ⎥ (14) A = ⎣ r3 − r2 )T ⎦ ∈ R3×3 r1 − r3 )T To solve this linear dependence problem, we again use Bezout’s Theorem and keep one of the second-order equations: (r − r1 ) · (r − r2 ) = 0 (15) (r − r2 ) · (r − r3 ) = 0 (16) (r − r2 ) · (r − r2 ) = 0 → (r − r2 ) ⊥ (r3 − r1 ) (17) I.e. the plane passes through r2 - this intersecting point is the solution and is known as the orthocenter or the principal point. Now, all we need is to find the quantity f to find the Center of Projection. Next, note the following relations between the vanishing points in the inverse plane and ẑ, which lies perpendicular to the image plane: r1 · ẑ = 0 (18) r2 · ẑ = 0 (19) r3 · ẑ = 0 (20) What else is this useful for? Here are some other applications: • Camera calibration (this was the example above) • Detecting image cropping - e.g. if you have been cropped out of an image • Photogrammetry - e.g. by verifying if the explorer who claimed he was the first to make it “all the way” to the North Pole actually did (fun fact: he didn’t). Next, now that we’ve determined the principal point, what can we say about f (the “focal length”)? For this, let us consider the 3D simplex, which is Δ  e1 = 1 0 Δ  e2 = 0 1 Δ  e3 = 0 0 triangular surface in R3 given by the unit vectors: T 0 T 0 T 1 4 (21) (22) (23) Using this 3D simplex, let us suppose that each side of the triangles formed by this√ simplex take length v = √ consistent with the l2 norm of the triangles spanned by the unit simplex ( 12 + 12 = 2). √ 2, which is Next, we solve for f by finding the value of a such that the dot product between the unit vector perpendicular to the simplex and a vector of all a is equal to 1: iT  T h 1 √ √1 √1 a a a =1 (24) 3 3 3 3a √ =1 3 √ 3 1 a= =√ 3 3 (25) (26) This value of a = √13 = f . Then we can relate the lengths of the sides v (which correspond to the magnitudes of the vectors between the principal point and the vanishing points (||r − ri ||2 )) and f : v= √ 1 v 2, f = √ =⇒ f = √ 3 6 (27) With this, we’ve now computed both the principal point and the “focal length” f for camera calibration. 1.2.4 Application: Understand Orientation of Camera w.r.t. World For this problem, the goal is to transform from the world frame of reference to the camera frame of reference, i.e. find a frame of reference such that the unit vectors x̂c , ŷc , ẑc have the following orthogonality properties: x̂c · ŷc ≈ 0 (28) c c (29) c c (30) ŷ · ẑ ≈ 0 x̂ · ẑ ≈ 0 (Note that the c superscript refers to the camera coordinate system.) If the location of the Center of Projection (COP) is given above the image plane as the vector pc and the vanishing points are given as vectors rc1 , rc2 , and rc3 (note that these vanishing points must be in the same frame of reference in order for this computation to carry out), then we can derive expressions for the unit vectors through the following relations: pc − r1c ||pc − r1c ||2 pc − rc2 (pc − r2 ) //ŷc =⇒ ŷc = ||pc − r2c ||2 pc − rc3 (pc − r3 ) //ẑc =⇒ ẑc = ||pc − r3c ||2 (pc − r1 ) //x̂c =⇒ x̂c = (31) (32) (33) Then, after deriving the relative transformation between the world frame (typically denoted w in robotics) and the camera frame (typically denoted c in robotics), we can express the principal point/Center of Projection in the camera coordinate frame: r = αx̂c + βŷc + γẑc (34) Where (α, β, γ) are the coordinates in the object coordinate system (since x̂c , ŷc , and ẑc comprise the orthogonal basis of this coordinate system). Then we can express the relative coordinates of objects in this coordinate system:  T r0 = α β γ (35) To transform between frames, we can do so via the following equation: ⎡ ⎤ −(x̂c )T ⎢ ⎥ r = ⎣−(ŷc )T ⎦ r0 −(ẑc )T ⎡ (36) ⎤ −(x̂c )T Δ ⎢ ⎥ Note that the matrix defined by: R = ⎣−(ŷc )T ⎦ is orthonormal, since these vector entries are orthogonal to one another. c T −(ẑ ) This matrix R is a rotation matrix, which means it is skew-symmetric, invertible, and its transpose is equal to its inverse: 5 R−1 = RT . Therefore, if we wanted to solve the reverse problem that we did above (finding object coordinates from camera coordinates), we can do so by simply taking the transpose of the matrix: ⎡ ⎤−1 −(x̂c )T ⎢ ⎥ r0 = ⎣−(ŷc )T ⎦ r (37) c T −(ẑ ) ⎡ ⎤T −(x̂c )T ⎢ ⎥ = ⎣−(ŷc )T ⎦ r (38) c T −(ẑ ) 1.3 Brightness We’ll now switch to the topic of brightness, and how we can use it for surface estimation. Recall that for a Lambertian surface (which we’ll assume we use here for now), the power received by photoreceptors (such as a human eye or an array of photodiodes) depends both on the power emitted by the source, but also the angle between the light source and the object. However, the brightness of the object does not depend on the viewing angle between the object and the viewer. This is relevant for foreshortening (the visual effect or optical illusion that causes an object or distance to appear shorter than it actually is because it is angled toward the viewer [6]): the perceived area of an object is the true area times the cosine of the angle between the light source and the object/viewer. Definition: Lambertian Object: An object that appears equally bright from all viewing directions and reflects all incident light, absorbing none [5]. Let’s look at a simple case: a Lambertian surface. If we have the brightness observed and we have this modeled as: E = n̂ · s, (39) Where s is the vector between the light source and the object, then can we use this information to recover the surface orientation given by n̂. This unit vector surface orientation has degrees of freedom, since it is a vector in the plane. It is hard to estimate this when just getting a single measurement for brightness. But what if we test different lighting conditions?: E1 = n̂ · s1 E2 = n̂ · s2 (40) n̂ · n̂ = ||n̂||2 = 1 (42) (41) This is equivalent, intuitively, to finding the intersection between two cones for which we have different angles, which forms a planar curve. We then intersect this planar curve with the unit sphere corresponding to the constraint ||n̂||2 = 1. By Bezout’s Theorem, this will produce two solutions. One problem with this approach, however, is that these equations are not linear. We can use the presence of reflectance to help us solve this problem. Let us define the following: Definition: Albedo: This is the ratio of power out of an object divided by power into an object: Δ Δ “albedo” = ρ = power in ∈ [0, 1] power out (43) Though the definition varies across different domains, in this class, we define albedo to be for a specific orientation, i.e. a specific si . Fun fact: Although an albedo greater than 1 technically violates the 2nd Law of Thermodynamics, superluminous surfaces such as those sprayed with flourescent paint can exhibit ρ > 1. Using this albedo term, we can now solve our problem of having nonlinearity in our equations. Note that below we use three different measurements this time, rather than just two: E1 = ρn̂ · s1 E2 = ρn̂ · s2 (44) E3 = ρn̂ · s3 (46) (45) 6 This creates a system of 3 unknowns and 3 Degrees of Freedom. We also add the following constraints: n = ρn̂ n n̂ = ||n||2 Combining these equations and constraints, we can rewrite the above in matrix/vector form: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ −ŝ1T −ŝT1 E1 E1 Δ ⎢ ⎢ T⎥ ⎥ −1 ⎣−ŝ2 ⎦ n = ⎣E2 ⎦ =⇒ n = S ⎣E2 ⎦ (Where S = ⎣−ŝT2 ⎦ .) T T E3 E3 −ŝ3 −ŝ3 (47) (48) (49) A quick note on the solution above: like other linear algebra-based approaches we’ve investigated so far, the matrix S above isn’t necessarily invertible. This matrix is not invertible when light sources are in a coplanar orientation relative to the object. If this is the case, then the matrix S becomes singular/linearly dependent, and therefore non-invertible. 1.3.1 What if We Can’t use Multiple Orientations? In the case where the orientation of the camera, object, and light source cannot be changed (i.e. everything is fixed), or if it is expensive to generate a surface estimation from a new orientation, then another option is to use different color sensors. Most cameras have RGB (“Red-Green-Blue”) sensors, and thus we can use the same approach as above, where each color corresponds to a different orientation. This RGB approach has a few issues: • RGB has “crosstalk” between color channels (it can be hard to excite/activate a single channel for color without exciting the others as well). • The object may not be uniformly-colored (which, practically, is quite often the case). However, despite the drawbacks, this approach enables us to recover the surface orientation of an object from a single RGB monocular camera. A final note: we originally assumed this object was Lambertian, and because of this used the relation that an object’s perceived area is its true area scaled by the cosine of the angle between the light source and the object, Does this apply for real surfaces? No, because many are not ideal Lambertian surfaces. However, in practice, we can just use a lookup table that can be calibrated using real images. 1.4 References 1. RANSAC Algorithm: http://www.cse.yorku.ca/~kosta/CompVis Notes/ransac.pdf 2. Bilinear Interpolation: https://en.wikipedia.org/wiki/Bilinear interpolation 3. Bicubic Interpolation: https://en.wikipedia.org/wiki/Bicubic interpolation 4. Multilateration: https://www.icao.int/Meetings/AMC/MA/2007/surv semi/Day02 SENSIS Turner.pdf 5. Lambertian Surface: Robot Vision, Page 212 6. Foreshortening: https://en.wikipedia.org/wiki/Perspective 7