Feature Detection using Integral Images

Figure 4: Left: Computation of feature values $F$ in the shaded region is based on the four upper rectangles. Middle: Calculation of the rotated integral image $I_r$. Right: Four lookups in the rotated integral image are required to compute the feature value a rotated feature $F_r$.

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 [22]. The features are called Haar-like, since they follow the same structure as the Haar basis, i.e., step functions introduced by Alfred Haar to define wavelets. They are also used in [13,3,20,22]. Fig. 3 (right) shows the eleven basis features, i.e., edge, line, diagonal and center surround features. The base resolution of the object detector is $30 \times 30$ pixels, thus, the set of possible features in this area is very large (642592 features, see [13] for calculation details). A single feature is effectively computed on input images using integral images [22], also known as summed area tables [13]. An integral image $I$ is an intermediate representation for the image and contains the sum of gray scale pixel values of image $N$ with height $y$ and width $x$, i.e.,

$$I(x,y) = \sum_{x'=0}^{x}\sum_{y'=0}^{y} N(x',y').$$

The integral image is computed recursively, by the formulas: $I(x,y) = I(x,y-1) + I(x-1,y) + N(x,y) - I(x-1,y-1)$ with $I(-1,y) = I(x,-1) = I(-1,-1) = 0$, therefore requiring only one scan over the input data. This intermediate representation $I(x,y)$ allows the computation of a rectangle feature value at $(x,y)$ with height and width $(h,w)$ using four references (see Fig. 4 (left)):

$$F(x,y,h,w) = I(x,y) + I(x+w,y+h) -$$

$$I(x,y+h) - I(x+w,y).$$

For the computation of the rotated features, Lienhart et. al. introduced rotated summed area tables that contain the sum of the pixels of the rectangle rotated by 45$^\circ$ with the bottom-most corner at $(x,y)$ and extending till the boundaries of the image (see Fig. 4 (middle and right)) [13]:

$$I_r(x,y) = \sum_{x'=0}^{x}\sum_{y'=0}^{x - \vert x'-y\vert} N(x',y').$$

The rotated integral image $I_r$ is computed recursively, i.e., $I_r(x,y) = I_r(x-1, y-1) + I_r(x+1, y-1) - I_r(x, y-2) + N(x,y) + N(x, y-1)$ using the start values $I_r(-1,y) = I_r(x, -1) = I_r(x,-2) = I_r(-1, -1) = I_r(-1, -2) = 0$. Four table lookups are required to compute the pixel sum of any rotated rectangle with the formula:

$$F_r(x,y,h,w) \!\! = \!\!\!\!\!\! I_r(x+w-h, y+w+h-1) + I_r(x, y-1) -$$

$$I_r(x-h,y+h-1) - I_r(x+w,y+w-1)$$

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 minimum number of examples are misclassified. Furthermore, the return values $(\alpha, \beta)$ 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.