Wykrywanie twarzy Violi-Jones obejmuje 180 tys. Funkcji

Wdrażałem adaptację algorytmu wykrywania twarzy Violi-Jonesa . Technika ta polega na umieszczeniu w obrazie podramki o wymiarach 24x24 pikseli, a następnie umieszczeniu wewnątrz niej prostokątnych elementów w każdym położeniu o każdym możliwym rozmiarze.

Te elementy mogą składać się z dwóch, trzech lub czterech prostokątów. Przedstawiono następujący przykład.

Twierdzą, że wyczerpujący zestaw to ponad 180 tysięcy (sekcja 2):

Biorąc pod uwagę, że podstawowa rozdzielczość detektora to 24x24, wyczerpujący zestaw cech prostokąta jest dość duży, ponad 180 000. Zwróć uwagę, że w przeciwieństwie do podstawy Haar, zestaw elementów prostokąta jest zbyt kompletny.

Poniższe stwierdzenia nie są wyraźnie podane w artykule, więc są to założenia z mojej strony:

1. Istnieją tylko 2 obiekty dwuprostokątne, 2 elementy trójprostokątne i 1 element czterokątny. Logika tego polega na tym, że obserwujemy różnicę między podświetlonymi prostokątami, a nie wyraźnie kolor, luminancję czy cokolwiek w tym rodzaju.
2. Nie możemy zdefiniować elementu typu A jako bloku 1x1 piksela; musi mieć co najmniej 1 x 2 piksele. Ponadto typ D musi mieć co najmniej 2 x 2 piksele i ta zasada obowiązuje odpowiednio do innych funkcji.
3. Nie możemy zdefiniować elementu typu A jako bloku 1 x 3 piksele, ponieważ środkowy piksel nie może być podzielony na partycje, a odjęcie go od siebie jest identyczne jak w bloku 1 x 2 piksele; ten typ elementu jest definiowany tylko dla parzystych szerokości. Ponadto szerokość cechy typu C musi być podzielna przez 3 i ta zasada obowiązuje odpowiednio do innych cech.
4. Nie możemy zdefiniować funkcję o szerokości i / lub wysokości 0. Dlatego iterate x i y do 24 minus wielkość funkcji.

Na podstawie tych założeń policzyłem wyczerpujący zestaw:

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

Wynik to 162.336 .

Jedynym sposobem, w jaki znalazłem przybliżenie „ponad 180 000”, o których mówią Viola i Jones, jest porzucenie założenia nr 4 i wprowadzenie błędów w kodzie. Wymaga to odpowiednio zmiany czterech wierszy na:

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

Wynik to 180 625 . (Zwróć uwagę, że skutecznie zapobiegnie to kiedykolwiek dotykaniu elementów prawej i / lub dolnej części ramy pomocniczej).

Teraz oczywiście pytanie: czy popełnili błąd w swojej implementacji? Czy rozważenie cech o powierzchni zerowej ma sens? A może źle to widzę?

Po bliższym przyjrzeniu się, twój kod wydaje mi się poprawny; co sprawia, że ​​można się zastanawiać, czy pierwotni autorzy mieli osobny błąd. Chyba ktoś powinien przyjrzeć się, jak implementuje to OpenCV!

Niemniej jednak jedną z sugestii, aby ułatwić zrozumienie, jest odwrócenie kolejności pętli for , przechodząc najpierw przez wszystkie rozmiary, a następnie przechodząc przez możliwe lokalizacje dla danego rozmiaru:

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

z takimi samymi wynikami, jak poprzedni 162336

Aby to zweryfikować, przetestowałem przypadek okna 4x4 i ręcznie sprawdziłem wszystkie przypadki (łatwe do policzenia, ponieważ kształty 1x2 / 2x1 i 1x3 / 3x1 są takie same tylko obrócone o 90 stopni):

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

wszystko. W dokumentach Violi i Jonesa wciąż jest pewne zamieszanie.

W ich artykule CVPR'01 jest to wyraźnie stwierdzone

„Mówiąc dokładniej, używamy trzech rodzajów funkcji. Wartość funkcji dwóch prostokątów jest różnicą między sumą pikseli w dwóch prostokątnych obszarach. Regiony mają ten sam rozmiar i kształt oraz sąsiadują ze sobą poziomo lub pionowo (patrz rysunek 1). Cecha trzech prostokątów oblicza sumę w dwóch zewnętrznych prostokątach, odejmowaną od sumy w prostokącie środkowym. Wreszcie cecha czterokątna ”.

W artykule IJCV'04 jest powiedziane dokładnie to samo. W sumie 4 funkcje . Ale co dziwne, tym razem stwierdzili, że wyczerpujący zestaw funkcji to 45396! Wydaje się, że nie jest to ostateczna wersja, ale tutaj chyba wprowadzono tam dodatkowe ograniczenia, takie jak min_width, min_height, szerokość / wysokość, a nawet położenie.

Zauważ, że oba artykuły można pobrać z jego strony internetowej .

Ponieważ nie przeczytałem całego artykułu, sformułowanie twojego cytatu mnie zaskakuje

Biorąc pod uwagę, że podstawowa rozdzielczość detektora to 24x24, wyczerpujący zestaw cech prostokąta jest dość duży, ponad 180 000. Zwróć uwagę, że w przeciwieństwie do podstawy Haar, zestaw elementów prostokąta jest zbyt kompletny.

„Zestaw funkcji prostokąta jest zbyt kompletny” „Wyczerpujący zestaw”

brzmi to dla mnie jak konfiguracja, w której oczekuję, że autor artykułu wyjaśni, w jaki sposób zmniejszają przestrzeń wyszukiwania do bardziej efektywnego zestawu, na przykład pozbywając się trywialnych przypadków, takich jak prostokąty z zerem powierzchnia.

edytuj: lub używając jakiegoś algorytmu uczenia maszynowego, jak sugeruje streszczenie. Wyczerpujący zestaw implikuje wszystkie możliwości, nie tylko te „rozsądne”.

Nie ma gwarancji, że którykolwiek autor jakiegokolwiek artykułu jest poprawny we wszystkich swoich założeniach i ustaleniach. Jeśli uważasz, że założenie nr 4 jest słuszne, zachowaj to założenie i wypróbuj swoją teorię. Możesz odnieść większy sukces niż pierwotni autorzy.

Całkiem dobra obserwacja, ale mogą domyślnie zerować ramkę 24x24 lub "przepełnić" i zacząć używać pierwszych pikseli, gdy wyjdzie poza granice, jak w przypadku przesunięć obrotowych, lub jak powiedział Breton, mogą uznać niektóre funkcje za "trywialne" a następnie odrzuć je za pomocą AdaBoost.

Ponadto napisałem wersje Twojego kodu w Pythonie i Matlabie, dzięki czemu mogę sam przetestować kod (łatwiejszy do debugowania i śledzenia), więc zamieszczam je tutaj, jeśli ktoś uzna je kiedyś za przydatne.

Pyton:

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)

W swoim oryginalnym artykule z 2001 roku stwierdzili tylko, że używane są trzy rodzaje funkcji:

używamy trzech rodzajów funkcji

Również

Regiony mają ten sam rozmiar i kształt

Ponieważ każdy rodzaj ma dwie orientacje, rozsądnie jest założyć, że używają łącznie 6 cech (przynajmniej do obliczenia całkowitej liczby cech): 2 elementy dwuprostokątne, 2 obiekty trójprostokątne i 2 obiekty czterokątne. Przy takim założeniu rzeczywiście istnieje ponad 180 000 funkcji:

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

Jeśli upuścisz jeden typ funkcji z czterema prostokątami (co wydaje się mieć miejsce w ich późniejszej publikacji), to całkowita liczba obiektów wyniesie 162336.