Next: Learning Classification Functions Up: Detecting Objects in 3D Previous: Rendering Images from Scan

## Feature Detection using Integral Images

There are many motivations for using features rather than pixels directly. For mobile robots, a critical motivation is that feature-based systems operate much faster than pixel-based systems [25]. The features used here have the same structure as the Haar basis functions, i.e., step functions introduced by Alfred Haar to define wavelets [8]. They are also used in [12,15,25]. Fig. (left) shows the eleven basis features, i.e., edge, line, diagonal and center surround features. The base resolution of the object detector is for instance pixels, thus, the set of possible features in this area is very large (642592 features, see [12] for calculation details). In contrast to the Haar basis functions, the set of rectangle features is not minimal. A single feature is effectively computed on input images using integral images [25], also known as summed area tables [12]. An integral image is an intermediate representation for the image and contains the sum of gray scale pixel values of image with height and width , i.e.,

The integral image is computed recursively, by the formulas: with , therefore requiring only one scan over the input data. This intermediate representation allows the computation of a rectangle feature value at with height and width using four references (see Fig. (right)):

For computing the rotated features, Lienhart et. al. introduced rotated summed area tables that contain the sum of the pixels of the rectangle rotated by 45 with the bottom-most corner at and extending till the boundaries of the image (see Fig. (bottom left)) [12]:

The rotated integral image is computed recursively, i.e., using the start values . Four table lookups are required to compute the pixel sum of any rotated rectangle with the formula:

Since the features are compositions of rectangles, they are computed with several lookups and subtractions weighted with the area of the black and white rectangles.

To detect a feature, a threshold is required. This threshold is automatically determined during a fitting process, such that a minimal number of examples are misclassified. Furthermore, the return values of the feature are determined, such that the error on the examples is minimized. The examples are given in a set of images that are classified as positive or negative samples. The set is also used in the learning phase that is briefly described next.

Next: Learning Classification Functions Up: Detecting Objects in 3D Previous: Rendering Images from Scan
root 2005-05-03