Some Theory behind Obstacle Detection

Seek not a set of beliefs; seek instead an awareness of what you already know.

his page will investigate the technology behind obstacle detection as it stands today, and how it might fill the needs of driverless vehicles running along beams. To replace the eyes and brains of a human driver with equally good (or better) technological devices is very tricky. The human mind´s ability to process sensory information is very advanced and complex. The research going on today to make robots detect obstacles is very much based on how insects do the same thing. We will examine the options available to FLYWAY®, and how these options function in theory. It is a fairly technical page. Suggestions for application in FLYWAY® is detailed on another page.		General Available scanner technologies Determining the velocity of an object Operation of "LADAR" Operation of digital cameras Methods to judge distances with ladar Optical flow with LADAR How is optical data processed? Scanning problems with LADAR Calculating safety requirements Microwave radar technology Far infrared sensor technology

1. General

here is a host of sensors available, many of them based on how insects function. What is needed for the automatic beamtraffic system is something that detects an object well ahead of impact, so tactile information won´t do. We need something with the ability to: Look sufficiently far ahead of the beamcar to be able to discern potential obstacles Scan the perimeter of the travelling direction, and allow for the fact that this travelling direction changes now and then, both vertically and horizontally Scan the perimeter of the travelling direction, also because objects might approach the path from the sides or from above/below, as well as being stationary and in the path of travel Evaluate what is being seen Do all this in sufficiently good time for the control system to brake the car before impact. We thus need: Sufficient range to allow for high vehicle speed Sufficient width, both to cover change of travelling direction and to see objects moving in from the sides Quick and reliable processing of data.	Scanners, in one form or another, have been in existence since World War II. The first use was in the form of radar, to detect enemy aircraft. Today´s applications include: aircraft radar speed detection (used by the police along our highways) obstacle detection for motorcars devices for blind or visually impaired persons obstacle detection for robots supervision of manufacturing processes scanning license plates of motorcars, using digital cameras There are 3 fields of research that are of particular interest in connection with operation of automatic transport systems of the kind we´re talking about here: obstacle detection for motorcars along highways obstacle detection for robots experiments with the vision of insects	Regarding these three points: Much experimentation has been done, and is still going on, at universities around the world, to arrive at decent obstacle detection systems to be used in connection with highway traffic, to bring down the rate of traffic fatalities. Every year about 50,000 people are killed on the roads in the European Community. The figure for the USA is similar. Apart from the human tragedy, there is a high cost and much inconvenience associated with traffic jams, emergency services and property damage as a consequence of road accidents. An essential requirement for any collision avoidance system is a sensor that can detect obstacles in the immediate traffic environment. Microwave radar is a strong candidate for this task because of it's ability to directly measure range and it's good performance in bad conditions when compared to optical systems. The pre-eminent technologies are thus ladar and microwave radar. robots are usually slow-moving, and have thus more time to process visual data. They could probably best benefit from digital camera-scanning. the most interesting aspect with the experimentation with insects is to discover how they separate potentially dangerous objects from non-dangerous. Some insects, such as grasshoppers, seem to be able to do just that.
Figure 1:2

2. Available Scanner Technologies

he sensors of the obstacle detection systems that are of interest to us are built on different technologies. Those that are available to us today are: Infrared sensors Common radar Microwave-based radar Digital cameras Laser Combination of digital cameras and laser Looking at these more closely: Infrared sensors are divided into: Near infrared sensors (laser radar, infrared sensors) which do not offer a sensible benefit in fog. Far infrared sensors (sensitive in the range of 8-14 mm), providing thermal images of the scenario independently from any light conditions, the enhanced visibility in fog and heavy rain condition is dependent on droplets dimensions. Infrared sensors are not suitable for our purpose. Common radar might be the obvious choice, at first thought. But common radar does not have a high enough frequency to provide the details of an object that would be necessary for identification. One could of course increase this frequency, but radar still has disadvantages as compared to laser. Microwave-based radar is a much more viable technology. It has good ability to distinguish small objects and is used in many fields, such as guiding docking ships. By using variable frequency during the sweep, one can obtain much information. Microwave range sensors (radar), operate properly in any poor visibility condition. Providing information from stationary objects require powerful signal processing to be extracted. Their functionality is limited in complex scenarios like urban road traffic.

Digital cameras is quite an interesting option. CCD/CMOS sensors are used, and they are active in the visibility range, and thus not offering much benefit in any reduced visibility condition. The technology is based on intelligent evaluation of what is seen. An everyday example of this is "OCR"; Optical Character Recognition. The computer that evaluates the pictures has a database of characters it has to recognize. Every character has deviations in the way it looks, depending on: type face font bold and/or cursive size "fuzzy borders", depending on contrasting colors between character and background and poor readability. Figure 2:1 One can realize from this why the first OCR-programs that came on the market were so highly priced. One practical use of this technique is traffic surveillance. Cameras mounted over traffic lanes (figure 2:1.) can scan the license plates of motorcars as these come into view, from the bottom of the area in view, as can be seen in figure 2:2. This information can then be used to check for stolen cars, charging toll fees, etc.

Could digital cameras be used for obstacle detection? Well, they have potential, but the mass of information which has to be processed is too huge! Today´s computers could not handle the workload in the short timespace which is available. Laser? Yes, this might be our choice for FlyWay, and we will go deeper into this technology further down on this page. Figure 2:2 A combination of digital cameras and laser? This is being used today to control assembly-line manufacturing processes, as shown in figure 2:3.. It could conceivably be of use in connection with obstacle detection. Figure 2:3

3. Determining the velocity of an object

peed is a quantity, whereas velocity is a vector. Thus, when a mathematician talks about the velocity of an object, he is not only referring to its speed, but also to its direction of travel. And this is what we mean by the term "velocity" in this chapter. An object poses a threat of collision if: it is approaching it is moving laterally across the path of travel. In connection with beam-carried traffic, we would have to consider 4 cases of relative motion that could pose such a threat: The scanner is mounted on a moving car. In this case we would have to deal with relative velocity; i.e. the object might be stationary, but it is approaching the car insofar as the car is moving. The scanner is mounted on a moving car, and the detected object seems to be stationary, or moving towards and away from the beamcar, longitudinally, but it does not necessarily have any lateral (sideways) movement. This would be the case if the beamcar is following behind another beamcar. The danger here is that the object might suddenly approach the car (relatively speaking), and the car´s speed has to be regulated to prepare for this possibility. In other words; the closer the object, the lower the speed. The scanner is mounted on a beamcar which is stationary at the moment. There is a theoretical possibility here to allow the car to take evasive action if an object is approaching too fast and is not identified. The scanner is mounted on a beam or other fixed object, overlooking the beamcar paths. The cars in the area would then have to rely on evaluation from these sources. In cases 2, 3 and 4, we will also have to deal adequately with stationary objects, relatively speaking, that might pose a threath, although they are not approaching the car at the moment. Most animals (and humans) make use of the fact that they have two eyes to judge the distance to objects; they use stereoscopic vision. Insects have compound eyes, and such eyes cannot work in that manner, even if the eyes are facing in the same direction. So how do they judge distances and motions of objects in their vicinity? One interesting experiment, performed on a grasshopper, indicates an answer. The grasshopper was mounted in front of a cinema screen, showing sequences from "Star Wars". Twitchings in the animal´s muscles were measured, and it turned out that the grasshopper didn´t try to jump away in every situation where an object on the screen was moving towards it, but only when the direction of movement was such that an impact seemed imminent. Let us from this information sort out how a "grasshopper-based" obstacle detection system would function. Figure 3:1 Case 1: The object grows. An approaching object becomes larger in the field of vision; the detection angle gets bigger, as shown in figure 3:1. Clearly, an object which really expands to become bigger, without actually approaching the scanner, would fool this function of the scanner, as it probably would fool the grasshopper. But since "our" detection function also would include ordinary distance- or intensity-measurements, that possibility is eliminated. Besides; objects that expand their physical size that fast are very rare in the real world.

Figure 3:2 Case 2: The object grows, but also moves sideways. In figure 3:2, an object is detected at time = t0 (A in figure 3:2) and again at time = t1 (cases B through E). As the approaching object becomes larger in the field of vision it also moves at an angle, relative to the detector. I.e., it is not approaching head-on. The task of the detection device would then be to decide whether the angular movement of the object is too small, relative to: its approaching speed its distance the size of the area to be protected to avoid an impact (case B in figure 3:2) or if it goes clear (case C). To adequatly be able to monitor the object, the scanning angle would either have to be altered in order to be wide enough (case D) or the scanner should be able to follow the object (case E in figure 3:2). This is apparently how insects judge danger in their sorroundings. What should be remembered here is that this scanning has to be done in 2 dimensions; height and width, as shown in figure 4:4 below. How wide a sweep? One can see from these examples that the sweep of the radar would have to be real wide to catch moving objects coming in from the side, or from above or below. Looking at case A in figure 3:4 below, object A might not be detected until it´s too late. In case B object A is detected, but at a cost. The larger the area that the scanning has to cover, the more processing work it will be for the computer, and the evaluation of the scan might not be finished until it is too late. This is a strong case for using stationary scanners instead of mounting them on the vehicles. This approach would be extremely expensive for the road traffic, considering the large amounts of roads out there. But for a beam traffic system, stationary scanners would probably be the preferable option.

Figure 3:4

Figure 3:6

How a grasshopper might see it The grasshopper watching "Star Wars" on a movie screen could not have had any way of knowing how big an approaching object was, nor how far away it was. Thus, it would not have any way of "calculating" time-to-impact. All it could see was; How much the object filled its field of vision How quickly the object filled its field of vision What part of its field of vision was being filled by the object.

Putting together these three parameters, it would be possible to judge impact or no impact, but not when. One can then assume that the grasshopper would get out of the way as soon as it reached the conclusion "impact", and not bother about "when". This would be quite sufficient for the grasshopper´s need, provided that the approaching object does not suddenly change travel direction.

Figure 3:6 above illustrate this reasoning. In the top scenario (labeled A) the grasshopper sees that the object is disappering from its field of vision while also growing. The grasshopper will of course have a safety margin, and if the object comes within this margin, as it does in scenario B, the grasshopper jumps away, even though it would not have been hit by the object.

4. Operation of "LADAR"

"RADAR" is the acronym for "Radio Detection and Ranging". If one replaces the first word with "Laser" (which in itself is an acronym), one gets the acronym "LADAR". Laser beams are eminently suitable for the task of identifying obstacles. They keep a narrow beam over long distances; the beam does not spread out at an angle like other type of beams. Thus, NASA has for instance been able to measure the distance to the moon by bouncing a Laser beam off its surface! The device includes information processing ability, which can be programmed to: report only objects above a certain size report only moving objects report only objects within a certain distance when looking vertically down at terrain below; report only objects that do not agree with what the topology should look lika at that location report the distance and even the sloping angle of objects. A laser beam consists of light, and consequently, the beam cannot be deflected by a varying electric or magnetic field, as is done with the electron beam in a television set. Instead, the laser beam in this kind of application is made to scan across a pre-set angle by means of a fast-moving mirror as shown schematically at A in figure 4:2. A scanning frequency of 1000 Hz is common, which indicates what demands are put on the motor that drives this mirror. Figure 4:1

Radar measures the timelag before the beam gets reflected from an object. Radar is an excellent means of detecting other vehicles, because radar works at long ranges and is relatively unaffected by rain or snow. One such radar for vehicle detection was capable of detecting motor vehicles on a highway at distances of up to 200 meters with a range resolution of approximately 0.1 meters. The sensor had a 3o vertical field of view and a 12o horizontal field of view. Bearing to a target could be estimated via wavefront reconstruction, and, when combined with geometric information about the road, potential obstacles could be mapped to an individual lane. Since radars provide direct range, are less expensive than lasers and digital camera systems and may also provide a doppler velocity measurement, they will most likely be a standard sensor for automated vehicles. Unfortunately, current radars are not able to reliably detect small objects at ample distances. Metal surfaces are good radar reflectors, and hence make vehicle detection fairly easy. The ease with which an object may be detected at a given range is related to its radar cross section. Vehicles have a much larger radar cross section (10 m2 ) than people (0.2 to 2 m2), and most debris and flying objects will likely have an even smaller radar cross section, making them undetectable with radar. Figure 4:2

Laser depends on scanning the object several times while either the object or the scanner moves, in order to positively identify an object, and its distance. A laser scanner does not detect "smoothly", as does radar. Rather, it looks at a set number of points along its perimeter (i.e. it has a maximum resolution), and the detector catches the reflection of each point (if there is a reflection), as shown in figure 4:3. In most cases the intensity of the reflected beam has turned out to be more usefull than timelag measurements, to determine distance. Another interesting technology is to measure polarization of reflected light to determine orientation, but that method is not investigated here. Identifying an object is a tricky business, and it gets even trickier considering that a moving scanner equipment might not move smoothly as it scans; the vehicle it is mounted on might pitch and jaw as it travels. With a well-constructed stereo jig, stereo has the advantage that both cameras will have a similar roll and pitch. In optical flow, by using a temporal baseline, there is no such guarantee. The pitch and roll of the vehicle and camera system are likely to change somewhat from image to image. This makes matching and accurate flow vector estimation quite difficult. But by feeding this scanned data to a computer as it comes in, "intelligent" appraisals of objects can be arrived at. Figure 4:3

Figure 4:4

Reflectance Intensity Figure 4:5 As everyone knows, if one aims a light beam toward a mirror surface at an angle, the beam will bounce off at the same angle, but in the opposite direction, as shown in figure 4:5. Thus, the beam depends on some opacity and/or some roughness on the detected object, which scatters the beam, in order for some of the beam´s light to return to the detector (assuming, of course, that the detector is very close to the transmitter).

Figure 4:6 The standard laser reflectance model comes from laser communication theory. Assuming a "Lambertian" surface, the standard reflection model states is illustrated in figure 4:6. in this equation; I = laser intensity r = the surface albedo q = the angle of incidence z = range to the target.

5. Operation of Digital Cameras

igital cameras and videocameras have come into popular use, as the technique has developed and the equipment has plummeted to affordable prices. They record what they see, in the form of pixels, more or less as a human would see his surroundings. The camera can see colors, also outside the "human" range, as infra-red and ultra-violet. It can also judge distances to objects, as anyone who has used an auto-focusing camera can testify.		Thus, the main advantage as compared to ladar is that digital cameras can provide a lot more detail, enabling the processor to identify different objects according to various criteria. This can also be a disadvantage, insofar as the computer needs longer time to process the extra information. When it comes to obstacle detection, that time might simply not be available, and so, digital cameras are not the best choice in every situation.

6. Methods to Judge Distances with Ladar

There are a few different methods to measure distances with Ladar. They are: Measuring the time between transmission and return of a signal Measuring the intensity of the returned signal Using stereo vision and triangulation Using Laser striping Using optical flow All laser rangefinders operate by emitting laser energy and measuring the time it takes for the energy to travel away from the sensor, strike a surface, and return. There are three basic methods for measuring this time interval: pulsed time-of-flight AM phase-differencing FM beat frequency. For these three methods, the target range is: z = (cDt /2) where Dt is the roundtrip time of the laser energy, and c is the speed of light. We will look a bit closer at these methods in chapter 8 below. Figure 6:1: pulsed time-of-flight Measuring the time lag before the bounced signal returns to the detector (illustrated in figure 6:1) would seem the most logical way of appraising distances. A 3-D laser scanner operates by sweeping a laser across the scene in two dimensions. At each pixel, the instrument measures the time it takes for a laser beam to leave the sensor, strike a surface, and return. There are several methods for measuring the time. Measuring the intensity of the returned signal: Many sensors provide an intensity measurement at each pixel by measuring the energy of the returned laser signal. It has been found that measuring the intensity of the returned signal is often the most reliable method, both for distance measuring and for detecting the object at all, in adverse weather conditions.

Stereo vision: A number of systems described in the intelligent vehicle literature use stereo as an obstacle detection method. But successful stereo algorithms can be quite complicated, and the equipment rather expensive, and so we have decided not to use such a system in FLYWAY. Laser striping is an indirect ranging method that has been used on robots (especially indoor robots). Laser striping uses a fixed CCD camera and a laser stripe (visible to the CCD) that is swept across a scene. Triangulating between the known direction of the laser and the direction provided by the laser stripe position on the CCD provides a range estimate at each image row. Laser striping can provide 3-D geometry fairly quickly, since the laser only needs to be scanned in one direction, and computation is simple. But there are a couple problems with laser striping. The returning laser pulse must be easily detectable within the image (it must be significantly stronger than ambient light). We don´t encounter this problem, using digital cameras. As with any triangulation system, range accuracy improves as the distance between the laser and CCD is increased. However, as this distance is increased, the problem of “shadowing” worsens. Shadowing occurs when points visible to the laser may not be visible to the detector and vice versa. For the simplest systems (a beam diverged by a cylindrical lens), laser striping requires more laser power than direct methods and hence is most useful indoors or at short distances. Laser rangefinders avoid the shadowing problem by keeping the transmitted and received beams approximately coaxial, (as in figure 6:1) and measuring range directly, which time lag measurements (the first item in the list) is an example of. Thus, a full sweep in two-dimensions can provide both a depth map and an intensity image. Optical flow: This is the method that is the most useful when dealing with moving objects. We will thus describe this method further in the next chapter.

Mathematical Methods detailed explanation of how to treat the reflected signal could fill a book. The methods are both varied and quite complex, and one often have to use more than one method and let their respective results complement each other. This is because, as stated: the data is complex by its very nature the data is corrupted by noise of various kinds more than one scanning method is used, often interchangeably weather conditions and light conditions affect the results both static and moving objects have to be tracked, using different evaluation methods This last point means that static objects are revealed by stored information how the area in view "should" look like, whereas moving objects are revealed by comparing successive "frames" or scanning lines. What follows here is just a brief listing.

Least Squares Ordinary least squares regression techniques estimate desired parameters by minimizing the sum of the squared residuals. Mathematically: Thus; least squares estimation chooses the parameter set which minimizes the sum of squared residuals. Although least squares methods are among the most commonly used methods in parameter estimation, they perform very poorly with respect to outliers. Least Median of Squares (LMS) Least median of squares estimation chooses the parameter set which minimizes the median of the squared residuals. There are many robust statistics techniques that can produce estimates that are unaffected by some outliers. One way to characterize a statistical method is by its breakdown point, which is the smallest percentage of outliers that can result in arbitrarily large errors in the resulting estimate.

Least Trimmed Squares (LTS) Least trimmed squares estimation chooses the parameter set which minimizes the sum of the smallest squared residuals. For every parameter combination, the residuals are calculated for every point and then sorted. The smallest squared residuals are summed, and the parameter combination which minimizes this sum is chosen. Least Squares of Maxima This method for range estimation tracks the maximum obstacle intensity at each frame, and then uses only these maximum intensity measurements to generate a least-squares fit to the model. Least Squares of Medians This method is similar to the previous method. Instead of taking the maximum intensity at each time instant, it takes the median, and uses only these median intensities to calculate the least squares parameter set.

7. Optical Flow with LADAR

y "optical flow" is meant the steady flow of optical information, insofar as the area covered by the scanner/camera is scanned again and again. Scanners that determine distance to an object by measuring the intensity of the reflected signal (a technique which has been found to be more reliable than measuring the delay until the signal returns) are handicapped if the detected object does not move relative to the scanner. But as soon as there is a relative movement, the scanner can use the input from two or more frames (or "pictures") to calculate the distance to the object. An example is shown in figure 7:1. At time time = t0 the scanner detects an object, whose upper edge is at a certain angle as compared to a reference point (mounted on a pole in this example). At time = t1 this angle has changed, because of this relative motion, and simple trigonometry then provides both distance and bearing to the object. If the time between t0 and t1 is known, relative speed can also be calculated. In addition to that, if the length of the temporal base d is known or can be calculated from known speed, the absolute speed of the detected object can (of course) also be calculated. The size of the object can be arrived at, using the same method of comparing successive frames, as shown in figure 7:2. Now, optical flow calculations are sensitive to noise,so there is a limit to how small a difference in angles can be, if one wants to reliably detect an objects parameters, such as size, distance and velocity. If angles can´t be made big enough (because the object is too small and/or too distant, one can compensate for this by comparing more than just two frames, since this will filter out much of the noise. This is illustrated in figure 7:3. By increasing the temporal baseline d, we can improve the object’s detectability, as this will increase the difference in angles between frames. But this comes at a cost: we need to push our lookahead distance back by just as much, to compensate. This means that we have to detect the object in the first frames while it is further away. Increasing the temporal baseline also has the drawbacks of increasing the effective sensor latency and possibly increasing processor memory requirements, since we may need to maintain a queue of back images for processing until the accumulated temporal baseline (from time = t0 to t3 in our example in figure 7:3) is long enough for the current image. To clarify this a bit; memory requirements is not only proportional to the number of frames queued for simultaneous processing and comparison, but also to the time those frames are queued. And this is because more than one series of frames might have to be stored simultaneously if storage time is extended.

Figure 7:1 Figure 7:2 Figure 7:3

simple example of how memory is used is provided in figure 7:5. Two series of 4 frames each are stored before each series is processed. If time between collection of frames from scanning is doubled, the next series of frames will start being stored before the previous series is completely collected. Thus, in B, more memory is required than in A. It is clear that trying to remedy this by instead extending the time interval between collecting frames will only degrade performance.

Figure 7:5

8. How is Optical Data Processed?

Figure 8:1

ost ranging software systems have been image-based, meaning that the system waits for an entire laser image to be acquired and processed before obstacles are reported to the path generation module. But one could also have a system that processes range data pixel by pixel to reduce the latencies involved and thus improve system efficiency. A pixel by pixel method also reduces the dependency on a particular range sensor, since methods which use entire images are tuned to the specific field-of-view and geometry of the sensor. Reported latencies for pixel by pixel systems has been reduced to under 100 ms and less. With the addition of a planning module, such systems has performed well in multi-kilometer traverses through unknown terrain. Comparing the Image with Databased Images Both lasers and digital cameras benefit from being able to compare images not only with previous images, but also with information from a database, showing what the window in view ought to look like. One can note that:

for vehicle-based scanners, this is very cumbersome to implement for stationary scanners, this would be easy to implement vehicle-based scanners would sometimes have difficulties judging what they are seeing, without such databased information stationary scanners would, after interrupted service, be able to see both moving and stationary objects with the aid of such a database database information is needed in order to see negative obstacles. Points 4 and 5 might warrant explanations. Stationary objects need to be moved into view before they can stay there as stationary objects. That motion would normally be detected, but not if the scanner is temporarily out of service. Say that the maintenace crew that fixed the scanner forgot some implement nearby the track when they left. That would be detected by the scanner, if it had access to information would its view should look like. Negative obstacles is the term, in connection with road traffic, for missing things, like holes and ditches. For road traffic, these could be as dangerous as positive obstacles. For beam traffic, a suddenly missing beam segment could be just as dangerous.

Pulsed Time-of-Flight A time-of-flight laser sensor operates by emitting a concentrated laser energy pulse for each pixel in the viewed window. The pulse travels away from the sensor, strikes a surface, and returns to the detector. A clock measures the time elapsed between the beginning of the pulse and the leading edge of the return pulse (see figure 6:1). Since lightspeed is 3x10 8 m/s, short distances can be measured only with very short pulses and complicated, fast electronics. There are devices that has an accuracy of +/- 3 cm and a resolution of 2 cm with a maximum data rate of 12,000 points per second. Resolution and accuracy can be improved with longer "dwell times" by mathematically taking the average of many pulses. This results of course in lower data rates. The maximum range of this laser depends on how good a reflector the detected object is; 150 meters for good reflectors (r > 0.8), or 50 meters for bad reflectors (r > 0.1). Retroreflectors can be detected up to 1000 meters away. The laser also provides 8-bit intensity for each pixel. The minimum distance the sensor can measure is 1 meter. When operating in some environments, it is possible for some of the outgoing laser energy to be reflected by dust or fog, while the remainder of the energy travels until it reaches a solid surface and returns to the detector. In this case, the receiver will see multiple return pulses. The laser measures the time elapsed between the beginning of the pulse and the last pulse returned to the receiver (see figure 8:1). Provided the dust or fog is not too dense, this can find the range to the first solid surface. This high-penetration version of the sensor can achieve an accuracy of +/- 10 cm and a resolution of 10 cm and provides 8- bit reflectance data. Clearly, more laser power is needed to detect targets through dust and fog at similar ranges since less energy penetrates to the final target.

Frequency-Modulated Continuous Wave (FMCW) Another type of laser rangefinder is the frequency modulated continuous wave (FMCW) device. The emitted light is modulated by a sine wave at varying frequency, and mixed with the reflected energy. Range can be estimated by measuring the resulting beat frequency. Although other frequency modulations schemes are possible, the frequency “chirp” generally follows a periodic triangular waveform. With triangular frequency modulation, the distance to the target is proportional to the (maximum) "beat" frequency, i.e. the absolute difference in frequency between the returning signal and the emitted signal (see figure 8:2). Figure 8:2 Typical chirped waveforms and beat frequency for an FMCW laser. fe(t) is the emitted frequency, and fr(t) is the reflected frequency. Bp is the peak beat frequency for a measurement. Dt is the delay in the reflected signal, and Tr is the period of the frequency chirp. Range to the target thus becomes: z = c*Dt/2 = c*Bp*Tr/4*Df There are some competing factors to consider when choosing system parameters for an FMCW laser. Note that the proper beat frequency Bp can only be measured during part of the time. The time of length Dt when it can not be measured is called the dead time. The fraction of dead time is 2*D*t/Tr, and the theoretical maximum measurable distance is zmax = c*Tr/4 at which point Bp is measurable at only a single instant.

To combat noise it is important to make Tr relatively large, in order to keep the dead time as small as possible and increase the available sampling time available to measure the beat frequency. However, a shorter Tr will increase the potential data rate received by the detector. In practice, the maximum range of the laser system is governed by the sensor power and noise levels, and does not come close to the theoretical maximum. The minimum distance that can be measured by the system is dependent upon the amount of time it takes to properly sample the beat frequency signal. It is considered that half a period of the beat signal is necessary, resulting in: zmin = c/4*Df Thus, a larger swept frequency will make it easier to detect small distances, but increasing the swept frequency will increase necessary filter bandwidths and can often introduce nonlinearities in the chirp waveform which, in turn, results in rather poor range estimates. Amplitude Modulated Continuous Wave (AMCW) AMCW lasers operate by modulating the power of the emitted light with a sine wave of a given frequency. The returned energy waveform is delayed by the travel time Dt and appears proportionately phase-shifted when compared to the emitted energy. The distance is proportional to the phase, up to an ambiguity at a 2p phase difference: z = f*Dr/2p The range, z, is thus proportional to the phase difference f and the ambiguity interval, DR. The Z+F laser improves on the usual AMCW method by using a dual-frequency amplitude-modulated signal. The receiver measures the phase difference between the original and returned laser signal at both modulation frequencies. The Z+F laser uses a combination of two modulation frequencies to provide improved accuracy over standard single modulation schemes. Figure 8:3

9. Scanning Problems with LADAR

Figure 9:1

Reflectance Crosstalk Ideally, a laser should measure the same median range to two targets which are equally distant but have different reflectance. In practice, however, this is not always the case. Crosstalk is a phenomenon in which reflectance or intensity values affect the measured range. To some degree, intensity always affects the range values. Lower signal intensity decrease the signal-to-noise ratio and therefore increase the variance in measured range, although this should not affect the average range. The electronics implementation of the device is critical here: both capacitive and inductive links between the intensity and range can cause crosstalk. The sensor optics can also produce effects similar to crosstalk caused by internal reflections. This is called optical crosstalk. The plexiglass protective cover on the optics causes significant optical crosstalk. Although internal reflections may be much reduced without the cover, they can still affect range and intensity measurements significantly when the target surface is far away, and the reflected laser signal from the target thus is low in energy. The nearly constant internal reflections can be considered as a constant phasor added to the target signal. Figure 9:3 illustrates the effect of internal reflection. vir represents the portion of the signal returned from a constant internal reflection, and vt represents the signal returned from the target. The measured return is v, which is the vector sum of vt and vir. The measured intensity (the length of v) is here greater than the intensity returned from the target.

Figure 9:3 Figure 9:4 Figure 9:4 shows a phasor diagram with the same internal reflection, vir, as in figure 9:3. A target at a different distance is represented by vt. In this case the measured intensity of the resulting phasor v is less than the intensity of the signal reflected from the target.

Temporal Mixing "Temporal mixing" occurs when, within a single laser sample, the laser moves from one surface to another. This phenomenon is especially noticeable at edges between darker and lighter surfaces. As a laser moves from a dark surface to a light surface, the returned signal amplitude jumps. This can lead to large errors in phase estimation and thus large range errors. Figure 9:5 Figure 9:5 illustrates the shape of the reflected signal when an AMCW laser sweeps from a dark surface to a bright surface. At time t0, the laser transitions from a surface with 15% reflectivity to one with 100% reflectivity, resulting in a jump in signal amplitude. This frequently results in an incorrect phase difference measurement near the transition time, and can result in a drastically incorrect range measurement.

Figure 9:6 The graph shows the range values for a section of one row of an image centered on an black/white boundary. One can see the large momentary jump in range values at the border between the black and white surfaces caused by temporal mixing. Crosstalk results here in a small (2 cm) difference reported range between the black and white surface. This phenomenon is not caused by the laser itself, and only appears when the laser is combined with a scanner. Abnormally high range values are reported for quite a few pixels at edge boundaries. Some of these may be explained by low returned signal strength caused by specular reflections off metal surfaces. However, the pixels on the edge between the black and white areas cannot be explained by specular reflections, but are instead attributed to the temporal mixing of the laser signal. Temporal mixing can probably not be eliminated completely from any scanning AMCW laser system. Increasing the modulation frequency and signal processing bandwidth or reducing scan speeds may reduce the problem.

Photon Noise There are two major types of noise that contribute to the reflected signal, and makes it hard to interpret. One is photon noise, and is the result of ambient (non-laser) photons seen at the photodetector. Thus, it is independent of the laser signal itself, and can be measured with an active photodetector and inactive laser. In daylight, photon noise can be significant. Photon noise can sometimes overpower the signal received from some surfaces beyond 20 or 30 meters in strong daylight. Another type of noise is "general" signal noise, its amplitude being dependent on signal amplitude. This type of noise is attributable to electronic noise in the laser modulation and/or noise in the acquisition and signal processing electronics. Photon noise is independent of range and reflectance, since it is independent of the actual signal. It may be reduced in comparison to the signal, however, by reducing the sampling frequency of the detector or increasing the laser signal strength.

Intensity Drift Signal drift can be a problem in almost all sensor systems. Laser systems are no different. Drift in laser systems is primarily caused by changes in temperature. Temperature changes can affect the laser system in a number of ways. The main effect, however, is that changes in temperature tend to alter the length of the laser cavity and thus the laser frequency. For laser ranging systems, the change in laser frequency can show up as a shift in phase resulting in a range drift. For intensity measurements, changes in the laser frequency affect the gain of the optical filter in front of the receiver. As the frequency shifts farther away from the center of the optical bandwidth filter, the measured intensity of the signal will drop.

Problem with the Intensity-based Method A problem inherent to the intensity-based method is that a given intensity measurement has multiple possible causes or interpretations. A pixel of medium brightness may be caused by a white object at a long distance or a dark object at a close distance, or it could be an infinite number of other possibilities. This many-to-one mapping from the 3D world to the 2D image is a problem inherent to all vision methods that try to reconstruct 3D world information. Assuming a relatively flat world with a number of obstacles removes some possibilities, but does not eliminate all ambiguity. In particular, a dark obstacle may appear like the road, and a bright road patch may look like an obstacle.

Dark Obstacles It could clearly be a problem to detect an object that does not reflect the laser beam. Asphalt is an example; road pixel intensities often have near zero intensity at long ranges which makes them inseparable from darker objects with the current laser power. At short ranges or with increased laser power, black obstacles might be separated from road pixels and detected as obstacles. We have earlier used the term negative obstacles for things that are "missing", that ought to be in a certain place. These can only be detected by comparing the view with a digitized reference image, stored in a databank. Dark obstacles will have to be treated the same way, i.e. comparison with a reference image. And the reference used would in most cases have had to be sampled under the same light conditions as those prevailing at the time of scanning.

Other Considerations Laser reflectance depends on many factors, such as: target range, angle of incidence, albedo, surface roughness, and shininess (how much energy the surface reflects specularly). While it is unlikely that all of these parameters can be determined from a limited number of reflectance measurements from an unknown obstacle, the model can be simplified for the purpose of target range estimation. While the full reflectance model cannot be fully exploited in the detection of obstacles, it is useful to understanding where intensity-based segmentation methods will fail. There are some surfaces that, when vertical, will appear as being nearly horizontal. For example, an obstacle that has a significantly lower albedo than the background may look very similar to the background because of the difference in incidence angle. These same surfaces will have to be detected by a different obstacle detection method, to ensure that the obstacle is indeed detected.

Figure 9:9 Detection of a pointed or edgy object can be tricky. As shown in this example, pulses 1 and 3 are deflected in other directions, and only pulse 2 reaches the detector. The result is an image much smaller than the actual size of the object. Alternatively, these same surfaces might be detectable with a different laser wavelength since the albedo is wavelength-dependent.

10. Calculating Safety Requirements

he necessary lookahead distance for an obstacle detection system is the distance the vehicle travels in the time it takes to sense, process and detect an object, and apply the brakes, plus the stopping distance. If: L0 is the lookahead distance, in meters, v0 is the initial velocity of the vehicle (meters/second), a is the braking deceleration (meters/second2), ts = time for sensing (sec.), tp = time for processing the data (sec.), tb = time for braking to a halt (sec.) Then we get the formula: L0 = v0(ts + tp + tb) + v02/2*a To guarantee safety, the obstacle detection system must be able to examine terrain at least as fast as it moves over it. This requires the throughput ratio, þcyc to be smaller than 1. The throughput ratio is given by: þcyc = v*Tcyc/DR Where Tcyc is the cycle time in seconds v = velocity of vehicle (in meters per sec.) and DR is the projection of the pixels examined by the algorithm in a single cycle onto the ground plane. While the first equation is rather obvious, this one might need some explaining. Simply put, as the velocity increases, the cycle time has to be correspondingly shorter, to keep the product of these 2 figures under a certain value. The value of DR then has to be large enough to make the whole factor less than one. DR is then an additional stretch of road, on top of the lookahead distance.

Figure 10:1 1/þcyc is the terrain oversampling factor. Oversampling factors greater than one may allow the system to track a potential obstacle over multiple frames for increased system reliability. One can thus surmise that Tcyc is the time required to compare a sufficient number of frames to determine whether there is an obstacle ahead. While þcyc is calculated from road conditions, where the scanner looks downwards toward the roadbed, it is a relevant factor to calculate with when considering beam traffic systems as well. But; only if the scanner is mounted on the vehicle. Here we find one of the two biggest advantages with having the scanners mounted on the beams (the other advantage is, as mentioned, that the scanner will then be kept steady).

11. Microwave Radar Technology

he first radar prototypes tested on road vehicles were by SEL Lorentz together with Daimler-Benz, and AEG Telefunken together with Bosch and VDO. They were based on a single fixed beam antenna, and were inefficient in the detection of obstacles on the side lanes, bridges and of road structures around curves, and the operative range was limited to about 50 m. In the following years radar companies limited the detection to moving targets. The problem of the side lane obstacles was solved with an increase of the angular field of view, and with the addition of the angular resolution by using multi-beam solutions, so the operative range reached around 100 meters.

A mechanical scanning antenna solution was chosen for the ACC radar. The chosen antenna configuration could guarantee good angular accuracy for a wider field of view, when compared to the fixed multi-beam solutions, so the operative range was extended to 150 m, but stationary obstacles were still not signalled. The third generation of radar prototype systems detects stationary obstacles up to the braking distance. In these cases an obstacle is located and identified at around 200 m. To this generation belongs the 77 GHz scanning radar developed within the AWARE project for collision warning and avoidance (CW/A) vehicle systems.

The CW/A system is intended to be applicable in motor- and highway traffic (urban traffic is not covered at this stage). Moving and stationary obstacles in front of the vehicle are detected and tracked, post-processing modules analyse the radar tracks, and when necessary the driver is alerted. The main limitations of the state of the art microwave radars are related to the detection of objects not belonging to the road, like bridges, to the difficulty to extract road geometry, and to the relatively rough classification of objects types. The human machine interface of a radar system is typically based on visual (like icons on a LCD changing color to red if the obstacle comes so close as to become an imminent danger) and/or acoustic warnings.

One common and very useful method is to vary the frequency between two end values during each scan line (i.e. from one end of the scanned area to the other). The example in figure 11:1 shows how much information one can get out of this. The echo pulse has the same frequency as the wave which hit the object. The position of the echo along the time axis reveals the vertical position of the object, if we know which scanline made the hit (number 2 in this example). The position of the echo along the frequency axis reveals the horizontal position of the object. The size of the echo along both axis reveals the dimensions of the object. The time lag between the echo and the time the same frequency was sent reveals the distance to the object. The amplitude of the echo can, to some extent, reveal which scan line it belongs to, should it be a distant object. Comparison between successive frames will finally reveal if and how the object is moving, relative to the scanner.

Figure 11.1

12. Far Infrared Sensor Technology

he fast evolution in the field of uncooled infrared matrix sensors operating in the range of 8-14 microns (i.e. with a wavelength of 8-14 micro-meters) allows the presence on the market (since 1997) of a number of non-automotive products based on "microbolometric" sensors. These products are not suitable for in-vehicle applications, due to their cost and dimensions, but their performances provide high resolution and good quality images in reduced visibility conditions. The output of a far infrared sensor is an image that provides an enhanced view of the road ahead as it is the thermal map of the scene ahead totally independent from the presence of illumination.

The cost of these cameras can be reduced by 30% with the use of low cost optics (transparent in the required spectral range). The non-automotive optics are made of rare materials like Germanium, the alternatives are doped Silicon and the new material TEX glass, which show promise, as the fabrication process will be less costly. Furthermore, ongoing development on microbolometer sensors will allow reducing the cost of the microbolometer sensor to 150-100 Euros for large mass production quantities. This reduction will be allowed as the next sensor generation will be based on an all Silicon technology that will replace the actual hybrid technology which has high production costs.

In USA, Raytheon developed an automotive far infrared camera for the Night Vision System from GM (USA). This infrared sensor is pyroelectric and it needs a mechanical chopper for its operation. The presentation of images to the driver is done via a head-up display developed by Delco Delphi. It can only be used at night. In parallel, within the project Brite Euram DARWIN, an automotive far infrared camera has been developed, The sensor is high-resolution microbolometric, without the need of a mechanical chopper and the optics is made of TEX glass. The image is presented to the driver, without image processing, in a head-up display for night vision application. Both types of HUDs display the information in a virtual image that "floats" in front of the car at a fixed distance.