Metody klasyfikacji obiektów w wizji komputerowej - ebook

Przedmowa

O rozpoznawaniu obiektów

Rozpoznawanie obiektów (ang. pattern recognition) jako dziedzina nauki zajmuje się różnymi aspektami, teoretycznymi i praktycznymi, projektowania i tworzenia komputerowych systemów rozpoznawania. Należy w tym miejscu poczynić uwagę, że istnieją również inne polskie tłumaczenia angielskiego terminu pattern recognition, znane jako rozpoznawanie obrazów lub rozpoznawanie wzorców. Celem każdego komputerowego systemu rozpoznawania jest, mówiąc najogólniej, udzielanie prawidłowych odpowiedzi, czyli wytwarzanie odpowiednich wartości wyjściowych na wprowadzane dane wejściowe, którymi są obiekty podlegające rozpoznawaniu. Odpowiedź komputerowego systemu rozpoznawania na podany obiekt może być liczbą naturalną, dowolną liczbą rzeczywistą lub też podziałem na grupy podanego na wejście zbioru obiektów. W pierwszym przypadku mówimy o zadaniu klasyfikacji nadzorowanej (ang. supervised classification), odpowiedź stanowi tu etykietę klasy obiektu. W drugim przypadku mamy do czynienia z zadaniem regresji. Trzeci przypadek dotyczy zadania grupowania, zwanego również klasteryzacją (ang. clustering) lub klasyfikacją nienadzorowaną (ang. unsupervised classification). W przypadku klasyfikacji nadzorowanej i regresji odpowiedzi systemu rozpoznającego mogą być traktowane jako wartości pewnej funkcji opisującej zależność między wyjściem systemu a zmiennymi wejściowymi.

Pojęcie obiekt (ang. pattern) jest w wymienionej dziedzinie traktowane bardzo szeroko. Może ono oznaczać na przykład zjawisko, sytuację, proces, sygnał. Oto kilka przykładów obiektów podlegających rozpoznawaniu: tekst pisany, sygnał mowy, elektrokardiogram, stan diagnozowanego na różne choroby pacjenta, obraz dna oka, poskanowany rysunek techniczny, zdjęcie satelitarne terenu.

Aby możliwe było zunifikowane podejście do rozpoznawania, każdy obiekt powinien być reprezentowany albo w postaci zespołu zmierzonych lub obliczonych cech (tzw. wektora cech), albo w postaci odpowiedniej struktury symbolicznej (np. grafu). Wybrane cechy lub struktura symboliczna są oczywiście uzależnione od rodzaju rozpoznawanego obiektu, natomiast pomysłodawcą przy ich wyborze powinien być specjalista w danej dziedzinie współpracujący z konstruktorem komputerowego systemu rozpoznawania.

Komputerowe systemy rozpoznawania znajdują liczne zastosowania w wielu dziedzinach. Podamy kilka przykładów takich systemów w przypadku, gdy dane wejściowe systemu stanowi obraz pozyskany przez odpowiednie urządzenie do akwizycji, na przykład kamerę czy skaner:

- systemy rozpoznawania znaków: maszynowych i ręcznie pisanych (on/offline),
- systemy rozpoznawania zdjęć lotniczych i satelitarnych terenu dla celów rejestracji zmian w kartografii i meteorologii,
- systemy do badań przesiewowych zdjęć rentgenowskich i innych w medycynie,
- systemy analizy obrazów mikroskopowych dla wykrycia obecności pewnych faz,
- systemy bioidentyfikacji na podstawie obrazu odcisków palców, tęczówki oka i innych cech biometrycznych,
- systemy kontroli jakości produktów w przemyśle na podstawie obrazu taśmy technologicznej,
- systemy bezpieczeństwa, na przykład w prześwietleniach bagażu,
- systemy sterowania ruchem miejskim.

Wymienione systemy rozpoznawania są jednocześnie przykładem tzw. komputerowych systemów wizyjnych szczególnego typu, tj. takich, których celem jest rozpoznanie obiektów występujących w analizowanej scenie. Komputerowy system wizyjny to układ współpracujących ze sobą modułów – urządzeń elektronicznych wraz z oprogramowaniem, którego funkcją jest automatyczna analiza wizyjna otoczenia na podobieństwo zmysłu wzroku u ludzi. W systemie takim soczewkę oka zastąpiono obiektywem, siatkówce odpowiada światłoczuły przetwornik, a rolę ludzkiego mózgu pełni komputer wraz z wyspecjalizowanym oprogramowaniem, które implementuje algorytmy sztucznej inteligencji umożliwiające przetwarzanie i rozpoznawanie informacji obrazowej w stopniu porównywalnym ze zmysłem wzroku człowieka.

Wizję komputerową (ang. computer vision) lub inaczej widzenie komputerowe w sposób najbardziej ogólny można określić jako dział nauki i techniki zajmujący się przetwarzaniem i analizowaniem obrazów cyfrowych w celu uzyskania z nich potrzebnych danych. Na podstawie tych danych komputer lub robot mogą podejmować różnorodne decyzje i przyjmować zadania do wykonania. Przykładami zadań realizowanych przez komputerowe systemy wizyjne mogą być:

- rozpoznawanie obiektów,
- określanie ich położenia w przestrzeni,
- rekonstrukcja sceny trójwymiarowej,
- sterowanie robotami lub manipulatorami.

W książce są przedstawione uniwersalne metody klasyfikacji obiektów, które jednakże są bardzo często stosowane w wizyjnych komputerowych systemach rozpoznawania na różnych etapach przetwarzania, począwszy od operacji niskopoziomowych na obrazie takich jak segmentacja obrazu, a skończywszy na przyporządkowaniu etykiety klasowej obrazom obiektów.

Zanim wyjaśnimy istotę automatycznej klasyfikacji obiektów, rozpatrzmy dla przykładu czynność rozpoznawania przez umysł człowieka tekstów pisanych, stanowiący najdoskonalszy jak dotąd naturalny system rozpoznający. Ten naturalny proces rozpoznawania jest wynikiem uprzedniego procesu uczenia z przykładów, które w tym przypadku odbywa się przez wielokrotne pokazywanie (uczniowi) poszczególnych liter wraz z towarzyszącą informacją o tym, jaka to jest litera. W trakcie takiego procesu prezentacji dochodzi w mózgu do wytworzenia pewnych reguł decyzyjnych, które umożliwiają późniejsze, samodzielne czytanie tekstów. Zdolność do uczenia się jest podstawową cechą charakteryzującą komputerowe systemy rozpoznawania. Konieczność fazy uczenia z przykładów w każdym komputerowym systemie rozpoznającym jest konsekwencją braku wiedzy na temat wspomnianych reguł decyzyjnych. Cała dostępna wiedza na ten temat jest zawarta jedynie w zbiorze przykładów.

Na czym polega uczenie się w komputerowym systemie rozpoznawania? Najogólniej oznacza ono pewne zmiany w systemie o charakterze adaptacyjnym, które umożliwiają mu coraz lepsze lub wydajniejsze działanie . W rezultacie procesu uczenia system wypracowuje pewne uogólnienia doświadczenia pozyskane z przykładów uczących, co stanowi rodzaj wiedzy, która nie została bezpośrednio wprowadzona do systemu, lecz nabyta przez niego podczas procesu uczenia. Wiedza ta może być reprezentowana na wiele różnych sposobów, na przykład za pomocą rozkładów prawdopodobieństwa, współczynników pewnych funkcji, zbioru reguł, struktur symbolicznych, gramatyk formalnych, hierarchii podziałów.

Zaprojektowanie komputerowego systemu rozpoznawania wymaga realizacji wielu podzadań, spośród których do najważniejszych należą kolejno:

- wstępne przetwarzanie obiektów,
- tworzenie ich właściwej reprezentacji poprzez ustalenie cech je charakteryzujących lub odpowiedniej struktury symbolicznej,
- uczenie,
- ocena jakości skonstruowanego systemu.

W przypadku klasyfikacji nadzorowanej chodzi o przyporządkowanie nieznanego obiektu podanego na wejście systemu do odpowiedniej klasy, na przykład pacjenta do klasy zdrowych lub chorych na pewną chorobę. Najważniejszym elementem systemu rozpoznającego jest tu klasyfikator, czyli funkcja odwzorowująca przestrzeń reprezentacji obiektów w zbiór numerów klas. Klasyfikator zostaje wyznaczony w procedurze uczenia na podstawie tzw. zbioru uczącego, czyli wylosowanego, małego podzbioru obiektów populacji podlegającej badaniu, tzn. populacji, dla której chcemy zbudować klasyfikator. Każdy obiekt zbioru uczącego ma tu etykietę mówiącą o jego rzeczywistej przynależności do określonej klasy.

W klasyfikacji nadzorowanej zasadniczo wyróżnia się dwa podejścia różniące się sposobem traktowania rozpoznawanego obiektu.

1) Podejście decyzyjno-teoretyczne, zwane też statystycznym, w którym każdy obiekt reprezentowany jest przez wektor cech widziany jako punkt w przestrzeni cech. W obrębie tego podejścia mieszczą się również metody wykorzystujące sztuczne sieci neuronowe.

2) Podejście strukturalne, w którym każdy obiekt jest reprezentowany jako złożenie składowych pierwotnych za pomocą różnych relacji, jakie mogą zachodzić między tymi składowymi.

W obrębie podejścia decyzyjno-teoretycznego można wyróżnić trzy zasadnicze grupy algorytmów. Pierwszą grupę stanowią algorytmy oparte na koncepcji podobieństwa: obiekty podobne do siebie powinny zostać przydzielone do tej samej klasy. Przykładami są algorytmy oparte na dopasowaniu wzorców (ang. template matching) oraz algorytmy minimalno-odległościowe (ang. minimum distance). Druga grupa to empiryczne klasyfikatory Bayesa, w których klasyfikator konstruuje się na podstawie funkcji gęstości prawdopodobieństwa wielowymiarowego rozkładu cech obiektów. Klasyfikatory definiowane w sposób bezpośredni tworzą trzecią grupę. Po wybraniu modelu, tzn. jego postaci funkcyjnej, następuje określanie na podstawie zbioru uczącego wartości nieznanych parametrów funkcji lub samej funkcji, za pomocą różnych algorytmów – najczęściej optymalizacji odpowiednio dobranych funkcji kryterialnych. Specyficznym typem klasyfikatora jest klasyfikator drzewiasty wykorzystujący drzewo decyzyjne, które uzyskuje się na podstawie zbioru uczącego.

W obrębie podejścia strukturalnego wyróżnia się dwie różne grupy metod konstrukcji algorytmów klasyfikacji. Algorytmy pierwszej grupy wykorzystują struktury symboliczne – obiekt reprezentowany jest za pomocą struktury symbolicznej, na przykład ciągu, drzewa czy grafu. Klasyfikacja odbywa się przez strukturalne dopasowanie struktury symbolicznej nieznanego obiektu do modeli klas. Drugą grupę tworzą metody wykorzystujące gramatykę, zwane inaczej syntaktycznymi, w których model klasy jest zdefiniowany przez gramatykę będącą mechanizmem generującym wszystkie wystąpienia obiektów danej klasy w postaci odpowiedniej do typu gramatyki: ciągu, drzewa, czy grafu. Klasyfikacja odbywa się przez wykonanie analiz syntaktycznych reprezentacji nieznanego obiektu względem gramatyk definiujących klasy.

W klasyfikacji nienadzorowanej, popularnie zwanej grupowaniem, systemowi dostarcza się zbiór uczący złożony jedynie z opisów obiektów bez ich etykiety klasowej. O dostarczonym zbiorze zakłada się, że składa się on z pewnych grup, przy czym liczba grup jest najczęściej również nieznana. System rozpoznawania ma odkryć za pomocą odpowiednich algorytmów grupowania nieznany podział dostarczonego mu zbioru, czyli dokonać grupowania tego zbioru. Grupowanie polega na takiej organizacji zbioru obiektów w grupy, aby obiekty w obrębie każdej grupy były bardziej „podobne” do siebie niż do obiektów z innych grup. Zdecydowana większość algorytmów opiera się na reprezentacji wektorowej, dlatego w tej książce zajmiemy się jedynie tym przypadkiem. Istnieje wiele różnych podziałów algorytmów grupowania, stosownie do różnych kryteriów. Biorąc pod uwagę wielką różnorodność tych algorytmów oraz kryteriów podziału, jest praktycznie niemożliwe zaproponowanie podziału ujmującego w sposób jednolity je wszystkie. Na potrzeby niniejszej książki przyjmiemy podział zaproponowany w opracowaniu , według którego wyróżnia się dwie podstawowe grupy algorytmów:

- Algorytmy podziałowe dające w wyniku jeden podział zbioru uczącego. Wśród najbardziej znanych należałoby wymienić algorytmy iteracyjnej optymalizacji, algorytmy gęstościowe i grafowe.
- Algorytmy hierarchiczne dające w wyniku hierarchię zagnieżdżonych podziałów zwaną dendrogramem. Można tu wyróżnić podgrupę algorytmów aglomeracyjnych oraz algorytmów podziału.

W algorytmach optymalizacji iteracyjnej podział jest wynikiem iteracyjnej minimalizacji obranej funkcji kryterialnej. W algorytmach gęstościowych grupy są identyfikowane przez obszary w przestrzeni cech o dużej gęstości, które są oddzielone od siebie obszarami o małej gęstości. Algorytmy tej grupy różnią się sposobem estymacji funkcji gęstości oraz poszukiwania jej maksimów. W algorytmach grafowych wektory zbioru reprezentowane są w postaci różnych grafów, a grupy identyfikowane są jako podgrafy spełniające określone kryteria. Spośród innych algorytmów można wymienić algorytmy grupowania, które wykorzystują sieci neuronowe, na przykład sieć Kohonena uczoną przez współzawodnictwo. W algorytmach hierarchicznych tworzenie dendrogramu może być rozpoczynane od dołu przez łączenie małych grup w większe, jak w algorytmach aglomeracyjnych, lub od góry, przez podział dużych grup na mniejsze, jak w algorytmach podziału.

W książce są omawiane podstawowe metody klasyfikacji, natomiast na końcu każdego rozdziału są podane najważniejsze pozycje literaturowe (w tym książkowe). Dopiero sięgnięcie do tych ostatnich daje Czytelnikowi możliwość uzyskania pełnej bibliografii w dziedzinie rozpoznawania obiektów.

O książce

Książka powstała na podstawie notatek do wykładu „Wizja komputerowa i rozpoznawanie obrazów” (pierwotnie „Podstawy przetwarzania i rozpoznawania obrazów”), który Autorka wygłasza od lat na kierunku informatyka na Wydziale Automatyki Elektroniki i Informatyki Politechniki Śląskiej w Gliwicach. Jest to podręcznik i nie pretenduje do roli monografii przedmiotu. Jest to drugie, poprawione i uzupełnione wydanie poprzedniej wersji wydanej ponad pięć lat temu nakładem Akademickiej Oficyny Wydawniczej EXIT pod tytułem Automatyczna klasyfikacja obiektów. W obecnym wydaniu nacisk został położony na zastosowania metod klasyfikacji w komputerowych systemach wizyjnych. W związku z tym zostały zamieszczone w książce następujące ich przykłady:

- komputerowy system wizyjny dla rozpoznawania jaskry w okulistyce,
- komputerowy system wizyjny dla rozpoznawania map geodezyjnych w geodezji i kartografii wraz z podsystemami dla rozpoznawania symboli kartograficznych.

Od Czytelnika wymagana jest znajomość elementarnych podstaw rachunku prawdopodobieństwa, statystyki matematycznej, algebry liniowej i optymalizacji (programowanie liniowe i kwadratowe).

Książka składa się z 10 rozdziałów. W „Przedmowie”, po wprowadzeniu w zagadnienie maszynowej klasyfikacji obiektów, jest przedstawiona krótka charakterystyka istniejących podejść do klasyfikacji obiektów. Rozdział 1 zawiera definicje poszczególnych komponentów zadania automatycznej klasyfikacji (nadzorowanej i nienadzorowanej) oraz opisy dwóch podstawowych metod reprezentacji obiektów. Są w nim zamieszczone również dwa proste przykłady zadania klasyfikacji: klasyfikator minimalno-odległościowy oraz algorytm grupowania sekwencyjnego. Poszczególne, omawiane algorytmy klasyfikacji różnią się postacią funkcji dyskryminacyjnych oraz metodami ich uczenia. Z tego względu prezentacja algorytmów klasyfikacji w rozdziałach 2 i 3 sprowadza się do opisu funkcji dyskryminacyjnych i metod ich uzyskiwania. W rozdziale 2 omawiam grupę empirycznych klasyfikatorów Bayesa, w których wykorzystuje się ogólną postać funkcji dyskryminacyjnych optymalnego klasyfikatora Bayesa. Rozdział 3 poświęcony jest obszernej grupie klasyfikatorów, w których funkcje dyskryminacyjne znajduje się bezpośrednio jako funkcje liniowe lub nieliniowe, przez optymalizację odpowiedniej funkcji kryterialnej. Klasyfikatorom strukturalnym poświęcone są rozdziały: czwarty, który dotyczy klasyfikatorów definiowanych przez struktury symboliczne, oraz piąty, zawierający opis klasyfikatorów definiowanych przez gramatyki. W rozdziałach tych został opisany komputerowy system wizyjny służący do rozpoznawania map geodezyjnych, a w szczególności Polskiej Zasadniczej Mapy Kraju. Bazuje on na specjalnie zaprojektowanej reprezentacji, będącej nową, hybrydową strukturą symboliczną. Podziałowe oraz hierarchiczne algorytmy grupowania są treścią rozdziałów szóstego oraz siódmego. Zagadnienia oceny jakości klasyfikatora, jego własności uogólniających, przeuczenia oraz niedouczenia są przedstawione w rozdziale ósmym. Rozdział dziewiąty stanowi wprowadzenie w ważne dla osiągnięcia odpowiedniej sprawności klasyfikacji zagadnienie ekstrakcji i selekcji cech. W rozdziale dziesiątym jest opisane krok po kroku konstruowanie komputerowego systemu wizyjnego dla celów rozpoznawania chorych na jaskrę w okulistyce. „Sercem” systemu wspomagającego lekarza-okulistę jest odpowiednio zaprojektowany klasyfikator, działający na zaproponowanej reprezentacji obrazu dna oka. Każdy z przedstawianych w książce algorytmów klasyfikacji zilustrowany jest przykładem bazującym na odpowiednio wygenerowanym zbiorze uczącym.

W różnych miejscach tekstu zostały usunięte błędy zauważone w pierwszym wydaniu oraz wprowadzone pewne zmiany mające na celu polepszenie wykładu (rozdz. 2, 3, 4, 8 i 9). Jeśli chodzi o rozszerzenia w stosunku do pierwszego wydania, to przede wszystkim dodano nowe punkty w istniejących rozdziałach (2 i 3), a także nowy rozdział (ostatni), w którym są opisane poszczególne kroki konstruowania klasyfikatora obrazów dna oka służącego do wspierania lekarza okulisty w diagnozowaniu jaskry. Rozdziały 1 i 2 zostały gruntownie przebudowane. W rozdziale 2, w części dotyczącej parametrycznych klasyfikatorów Bayesa, są dodane nowe przypadki szczególne klasyfikatora gaussowskiego oraz pewne informacje na temat regularyzowanej analizy dyskryminacyjnej. Część dotyczącą empirycznych klasyfikatorów nieparametrycznych została uzupełniona o nowe, wybrane algorytmy „usprawniające” implementację klasyfikatora k najbliższych sąsiadów. W rozdziale trzecim dodano punkt opisujący liniowy klasyfikator Fishera. Rozdział 8 został nieco „przebudowany”, tak by służył lepszemu zrozumieniu tak ważnego problemu, jakim jest ocena błędu klasyfikatora. W rozdziale 9 został rozbudowany punkt dotyczący analizy komponentów głównych a także podpunkt dotyczący selekcji cech. Rozdział 10 jest nowym rozdziałem, w którym jest opisane tworzenie klasyfikatora w praktyce. Liczne przykłady zamieszczone w tej książce zostały zaimplementowane w systemie do obliczeń naukowo-technicznych Matlab.

Tematyka poruszana w niniejszej książce ma bogatą literaturę. Wśród pozycji anglojęzycznych ważne są prace: . W literaturze polskojęzycznej należałoby wskazać przede wszystkim prace: . Spośród wymienionych, najbardziej znanych prac w języku polskim jest tylko jedna pozycja: R. Tadeusiewicz, M. Flasiński Rozpoznawanie obrazów, wydana w 1991 r., w której są omówione oba podejścia do rozpoznawania obiektów: decyzyjno-teoretyczne oraz strukturalne. Niniejsza książka zapełnia więc istniejącą w tej kwestii na polskim rynku lukę. Są tu przedstawione w jednolitym ujęciu poszczególne elementy składowe komputerowych systemów klasyfikacji obiektów, czyli automatycznej klasyfikacji obiektów, w których obiekt może mieć reprezentację zarówno wektorową, jak i strukturalną. Zakłada się tu również, że cechy obiektu są ilościowe. Czytelnika zainteresowanego klasyfikacją jakościową odsyłamy na przykład do książki , w której ta klasyfikacja stanowi główny temat. Czytelnika zainteresowanego zadaniem regresji odsyłamy do odpowiednich podręczników, na przykład .

Podziękowania

W pewnym zakresie do powstania niniejszej książki przyczynili się niektórzy moi dyplomanci i doktoranci, implementując i testując wybrane algorytmy, co przyczyniło się do poprawy niektórych błędów. Za to im serdecznie dziękuję ! Dziękuję również swojemu doktorantowi, panu dr. Adrianowi Bruecknerowi za pomoc w wykonaniu niektórych rysunków oraz obliczeń do przykładów zamieszczonych w niniejszej książce.

Osobne podziękowania należą się Paniom Redaktor: Kindze Tomaszewskiej oraz Izabeli Mice z Redakcji Matematyczno-Przyrodniczej Wydawnictwa PWN za przychylność i cenne uwagi.

Literatura

Bishop Ch. (2006), Pattern recognition and machine learning. Springer, Berlin.

Bolc L., Zaremba P. (1992), Wprowadzenie do uczenia się maszyn. Akademicka Oficyna Wydawnicza PLJ, Warszawa.

Bunke H., Sanfelieu A. (2000), Syntactic and structural pattern recognition. Theory and applications. World Scientific, Singapore.

Cichosz P. (2000), Systemy uczące się. WNT, Warszawa.

Devroye L., Gyorfi L., Lugosi G. (1996), A probabilistic theory of pattern recognition. Springer, Berlin.

Duda R.O., Hart P.E., Stork D.G. (2000), Pattern classification and scene analysis. Wiley, New York.

Gatnar E. (1998), Symboliczne metody klasyfikacji danych. PWN, Warszawa.

Jain A.K., Duin R.P.W., Mao J. (2000), „Statistical pattern recognition: a review”. IEEE Trans. PAMI, 22(1), s. 4–37.

Jain A.K., Murthy M.N., Flynn P.J. (1999), „Data clustering: a review”. ACM Computing Surveys, 31(3), s. 264–323.

Hastie T., Tibshirani R., Friedman J., (2001), The elements of statistical learning: data mining, inference and prediction. Springer, Berlin.

Krawiec K., Stefanowski J. (2003), Uczenie maszynowe i sieci neuronowe. Wyd. Politechniki Poznańskiej, Poznań.

Koronacki J., Ćwik J. (2005), Statystyczne systemy uczące się. WNT, Warszawa.

Krzyśko M., Wołyński W., Górecki T., Skorzybut M. (2008), Systemy uczące się. WNT, Warszawa.

Kulikowski J.L. (1972), Cybernetyczne układy rozpoznające. PWN, Warszawa.

Kurzyński M. (1997), Rozpoznawanie obiektów. Metody statystyczne. Oficyna Wyd. Politechniki Wrocławskiej, Wrocław.

Malina W. (2002), Podstawy automatycznej klasyfikacji obrazów. Wyd. Politechniki Gdańskiej, Gdańsk.

Malina W., Śmiatacz M. (2010), Rozpoznawanie obrazów. Akademicka Oficyna Wydawnicza EXIT, Warszawa.

Schalkoff R.J. (1996), Pattern recognition: statistical, structural and neural approaches. Wiley, New York.

Stąpor K. (2005), Automatyczna klasyfikacja obiektów. Akademicka Oficyna Wydawnicza EXIT, Warszawa.

Stąpor K. (2008), Wykłady z metod statystycznych dla informatyków. Wyd. Politechniki Śląskiej, Gliwice.

Szczepaniak P. (2004), Obliczenia inteligentne, szybkie przekształcenia i klasyfikatory. Akademicka Oficyna Wydawnicza EXIT, Warszawa.

Tadeusiewicz R., Flasiński M. (1991), Rozpoznawanie obrazów. PWN, Warszawa.

Theodoridis S., Koutroumbas K. (2009), Pattern recognition. Elsevier Academic Press, Amsterdam.

Webb A.R., (2002), Statistical pattern recognition. Wiley, New York.

Wojciechowski K. (1987), Rozpoznawanie obrazów. Wyd. Politechniki Śląskiej, skrypt nr. 1304, Gliwice.1

Elementy składowe zadania rozpoznawania

W rozdziale są przedstawione dwie podstawowe metody reprezentacji obiektów: wektorowa i strukturalna oraz elementy składowe zadania klasyfikacji nadzorowanej i nienadzorowanej. Jest to uzupełnione dwoma prostymi przykładami zadań klasyfikacji opisującymi: procedurę konstruowania klasyfikatora minimalno-odległościowego i algorytm grupowania sekwencyjnego.

1.1. Metody reprezentacji obiektów

Aby możliwe było zunifikowane podejście do rozpoznawania, każdy obiekt należy przedstawić albo w postaci wektora cech, czyli zespołu pomierzonych lub obliczonych cech, albo w postaci odpowiedniej struktury symbolicznej. Poniżej podajemy krótką charakterystykę tych dwóch rodzajów reprezentacji.

Reprezentacja wektorowa

W tej metodzie reprezentacji obiekt jest opisywany za pomocą cech (ang. features), tj. wielkości poddających się naszej obserwacji lub pomiarowi. Natura cech jest określona rodzajem rozpoznawanego obiektu i zależy od zastosowanej techniki pomiarowej. Zbiór wytypowanych d cech Z_(k) (dla k = 1, ..., d), „ujęty” w postaci wektora-kolumny:

(1.1)

nazywany jest wektorem cech obiektu. Jego „realizację” stanowi ciąg d kolejnych wartości wytypowanych cech (potocznie te dwa pojęcia są utożsamiane). Wartości te stanowią opis obiektu, jego reprezentację, która w zadaniu klasyfikacji jest jedynym źródłem informacji o obiekcie.

Poczynimy w tym miejscu ogólną uwagę dotyczącą stosowanej w książce notacji dla wektora. Mianowicie, w celu uproszczenia zapisów oraz ze względu na fakt, że będziemy mieli do czynienia prawie zawsze z wektorem o więcej niż jednej składowej, będziemy oznaczać wektor samą tylko literą, na przykład w, zamiast notacji tradycyjnej , tzn. bez znaku wektora nad literą.

Zbiór wszystkich wartości, jakie może przyjmować wektor cech w rozpatrywanym zadaniu klasyfikacji, nazywa się przestrzenią cech (ang. feature space). Oznaczać ją będziemy literą E. Obiekty w przestrzeni cech są reprezentowane przez punkty (rys. 1.1).

Realne obiekty są na ogół opisywane dużą liczbą cech. Cechy powinny być tak dobrane, aby były reprezentatywne, tzn. by obiekty pochodzące z różnych klas miały różne wartości tych cech, a obiekty z tej samej klasy – wartości dość zbliżone. W literaturze istnieją liczne metody selekcji cech pozwalające na wybór optymalnego podzbioru cech, tzn. zapewniającego największą zdolność rozróżniania obiektów z różnych klas. Istnieją również metody ekstrakcji cech polegające na generacji nowych cech z istniejących, co w niektórych przypadkach umożliwia lepszą rozróżnialność.

Jeśli w przestrzeni cech istnieje hiperpłaszczyzna, za pomocą której można rozdzielić obiekty pochodzące z dwóch klas, to mówimy, że są one liniowo separowalne (rys. 1.1a). W przeciwnym wypadku mamy do czynienia z przypadkiem nieliniowej separowalności (rys. 1.1b). Aby zbiór obiektów pochodzących z więcej niż dwóch klas (c > 2) był liniowo separowalny, dla każdej pary klas musi istnieć hiperpłaszczyzna rozdzielająca w przestrzeni cech, czyli razem (c – 1) hiperpłaszczyzn.

Rys. 1.1. Obiekty w 2-wymiarowej przestrzeni cech: a) liniowo separowalne, b) nieliniowo separowalne

Cechy obiektów mogą być dwojakiego rodzaju: jakościowe i ilościowe. Cechy jakościowe to takie, które nie mogą być w sposób jednoznaczny i oczywisty scharakteryzowane za pomocą liczb (np. grupa krwi, kolor). Cechy ilościowe z kolei dają się wyrazić za pomocą jednostek miary w pewnej skali (np. wzrost, poziom hemoglobiny we krwi). W obrębie cech ilościowych, zwanych też mierzalnymi, wyróżniamy dwie podgrupy: cechy ciągłe i dyskretne. Dziedziną cech ciągłych są liczby rzeczywiste, a cech dyskretnych – liczby całkowite; w obu przypadkach zazwyczaj z pewnego przedziału. Szczególnym przypadkiem tej drugiej grupy są cechy binarne, wskazujące na przykład na obecność lub brak jakiegoś objawu.

Po wytypowaniu cech, które będą reprezentatywne dla populacji obiektów z wielu klas, musimy podjąć decyzję o tym, jak będziemy mierzyć wartości bądź określać odmiany tych cech w trakcie obserwacji. Badając na przykład liczbę białych ciałek we krwi, możemy określić ją, używając terminów „poniżej normy”, „w normie”, „powyżej normy”, czyli w tak zwanej skali porządkowej, lub możemy określić ją w liczbach w polu widzenia. Wybór odpowiedniego sposobu pomiaru oraz sposobu przedstawiania jego wyniku zależy od celu zadania klasyfikacji.

Cechy możemy określać na następujących skalach wartości.

- Skala nominalna: dotyczy cech jakościowych, umożliwia jedynie stwierdzenie, czy dwie cechy są równe, czy różne (np. grupa krwi).
- Skala porządkowa: umożliwia ustalenie relacji porządku liniowego w zbiorze wartości cechy (np. poniżej normy, w normie, powyżej normy).
- Skala liczbowa: dziedziny wartości cechy są zdefiniowane na liczbowych skalach pomiarowych, przedziałowych i ilorazowych. W tych ostatnich jest zdefiniowane bezwzględne zero i możliwe są względne porównania obiektów za pomocą ilorazów (np. jeden obiekt jest większy od drugiego k razy).

W przypadku gdy składowe wektora cech są liczbami rzeczywistymi, mamy do czynienia z d-wymiarową przestrzenią euklidesową, tj. E = R^(d), gdzie R jest zbiorem liczb rzeczywistych. W niniejszej książce, jeśli chodzi o reprezentację wektorową, będziemy ograniczali się tylko do tej przestrzeni.

Reprezentacja strukturalna

Charakterystyczną cechą podejścia strukturalnego jest reprezentowanie struktury obiektów, która rozumiana jest jako specyficzny sposób złożenia z prostszych obiektów składowych. Złożony obiekt jest dzielony na prostsze obiekty składowe do momentu, aż otrzymamy tzw. składowe pierwotne obiektu zwane również prymitywami, które są już pewnymi niepodzielnymi i niezależnymi elementami. Prymitywy definiuje się w zależności od konkretnego zastosowania. Równie ważnym jak definicja prymitywów jest określenie prawidłowego sposobu ich złożenia. Określenie tego złożenia odbywa się przez identyfikację różnych relacji, jakie zachodzą między prymitywami i utworzonymi z nich obiektami składowymi w obiekcie złożonym. Odpowiednio do dwóch kierunków istniejących w podejściu strukturalnym stosowane są dwa rodzaje reprezentacji:

1) struktury symboliczne,

2) gramatyki.

W pierwszym z nich obiekty i modele klas reprezentowane są za pomocą struktur symbolicznych, takich jak na przykład ciąg (łańcuch), drzewo, graf czy opis relacyjny. Struktury te umożliwiają wyrażenie w jawny sposób relacji między elementami składowymi obiektu.

Przykład wykorzystania grafu do reprezentacji symboli kartograficznych na mapach geodezyjnych jest pokazany na rys. 1.2 oraz rys. 1.3. Pochodzi on z pracy . Węzły w grafie reprezentują wierzchołki (punkty narożne) danego symbolu, a krawędzie grafu odpowiadają łukom krzywych (odcinkom prostym) łączącym dwa punkty narożne w symbolu kartograficznym. Krawędzie w grafie mogą być dodatkowo etykietowane wektorem atrybutów, które opisują parametry łuków krzywych (np. długość znormalizowana, kąt). Dla symboli wieloobiektowych, takich jak na przykład symbol drzewa pokazany na rys. 1.3, stosowany jest dodatkowo tzw. graf komponentów, w którym wierzchołki reprezentują proste obiekty składowe złożonego obiektu, a jego krawędzie określają relacje, jakie zachodzą między nimi. W ogólnym przypadku relacje te mogą być nie tylko typu przestrzennego, jak w prezentowanym zastosowaniu, ale również temporalne, konceptualne itp.

Rys. 1.2. Graf prototypu (a) i obiektu (b) symbolu kartograficznego fontanna

Rys. 1.3. Grafy składników prototypu symbolu kartograficznego drzewo (a) oraz graf komponentów (b)

Drugi rodzaj reprezentacji strukturalnej to gramatyka, za pomocą której specyfikowane są modele klas. W uproszczeniu, gramatyka jest zbiorem reguł zapisanych w postaci produkcji gramatyki, określających sposób złożenia obiektu z prostszych obiektów składowych. Wszystkie relacje między obiektami składowymi są wyspecyfikowane niejawnie w produkcjach gramatyki. Gramatyka stanowi mechanizm generujący wszystkie wystąpienia obiektów danej klasy. W zależności od typu gramatyki, ciągowej, drzewowej lub grafowej, generowane przez nią struktury są ciągami, drzewami lub grafami.

Zbiór wszystkich możliwych reprezentacji strukturalnych obiektów tworzy przestrzeń opisów strukturalnych.

1.2. Zadanie klasyfikacji nadzorowanej

1.2.1. Sformułowanie problemu

Będziemy zakładać, że na interesującym nas zbiorze obiektów O, które chcemy automatycznie rozpoznawać, czyli na całej badanej populacji, zdefiniowany jest pewien podział na c rozłącznych klas: O₁, ..., O_(c), co jest równoważne istnieniu pewnej funkcji podziału Θ:

(1.2)

która dokonuje odwzorowania zbioru obiektów O w zbiór I indeksów/etykiet klas. Oczywiście reguł przynależności obiektów do poszczególnych klas, a więc funkcji podziału Θ, nie znamy. Dany nam jest jedynie mały podzbiór zbioru O zwany zbiorem uczącym (dokładniej – jego realizacją) o postaci:

(1.3)

Każdy element zbioru uczącego jest parą (x_(i), t_(i)) złożoną z reprezentacji x_(i) obiektu o_(i) oraz etykiety t_(i) klasy, która stanowi poprawną klasyfikację obiektu o_(i) (tj. jego rzeczywistą klasę). W przypadku gdy obiekt o_(i) jest reprezentowany w postaci wektorowej i przestrzeń reprezentacji E stanowi d-wymiarową przestrzeń euklidesową (E = R^(d)), opis obiektu o_(i) jest wektorem którego składowe x_(ik) są wartościami cech Z_(k) (dla k = 1, ..., d) tego obiektu w wybranej przestrzeni reprezentacji E. W tym przypadku zbiór u_(n) jest traktowany jako realizacja zbioru uczącego:

(1.4)

gdzie:

(1.5)

jest d-wymiarowym wektorem losowym, którego składowe nazywane są cechami lub atrybutami, natomiast T_(i) dla i = 1, ..., n są zmiennymi losowymi o takim samym rozkładzie jak rozkład dyskretnej zmiennej losowej T. Rozkład ten jest scharakteryzowany prawdopodobieństwami P(i) pojawiania się poszczególnych klas, czyli etykiet ze zbioru I = {1, ..., c}. Każdy wektor losowy X_(i) przyjmuje wartości z wybranej przestrzeni reprezentacji określonej wektorem cech Każda z par losowych (X_(i), T_(i)) ma identyczny rozkład, taki jak rozkład pary (Z, T).

W komputerowym systemie rozpoznawania nieznana nam funkcja podziału Θ jest „realizowana” lub raczej przybliżana przez złożenie Φ trzech odwzorowań składowych Φ₁, Φ₂, Φ₃ :

Φ = Φ₃Φ₂Φ₁.
(1.6)

Pierwsze z nich:

Φ₁ : O → E,
(1.7)

dokonuje przyporządkowania każdemu obiektowi o ze zbioru O jego reprezentacji x z wybranej przestrzeni reprezentacji E. Etap „zaprojektowania” odpowiedniej reprezentacji obiektu, nazywany często jego recepcją lub generacją cech, jest niesamowicie ważny w systemie automatycznego rozpoznawania.

Odwzorowanie drugie:

Φ₂ : E → R^(c),
(1.8)

przyporządkowuje reprezentacji x obiektu o wektor c liczb rzeczywistych:

,
(1.9)

którego poszczególne składowe są wartościami tzw. funkcji dyskryminacyjnych. Funkcja dyskryminacyjna g_(k)(x) dla k-tej klasy odwzorowuje przestrzeń reprezentacji E w zbiór liczb rzeczywistych R:

g_(k) : E → R, k = 1, ..., c,
(1.10)

i powinna być wybrana w taki sposób, że dla każdej reprezentacji x obiektu z k-tej klasy przyjmuje największą wartość spośród c wartości wszystkich funkcji dyskryminacyjnych:

(1.11)

Wartość g_(k)(x) k-tej funkcji dyskryminacyjnej można traktować jako miarę pewnego podobieństwa lub stopnia przynależności obiektu o reprezentowanego poprzez opis x do k-tej klasy.

Ostatnie odwzorowanie:

Φ₃ : R^(c) → Zd_(c),
(1.12)

przypisuje wektorowi obliczonych wartości funkcji dyskryminacyjnych odpowiednią decyzję i ze zbioru decyzji Zd_(c) = {0, 1, 2, ...., c}:

(1.13)

czyli etykietę klasy lub etykietę 0 symbolizującą decyzję „brak przynależności do klasy”. Wprowadza się ją, gdyż w wielu zadaniach klasyfikacji mamy do czynienia z sytuacjami dwuznacznymi, w których podjęcie decyzji o klasie obiektu jest obarczone dużym ryzykiem i lepiej jest nie podejmować wtedy żadnej decyzji.

Odwzorowanie Φ₃ może być realizowane na wiele różnych sposobów. W podstawowej metodzie podejmowania decyzji obiekt reprezentowany za pomocą opisu x jest przypisywany do tej klasy k ∈ Zd_(c), dla której wartość funkcji dyskryminacyjnej g_(k)(x) jest największa:

(1.14)

W rzeczywistych warunkach mogą zaistnieć sytuacje, w których powyższy warunek nie jest spełniony w sposób wskazujący wyraźnie na jedną, konkretną klasę. Dlatego umożliwia się niepodejmowanie decyzji o przypisaniu etykiety klasowej w takich „niezbyt jasnych” sytuacjach. Mamy wówczas:

(1.15)

co jest znacznie lepszym rozwiązaniem niż wskazanie błędnej klasy.

Spośród wielu możliwych, innych niż podstawowa metod podejmowania decyzji, które uwzględniają ponadto wymienione, niejednoznaczne sytuacje przedstawimy jedną. Metoda ta bazuje na dwóch progach: akceptacji T_(acc) oraz odrzucenia T_(rej):

(1.16)

przy założeniu, że T_(rej) < T_(acc). Metoda wymaga, aby wartość dominującej funkcji dyskryminacyjnej była większa od założonej wartości progowej T_(acc), a wartości wszystkich innych funkcji dyskryminacyjnych poza tą, o maksymalnej wartości nie mogą przekroczyć pewnej wartości progowej. W przeciwnym wypadku sytuacja jest niejednoznaczna i nie podejmuje się żadnej decyzji.

Funkcję Ψ, będącą złożeniem zdefiniowanych wyżej dwóch funkcji składowych Φ₂, Φ₃:

Ψ = Φ₃Φ₂ : E → Zc,
(1.17)

czyli dokonującą odwzorowania przestrzeni reprezentacji E w zbiór decyzji, nazywamy klasyfikatorem, a proces przypisywania etykiety klasowej Ψ(x) danej reprezentacji x pewnego obiektu – klasyfikacją lub czasami predykcją. Odwzorowanie Ψ ma umożliwić przypisywanie reprezentacji x dowolnego obiektu o ze zbioru O do jednej z c klas lub niepodejmowanie decyzji o klasie w sytuacjach wątpliwych. Celem jest znalezienie takiego klasyfikatora Ψ, który daje dokładną predykcję. W przypadku reprezentacji wektorowej miarą jakości klasyfikatora Ψ jest najczęściej jego prawdopodobieństwo błędnej klasyfikacji:

Err(Ψ) = P(Ψ(x) ≠ T).
(1.18)

Jak pokażemy w następnym rozdziale, ze względu na prawdopodobieństwo błędu optymalny jest klasyfikator bayesowski, który je minimalizuje. Niestety zależy on od rozkładu prawdopodobieństwa pary (Z, T), który najczęściej nie jest znany. Dlatego pojawia się problem skonstruowania klasyfikatora

(x) = (x; U_(n))
(1.19)

na podstawie zbioru uczącego U_(n) = {(X₁, T₁), ..., (X_(n), T_(n))}. Tę procedurę konstruowania klasyfikatora na podstawie zbioru uczącego nazywamy jego uczeniem, dokładniej uczeniem z nauczycielem lub uczeniem nadzorowanym (ang. supervised learning). Ponieważ klasyfikator zostaje nauczony tylko na pewnym małym podzbiorze populacji, jakim jest zbiór uczący, powinien mieć jak największe zdolności do uogólniania (generalizacji) własności zbioru uczącego. Dobra generalizacja oznacza „zapamiętanie” tylko własności najbardziej istotnych dla całej populacji, a nie tych związanych z konkretnym zbiorem uczącym. Zbyt dokładne „dopasowanie” do konkretnego zbioru uczącego skutkuje przeuczeniem klasyfikatora. Odwrotna sytuacja, niedouczenie, występuje, gdy klasyfikator nie odzwierciedla istotnych własności populacji. Niedouczenie i przeuczenie obniżają dokładność predykcji, a tym samym jakość klasyfikatora. W rozdziale 8 zajmiemy się dokładniej własnościami generalizacyjnymi klasyfikatora i zilustrujemy to pojęcie przykładem.

Jakość klasyfikatora jest definiowana przez warunkowe prawdopodobieństwo błędnej klasyfikacji:

Err(; U_(n)) = (P((x) ≠ T) | (U_(n)),
(1.20)

czyli dla ustalonego zbioru uczącego U_(n). Wielkość Err(; U_(n)) jest zmienną losową, zależy bowiem od losowego zbioru uczącego U_(n). Właściwie powinniśmy oznaczać klasyfikator wyuczony na zbiorze uczącym U_(n) jako (x; U_(n)), często jednak piszemy tylko (x). Chcielibyśmy znaleźć taki klasyfikator , dla którego Err(; U_(n)) jest niewiele większe od błędu klasyfikatora bayesowskiego. Różnym metodom szacowania powyższego prawdopodobieństwa błędnej klasyfikacji poświęcony jest rozdział 8. Prezentowane tam oszacowania są również stosowane dla oceny błędu klasyfikatora opartego na reprezentacji strukturalnej.

Opierając się na wprowadzonym pojęciu funkcji dyskryminacyjnej oraz najczęściej stosowanym sposobie podejmowania decyzji – metodzie podstawowej, można zapisać klasyfikator w następującej postaci:

(x) = k, jeżeli
(1.21)

Zalicza on obiekt reprezentowany opisem x to tej klasy, dla której wartość jej funkcji dyskryminacyjnej jest największa. W powyższym wzorze _(k)(x) oznacza aproksymację na podstawie zbioru uczącego U_(n) nieznanej funkcji g_(k)(x). W przypadku klasyfikatorów wykorzystujących reprezentację wektorową, a więc w przypadku przestrzeni cech E = R^(d), mówimy o tzw. obszarach decyzyjnych w tej przestrzeni. Klasyfikator zdefiniowany za pomocą funkcji dyskryminacyjnych dzieli przestrzeń cech na c rozłącznych obszarów decyzyjnych ObDec_(i):

ObDec_(i) = {x ∈E : (x) = i}, i ∈Zd_(c),
(1.22)

z których każdy odpowiada jednej z c klas. Obszary decyzyjne oddzielone są od siebie powierzchniami decyzyjnymi. Powierzchnia decyzyjna _(ij) (x) rozdzielająca klasę i-tą od klasy j-ej jest dana równaniem:

_(ij)(x) = _(i)(x) – _(j)(x) = 0.
(1.23)

Porównując parami wszystkie funkcje dyskryminacyjne, otrzymamy równania wszystkich możliwych powierzchni decyzyjnych w przestrzeni cech.

Przedstawione zadanie klasyfikacji należy rozpatrywać w dwóch trybach:

- uczenia i walidacji,
- testowania i eksploatacji.

W trybie uczenia i walidacji następuje wyznaczenie modelu, tzn. funkcji dyskryminacyjnych klasyfikatora, wartości pewnych jego parametrów oraz ewentualnie prototypów klas. Tryb ten obejmuje następujące etapy (rys. 1.4):

1) przetwarzanie wstępne,

2) typowanie reprezentacji i jej obliczanie,

3) ekstrakcję i selekcję cech,

4) uczenie klasyfikatora i jego walidację.

Pierwszym etapem jest przetwarzanie wstępne, którego podstawowym celem jest odpowiednie przygotowanie zbioru uczącego, tj. próby losowej wylosowanej z populacji interesujących nas obiektów. Etap ten jest silnie uzależniony od zastosowania. W przypadku systemów widzenia komputerowego etap ten obejmuje akwizycję obrazu, operacje odszumiania i polepszania kontrastu oraz segmentację. Skrótowy opis wymienionych operacji na obrazie znajduje się w rozdziale 10, w którym krok po kroku jest opisana budowa rzeczywistego klasyfikatora obrazów dna oka służącego do diagnozowania jaskry. Niezbędnym procesem jest dokonanie etykietowania wydzielonych obiektów, tzn. przypisanie im klasy przez specjalistę w dziedzinie. Następnym etapem jest wyznaczenie odpowiedniej reprezentacji obiektu: wytypowanie wektora cech lub, w przypadku podejścia strukturalnego, rodzaju struktury symbolicznej/gramatyki. Po wyborze sposobu reprezentacji następuje jej obliczenie dla wszystkich obiektów. Tak utworzony zbiór etykietowanych reprezentacji obiektów tworzy zbiór uczący u_(n). Następne metody selekcji lub ekstrakcji cech stosowane są w celu wyznaczenia zespołu nowych cech o pożądanych, silnych własnościach dyskryminujących. Podstawowym celem uczenia i walidacji jest wyznaczenie modelu, tj. zbioru c funkcji dyskryminacyjnych i ewentualnie prototypów klas (w przypadku niektórych klasyfikatorów) oraz optymalnych wartości nieznanych parametrów klasyfikatora (np. liczby neuronów w warstwie ukrytej perceptronu wielowarstwowego lub wartości parametru regularyzacyjnego C w klasyfikatorze SVM).

Rys. 1.4. Etapy trybu uczenia i walidacji klasyfikatora

W trybie testowania i eksploatacji dokonuje się oceny jakości zbudowanego klasyfikatora, a dalej wykorzystuje się go do klasyfikacji nowych obiektów o nieznanej przynależności klasowej na podstawie ich reprezentacji. Uzyskanie odpowiednio wysokiej sprawności gwarantuje dostatecznie poprawną eksploatację nauczonego klasyfikatora.