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 $30 \times 30$ 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 $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. (right)):

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

$$end{tex2html_deferred}$$

$$end{tex2html_deferred} I(x,y+h) - I(x+w,y).$$

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$^\circ$ with the bottom-most corner at $(x,y)$ and extending till the boundaries of the image (see Fig. (bottom left)) [12]:

$$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-1) + 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) +$$

$$end{tex2html_deferred}$$

$$end{tex2html_deferred} I_r(x, y-1) - I_r(x-h,y+h-1) -$$

$$end{tex2html_deferred}$$

$$end{tex2html_deferred} 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.

Figure: Top left: Edge, line, diagonal and center surround features are used for classification. Top right: Computation of feature values $F$ in the shaded region is based on the four upper rectangles. Bottom left: Calculation of the rotated integral image $I_r$. Bottom right: Four lookups in the rotated integral image are required to compute the feature value of a rotated feature $F_r$.

   

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 $(\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.