Time to Collision Warning Chip

1 Time to Collision Warning Chip: Background: Under certain circumstances, it is possible to estimate the time to collision (TTC) from a time varying image. It would be useful to encapsulate an algorithm for doing this into a cheap camera, ideally with computation done on the chip that senses the image. That way, there is no need to move large volumes of image data from an image sensor to a processing chip. Such a chip would perform an extreme bandwidth compression: it has high bandwidth in (image sequence) and low bandwidth out (time to collision). Such a device could be outfitted with a cheap plastic lens and used as a warning system, aimed, for example, out the rear of car into each of the two ‘blind spots’ that are not easily visible in the driver’s mirrors. The key to recovering the time to collision is the realization that there are constraints between the brightness gradient (spatial derivatives of brightness) and the time derivative of brightness at a point in the image. These depend on motion field, and the motion field in turn depends on the rigid body motion between the camera and the object(s) being viewed. Focus of Expansion: A related chip is the ‘focus of expansion’ (FOE) chip built by Ig McQuirk. This is an analog VLSI chip that finds the focus of expansion. His chip uses spatial and time derivatives of brightness to locate the point in the image towards which motion is taking place. Again, this is a high band width in, low band width out application. The difference between the two projects (FOE versus TTC) is that in the FOE chip, the intent is to be insensitive to the magnitude of the velocity, and to distances to points in the scene, while in the TTC chip the opposite is the case: the intent is to be insensitive to the direction of motion instead, which is exactly what the FOE chip recovers. Note that the time to collision is just the ratio of velocity to distance. Interestingly, it is not possible to determine either absolute velocity or absolute distance from an image sequence, while the ratio of distance to velocity can be determined. Absolute distance or velocity cannot be determined because of the ‘scale factor ambiguity’: if we scale distances in the scene by some constant factor k, while also scaling the velocities by the same factor k, then we get the same image sequence. In some sense the two chips (FOE and TTC) serve complementary functions: one finds the direction of motion (FOE) while the other finds 2 the time until we ‘get there.’ While the FOE chips exploits ‘stationary points’ — points where the time derivative of brightness is zero while the spatial derivatives are not — the TTC chip cannot make use of information at stationary points, since this is insensitive to the velocity. Method: The basis of both FOE and TCC algorithms is the ‘constant brightness assumption’: dE(x, y , t) =0 dt which is based on the observation that in many situations the brightness of a point does not change as it moves in the image. The above total derivative can be expanded into: uEx + vEy + Et = 0 where u = dx/dt, v = dy /dt are the x and y components of the motion field in the image, while Ex , Ey , Et are the x, y, and t derivatives of brightness. For convenience this can also be written Er .r + Et = 0 where Er = (Ex , Ey , 0)T while r  = (u, v, 0)T . The constant brightness assumption naturally does not apply in all cases. It is violated by a specular surfaces, since typically such a surface will have different brightnesses when viewed from different directions. It is also violated if the light sources move relative to the scene. But in many practical situations it is a useful and reasonable assumption. Motion Field: The image velocity (u, v) is a projection of the velocity of the corresponding point in the world in front of the camera. The image point and the scene point are connected by a ray going through the center of projection. The perspective projection equation is simply 1 1 r= R f R · ẑ where r = (x, y , f )T is a vector to a point in the image, while R = (X, Y , Z)T is the vector to the corresponding point in the scene. Here R · ẑ = Z, with ẑ the unit vector along the optical axis, and f the principal distance of the camera (usually just slightly larger than the focal length). To obtain the motion field (a vector field in the image plane) we differentiate the perspective projection equation with respect to time. 1  R · ˆ z R − R r = R·ˆ z (R · ˆ z)2 f 3 where r = dr/dt and R  = dR/dt. This equation relates velocities of scene points to corresponding velocities projected into the image plane. This can also be re-written using some vector identities and the perspective projection equation: 1  z (r × R  ) × ˆ r = f R · ẑ where × denotes the cross product and · denotes dot-product. Brightness and Motion Constraint: The image velocity r is (u, v, 0)T while the velocity in the scene is R  . If we insert the above equation for r in the brightness change constraint equation we get — after some manipulation: R · s Et = R · ẑ where s = r × (Er × ẑ). The vector s can also be written in terms of its components � �T s = f Ex , f Ey , −(xEx + yEy ) The above equation — which applies at every image point — is a constraint relating measurable quantities such as spatial and time derivatives of brightness to unknowns such as velocities and distances in the scene. In the case of rigid body motion R  = −t − ω × R where t = (U, V , W )T is the instantaneous translational velocity of the camera, while ω = (A, B, C)T is the instantaneous rotational velocity. Since the above equation applies at every picture cell, there potentially is a lot of constraint to work with. If the only unknowns are the parameters of rigid body motion (3 parameters for translation and 3 for rotation) then we have highly over-determined system and a stable solution can be achieved even in the presence of a lot of noise in the measurements. However, in an arbitrary scene, the ‘depth’ Z = R · ẑ, is not known and this can vary from place to place in the image. The total number of unknowns increases dramatically if we add unknown depths at every picture cell. This can make the problem not so well posed (i.e. number of constraints is not greater than the number of unknowns). This is why we expect to have to work instead with a reduced model. The simplest case to investigate is a constant depth model, the next easiest a planar surface approximation, and then a quadratic surface. These simple models may prove adequate if we divide the image into patches small enough so that the surface images in any given patch is 4 approximately at constant depth, or approximately planar. We have to be careful, however, not to make the patches too small, since the component of motion along the optical axies becomes less well determined with a narrow field of view. Also, while the larger the patches, the more constraint it provides, a large patch is more likely to contain image components from more than one object. Ideally, the division into patches should be adaptive. If there is a lot of textureal detail, a small patch can be used, while if brightness varies only slowly, a large patch may be needed to get satisfatory results. Rigid Body Motion: If the camera is translating with velocity t and rotating with angular velocity ω with respect to an object in the scene, then R  = −t − ω × R where t = (U, V , W )T and ω = (A, B, C)T say. Our task is to recover the components of motion and the depth. For recovering the time to impact we are actually only concerned about Z R · ẑ T = = . W t · ẑ Plan: We will first explore a number of algorithmic alternatives on existing work stations using both real image sequences created under controlled conditions as well as synthetic sequences where the motion and shapes of objects is known exactly.