Обнаружение лица Viola-Jones требует 180 тыс. Функций

мы осуществляем адаптациюViola-Jones' алгоритм распознавания лиц, Этот метод основан на размещении подкадра 24x24 пикселей на изображении и последующем размещении прямоугольных элементов внутри него в каждой позиции с любым возможным размером.

Эти функции могут состоять из двух, трех или четырех прямоугольников. Следующий пример представлен.

Они утверждают, что исчерпывающий набор составляет более 180 КБ (раздел 2):

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

Следующие утверждения прямо не изложены в документе, поэтому они являются предположениями с моей стороны:

Есть только 2 объекта с двумя прямоугольниками, 2 объекта с тремя прямоугольниками и 1 объект с четырьмя прямоугольниками. Логика этого заключается в том, что мы наблюдаемразница между выделенными прямоугольниками, а не явно цветом или яркостью или чем-то в этом роде.Мы не можем определить тип объекта A как блок пикселей 1x1; он должен быть не менее 1х2 пикселей. Кроме того, тип D должен быть не менее 2x2 пикселей, и это правило соответствует другим функциям.Мы не можем определить тип объекта A как блок пикселей 1x3, так как средний пиксель не может быть разделен, и вычитание его из себя идентично блоку пикселей 1x2; этот тип объекта определен только для четной ширины. Кроме того, ширина типа объекта C должна делиться на 3, и это правило выполняется в соответствии с другими объектами.Мы не можем определить объект с шириной и / или высотой 0. Поэтому мы повторяем x и у до 24 минус размер функции.

Исходя из этих предположений, яМы насчитали исчерпывающий набор:

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 
 Paul Lammertsma10 нояб. 2009 г., 14:39
Точно так же, если бы я начал х в 0, он должен был бы бежать кx < size - 1так что нет выгоды.
 Niki10 нояб. 2009 г., 14:13
Почему я получаю count = 114829, когда я запускаю ваш код?
 Breton10 нояб. 2009 г., 15:49
Айеп, я могуТочно так же он не может приблизиться к 180 000. Вот'Это моя паршивая попытка.jsbin.com/imase/edit (нажмите вкладку вывода для результата, вкладку JavaScript для исходного кода)
 Paul Lammertsma10 нояб. 2009 г., 16:35
@Breton: я могу написать код для демонстрации 180k +, отбросив предположение # 4 и представив ошибки, которые мы обсуждали в коде:jsbin.com/ibahe/edit
 Paul Lammertsma10 нояб. 2009 г., 15:10
Ха-ха, молодец, теперь мывсе на одной стадии! Хороший вопрос, бретонец, размер никогда не может достигать 24, как он есть. Я'Я еще раз посмотрю.
 Niki10 нояб. 2009 г., 14:48
Что ж, если x / y начать с 0, я получу 162336. Если я отброшу предположение # 4 и позволю ширине / высоте начать с 0, я получу 212256. Интересно, как они получили 180k ...
 Breton10 нояб. 2009 г., 14:43
мы сделали миллионы для петель. это кажется мне неправильным. <размер не позволит x стать 24, начиная с 0, вы получите 0 ... 23. При ширине в 1 пиксель прямоугольник никогда не покинет рамки.
 Paul Lammertsma10 нояб. 2009 г., 14:37
Помимо того, начинается ли он с 0 или 1 и заканчивается наx < size связано с предположением № 4: я хочу, чтобы объект оставался в подкадре, но имел размер по крайней мере 1x1. Что касается того, не должен ли размер элемента выходить за пределы подкадра, возможно, это тоже предположение.
 Ron10 нояб. 2009 г., 16:54
спасибо, что подняли эту статью, яЯ никогда не слышал об этом раньше. Это'очень аккуратно.
 Niki10 нояб. 2009 г., 14:31
Почему ваши петли x / y начинаются с 1? Я предполагаю, что x / y - верхняя левая координата прямоугольника объекта. не должен»t x / y начинаются с 0/0 тогда?

Ответы на вопрос(5)

Учитывая, что базовое разрешение детектора составляет 24x24, исчерпывающий набор прямоугольных элементов довольно велик - более 180 000. Обратите внимание, что в отличие от основы Хаара, набор прямоугольных элементов является слишком полным ».

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

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

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

 Breton10 нояб. 2009 г., 14:03
Вы уверены, что ваш код нетодин на один ошибки? Я только присмотрелся, и у вас наверняка есть забавный способ написания цикла for.
 Paul Lammertsma10 нояб. 2009 г., 13:57
Я должен включить сноску после "переполненный ":"Полный базис не имеет линейной зависимости между базовыми элементами и имеет то же количество элементов, что и пространство изображения, в данном случае 576. Полный набор из 180 000 тысяч объектов во много раз переполнен ». Они явно не избавляются от классификаторов без поверхности, они используют AdaBoost, чтобы определить это "очень небольшое количество этих функций может быть объединено для формирования эффективного классификатора », Итак, элементы с нулевой поверхностью будут немедленно отброшены, но зачем их рассматривать в первую очередь?
 Paul Lammertsma10 нояб. 2009 г., 14:00
Я согласен, исчерпывающий набор предполагает все возможности. Но учтите, что если вы берете от 1 до 24 для х и ширина <= x, функция будет расширяться на 1 пиксель за пределы субкадра!
 Breton10 нояб. 2009 г., 14:35
Ну, в основном, за исключением того, что, как указано выше, вы начинаете свои координаты x / y с 1 вместо 0, что может объяснить вашу дискретность.
 Paul Lammertsma10 нояб. 2009 г., 14:25
Итак, в итоге, кажется, что Виола & Джонс считал, что их слишком полный набор прямоугольных элементов включает объекты с нулевой поверхностью. Это звучит логично для вас?
 Breton10 нояб. 2009 г., 13:59
Ну, это звучит как рассуждение кого-то действительно в теорию множеств.
 Breton10 нояб. 2009 г., 14:16
Я должен уточнить это - я просто подумал об этом немного, и если у вас есть прямоугольник, который составляет 1 пиксель в высоту, 2 пикселя в высоту, 3 пикселя в высоту, вплоть до 24 пикселей в высоту, у вас есть 24 вида прямоугольника, все который вписывается в субкадр высотой 24 пикселя. Какие свесы?
 Paul Lammertsma10 нояб. 2009 г., 14:23
Вы'правы; петли были неряшливы. Я перепутал размеры с расположением объекта. Я'Я редактировал его в ОП. Вы'Также верно о свесах: их нет. Единственный способ, которым я могу воспроизвести 180k +, это установить петли for для ширины и высоты, которые начинаются с 0.
Решение Вопроса

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

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

#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;
}
</stdio.h>

с теми же результатами, что и предыдущий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
 Paul Lammertsma10 нояб. 2009 г., 23:07
Убедительные. Настолько убедительно, что яЯ уверен, что мыверно. Я'мы отправили автору электронное письмо, чтобы узнать,Мы допустили фундаментальную ошибку в моих рассуждениях. Мы'посмотрим, есть ли у занятого парня время ответить.
 Amro17 нояб. 2009 г., 17:53
Отлично, спасибо за обновление. Для желающих я нашел ссылку на IJCV '04 статья:lear.inrialpes.fr/people/triggs/student/vj/viola-ijcv04.pdf
 Paul Lammertsma20 нояб. 2009 г., 15:56
Да, этосидеть. 160К, а не 180К.
 Amro10 нояб. 2009 г., 23:32
имейте в виду, что эта штука существует уже пару лет, и с тех пор было сделано много улучшений
 Paul Lammertsma17 нояб. 2009 г., 12:16
Первоначальный документ, в котором была заявлена 180k, взят из материалов конференции 2001 года по компьютерному зрению и распознаванию образов. Пересмотренный документ, принятый в 2003 году и опубликованный в Международном журнале компьютерного зрения в 2004 году, гласит на с. 139 (конец раздела 2): «исчерпывающий набор прямоугольников довольно большой, 160 000 ", Похоже, мы были правы!

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

 Michael Dillon10 нояб. 2009 г., 17:18
Дело в том, что все люди. Все совершают ошибки. Когда громкое имя совершает ошибки, оно часто скрывается от поколений, потому что люди боятся сомневаться в полученной мудрости. Но настоящая наука следует научному методу и не поклоняется никому, как бы ни были велики их имена. Если это наука, то простые смертные могут приложить усилия, понять, как это работает, и приспособить их к своим обстоятельствам.
 Paul Lammertsma10 нояб. 2009 г., 14:03
Эксперимент показывает, что он работает, по-видимому, точно так же. Я считаю, что AdaBoost просто удаляет эти дополнительные функции с нулевой поверхностью в первом цикле, но я неТ на самом деле смотрел на это.
 Paul Lammertsma10 нояб. 2009 г., 16:48
Определенно, и я нене сомневаюсь в их методе вообще. Это'Эффективно и работает очень хорошо! Теория обоснована, но я полагаю, что они могли ошибочно обрезать свой детектор на один пиксель короче и включать ненужные функции с нулевой поверхностью. Если нет, то я призываю вас продемонстрировать возможности 180k!
 Dima10 нояб. 2009 г., 16:29
Виола и Джонс очень громкие имена в компьютерном зрении. На самом деле, этот конкретный документ считается оригинальным. Все делают ошибки, но этот конкретный алгоритм доказал свою эффективность.
 Paul Lammertsma10 нояб. 2009 г., 17:43
Мы'я увижу; Я'Мы отправили письмо автору.

В их CVPR01 бумага, в которой четко указано, что

Более конкретно, мы используемтри виды функций. Значениедвухугольник это разница между суммой пикселей в двух прямоугольных областях. Регионы имеют одинаковый размер и форму и расположены горизонтально или вертикально рядом (см. Рисунок 1).Трехугольник вычисляет сумму в двух внешних прямоугольниках, вычтенных из суммы в центральном прямоугольнике. в заключениечетырехугольник ».

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

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

но они могут неявно заполнять кадр 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)
 Kasparov9225 мар. 2018 г., 09:37
Почему вы используете 5 функций, только 4 размещены в основном вопросе. Но все равно спасибо за версию Python.

Ваш ответ на вопрос