Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Viola-Jones' face detection claims 180k features

I've been implementing an adaptation of Viola-Jones' face detection algorithm. The technique relies upon placing a subframe of 24x24 pixels within an image, and subsequently placing rectangular features inside it in every position with every size possible.

These features can consist of two, three or four rectangles. The following example is presented.

Rectangle features

They claim the exhaustive set is more than 180k (section 2):

Given that the base resolution of the detector is 24x24, the exhaustive set of rectangle features is quite large, over 180,000 . Note that unlike the Haar basis, the set of rectangle features is overcomplete.

The following statements are not explicitly stated in the paper, so they are assumptions on my part:

  1. There are only 2 two-rectangle features, 2 three-rectangle features and 1 four-rectangle feature. The logic behind this is that we are observing the difference between the highlighted rectangles, not explicitly the color or luminance or anything of that sort.
  2. We cannot define feature type A as a 1x1 pixel block; it must at least be at least 1x2 pixels. Also, type D must be at least 2x2 pixels, and this rule holds accordingly to the other features.
  3. We cannot define feature type A as a 1x3 pixel block as the middle pixel cannot be partitioned, and subtracting it from itself is identical to a 1x2 pixel block; this feature type is only defined for even widths. Also, the width of feature type C must be divisible by 3, and this rule holds accordingly to the other features.
  4. We cannot define a feature with a width and/or height of 0. Therefore, we iterate x and y to 24 minus the size of the feature.

Based upon these assumptions, I've counted the exhaustive set:

const int frameSize = 24; const int features = 5; // All five feature types: const int feature[features][2] = {{2,1}, {1,2}, {3,1}, {1,3}, {2,2}};  int count = 0; // Each feature: for (int i = 0; i < features; i++) {     int sizeX = feature[i][0];     int sizeY = feature[i][1];     // Each position:     for (int x = 0; x <= frameSize-sizeX; x++) {         for (int y = 0; y <= frameSize-sizeY; y++) {             // Each size fitting within the frameSize:             for (int width = sizeX; width <= frameSize-x; width+=sizeX) {                 for (int height = sizeY; height <= frameSize-y; height+=sizeY) {                     count++;                 }             }         }     } } 

The result is 162,336.

The only way I found to approximate the "over 180,000" Viola & Jones speak of, is dropping assumption #4 and by introducing bugs in the code. This involves changing four lines respectively to:

for (int width = 0; width < frameSize-x; width+=sizeX) for (int height = 0; height < frameSize-y; height+=sizeY) 

The result is then 180,625. (Note that this will effectively prevent the features from ever touching the right and/or bottom of the subframe.)

Now of course the question: have they made a mistake in their implementation? Does it make any sense to consider features with a surface of zero? Or am I seeing it the wrong way?

like image 967
Paul Lammertsma Avatar asked Nov 10 '09 12:11

Paul Lammertsma


People also ask

How many Haar like features Viola and Jones identified in their research?

There are 3 types of Haar-like features that Viola and Jones identified in their research: Edge features. Line-features. Four-sided features.

How does viola jones algorithm work?

The Viola-Jones algorithm works with frontal face Images that is why all the features of a human face must be visible i.e., two eyes and eyebrows, nose, lips, symmetry, and relative position of features and parts of the face. The Viola-Jones algorithm looks for hundreds of these kinds of features in the face.


2 Answers

all. There is still some confusion in Viola and Jones' papers.

In their CVPR'01 paper it is clearly stated that

"More specifically, we use three kinds of features. The value of a two-rectangle feature is the difference between the sum of the pixels within two rectangular regions. The regions have the same size and shape and are horizontally or vertically adjacent (see Figure 1). A three-rectangle feature computes the sum within two outside rectangles subtracted from the sum in a center rectangle. Finally a four-rectangle feature".

In the IJCV'04 paper, exactly the same thing is said. So altogether, 4 features. But strangely enough, they stated this time that the the exhaustive feature set is 45396! That does not seem to be the final version.Here I guess that some additional constraints were introduced there, such as min_width, min_height, width/height ratio, and even position.

Note that both papers are downloadable on his webpage.

like image 30
Laoma from Singapore Avatar answered Sep 22 '22 04:09

Laoma from Singapore


Upon closer look, your code looks correct to me; which makes one wonder whether the original authors had an off-by-one bug. I guess someone ought to look at how OpenCV implements it!

Nonetheless, one suggestion to make it easier to understand is to flip the order of the for loops by going over all sizes first, then looping over the possible locations given the size:

#include <stdio.h> int main() {     int i, x, y, sizeX, sizeY, width, height, count, c;      /* All five shape types */     const int features = 5;     const int feature[][2] = {{2,1}, {1,2}, {3,1}, {1,3}, {2,2}};     const int frameSize = 24;      count = 0;     /* Each shape */     for (i = 0; i < features; i++) {         sizeX = feature[i][0];         sizeY = feature[i][1];         printf("%dx%d shapes:\n", sizeX, sizeY);          /* each size (multiples of basic shapes) */         for (width = sizeX; width <= frameSize; width+=sizeX) {             for (height = sizeY; height <= frameSize; height+=sizeY) {                 printf("\tsize: %dx%d => ", width, height);                 c=count;                  /* each possible position given size */                 for (x = 0; x <= frameSize-width; x++) {                     for (y = 0; y <= frameSize-height; y++) {                         count++;                     }                 }                 printf("count: %d\n", count-c);             }         }     }     printf("%d\n", count);      return 0; } 

with the same results as the previous 162336


To verify it, I tested the case of a 4x4 window and manually checked all cases (easy to count since 1x2/2x1 and 1x3/3x1 shapes are the same only 90 degrees rotated):

2x1 shapes:         size: 2x1 => count: 12         size: 2x2 => count: 9         size: 2x3 => count: 6         size: 2x4 => count: 3         size: 4x1 => count: 4         size: 4x2 => count: 3         size: 4x3 => count: 2         size: 4x4 => count: 1 1x2 shapes:         size: 1x2 => count: 12             +-----------------------+         size: 1x4 => count: 4              |     |     |     |     |         size: 2x2 => count: 9              |     |     |     |     |         size: 2x4 => count: 3              +-----+-----+-----+-----+         size: 3x2 => count: 6              |     |     |     |     |         size: 3x4 => count: 2              |     |     |     |     |         size: 4x2 => count: 3              +-----+-----+-----+-----+         size: 4x4 => count: 1              |     |     |     |     | 3x1 shapes:                                |     |     |     |     |         size: 3x1 => count: 8              +-----+-----+-----+-----+         size: 3x2 => count: 6              |     |     |     |     |         size: 3x3 => count: 4              |     |     |     |     |         size: 3x4 => count: 2              +-----------------------+ 1x3 shapes:         size: 1x3 => count: 8                  Total Count = 136         size: 2x3 => count: 6         size: 3x3 => count: 4         size: 4x3 => count: 2 2x2 shapes:         size: 2x2 => count: 9         size: 2x4 => count: 3         size: 4x2 => count: 3         size: 4x4 => count: 1 
like image 155
Amro Avatar answered Sep 19 '22 04:09

Amro