Распознавание лиц Виолы-Джонс требует 180 тысяч функций

При ближайшем рассмотрении ваш код мне кажется правильным; что заставляет задуматься о том, были ли у первоначальных авторов отдельные ошибки. Я думаю, кто-то должен посмотреть, как OpenCV реализует это!

Тем не менее, есть одно предложение, чтобы упростить понимание, - это изменить порядок циклов for, сначала перейдя по всем размерам, а затем перебирая возможные местоположения с учетом размера:

#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;
}

с теми же результатами, что и предыдущий 162336

Чтобы проверить это, я протестировал случай окна 4x4 и вручную проверил все варианты (легко подсчитать, поскольку формы 1x2 / 2x1 и 1x3 / 3x1 одинаковы, только повернуты на 90 градусов):

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

все. В документах Виолы и Джонса все еще есть некоторая путаница.

В их статье CVPR'01 четко указано, что

"В частности, мы используем три типа функций. Значение двухпрямоугольника - это разница между суммой пикселей в две прямоугольные области. Области имеют одинаковый размер и форму и примыкают друг к другу по горизонтали или вертикали (см. рис. 1). Элемент из трех прямоугольников вычисляет сумму в двух внешних прямоугольниках вычитается из суммы в центральном прямоугольнике. Наконец, четырехугольник ".

В статье IJCV'04 сказано то же самое. Итого 4 функции. Но, как ни странно, на этот раз они заявили, что исчерпывающий набор функций составляет 45396! Это не похоже на окончательную версию. Здесь я предполагаю, что там были введены некоторые дополнительные ограничения, такие как min_width, min_height, соотношение ширины / высоты и даже положение.

Обратите внимание, что оба документа можно загрузить с его веб-страницы.

Не прочитав всю газету, мне бросается в глаза формулировка вашей цитаты

Учитывая, что базовое разрешение детектора составляет 24x24, исчерпывающий набор функций прямоугольника довольно велик, более 180000. Обратите внимание, что в отличие от базиса Хаара, набор функций прямоугольника является избыточным.

«Набор характеристик прямоугольника переполнен» «Исчерпывающий набор»

для меня это звучит как установка, когда я ожидаю, что автор статьи последует объяснением того, как они сокращают пространство поиска до более эффективного набора, например, избавляясь от тривиальных случаев, таких как прямоугольники с нулем площадь поверхности.

edit: или используя какой-то алгоритм машинного обучения, как намекает аннотация. Исчерпывающий набор подразумевает все возможности, а не только «разумные».

Нет никакой гарантии, что любой автор любой статьи прав во всех своих предположениях и выводах. Если вы думаете, что предположение №4 верно, оставьте это предположение и попробуйте свою теорию. Вы можете быть более успешными, чем первоначальные авторы.

Неплохое наблюдение, но они могут неявно обнулить кадр 24x24 или «переполнить» и начать использовать первые пиксели, когда он выходит за пределы, например, при поворотных сдвигах, или, как сказал Бретон, они могут рассматривать некоторые особенности как «тривиальные особенности» а затем отбросьте их с помощью AdaBoost.

Кроме того, я написал версии вашего кода для Python и Matlab, чтобы я мог сам протестировать код (для меня проще отлаживать и отслеживать), и поэтому я размещаю их здесь, если кто-то сочтет их полезными.

Python:

frameSize = 24;
features = 5;
# All five feature types:
feature = [[2,1], [1,2], [3,1], [1,3], [2,2]]

count = 0;
# Each feature:
for i in range(features):
    sizeX = feature[i][0]
    sizeY = feature[i][1]
    # Each position:
    for x in range(frameSize-sizeX+1):
        for y in range(frameSize-sizeY+1):
            # Each size fitting within the frameSize:
            for width in range(sizeX,frameSize-x+1,sizeX):
                for height in range(sizeY,frameSize-y+1,sizeY):
                    count=count+1
print (count)

Matlab:

frameSize = 24;
features = 5;
% All five feature types:
feature = [[2,1]; [1,2]; [3,1]; [1,3]; [2,2]];

count = 0;
% Each feature:
for ii = 1:features
    sizeX = feature(ii,1);
    sizeY = feature(ii,2);
    % Each position:
    for x = 0:frameSize-sizeX
        for y = 0:frameSize-sizeY
            % Each size fitting within the frameSize:
            for width = sizeX:sizeX:frameSize-x
                for height = sizeY:sizeY:frameSize-y
                    count=count+1;
                end
            end
        end
    end
end

display(count)

В своей оригинальной статье 2001 года они только заявляют, что используются три типа функций:

мы используем три вида функций

Также

Регионы имеют одинаковый размер и форму.

Поскольку каждый вид имеет две ориентации, разумно предположить, что они используют в общей сложности 6 функций (по крайней мере, для вычисления общего количества функций): 2 двухпрямоугольных объекта, 2 трех прямоугольных объекта и 2 четырехугольных объекта. Исходя из этого предположения, действительно существует более 180000 функций:

feature_types = [(1,2), (2,1), (1,3), (3,1), (2,2), (2,2)]
window_size = (24,24)

total_features = 0
for f_type in feature_types:
    for f_height in range(f_type[0], window_size[0] + 1, f_type[0]):
        for f_width in range(f_type[1], window_size[1] + 1, f_type[1]):
            total_features += (window_size[0] - f_height + 1) * (window_size[1] - f_width + 1)
            
print(total_features)
# 183072

Если вы отбросите один тип объектов с четырьмя прямоугольниками (что, по-видимому, имеет место в их более поздней публикации), то общее количество функций составит 162 336.