Haar-like features

Haar-like features are digital image features used in object recognition. They owe their name to their intuitive similarity with Haar wavelets.

Historically, working with only image intensities (i.e., the RGB pixel values at each and every pixel of image) made the task computationally expensive. A publication by Papageorgiou et al. [Papageorgiou, Oren and Poggio, "a general framework for object detection", International Conference on Computer Vision, 1998.] discussed working with an alternate feature set instead of the usual image intensities. This feature set considers rectangular regions of the image and sums up the pixels in this region. This sum is used to categorize images. For example, let us say we have an image database with human faces and buildings. It is possible that if the eye and the hair region of the faces is considered, the sum of the pixels in this region would be quite high for the human faces and arbitrarily high or low for the buildings. The value for the latter would depend on the structure of the building, its environment while the values for the former will be more less roughly the same. We could thus categorize all images whose Haar-like feature in this rectangular region to be in a certain range of values as one category and those falling out of this range in another. This might roughly divide the set of images into ones having a lot of faces and a few buildings and the other having a lot of buildings and a few faces. This procedure could be iteratively carried out to further divide the image clusters.

Rectangular Haar-like features

A simple rectangular Haar-like feature can be defined as the difference of the sum of pixels of areas inside the rectangle, which can be at any position and scale within the original image. This modified feature set is called "2 rectangle feature". Viola and Jones [Viola and Jones, "Rapid object detection using boosted cascade of simple features", Computer Vision and Pattern Recognition, 2001] also defined 3 rectangle features and 4 rectangle features. The values indicate certain characteristics of a particular area of the image. Each feature type can indicate the existence (or not) of certain characteristics in the image, such as edges or changes in texture. For example, a 2 rectangle feature can indicate where lies the border between a dark region and a light region.

Fast computation of Haar-like features

One of the contributions of Viola and Jones was to use Summed-area Tables [Crow, F, "Summed-area tables for texture mapping", in Proceedings of SIGGRAPH, 18(3):207-212, 1984] , which they called "Integral Images". Integral Images can be defined as 2-dimensional lookup table in the form of a matrix with the same size of the original image. Each element of the Integral Image contains the sum of all pixels located on the up-left region of the original image (in relation to the element's position). This allows to compute sum of rectangular areas in the image, at any position or scale, using only 4 lookups:

$sum\; =\; pt\_\{4\}\; -\; pt\_\{3\}\; -\; pt\_\{2\}\; +\; pt\_\{1\}$

where points $pt\_\{n\}$ belong to the Integral Image (include a figure).

Each Haar-like feature may need more than 4 lookups, depending on how it was defined. Viola and Jones's 2 rectangle features need 6 lookups, 3 rectangle features need 8 lookups and 4 rectangle features need 9 lookups.

Tilted Haar-like features

Lienhart and Maydt [Lienhart, R. and Maydt, J., "An extended set of Haar-like features for rapid object detection", ICIP02, pp. I: 900-903, 2002] introduced the concept of a tilted ($45^o$) Haar-like feature. This was used to increase the dimensionality of the set of features in an attempt to improve the detection of objects in images. This was successful, as some of these features are able to describe the object in a better way. For example, a 2 rectangle tilted Haar-like feature can indicate the existence of an edge at $45^o$.

Messom and Barczak [Messom, C.H. and Barczak, A.L.C., "Fast and Efficient Rotated Haar-like Features Using Rotated Integral Images", Australian Conference on Robotics and Automation (ACRA2006), pp. 1-6, 2006] extended the idea to a generic rotated Haar-like feature. Although the idea sounds mathematically sound, practical problems prevented the use of Haar-like features at any angle. In order to be fast, detection algorithms use low resolution images, causing rounding errors. For this reason, rotated Haar-like features are not commonly used.

References

* Haar A. "Zur Theorie der orthogonalen Funktionensysteme", Mathematische Annalen, 69, pp. 331-371, 1910.