PCA, Eigenfaces i rozpoznawanie twarzy

Czym jest PCA?

PCA czyli Principal Component Analysis czyli analiza głównych składowych jest jedną z metod statystycznych służących do analizy zbioru danych. Jeśli kogoś interesuje dokładniejsze omówienie tematu - polecam poszperać choćby po sieci (Wikipedia dla leniwych). Na potrzeby zaś tego wpisu i naszych rozważań uświadomimy sobie jedynie, że PCA umożliwia określenie w jakim stopniu dany klasyfikator jest zgodny z badanym obiektem. Innymi słowy -  jak daleko wartości elementu wzorowego do wartości badanego obiektu.

Czym jest rozpoznawanie twarzy?

Niby oczywistość, ale lepiej ją uściślić teraz, niż potem gubić się w zeznaniach. Z grubsza chodzi o to aby mając zbiór zdjęć z zidentyfikowanymi osobami móc określić czy nowe zdjęcie należy do jakiejś osoby z naszego zbioru (a jeśli tak, to której), czy też jest ono fotografią kogoś zupełnie nowego.

Etapy działania

1. Przygotować zbiór uczący składający się z obrazów o tych samych wymiarach/rozdzielczości (szerokość i wysokość), w których oczy i usta osób znajdują się na podobnej wysokości.
2.  Poddać obrazy operacji wyrównywania histogramów (histogram equalization) w celu redukcji wpływu różnicy oświetlenia.
3. Obliczyć wartości pikseli dla średniego obrazu i odjąć ten obraz od każdego obrazu ze zbioru uczącego.
4. Utworzyć macierz zawierającą wszystkie obrazy (każdy obraz to jeden wektor).
5. Obliczyć wektory własne powyższej macierzy.
6. Obliczyć PCA na podstawie wektorów własnych (jeśli decydujemy się na pominięcie niektórych wektorów to należy odrzucić te z najmniejszymi wartościami własnymi).
7. Wykonać projekcję z wykorzystaniem PCA dla każdego obrazu ze zbioru uczącego.
8. Projekcje nowych zdjęć porównywać z projekcjami obiektów już rozpoznanych i wyszukiwać wyników najbliższych.

Accord.NET

Czym jest Accord.NET? Z grubsza jest to framework oferujący bogactwo funkcji matematycznych i statystycznych, w tym m.in. rozkład na wektory własne, analizę PCA, LDA oraz wykrywanie twarzy (które działa trochę topornie, ale działa). Dlaczego wybrałem ten framework do realizacji tego zadania? Cóż popularną alternatywą byłoby użycie biblioteki OpenCV, która dość szeroko jest do tego celu (rozpoznawania twarzy) rekomendowana. Niestety cud ten technologii nie doczekał się sensownego wsparcia pod C# (wrappery działają różnie i generalnie w mojej opinii nie nadają się do użycia w produktach komercyjnych ze względu na moc różnych drobnych i nie tylko problemów z ich działaniem). Natomiast z racji tego, że Accord.NET jest bezproblemowy w użyciu (i ma wiele przykładów i opisów działania różnych zaimplementowanych funkcji) to praca z nim okazała się bardzo przyjemna.

Dithering i C# (PGM)

Niecały rok temu opublikowałem wpis o ditheringu, w którym w zasadzie nic prócz pokazania efektów tego cudu "nowoczesnej" technologii nie pokazałem. Dziś zamierzam to naprawić poprzez:

• udostępnienie biblioteki, wykonującej obsługującej proces ditheringu (póki co na plikach PGM) przy użyciu metod:
• Random
• Threshold
• Ordered
• Floyd-Steinberg
• "fałszywy" Floyd-Steinberg (czasem opisywany jako Floyd-Steinberg - stąd "fałszywy")
• Jarvis-Judice-Ninke
• Stucki
• Burkes
• Sierra
• zgrubny opis owych metod wraz z przykładowymi efektami ich działania
• W najbliższym zaś czasie dorzucę kilka własnych metod będących mniej lub bardziej efektem mych eksperymentów :)

Biblioteka

Obsługa ditheringu została dodana jako statyczna klasa (Transform.Dither) biblioteki Runaurufu.Drawing (do pobrania z chomika) i w obecnym kształcie zawiera metody:

public static class Dither
{
    public static PgmImage Threshold(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Random(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered(PgmImage img, UInt16[] box, UInt16 newMaxColor){...}
    public static PgmImage Ordered2(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered3(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered4(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered8(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered16(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage FloydSteinberg(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage FalseFloydSteinberg(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage JarvisJudiceNinke(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Stucki(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Burkes(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Sierra3(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Sierra2(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Sierra24A(PgmImage img, UInt16 newMaxColor){...}
}

Metody Ordered2 - Ordered16 wywołują metodę Ordered z wykorzystaniem predefiniowanych tablic kwadratowych o boku równym numerowi znajdującemu się przy nazwie metody (Ordered2 - tablica 2x2).

Metody Threshold i Ordered wykorzystują zrównoleglenie (Parallel.For) - niestety metody z propagacją błędu nie są w stanie z daru wielowątkowości skorzystać.

Opis metod

Oryginalny obraz

Oryginalny obraz w odcieniach szarości

Nie będę się tu zagłębiał w to po co powstał dithering, ani czym jest - bo na pierwsze pytanie można napisać rozprawę naukową i dość dobry ogląd sytuacji przedstawia nam choćby Wikipedia, a na pytanie czym jest odpowiedź znaleźć można w poniższym opisie wybranych metod. Dodatkowo dla porównania załączyłem obrazy będące wynikiem działania każdego z algorytmów na obrazie przykładowym złożonym z 4 elementów (w tle gra Civilization V, a z przodu przykładowe pingwiny z Windowsa oraz popularne obrazy - Lena i rzeźba Dawida dłuta Michała Anioła):

Threshold

Threshold dithering

Jedna z prostszych metod ograniczania ilości kolorów obrazu. Polega na rzutowaniu wartości mniejszych od pewnego wybranego progu (ang. threshold - próg, wartość progowa) na jedną zadaną wartość, a wartości większych lub równych na wartość inną (np. 0 i 255). Zazwyczaj wartość progu określa się jako medianę dostępnych wartości (128 = 256/2). Metoda ta ma tą zaletę, że jest szybka i bardzo łatwa do zrównoleglenia. Niestety wiele do życzenia pozostawia efekt końcowy w przypadku zdjęć o zróżnicowanej kolorystyce.

Random

Random dithering

Kolejna prosta metoda, która tym razem wykorzystuje losowo generowaną wartość progową (losowe wartości mogą znajdować się w takim samym zakresie jak wartości dla poszczególnych pikseli). Dla każdego piksela próg jest generowany osobno, co redukuje możliwość powstawania różnego rodzaju powtarzających się wzorów, jednak z tego samego powodu nie ma praktycznej możliwości dwukrotnego wygenerowania takich samych obrazów bez zapisania również wszystkich użytych progów.

Ordered

Ordered dithering ze wzorem 16x16

Metoda uporządkowanego ditheringu jest jedną z metod związanych z używaniem pewnych wzorów, które "nakłada się" na obraz poddawany obróbce. W tym przypadku wartości progowe pochodzą właśnie z owego wzoru, który powtarza się tak horyzontalnie jak i wertykalnie - stąd też biorą się podobnie rozlokowane artefakty. Zaletą algorytmu jest łatwość zrównoleglenia, która w połączeniu z całkiem dobrymi rezultatami wizualnymi tej metody okazuje się idealnym rozwiązaniem w przypadku wielordzeniowych systemów.

Floyd-Steinberg

Floyd-Steinberg

Z metod związanych z propagacją błędu omówię jedynie metodę Floyda-Steinberga. Dlaczego? A z tej prostej przyczyny, że pozostałe (a mówiąc wprost - pochodne) różnią się wyłącznie pozycjami i wartościami ułamku błędu.
Metoda ta opiera się na wykryciu błędu między wartością piksela (konkretnych kolorów w pikselu) oryginalnego obrazu, a wartością w obrazie przetworzonym.

Opis propagacji błędu
w metodzie Floyda-Steinberga
gwiazdką (*) oznaczono
aktualnie przetwarzany piksel

Owa różnica - błąd kwantyzacji - jest następnie rozdzielana wg zdefiniowanej tablicy (zaprezentowanej obok) na sąsiednie nieprzetworzone piksele. Wadą tej metody jest kompletna niezdolność do zrównoleglenia - algorytm musi przejść piksel po pikselu - która jednak jest niejako zacierana przez niesamowite efekty uzyskiwane dzięki tej metodzie. Za konceptem propagacji błędu stoi proste spostrzeżenie - zarówno wartość 0 jak i 120 zostaną zrzutowane na 0, co sprawia, że obraz z szarego staje się czarny. Jeśli jednak mamy 3 kolejne piksele o wartości 120, to wynikiem pracy tego algorytmu nie będzie ciąg {0,0,0}, ale ciąg {0, 255 (120 + 52.5), 0 (120 - 82.5)}, który o wiele lepiej prezentuje szarość.

Stucki dithering

Pochodne metody różnią się jedynie wartościami, liczbą i pozycją ułamków błędu kwantyzacji.

Bibliografia

Czyli co warto przeglądnąć w poszukiwaniu informacji o ditheringu...

• Wikipedia - czyli dobry wstęp do rozpoczęcia przygody z tą tematyką
• Praca Lee Daniela Crockera (rozszerzona przez Paula Boulaya oraz Mike Morra) - opisuje dobrze zarówno historię całej idei ditheringu jak i wyżej omawiane algorytmy. (mirror)
• Joel Yliluoma's arbitrary-palette positional dithering algorithm - strona z przykładami i kodami źródłowymi w PHP. Przydatna do porównania różnych algorytmów - również przy zastosowaniu w filmie.
• Image Based Artistic Dithering - praca  studentów z PUC w Rio, może nie odkrywcza, ale jeśli ktoś zaczyna przygodę z tą tematyką to może się przydać (choć jak ktoś faktycznie chce ugryźć temat to o wiele lepiej zacząć od pracy Lee Daniela Crockera)

Obsługa formatu Netpbm przez C#

 Wstęp teoretyczny

Format Netpbm odnosi się tak na prawdę do zestawu formatów plikowych służących do przechowywania obrazów. W skład tego pakietu wchodzą trzy podstawowe formaty:

• PBM - Portable Bit Map
• PGM - Portable Gray Map
• PPM - Portable Pixel Map

 Do tego czasem dorzuca się PAM (Portable Arbitrary Map), którego struktura opiera się na zasadach wręcz identycznych do tych odnoszących się do PBM/PGM/PPM (które od teraz zbiorczo będę określał jako PNM - Portable Any Map).
Jeśli kogoś interesuje więcej na temat tego formatu to zapraszam do czytania:

• http://netpbm.sourceforge.net/doc/
• http://en.wikipedia.org/wiki/Netpbm
• http://en.wikipedia.org/wiki/Netpbm_format

A jeśli nie chcecie zagłębiać się w te techniczne detale (bo i po co?) to potraktujmy ten wstęp teoretyczny za zakończony i przejdźmy do sedna...

Dithering

Tak się jakoś złożyło, że przez ostatnie dni zagłębiłem się w tematykę ditheringu. Cóż implementacja algorytmów sama w sobie nie jest ciężka i po prawdzie przynosi ogrom radości, gdy w końcu udaje się wygenerować w miarę podobny do pierwowzoru obraz :P
Tak czy inaczej w celu uproszczenia programu używałem plików PGM/PBM.

Ale czym jest sam dithering? W skrócie to jest to taka transformacja obrazu by przy mniejszej palecie kolorów dawał złudzenie większej palety, czy jak kto woli - najbardziej przypominał on pierwowzór.
Innymi słowy chodzi o to by np. taki 8 bitowy/px obraz (256 kolorów)

Orginal grayscale picture

Po redukcji do 1 bita na piksel (2 kolory) nie wyglądał tak:

Threshold dithering

ale np. tak:

Ordered dithering

Floyd-Steinberg combined with ordered dithering

Floyd-Steinberg combined with ordered dithering and negative error propagation

Prawda, że widać różnicę? Algorytmów do ditheringu jest cała masa i mimo iż niegdyś używano ich prawie jedynie do przełamywania technologicznych ograniczeń (np. wyświetlacze o małej gamie barw) to obecnie używa się ich również w artystycznym ujęciu. Ot choćby obraz wektorowy poddany ditheringowi może okazać się ciekawszy dla widza niż przed taką obróbką (ludzie to takie dziwne stworzenia co nie lubią wyraźnych konturów i jednolitych powierzchni).