IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,
lights is a ubiquitous vehicle feature at night; however, it could be confused with traffic lights and background lights. We believe that these cues have limited employability.
Utilizing horizontal and vertical edges for HG is probably the most promising, knowledge-based, approach reported in the literature. Our experience with using edge information in realistic experiments has been very positive . Although this method can suffer from false positives, many of them can be rejected quickly using simple tests (e.g., aspect ratio). From a practical point of view, there are fast implementations of edge detection in hardware making this approach even more attractive. The main problem with this approach is that it depends on a number of parameters that could affect system performance and robustness. For example, we need to decide the thresholds for the edge detection step, the thresholds for choosing the most important vertical and horizontal edges, and the thresholds for choosing the best maxima (i.e., peaks) in the profile images. A set of parameter values might work well under certain conditions, however, they might fail in other situations. We have described in Section 5 a multiresolution scheme addressing these issues.
Critique of Stereo-Based HG Methods
Stereo-based methods have been employed extensively for HG, however, traditional implementations are time con- suming and work well only if the camera parameters have been estimated accurately. As a result, their performance is significantly impaired. Using stereo vision to hypothesize vehicle location, dense disparity maps are necessary to guarantee that all regions are searched for potential vehicles. Naive approaches to stereo computation are not suitable for dynamic object detection at reasonable vehicle speed due to the high complexity (i.e., Oðdm2n2Þ, where d is the number of shifts over which the correspondence search is performed, m is the size of the support window, and n is the size of the images). There have been several approaches to overcome this problem, such as, computing sparse disparity maps , , employing multiresolution schemes , , or using prior knowledge about the environment to limit the search for correspondences .
Estimating the stereo parameters accurately is also hard to guarantee in an on-road scenario. Since the stereo rig is on a moving vehicle, vibrations from the vehicle’s motion and windy conditions might shift the cameras, while the height of the cameras keeps changing due to the vehicle’s suspension. Suwa et al.  proposed a method to update the parameters and compensate for errors caused by camera movements. The 3D measurements of a stereo-based system are calculated using:
Mw ¼ RcMc þ tc;
where Mw and Mc represent vectors in the world coordinate and camera coordinate systems, Rc is a rotation matrix, and tc is a translation vector. A two-parameter sway model was used in : the sway direction angle and the sway range. Incorporating the effect of sway parameters leads to a
modified model: Mw ¼ RRðR
RMc þ tcÞ þ t;
w h e r e ¼ 2 s i n 1 ð d 2 H Þ , d i s t h e s w a y r a n g e , H i s t h e h e i g h the camera, denotes the sway direction angle, and the set up tilt angle. The two sway parameters were estimated from t o f
corresponding pairs with sway and without sway. The image data without sway was assumed to have been obtained from the no sway image while the sway data was obtained by using correlation. Estimation was done using least squares.
Bertozzi et al.  have also analyzed the parameter drifts and argued that vibrations affect, mostly, extrinsic para- meters, and not the intrinsic parameters. A fast self-calibra- tion method was considered to deal with this issue. Eight carefully designed markers were put on the hood, four for each of the two cameras. Since the world coordinates of the markers were known, the determination of their image coordinates was sufficient to compute the position and orientation of the cameras in the same reference system.
Critique of Motion-Based HG
In general, motion-based methods can detect objects based on relative motion information. Obviously, this is a major limitation, for example, this method cannot be used to detect static obstacles, which can represent a big threat. Despite this fact, employing motion information for HG has shown promising results; however, it is computationally intensive while its performance is affected by several factors. Generating a displacement vector for each pixel (continuous approach) is time-consuming and impractical for a real-time system. In contrast, discrete methods based on image features such as color blobs  or local intensity minima and maxima  has shown good performance while being faster. There have been also attempts to speed up motion-based computations using multiresolution schemes . Several factors affect the computation of motion information  including:
Displacements between consecutive frames. Fast move- ment of the host vehicles causes significant pixel displacements. Points in the image can move by more than five pixels, when the car moves at a speed faster than 30 km/h. Consequently, aliasing in the computation of the temporal derivatives introduces errors into the computation of optical flow. Lack of textures. Large portions in the images represent the road bed, where gray-level variations are quite small, especially when driving the vehicle in a country road. Significant instability can be introduced to the computation of the spatial deriva- tives due to texture insufficiency. Shocks and vibrations. Image motion is the sum of a smooth component due to the car ego-motion and a high frequency component due to the camera shocks and vibrations. In the presence of shocks and vibrations, caused by mechanical instability of the camera, a high frequency noise is introduced to the intensity profile. This noise gets greatly amplified during the computation of the temporal derivatives. In general, error introduced by shocks and vibra- tions is small if the camera is mounted on high quality antivibrating platforms and the vehicle is moving along usual roads. However, if the camera is mounted less carefully or the vehicle is driven on a bumpy road, the error can be 10 times larger.
Among these factors, camera movement is the main reason that traditional differential methods fail. If we can counter- balance camera movements, then these methods could become very useful. This is the objective of another research