Polski

English


Home

O mnie

Badania

Dla studentów

Publikacje

Kontakt

Ukryte Modele Markowa w Rozpoznawaniu Dwuwymiarowych Wzorców na Obrazach Cyfrowych,
Akademicka Oficyna Wydawnicza EXIT, Warszawa, 2013.

Praca dotyczy rozpoznawania wzorców na obrazach cyfrowych. Rozpoznawanie wzorców jest działem sztucznej inteligencji zajmującym się klasyfikacją obserwacji. Celem rozpoznawania jest klasyfikowanie danych (wzorców) na podstawie wiedzy a priori lub na podstawie informacji statystycznych uzyskanych z wzorca. Wzorce są zazwyczaj zbiorem obserwacji lub pomiarów. Przykładami wzorców są: wycinek sygnału EKG, cyfrowy sygnał audio głoski lub słowa, litera (zarówno w postaci obrazu jak i kodu), obraz odcisku palca, obraz tęczówki oka, obraz twarzy, obraz samochodu lub samolotu, czy sekwencja białek. Wśród szerokiej gamy metod rozpoznawania wzorców są metody statystyczne. W przeciwieństwie do metod probabilistycznych wykorzystujących prawdopodobieństwo a priori, metody statystyczne wykorzystują reguły decyzyjne ze zbiorem uczącym, złożonym z obiektów, dla których znany jest wektor cech i etykieta klasy wzorca. Jedną z wielu metod rozpoznawania wzorca są ukryte modele Markowa (UMM). Są powszechnie stosowane w rozpoznawaniu mowy. W przypadku systemów rozpoznawania wzorców na obrazach cyfrowych, opartych o ukryte modele Markowa, pojawia się problem z wymiarowością danych wejściowych. UMM pracują z jednowymiarowymi wektorami opisującymi wzorzec (obraz). Istnieje zatem konieczność przekształcenia wzorców dwuwymiarowych w wektory. Niestety powoduje to utratę części informacji zawartej w obrazie. Struktura obrazu niesie ze sobą informacje, która może być użyteczna w procesie rozpoznawania. Ponadto należy się zastanowić nad koniecznością przekształcania dwuwymiarowej informacji wejściowej w sygnał jednowymiarowy, ponieważ wiąże się to z dodatkowymi operacjami i obliczeniami. Z tego względu wygodniej, łatwiej i szybciej można by było rozpoznawać obrazy (wzorce dwuwymiarowe), gdyby istniała możliwość wprowadzania danych dwuwymiarowych do dwuwymiarowego UMM. Próbę rozwiązania tego problemu przedstawiono m.in. w pracach [Beom-Joon 2004, Eickeler 1999, Min-Ta 2001,] . Przedstawiony tam pseudo 2D ukryty model Markowa, jest połączeniem jednowymiarowych modeli. Model ten nie jest w pełni dwuwymiarowy, a ponadto przetwarza on dane jednowymiarowe. Każdy ze składowych modeli pracuje z wektorem danych. W pełni dwuwymiarowe ukryte modele Markowa zaprezentowano w pracach [Dhiraj 2006, Joshi 2006, Li 2000, Yujian 2007]. Zaproponowano w nich definicje i dowody na poprawność idei 2D UMM. Yujian w [Yujian 2007] pokazał szereg analitycznych formuł i wzorów do rozwiązania trzech podstawowych problemów w UMM. Zaproponowane rozwiązanie problemu wyznaczenia optymalnej sekwencji stanów (mając dany model i sekwencje obserwacji) za pomocą algorytmu Viterbiego jest użyteczne i pomimo przetwarzania danych jednowymiarowych może być łatwo zaadaptowane do danych dwuwymiarowych. Niestety, dla pozostałych dwóch problemów (wyznaczenie prawdopodobieństwa wygenerowania obserwacji przez model oraz estymacja parametrów modelu) zaproponowano rozwiązania potrafiące przetwarzać dane jednowymiarowe. Z kolei Park i Lee w pracy [Park1998] podjęli się rozwiązania problemu analizy danych dwuwymiarowych za pomocą 2D UMM. Niestety, okazało się, że dwuwymiarowy model Markowa występuje jedynie w tytule publikacji. Autorzy tej pracy zaproponowali modyfikację losowych pól Markowa niesłusznie nazywając ją dwuwymiarowym ukrytym modelem Markowa. Losowe pola Markowa mają tutaj zastosowanie w segmentacji obrazów, polegającej na przypisaniu pojedynczego piksela do jednej z dwóch klas – biały lub czarny piksel – a następnie rozpoznaniu napisanego ręcznie znaku. W tej roli losowe pola Markowa spisują się dobrze, jednak w rozpoznawaniu bardziej złożonych wzorców ich zastosowanie jest ograniczone i mniej skuteczne. Jak widać przedstawione metody nie rozwiązują w pełni problemu dwuwymiarowych danych wejściowych reprezentujących wzorce na obrazach cyfrowych. Wspomniane rozwiązania nie dają możliwości realizacji dwuwymiarowych modeli Markowa potrafiących przetwarzać dane dwuwymiarowe. Dlatego podjąłem się opracowania rozwiązania tego problemu i przedstawiono je w dalszej części pracy. Praca składa się z sześciu rozdziałów prezentujących zagadnienia związane z rozpoznawaniem wzorców dwuwymiarowych na obrazach cyfrowych za pomocą dwuwymiarowych ukrytych modeli Markowa. Rozdział pierwszy stanowi wprowadzenie do zagadnienia rozpoznawania wzorca, jego definicje oraz przykłady. Ponadto zdefiniowano problem z przetwarzaniem danych dwuwymiarowych reprezentujących wzorzec przez modele Markowa. W rozdziale drugim przedstawiono charakterystyki wybranych metod rozpoznawania wzorców. Przedstawiono budowę klasycznego systemu rozpoznawania wzorców, oraz omówiono najpopularniejsze podejścia do tego zagadnienia spotykane w literaturze. Więcej uwagi poświecono metodom statystycznym, do których zaliczają się metody bazujące na ukrytych modelach Markowa. Scharakteryzowano najpopularniejsze klasyfikatory wykorzystywane w praktyce. W ostatniej części rozdziału przedstawiono problem wymiarowości spotykany przy ekstrakcji cech wzorców. Rozdział trzeci stanowi przegląd popularnych transformat wykorzystywanych do ekstrakcji cech wzorca z obrazu cyfrowego. W rozdziale autor ograniczył rozważania do metod wykorzystywanych w praktyce i sprawdzających się w analizie i przetwarzaniu skomplikowanych obrazów. Pominięte zostały proste metody ekstrakcji cech wykorzystujące cechy geometryczne, ze względu na ich niską skuteczność przy przetwarzaniu bardziej skomplikowanych obrazów. Rozdział ten jest niezbędnym uzupełnieniem pozostałych rozdziałów, gdyż bez odpowiedniego mechanizmu wydobywania i przetwarzania cech wzorca, nie jest możliwe opracowanie skutecznego systemu rozpoznawania wzorca. Rozdział czwarty przedstawia charakterystykę klasycznych jednowymiarowych ukrytych modeli Makowa. Przedstawiono tu parametry i strukturę modeli wraz z zasadami ich doboru. Omówiono etapy tworzenia systemu rozpoznawani oraz reguły jakimi należy się kierować przy projektowaniu i opracowywaniu metody rozpoznawania wzorca. Ponadto przedstawiono algorytmy służące do estymacji parametrów modeli Markowa oraz wyznaczania prawdopodobieństwa wygenerowania obserwacji przez dany model. Uzupełnieniem rozdziału są praktyczne przykłady zastosowań modeli Markowa pozwalające na lepsze zrozumienie idei i zasady ich działania. W rozdziale piątym przedstawiono autorską propozycję rozwiązania problemu danych dwuwymiarowych przetwarzanych przez ukryte modele Markowa. Przedstawiono założenia do opracowania takich modeli. Zaproponowano strukturę i parametry 2D ukrytych modeli Markowa. Zaprezentowano autorskie zmodyfikowane algorytmy służące do estymacji parametrów ukrytych modeli Markowa oraz wyznaczania prawdopodobieństwa wygenerowania obserwacji przez dany model. Zaproponowane rozwiązania umożliwiają przetwarzanie danych dwuwymiarowych przez dwuwymiarowy ukryty model Markowa. Jako uzupełnienie zamieszczono kody programów realizujących te algorytmy. Rozdział szósty przedstawia wyniki eksperymentów przeprowadzonych przez autora. Na początku scharakteryzowano dane wykorzystane w badaniach. Następnie opisano przebieg eksperymentów, których celem było praktyczne potwierdzenie słuszności i poprawności idei 2D UMM przetwarzających dane dwuwymiarowe. Ponadto przedstawiono porównanie zaproponowanej metody do klasycznej metody PCA i do klasycznych jednowymiarowych ukrytych modeli Markowa. W pracy zaproponowano nowe rozwiązanie problemu przetwarzania dwuwymiarowych danych przez ukryte modele Markowa. Proponowane rozwiązania dotyczą opracowania nowej struktury ukrytego modelu Markowa oraz podstawowych algorytmów niezbędnych w procesach rozpoznawania wzorców. Zaprezentowana idea dwuwymiarowych modeli Markowa przetwarzających dane dwuwymiarowe pozwala na pominięcie kroku przekształcania danych wejściowych z postaci macierzy na wektor. Dzięki temu rozwiązaniu unika się utraty części informacji zawartej w danych wejściowych, co potwierdza wyższy poziom rozpoznania wzorców. Zaprezentowana metodologia i algorytmy pozwalają na opracowanie systemu rozpoznawania wzorca, a zaproponowane nowe rozwiązanie tego problemu jest w pełni użyteczne, co udowodniono eksperymentalnie. Na podstawie przeprowadzonych badań stwierdzono poprawność założenia, że możliwe jest opracowanie systemu rozpoznawania wzorca z wykorzystaniem dwuwymiarowych ukrytych modeli Markowa, oraz poprawność założenia, że dwuwymiarowy model Markowa może działać z danymi dwuwymiarowymi. Na podstawie badań stwierdzono również poprawność działania zmodyfikowanej procedury estymacji parametrów 2D UMM dla danych dwuwymiarowych, oraz procedury wyznaczania prawdopodobieństwa wygenerowania dwuwymiarowej obserwacji przez 2D UMM. Na podstawie wyników przeprowadzonych eksperymentów stwierdzono, że system rozpoznawania wzorców oparty na 2D UMM okazał się skuteczniejszy (92%) niż system z 1D UMM (90%) oraz od metody PCA (86%), Systemy rozpoznawania obrazów oparte o ukryte modele Markowa zaczęły pojawiać się w latach osiemdziesiątych dwudziestego wieku, gdy zaczęto dysponować odpowiednią mocą obliczeniową komputerów. Od tamtej pory stają się coraz powszechniejsze i stanowią konkurencję dla klasycznych metod takich jak analiza komponentów głównych, a dzięki swej skuteczności mogą stać się rozwiązaniami dominującymi. W przyszłości, gdy zasoby obliczeniowe systemów komputerowych wzrosną, będzie możliwe przetwarzanie macierzy cech w całości. Kolejnym kierunkiem rozwoju dwuwymiarowych modeli Markowa jest przetwarzanie obrazów trójwymiarowych. Możliwe będzie wykorzystanie do tego celu zaproponowanego tutaj rozwiązania, ponieważ danymi wejściowymi, stanowiącymi sekwencje obserwacji, mogą być częściowe obrazy dwuwymiarowe wyodrębnione z danych trójwymiarowych.
Dorobek naukowo – badawczy
Moją pierwszą tematyką badań było progowanie obrazów cyfrowych. Klasyczne procedury szybkiej detekcji i/lub rozpoznawania obiektów na scenach niejednorodnych potrzebują segmentacji sceny na jednorodne części – tekstury, to znaczy obszary jednorodne w sensie kryteriów sformułowanych przez badacza. I tylko po segmentacji, można w sposób merytoryczny syntezować algorytmiczne procedury detekcji, rozpoznawania itd. Jednak wiadomo, że procedury segmentacji są procedurami zbyt zasobochłonnymi oraz trudnymi do realizowania w czasie rzeczywistym. W przeciwieństwie do segmentacji, alternatywnym rozwiązaniem są techniki progowania. W przypadku jednorodnych scen wykorzystuje się korelacyjne kryterium Brink’a i entropijne kryterium Pun’a. Jednak rozpoznawanie obiektów na jednorodnych scenach jest przypadkiem dużo prostszym niż spotykane w nowoczesnych technikach rozpoznawanie obiektów na scenach naturalnych w czasie rzeczywistym. Procedura progowania niejednorodnej sceny w celu wydzielania pary „obiekt - tło” posiadającej najlepszy, z pośród możliwych w danej sytuacji, stosunek sygnału do szumu, daje możliwość w większości przypadków uniknięcia procedur segmentacji sceny. Drugim aspektem badań było zapewnienie możliwości automatycznego ustalenia optymalnej wartości progowej dla konstruowania odpowiednich procedur do progowania obrazów. W badaniach przeanalizowano problem czułości znanych kryteriów progowania scen jednorodnych, a także czułości oraz właściwości nowego pseudo-entropijnego kryterium KoJ dla progowania scen niejednorodnych w technikach czasu rzeczywistego. Ponadto opracowano procedurę automatycznego dobierania optymalnej wartości progu.
Kolejną tematyką badań w początkowym etapie mojej kariery naukowej było zastosowanie pseudo-entropii w rozpoznawaniu twarzy. W ramach badań opracowano alternatywną metodę rozpoznawania twarzy, wykorzystującą nowatorskie kryterium podobieństwa JeK (opracowane przez prof. Kompanets'a), wykorzystujące pseudo-entropie i jej właściwości. Ważnym aspektem procesu rozpoznawania twarzy jest odpowiedni wybór przestrzeni cech charakterystycznych. Podobnie jak w rozpoznawaniu dowolnych wzorców należy wybrać charakterystyczne właściwości badanego obiektu oraz uniezależnić je od czynników zakłócających i zewnętrznych. W obrazie twarzy wybiera się punkty niezmienne wraz z wiekiem, oraz takie, których nie można zmienić ani zamaskować lub zniekształcić. Do badań zostały wybrane następujące punkty charakterystyczne twarzy: kąciki oczu, kąciki ust oraz ich górny i dolny brzeg, podstawa nosa oraz koniec brody. Wszystkie punkty zostały przeliczone względem nowego układu współrzędnych, którego środek jest w punkcie O. Wyznaczony on jest w następujący sposób: oś Y przebiega prostopadle do środka odcinka między wewnętrznymi kącikami oczu, natomiast oś X jest równoległa do linii poziomej oczu przebiegającej przez wewnętrzne kąciki oczu i przesunięta w dół o długość odcinka między wewnętrznymi końcami oczu. Jednym z ostatnich etapów w procesie rozpoznawania wzorca jest pomiar podobieństwa badanych obiektów. Dotychczas opracowano wiele metod jego pomiaru, zależnych od rodzaju badanej informacji. W eksperymencie wykorzystano ideę porównywania pary obiektów opartą na pseudo-entropijnym kryterium podobieństwa JeK. Głównym znaczeniem zawartym w przedrostku pseudo jest to, że przedstawionym do analizy obiektom informacyjnym dowolnej natury formalnie przypisano właściwości, które posiadają rozkłady prawdopodobieństw obiektów losowych. Jak potwierdziła praktyka, takie podejście okazało się nie tylko efektywnym ale także zawierającym swoją własna problematykę. Jak wykazał eksperyment, opracowana metoda identyfikacji twarzy z wykorzystaniem pseudo-entropijnego kryterium podobieństwa JeK dała zadowalające wyniki. Ponadto charakteryzuje się niską złożonością obliczeniową w stosunku do metod oparty na obliczeniach statystycznych oraz krótkim czasem potrzebnym do klasyfikacji twarzy umożliwia zastosowanie jej w systemach czasu rzeczywistego. Niestety pomimo obiecujących wyników, dalsze prace nad tą metodą identyfikacji osób wykazały znaczny spadek skuteczności wraz ze wzrostem rozmiaru bazy twarzy (powyżej 100). Przyczyną tego były zbyt małe różnice w cechach geometrycznych twarzy miedzy poszczególnymi osobami. Dlatego dalsze badania skierowano w stronę innych metod identyfikacji osób, czego rezultatem była tematyka badań przedstawiona w rozprawie doktorskiej.

Praca doktorska
Moja praca doktorska dotyczyła biometrii, czyli identyfikacji osób na podstawie cech biologicznych. Postawą mojej pracy doktorskiej była metoda identyfikacji osób w oparciu o fuzję transformacji falkowej i ukrytych modeli Markowa. Wzorcem biometrycznym w tej metodzie był obraz twarzy. Celem badań było opracowanie systemu i komponentów programowych do identyfikacji twarzy reprezentowanej przez jej obraz cyfrowy, w oparciu o fuzje Transformacji Falkowej i Ukrytych Modeli Markowa. Koniecznym wymaganiem do opracowania było udowodnienie eksperymentalne potwierdzające poprawność metody, a także osiągnięcie porównywalnych z istniejącymi systemami poziomu błędów i złożoności obliczeniowej. Ponadto przeprowadzono badania eksperymentalne w celu prawidłowego wyboru odpowiednich wartości parametrów modeli w poszczególnych fazach działania systemu programowego FaMar. Przedstawiona metoda charakteryzuję się nowatorstwem polegającym na wykorzystaniu trzech obszarów twarzy (oczy, nos, usta) do identyfikacji i zbudowaniem dla każdego z nich niezależnego ukrytego modelu Markowa. W porównaniu do innych metod identyfikacji twarzy charakterystyki systemu FaMar są porównywalne. Poziom błędów rozpoznawania za pomocą systemu FaMar wynosi około 8%, podczas gdy poziom błędów istniejących metod waha się 3-16%. Praca była wspierana przez grant promotorski KBN nr 4T11C00425.
PDF

Detekcja twarzy
Pierwszym elementem systemu identyfikacji użytkownika jest zagadnienie detekcji twarzy. Rezultat identyfikacji zależy od skuteczności procedury detekcji i lokalizacji twarzy. Istnieje wiele popularnych metod detekcji twarzy, które można podzielić na dwie grupy: (i) bazujące na detekcji koloru skóry, (ii) wykorzystujące dopasowanie wzorca. Do detekcji koloru skóry wykorzystuje się jeden z modeli barw, np. RGB, HSV, YCbCr, a następnie weryfikuje się czy wybrany obszar jest twarzą. W systemach dopasowania wzorca należy przeszukać cały obraz porównując fragmenty do wzorca. Te metody są czasochłonne i wymagające dużej mocy obliczeniowej. Większość z tych metod nie jest użytecznych w systemach typu on-line lub czasu rzeczywistego ze względu na czas obliczeń. Zaproponowana przeze mnie hybrydowa metoda jest użyteczna w tego typu systemach i daje możliwość budowy i rozwoju praktycznych systemów identyfikacji osób. Wykorzystuje ona elementy wspomnianych metod w taki sposób, aby skrócić czas obliczeń. Po wstępnej selekcji potencjalnych obszarów mogących zawierać twarz, następuje weryfikacja przy wykorzystaniu wzorca oczu, a nie całej twarzy, co znacznie skraca czas obliczeń. Opracowana metoda detekcji twarzy wykorzystuje do wstępnej selekcji obszarów model barw HSV. Badania porównawcze wykazały, że użycie tego modelu barw daje najlepsze wyniki w porównaniu do innych modeli i jest mniej podatny na zmiany typu oświetlenia.

Rozpoznawanie mówcy
Rozpoznawanie mówcy służące jego identyfikacji lub weryfikacji, jest automatycznym procesem rozpoznania, kto mówi na podstawie sygnału mowy. Systemy biometryczne wykorzystujące unikalną informacje zawarta w głosie człowieka maja zastosowanie w kontroli dostępu, bankowości telefonicznej czy sterowaniu głosem. Systemy rozpoznawania mówcy można podzielić zależne od tego, co mówi człowiek (konieczne jest wypowiedzenie określonej sekwencji słów), oraz niezależne od wypowiadanych słów. W swoich badaniach na identyfikacją mówcy opracowałem metodę rozpoznawania niezależną od wypowiadanych słów. W praktyce oznacza to, że mówca wygłasza dowolny tekst i na podstawie sygnału mowy jest rozpoznawany. Zaproponowana metoda wykorzystuje analizę cepstralną w skali mel oraz wielopoziomową transformacje falkową. Wyniki eksperymentów pokazały, że korzystając z tego rozwiązania, można zbudować skuteczny system identyfikacji mówcy osiągający skuteczność 90 %.

Kontrola dostępu do zasobów
Kontynuacja moich badań przeprowadzonych w ramach pracy doktorskiej było opracowanie systemu kontroli dostępu do zasobów w czasie rzeczywistym wykorzystującego identyfikacje osób na podstawie obrazu twarzy. System wykorzystuje metodę identyfikacji osób na bazie fuzji transformacji falkowej i ukrytych modeli Markowa. Jednak do tego, aby pracował w czasie rzeczywistym niezbędna była procedura szybkiej detekcji i lokalizacji twarzy na obrazie pochodzącym z kamery. Tutaj przydatne okazały się wyniki moich wcześniejszych badań nad detekcja twarzy. Dzięki dostosowaniu opracowanej wcześniej metody detekcji twarzy powstał zintegrowany system kontroli dostępu do zasobów w czasie rzeczywistym.

Recenzje i ekspertyzy
W swojej pracy naukowej często występuję w roli recenzenta. Dotychczas zrecenzowałem 17 artykułów w czasopismach: Optica Applicata, Machine Graphics & Vision, Metody Informatyki Stosowanej i Przegląd Elektrotechniczny. Recenzowałem również wnioski na dofinansowanie badań z funduszy europejskich w ramach Programu Operacyjnego Innowacyjna Gospodarka. Na zlecenie Narodowego Centrum Badań i Rozwoju recenzowałem 3 wnioski dotyczące projektu zgłoszonego przez Agencje Bezpieczeństwa Wewnętrznego, a dotyczącego zastosowania nowoczesnych technik biometrycznych w dokumentach tożsamości. Będąc biegłym sądowym wykonuję ekspertyzy zlecane przez organy wymiaru sprawiedliwości. Dotychczas wykonałem ponad 50 ekspertyz na zlecenie takich instytucji jak: Prokuratura Krajowa, Centralne Biuro Śledcze, Prokuratura Apelacyjna w Katowicach oraz sądy i prokuratury.