6.801/ 6.866 Machine Vision, Quiz 1 Review

6.801/6.866: Machine Vision, Quiz 1 Review These lecture summaries are designed to be a review of the lecture. Though I do my best to include all main topics from the lecture, the lectures will have more elaborated explanations than these notes. Here you will find a review of some of the topics covered so far in Machine Vision. These are as follows in the section notes: 1. Mathematics review - Unconstrained optimization, Green’s Theorem, Bezout’s Theorem, Nyquist Sampling Theorem 2. Projection - Perspective vs. Orthographic, Object vs. Image space 3. Optical Flow - BCCE/optical flow, Time to Contact, vanishing points 4. Photometry - Radiance, irradiance, illumination, geometry, BRDF, Helmholtz Reciprocity 5. Different surface types - Lambertian, Hapke 6. Shape from Shading (SfS) - Hapke case, general case, reflectance maps, image irradiance equation 7. Photometric Stereo - least squares, multiple measurement variant, multiple light sources variant 8. Computational molecules - Sobel, Robert, Silver operators, finite differences (forward, backward, and average), Laplacians 9. Lenses - Thin lenses, thick lenses, telecentric lens, focal length, principal planes, pinhole model 10. Patent Review - Edge detector, Object Detection 1 Quick Mathematics Review Let’s quickly touch on some important mathematical theorems that are useful for machine vision. • Unconstrained optimization: Suppose we are trying to optimize an objective J(a, b, c) by some set of parameters {a, b, c}. We can find the best set of parameters {a∗ , b∗ , c∗ } using first-order conditions: a∗ , b∗ , c∗ = arg min J(a, b, c) a,b,c ∂J =0 → ∂a ∂J → =0 ∂b ∂J → =0 ∂c The solution a∗ , b∗ , c∗ is the set of a, b, c that satisfies these first-order conditions. Note that this procedure is identical with maximization. • Green’s Theorem relates the line integral of a contour to the area located within that contour: I ZZ  ∂M ∂L  (Ldx + M dy) = − dxdy ∂x ∂y L D 1 • Bézout’s Theorem: The maximum number of solutions is the product of the polynomial order of each equation in the system of equations: number of solutions = E Y oe e=1 • Nyquist Sampling Theorem: We must sample at twice the frequency of the highest-varying component of our image to avoid aliasing and consequently reducing spatial artifacts. • Taylor Series: We can expand any analytical, continuous, infinitely-differentiable function into its Taylor Series form according to: ∞ f (x + δx) = f (x) + δxf 0 (x) + X (δx)i f (i) (x) (δx)3 000 (δx)4 (4) (δx)2 00 ∆ f (x) + f (x) + f (x) + ... = , where 0! = 1 2! 3! 24 i! i=0 For a single variable function, and: f (x + δx , y + δy ) = f (x, y) + δx ∂f (x, y) ∂f (x, y) + δy + ··· ∂x ∂y For a multivariable function. 2 Projection: Perspective and Orthographic A few important notes to remember: • We use CAPITAL LETTERS for WORLD SPACE, and lowercase letters for image space. • Orthographic projection is essentially the limit of perspective projection as we move the point we are mapping to the image plane far away from the optical axis. • We can derive perspective projection from the pinhole model and similar triangles. Perspective Projection: X y Y x = , = (component form) f Z f Z 1 1 r= R (vector form) f R · ẑ Orthographic Projection: x= 3 f f X, y = y Z0 Z0 Optical Flow Optical flow captures the motion of an image over time in image space. Therefore, we will be interested in how brightness in the image changes with respect to (i) time, (ii) in the x-direction, and (iii) in the y-direction. We will use derivatives to describe these different quantities: ∆ dx dt - i.e. the velocity in the image space in the x direction. ∆ dx dt - i.e. the velocity in the image space in the y direction. • u= • v= • ∂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. 2 If x(t) and y(t) both depend on t, then the chain rule gives us the following for the total derivative: dE(x, y, t) dx ∂E dy ∂E ∂E = + + =0 dt dt ∂x dt ∂y ∂t Rewriting this in terms of u, v from above: uEx + vEy + Et = 0 This equation above is known as the Brightness Change Constraint Equation (BCCE). This is also one of the most important equations in 2D optical flow. Normalizing the equation on the right by the magnitude of the brightness derivative vectors, we can derive the brightness gradient: ! Ey Et Ex ,q = (u, v) · Ĝ = − q (u, v) · q 2 2 2 2 2 Ex + Ey Ex + Ey Ex + Ey2 ! Ex Ey Brightness Gradient : Ĝ = q ,q Ex2 + Ey2 Ex2 + Ey2 What is the brightness gradient? ! • A unit vector given by: √ Ex , 2 +E 2 Ex y √ E2y 2 Ex +Ey ∈ R2 . • Measures spatial changes in brightness in the image in the image plane x and y directions. We are also interested in contours of constant brightness, or isophotes. These are curves on an illuminated surface that connects points of equal brightness (source: Wikipedia). Finally, we are also interested in solving for optimal values of u and v for multiple measurements. In the ideal case without noise:      1 U Ey2 −Ey1 −Et1 = V −Et2 (Ex1 Ey2 − Ey1 Ex2 ) −Ex2 Ex1 When there is noise we simply minimize our objective, instead of setting it equal to zero: Z Z ∆ J(u, v) = (uEx + vEy + Et )2 dxdy x∈X y∈Y We solve for our set of optimal parameters by finding the set of parameters that minimizes this objective: Z Z u∗ , v ∗ = arg min J(u, v) = arg min (uEx + vEy + Et )2 dxdy u,v u,v x∈X y∈Y Since this is an unconstrained optimization problem, we can solve by finding the minimum of the two variables using two First-Order Conditions (FOCs): • ∂J(u,v) ∂u =0 • ∂J(u,v) ∂v =0 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. Applications include: • Multilateration • Calibration Objects (Sphere, Cube) • Camera Calibration 3 We will also look at Time to Contact (TTC): meters Z ∆ Z == dZ = meters = seconds W seconds dt Let us express the inverse of this Time to Contact (TTC) quantity as C, which can be interpreted roughly as the number of frames until contact is made: ∆ C= 4 W 1 = Z TTC Photometry Here, we will mostly focus on some of the definitions we have encountered from lecture: • Photometry: Photometry is the science of measuring visible radiation, light, in units that are weighted according to the sensitivity of the human eye. It is a quantitative science based on a statistical model of the human visual perception of light (eye sensitivity curve) under carefully controlled conditions. • Radiometry: Radiometry is the science of measuring radiation energy in any portion of the electromagnetic spectrum. In practice, the term is usually limited to the measurement of ultraviolet (UV), visible (VIS), and infrared (IR) radiation using optical instruments. ∆ 2 • Irradiance: E = δP δA (W/m ). This corresponds to light falling on a surface. When imaging an object, irradiance is converted to a grey level. ∆ δP δW • Intensity: I = ∆ • Radiance: L = (W/ster). This quantity applied to a point source and is often directionally-dependent. δ2 P δAδΩ (W/m2 × ster). This photometric quantity is a measure of how bright a surface appears in an image. e ,φe ) • BRDF (Bidirectional Reflectance Distribution): f (θi , θe , φi , φe ) = δL(θ δE(θi ,φi ) . This function captures the fact that oftentimes, we are only interested in light hitting the camera, as opposed to the total amount of light emitted from an object. Last time, we had the following equation to relate image irradiance with object/surface radiance: π  d 2 cos4 α E= L 4 f Where the irradiance of the image E is on the lefthand side and the radiance of the object/scene L is on the right. The BRDF must also satisfy Helmholtz reciprocity, otherwise we would be violating the 2nd Law of Thermodynamics. Mathematically, recall that Helmholtz reciprocity is given by: f (θi , θe , φi , φe ) = f (θe , θi , φe , φi ) ∀ θi , θe , φi , φe 5 Different Surface Types With many of our photometric properties established, we can also discuss photometric properties of different types of surfaces. Before we dive in, it is important to also recall the definition of surface orientation: ∆ ∂z ∂x • p= ∆ ∂z ∂y • q= • Lambertian Surfaces: – Ideal Lambertian surfaces are equally bright from all directions, i.e. f (θi , θe , φi , φe ) = f (θe , θi , φe , φi ) ∀ θi , θe , φi , φe AND f (θi , θe , φi , φe ) = K ∈ R with respect to θe , φe – “Lambert’s Law”: Ei ∝ cos θi = n̂ · ŝi 4 • Hapke Surfaces: – The BRDF of a Hapke surface is given by: 1 f (θi , φi , θe , φe ) = √ cos θe cos θi – Isophotes of Hapke surfaces are linear in spatial gradient, or (p, q) space. • What do the isophotes of the moon look like, supposing the moon can fall under some of the different types of surfaces we have discussed? – Lambertian: We will see circles and ellipses of isophotes, depending on the angle made between the viewer and the the moon. – Hapke: Because of the BRDF behavior, isophotes will run longitudinally along the moon in the case in which it is a Hapke surface. 6 Shape from Shading (SfS) This is one of the most fundamental problems in machine vision in which we try to estimate the surface of an object from brightness measurements. Several variations of this problem we consider: • Hapke surfaces - this leads to linear isophotes in (p, q) space, and allows us to solve for one of the dimensions of interest. • General case: There are several techniques we can apply to solve for this: – Green’s Theorem (see lecture notes handout) – Iterative Discrete Optimization (see lecture notes handout) For these problems, we considered: – – – – – Characteristic strips (x, y, z, p, q) Initial curves/base characteristics Normalizing with respect to constant step sizes A system of 5 ODEs Stationary points and estimates of surfaces around them for initial points Next, let us review reflectance maps. A reflectance map R(p, q) is a lookup table (or, for simpler cases, a parametric function) ∂z ∂z , q = ∂y . that stores the brightness for particular surface orientations p = ∂x The Image Irradiance Equation relates the reflectance map to the brightness function in the image E(x, y) and is the first step in many Shape from Shading approaches. E(x, y) = R(p, q) 7 Photometric Stereo Photometric stereo is a technique in machine vision for estimating the surface normals of objects by observing that object under different lighting conditions. This problem is quite common in machine vision applications. One way we can solve photometric stereo is by taking multiple brightness measurements from a light source that we move around. This problem becomes:     −sT1 E1  T  E2  −s n =  2 E3 −sT3 Written compactly: Sn = E −→ n = S−1 E Note that we we need S to be invertible to compute this, which occurs when the light source vectors are not coplanar. Other variations of this problem: 5 • Using light sources at different electromagnetic frequencies • Using a camera with different light filters • Moving the object to different locations 8 Computational Molecules These are crucial components for applying machine concepts to real-life problems. 1. Ex = 1 (E(x, y) − E(x − 1, y)) (Backward Difference), 1 (z(x + 1, y) − z(x, y)) (Forward Difference) 2. Ey = 1 (E(x, y) − E(x, y − 1)) (Backward Difference), 1 (E(x, y + 1) − E(x, y)) (Forward Difference) 3. ∆E = ∇2 E = 4. Exx = 5. Eyy = ∂2E ∂x2 2 ∂ z ∂y 2 = = 1 2 (4E(x, y) 1 2 (E(x − (E(x − 1, y) + E(x + 1, y) + E(x, y − 1) + E(x, y + 1))) − 1, y) − 2(x, y) + E(x + 1, y)) 1 2 (E(x, y − 1) − 2(x, y) + E(x, y + 1)) 6. Robert’s Cross: This approximates derivatives in a coordinate system rotated 45 degrees (x0 , y 0 ). The derivatives can be approximated using the Kx0 and Ky0 kernels:   ∂E 0 −1 0 = → K x −1 0 ∂x0   ∂E 1 0 0 = → K y 0 −1 ∂y 0 7. Sobel Operator: This computational molecule requires more computation and it is not as high-resolution. It is also more robust to noise than the computational molecules used above:   −1 0 1 ∂E → Kx =  2 0 2 ∂x −1 0 1   −1 2 −1 ∂E → Ky =  0 0 0  ∂y 1 2 1 8. Silver Operators: This computational molecule is designed for a hexagonal grid. Though these filters have some advantages, unfortunately, they are not compatible with most cameras as very few cameras have a hexagonal pixel structure.   0 1 0 9. “Direct Edge” Laplacian: 12 1 −4 1 0 1 0   1 0 1 10. “Indirect Edge” Laplacian: 212 0 −4 0 1 0 1 11. Rotationally-symmetric Laplacian:    1 0 1 0   1 1 0 0 −4 4 2 1 −4 1 + 1  22 0 1 0 1 0   1  1 4 1 0 = 2 4 −20 6 1 1 4  1 4 1 Some methods we used for analyzing how well these work: 1. Taylor Series: From previous lectures we saw that we could use averaging to reduce the error terms from 2nd order derivatives to third order derivatives. This is useful for analytically determining the error. 2. Test functions: We will touch more on these later, but these are helpful for testing your derivative estimates using analytical expressions, such as polynomial functions. 3. Fourier domain: This type of analysis is helpful for understanding how these “stencils”/molecules affect higher (spatial) frequency image content. 6 Figure 1: Silver Operators with a hexagonal grid. 9 Lenses Lenses are also important, because they determine our ability to sense light and perform important machine vision applications. Some types of lenses: • Thin lenses are the first type of lens we consider. These are often made from glass spheres, and obey the following three rules: – Central rays (rays that pass through the center of the lens) are undeflected - this allows us to preserve perspective projection as we had for pinhole cameras. – The ray from the focal center emerges parallel to the optical axis. – Any parallel rays go through the focal center. • Thick lenses (cascaded thin lenses) • Telecentric lenses - These “move” the the Center of Projection to infinity to achieve approximately orthographic projection. • Potential distortions caused by lenses: – Radial distortion: In order to bring the entire angle into an image (e.g. for wide-angle lenses), we have the “squash” the edges of the solid angle, thus leading to distortion that is radially-dependent. Typically, other lens defects are mitigated at the cost of increased radial distortion. Some specific kinds of radial distortion [5]: ∗ Barrel distortion ∗ Mustache distortion ∗ Pincushion distortion – Lens Defects: These occur frequently when manufacturing lenses, and can originate from a multitude of different issues. 10 Patent Review The two patents we touched on were for: • Fast and Accurate Edge detection: At a high level, this framework leveraged the following steps for fast edge detection: – CORDIC algorithm for estimating (and subsequently quantizing) the brightness gradient direction – Thresholding gradients via Non-Maximum Suppression (NMS) – Interpolation at the sub-pixel level along with peak finding for accurate edge detection at sub-pixel level – Bias compensation 7 – Plane position We also discussed some issues/considerations with the following aspects of this framework’s design: – Quantization of gradient direction – Interpolation method for sub-pixel accuracy (quadratic, piecewise linear, cubic, etc.) • Object detection and pose estimation: At a high level, this framework leveraged the following steps for fast object detection/pose estimation: – Finding specific probing points in a template image that we use for comparing/estimating gradients. – Using different scoring functions to compare template image to different configurations of the runtime image to find the object along with its pose (position with orientation). 8