Lecture 2 Notes: Image Formation, Perspective Projection, Time Derivative, Motion Field

6.801/6.866: Machine Vision, Lecture 2 1 Lecture 2: Image Formation, Perspective Projection, Time Derivative, Motion Field Definition of perspective projection: X y Y x = , = (component form) f Z f Z 1 1 r= R (vector form) f R · ẑ (1) (2) If we differentiate these perspective projection equations: 1 dX X dZ 1 dx = − 2 f dt Z dt Z dt What are these derivatives? They correspond to velocities. Let’s define some of these velocities: ∆ dx dt • u= ∆ dy dt • v= ∆ dX dt • U= ∆ dY dt • V = ∆ dZ dt • W = Now, rewriting the differentiated perspective projection equations with these velocity terms, we first write the equation for the x component: 1 1 X u = U − 2W f Z Z (3) 1 Y 1 v = V − 2W f Z Z (4) Similarly, for y: Why are these equations relevant? They allow us to find parts of the image that don’t exhibit any motion - i.e. stationary points. Let’s find where U = V = 0. Let the point (x0 , y0 ) correspond to this point. Then: x0 U y0 V = , = f W f W (5) 1 Focus of Expansion (FOE): Point in image space given by (x0 , y0 ). This point is where the 3D motion vector intersects with the line given by z = f . Why is FOE useful? If you know FOE, you can derive the direction of motion by drawing a vector from the origin to FOE. Additionally, we can rewrite the differentiated perspective projection equations with FOE: 1 x0 − x W 1 y0 − y W u= (x comp.), v= (y comp.) f f Z f f Z (6) Cancelling out the focal length (f ) terms: u = (x0 − x) W W (x comp.), v = (y0 − y) (y comp.) Z Z (7) A few points here: • You can draw the vector diagram of the motion field in the image plane. • All vectors in the motion field expand outward from FOE. • Recall that perspective projection cannot give us absolute distances. For building intuition, let’s additionally consider what each of these quantities mean. The inverse term meters meters second Z W = Z dZ dt has units of = seconds - i.e. Time of Impact. Let’s now revisit these equations in vector form, rather than in the component form derived above: 1 R d 1 dr = − (R · r̂) f dt R · ẑ (R · r̂)2 dt (8) Let’s rewrite this with dots for derivatives. Fun fact: The above notation is Leibniz notation, and the following is Newtonian notation: 1 R 1 ṙ = Ṙ − (Ṙ · ẑ) f R · ẑ (R · ẑ)2 (9) 1 1 1 ṙ = (Ṙ − W r) f Z f (10) One way for reasoning about these equations is that motion is magnified by the ratio of the distance terms. Next, we’ll reintroduce the idea of Focus of Expansion, but this time, for the vector form. FOE in the vector form is given at the point where ṙ = 0: 1 1 ṙ = Ṙ f W (11) We can use a dot product/cross product identity to rewrite the above expression in terms of cross products. The identity is as follows for any a, b, c ∈ Rn a × (b × c) = (c · a)b − (a · b)c (12) Using this identity, we rewrite the expression above to solve for FOE: 1 1 ṙ = (ẑ × (Ṙ × R)) f (R · ẑ)2 (13) What is this expression? This is image motion expressed in terms of world motion. Note the following identities/properties of this motion, which are helpful for building intuition: • ṙ · ẑ = 0 =⇒ Image motion is perpendicular to the z-axis. This makes since intuitively because otherwise the image would be coming out of/going into the image plane. • ṙ ⊥ ẑ • Ṙ k R =⇒ ṙ = 0 (this condition results in there being no image motion). 2 1.1 Brightness and Motion Let’s now consider how brightness and motion are intertwined. Note that for this section, we will frequently be switching between continuous and discrete. The following substitutions/conversions are made: • Representations of brightness functions: E(x, y) ↔ E[x, y] R R P P • Integrals and Sums: x y ↔ x y ∂E 1 • Brightness Gradients and Finite Differences: ( ∂E ∂x , ∂y ) ↔ ( δx (E[k, e + 1] − E[k, e]) 1.1.1 1D Case dx = U =⇒ δx = U δ dt (14) By taking a linear approximation of the local brightness: δE = Ex δx = uEx δt (note here that Ex = ∂E ) ∂x (15) Dividing each side by δt, we have: uEx + Et = 0 =⇒ U = − ∂E Ex ∂t = − ∂E Et ∂x (16) A couple of points about this: • This 1D result allows us to recover motion from brightness. • We can infer motion from a single point. However, this is only true in the 1D case. • We can estimate from 1 pixel, but frequently, we have much more than 1 pixel, so why use just 1? We can reduce noise by estimating motion from many pixels through regression techniques such as Ordinary Least Squares (OLS). • From statistics, the standard deviation of the motion estimates will be reduced by a factor of of pixels sampled for estimating motion. √1 , N where N is the number Finite Difference approximation for E is given by: E≈ 1 (E(x + δx, t) − E(x, t)) δx (17) Motion estimation can be done through unweighted averaging: ūunweighted = N 1 X −Eti N i=1 Exi (18) As well as weighted averaging: PN ūweighted = i=1 wi PN i=1 −Eti Exi (19) wi A quick check here: take wi = 1 ∀ i ∈ {1, ..., N }. Then we have that ūweighted = 1 N PN −Et i=1 Ex = ūunweighted . Note that in the continuous domain, the sums in the weighted and unweighted average values are simply replaced with integrals. 3 1.1.2 2D Case While these results are great, we must remember that images are in 2D, and not 1D. Let’s look at the 2D case. First and foremost, let’s look at the brightness function, since it now depends on x, y, and t: E(x, y, t). The relevant partial derivatives here are thus: • ∂E ∂x - i.e. how the brightness changes in the x direction. • ∂E ∂y - i.e. how the brightness changes in the y direction. • ∂E ∂t - i.e. how the brightness changes w.r.t. time. As in the previous 1D case, we can approximate these derivatives with finite forward first differences: • ∂E ∂x = Ex ≈ 1 δx (E(x • ∂E ∂y = Ey ≈ 1 δy (E(x, y • ∂E ∂t = Et ≈ 1 δt (E(x, y, t + δx, y, t) − E(x, y, t)) + δy, t) − E(x, y, t)) + δt) − E(x, y, t)) Furthermore, let’s suppose that x and y are parameterized by time, i.e. x = x(t), y = y(t). Then we can compute the First-Order Condition (FOC) given by: dE(x, y, t) =0 dt (20) Here, we can invoke the chain rule, and we obtain the result given by: dE(x, y, t) dx ∂E dy ∂E ∂E = + + =0 dt dt ∂x dt ∂y ∂t (21) Rewriting this in terms of u, v, w from above: uEx + vEy + Et = 0 (22) Objective here: We have a time-varying sequence of images, and our goal is to find and recover motion. To build intuition, it is also common to plot in velocity space given by (u, v). For instance, a linear equation in the 2D world corresponds to a line in velocity space. Rewriting the equation above as a dot product: uEx + vEy + Et = 0 ↔ (u, v) · (Ex , Ey ) = −Et (23) Normalizing the equation on the right by the magnitude of the brightness derivative vectors, we obtain the brightness gradient: ! Ey Et Ex ,q = −q (24) (u, v) · q Ex2 + Ey2 Ex2 + Ey2 Ex2 + Ey2 What is the brightness gradient? ! • A unit vector given by: √ E2x 2 , Ex +Ey √ E2y 2 Ex +Ey ∈ R2 . • Measures spatial changes in brightness in the image in the image plane x and y directions. Isophotes: A curve on an illuminated surface that connects points of equal brightness (source: Wikipedia). As we saw in the previous case with 1D, we don’t want to just estimate with just one pixel. For multiple pixels, we will solve a system of N equations and two unknowns: uEx1 + vEy1 + Et1 = 0 uEx2 + vEy2 + Et2 = 0 (25) (26) Rewriting this in matrix form:  Ex1 Ex2 Ey1 Ey2     U −Et1 = V −Et2 (27) 4 Solving this as a standard Ax = b problem, we have:    1 U Ey2 = V (Ex1 Ey2 − Ey1 Ex2 ) −Ex2 −Ey1 Ex1   −Et1 −Et2 (28) 1 is the determinant of the partial derivatives matrix, since we are taking its Note that the expression given by (Ex Ey −E y1 Ex2 ) 1 2 inverse (in this case, simply a 2x2 matrix). When can/does this fail? It’s important to be cognizant of edge cases in which this motion estimation procedure/algorithm fails. Some cases to consider: • When brightness partial derivatives / brightness gradients are parallel to one another ↔ The determinant goes to zero ↔ E E This corresponds to linear dependence in the observations. This occurs when Ex1 Ey2 = Ey1 Ex2 =⇒ Exy1 = Exy2 . 1 2 This issue can be mitigated by weighting the pixels as we saw in the 1D case above. However, a more robust solution is to search for a minima of motion, rather than the point where it has zero motion. The intuition here is that even if we aren’t able to find a point of zero motion, we can still get as close to zero as possible. Mathematically, let us define the following objective: Z Z ∆ J(u, v) = (uEx + vEy + Et )2 dxdy (29) x∈X y∈Y Then we now seek to solve the problem of: u∗ , v ∗ = arg min J(u, v) = arg min u,v u,v Z x∈X Z (uEx + vEy + Et )2 dxdy (30) y∈Y Since this is an unconstrained optimization problem, we can solve by finding the minima of the two variables using two First-Order Conditions (FOCs): • ∂J(u,v) ∂u =0 • ∂J(u,v) ∂v =0 Here, we have two equations and two unknowns. When can this fail? • When we have linear independence. This occurs when: – E = 0 everywhere – E = constant – Ex = 0 – Ey = 0 – Ex = Ey – Ex = kEy • When E = 0 everywhere (professor’s intuition: “You’re in a mine.”) • When Ex , Ey = 0 (constant brightness). R R R R R R • Mathematically, this fails when: x x Ex2 y y Ey2 − ( x y Ex Ey )2 = 0 When is this approach possible? Only when isophotes are not parallel straight lines - i.e. want isophote curvature/rapid turning of brightness gradients. Noise Gain: Intuition - if I change a value by this much in the image, how much does this change in the result? 5