Building mobile and embedded consumer devices that can "see"

Eldad Melamed, CEVA

July 5, 2011

Eldad Melamed, CEVA

Other challenges that face detection algorithms must overcome are: pose (frontal, 45 degree, profile, upside down), presence or absence of structural components (beards, mustaches, glasses), facial expression, occlusion (faces may be partially occluded by other objects), image orientation (face appearance directly vary for different rotations about the camera's optical axis), and imaging conditions (lighting, camera characteristics, resolution).

Although many face detection algorithms have been introduced in the literature, only a handful of them can meet the real-time constraints of mobile devices. While many face detection algorithms have been reported to generate high detection rates, very few of them are suitable for real-time deployment on mobile devices such as cell-phones due to the computation and memory limitations of these devices.

Cascade classifier algorithm provides more efficiency
Normally, real-time implementations of face detection algorithms are done on PC platforms with relatively powerful CPUs and large memory sizes. The examination of the existing face-detection products reveal that the algorithm introduced by Viola and Jones in 2001 has been widely adopted. This is a breakthrough work that enabled appearance-based methods to run in real-time, while keeping the same or improved accuracy.

The algorithm uses a boosted cascade of simple features and can be divided to three main components:

(1) Integral graph--efficient convolution for fast feature evaluation;
(2) Use Adaboost for feature selection and sort them in the order of importance. Each feature can be used as a simple (weak) classifier;
(3) Use Adaboost to learn the cascade classifier (ensemble of weak classifiers) that filters out the regions that most likely do not contain faces. Figure 2 is a schematic representation of the cascade of classifiers. Within an image, most sub images are non-face instances.

Based on this assumption we can use smaller and efficient classifiers to reject many negative examples at early stage while detecting almost all the positive instances. More complex classifiers are used at later stage to examine difficult cases.

Example: 24 stages cascade classifier
2-feature classifier in the first stage => rejecting 60% non-faces while detecting 100% faces
5-feature classifier in the second stage => rejecting 80% non-faces while detecting 100% faces
20-feature classifier in stages 3, 4, and 5
50-feature classifier in stages 6 and 7
100-feature classifier in stages 8 to 12
200-feature classifier in stage 13 to 24



Click on image to enlarge. Figure 2. The cascade of classifiers

During the first stage of the face detection algorithm, rectangle features can be computed very rapidly using an intermediate representation called integral image. As shown in Figure 3 the value of the integral image at point (x,y) is the sum of all the pixels above and to the left. The sum of pixels within D can be computed as 4+1-(2+3).


Click on image to enlarge. Figure 3.  Rapid evaluation of rectangular features by integral image

Real-time recognition requires parallelism
To implement a real time face detection application on embedded device there is a need for a high-level of parallelism, combining instruction-level and data-level parallelism. Very long instruction word (VLIW) architectures allow a high level of concurrent instruction processing, providing extended parallelism as well as low power consumption.

Single instruction multiple data (SIMD) architectures enable single instructions to operate on multiple data elements resulting in code size reduction and increased performance. Using vector processor architecture accelerates these integral sum calculations by a factor of the parallel number of adders/subtractors. If a vector register can be loaded with 16 pixels, and these pixels can be added to the next vector simultaneously, the acceleration factor is 16. Evidently, adding similar vector processing unit to the processor doubles this factor.