Wykrywanie twarzy Violi-Jones obejmuje 180 tys. Funkcji

84

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.

Funkcje prostokątne

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ę?

Paul Lammertsma
źródło
Dlaczego otrzymuję count = 114829, kiedy uruchomię Twój kod?
Niki
Dlaczego twoje pętle X / Y zaczynają się od 1? Zakładam, że x / y jest lewą górną współrzędną prostokąta funkcji. Czy zatem x / y nie powinno zaczynać się od 0/0?
Niki
Oprócz tego, czy zaczyna się od 0, czy 1, koniec na x < sizema związek z założeniem nr 4: chcę, aby funkcja pozostała w ramie pomocniczej, ale miała wymiar co najmniej 1x1. A jeśli chodzi o to, czy wymiar elementu nie powinien wystawać poza ramę pomocniczą, cóż, być może to też jest założenie.
Paul Lammertsma
Podobnie, gdybym zaczął x od 0, musiałby biec do x < size - 1, więc nie ma zysku.
Paul Lammertsma
Zrobiłem milion dla pętli. wydaje mi się to niewłaściwe. <rozmiar uniemożliwiłby przekształcenie x w 24, zaczynając od 0, daje 0 ... 23, Przy wymiarze 1 piksela, prostokąt nigdy nie opuści ramki.
Breton

Odpowiedzi:

40

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
Amro
źródło
Przekonywający. Tak przekonujące, że jestem całkiem pewien, że mamy rację. Wysłałem e-mail do autora, aby sprawdzić, czy popełniłem jakiś fundamentalny błąd w swoim rozumowaniu. Zobaczymy, czy facet, który jest zajęty, zdąży odpowiedzieć.
Paul Lammertsma
pamiętajcie, że ta rzecz jest niedostępna od kilku lat i od tego czasu wprowadzono wiele ulepszeń
Amro
25
Oryginalny artykuł, w którym podano 180 tys., Pochodzi z materiałów z konferencji na temat widzenia komputerowego i rozpoznawania wzorców w 2001 roku. Zmieniony artykuł, przyjęty w 2003 roku i opublikowany w International Journal of Computer Vision w 2004 roku, stwierdza na str. 139 (koniec części 2): „wyczerpujący zbiór prostokątów jest dość duży, 160 000”. Wygląda na to, że mieliśmy rację!
Paul Lammertsma
3
Świetnie, dzięki za aktualizację. Dla zainteresowanych znalazłem link do artykułu IJCV'04
Amro
Tak, to jest to. 160 tys., A nie 180 tys.
Paul Lammertsma
9

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 .

Laoma z Singapuru
źródło
3

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”.

Breton
źródło
Powinienem dodać przypis po „overcomplete”: „Kompletna baza nie ma liniowej zależności między elementami bazowymi i ma taką samą liczbę elementów jak przestrzeń obrazu, w tym przypadku 576. Pełny zestaw 180 000 tysięcy cech jest wielokrotnie przekroczony kompletny." Nie pozbywają się jawnie klasyfikatorów bez powierzchni, używają AdaBoost do ustalenia, że ​​„bardzo mała liczba tych cech może być połączona w celu stworzenia efektywnego klasyfikatora”. Ok, więc cechy powierzchni zerowej zostaną natychmiast usunięte, ale po co je w pierwszej kolejności rozważać?
Paul Lammertsma
Cóż, brzmi to jak rozumowanie kogoś naprawdę w teorii mnogości.
Breton,
Zgadzam się, wyczerpujący zestaw oznaczałby wszystkie możliwości. Ale weź pod uwagę, że jeśli weźmiesz od 1 do 24 dla xi szerokość <= x, funkcja wydłuży 1 piksel poza ramkę pomocniczą!
Paul Lammertsma
Czy na pewno w Twoim kodzie nie ma błędów typu „off by one”? Właśnie przyjrzałem się bliżej i na pewno masz zabawny sposób pisania pętli for.
Breton
Powinienem to zakwalifikować - po prostu przemyślałem to trochę, a jeśli masz prostokąt o wysokości 1 piksela, wysokości 2 pikseli, wysokości 3 pikseli, aż do wysokości 24 pikseli, masz 24 rodzaje prostokątów, wszystkie które mieszczą się w ramce pomocniczej o wysokości 24 pikseli. Jakie nawisy?
Breton
2

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.

Michael Dillon
źródło
Eksperymenty pokazują, że działa on z pozoru dokładnie tak samo. Uważam, że AdaBoost po prostu usuwa te dodatkowe funkcje zerowej powierzchni w pierwszym cyklu, ale tak naprawdę nie zaglądałem do tego.
Paul Lammertsma
Viola i Jones to wielkie nazwiska w dziedzinie widzenia komputerowego. W rzeczywistości ten konkretny artykuł jest uważany za przełomowy. Każdy popełnia błędy, ale udowodniono, że ten konkretny algorytm działa bardzo dobrze.
Dima
1
Zdecydowanie i wcale nie wątpię w ich metodę. Jest wydajny i działa bardzo dobrze! Teoria jest słuszna, ale wydaje mi się, że mogli omyłkowo przyciąć swój detektor o jeden piksel i uwzględnić niepotrzebne elementy o zerowej powierzchni. Jeśli nie, wzywam Cię do zademonstrowania 180 000 funkcji!
Paul Lammertsma
Faktem jest, że każdy jest człowiekiem. Wszyscy popełniają błędy. Kiedy wielkie nazwisko popełnia błędy, często pozostają one ukryte przez pokolenia, ponieważ ludzie boją się kwestionować otrzymaną mądrość. Ale prawdziwa nauka postępuje zgodnie z metodą naukową i nie oddaje czci nikomu, bez względu na to, jak wielkie jest jego imię. Jeśli jest to nauka, zwykli śmiertelnicy mogą włożyć wysiłek, zrozumieć, jak to działa i dostosować to do swoich okoliczności.
Michael Dillon
Zobaczymy; Wysłałem e-mail do autora.
Paul Lammertsma
1

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)
Бојан Матовски
źródło
Dlaczego używasz 5 funkcji, tylko 4 są zamieszczone w głównym pytaniu. Ale i tak dziękuję za wersję Pythona.
Kasparow92
0

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.

Andreas K.
źródło