wrong indices used in Haar feature detection and elsewhere (Bug #562)

Hi,

on the mailing list, under the heading "Bug in Haar feature detection?", the following has been discussed:

zingo4ringo said:

I have been trying to write a Haar feature and face detection on another platform and I'm using OpenCV as a reference, however, I think there is a bug in OpenCV's implementation specifically when accessing the Integral Image, as described below. The effect is that the code in OpenCV is testing a bigger box than defined in the face data.

I am using the 'haarcascade_frontalface_alt.xml' face data.

This has a window of 20x20 pixels. The .xml defines different boxes that need to be tested. The boxes are defined as x,y,width, and height.

If you look at the data you can find sets where x=0 and width=20, which means, that since this is a 20x20 window, you need to test a rectangle which has a width of 20 pixels and which starts at the first pixel. (You never have a width of 0. Also a width of 1 means that the rectangle is only one pixel wide).

The bug in OpenCV is that for such a situation it tries to find the area (using the integral image) for a box that is 21 pixels wide (i.e. a width of 1 will be treated as 2 pixels). This is caused by the addressing in the integral image.

In cvhaar.cpp, inside cvHaarDetectObjects(), I tried to dump the IntegralImage using:

for(jj=0; jj <= 20; jj++)
for(ii=0; ii <= 20; ii++)
printf("II = %d\n", ii, jj,
(sum_elem_ptr(*sum, jj, ii))r0);

(after calling cvSetImagesForHaarClassifierCascade).

The interesting part is that for jj or ii equal 0, there data is zero, i.e. there is no image data, and for ii/jj == 20, there is data.

Yet when accessing the IntegralImage, the code uses (see cvSetImagesForHaarClassifierCascade() ):

cascade->p0 = sum_elem_ptr(*sum, equRect.y, equRect.x);
 cascade->p1 = sum_elem_ptr(*sum, equRect.y, equRect.x + equRect.width );
 cascade->p2 = sum_elem_ptr(*sum, equRect.y + equRect.height, equRect.x );
 cascade->p3 = sum_elem_ptr(*sum, equRect.y + equRect.height,
                                     equRect.x + equRect.width );

Which I think should really be adding +1 when we are using .x or .y only (no need to add the 1 when using height or width, since it's already included in there):

cascade->p0 = sum_elem_ptr(*sum, equRect.y+1, equRect.x+1);
 cascade->p1 = sum_elem_ptr(*sum, equRect.y+1, equRect.x + equRect.width );
 cascade->p2 = sum_elem_ptr(*sum, equRect.y + equRect.height, equRect.x +1);
 cascade->p3 = sum_elem_ptr(*sum, equRect.y + equRect.height,
                                     equRect.x + equRect.width );

Am I right in assuming this is a bug and OpenCV is testing bigger boxes than it should be?

and also:

Indeed, the variance calculation inside the function is also wrong: it tries to find the average pixel and the average pixel_squared, and for this it uses a 19x19 (=361 pixels) window (and not 20x20), yet for finding the average it divides by 18x18=324 ('inv_window_area' variable), which is wrong!

Incidental, the version I wrote which uses the correct box definition has less false-positives stage 0 and stage 1 detection on the example face detector I am using. Could this be a reason why other users are reporting slow facedetection?

And this is confirmed by Robin Hewitt:

Yes, I noticed this too -- as early as version 1.0. I've never seen anything
really bad happen because of it, but it might somewhat reduce accuracy. The
variance calculation is similarly affected and that probably has a greater
effect when scaling to larger rectangles. There are similar miscalculations
scattered throughout many functions in OpenCV because of the way rectangles are
defined. I prefer to use explicit corner points and scale these directly because
most of the time what you want is a rescaled point, not a width or height. If
width or height is needed, I compute as 1+xmax-xmin. OpenCV convention starts
with width and height, then computes xmax and ymax. Individual programmers
almost never remember the extra pixel. If the error is made consistently (which
it is), the effects will often cancel out, but not always. Scaling the variance
roi is a case where the effect doesn't cancel.

Any chance of seeing this fixed?