Struktura wykrywania obiektów Viola–Jones - Viola–Jones object detection framework

Struktura wykrywania obiektów Viola-Jones jest strukturą wykrywania obiektów , która została zaproponowana w 2001 roku przez Paula Violę i Michaela Jonesa . Choć można go wyszkolić w wykrywaniu różnych klas obiektów, motywował go przede wszystkim problem wykrywania twarzy .

Opis problemu

Problemem do rozwiązania jest wykrywanie twarzy na obrazie. Człowiek może to zrobić z łatwością, ale komputer potrzebuje precyzyjnych instrukcji i ograniczeń. Aby zadanie było łatwiejsze do wykonania, Viola-Jones wymaga pełnego widoku przednich pionowych twarzy. Dlatego, aby zostać wykrytym, cała twarz musi być skierowana w stronę kamery i nie może być przechylona na żadną stronę. Chociaż wydaje się, że te ograniczenia mogą nieco zmniejszyć użyteczność algorytmu, ponieważ po etapie wykrywania najczęściej następuje etap rozpoznawania, w praktyce te ograniczenia dotyczące pozy są całkiem do przyjęcia.

Składniki ram

Przykładowe cechy prostokąta pokazane w odniesieniu do otaczającego okna wykrywania

Rodzaje funkcji i ocena

Cechy algorytmu Viola-Jonesa, które czynią go dobrym algorytmem wykrywania to:

• Odporny – bardzo wysoki współczynnik wykrywalności (wskaźnik wyników prawdziwie dodatnich) i zawsze bardzo niski współczynnik wyników fałszywie dodatnich.
• W czasie rzeczywistym — do zastosowań praktycznych należy przetwarzać co najmniej 2 klatki na sekundę.
• Tylko wykrywanie twarzy (nie rozpoznawanie) — celem jest odróżnienie twarzy od osób niebędących twarzami (wykrywanie jest pierwszym krokiem w procesie rozpoznawania).

Algorytm składa się z czterech etapów:

1. Wybór funkcji haar
2. Tworzenie integralnego obrazu
3. Szkolenie Adaboost
4. Klasyfikatory kaskadowe

Cechy poszukiwane przez ramę wykrywania powszechnie obejmują sumy pikseli obrazu w prostokątnych obszarach. Jako takie wykazują pewne podobieństwo do podstawowych funkcji Haara , które były wcześniej używane w dziedzinie wykrywania obiektów na podstawie obrazu. Ponieważ jednak wszystkie funkcje używane przez Violę i Jonesa opierają się na więcej niż jednym prostokątnym obszarze, są one na ogół bardziej złożone. Rysunek po prawej ilustruje cztery różne typy funkcji używanych w ramach. Wartość dowolnej funkcji to suma pikseli w wyraźnych prostokątach odjęta od sumy pikseli w zacienionych prostokątach. Prostokątne cechy tego rodzaju są prymitywne w porównaniu z alternatywami, takimi jak sterowalne filtry . Chociaż są wrażliwe na cechy pionowe i poziome, ich sprzężenie zwrotne jest znacznie bardziej zgrubne.

Na twarz nakładana jest cecha haar, która wygląda podobnie do grzbietu nosa

Haar Cecha, która wygląda podobnie do okolicy oczu, która jest ciemniejsza niż górne policzki, jest nakładana na twarz

3. i 4. rodzaj cechy Haar

Funkcje haara

Wszystkie ludzkie twarze mają podobne właściwości. Te prawidłowości można dopasować za pomocą funkcji Haar .

Kilka właściwości wspólnych dla ludzkich twarzy:

• Okolice oczu są ciemniejsze niż górne policzki.
• Obszar mostka nosa jest jaśniejszy niż oczy.

Kompozycja właściwości tworzących dopasowane rysy twarzy:

• Lokalizacja i rozmiar: oczy, usta, grzbiet nosa
• Wartość: zorientowane gradienty intensywności pikseli

Cztery cechy dopasowane przez ten algorytm są następnie wyszukiwane na obrazie twarzy (pokazanym po prawej stronie).

Cechy prostokąta:

• Wartość = Σ (piksele w obszarze czarnym) - Σ (piksele w obszarze białym)
• Trzy typy: dwu-, trzy-, cztero-prostokątne, Viola & Jones wykorzystywały cechy dwóch prostokątów
• Na przykład: różnica jasności między białymi i czarnymi prostokątami na określonym obszarze
• Każda funkcja jest powiązana ze specjalną lokalizacją w podoknie

Zsumowana tabela powierzchni

Reprezentacja obrazu zwana obrazem integralnym ocenia prostokątne cechy w stałym czasie, co daje im znaczną przewagę szybkości nad bardziej wyrafinowanymi alternatywnymi cechami. Ponieważ prostokątny obszar każdego elementu zawsze przylega do co najmniej jednego innego prostokąta, wynika z tego, że dowolny element z dwoma prostokątami można obliczyć w sześciu odwołaniach do tablicy, dowolny element z trzema prostokątami w ośmiu, a dowolny element z czterema prostokątami w dziewięciu.

Algorytm uczenia

Szybkość, z jaką można oceniać cechy, nie kompensuje jednak w wystarczającym stopniu ich liczby. Na przykład w standardowym podokienku 24x24 piksele jest łącznie M = 162,336 możliwych funkcji i ocena ich wszystkich podczas testowania obrazu byłaby zbyt kosztowna. W związku z tym struktura wykrywania obiektów wykorzystuje wariant algorytmu uczenia AdaBoost zarówno do wybierania najlepszych funkcji, jak i do trenowania klasyfikatorów, które z nich korzystają. Algorytm ten konstruuje „silny” klasyfikator jako liniową kombinację ważonych prostych „słabych” klasyfikatorów.

${\ Displaystyle h (\ mathbf {x} ) = \ operatorname {sgn} \ lewo (\ suma _ {j = 1} ^ {M} \ alfa _ {j} h_ {j} (\ mathbf {x}) \ dobrze)}$

Każdy słaby klasyfikator jest funkcją progową opartą na właściwości . ${\displaystyle f_{j}}$

${\ Displaystyle h_ {j} (\ mathbf {x} ) = {\ zacząć {przypadki}-s_ {j} i {\ tekst {jeśli}} f_ {j} <\ theta _ {j} \ \ s_ {j }&{\text{otherwise}}\end{cases}}}$

W treningu określana jest wartość progowa i polaryzacja , a także współczynniki . ${\ Displaystyle \ theta _ {j}}$${\ Displaystyle s_ {j} \ w \ pm 1}$${\ Displaystyle \ alfa _ {j}}$

Tutaj podana jest uproszczona wersja algorytmu uczenia:

Dane wejściowe: Zestaw N pozytywnych i negatywnych obrazów treningowych wraz z ich etykietami . Jeśli obraz i jest twarzą , jeśli nie . ${\ Displaystyle {(\ mathbf {x} ^ {i}, Y ^ {i})}}$${\ Displaystyle y ^ {i} = 1}$${\ Displaystyle y ^ {i} = -1}$

1. Inicjalizacja: przypisz wagę do każdego obrazu i .${\ Displaystyle w_ {1} ^ {i} = {\ Frac {1} {N}}}$
2. Dla każdej funkcji z${\displaystyle f_{j}}$${\displaystyle j=1,...,M}$
   1. Znormalizuj wagi tak, aby sumowały się do jednego.
   2. Zastosuj tę funkcję do każdego obrazu w zestawie uczącym, a następnie znajdź optymalny próg i polaryzację, które minimalizują ważony błąd klasyfikacji. To jest gdzie${\ Displaystyle \ theta _ {j}, s_ {j}}$${\ Displaystyle \ theta _ {j}, s_ {j} = \ arg \ min _ {\ theta, s} \; \ suma _ {i = 1} ^ {N} w_ {j} ^ {i} \ varepsilon _{j}^{i}}$${\ Displaystyle \ varepsilon _ {j} ^ {i} = {\ zacząć {przypadki} 0 i {\ tekst {jeśli}} y ^ {i} = h_ {j} (\ mathbf {x} ^ {i} \ theta _{j},s_{j})\\1&{\text{otherwise}}\end{cases}}}$
   3. Przypisz do tego wagę, która jest odwrotnie proporcjonalna do poziomu błędu. W ten sposób najlepsze klasyfikatory są uważane za więcej.${\ Displaystyle \ alfa _ {j}}$${\displaystyle h_{j}}$
   4. Wagi dla następnej iteracji, tj. , są zmniejszane dla obrazów i, które zostały prawidłowo sklasyfikowane.${\ Displaystyle w_ {j+1} ^ {i}}$
3. Ustaw końcowy klasyfikator na ${\ Displaystyle h (\ mathbf {x} ) = \ operatorname {sgn} \ lewo (\ suma _ {j = 1} ^ {M} \ alfa _ {j} h_ {j} (\ mathbf {x}) \ dobrze)}$

Architektura kaskadowa

• Średnio tylko 0,01% wszystkich podokien jest pozytywnych (twarze)
• Na wszystkich oknach podrzędnych spędza się jednakowy czas obliczeniowy
• Musi spędzać większość czasu tylko na potencjalnie pozytywnych podoknach.
• Prosty dwufunkcyjny klasyfikator może osiągnąć prawie 100% wskaźnik wykrywalności przy 50% wskaźniku FP.
• Ten klasyfikator może działać jako pierwsza warstwa serii, aby odfiltrować większość negatywnych okien
• Druga warstwa z 10 funkcjami może poradzić sobie z „twardszymi” oknami negatywowymi, które przetrwały pierwszą warstwę i tak dalej...
• Kaskada stopniowo coraz bardziej złożonych klasyfikatorów zapewnia jeszcze lepsze wskaźniki wykrywalności. Ocena silnych klasyfikatorów generowanych przez proces uczenia się może być wykonana szybko, ale nie jest wystarczająco szybka, aby działać w czasie rzeczywistym. Z tego powodu silne klasyfikatory są ułożone kaskadowo w kolejności złożoności, gdzie każdy kolejny klasyfikator jest szkolony tylko na tych wybranych próbkach, które przechodzą przez poprzednie klasyfikatory. Jeśli na dowolnym etapie kaskady klasyfikator odrzuci sprawdzane podokno, dalsze przetwarzanie nie jest wykonywane i kontynuuje przeszukiwanie następnego podokna. Kaskada ma więc postać zdegenerowanego drzewa. W przypadku twarzy pierwszy klasyfikator w kaskadzie – zwany operatorem uwagi – wykorzystuje tylko dwie cechy, aby uzyskać współczynnik fałszywie negatywnych wyników wynoszący około 0% i współczynnik fałszywie pozytywnych wynoszący 40%. Efektem tego pojedynczego klasyfikatora jest zmniejszenie o około połowę liczby oceniania całej kaskady.

W kaskadowaniu każdy etap składa się z silnego klasyfikatora. Tak więc wszystkie funkcje są pogrupowane w kilka etapów, w których każdy etap ma określoną liczbę funkcji.

Zadaniem każdego etapu jest ustalenie, czy dane podokno na pewno nie jest twarzą, czy może być twarzą. Dane okno podrzędne jest natychmiast odrzucane jako nie twarz, jeśli nie powiedzie się w którymkolwiek z etapów.

Poniżej przedstawiono proste ramy szkolenia kaskadowego:

• f = maksymalny akceptowalny odsetek wyników fałszywie dodatnich na warstwę.
• d = minimalny akceptowalny współczynnik wykrywania na warstwę.
• Ftarget = docelowy ogólny odsetek wyników fałszywie pozytywnych.
• P = zbiór pozytywnych przykładów.
• N = zbiór negatywnych przykładów.

F(0) = 1.0; D(0) = 1.0; i = 0

while F(i) > Ftarget
    increase i
    n(i) = 0; F(i)= F(i-1)

    while F(i) > f × F(i-1)
        increase n(i)
        use P and N to train a classifier with n(i) features using AdaBoost
        Evaluate current cascaded classifier on validation set to determine F(i) and D(i)
        decrease threshold for the ith classifier (i.e. how many weak classifiers need to accept for strong classifier to accept)
            until the current cascaded classifier has a detection rate of at least d × D(i-1) (this also affects F(i))
    N = ∅
    if F(i) > Ftarget then 
        evaluate the current cascaded detector on the set of non-face images 
        and put any false detections into the set N.

Architektura kaskadowa ma interesujące implikacje dla wydajności poszczególnych klasyfikatorów. Ponieważ aktywacja każdego klasyfikatora zależy wyłącznie od zachowania jego poprzednika, współczynnik fałszywie dodatnich wyników dla całej kaskady wynosi:

${\ Displaystyle F = \ prod _ {i = 1} ^ {K} f_ {i}}.$

Podobnie wskaźnik wykrywalności to:

${\ Displaystyle D = \ prod _ {i = 1} ^ {K} d_ {i}}.$

Tak więc, aby dopasować wskaźniki fałszywie dodatnich zwykle osiągane przez inne detektory, każdy klasyfikator może ujść na sucho z zaskakująco niską wydajnością. Na przykład, w kaskadzie 32 stopnia w celu uzyskania wyników fałszywie dodatnich wynosi 10 ^{- 6} , każdy separator musi osiągnąć tylko wyników fałszywie dodatnich wynosi około 65%. Jednocześnie jednak każdy klasyfikator musi być wyjątkowo zdolny, jeśli ma osiągnąć odpowiednie wskaźniki wykrywalności. Na przykład, aby osiągnąć wskaźnik wykrywalności około 90%, każdy klasyfikator we wspomnianej kaskadzie musi osiągnąć wskaźnik wykrywalności około 99,7%.

Używanie Violi–Jonesa do śledzenia obiektów

W filmach przedstawiających poruszające się obiekty nie trzeba stosować wykrywania obiektów do każdej klatki. Zamiast tego można użyć algorytmów śledzenia, takich jak algorytm KLT, do wykrywania istotnych cech w obrębie ramek ograniczających wykrywanie i śledzenia ich ruchu między ramkami. Nie tylko poprawia to szybkość śledzenia, eliminując potrzebę ponownego wykrywania obiektów w każdej klatce, ale także poprawia odporność, ponieważ najistotniejsze funkcje są bardziej odporne niż struktura wykrywania Viola-Jones na zmiany rotacji i fotometrii.

Bibliografia

Linki zewnętrzne

• Slajdy przedstawiające ramy
• Informacje dotyczące funkcji podstawy Haar
• Rozszerzenie frameworka Viola–Jones o funkcję SURF
• IMMI - Rapidminer Image Mining Extension - narzędzie open-source do eksploracji obrazów
• Niezawodne wykrywanie twarzy w czasie rzeczywistym
• Ulepszony algorytm wykrywacza obiektów Viola-Jones
• Cytaty algorytmu Viola-Jonesa w Google Scholar
• Wykład wideo na YouTube na temat algorytmu Violi–Jonesa - Adaboost Wyjaśnienie z ppt autorstwa Qing Chen, Discovery Labs, University of Ottawa oraz wykład wideo Ramsriego Gouthama.

Realizacje

• Implementacja algorytmu wykrywania twarzy Viola–Jones autorstwa Ole Helviga Jensena
• MATLAB: [1] , [2]
• OpenCV: zaimplementowany jako cvHaarDetectObjects().
  • Wykrywanie kaskady haar w OpenCV
  • Szkolenie klasyfikatorów kaskadowych w OpenCV