PROBLEMY WSPÓŁCZESNEJ NAUKI TEORIA I ZASTOSOWANIA INFORMATYKA Ryszard S. Choraś KOMPUTEROWA WIZJA Metody interpretacji i identyfikacji obiektów MÓZG' NERW OPTYCZNY KOMPUTER KAMERA Akademicka Oficyna Wydawnicza EXIT Warszawa 2005 KOMPUTEROWA WIZJA METODY INTERPRETACJI I IDENTYFIKACJI OBIEKTÓW Przetwarzanie obrazów i rozpoznawanie obrazów są względnie zamkniętymi obszarami zastosowania komputerów, które wspólnie definiują pole komputerowej wizji. Jest pewna analogia pomiędzy systemem komputerowej wizji i systemem wzrokowym człowieka. Komputerowe przetwarzanie obrazu jest analogiem procesu, który ma miejsce w ludzkim oku i nerwie optycznym. Rozpoznawanie obrazu reprezentuje w większym stopniu percepcję wizualną, która ma miejsce w ludzkim mózgu. Zadania komputerowej wizji przekraczają zadania rozpoznawania obrazów. Tylko niewielka ich część może być opisana przez klasyczny układ rozpoznawania, kiedy zadany jest skończony alfabet klasyfikacji, wystarczająco prosty model opisu klasyfikowanego obiektu (obrazu) i znaleziono regułę decyzyjną, odnoszącą obraz do jednej z wcześniej zadanych klas. Tworzone przez człowieka modele systemów analizy i interpretacji informacji obrazowej oparte sana tym co wiadomo o systemie wzrokowym ludzi (HVS). W książce przedstawiono następujące zagadnienia: • Otrzymywanie (akwizycję) obrazu, • Przetwarzanie wstępne obrazu cyfrowego, • Analizę obrazu, • Rozpoznawanie obrazu. KOMPUTEROWA WIZJA Metody interpretacji i identyfikacji obiektów PROBLEMY WSPÓŁCZESNEJ NAUKI TEORIA I ZASTOSOWANIA INFORMATYKA Edytor serii: Leonard Bole Pamięci Ojca Poświęcam II Przedmowa ..Lecz wy się uczcie patrzeć, a nie gapić.. Bertold Brecht Kariera Artura Ui Vere scire est per causas scire - Prawdziwa wiedza jest wiedzą przyczynową Zainteresowanie zagadnieniami komputerowej wizji wynika z rozwoju szeroko pojętych zagadnień obejmujących informatykę i teorię sterowania i ich wymagań dotyczących dokładności przetwarzanych informacji. Komputerowa wizja (lub jak sugerowało to kilka osób komputerowe widzenie albo komputerowe postrzeganie rozwija się bardzo intensywnie przez ostatnie dziesięciolecia. Jednak wiele fundamentalnych pytań ciągle wymaga odpowiedzi i opracowania sposobów reprezentacji informacji przestrzennej. Książka jest wynikiem lat pracy w dziedzinie przetwarzania obrazów. Nie jest przeglądem prac opublikowanych przez innych Autorów, ale raczej wyborem metod i zagadnień rozwijanych przez Autora. Każdy kto podejmuje trud przedstawienia i dotarcia do Czytelników za pośrednictwem książki zdaje sobie sprawę jak ważną rolę III odgrywa wsparcie ze strony Rodziny. Dziękuję Żonie za wyrozumiałość i cierpliwość, Córce która mobilizowała mnie do zakończenia prac nad książką oraz Synowi który był pierwszym czytelnikiem i krytykiem książki. Podziękowania należą się życzliwym krytykom książki spośród moich kolegów oraz Recenzentowi którego uwagi przyczyniły się usunięcia wielu usterek maszynopisu. Bydgoszcz, maj, 2005 Ryszard S. Choraś Spis treści 1 Wprowadzenie w problematykę komputerowej wizji 1 1.1 Cyfrowe przetwarzanie obrazów 1 1.2 Ogólna charakterystyka systemów komputerowej wizji 1 1.3 Systemy komputerowej wizji w robotyce 5 2 System wzrokowy człowieka 11 2.1 Wprowadzenie 11 2.2 Model systemu wzrokowego 20 3 Akwizycja obrazu 25 3.1 Wprowadzenie 25 3.2 Przetworniki obrazowe optyczno-elektryczne .... 25 3.3 Geometria systemu przetwornika obrazu 31 3.4 Cyfrowa reprezentacja obrazów 34 3.4.1 Próbkowanie obrazu 35 3.4.2 Kwantowanie obrazu 39 3.4.3 Matematyczna reprezentacja obrazu cyfrowego 42 4 Przetwarzanie wstępne obrazu cyfrowego 47 4.1 Histogram obrazu i jego modyfikacje 47 4.2 Transformacja skali jaskrawości obrazu 54 4.2.1 Metoda liniowego dopasowania jaskrawości 57 4.2.2 Metoda transformacji logarytmicznej . 58 4.2.3 Metoda transformacji wykładniczej . . 59 4.2.4 Metoda modyfikacji histogramu .... 59 4.2.5 Zmodyfikowane transformacje: logarytmiczna i wykładnicza 60 4.3 Filtracja obrazu 61 VI Spis treści 4.3.1 Filtry adaptacyjne 65 4.3.2 Filtry wygładzające 68 4.4 Wykrywanie zmian jaskrawości 73 4.5 Segmentacja obrazu 85 4.5.1 Matematyczne sformułowanie zadania segmentacji 86 4.5.2 Segmentacja metodą wydzielania granic obszarów 88 4.5.3 Segmentacja metodą rozmieszczenia punktów obrazu 89 5 Analiza obrazu 95 5.1 Reprezentacja obrazu na podstawie jaskrawości -cechy histogramu 95 5.2 Właściwości topologiczne obrazów 98 5.3 Reprezentacja linii konturowych i granic obiektów 104 5.3.1 Lokalne elementy krzywej 104 5.3.2 Krzywa a - s 110 5.3.3 Reprezentacja konturu obiektu za pomocą współczynników Fouriera .... 112 5.3.4 Interpolacja i aproksymacja krzywej konturu 113 5.3.5 Transformacja Hougłra • • • 117 5.4 Detekcja punktów charakterystycznych obiektu . . 124 5.5 Reprezentacja obszarów obiektów 128 5.5.1 Reprezentacja obszaru za pomocą długości serii elementów 128 5.5.2 Projekcje 129 5.5.3 Reprezentacja hierarchiczna za pomocą drzew czwórkowych i piramidy obrazów 130 5.6 Tekstury i parametry opisu tekstur 133 5.7 Momenty geometryczne 140 5.8 Morfologiczne operacje przetwarzania obrazów . . 147 5.8.1 Morfologiczne operacje przetwarzania obrazów binarnych 147 5.8.2 Morfologiczne operacje przetwarzania obrazów o wielu poziomach jaskrawości 159 5.8.1 6 Rozpoznawanie obrazów163 Spis treści VII • • 163 6.1 Wprowadzenie g 6.2 Klasyfikatory odległościowe ? • 6.2.1 Klasyfikator najmniejszej odległości . . HU 6.2.2 K-najbliższych sąsiadów 6.3 Klasyfikatory statystyczne 6.3.1 Klasteryzacja 6.4 Selekcja cech ' n 197 6.4.1 Wybór nx cech z n początkowych cech i"u 6.4.2 Wybór nx cech poprzez liniową kombinację n cech oryginalnych 6.4.3 Metoda PCA j°J 6.4.4 LDA 6.4.1 Rozdział 1 Wprowadzenie w problematykę komputerowej wizji 1.1 Cyfrowe przetwarzanie obrazów Cyfrowe przetwarzanie obrazów charakteryzuje się obecnie intensywnym rozwojem różnych metod i zastosowań, co ma bezpośredni związek ze zwiększeniem szybkości i efektywności maszyn cyfrowych i ulepszeniem technologii przetwarzania sygnałów. Przetwarzanie obrazów odgrywa istotną rolę w wielu dziedzinach nauki i techniki (10], [80], [41], [42]. Jest stosowane przy cyfrowej transmisji obrazów satelitarnych i wideotelefonii, przy uzyskiwaniu obrazów o wysokiej rozdzielczości oraz jakości za pomocą mikroskopów elektronowych, przy automatycznej klasyfikacji i teledetekcji, przy automatycznym wykreślaniu map na podstawie zdjęć lotniczych, przy wykrywaniu wad i uszkodzeń części maszynowych na podstawie rentgenogramów przemysłowych itd.. Tworzone są systemy przetwarzania obrazów realizujące analizę scen widzianych przez "oko" robota przemysłowego i umożliwiające kontrolę jego operacji. Przedstawiona lista zastosowań jest oczywiście niepełna i daje tylko pewne wyobrażenie o możliwościach wykorzystania cyfrowego przetwarzania obrazów. Przetwarzanie obrazów występuje w każdym z przedstawionych w Tablicy 1.1 zagadnień. 1.2 Ogólna charakterystyka systemów komputerowej wizji Przetwarzanie obrazów i rozpoznawanie obrazów są względnie zamkniętymi obszarami zastosowania komputerów, które wspólnie definiują pole komputerowej wizji. Jest pewna analogia pomiędzy systemem 2 Rozdział 1. Wprowadzenie w problematykę komputerowej wizji Tablica 1.1: Przetwarzanie obrazów i zagadnienia pokrewne Obraz Opis Obraz Przetwarzanie obrazów Komputerowa wizja Rozpoznawanie obrazów Komputerowa wizja Opis Grafika komputerowa Transformacja opisu komputerowej wizji i systemem wzrokowym człowieka. Komputerowe przetwarzanie obrazu jest analogiem procesu, który ma miejsce w ludzkim oku i nerwie optycznym. Rozpoznawanie obrazu reprezentuje w większym stopniu percepcję wizualną, która ma miejsce w ludzkim mózgu. Proces ten można przedstawić: Oko -? Nerw optyczny -? Mózg Kamera -? Przetwornik A/C -> Komputer Otrzymywanie -? Transmisja -? Interpretacja obrazu Komputerowa wizja obejmuje zagadnienia i metody rozwiązania całego szeregu problemów naukowych takich jak np. psychologiczne problemy percepcji wzrokowej, cyfrowe przetwarzanie i analiza obrazu, architektura systemów ekspertowych i technologia ich opracowania, inżynieria wiedzy. Każdy z wymienionych problemów przedstawia samodzielny obszar badań, wykorzystujący swoją metodologię rozwiązywania zadań a także swoje klasy metod i algorytmów. Jakie są zadania komputerowej wizji? Praktycznie wszystkie zadania komputerowej wizji sprowadzają się do rozwiązania następujących problemów: - określenia jakie obiekty znajdują się w polu widzenia użytkownika, 1,2. Ogólna charakterystyka systemów komputerowej wizji 3 gdzie te obiekty są położone, dlaczego dane obiekty znajdują się w polu widzenia tj. jaka jest oglądana sytuacja w całości. Zadania komputerowej wizji przekraczają zadania rozpoznawania obrazów. Tylko niewielka ich część może być opisana przez klasyczny układ rozpoznawania, kiedy zadany jest skończony alfabet klasyfikacji, wystarczająco prosty model opisu klasyfikowanego obiektu (obrazu) i eziono regułę decyzyjną, odnoszącą obraz do jednej z wcześniej Hlanych klas. Częściej spotykamy sytuację, kiedy wyznaczenie skończonego alfabetu klasyfikacji jest trudne a ustalenie zadanego modelu opisu obrazu co najmniej problematyczne czyli, że dokonanie syntezy reguły decyzyjnej w przytoczonym wyżej rozumieniu jest niemożliwe. Część autorów, poprzestaje na przekonaniu, że rozpoznawanie obiektu sprowadza się do identyfikacji jego obrazu z zakodowanym wzorcem. Jednak rozpoznawanie (z funkcjonalnego punktu widzenia) to proces bardziej złożony. Aby rozpoznać obiekt (w pełni), czyli zrozumieć jego znaczenie dla swojego działania należy: - spostrzec go i zidentyfikować, - uświadomić sobie relacje funkcjonalne i znaczeniowe między obiektem a innymi elementami koła spostrzeżeniowego, - uświadomić sobie relacje między obiektem a niektórymi treściami swego doświadczenia, - wzbudzić dodatkowe formy aktywności poznawczej ułatwiające rozpoznanie np. eliminujące czynniki zakłócające proces, - ustalić przedział tolerancji stopnia niezgodności obrazu psychicznego z wzorcem, - skojarzyć obraz psychiczny z nazwą obiektu. Rozwiązanie kompleksowych i złożonych zadań pojmowania obrazu nie jest możliwe, jeżeli w każdym konkretnym momencie czasu mamy do czynienia tylko z cyfrowym zbiorem N x N elementów obrazu. Rozwiązanie tych zadań wymaga zgromadzenia w pamięci systemu różnorodnej informacji, a mianowicie: - o warunkach uzyskiwania obrazów o charakterze otoczenia i ośrodka rozprzestrzeniania wideosygnału (np. kanału), 4 Rozdział 1. Wprowadzenie w problematykę komputerowej wizji - o przedmiotach w obrazie (np. możliwe typy obiektów i ich jaskrawości, geometryczne właściwości itp.), - o doświadczeniach z zakresu przetwarzania obrazu danej klasy (wiedza o najbardziej efektywnych algorytmach i ich parametrach). Pełne, bogate w szczegóły odwzorowanie obrazu przechowywane jest w pamięci ultrakrótkotrwałej, nazywanej też pamięcią ikoniczną. Odwzorowanie takie przechowywane jest w pamięci ikonicznej w celu jego wstępnego przetwarzania umożliwiającego identyfikację. Identyfikacja wzrokowa ma charakter symultaniczny. W ramach wstępnego przetwarzania zostają wyodrębnione poszczególne elementy odwzorowania ze względu na ich lokalizację przestrzenną, a także kształt, wielkości i barwę. W celu identyfikacji wyodrębnione elementy odwzorowania zostają poddane porównaniu z zawartym w pamięci wzorcem. Aby było to możliwe muszą przybrać formę wzorca, z którym mają być porównane, czyli muszą być przetransformowane w odpowiedni kod - na tym etapie następuje pewna strata informacji. Istnieją dwa sposoby stwierdzenia identyczności - tożsamość, czyli stwierdzenie braku różnic, oraz ocena stopnia podobieństwa. Człowiek oglądający obraz nie tylko zapamiętuje odbieraną informację o obrazie, ale wykorzystując odpowiednie obszary mózgu dokonuje jego interpretacji. Interpretacja dokonywana jest nie tylko na odbieranym sygnale obrazu, ale też na wcześniej znanych wiadomościach o tym co obraz powinien sobą przedstawiać. Wiadomości te uzyskuje się z wcześniej odbieranych i przechowywanych w pamięci informacji o obrazie. Porównanie informacji o obrazie z informacją już znajdującą się w pamięci umożliwia interpretację obrazu. Porównanie nie powinno być połączone z pełnym przeglądem informacji znajdującej się w pamięci, gdyż powodowałoby to wydłużenie procesu interpretacji. Unikalność procedury interpretacji - tzw. procedury: analizy przez syntezę - polega na tym, że możliwe jest analizowanie tylko tego fragmentu obrazu, który jest niezbędny do jednoznacznej interpretacji obrazu. Potwierdzeniem prawidłowości modelu analizy przez syntezę są eksperymentalne fakty uzyskane w procesie interpretacji danych przez człowieka. Człowiek przyjmuje do analizy tylko tyle danych, ile jest niezbędnych do potwierdzenia hipotezy odnośnie obrazu i uzupełnia brakującą informację o obrazie danymi ze swojej wewnętrznej pamięci, I Systemy komputerowej wizji w robotyce 5 W której zawarty jest model obrazu. Procedura interpretacji umożliwia: nowej informacji, PI zapamiętywanie w formie pewnych pojęć i ich związków, poszukiwanie w bazie danych informacji pozwalającej na określenie co przedstawia obraz, analizę wybranej informacji, smianę struktury informacji w bazie danych zgodnie z nową informacją, ustalenie nowych związków pomiędzy pewnymi pojęciami o obrazie. Człowiek wykorzystuje tzw. myślenie obrazowe (transformacja obrazu + wyobrażenia wizualne). Na selekcję i identyfikację obrazów w pływają w przypadku człowieka emocje i motywy. Funkcja interpretacji vjna sprowadza się do nadawania znaczeń poszczególnym elemeniniii obrazu. Znaczenia te konkurują ze sobą w fazie identyfikacji ze względu na różne kryteria formalne. W przypadku człowieka na identyfikację i interpretację obrazu ma również wpływ proces myślenia. Wyodrębnienie i rozpoznawanie poszczególnych elementów obrazu może na drodze asocjacji być powiązane z odpowiednimi nazwami, które wydobyte z pamięci pojawiają się w świadomości. Intelekt człowieka pozwala na dalsze przetwarzanie części informacji zawartej w obrazie, na jej wzbogacenie. Dzieje się tak przez interpretację myślową. System komputerowej wizji przedstawiono na Rysunku 1.1. 1.3 Systemy komputerowej wizji w robotyce Spektakularnym przykładem wykorzystania komputerowej wizji są systemy wizyjne robotów inteligentnych lub inaczej nazywanych robotów myślących. Określenia te są skrajnie niejednoznaczne (również w stosunku do człowieka) jako, że dotychczas nie znaleziono dokładnego określenia i miary stopnia inteligencji i myślenia. Wg. Marvina Minsky'ego [62], "o systemie można powiedzieć, , że jest inteligentny, wtedy, gdy może adaptować się do nowych 6 Rozdział 1. Wprowadzenie w problematykę komputerowej wizji Baza danych k* Procedury identyfikacji obiektu * ł ^ Mechanizm interpretacji danych Przetwarzanie wstępne obraza /tL_ -? Pamięć -? Procedury interpretacji obraza Wynik 4_ *- ^ Rysunek 1.1: Schemat blokowy komputerowej wizji sytuacji, gdy ma zdolność rozumowania, rozumienia relacji pomiędzy faktami, odkrywania znaczeń, rozpoznawania prawdy. Często oczekuje się też od niego zdolności do uczenia się, to znaczy udoskonalania swojego działania w oparciu o przeszłe doświadczenia". Natomiast inni Autorzy skłaniają się do poglądu, że sztuczna inteligencja to "nauka komputerowa polegająca na projektowaniu systemów inteligentnych tzn. posługujących się rozumowaniem niealgorytmicznym, twórczym, czyli heurystycznym "[37]. Do podstawowych problemów sztucznej inteligencji (zgodnie z ACM - Association for Computing Machinery) należy z pewnością zaliczyć: - symulację zdolności zmysłowych człowieka (w tym rozpoznawanie obrazów i mowy, interpretacja obrazów), - automatyczne rozwiązywanie problemów, - reprezentację wiedzy, - automatyczne wnioskowanie w sytuacji problemowej, - twórczość maszynową, - teorię gier itp.. Syttcmy komputerowej wizji w robotyce 7 i ię pytanie czy można terminem "inteligentny-myśłący" i bota, wykorzystującego na poziomie sterowania metody MM1 '? się w ramach przytoczonych wyżej obszarów sztucznej ? IM ji. Odpowiedź nie jest jednoznaczna, jako, że pojęcie in',<'iitny-myślący" związane jest nie ze stosowanymi metodami, końcowymi wynikami. Zwykle mówiąc o robotach inteligentnych na myśli roboty, które po zakończeniu procesu uczenia, njłj swoje zadania przy warunku otrzymywania informacji o cniu, w którym funkcjonują. Program działania takiego robota formowany na podstawie zadanego celu, informacji a'priori o !<• i bieżącej informacji otrzymywanej z systemu komputerowej W sformułowaniu ideologii pierwszych systemów komputerowej dla robotyki, ważną rolę odegrały prace Roberts'a [81], Guzmana Falka [24]. Układ blokowy systemu wizji robota przedstawiono na Rysunku ' ()l)iaz poprzez układ optyczny doprowadzany jest do przetwornika i światło-sygnał elektryczny, który jest następnie wzmacniany i zapamiętywany. Układ analizy obrazu służy do wydzielania, określania i">łrzędnych i położenia obiektu oraz rozpoznawania obiektu. Na lawie otrzymanej informacji wypracowywane są sygnały umoż-i jące odpowiedni ruch ramienia manipulatora w kierunku obiektu. W pracach [94], [2] określono wymagania odnośnie systemu wizyj- I robota: szybkość przetwarzania informacji dotyczącej jednego obiektu powinna wynosić ok. 200ms, - system powinien uwzględniać możliwość ruchu obiektu z szybkością do ok. Im/min, - algorytmy przetwarzania obrazów powinny mieć charakter uniwer- salny, - jakość obrazu powinna być wystarczająco wysoka, - mała czułość na zakłócenia. Metody komputerowej wizji rozwinęły się silniej dopiero w ostatnich latach i nabrały znaczenia szczególnie po wprowadzeniu III i kolejnych generacji komputerów. Podstawy teoretyczne i praktyczne 8 Rozdział 1. Wprowadzenie w problematykę komputerowej wizji Przetwornik światło -sygnał ^ Układ przetwarzania wstępnego obrazu n ?/,>??? zr Pamięć obraza Układ analizy obrazu Przestrzeń Robota Mikroprocesor Mechanizm wykonawczy Sterownik Układ sterownika wizji Rysunek 1.2: Schemat blokowy systemu wizji robota zadań komputerowej wizji zawarte są zarówno w książkach jak i pracach oryginalnych. Określiło to jeden z celów tej książki. Autor chciał przedstawić istotne zagadnienia z dziedziny komputerowej wizji. Z jednej strony umożliwiają one łatwe wniknięcie w nowoczesny rozwój tej dziedziny, a z drugiej dają możliwie pełny obraz metod komputerowej wizji - co nie oznacza w żadnym razie dążenia do wyczerpującego przeglądu literatury. Tworzone przez człowieka modele systemów analizy i interpretacji informacji obrazowej oparte są na tym co wiadomo o systemie wzrokowym ludzi (HVS - Humań Visual System). Powtarza się ten sam schemat analizy: - wydzielanie lokalnych charakterystyk analizowanego obrazu czyli cech, - tworzenie opisu lokalnych fragmentów obrazu, - dopasowanie opisu do wzorców. Rozwój i postęp w tworzeniu systemów analizy i interpretacji obrazów jest bardzo duży. Możliwości systemów wydają się być imponu- I t Systemy komputerowej wizji w robotyce 9 jednak w porównaniu z systemem wzrokowym człowieka (HVS) j( określić jako znikome. Na wstępie bardzo skrótowo omówiono m wzrokowy człowieka. Następnie w pracy są rozpatrywane me- Łodj i algorytmy przetwarzania informacji w systemie komputerowej I 'roces komputerowego widzenia podzielony został na następu- i dnienia: i ( Hrzymywanie (akwizycję) obrazu, 2. Przetwarzanie wstępne obrazu cyfrowego, 3, Analizę obrazu, I Rozpoznawanie obrazu, W dalszej części pracy są one szczegółowo omawiane i zilustrowane kładami (przetwarzanymi obrazami). Rozdział 2 System wzrokowy człowieka 2.1 Wprowadzenie Zadaniem tego rozdziału jest zwięzłe i przystępne przedstawienie me- < linnizmu powstawania obrazów świata zewnętrznego postrzeganych przez człowieka. Nie ma żadnego znaczenia, czy światło pochodzi bez- • ilnio od źródła promieniowania, czy też jest częścią odbitą lub ? puszczoną przez oświetloną materię (Rysunek 2.1). riomieniowanie < Promieniowanie 4włetlne \ \ \ / odbite Promieniowanie " \ \ Promieniowanie pochłaniane f \ załamywane Promieniowanie rozproszone Promieniowanie przechodzące Rysunek 2.1: Przechodzenie promieniowania przez ośrodek fizyczny I 'rzedstawimy krótką charakterystykę systemu wzrokowego (wizu-llnego) i niektóre parametry wizualne rozpatrywane w różnych zasto-owaniach technik przetwarzania obrazów. Kompleksowe aspekty per-11 pcji wizualnej najlepiej wyjaśnić podając krótki opis systemu wzro-bowego (wizualnego) człowieka (HVS). Pod względem anatomicznym, //1 'S można podzielić na cztery elementy: gałkę oczną, nerw optyczny, 12 Rozdział 2^y?ęmwz1^^ ciała kolankowate boczne i część wzrokową kory mózgowej (Rysunek 2.2). Funkcja gałki ocznej jako układu optycznego jest analogiczna do funkcji aparatu fotograficznego, rejestrującego załamane promienie świetlne na światłoczułej powierzchni. Gałka oczna jest narządem, który przekazuje wrażenia wzrokowe do mózgu, gdzie są one analizowane i przetwarzane w jeden obraz. Oko ma za zadanie oglądanie, mózg natomiast decyduje o tym, co jest spostrzegane i jak rejestrowane. Warstwa połączeń synapsyc"iy<* Warstwa kowóre" flMalMafJBM>W** i ? v I FfVSY a) salka oczna, b) siatkówka, ł 1 Wprowadzenie 13 W powstawaniu wrażenia obrazu w mózgu mają udział: fizyczne ? i w ości promieniowania (Rysunek 2.3), zjawiska fizjologiczne za- • IHHI/^CC pod wpływem tego promieniowania w oku i układzie ner- iii oraz zjawiska natury psychologicznej zachodzące w mózgu. odbiera tylko część promieniowania nań padającego. Związane to z własnościami fizyko-chemicznymi rogówki, czopków i pręci- < )n iw.nl/rmr 17 Uktad zobrazowania E{A) Jk Współczynnik ttgljr uwzględniający R( X ) zjawiska absorpcji i odbicia Układ zobrazowania * r 9 * b SM) 1 I * Fi V\R( l") S2(A) * .S3U) 1 Rysunek 2.5: Model widzenia barwnego Impulsy elektryczne są silnie zależne od chwilowych zmian pa- iimetrów bodźców. Zmiana luminancji z 10^ do 11^ wydaje się iza jeżeli następuje w krótkim czasie, niż w przypadku, gdy czas j zmiany jest długi. Odpowiedzi na zmiany luminancji również ą natychmiastowe. Nawet jeżeli oglądana scena jest stacjonarna, ępuje ruch mięśni gałki ocznej. Ruch ten to małe oscylacje z 'otliwością około lO3^ i z amplitudą ok. 0.1° (Umiliradianów) i widzenia. Dla obiektów stacjonarnych ruch mięśni wprowadza podobnego do procedury przeplatania w telewizji. Plamka żółta obejmuje efektywny kąt widzenia wynoszący ok.l0°. Fotografia !) x \2cm widziana z odległości 40cm lub 26" ekran TV widziany z odległości 3m obejmują ok. 20° kąta widzenia. 18 Rozdział 2. System wzrokowy człowieka Rysunek 2.6: Zjawisko kontrastu równoczesnego luminancji W przetwarzaniu obrazów do opisu właściwości systemu wizyjnego, informacji w obrazie i charakterystyk urządzeń zobrazowania, stosujemy m.in. takie pojęcia bezpośrednio związane z fizjologią HVS jak luminancja, jaskrawość i kontrast. Luminancja określa energię emitowaną w kierunku obserwatora przez niekoherentne źródło światła na jednostkę czasu i powierzchni. Zmiana luminancji np. z 1^ do 2-^, w czasie lub przestrzeni, daje obserwatorowi iluzję, że wystąpiła większa zmiana niż w przypadku zmiany luminancji z 50^ do 51^. Obserwacja ta pozwoliła na sprecyzowanie definicji jaskrawości B nieliniowo zależnej od luminancji. Zależność ta określana jest przez prawo Webera-Fechnera B = lnL (2.1) W|n < wadzenie 19 BODZIEC ŚWIETLNY ILOSC ( CHROMATYCZNOŚĆ ) ( JASNOŚĆ ) IEŃ ) ( NASYCENIE ) Rysunek 2.7: Charakterystyka bodźca świetlnego / oznacza luminancję. Prawo Webera-Fechnera nie odzwierciedla efektu nasycenia przy (2.2) ? li luininancjach. Określając jaskrawość B jako / >' = arc sin hkL amy liniową zależność jaskrawości od luminancji w przy-ii gdy luminancja jest bliska zeru i zgodną z prawem Webera-inera dla dużych wartości luminancji. Kontrast jest stosowany przy określaniu różnicy w luminancji któw.Istnieje szereg definicji kontrastu np. (Rysunek 2.8) L+ A L l_+ AL i.bi AL Rysunek 2.8: Kontrast C = ^r c = L (L0b - Lt\a) _ AL tla Hla (2.3) 20 Rozdział 2. System wzrokowy człowieka Kontrast może być dodatni lub ujemny. Kontrast ujemny jest wtedy kiedy obiekt jest mniej oświetlony niż tło. Bardziej adekwatną definicją jest (Rysunek 2.9) tzw. kontrast Michelsona c = '-'max '-'min '-'mai. ' '-'min lub C = {Lob - Ltla) (Lot + Lt\a) (2.4) (2.5) Ł u m i n a n c i a '-""?'-",> Lmax+ '-min IAAAAAL:- Położenie Rysunek 2.9: Definicja kontrastu Michelsona Znak C określa przypadki: jasny obiekt - ciemne tło i czarny obiekt - jasne tło. Współczynnik czułości kontrastowej wskazuje na lokalne, przestrzenne i czasowe względne zmiany luminancji (Rysunek 2.10 i Rysunek 2.11). 2.2 Model systemu wzrokowego Kompletny model systemu wzrokowego (wizualnego) człowieka musi zawierać model oka, model traktu optycznego i model tzw. wizualnej części kory mózgowej. W chwili obecnej modele HVS znajdują się we wstępnej fazie rozwoju [14]. Model HVS można określić m.in. metodą Model systemu wzrokowego 21 I.+Al. ..?:,& L i ~m- *V*T? tog l iifk 2.10: Czułość kontrastowa. Ilustracja prawa Webera - Fechnera l. + Al. unek 2.11: Czułość kontrastowa dla oka które adaptuje się do LQ oinetryczną. Metoda ta polega na rejestracji reakcji typu "wy- 111 zmianę bodźca świetlnego", "bodziec na lewej połowie pola • nią" itp., grupy odpowiednio przygotowanych ludzi na sekwencję ? ów obrazowych. Zwykle bodźce obrazowe (Rysunek 2.12) opisy- wyrażeniem /(./:, y) = I0 + k cos[27r/0(:r cos q - y sin q)] i zęstotliwość przestrzenna, jaskrawość tła, kąt nachylenia linii luminancji bodźca świetlnego. (2.6) Wyniki tego typu doświadczeń pozwalają stwierdzić, że wykry- ilność bodźca dla dowolnych, ale ustalonych /o i q, zależy tylko od inku j- określonego mianem kontrastu, a nie oddzielnie od k i zułość systemu HVS zależy zarówno od /o jak i od q. Wartość określająca próg wykrywalności bodźca nazywana jest czułością iintrastową. Jest ona funkcją częstotliwości przestrzennych /o i Rysunek 2.12: Bodźce obrazowe wykorzystywane w metodach psychometrycznych (dla różnych kątów q) rośnie początkowo liniowo ze wzrostem /o, a następnie stosunkowo szybko maleje w zakresie dużych częstotliwości przestrzennych (Rysunek 2.13). Częstotliwości przestrzenne odpowiadające maksymalnej czułości obejmują zakres 3 s^ffi*ń "*" 4.5^^. Czułość zależy od q i jest maksymalna dla poziomych i pionowych linii luminancji bodźca świetlnego. HVS najbardziej czuły jest na zmiany bodźców w świetle zielonym, mniej w czerwonym, a najmniej w niebieskim. Receptory siatkówki oka, pręciki i czopki, reagują na pobudzenie nieliniowo. Charakterystykę przejścia HVS aproksymuje się wagowymi funkcjami logarytmicznymi lub funkcjami schodkowymi. W wyniku przeprowadzonych badań stwierdzono, że oko człowieka pracuje jak nieliniowy filtr (Rysunek 2.14a), który jest modelowany przez znane układy elektroniczne (Rysunek 2.14b). Inne doświadczenia m.in. przy wykorzystaniu bodźców obrazowych w postaci dwóch sygnałów sinusoidalnych o różnych częstotliwościach, pozwoliły na sformułowanie następującego wniosku: "HVS ma pewną liczbę równoległych mechanizmów wykrywania bodźców. Są to tzw. kanały przestrzenne nastrojone na różne częstotliwości przestrzenne i wykrywające bodźce o różnych kątach orientacji" (Rysunek 2.14c). Wyniki badań nad systemami HVS zostały dokładnie udokumentowane, można więc przyjąć, że prezentowany model HVS odpowiada rzeczywistemu systemowi (jest prawdziwy). Na tej podstawie przyjęto założenie, że system komputerowej wizji powinien posiadać strukturę analogiczna Model systemu wzrokowego 23 l 11 iikt my systemu wzrokowego człowieka. Czułość kontrastowa i Cykle na stopień Rysunek 2.13: Charakterystyka czułości HVS OTYCZWy SYSTEM OKA CHARAKTERYSTYKA KOMÓRKI LATERALNE •..u.*. SIATKÓWKI ' ' ' *WY FILTR m.cz. TRANSFORMACJA LOGARYTMICZNA FILTR Vi.CZ. ***M k-ty IKZeSTRZENNY KANAŁ T PROGOWANtE EXCLUSNE OR -J SZUM linek 2.14: Model systemu wizyjnego człowieka. Model analizatora widzenia model techniczny HVS (b) i mechanizm wykrywania bodźców (c) i Ku/dział 3 Akwizycja obrazu i I Wprowadzenie I i;ile tym przedstawimy przetworniki obrazowe optyczno - elek-nr wykorzystywane do uzyskania przebiegu elektrycznego odpo-i I.Kego rozkładowi świateł analizowanej sceny. Zostanie pokazany '•iiii/in rzutowania 3D obiektów na 2D obraz. Przedstawione zo-i metody uzyskiwania obrazu cyfrowego, a więc metody próbko-i i dyskretyzacji obrazu. Przetworniki obrazowe optyczno-elektryczne ne systemy receptorów czyli przetworniki obrazowe optyczno-l.ryczne oraz ich podstawowe charakterystyki przedstawiono w I .UH v 3.1. Przy wykorzystaniu przetworników obrazowych obraz obiektu '\ ) można otrzymać metodami bezpośrednim tj. takimi w których i nie znajduje się pomiędzy przetwornikiem a źródłem światła lub też metodami tzw. cieniowymi, w których obiekt położony jest i':dzy źródłem światła i przetwornikiem obrazowym (Rysunek Przy metodzie cieniowej obszar obrazu o dobrej jakości jest izy, niż przy metodzie bezpośredniej i znacznie słabiej zależny od etlenia obiektu. Przy metodzie bezpośredniej na jakość obrazu zny wpływ ma pojawienie się na powierzchni obiektu tzw. blików. I'izetwarzanie optoelektroniczne zachodzi w specyficznym dla każ-? rozwiązania przetwornika obrazowego elemencie, wykonanym z R0zdział3_J^Ś?li^^ 26 Tablica 3 /orników obrazowych elektro .1: Charakterystyki pewnych przetw optycznych 1'f/etworniki obrazowe optyczno-elektryczne 27 mej i światłoczułej. Na element światłoczuły rzutowany jest stru-iwietlny pochodzący od analizowanej sceny. Fotony tworzące ten I rumień po wniknięciu w głąb struktury materiału światłoczułego ;.ilują na elektrony jego atomów, oddając im energię. W wyniku •ddziaływań wystąpi zjawisko uwalniania nośników prądu z orbit ??.ii r/atomowych. Liczba nośników zależy od natężenia oświetle-Zjawisko to nosi nazwę efektu fotoelektrycznego, przy czym jeżeli uione nośniki prądu elektrycznego pozostają wewnątrz struktury MI I u światłoczułego to mamy do czynienia z efektem fotoelek-nytn wewnętrznym, lub w przypadku przeciwnym, z efektem fo-cznym zewnętrznym. Oba wymienione efekty znalazły zastoinę w przetwornikach obrazowych. TT TtmtttTTT a) cieniowe \m\ b) bezpośrednie Rysunek 3.1: Metody oświetlenia obiektów l"J hardziej znanym i rozpowszechnionym przetwornikiem ob- in jost telewizyjna lampa analizująca, najczęściej widikon, o uym odchylaniu i skupianiu wiązki elektronowej (Rysunek W |ej budowie można wyróżnić dwie zasadnicze części: sekcję ii sekcję wybierania. Pierwsza z nich zawiera element u lv, w którym zachodzi przetwarzanie optoelektroniczne ulacja fotoładunków. Sekcja wybierania formuje, skupia i >/.kę elektronową adresującą element światłoczuły. Wiązka mi :i się w próżni wewnątrz szklanej bańki. Budowa sekcji i u. i w zasadniczy sposób zależy od przyjętego sposobu 4P #* Rozdział^^Ś^-^^ rdworniki obrazowe optyczno-elektryczne 29 28 + 5oav -100V skupiania i odchylania wiązki wybierającej. Możemy więc spotkać lampy analizujące realizujące proces wybierania wyłącznie na drodze magnetycznej, wyłącznie na drodze elektrostatycznej lub też w sposób Bańka "•"'? \- i magnetyczny 7* -\ r~ CewW odchylające CewW skupiające C*wW korekcyjne Rysunek 3.2: Telewizyjna lampa analizująca (widikon) Wykorzystanie lamp analizujących pozwala na uzyskanie dużej ilości informacji obrazowej. Jednak ta zaleta lamp analizujących nie równoważy ich niedostatków, a w szczególności: - względnie dużych rozmiarów i masy lampy, - małej wytrzymałości mechanicznej, - znacznego poboru mocy, - konieczności stosowania wysokich napięć, - występowania zniekształceń geometrycznych obrazu, - bezwładności przetwarzania, - konieczności ekranowania magnetycznego i elektrycznego. Przedstawione wyżej uwarunkowania doprowadziły do powsta nia bezpróżniowych, monolitycznych przetworników obrazowych typi CID (ze wstrzykiwaniem ładunku) lub typu CTD (z przesuwem ła dunku). Wykorzystują one, w procesie przetwarzania, efekt fotoelel tryczny wewnętrzny. Uwolnione do struktury przetwornika foton* śniki są akumulowane w ściśle określonych obszarach, ograniczony raizanymi barierami potencjałowymi. Każdy taki obszar pojedynczy element przetwarzaj ąco-akumulujący pola świa-ii i może być traktowany jako kondensator o elementarnej W zależności od sposobu wytwarzania bariery potencjalna się kondensatory akumulująco-przetwarzjące złączowe Pi •??iworniki obrazu typu CID wyróżnia zastosowanie do ad-i powierzchni światłoczułej ortogonalnej macierzy X-Y. Ma-uoizy siatka przewodzących elektrod, krzyżujących się pod I prostym. Każdy węzeł macierzy odpowiada elementowi po-il światłoczułej i współpracuje dokładnie z jednym konden-o tu przetwarzająco-akumulującym (Rysunek 3.3). Adresowanie odbywa się przez jednoczesny zanik napięcia (do zera) na lodach aktualnie wybranego węzła. Powoduje to całkowitą i; ..studni" potencjałowej w tym węźle. W przypadku zaniku tylko na jednej elektrodzie węzła, nośniki przemieszczają się mi" pod drugą elektrodą. Uwolnione podczas adresowania wę-fntołudunki są wstrzykiwane do podłoża, a stamtąd dostają się do . /biorczej. "k yk f b) mmĄ ółprzewodnik samoistny typu n (n-Si) Studnia potencjałowa Półprzewodnik silnie domieszkowany (elektroda zbiorcza) + u. Rysunek 3.3: Węzeł macierzy adresującej przetwornika CID I '?" I stawowym problemem technicznym tego typu przetwornika ob-|est jego naświetlanie, ponieważ krzyżujące się wielopoziomowo rody węzła skutecznie przesłaniają fotoczułe złącza kondensato-MOS. Dlatego też w chwili obecnej stosowane jest rozwiązanie • -I i.iwione na Rysunku 3.4. Wielodiodowa struktura jest adreso- Rozdział 3. Akwizycja obrazu m GtOfTWtria systemu przetwornika obrazu 31 30 Kondensatory złączowe Ogniwo rejestru O Fazy przebiegu zegarowego af*1f* jKriJ Rysunek 3.6: Przetworniki obrazu typu CTD < i Geometria systemu przetwornika obrazu 111 ująć zagadnienie geometrii przetwornika obrazu nie musimy le- ii IWRĆ się znajomością szczegółów optyki i fotoelektroniki kamery. na jest tylko znajomość faktu, że soczewka kamery wyłapuje c światła przechodzące przez środek soczewki. Na Rysunku ? dstawiono schematycznie idealną kamerę gdzie l jest odległo- ibicktu od środka soczewki, natomiast / odległością pomiędzy ? ni soczewki i powierzchnią warstwy światłoczułej. Odległości ? powiązać za pomocą równania soczewki: "Ą-r wana przez macierz ortogonalną X-Y za pośrednictwem kluczy w postaci cienkowarstwowych tranzystorów MOS. Przetwornik tego typu ma większą czułość i lepsze właściwości spektralne od opisanego poprzednio. twomik obrazu typu MOS-XY Rysunek 3.4: Prze Przetworniki obrazu z przesuwem ładunku (CTD), wyróżnia sposób adresowania zakumulowanych fotoładunków, w którym zasadniczą rolę odgrywa pamięć analogowa. Stanowi ona najbardziej charak terystyczny podzespół przetwornika CTD. Każdej komórce pamięci przetwornika CTD jest przypisany jeden element przetwarzająco akumulującej struktury. Zgromadzony ładunek przemieszczany jest do odpowiadającej mu komórki pamięci. Wyjściowy prąd sygnału ob razu otrzymuje się odczytując sekwencyjnie całą pamięć przetworniki Przyjęty sposób odczytu umożliwia wykonanie pamięci w postaci re jestru przesuwającego. Jako element pamięci wykorzystuje się kon densator złączowy, sterowany tranzystorami FET. Pojedyncze ogniw rejestru tworzą dwa sąsiadujące ze sobą kondensatory i dwa sprzęga jące je tranzystory (jest to tzw. rejestr BBD, Rysunek 3.5). Elemen pamięci można wykonać całkowicie techniką MOS - w tym wypadki elementami pamięci są kondensatory MOS sterowane tranzystoram MOS - jest to rejestr typu CCD. Scalone przetworniki obrazu typu CTD są tworzone przez umies/ czenie obok siebie i na jednym podłożu określonej liczby analizatorów linii (Rysunek 3.6). Analiza obrazu najczęściej odbywa się wzdłuż lin pionowych. \viiując Rysunek 3.7 i Rysunek 3.8, zauważymy, że punkt wi- i • i u. i (> odpowiada środkowi soczewki, oś Z odpowiada optycznej osi płaszczyzna Z = f odpowiada powierzchni warstwy światło- i I Ma prostoty założymy, że / ma pewną ustaloną wartość. Jeżeli I ość / jest bardzo duża i znacznie większa niż ogniskowa soczewki l. jest zwykle w licznych zastosowaniach systemów komputero- Ai/ji), to równanie soczewki implikuje / ss F, i dla takiego przy- 'I odległość / jest często traktowana jak długość ogniskowej (jest t ała kamery). Innym układem współrzędnych, alternatywnym tadu przedstawionego na Rysunku 3.8, jest układ pokazany na liku 3.9. (X,Y,Z) Rysunek 3.9: Układ współrzędnych - płaszczyzna obrazu XY Punkt widzenia (0,0,-/) znajduje się w odległości / od płasz-ibrazu po ujemnej stronie osi Z. Równanie projekcji w tym i MI I ku ma postać f + z y = JOL. f + z (3.3) I-II układ współrzędnych jest bardzo przydatny gdy analizujemy 3D. W naturalny sposób można uzyskać ortograficzną ( lub l< .tą) projekcję przy założeniu / -> oo (Rysunek 3.10). Or- iliczna projekcja jest projekcją przez równoległe osie ortogonalne ??żyzny obrazu. Wtedy równania projekcji są dane przez x - Y. Taka projekcja daje bardzo dobrą aproksymację gdy obiekt miary porównywalne z długością ogniskowej, jest bardzo mały ? i "'łożony bardzo daleko od obserwatora, lub kiedy soczewka ma " dużą ogniskową. Przy przedstawianiu obrazu będziemy stosować następującą kon-|V układu współrzędnych: oś x będzie osią pionową, oś y będzie •fr ?$ % Rozdział 31A|wizyqą_obrazu Iffiwi reprezentacja obrazów 35 34 osią poziomą nych. Rysunek 3.10: Projekcja ortograficzna (Rysunek 3.U). Jest to prawoskrętny system współrzęd- K i ua K przedziałów, a jaskrawość każdego punktu jmuje wartość jednego z przedziałów. ? i Próbkowanie obrazu c, próbkowanie jest procesem przedstawienia ciągłego i i cą skończonego szeregu lub tablicy liczb zwanych prób- i próbek konieczna do odtworzenia obrazu jest łatwo okre-podstawie twierdzenia Whittakera - Kotielnikowa - Shan-W celu uzyskania zdyskretyzowanej postaci f(x, y) rozważali f(x,y) wykorzystujemy własność okresowego próbkowania ?inh( r, IJ) (Rysunek 3.12) (3.4) "'"''(''..'/) = 5Z X! $(x - ka,y- Ib) fc=-oo ł=-oo Rysunek 3.11: Układ współrzędnych xy obrazu 3.4 Cyfrowa reprezentacja obrazów Obrazy występujące w otaczającym nas świecie (obrazy naturalne) są obrazami ciągłymi, tj. mogą być rozpatrywane jako ciągła funkcja jaskrawości w zależności od położenia w przestrzeni obrazu. Sygnał pojawiający się na wyjściu przetwornika obrazu, np. kamery Tv, a re prezentujący obraz ciągły jest również ciągły. Cyfrowe przetwarzanie obrazu wymaga przetworzenia ciągłego sygnału obrazu do odpowiadającej mu postaci cyfrowej. Pierwszym etapem tej konwersji jest prób kowanie sygnału obrazu, w wyniku którego otrzymuje się M x JV wy miarową macierz punktów. Ponieważ jaskrawości tych punktów mogn mieć wartości ciągłe, następnym etapem jest kwantowanie. Dzielinn /i romb(x,y)f(x,y) = J^ Yl f{ka,lb)5(x-ka,y-lb) k=-oo l=-oo / [ka, Ib) = f(x, y)\x=ka natomiast a i b to odległości między y=lb ni próbkowania odpowiednio wzdłuż osi x i y. • ??linr ze wzorem (3.4) zdyskretyzowana funkcja / reprezen-i |"'st przez nieskończony zbiór funkcji delta Diraca o wyso-l'inporcjonalnych do f(ka,lb) rozmieszczonych w punktach Hi = Ib. Każdy punkt próbkowania może być traktowany lodek prostokątnego obszaru o wymiarach a x b zwanego komórką i i. Zbiór wszystkich komórek na płaszczyźnie xy tworzy lulkę próbkowania - raster. Próbkowanie za pomocą impulsów ? Diraca nosi nazwę próbkowania idealnego. Przy odtwarzaniu f{x,y) na podstawie jej postaci zdyskretyzowanej f(x,y) donu dwuwymiarowego przekształcenia Fouriera f(x,y)1 oo oo l[f(x,y)} = F{f(ka,lb) Yl E S(x-ka,y-lb)} = fe=-oo l=-oo oo oo = F{f(x,y)}(r)F{ ? ? 6(x-ka,y-lb)} = fe=-ool=-oo ni podrozdziale symbolem F będziemy oznaczali transformację Fouriera. Rozdział 3. Akwizycja obrazu 36 ? " 4 ( yfrowa reprezentacja obrazów 37 f(x.y) cowBru.vj= - v v j(u-k^,v-r-*) ' ab ~~ - *? "' /V Hm Model f(x,y) Próbkowanie comb(x.y) -(r) ? i(x.y) 4 comb(x.y) comb(x.yJ = ^ IJ fx-ka.y-/b) Sygnał Ciągły Spróbkowany \N dziedzinie przestrzennej (czasu) combfcy) = V Vj fx-ta.y./bj ? ? v ••dżinie częstotliwości (widma) F{u,v) i " * -• f ii U b Rysunek 3.12: Proces próbkowania Uliek 3.13: Próbkowanie. Sygnał w dziedzinie przestrzennej i dziedzinie częstotliwości. oo oo = ±-F{u,v)(r) E S ^ 0,0 fc=-Co!=-CO i oo oo i afefc^oo^oo u a 0 = (3.5) czyźnie częstotliwości w sposób regularny w punktach o ?,'ilnych u = -,v - oraz F(u,v) = F{/(^5y)} oraz F(u,v) = F{f(x,y)} Transformatę Fouriera funkcji comb(x, y) wyznaczamy na podsta wie twierdzenia o skalowaniu (Rysunek 3.13) 4"2 co co O? 2f COMB{u,v) = F{comb{x,y)} = \ ? ? <5(u-fc-,v-J-)(:ł' fc=-oo (=-oo oo co ki fc=-oo(=-co (3.1 Jeżeli transformacja Fouriera funkcji f{x,y) F(u,v) 6y I (u.v) F(u,v) to widmo funkcji f(x,y) przedstawia nieskończony zbiór po wtórzeń widma funkcji f(x,y) (Rysunek 3.14) rozmieszczonycli unek 3.14: Zwielokrotnione widmo F(u,v) funkcji f(x,y) A Rozdział 3. Akwizycja obrazu i I /linwa reprezentacja obrazów 39 38 "" f- V fika Ib) Binc[2A(x - ka)\ "nc[2B(v - " rS.13. Jai 7=0 Jdi Transformata Fouriera F(u, v) jest różna od zera tylko w skończonym obszarze R płaszczyzny częstotliwości przestrzennych v y 0 w przypadku przeciwnym v Niech prostokąt o bokach 2A i 2B odpowiednio w kierunku osi u i v będzie najmniejszym prostokątem, w którym całkowicie zawiera się obszar R. Jeżeli kopie F(u - |, v - ?) nie zachodzą na siebie, to wykonując odwrotne przekształcenie Fouriera, można odtworzyć funkcję pierwotną f(x,y). W celu otrzymania F{u,v) należy z transformaty Fouriera F{u, v) usunąć wszystkie składniki F(u--, v-|) z wyjątkiem składnika z indeksami fe = 0 i l - 0. Operację taką można zrealizować mnożąc transformatę F(u,v) przez funkcję nitrującą H{u,v) mającą postać dwuwymiarowej funkcji prostokątnej H("łt,) = rect(|i,^) (3.9) Tak więc, transformatę Fouriera F(u,v) możemy wyrazić jako iloczyn F{u,v)=T{u,v)rect{±,~) (3.10) Wykonując odwrotne przekształcenie Fouriera obu stron równości (3.10) i stosując twierdzenie o splocie otrzymujemy funkcję pierwotną /(x, y) = [comb{a, b)f{x, y)) * h(x, y) (3.11) gdzie * oznacza operację splotu h[x, y) = F~lH{u, v) = 2A 2B sinc{2Ax) sinc{2By) (3.12) Uwzględniając definicję funkcji comb oraz właściwości próbkowa nia i filtracji funkcji delta Diraca, możemy wzór (3.11) przedstawić w postaci (3.13: Funkcja f(x, y), która ma ograniczone widmo, tzn. jej transformat Fouriera jest różna od zera tylko w skończonym obszarze płaszczyzn\ • i przestrzennych, może być odtworzona z całkowitą dokładno-i i >< >dstawie nieskończonego, dyskretnego zbioru jej próbek. W wistości mamy skończoną liczbę próbek co sprawia, że wartości i f{x,y) w punktach pośrednich mogą być odtworzone tylko z i < U >kładnością. W praktyce nie mamy również do czynienia z ide- • "Irmentami próbkującymi w postaci dwuwymiarowych funkcji ' liraca, gdyż nie są one praktycznie realizowalne. I 4.2 Kwantowanie obrazu ? iwanie obrazu polega na tym, że zakres wartości próbek repre- i. ych obraz dzielony jest na przedziały oraz że wszystkie war- |>róbek wewnątrz przedziału są reprezentowane przez pojedyn- poziom (Rysunek 3.15). Kwantowanie może być przeprowadzone lub zmiennym skokiem kwantowania. Niech / i / reprezen- inplitudy rzeczywistego skalarnego sygnału próbki i jego wartości iowanej. / jest próbką procesu o znanej gęstości prawdopodo- i p(f). Inaczej mówiąc / należy do przedziału 0| < / < au (3.14) ic (a i au reprezentują dolną i górną granicę przedziału kwan-iiiin. Problem kwantowania wymaga określenia zbioru poziomów decyli ^/j i zbioru poziomów odtwarzania r^, takich, że jeżeli 4 < / < dj+1 (3.15) |)n')bka jest skwantowana do wartości poziomu odtwarzania Tj. Rysunek 3.16 ilustruje położenie poziomów decyzyjnych i odtwa- i dla J poziomów kwantowania. Poziomy decyzyjne i odtwarzania brane tak, by minimalizować błąd kwantowania między / i /. '? poziomów kwantowania średniokwadratowy błąd kwantowania I "l,i dużej liczby poziomów kwantowania J, gęstość prawdopodo-i może być wyrażona za pomocą stałej dla każdego przedziału i 'ślony wzorem 40 Rozdział 3. Akwizycja obrazu '. ."__ M Poziomy wyjściowe tniisnii Poziomy wejściowe Rysunek 3.15: Proces kwantowania kwantowania wartości p(rj). Mamy więc Jdj (3.17) który zdąża do wartości J-I ^iEpWfe-o)4-(dr^] j=0 (3.18 Poziom odtwarzania Tj dla zakresu od dj-i do dj może być okr< ślony drogą minimalizacji średniokwadratowego błędu kwantowania tj- de drj i stąd = 0 (3.W _ ai+l + d< ł 4 Cyfrowa reprezentacja obrazów 41 d.d d. d d J-1, J "o "i d2 i . i . i . i I , I , I , I Vt t t t t t t t t t t I t t t t t t1'. Wi J-1 r0 r1 r2 Syg. wyjściowy l 'LIZ ~ d,i n fi pt,ymalny wybór poziomu decyzyjnego można przeprowadzić malizując e określony przez (3.21) metodą mnożników Lagrange'a. Poziom decyzyjny może być obliczony na podstawie [1,10], jak . K-a<)C[p(/)]-^/ CW/)]-*4f (3.22) "/ = j(au - aj) J + cn (3.23) ; eO,l,...J. Rozdiiąi3_3^^^ Jeżeli liczba poziomów kwantowania jest mała, wtedy na podstawie (3.16) i (3.19) mamy 1=2p+1(/-r3)p(/W = stąd -?- = (d, - rtfpid,) - (Ą - rj_1)2p(d3) = 0 (3.24) (3.25) ii Sr, = 0 (3.26) 4T1 M/)# Rekurencyjne rozwiązanie tych równań dla danej gęstości prawdopodobieństwa p(f) prowadzi do otrzymania optymalnych wartości poziomów decyzyjnych i odtwarzania. Średniokwadratowy błąd kwantowania określony jest przez (3.27) ^E(n-%^ Czna reprezentacja obrazu cyfrowego 3.4.3 Matematyczna rep ^ ^ byc Obraz cycowy, * obrazf Pakowani opisany przez macierz (Rys- ^ W = Jłd ' : tvm wierszu i J-te] " • ".5 fnnkcii obrazu w i-tym ,. f sa wartościami iunKcji gdzie ho sa- w B dzie B jest kolumnie. x M _ j . 1...N oraz /" < Oczywiście Jij * u pewną stałą- i'>w.i reprezentacja obrazów 43 2 poziomowy układ kwantowania i i>it/plxel tibftz binarny Poziomy wejściowe Poziomy decyzyjne Poziomy odtwarzania Poziomy wyjściowa 8 bit/pixel Rysunek 3.17: Proces kwantowania i tlnaz posiada skończoną energię M N i=l 3=1 (3.30) Obraz cyfrowy może być również przedstawiony w postaci i i "i,i-kolumny lub wektor a-wiersza. Wektor-kolumna wymiaru 1 x \ jest definiowany jako f = [f\f2,...,fMf jdzie f1 = [/(*, 1),/(ż, 2),...,/(Ż,JV)]< Wektor (3.31) możemy zapisać, (3.31) (3.32) N n=l (3.33) dział 3 Akwizycja obrazu H Cyfrowa reprezentacja obrazów 45 [T]= fU ° < ' < M , ° < / < w N-1 I) M \ 0 1 2 w *s ; r 94 100 104 119 12 5 136 143 153 157 158 103 104 106 96 103 119 141 155 155 160 10! 136 136 123 li 78 117 149 155 160 110 130 144 149 12 8 78 97 151 161 158 109 137 178 167 11S 78 101 185 193 161 100 143 167 134 37 35 13 4 216 209 172 104 123 166 161 155 160 20 5 229 219 181 125 131 172 179 190 208 233 237 223 200 131 14 S 172 175 199 228 Ul 238 229 2G6 161 16$ 162 163 193 228 230 237 220 199 b) Itysunek 3.19: Obraz cyfrowy: a) macierz; b) wartości jaskrawości. • 1 v 8 bitów/element obrazu, b) 1 Rysunek 3.18: Obraz K'""*^^t^MU. d) 4 bity/element obrazu, e) 6 | ^ x M _ wymiarową macierzą; dla której y^fa podmacierz l W wierszy, 0 0 bit/element obrazu, c) W,^^ obrazu. gdzie (3.35) (3.34! [Nn] = 46 Rozdział 3. Akwizycja obrazu jest N x 1 - wymiarowym wektorem z jednym niezerowym elementem. Odwrotna operacja l/l - ? KH (3-36) n=l Oczywiście element macierzy o współrzędnych i, j, tj'. /y jest ele mentem wektora o numerze (i - l)N + j, tj. f(i-i)N+j = fi,j (3-37 gdzie i = 1...M, j = I....N. Ko/dział 4 Przetwarzanie wstępne obrazu cyfrowego icje wstępnego przetwarzania obrazów można podzielić na (Ry- I 1.1): racje przetwarzania pojedynczych punktów obrazu, .uje wykorzystujące w procesie przetwarzania grupy punktów obrazu. i k) pierwszej grupy zaliczamy operacje związane z modyfikacjami i nu, natomiast do drugiej operacje związane z wydzielaniem n |;iskrawości i różnego rodzaju filtracją obrazu. Histogram obrazu i jego modyfikacje i.un obrazu h(k) przedstawia sobą zależność liczby elementów od wartości poziomu jaskrawości k. Niech h : 0,1,...K -? Z nituje histogram obrazu [/], gdzie h(k) jest liczbą elementów posiadających jaskrawość k, gdzie 0 < k < K i Z jest zbio- ujemnych liczb całkowitych. Rysunek 4.2 przedstawia obrazy i i ich histogramy. I linti igramy obrazu wykorzystane są do określania wartości pro- iskrawości obrazu. Określenie wartości progowej jaskrawości • liwia zakwalifikowanie elementów obrazu do dwóch klas: klasy óo i litów obrazu tworzących tło i klasy 5\ elementów obrazu należą-h do obiektu, przy czym zakładamy, że rozkład poziomów jaskra- i w każdej klasie jest rozkładem gaussowskim (Rysunek 4.3a). W przypadku idealnym, w którym zakładamy, że: 48 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego I I łistogram obrazu i jego modyfikacje 49 (4.1) 9i.i= T M5i ~ wartości średnie rozkładów, °"<5o i a$i ' odchylenia standardowe rozkładów, Ps0, P^ - prawdopodobieństwo a'priori pixeli tła i obiektu. 2 aóo - crSl P50 W przypadku Ps1 = Ps0 lub jeśli a = 0 wtedy (4.3) (4.4) 50 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego (i-DN+j a) l>|W | -*? 255 l V ••"••?•I ^* 255 b) Rysunek 4.3: Określenie wartości progowej jaskrawości: a) Klasyfikacja elementów obrazu do dwóch klas, b) Rozkład poziomów jaskrawości - w klasie <5o poziom " 1", w klasie 5j poziom " 2" Jeżeli obraz zawiera pewną liczbę obszarów, jednorodnych pod względem jaskrawości elementów, tj. takich obszarów dla których rozkład prawdopodobieństwa jaskrawości jest unimodalny, to na histogramie powinny odpowiadać im międzymodowe minima w przedziałach których wybiera się wartości progowe jaskrawości. Wartością progową t funkcji jaskrawości obrazu nazywamy wartość jaskrawości określającą położenie pierwszego minimum histogramu h, większą od wartości jaskrawości określającej położenie maksimum histogramu. Granice pomiędzy poszczególnymi obszarami muszą być wyraźne tzn. istnieje ostry skok jaskrawości pomiędzy jaskrawościami elementów poszczególnych obszarów obrazu. Opierając się na fakcie, że miarą jednorodności elementów należących do odpowiedniej klasy jest wariancja, Otsu [73] zaproponował i I Histogram obrazu i jego modyfikacje 51 BWtodę wyboru wartości progowej takiej, która minimalizuje wariancję wewnątrz klas. /normalizowany histogram *-<*>' JHTN (4'5) |est analogiem funkcji gęstości prawdopodobieństwa w statystyce I może być traktowany jak prawdopodobieństwo elementu obrazu o i iści k. W tym przypadku ?>nor(A;) = l (4.6) k I Ha wartości progowej t mamy (qs0(t) + %(*) = 1) nor{K) fc=:1 1 >? I powiędnie wariancje definiujemy jako F3 r TTA = Z~uS Z> - PSo) hnor(h) (4.12) 2^k=l ""n-or\l^) H5O\L) fe=i 52 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego K <(t) = Sfc=t^ ^\yfc) = Z7AT. (* - ^)27w(*0(4.13) %(*) fe= fe=t+l Z-ife=t+l hnorik) K a2 = 52(ż-iLł)2/inor(fc). Mamy (4.14) gdzie afv(t) jest wariancją wewnątrz klas, natomiast Z reprezentuje histogram tdientu, gdzie h\(k) jest sumą wartości gradientu dla wszystkich (4.17) (4.18) i u'iitów obrazu mających wartość jaskrawości k hX{k) (r,c)€/(fc) r(fc) = {(r,c):/r,c = fe} < Iradient w przypadku obrazu analogowego f(x,y) jest wektorem, ngo moduł jest określony przez wyrażenie [{? $x )2 + ( $yV )2]^ ? < ibrazu cyfrowego pochodne aproksymowane są przez różnice ja-.vości wzdłuż odpowiednich współrzędnych np. dTfi = [(/rjC - • t i)2 + (/r+i,c -/r,c+i)2]3 ? Na Rysunku 4.5 przedstawiono możliwe padki zmiany jaskrawości elementów obrazu f(x,y)w pobliżu gra- bszarów oraz pochodne ?- i jĄ dla przypadku jednowymiarowego. W takich przypadkach optymalną wartością progową jaskrawości bę-poziom t\ dla którego h\(k) jest maksymalne. Wartość progowa iawości ti odpowiada punktom o największej wartości gradientu, ięc znajduje się na granicy między obiektem a tłem. t(x) y" const M(x) hx ft'*(x) lx Kysunek 4.5: Zmiana jaskrawości elementów obrazu f{x,y) w pobliżu granic obszarów Jeżeli M x N jest liczbą elementów obrazu, dla którego obliczany i' i histogram, to łatwo zauważyć, że: ? h{k) = M xN fc=0 (4.19) 54 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Dla dwóch obrazów (lub obszarów obrazu), możemy utworzyć dwuwymiarową tablicę h(v,u), określającą liczbę elementów przyjmujących wartości jaskrawości odpowiednio v w pierwszym obrazie i u w drugim. Jest to tzw. dwuwymiarowy histogram (Rysunek 4.6). poziomy jaskrawości obraz 1 2 0 1 1 0 5 5 1 2 2 1 5 7 7 5 5 1 2 6 6 0 7 10 10 7 1 2 6 6 2 2 7 10 10 7 2 6 6 2 1 0 5 7 7 5 6 6 2 1 5 obraz 1 obraz 2 o r a z 1 2 3 4 5 6 0 1 1 0 0 1 1 1 1 1 0 0 1 0 2 0 1 0 0 1 0 5 1 0 0 0 1 2 7 2 4 0 0 0 2 10 0 1 0 0 0 3 Rysunek 4.6: Zasada tworzenia dwuwymiarowego histogramu obrazu Niech M(/) będzie funkcją określającą zawartość informacji obrazowej w obrazie daną przez K Af(/) = ?>(*;)-max Ji(fc) (4.20) fc=0 Jeżeli t\i,j?Rfi,j ~ const, to M(/) = 0. Jeżeli A/CCGM^) = const, to M(/) = max i wtedy Af (/) - IgJJ. M(/) przyjmuje wartości bliskie minimalnej dla obrazów zawierających mało informacji, natomiast wartości bliskie maksymalnej dla obrazów zawierających dużo informacji obrazowych. Na Rysunku 4.7 przedstawiono obrazy binarne obrazów z Rysunku 4.2 uzyskane przy różnych wartościach progowych jaskrawości. 4.2 Transformacja skali jaskrawości obrazu Transformacja skali jaskrawości elementów obrazu umożliwia: - w przypadku, gdy zakres jaskrawości nie obejmuje całej skali dostępnej dla obrazu, rozciągnięcie tego zakresu (efekt zwiększenia kontrastu), Transformacja skali jaskrawości obrazu 55 c) d) imek 4.7: Obrazy binarne (obrazów z Rysunku 4.2) dla różnych wartości -owych jaskrawości: a) i b) dla wartości progowej 100, c) i d) dla wartości ? >wych wyznaczonych wg metody Otsu wynoszących odpowiednio 146 i 130 uwypuklenie pewnych zakresów jaskrawości i stłumienie innych, modyfikację jaskrawości elementów obrazu w celu uzyskania równomiernej częstotliwości występowania odpowiednich poziomów jaskrawości. Inuisformacja skali jaskrawości elementów obrazu może być zre- uana różnymi metodami. W najprostszym przypadku przeskalo- v można zrealizować przez podział zakresu jaskrawości np. odrzu- naj mniej znaczące bity. Jednak uzyskany w ten sposób obraz Ir nie jest zadowalający. Niech fcout = T(km) (4.21) 9U = TUiJ) (4-22) ; :ie: element obrazu wejściowego, Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego gij - element obrazu po transformacji, kont ~ poziom jaskrawości obrazu po transformacji, kin ~ poziom jaskrawości obrazu wejściowego, T - operator transformacji. Transformacje skali jaskrawości obrazu przedstawia Rysunek 4.8. ? *o* = T(kin) m1 out m a b) Rysunek 4.8: Transformacja skali jaskrawości obrazu: a) wielopoziomowa i b)dwupoziomowa Mamy fcout - 1 {Kin) ula femjn ^ fcjn ^ rCmax 1 fcmin ^ ^out ^ rCmax- Jeżeli a < k = /"j < 6 dla wszystkich i,j oraz [a,b] jest podprze-działem [kmin, kmax] , wtedy jaskrawość po transformacji wyraża się wzorem k> = b - a h - h a \K a) + kmin - n , "smaż(r) ^min(r) b - a (4.23) Transformacja powyższa rozszerza skalę jaskrawości do zakresu [*mini (tm)max\- W praktyce transformacja ^ = T(kin) może być transformacją kwadratową, logarytmiczną, wykładniczą itp. (Rysunek 4.9). Omówimy krótko pewne metody realizacji transformacji skali jaskrawości elementów obrazu. Transformacja skali jaskrawości obrazu 57 Negacja 14-1 I kouł m Pierwiastek / / j X n-tego stopnia / i Logarytm >\ / i / Potęg/ - i / X rhte90 I i / / \ stopnia I / / / / \ / i / ' / / / / "-- Odwrotność Jogarytmu Identyczność \ " m NT2 SN/4 H-1 Wejściowy1poziom jaskrawości k in Rysunek 4.9: Transformacja jaskrawości elementów obrazu 4.2.1 Metoda liniowego dopasowania jaskrawości i >ści jaskrawości kin elementów obrazu wejściowego są transfor-ni(! do wartości fcmt (Rysunek 4.10) <=u i P^f p -*=T^T 9/ 1 a 1 1 a b km l<\ imek 4.10: Liniowa transformacja skali jaskrawości elementów obrazu /•?,",/ = l q{kin -a)+o> . p(kin -b)+/3 0 < kin < CL a < kin < & o C kin ^ -Li (4.24) ?•: q,g,p są współczynnikami określającymi kontrast, nato-i M 0 stałymi sterującymi jaskrawością. jalne przypadki transformacji (4.24) otrzymujemy dla q = p = i \\ obcinanie poziomów jaskrawości), przy czym jeżeli dodatkowo 58 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Rysunek 4.11: Liniowa transformacja jaskrawości obrazu a = /3 = thr (wartości progowej jaskrawości), to mówimy o progowa-niu. 75:8 IM' \J \ ' " \ \ !8d \ \ s 150 s S 126 s 90 ^> 60 s 1 •" 30 ± s s j ' *. ~r s • 30 60 90 120 150 '80 2W 240 ZS5' 24000 22000 20 088 '8000 16860 1400C 12 ODO 10088 8066 | 6080 4888 2080 0 Lm JLI 0 50 106 1S8 288 250 Rysunek 4.12: Liniowa transformacja jaskrawości obrazu - negacja 4.2.2 Metoda transformacji logarytmicznej Logarytmiczna transformacja jaskrawości elementów obrazu jest określona formułą kout - Ig ("'i (4.25) Do (4.25) można wprowadzić tzw. parametr skalujący a, umożliwiający wybór części krzywej logarytmicznej. Wtedy i^mi.t lg(l + (exp(a) - l)h a (4.26) Transformacja skali jaskrawości obrazu 59 150 W 25B Rysunek 4.13: Logarytmiczna transformacja jaskrawości obrazu Xli m 210 189 12B 90 60 33 °8 1 f / ' ^ 30 SD 30 120 130 180 210 2"0 255 nm "1 60 BOB 50006 40 ODO 30000 20000 mon 0 50 <00 "0 200 2SS Rysunek 4.14: Transformacja jaskrawości obrazu - odwrotność logarytmu 4.2.3 Metoda transformacji wykładniczej h I to transformacja odwrotna do logarytmicznej. Mamy fcout = exp(A;in) (4.27) I •okonując parametryzacji otrzymujemy [1 + a)k(tm) - 1 "rmt a (4.28) I i '"arytmiczną i wykładniczą transformację jaskrawości elementów u przedstawia Rysunek 4.9. 4.2.4 Metoda modyfikacji histogramu nhraz wejściowy ma histogram h(kin) i realizujemy transforma-/ aa)** ~*,2 :"HHH| ? t U i Tlft *~ .: 2W - 1 ?< t l. '* ićnF 1 : Z |!j 1SB i^ifl Z B tt, .j- *"'???' GO , _-*==" " a a 9 ta ,50 180 J.0 MO255 Mson 12300B was 93000 i ?':::::: 93893 40000 23500 5- hi 9 "B 19 JOO :;. li) Rysunek 4.15: Wykładnicza transformacja jaskrawości a) kwadratowa, b) sześcienna. ula Kout = i \fcin)- Możemy zapisać, że Ci{kout) =c0{kin) (4.30) gdzie Ci , c0 są np. liczbami elementów o wartościach mniejszych, równych odpowiednio od k^t i kin , czyli (Rysunek 4.18) kont = c^icoikin)) (4.31) ? inek 4.16: Transformacja jaskrawości obrazu a) pierwiastek kwadratowy, b) pierwiastek sześcienny. Ilysunek 4.17: Transformacja jaskrawości obrazu - wyrównywanie histogramu 4.2.5 Zmodyfikowane transformacje: logarytmiczna i wykładnicza (4.32) (4.33) Transformacje te określają odpowiednio wyrażenia lg(l + (exp(a) - l))c(kin) b h - 1 + a)c{kin) - 1 k 4.3 Filtracja obrazu owy system przetwarzania obrazu można opisać za pomocą pew-i operatora matematycznego L , który transformuje wejściowy ob-! f(k, l)} w wyjściowy obraz {y(k, l)} (Rysunek 4.19) y(k,l) = L[{f(k,l)}}. (4.34) System nazywany jest liniowym, jeżeli przekształca liniową kom-blnację dowolnych sygnałów wejściowych w liniową kombinację odpo- 62 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego k",= T(kJ Rysunek 4.18: Modyfikacja histogramu jaskrawości f(k,l) y(k,D. Rysunek 4.19: System przetwarzania sygnałów władających im sygnałów wyjściowych. L[af(k, l) + bz{k, l)} = aL[f(k, l)} + bL[z(k, l)] (4.35) Możemy zapisać oo oo /(M) = Y Y f(m,n)S(k-m,l-n) m=-oo n=-oo (4.36) oo oo y(k,l) = L[ Y Y f(m,n)S(k-m,l-n)] m=-oo n=-oo (4.37) gdzie S(k, 0 = 1 dla k + l = 0 ó(k, 0 = 0 dla k + 1^0 (4.38) Na podstawie własności liniowości operator L można wprowadzić pod znak sumy otrzymując Filtracja obrazu 63 oo oo V(k,l)= E E f(m,n)L[6(k-m,l-n)} = m=-oo n=-oo oo oo = E E f(m,n)h(k,l,m,n) (4.39) m=-oo n=-oo gdzie h(k,l,m,n) jest odpowiedzią systemu na sygnał 5(k,l) . leżeli układ jest niezmienniczy względem przesunięcia sygnału w /czyźnie wejściowej to h(k, l, m, n) = h(k - m,l - n) (4.40) Możemy więc zapisać oo oo ?(M)= E E f(m,ń)h(m-k,n-l) (4.41) m=-oo ra=-oo co oznacza, że sygnał wyjściowy jest splotem sygnału wejściowego "dpowiedzią impulsową układu (y(M)} = {/(M)}*{MM)} (4.42) idzie * oznacza operację splotu. Dokonując zamiany zmiennych, otrzymujemy oo oo V(k,l)= E E h(k,l)f(k-m,l-n) (4.43) m=-oo n=-oo Realizując transformację Fouriera obu stron (4.41) i stosując twier-iie o splocie mamy Y(wfc, m) = F(uk, ui)H(ufe, ui) (4.44) gdzie Y, F, H są dwuwymiarowymi transformatorami Fouriera mlpowiednio sygnałów wyjściowego, wejściowego i odpowiedzi impul-KWej. Ponieważ w zależności od charakterystyki amplitudowej układu liniowego określonej modułem funkcji przenoszenia, pewne składowe li.u nioniczne mogą być w mniejszym lub większym stopniu wytłumione, układy liniowe wykazują własność filtracji widma sygnału i ftazywane są filtrami (Rysunek 4.20 i Rysunek 4.21). 64 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Fittr dolnopizepu stówy Filtr górnoprzepustowy i-i -i LP HP: Rysunek 4.20: Odpowiedzi impulsowe filtrów dolno- i górnoprzepustowych Liniowe przestrzennie niezmiennicze filtry mogą być definiowane przez równanie różnicowe typu y% l) = J2Y, a(m> n)f(k -m,i-n)- Si Si J2 H 6(m' n)y(k -m,i-n) Ri Ri (4.45) gdzie {f(k,l)} obraz wejściowy; {y(k, l)} obraz wyjściowy; {a(m, n)}, {6(m,n)} - są współczynnikami macierzy definiującej filtr, natomiast Ą , Ą oznaczają odpowiednio pewne zbiory, różne dla różnych klas filtrów. Pierwszą ważną klasę filtrów otrzymujemy, gdy Ą jest definiowane jak zbiór 0 < m < M - 1, 0 < ra < TV - 1 i Ą jest zbiorem pustym. Wyrażenie (4.45) redukuje się do M-1N-1 m=0 n=0 (4.46) i określa klasy filtrów o skończonej odpowiedzi impulsowej tzw. FIR. Filtracja obrazu 65 Obraz oryginalny Obraz po filtracji dolnoprzepustowej Obraz po filtracji górnoprzepustowej Obraz po filtracji filtrem pasmowym Rysunek 4.21: Wyniki filtracji dolno- górno- i pasmowoprzepustowej |i żeli R\ nie jest zbiorem pustym, i spełnione są następujące warunki: y(k, 10 = 0 dla k<0 i/lub l < 0 /(fe,0 = 0 dla k<0 i/lub l<0 to M-lN-l 2/(fc> 0=EE a(m' n^^k -(tm),l-n)- m=0 n=0 K-l L-l J2 ? 6Kn)y(k -m,l-n) (4.47) m=0 n=0 Relacja ta przedstawiona jest graficznie na Rysunku 4.22. 4.3.1 Filtry adaptacyjne I >( i wygładzania obrazu można zastosować filtr Kalmana. Jeżeli cy-Imwy obraz jest określony przez (3.29), to może być opisany przez liniowy zbiór równań Fi,k = Xi? + e^fc Xi,k = A,kX(i, k-l) + U^k (4.48) (4.49) 66 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Obraz wejściowy 1 Obraz wyjściowy 1 obszar obrazu z nieznanymi punktami Rysunek 4.22: Zasada filtracji FIR gdzie e^k ~ szum, E[ei,kći,j] - R$k,j, Aitk - macierz określająca zależność pomiędzy sąsiednimi częściami obrazu (transition matrix), U^k ~ wejściowa sekwencja (której wartości są zawsze równe zeru z wyjątkiem tych punktów, dla których istnieją kontury obszarów), i przedstawiony następująco Fi,k - AitkXifk- L + Uitk + &i,k - Aitk{F^k-i - egfc-i) + uitk + e^fc Jeżeli wektor - AWT -, Ai,k ea = L ni,k J l2x (4.50) (4.51) jest wektorem parametrów, gdzie A\fi jest j-tym wektorem wierszowym macierzy Ąfc, a Ci,k = *?_, - ąk (4-52) •I < Filtracja obrazu 67 i macierz Ci,* 0 0 C,k 0 o (4.53) 0 0 ... ClJt wtedy równanie (4.48) możemy zapisać w postaci Fi,k - Zitk&i,k + Uitk + &i,k (4.54) < >/ k można zapisać jak (c)/,* = (c)/,*-! + Wfc (4.55) gdzie wfc jest szumem gaussowskim o zerowej średniej, z macierzą kowariancji W. Kownanie (4.54) jest nazywane równaniem obserwacji, natomiast 15) jest równaniem stanu. Do oszacowania wektora 0^ można wykorzystać filtr Kalmana. • Mrzymujemy Kl,k ~ Pl,kZl,k{ZitkPl,k-\Zi,k + R) (4.56) Qi,k = 0/,*-i + Ki,k(Fi,k ~~ Zlk@i,k-i) Plik = (/ - K^Zltk)Pi,k~i + W (4.57) (4.58) Z macierzy Zitk+i w następnym kroku otrzymujemy oszacowanie ei,k - Fi,k ~ Zitk&i,k (4.59) Do realizacji przedstawionego powyżej filtru wymagana jest tylko jomość a'priori macierzy R i W. 68 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego 4.3.2 Filtry wygładzające Zakłócenia (szumy) występują jako rozpoznawane zmiany izolowanych elementów obrazu. Jest to zjawisko groźne w systemach komputerowej wizji m.in. dlatego, że powoduje rozmycie linii konturowych obiektów, co może prowadzić do błędnej identyfikacji obiektów. Istnieją różne metody walki z zakłóceniami. Przy znanej charakterystyce widmowej zakłócenia, optymalne są winerowskie filtry i ich różne modyfikacje. Jednak w praktyce nie są znane modele procesów zakłóceń i przy realizacji klasycznych metod filtracji napotykamy na różne trudności np. bardzo duże ilości obliczeń. Rozpowszechnione są za to stosunkowo proste metody eliminacji zakłóceń oparte na uśrednianiu i operacjach logicznych. Jedną z bardziej popularnych metod filtracji jest metoda wygładzania (realizująca filtrację małej częstotliwości). Wygładzony obraz realizuje się w postaci splotu obrazu wejściowego z maską określonego wymiaru. W odróżnieniu od masek wykorzystywanych w procesie wydzielania zmian jaskrawości, maski wygładzające zawierają wyłącznie dodatnie elementy np. 111 1 1 1 1 1 1 1 1 1 1 2 1 9 1 1 1 10 1 1 1 16 12 1" 2 4 2. 12 1 Operacja wygładzenia może być realizowana różnymi sposobami. Przede wszystkim - przez bezpośrednie obliczanie splotu obrazu wejściowego z maską, tj. Ftj = (F * H)ij gdzie F i F są odpowiednio obrazami wejściowym i wygładzonym, natomiast H - maską wygładzającą. Przy dużych wymiarach masek obliczenie splotu wygodnie jest realizować za pomocą szybkiej transformacji Fouriera. Zauważmy, że przy wydzielaniu zmian jaskrawości za pomocą maski H, odpowiadającej oknu 8 w obrazie wejściowym, jaskrawość obrazu w punktach, które nie mogą być środkiem 9 (ponieważ okno wyjdzie za przedział rastru) przyjmuje się równe zeru. W przypadku filtracji zakłóceń metodą wygładzania - jaskrawość w takich punktach jest równa jaskrawości tych punktów w obrazie wejściowym. Jeżeli w obrazie występują tzw. zakłócenia lokalne, wywołane np. tzw. blikami itp., to sposoby eliminacji zakłóceń opisane wyżej, nie są skuteczne i nie zapewniają ich eliminacji. Zauważymy, że losowe skoki jaskrawości w obrazie można rozpatrywać jako zakłócenia lokalne. W [42],[12] pokazano, że w wyniku filtracji małej częstotliwości zakłócenia lokalne zmniejszają się, ale nie są likwidowane. ?1 ł Filtracja obrazu 69 .ledną z metod eliminacji tego typu zakłóceń jest filtracja melonowa (FM). Filtracja medianowa jest operacją nieliniową i ten iil.i komplikuje matematyczną analizę jej właściwości. Realizowana • i najprościej przez przesuwanie pewnego "okna"wzdłuż wierszy •'.howego obrazu i zamianę wartości elementu obrazu w środku "okna" przez wartość mediany elementów wewnątrz okna. Otrzy-Dauje się przy tym obraz bardziej gładki w porównaniu z obrazem iowym. W porównaniu z liniową filtracją małej częstotliwości, I \l umożliwia zachowanie ostrych zmian jaskrawości oraz dużą ? l a), przy czym wszystkie elementy obrazu po jednej stronie prostej rozdzielającej te zbiory będą miały jaskrawość a, natomiast po drugiej stronie prostej jaskrawość b. Jeżeli At jest symetryczne względem punktu (0,0) i ora ten punkt, to FM określony przez (4.60) zachowuje skoki ja- iwości w obrazie. Jeżeli {r,s) eĄ-* (-r, -s) 6 Aj i (0,0) e Ah ? imponujemy At na linie w R, przechodzące przez punkt (0,0). W tedy,madiana(fi j : (i,j) € LA n At) = /0j0, gdyż dla tak okre- lonego At, LAC\ Ai musi mieć nieparzystą liczbę punktów z których i Milowa (wyłączając /0,o) jest > /0,0, natomiast druga połowa < /0)0. Ponieważ wszystkie linie przechodzące przez punkt (0,0) nie stykają •' sobą w innych punktach, wyłączając punkt (0,0) otrzymujemy, < I uiłowa elementów w At musi być > /0,o , natomiast druga połowa - /(),(, . Jeżeli punkt (0, 0) jest punktem środkowym okna {fi+rJ+s}, i" w świetle powyższych rozważań mamy mediana(fi+rd+8 : ("', j) <=ALC\ LA) = fTrt (4.61) Dla każdej prostej LA przechodzącej przez punkt środkowy iłkna, połowa elementów będzie miała jaskrawość a, natomiast druga polowa b. Na wyjściu FM zachowany zostanie skok jaskrawości obrazu. Niekiedy przy przetwarzaniu obrazów występuje tzw. szum impulsowy zakłócający obraz. W obrazie szum impulsowy reprezento-. jest przez pojedyncze punkty o maksymalnej lub minimalnej rawości czyli impulsy o bardzo dużej amplitudzie dodatniej lub 111'i miej. Zastosowanie FM eliminuje z obrazu szum impulsowy, przy i prawdopodobieństwo otrzymania na wyjściu FM zakłóconego 1 lamentu wynosi (?-i) I" SC* )P\l-P)L-k (4.62) fc=0 * i bardzo szybko zmniejsza się ze zwiększeniem liczby elementów \\ przy czym L jest wymiarem Aj. Szum impulsowy w punkcie (i,j) obrazu występuje z prawdopo- dobieństwem F, które nie zależy ani od występowania szumu w in- punktach obrazu, ani też od obrazu wejściowego. Niech zakłócony punkt obrazu ma wartość a. Jeżeli {/,',} będzie obrazem zakłóconym to -' jaz prawdopodobieństwem F , ^ \ f*j z prawdopodobieństwem (1 - F) \ ? i 72 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Niech punkt (% ,j ) będzie położony na części obrazu ze stałą wartością jaskrawości fUr,f+s = fi\f = cźd, (r,s)eAl (4.64) i niech yij = mediana(f'itj) (4.65) Wtedy yj •" = // •" = c tylko w tym przypadku, jeżeli liczba impulsów szumu w Ai ze środkiem w (i ,j ) będzie mniejsza od połowy liczby punktów w A\ tj. mniejsza lub równa ( ~ , gdzie L - wymiar Ai. Ponieważ liczba zakłóconych punktów w Ai ma rozkład dwumianowy, mamy L-l P(Vi'j' - *j") = Ż( fc )^(1 - ^ (4-66) fc=0 Prawdopodobieństwo wystąpienia błędu wynosi (Ł-D i- ? (ł ^ - p^L'k (4-67) fc=0 ft W pracy [78] przedstawiono zależności ilustrujące zależność prawdopodobieństwa wystąpienia błędu przy FM od L i P. Jeżeli mamy (4> = {U,} = Ki) (4-68) gdzie {n^j} reprezentuje pewien szum, to oszacowanie obrazu oryginalnego jest dane przez {fij} = mediana{fij} + mediana[{fi^] - mediana{fi^)\ (4.69) Przedstawimy wyniki zastosowania filtracji medianowej dla sygnału dwuwymiarowego tj. obrazu. Na Rysunku 4.26 przedstawiono obraz z Rysunku 4.2a zakłócony szumem o rozkładach normalnym (a) i jednostajnym (b), oraz odpowiednio obrazy uzyskane w wyniku FM dla okna A5. 4 4. Wykrywanie zmian jaskrawości 73 c) d) ltvsunek 4.26: Wyniki FM: obraz oryginalny z Rys.4.la zakłócony szumem o rozkładzie normalnym (a) i szumem o rozkładzie jednostajnym (c), oraz odpowiednio obrazy po FM dla okna 5x5 elementowego (okna As) Innym rodzajem filtracji jest filtracja przestrzenno - zależna implementowana poprzez zmianę typu filtru lub wartości współczynni-l.uw wagowych masek dla różnych obszarów obrazu. Tego rodzaju filii rm zachowującym zmiany jaskrawości w obrazie jest filtr Kuwahary |'>0|,[89],[119] (Rys. 4.27). Kwadratowe okno rozmiaru 4L + 1 jest dzielni ic na 4 obszary z których każdy zawiera punkt środkowy. Wartość rawości piksela środkowego jest zastępowana przez średnią wartość i awości obszaru z najmniejszą wariancją. 4.4 Wykrywanie zmian jaskrawości Idi/patrzmy obraz analogowy f(x,y), gdzie funkcja f(x,y) > 0 jest uczkowalna w całym obszarze obrazu (Rysunek 4.28). Określimy I"H hodną: 74 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Obszar 3 Obszar 1 ? i ? ? ; ? ? ? ? ? ? mm* ? ? ? ? ? i i Obszar 2 PłJtset środkowy Obszar 4 Rysunek 4.27: Filtr Kuwahary Sf(x,y) Se lim t-o f(x + te1,y + te2 - f(x,y) __ t 6f{x,y) , . Sf(x,y) . cos ip H sin ip 8y Sx (4.70) gdzie: e\ = cos^ , e2 = sin^> , e = (ei, e2) - wektor jednostkowy, %l> - kąt pomiędzy wektorem e i osią x. Pochodna (4.70) jest funkcją ip i jest równa zeru w kierunku równoległym do linii skoku jaskrawości r (Rysunek 4.29), osiągając wartość maksymalną w kierunku prostopadłym do granicy pomiędzy obszarami o różnej jaskrawości tj. dla kąta 6f{x,y) fl = arctgb/fcy Sy (4.71) Maksymalna wartość d->^,y> i wynosi rM(x,y) 2 + (5f(x,y))2]h Sy óx (4.72) i i Wykrywanie zmian jaskrawości 75 inek 4.28: Obrazy, profile zmian jaskrawości oraz pierwsze i drugie pochodne funkcji jaskrawości I >la obrazu cyfrowego rozpatrujemy nie pochodne cząstkowe, ale o 11 oszacowanie za pomocą skończonych różnic, aproksymujące po-i liodne z różną dokładnością. Jednym ze sposobów aproksymacji po-i liodnych jest wykorzystanie operatora Robertsa tj. i+lj+1 •+lj IJ Sf, Si sfj,j Sj JiJ J% - fi,j+l ~~ fi (4.73) (4.74) ()peratory tego typu mają następujące wady: (a) pochodne >l>liczane nie względem punktu (i,j), ale względem punktu ' • c, j' + |) i (b) wrażliwość na zakłócenia. Aby zmniejszyć czułość i kłócenia zwiększa się wymiary tzw. maski operatora określającej ? li•iiicnty obrazu wykorzystywane przy tworzeniu odpowiednich różnic 76 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Rysunek 4.29: Skok jaskrawości jaskrawości (odpowiada to operacji "wygładzania" obrazu przez wagowe uśrednianie jaskrawości elementów). Najbardziej popularne są 3 x 3 elementowe maski operatorów. Niech fij i gitj , i, j = 0,1,..., N - 1 oznaczają odpowiednio dyskretne obrazy wejściowy i gradientu. Dyskretnymi analogami równania (4.72) są 2 li 9i,j = \dllj + d2f^ (4.75) 9i,j = \dUj + Aj | (4.76) gdzie: dlij i d2ij - oszacowania pochodnych cząstkowych funkcji jaskrawości w punkcie (",j). W Tablicy 4.1 przedstawiono różnicowe operatory gradientu, natomiast na Rysunku 4.30 przykłady zastosowania operatorów wydzielania zmian jaskrawości. Niech Ffj Ffj będą wektorami określającymi otoczenie punktu (UY- {FijJ - (/u>/tJ+i"/t+iJ>/"+iJ+i) (4-77) \^i,j) = (/*'-lj-li fi-ljt fi-lj+U /tj-li /łj+1) fi+lJ-U /ł+lji /t+lj+l)(4-78 gdzie symbol t oznacza transponowanie wektora. Składniki tych wektorów to uporządkowane wg. wierszy elementy otoczenia, odpowiednio wymiaru 2x2 i/lub 3x3, punktu (i,j). Obraz i i Wykrywanie zmian jaskrawości 77 Tablica 4.1: Różnicowe operatory gradientu NMW* opera- Wyrażenia do obliczenia Wektory wagowe Wq Okno i< owy [fi,3 ~ fi,j + l] + lli+l,j ~ Ii+l,j + l] fi,, = [fi-t-l.j ~ ti,]\ + l/ł+lj+1 - Ii,j+l] Wx = 1 -1 1 . -1 i W2 = -1 -1 1 1 2X2 Mwl.nrtsa dlij = fi.j - fi+l,j + l **IJ = fi + l,j - fi,j+l Wi = 1 0 0 -1 i W2 = 0 -1 1 0 2x2 M"" Róż- dlij = max (/ij./i+ij./i.j+iJi+ij+i) d2itj = -min {fi,j,fi+i,j, ftj+l, fi+lj+ll Nie ma 2x2 l*i"wltta'a "Uj = [ti-l,j-l + fi,i-\ +/i+l,J-lj-[/•-l.j + 1 + /t,j + l + /i+lj + l) [/i+l,J-l + fi + l,j + Ii + l,j+l]~ [Ii-l,j-l + Ii-l,} + Ii-l,j+l] Wl = - 1 ? 0 -1 1 0 -1 1 0 . -1 . ; W-2 = -1 -1 0 0 0 1 1 . 1 . 3X3 dU.i - [fi-ij-i +2/i,j_i + /i+ij-ij- [/i-l.j+l +2/i,i+l +/.+l,j+l] d2;,, = [/i+l.j-l +2/;+i,j +A+1J+1I- Ufł-l.i-1 +2/i-l,j +/i-l,j+ll WX = - 1 - 0 -1 2 0 -2 1 0 . -1 . ; W2 = -2 -1 0 0 0 1 2 . 1 . 3x3 ??.i .ulientu uzyskany za pomocą operatorów przedstawionych w Tablicy i I określamy jak 9i,j lub (WłFtf + (WiFtf (4.79) 9u = (WtFfrf + (W^f (4.80) w zależności od tego, czy wykorzystujemy wektory otoczenia Ffj i ) Ftr Wektory bazowe {Wi} są ortogonalne i mogą być przyjęte jako baza '• wymiarowej przestrzeni euklidesowej. Jeżeli baza jest ortonormalna, 78 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego h 4 Wykrywanie zmian jaskrawości 79 my więc Rysunek 4.30: Przykłady zastosowania operatorów wykrywania zmian jaskrawości a) i b) różnicowe operatory gradientu, c) i d) operatory laplasjanu (obraz d) jest obrazem zanegowanym), e) operator Prewitt'a i f) operator Sobela pr (4.82) L^nJ Lt=l \FiJ = (4.83) przy czym (4.84) Wu\ 9 = arc cos Innymi operatorami wykrywania zmian jaskrawości nie przedsta-nymi w Tablicy 4.1 są operatory Kirsch'a Q, Marr - Hildretłi'a [21] ? Canny [9]. W przypadku operatora Kirsch'a mamy max {3(fk + fk+l + fk+2 + fk+3 + fk+A) fc=0...7mod8 5(/*+5 + /*+6+/*+7)} (4.85) oraz kierunek zmiany jaskrawości 7 = (90 + kmax ? Ab°)mod 360°. (4.86) przy czym numeracja elementów obrazu w oknie 3x3 jest zgodna Rysunkiem 4.31. Operator Marr - Hildreth lokalizuje zmiany jaskrawości w punktach cięć drugiej pochodnej obrazu z zerowym poziomem jaskrawości, uny (4.8i; to mnożenie skalarne HfFyHlWIMFyllcoB* określa długość projekcji wektora F*j na kierunek zadany przez wektor Wt , przy czym 9 jest kątem pomiędzy wektorami F^j i W,,. V'%(i, j, a)} * /(i, j) = h(i, j) * /(i, j) gdzie 2, 2 g(i,j) = e{~'~?*-), (4.87) (4.88) 80 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego f5 U f 7 U '" V u \ % a) +5 +5 -tSY-3 +5 ^-Su'-3 -5 4-5Y-3 -3 -3*1 -i [0] -3 i!-3 [0] *511 -3 [0] +5i|-3 [0] *5 3 -3 -3A.-3 -3 -3^.-3 -3 +5A-S +5 +5,' J-3 -3 -3^-3 -3 -})( [-3 [0] -3JJ+S JO] -*| U5 +5 -5A+S *S ~3A ?5 -3 -3M*S +5 -3. 5 [0] -ł|^ pi -"j ?5 -3 -3A-3 -3 -3,! b) Rysunek 4.31: Numeracja elementów obrazu w oknie 3x3 operatora Kirscha (a) i maski operatora Kirscha (b) • jest operatorem splotu, 72 -ł- I2 - (72 ;-%#) (4.89) c jest współczynnikiem normalizującym dobieranym w taki sposób, by suma elementów maski była równa zero. Przykładowa maska tzw. Mexican Hat jest następująca 0 0 -1 0 0 0 -1 -2 -1 0 -1 -2 16 -2 -1 0 -1 -2 -1 0 0 0 -1 0 0 Operator Marr - Hildreth może być aproksymowany przez różnicę dwóch filtrów gaussowskich, np. dla przypadku jednowymiarowego jak KhJ) = 9i{i,j)-92(hj) (4.90) i 1 Wykrywanie zmian jaskrawości 81 < "i>t,ymalna aproksymacja dla cr2 = 1,6 • /*-5t fi = 7r(/ * 9) = / * a* = / * 9i = f * -g(hJ) (4-93) Q-j(f*g) = f*-Q-jg = f*gJ = f*-2 fi = hU * 9) - / * -?29 = / * 9i = / * -i9(h J) (4-94) 2. Obliczamy amplitudy gradientu i oszacowanie kierunku lokalnej zmiany jaskrawości dla każdego punktu obrazu, I = mf*9)\ = y/f? + fj, (4-95) 3. Określamy położenia zmian jaskrawości (4.92), 82 Rozdział 4. Pr^twarranie wstępne obrazu cyfrowego I I Wykrywanie zmian jaskrawości 83 4. Eliminujemy amplitudy gradientu mniejsze od maksymalnych (Rysunek 4.33), 5. Realizujemy operację progowania z dwoma wartościami progowymi. Stosujemy dwie wartości progowe - małą thi i dużą thh przy czym zwykle thh - 2 ? thi. Tworzone są dwa obrazy po operacji progowania 4 i /j. W obrazie Ii uzyskujemy poprzerywane linie konturowe, ale analizując 8-elementowe sąsiedztwo elementów Ii można połączyć elementy linii krawędzi w Ih- -h- t> r-) Amplituda -" Operacja pocieniania Filtr Gaussowski i-*? X U_L^ Kąt -? Obliczanie gradientu Rysunek 4.32: Algorytm Canny wykrywania zmian jaskrawości. Rozważany element obrazu Modut gradientu Pjest większy niż moduły gradientu w punkach AiB Kierunek gradientu Średni modut gradientu dwóch punktów obrazu Rysunek 4.33: Algorytm eliminowania modułów gradientu mniejszych od maksymalnych Haralick [33] zaproponował by funkcję reprezentującą jaskrawość' obrazu która może być rozpatrywana jako pewna powierzchnia (sąsiedztwa rozpatrywanego punktu obrazu), modelować za pomocą płatów powierzchni opisywanych funkcjami (stałymi, liniowymi, drugiego c) d) ick 4.34: Wykrywanie zmian jaskrawości metodami a) Kirscha, b) Prewitta i Canny (c dla a = 1 i d dla a - 2.8) eciego stopnia) wielomianowymi. Minimalizowana jest funkcja iitrilu pomiędzy płatowym modelem powierzchni obrazu i rzeczywi- i próbkami obrazu. Obliczane były (w kierunku zmiany gradientu awości) druga i trzecia pochodna funkcji trzeciego stopnia mode- i ej jaskrawość. Punkt jest punktem w którym występuje zmiana jaskrawości jeżeli: I. druga pochodna funkcji modelującej jaskrawość jest równa zero, ' trzecia pochodna tej funkcji jest ujemna. Haralick rozważał funkcję trzeciego stopnia ;) = k1+k2i+k3j+kĄf+hij+k6j2+k7i3+k8i2j+k9ij2+kwj3 (4.96) Kierunek gradientu w punkcie (i,j) = 0 jest określony przez 8in0 = -j=p=, cos9 = -jJ^= (4.97) y k2 + k3 y k2 + ks 84 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Wtedy, pierwsza i druga pochodna definiowane są przez równania f'e(i,j) = ^sin9 + ^cos9 (4.98) f)2 f 82 f 82 f f (i, j) = y-sin29 + ^cos29 + 2-^sin9cos9 (4.99) Podstawiając i = psind, j = pcosO otrzymujemy równanie (4.96) w postaci fe(p) = Co + ClP + C2p2 + C3p3 (4.100) gdzie Co = ki, Ci = k2sin9 + k3cos9 C2 = k^sin^O + k5sin9cos9 + kQcos29 Cs = k7sin?9 + k$sin29cos9 + k9sin9cos29 + kiQcosz9 Różniczkując fo(p) względem p otrzymujemy f'9(p) = C1 + 2C2p + 3C3p2, fe{p) = 2C2 + QC3p, (4.101) fe'(p) = 6C3. Z warunków określających kiedy punkt obrazu jest punktem zmiany jaskrawości otrzymujemy fe (p) < 0 czyli C3 < 0 oraz z fe{p) = 2C2 + 6C3p = 0 mamy |^| < Po- Wykrywaąnie zmian jaskrawości metodą Haralicka polega więc na: 1. obliczeniu fci, k2, k3,..., kw, 2. obliczeniu 9, sin9, cos9, 3. obliczeniu C2,C3, 4. sprawdzeniu czy C3 < 0 i \{g-\ < po i podjęcie decyzji o wykryciu zmiany jaskrawości w punkcie i, j. Obliczenie ki, k2, k3,..., kio można zrealizować na podstawie najmniejszego średniokwadratowego błędu pomiędzy powierzchniami modelującą i rzeczywistą jaskrawości. Można to zrealizować wykorzystując odpowiednie maski splotu (Rysunek 4.35). i S Segmentacja obrazu 85 •13 2 7 ?" -13 ! 2 17 22 17 •> T*!j 7 22 27 22 7 j 2 17" 22 i7 2 • 13 2 7 2 1.1 31 -5 -17 -5 ?11 -44 -62 -68 ?m .44 0 0 li 0 1) H 62 08 m 44 ?31 .1 17 i) -:!1 fc, 31 -11 0 44 -31 -5 -62 1) 62 5 17 -6* ii m 17 i -5 •62 i) 62 ~i : :il -44 0 44 •31 -> 2 2 2 2 -i -1 .i -1. -1 _2 _2 _2 _2 .2 -1 -1 _ s .i -1 ?" 2 ?" 2 2 1 2 U _2 -4 2 1 U -1 "2 0 0 I) 0 0 -2 -1 0 1 2 -1 .'" li '1 f *-, fc, 2 -1 1-2 1-1 ?> 2 -1-2 -1 >> 2 -1 -2 i -1 2 2 -11-2 1 -S 2 •> -1[-2| -i 2 1 -1 -1 -1 -1 i Hi) ?4 -2 0 2 i 2 •> 2 2 2 2 1 0 -1 "?) U 0 U 0 0 1 2 0 .9 .4 _?> .-." _2 _'> _2 2 i i) -1 "-> 1 I 1 ł 1 •1 -2 u •) 4 I 11(1 I* -i 2 1 2 -4 .'} 1 •} 1 . ?> 0 0 i) 1) 0 2 -1 Ji •1 2 1 -2 4 _2 ł -1 2 1) "\> i -1 ?> i) -2 1 -1 •> U "*> l -1 •> U -1 1 -1 ?> (ł -2 1 I!vsunek 4.35: Maski Haralicka wykorzystywane do obliczeń fej,t = 1,2,..., 10. 4.5 Segmentacja obrazu Z punktu widzenia operacji segmentacji wszystkie obrazy można sprowadzić do dwóch typów [10],[45],[80]: (a) obrazy zawierające obiekty, które mogą być bez trudu interpretowane, jako że posiadają znany model opisu, oraz (I)) obrazy w których jednorodne pod względem koloru lub wartości |n.skrawości obszary obrazu nie mają jednoznacznej nazwy i interpre-tacji np. tekstury. ()dpowiednio do tej klasyfikacji obrazów będziemy operowali poję-? iami segmentacji pełnej lub częściowej. 86 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego 4.5. Segmentacja obrazu 87 (4.102) (4.104) (4.105) 4.5.1 Matematyczne sformułowanie zadania segmentacji Niech fij będzie funkcją jaskrawości analizowanego obrazu, X -skończonym podzbiorem płaszczyzny, na której określona jest funkcja fij; S = {Si, S2, ? ? ?, SK} ~ określa podział X na K niepustych podzbiorów Su i = 1, 2,..., K, Reg - reguła określona na zbiorze S i przyjmująca wartość prawda wtedy i tylko wtedy, kiedy dowolna para punktów z każdego podzbioru S* odpowiada pewnemu kryterium jednorodności. Segmentacją obrazu /y wg. reguły Reg jest podział S = {Si, S-2, ? ? ?, SK} odpowiadający warunkom a) uf=1Si = X b) Si n Sj = o, Vi ^ j c) Reg(Si) = prawda Vz d) Reg(Si n Ą) = fałsz Vi, ^ j Reguła Reg określa pewne kryterium jednorodności i zależy od właściwości funkcji fij. Np. reguła Reg może być określona następująco Reg(Si prawda jeżeli ftj = ... = fk,i fałsz w przypadku przeciwnym gdzie (k,l) C Si, k, l = 1, 2,..., M i M oznacza liczbę punktów w obszarze Ą, lub przez Reg(Si) = prawda jeżeli \fM - fkJL\ < t .^ ^\ fałsz w przypadku przeciwnym gdzie (i,j), (k,l) - dowolne punkty w obszarze Si, t - wartość progowa. Segmentację rozpatrujemy jako bsg '? jij ? Sij Sij = Xi przy (i,j) G Su i = l,2,...,K Segmentacja W oparciu 0 algorytmy wydzielanie granic obszarów 3 Przestrzenne różniczkowani Filtracja w. cz. ZL W oparciu o kryteria jednorodności czyli przez podział/ rozrost Aproksymacja funkcjonalna obszarów Operacje progowania i grupowania Podział lub rozrost obszarów Metody relaksacyjne Rysunek 4.36: Klasyfikacja metod segmentacji gdzie fij, s^j oznaczają funkcje określające odpowiednio obraz iściowy i obraz po segmentacji, natomiast Aj jest etykietą (nazwą) tego obszaru. Do rozwiązania zadania segmentacji można stosować dwa ogólne podejścia. Pierwsze - dobrze opisane w literaturze [ ] - oparte jest I 1 prostym fakcie, że pewne właściwości punktów obrazu należących t|o różnych obszarów sąsiednich są różne. Sprowadza to zadanie jmentacji do zadania wydzielenia granic obszaru. Drugie podejście l"'lega na znalezieniu punktów obrazu, które spełniają pewne kryte-ninii jednorodności i połączeniu ich w obszar, któremu przypisuje się kietę (nazwę). Z pierwszym podejściem związane są ograniczenia polegające na u. że podział S jest zbiorem dwuelementowym S = {Si, S2}, gdzie gdzie Si - podzbiór granicznych elementów obszarów, S% - X/S\ - zbiór wewnętrznych punktów obszarów. Praktycznie oznacza to, że algorytm wydzielania granic nie pozwala na przydzielanie różnych etykiet (nazw) różnym obszarom. W przypadku drugiego podejścia Reg określają wzory (4.103), (4.104) i (4.105). Klasyfikację metod segmentacji przedstawia Rysunek 4.36. 4.5.2 Segmentacja metodą wydzielania granic obszarów Można wyodrębnić trzy metody wydzielania granic obszarów: - przestrzenne różniczkowanie, - aproksymacja funkcjonalna, - wysokoczęstotliwościowa filtracja. Metoda przestrzennego różniczkowania wykorzystuje fakt, że graniczne punkty obszarów mają dużą wartość modułu gradientu funkcji Algorytm przestrzennego różniczkowania przekształca wejściowy obraz w skalarne pole g^j (4.106) w-Wijl v^eX (4.107) , o fnnkcii jaskrawości, fi(i,j Jest ob !fr . "fr - P-tadM ^^ a^dientu przy wykorzystań,,, razem gradW Przetwarzaj obraz " pewnego operatora progowego th np. (4.108) •e ""teDne obrazu cyfrowe|? RozdziąM_2^^^ ki = • r hmarnv obraz konturowy, otrzymujemy binarny o otrzymujemy Metoda aproksymacji funkcjonalnej polega na wykorzystaniu al gorytmów optymalizacji dla celów wydzielania granic obszarów. Din każdego punktu obrazu {x ,y) rozpatruje się otoczenie R z punku MU 9ij > th 9iJ < th 4.5. Segmentacja obrazu 89 środkowym w [x ,y). Dla elementów obrazu należących do R określana jest funkcja: f{x,y,ci,c2,t,ai,a2) = { a przy cxx + c2y > i, (x, y) € R ax + a2 przy cxx + c2y < t, (x,y) G R (4.109) 0 {x,y)ŹR gdzie c\,c2, t, a\, &i są parametrami liczbowymi. Funkcja (4.109) określa tzw. idealną granicę obszaru w punkcie ts,y), przy czym C\,C2,t określają orientację i położenie idealnej ??i.niicy obszaru względem (x ,y), a ci\,a2 - amplitudowe charaktery-ityki granicy obszaru. Zadanie segmentacji sprowadza się do aproksymacji funkcji f(x, y) z funkcję f(x,y) . Jakość tej aproksymacji oceniamy za pomocą metryki p(/, /). P (/,/) = / / f{x,y)- f{x,y,Ci,c2,t,ai,a2) dxdy (4.110) Metoda filtracji wieloczęstotliwościowej polega na wydzielaniu grani, obszarów za pomocą przetwarzania obrazu w obszarze częstotliwo-• 1 przestrzennych, ponieważ informacje o granicach obszarów zawarte wysokoczęstotliwościowej składowej widma obrazu. 4.5.3 Segmentacja metodą rozmieszczenia punktów obrazu 1 ytmy segmentacji metodą rozmieszczania punktów obrazu dzie-ua: orytmy progowego przetwarzania obrazu i grupowania punktów ' harakterystycznych, •rytmy rozrostu obszarów, ni \ tmy relaksacyjnego rozmieszczania punktów obrazu. 90 Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego Progowe przetwarzanie obrazu i grupowanie punktów charakterystycznych Metoda ta polega na przetwarzaniu funkcji jaskrawości obrazu za pomocą operatora Th:f(x,y)-+s(x,y) (4.111) f A7 przy Tj < f(x, y) < TJ+1 s(x,y)=! X1 przy f(x,y) TK-\ gdzie s(x, y) - obraz po segmentacji; K - liczba obszarów segmentacji; Ai, Aa,..., XK ~ etykiety (nazwy) obszarów; Ti, T2,..., TK - uporządkowane wartości progowe T0 < Ti < ... < TK~v Zadanie segmentacji można traktować jako zadanie szukania grup w przestrzeni cech. Niech z, = 4>(x, y) będzie wejściowym losowym polem poddanym segmentacji. Każdemu punktowi (x, y) obrazu odpowiada wektor cech tj. (x, y) -> zł = (zx, z3,..., zn). p(z) jest gęstością rozkładu prawdopodobieństwa 1-rzędu losowego pola 4>(x,y). Niech p(z) -ZPjPjiz), ?P, = 1 (4.113) i=i i=i gdzie: Pj - współczynniki liczbowe, Pi (z) - gęstość rozkładu prawdopodobieństwa j-tej składowej. Współczynniki Pj interpretujemy jak prawdopodobieństwo a'priori zdarzenia {punkt obrazu (x, y) -* z należy do j - tego obszaru} i określają one rozkład prawdopodobieństwa punktów, należących do j-tego obszaru obrazu. i 5 Segmentacja obrazu 91 Zadanie sprowadza się do statystycznej oceny współczynników Pj i funkcji Pj(z). Po oszacowaniu Pj i Pj(z) rozmieszczenie punktów ob-i u realizuje się wg reguły: l>unkt obrazu (xo:yo) , posiadający wektor cech ZQ otrzymuje ety-? ? Xj? , jeżeli PjPj(Z0) = max (PKpK(Z0)) , K=l,2,... (4.114) Jest to zadanie wydzielenia "unimodalnych podzbiorów" zbioru dftnych [J, rozwiązywane metodami grupowania (Rysunek 4.37). Budowa opisu Wydzielanie cech z -* Grupowanie / -" \ Klasyfikacja elementów -> Rozmieszczenie punktów obrazu ?- \ f('J) Pj (z) S(i J) Rysunek 4.37: Segmantacja metodą grupowania Metoda rozrostu obszarów Metoda ta w odróżnieniu od metody grupowania oparta jest na ak-i\\vnym wykorzystaniu dla celów segmentacji lokalnej informacji o • i ? hach. Na płaszczyźnie obrazu ustala się pewną liczbę punktów po-? 11 kowych (wybranych w dowolny sposób), przydziela się im etykiety, i następnie realizuje się analizę punktów sąsiednich. Jeżeli dla pary punktów spełniony jest warunek jednorodności to punkty te otrzymują I 1I..1 samą etykietę. Proces ten trwa do chwili, aż wszystkie punkty ob- mają etykiety. Z powyższego krótkiego opisu wynika, że krytycz-nytni momentami w tej metodzie są: sposób wyboru punktów począt- II iwych, postać kryterium jednorodności i sposób przeglądania punk- 11 iw obrazu. Proponowane i doświadczalnie sprawdzone kryterium jed norodności jest następujące RegiSJ = { P!Tda ^^ 'fi^i|S kreślając hu(k) dla k = O, ...,L - 1, czyli dla wszystkich iwych poziomów jaskrawości obrazu, uzyskujemy histogram ?II. Na podstawie histogramu jaskrawości można zdefiniować szereg uych cech charakteryzujących obraz (obszar obrazu). Są to: Momenty L-l nu = E[v*] = J2 ^Kik) fe=0 |dzie i = 1,2,... oznacza rząd momentu. Momenty bezwzględne L-l mi = E[\u\i] = J2\k\ihu(k) * = 1,2,... fc=0 Momenty centralne & = E{[u - E(u)]*} = ?(* - m^Kik) fc=0 Bezwzględne momenty centralne L-l /5i = E[\u - Eiu)]1} = J2 \k - rnjKik) k=0 Entropia L-l H = E[- log2 hu) = - Yl Kik) log2 hu(k) fc=0 (5.2) (5.3) (5.4) (5.5) (5.6) Najczęściej wykorzystywane cechy określające rozkład jaskrawości ibrazu (cechy histogramu) to: odchylenie standardowe jaskrawości - /ii, wartość średnia jaskrawości - mi, wariancja - jU2, oraz momenty m2, ju.3, (0,4 - 3). 98 Rozdział 5. Analiza obrazu Inne możliwe do obliczenia na podstawie histogramu cechy obrazu to wartość mediany i wartość modowa. Niektóre cechy określające rozkład jaskrawości obrazu można obliczyć bez znajomości explicite histogramu, dotyczy to np. mi{a,, b) m -- Y, 2[u(m ~a,n- b)}1 (5.7) ok (m,n) eOk fM(a,b) = -- Y 5Z[w(m-a,n-6)~mi(a,6)]1 (5.8) ly°k (m,n) eOk gdzie i = 1,2 i Non Jest liczbą pbceli w obszarze Ok. 5.2 Właściwości topologiczne obrazów Właściwości topologiczne i relacje między obiektami obrazu dyskretnego spełniają ważną rolę w procesie analizy i opisu obrazu. Najczęściej właściwości te i relacje definiowane są dla podzbiorów obrazu wydzielonych w procesie segmentacji obrazu np. dla obiektów obrazu. W procesie rozpoznawania obrazów podejście topologiczne można zastosować do zdefiniowania pojęcia obiektu i tła. W rozdziale tym przedstawimy pewne właściwości topologiczne obrazów dyskretnych dwuwymiarowych i trójwymiarowych, tj. właściwości zależne tylko od położenia punktów należących do danego podzbioru obrazu, a niezależne od wartości jaskrawości tych punktów oraz możliwości wykorzystania właściwości topologicznych obrazów w procesie analizy obrazów. Rozważamy dyskretny obraz o M wierszach i N kolumnach. Dwójka (i,j) oznacza położenie elementu obrazu w i-tym wierszu i jf-tej kolumnie, a F = {f(i,j)} - obraz dyskretny, w którym wartość jaskrawości elementu jest określona przez f(i,j). Każdy punkt f(i,j) obrazu dyskretnego będzie reprezentowany przez dwójkę całkowitą (i,j), odpowiadającą współrzędnym w obszarze R, gdzie R tablicą liczb całkowitych - współrzędnych punktów obrazu tj. R = {(i,j)\l < i < M i 1 < j < N}. Punkt (ij) <= R, który nie jest punktem brzegowym obszau, ma cztery poziome i pionowe elementy sąsiednie oznaczone przez (i ± l,j) i (i,j ± 1) oraz cztery diagonalne elementy sąsiednie oznaczone przez (z±l, j±l). i 2. Właściwości topologiczne obrazów 99 Odległością lub metryką d pomiędzy parą punktów należących do 11 |est liczba rzeczywista nieujemna, taka że dla wszystkich elementów 1/j),(h,k),(l,p) mamy il((i,j),(h,k)) = 0 wtedy i tylko wtedy (i,j) = (h,k) d((i,j),(h,k)) = d((h,k),(i,j)) (5.9) d((i,j), (l,p)) < d((i,j), (h, k)) + d((h, k), (l,p)) Standardowymi metrykami są *((", J), (h, k)) = \i-h\ + \j - k\ (5.10) d8((i,j), (h, k)) = max(|i - h\, \j - k\) (5.11) 4-elementowe otoczenie (sąsiedztwo) N±(i,j) i 8-elementowe oto-? cnie (sąsiedztwo) Ng(i,j) elementu (i,j) definiujemy jako (Rysunek 5.3) N4(i,j) = {(h,k); d4((i,j),(h,k)) 9 , jego wartość określamy jako k - 8, W ipółczynnik krzywizny w punkcie /0 = 1 jest definiowany jako tf4(/o) = l-^?/* + lE AA+i/fc+2 (5.17) A'8(/o) = l-^?/* + §? /*/*+! + !E fk7k+ifk+2 (5.18) gdzie / jest zbiorem liczb całkowitych {1,2,..., 8}. U u u u u f, u f. f. Rysunek 5.4: Punkt obrazu /o i jego 8-elementowe sąsiedztwo Dla przypadku trójwymiarowych obrazów dyskretnych R jest trójwymiarową tablicą punktów obrazu takich, że R = {(i,j,k)\l < i < M, 1 < j < iV, 1 < k < i^}. Dla punktu (i,j, k) E R możemy określić sąsiedztwa (Rysunek 5.5): Rozdział 5. Analiza obrazu 6-elementowe: (i ± 1, j, fc), (i, j ± 1, fc), (i, j, k ± 1), 12-elementowe: (i ± 1, j ± 1, k), (i, j ± 1, fc ± 1), (" ± 1, j, A; ± 1) 8-elementowe: (i ± 1, j ± 1, fc ± 1) ^ 26-elementowe: uwzględniające jednocześnie wszystkie trzy przedstawione wcześniej. j-1 i i+1 j-1 i i+1 i-1 i i+1 Rysunek 5.5: Sąsiedztwo elementu w przestrzeni trójwymiarowej: a -6-elementowe, b - 12-elementowe, c - 8-elementowe (5.19) (5.20) OdległośC pomiędzy punktami (i, j, fc) i (u, v,w) obliczamy następująco dW(*J.*),(th*."))-'^H-^b-*l>-"l) Odległości ds i dk spełniają wszystkie postulaty metryki w R. Ścieżka jest sekwencją P0, Pi,... Pt punktów (Pp = (ip, jp, fcp)) takich, że Pi jest punktem sąsiednim Pi_i, 1 < i < t. W zależności od wyboru definicji sąsiedztwa będziemy rozpatrywać odpowiednią ścieżkę. Analogicznie, jak w przypadku obrazu dwuwymiarowego, można określić, że dwa punkty podzbioru obrazu S będą 6- lub 26-połączone w S, i że będą istniały 6- lub 26-składniki w S. Ponieważ punkty zewnętrzne obrazu nie należą do S, wynika stąd, że wszystkie punkty w S, które są połączone (w S) z punktem granicy obrazu, należą do pewnego składnika w S. Składnik ten jest nazywany zbiorem zewnętrznym S (w przypadku dwuwymiarowym - tłem), wszystkie Właściwości topologiczne obrazów 103 HUK- składniki S (jeżeli istnieją) nazywamy wnękami w S. Z rozpatrywanego obrazu możemy wydzielić, poprzez zastosowanie • ?mówionych relacji i definicji topologicznych, informację opisującą strukturę i tworzącą opis. Liczba połączeń i współczynnik wizny wykorzystywane są do klasyfikacji elementów obrazu przy Walizie właściwości obrazu. li I oczywiste, że liczba połączeń iV|(/o) jest równa zeru, jeżeli /0 jest punktem izolowanym lub wewnętrznym. Właściwości topologiczne punktu /o są przedstawione w Tablicy 5.1, natomiast na Rysunku • (i przedstawiono fragment obrazu, na którym poszczególne punkty azu oznaczono zgodnie z Tablicą 5.1. Tablica 5.1: Właściwości topologiczne punktu obrazu /o Wartość NI lub iV| Klasyfikacja punktu /0 0 punkt wewnętrzny (W) lub izolowany (I) 1 punkt końcowy (K) 2 punkt połączenia (P) 3 punkt rozgałęzienia (R) 4 punkt skrzyżowania (S) W procesie analizy obrazu wygodnie jest znaleźć tzw. linię główną I ..i/dego obiektu, niezależną od zmian grubości. Znalezienie linii główni 'j może być realizowane za pomocą różnych algorytmów; jednym z ni jbardziej dogodnych jest następujący: dla każdego elementu obrazu o wartości 1 obliczamy wartości N% (iVg) i liczbę niezerowych elementów L(i,j), jeżeli JV| = 1 (iV? = 1) i 2 < L(i,j) < 6, wtedy element obrazu o wartości 1 jest zastępowany elementem o wartości 0, pod warunkiem, że ((i,j)A((ż,i-l)V(i,j+l)))V((ż,j)A((i-l,i)V("+l,i)))^G(5)(5.21) - otrzymany w wyniku takiej operacji obraz jest linią główną obiektu. 104 Rozdział 5. Analiza obrazu Tablica 5.2: Właściwości topologiczne punktu / obrazu półtonowego Wartość Nc Wartość K Klasyfikacja punktu /o 0 0 szyb o 1 szczyt • 1 >Tl krawędź + 2 przełęcz o Na podstawie wartości Nc i K można również klasyfikować elementy obrazów półtonowych o J poziomach jaskrawości. Wyrażenie na Nc jest identyczne jak (5.15, 5.16), z tym że fi = 1 jeżeli fi > f0 /, = 0 jeżeli /, + + + - + -- + 0 +o++-+-"-+ o o + + + - + + - + 998534789,4 -+ + + -+ + A A9 1 6 1 1 %A A +• ? - A ,4,4,4879,4989 8888899777 4446444323 Rysunek 5.7: Klasyfikacja fragmentu obrazu półtonowego przez pewien punkt krzywej, który dąży wzdłuż krzywej do danego punktu. Kąt a jaki tworzy styczna do krzywej w danym punkcie z osią Ox określamy przez •"-Jl (6-24) Krzywizną K linii w punkcie P nazywamy granicę stosunku zorientowanego kąta Aa zawartego między styczną w sąsiednim punkcie P , a styczną w punkcie P, do długości As łuku zawartego między tymi punktami, gdy punkt P dąży do punktu P, tzn. Aa ,_ "_s K= lim -r- (5.25) As-0 As Krzywiznę K wyznaczamy ze wzoru _ x (t)y"(t) - x"(t)y (t)> K- [(*W + (t/W] { ] Krzywa cyfrowa może być reprezentowana przez tzw. kod łańcu chowy (kod Freemana) (Rysunek 5.8). Niech A będzie skończonym zbiorem (alfabetem) z elementami nazywanymi literami - A = {0,1,..., 7} (Rysunek 5.8b). Kod łań cuchowy eh jest skończoną sekwencją liter, czyli jeżeli a\a2-..an sa elementami A, to łańcuch eh długości n jest określony przez eh 107 '" i Reprezentacja linii konturowych i granic obiektów 2 . i 3 * \ 1 / / / 2* " 0 4. : '- ? 0 ' r / \ 5 1 7 3 6 4 - kierunkowy kod łańcuchowy 8 - kierunkowy kod łańcuchowy a) i V Rysunek 5.8: 4- i 8- kierunkowy kod łańcuchowy ... an. Dla każdej litery o, z A długość wektora li powiązanego z st określona przez: h = i+Ą-^(i - (-ir i kąt aj x (5.27) względem osi Ox w prawoskrętnym układzie współrzędnych, gdzie ... 0,1,...,7. Jeżeli krzywa cyfrowa reprezentuje linię konturową obiektu to kod .' uchowy opisuje dany obiekt (Rysunek 5.9). lależy pamiętać, że kod łańcuchowy zależy zarówno od wyboru ftunktu startowego do analizy konturu jak i przekształceń obiektu (Rysunek 5.10). Krzywa cyfrowa związana z eh jest tworzona przez połączenie wek-? >w h (Rysunek 5.11). .leżeli eh = aia2...ax wtedy długość krzywej opisywanej przez i i-i i kod łańcuchowy określamy jak K 1 + Ą-l(l - (-!)"* (5.28) Na płaszczyźnie (x(l),y(l)) określają odpowiednio z-ową oraz y-współrzędną l, gdzie 0 < l < L. x(l) i y(l) są nazywane odpo-dnio x- i y-projekcjami (Rysunek 5.11). 108 Rozdział 5. Analiza obrazu / / a) • • • • • • ? ? • • • • p • • * i u- r * * • ? • 71 \~ b) 1 0.1 su "\7 V 3X 211 2^2 0303333232312121011011 3\/S 076666553321212 c) Rysunek 5.9: Reprezentacja linii granicznej obiektu za pomocą kodu łańcuchowego: (a)kody łańcuchowe, b) linie graniczne obiektów i c) ich odpowiednie kody łańcuchowe). prostej Jeżeli Pa i Ps są dwoma punktami krzywej cyfrowej połączonymi za pomocą s elementów kodu łańcuchowego to możemy wyznaczyć długość lls i kąt nachylenia as względem osi Ox odcinka linii orostei łączącej te punkty (Rysunek 5.12). Reprezentacja linii konturowych i granic obiektów 109 \ > -* :: ?;"; i k ?'T j *: \ -T7--gg^ Kod łańcuchowy 067644222 066444201 Krzywizna = różnica wartości kodu łańcuchowego -6-11202002 -6020022-11 Krzywizna znormalizowana = mod 8 271202002 202002271 Cykliczna permutacja - Kod 444201066 0022-11-602 002271202 002271202 Rysunek 5.10: Kody łańcuchowe tego samego obiektu poddanego rotacji i z różnymi punktami startowymi do analizy konturu Niech Ax i Ay wyznaczają odpowiednio zmiany w x- i y-projekcjach podczas przechodzenia elementów łańcucha opisującego krzywą cyfrową Axt = sign(Q - aiyk)sign(2 - ai:k) At/j = sign{A - aifk)sign(aiik) (5.29) gdzie Axs > Ays Axs < Ays 1 jeżeli z > 0 sign(z) = 0 jeżeli z = 0 -1 jeżeli z < 0 Axs U. = ^Ax* + Ay? arc tg a, = Ay jeżeli arc tg ?** jeżeli (5.30) (5.31) (5.32) 110 Rozdział 5. Analiza obrazu gdzie s s Axs - Y, &xi &Vs = 52 A^ i=i i=l (5.33) Krzywizna K W pewnym punkcie P jest definiowana jako różnica pomiędzy kątem as, określonym dla segmentu krzywej wyznaczonym punktami Pa i Ps, a kątem at określonym dla segmentu krzywej wyznaczonym punktami Ps i Pt (Rysunek 5.12). K - as - at (5.34) 4 x projekcja V5 Jv5 2vf+2 tłl+l 3^2*4 Rysunek 5.11: Krzywa cyfrowa związana zcftii- oraz y-projekcje 5.3.2 Krzywa a - s Niech kontur obiektu znajdującego się w obrazie tworzony jest przez pewną sekwencję punktów konturowych. Dla każdego punktu tej sekwencji, a jest kątem jaki tworzy styczna w danym punkcie konturu Reprezentacja linii konturowych i granic obiektów 111 a) b) Rysunek 5.12: Określenie parametrów krzywej cyfrowej / osią Ox, natomiast s jest długością konturu od punktu startowego PO punktu rozpatrywanego. Krzywa a - s (Rysunek 5.13) określa . reprezentację konturu i jest ciągłą wersją kodu łańcuchowego. Dla konturu zamkniętego, krzywa a - s jest periodyczna. Poziome •'drinki linii prostych krzywej a - s odpowiadają odcinkom linii pro-tych oryginalnego konturu. Inne odcinki linii prostych krzywej a - s • opowiadają łukom. Pierwsza pochodna krzywej a - s jest często wy-? nzystywana w procesie segmentacji konturu na quasi jednorodne seg-Baenty (odcinki linii prostych i łuki), ponieważ nieciągłości konturu oryginalnego objawiają się w przestrzeni da - ds w postaci lokalnych maksimów. 330 55 110 165 220 275 s- długość konturu w pikselach Rysunek 5.13: Krzywa a - s 112 Rozdział 5. Analiza obrazu 5.3.3 Reprezentacja konturu obiektu za pomocą współczynników Fouriera Rozpatrujemy krzywą cyfrową (kontur obiektu) przedstawioną w po staci parametrycznej x(n), y{n) n = 0,1, Wprowadzimy zmienną (zmienna okresowa z okresem N) (Rysunek 5.14) u(n) = x(n) + iy(n) (5.35) Oś urojona A u(n)=x(n)+iy(n) ^ Oś rzeczywista Rysunek 5.14: Krzywa cyfrowa - opis za pomocą współczynników Fouriera Dyskretna transformacja Fouriera (DFT) jest określona przez (n)=^?°(fc)exp(^) 0< n€ N (5.36) N-l a(k) =-- Y, u(n) exP 1 -^7- 0 < fc < iV n=0 (5.37) Zespolone współczynniki a(k) opisują kontur obiektu i są wykorzystywane w procesie rozpoznawania obiektów. Jeżeli kontur obiektu poddany został pewnym geometrycznym transformacjom, w wyniku których uzyskaliśmy nowy kontur opisany zmienną u(n), to współczynniki a(k) opisujące ten nowy kontur możemy otrzymać wykorzystując współczynniki a(k) (Tablica 5.3). W Tablicy 5.3 przyjęto następujące oznaczenia: uQ = xQ = t, Reprezentacja linii konturowych i granic obiektów 113 Tablica 5.3: Właściwości współczynników Fouriera Transformacja Kontur Współczynniki Fouriera Translacja u(n) = u(n) + UQ a(k) = a(k) + u05(k) Skalowanie u(n) = au(n) a(k) = aa(k) Obrót u{n) = u(n)em a(k) = a{k)e1^ ()db. zwierciadlane u(n) = u*(n)eiW + 2 a(k) = a*{-k)eiW + 2~i5 - 6$ jest kątem obrotu, - 6 jest kątem nachylenia prostej, względem której realizowane jest odbicie zwierciadlane, - ó(k) jest deltą Kroneckera. Z Tablicy 5.3 widać, że współczynniki Fouriera są inwariantne względem pewnych transformacji geometrycznych obiektu. I tak np. |5(fc)|, k = 1,2, ...,N - 1 jest inwariantne względem obrotu i "•Ibicia zwierciadlanego. S^-i jest inwariantne względem skalowania. Opis konturu obiektu za pomocą współczynników Fouriera może być wykorzystany do określenia podobieństwa konturów jeżeli mają niio różne rozmiary i orientacje (pasowanie konturów obiektów), .leżeli mamy dwa kontury reprezentowane odpowiednio przez zmienne u(n) i v(n), i opisywane odpowiednio przez współczynniki Fouriera a(k) i b(k), to kontury te są podobne jeżeli odległość d(u0, a, 0O) = min i V \u(n) - av(n)eie° - u0\ \ (5.38) uo>a>00 L=o J jest mała. Możemy określić minimalną odległość jak d = min|^|a(fc)-a6(A;)eieo|2| (5.39) 5.3.4 Interpolacja i aproksymacja krzywej konturu Rozpatrujemy krzywą reprezentującą kontur obiektu w postaci wyraźnej tj. y = F(x) i problem interpolacji i aproksymacji tej krzywej 114 Rozdział 5. Analiza obrazu za pomocą funkcji sklejanych. Niech sekwencja punktów konturowych jest określona przez (xo, yo), (xi, yi),..., (xn, yn) i niech X\ < Xj, jeżeli i < j (Rysunek 5.15). Funkcja f(x) jest funkcją sklejaną stopnia m, jeżeli spełnia warunki: - f(x) jest funkcją wielomianową rzędu mniejszego lub równego m w przedziale [zj_i,Xi|; (i = 1, n); - f(x) i jej pochodne do rzędu m - 1 są ciągłe w przedziale (xo, xn). Niech Pmti(x) oznacza funkcję sklejaną stopnia m w przedziale [xi-i,Xi] i niech P^r)j(x) oznacza pochodną r-tego rzędu. Punkty (xi,Ui), ? ? ? (xn-i,yn-i) są nazywane węzłami. Warunkiem ciągłości funkcji sklejanej jest J*2(Ą) = PSkifa) dla r = 0,l,...,m-l; i = 1,2,...,n-r 1(5.40) stąd Pm,i+i(x) = Pm,4(x) + Ci(a; - Xi)m (5.41) Błąd interpolacji w przypadku funkcji sklejanej stopnia 2k-l wynosi Ek = r{fk{x)}2dx (5.42) "'a-o W rozpatrywanym przypadku interpolująca funkcja sklejana przechodzi przez punkty tworzące kontur obiektu. W przypadku aproksymacji nie jest to wymagane, więc krzywa aproksymująca powinna spełniać następujące warunki: - przechodzić możliwie blisko wybranych punktów konturowych; - być krzywą gładką (Rysunek 5.16). Pierwszy warunek sprowadza się do warunku minimalizacji błędu średniokwadratowego Ey = JZiVi - f(xi)}2 (5.43) "=0 5.3. Reprezentacja linii konturowych i granic obiektów 115 (x" yj (x" y.) (x0. y.) Rysunek 5.15: Funkcja sklejana przechodząca przez punkty tworzące kontur obiektu Rysunek 5.16: Aproksymacja punktów konturu przez funkcję sklejaną Drugi warunek sprowadza się do minimalizacji wyrażenia (5.42). Najlepsza funkcja aproksymująca określona jest poprzez minimalizację ważonej sumy T = Ek + XEy (5.44) przy czym A jest pewną stałą. W przypadku krzywej przedstawionej w postaci parametrycznej, sekwencję punktów konturowych możemy aproksymować za pomocą funkcji B-sklejanej (Rysunek 5.17). Niech t będzie parametrem krzywej konturowej i niech x(t) i y(t) określają dany punkt tej krzywej. ()gólna B-sklejana funkcja interpolacyjna m-tego rzędu jest dana przez n X(t) J2 PiBi,m(t) i=-m+l (5.45) gdzie pi są współczynnikami, które należy określić (tzw. punkty kontrolne), B^m(t) i = 0,1,..., n; m = 1,2,... są funkcjami B-?sklejanymi m-tego rzędu, x(t) = [x(t),y(t)]T, pt = \pu,P2i]T- Funkcje B-sklejane mają następujące właściwości: 116 Rozdział 5. Analiza obrazu x", x" Rysunek 5.17: Aproksymacja punktów konturu funkcją B-sklejaną 1. Bi,m(t) jest najwyżej wielomianem (m- l)-rzędu w każdym pod-przedziale [?j,?j+1]; 2. Bi,m(t) = 0 dla t ^ ti; i ti+1 < t; 3- Bittn(t) ma ciągłe pochodne rzędu (m - 2); 4. B^m(t) określamy w następujący sposób Bim(t) = \\ k*), 1*2, "2J [rl,eĄ) (rf.af), (ł^.aC), ... Dla każdego punktu linii konturowej (x, y), kwantujemy przestrzeń parametrów 5.3. Reprezentacja linii konturowych i granic obiektów 123 a) b) Rysunek 5.25: Transformacja Hougha. Obraz wejściowy - (a), kontur (b), przestrzeń parametrów (c) , obraz odtworzony (d). Rysunek 5.26: Transformacja Hougha. Obraz wejściowy - (a), przestrzeń parametrów (b). P[x Myc Cmin ' ' ' Cmax J L^Cmin yCmax } a następnie dla kąta ó znajdujemy w R - tablicy wszystkie (a, r). Dla każdego (a,r) zgodnie z równaniem (5.61) obliczamy wartości [•^Cl He Znajdując lokalne maksima w F[a;c][yc], możemy określić położenie konturu obiektu - jeżeli P[xc][2/C] > T, wtedy kontur jest zlokalizowany w {xc,yc). W przypadku, gdy obraz wejściowy (obiekt) poddany jest działaniu transformacji afinicznych, takich jak skalowanie ze współczynnikiem s i obrót o kąt 0, to przestrzeń parametrów jest kwantowana następująco 124 Rozdział 5. Analiza obrazu y t styczna do (XrY) równoległa do osix / Rysunek 5.27: Uogólniona transformacja Hough'a -* [xCmin ??? Xcmax\[ycmin ••? 2/cmox j r min ••? "max\[Sr, Dla każdego punktu konturowego (x, y) i kąta 0 znajdujemy w R - tablicy wszystkie (a,r), a następnie dla "min <- " ^* "max; Oraz Smin T, wtedy kontur jest zlokalizowany w (xc,yc). 5.4 Detekcja punktów charakterystycznych obiektu W procesie rozpoznawania, cechy określające właściwości pewnych punktów obiektu, odgrywają bardzo ważną rolę. Dotyczy to charakte rystycznych punktów obiektu, które są punktami o dużej krzywiźnie. Punkty takie stabilnie określają położenie obiektu w poszczególnych obrazach sekwencji obrazów oraz umożliwiają określenie trajektorii ruchu obiektu w takiej sekwencji obrazów. Metody wydzielania takich punktów można podzielić na dwie grupy: 5.4. Detekcja punktów charakterystycznych obiektu 125 1. Pierwsza polega na wydzieleniu linii konturowych obiektu i ich opisie w postaci kodu łańcuchowego, a następnie poszukiwaniu punktów maksymalnej krzywizy z wykorzystaniem pochodnych cząstkowych względem x i y [72]; 2. Druga wykrywa charakterystyczne punkty obrazu o dużej krzy-wiźnie poprzez określenie lokalnej krzywizny definiowanej jako produkt modułu gradientu obrazu i zmiany kierunku gradientu [65],[5]. Niech fi i fj reprezentują pochodne cząstkowe obrazu /, czyli obrazy gradientu odpowiednio w kierunku i i j. Rozpatrujemy punkt obrazu p (punkt charakterystyczny) i jego otoczenie W (np. okno wymiaru 3x3 lub 5x5). Macierz C charakteryzuje strukturę poziomów jaskrawości i jest decydująca do określenia, czy punkt p jest punktem charakterystycznym o dużej krzywiźnie 2 C = Ylw fi 12W fifj Siy fifj Ylw fj w fi fi fi fj (5.62) Analizując wartości i wektory własne C możemy określić, czy dany punkt jest punktem charakterystycznym, ponieważ - wektory własne określają kierunek zmiany jaskrawości, - wartości własne określają amplitudę zmiany jaskrawości. Macierz C jest macierzą symetryczną i może być przedstawiona jako macierz diagonalna (np. przez rotację osi współrzędnych): C = Xi 0 0 A2 (5.63) gdzie X\ i A2 - nieujemne wartości własne Możemy rozpatrywać trzy przypadki: • otoczenie punktu jest obszarem o stałej jaskrawości - wartości własne Ai i A2 będą bardzo małe; • w otoczeniu punktu występuje idealny skok jaskrawości - mamy jedną wartość własną dużą i jedną małą (wektor własny związany z dużą wartością własną jest równoległy do kierunku gradientu obrazu); • 126 Rozdział 5. Analiza obrazu • otoczenie punktu zawiera dwa lub więcej kierunków zmian jaskrawości (np. punkt narożnikowy) - mamy dwie duże wartości własne (wektory własne są równoległe do kierunków gradientu). Przyjmując dla obrazu f(i,j) wymiar okna W określającego otoczenie rozpatrywanego punktu p, oraz wartość progową t dla wartości własnej A2, to procedura określająca punkty charakterystyczne (punkty o dużej krzywiźnie) może być przedstawiona w następujący sposób: - obliczamy gradient obrazu wejściowego /, - dla każdego punktu obrazu p: - obliczamy macierz C w otoczeniu W punktu p, - obliczamy A2 mniejszą wartość własną C, - jeżeli A2 > t, zapamiętujemy współrzędne punktu p na liście - sortujemy listę L w porządku zmniejszających się wartości A2, - przeglądamy posortowaną listę " z góry na dół", usuwając wszystkie punkty, które są w tym samym otoczeniu W punktu p. W wyniku powyższej procedury uzyskujemy listę punktów charakterystycznych, dla których A2 > t i które posiadają rozłączne otoczenia. Punkty charakterystyczne (punkty o dużej krzywiźnie) możemy wyznaczyć wykorzystując tylko pierwsze pochodne [70]: Trącej Det(C) V gdzie C jest macierzą c = Ji JiJj ?2 . fi/j Jj . (5.65) a / oznacza obraz / po filtracji filtrem gaussowskim czyli f = e -&-(r)f. 5.4. Detekcja punktów charakterystycznych obiektu 127 Jeżeli pierwsze pochodne mogą być aproksymowane przez szereg Taylora pierwszego rzędu to Ja JiJj JiJj Jjj + az C = Ji JiJj JiJj Jj Harris [65] definiuje Rij = Det(Ć) - kTrace2(Ć) (5.66) (5.67) i dla k = 0.04 definiuje punkty charakterystyczne (punkty o dużej krzywiźnie) jako punkty, dla których mamy max Rij. Na Rysunku 5.28 przedstawiono punkty charakterystyczne obrazu wydzielone przy wykorzystaniu operatora Harrisa. d) Rysunek 5.28: Punkty charakterystyczne obrazu wydzielone operatorem Harrisa. Obrazy wejściowe - (a)(c), punkty charakterystyczne (b)(d). 128 Rozdział 5. Analiza obrazu 5.5 Reprezentacja obszarów obiektów W systemach komputerowej wizji można obliczyć szereg parametrów charakteryzujących obiekty obrazu - w szczególności na podstawie obrazu binarnego. Przetwarzanie obrazów binarnych wymaga znacznie mniejszych pojemności pamięci i mniejszych mocy obliczeniowych w porównaniu z systemami wykorzystującymi obrazy o wielu poziomach jaskrawości. Szereg operacji przetwarzania obrazów binarnych jest realizowanych jako operacje logiczne, wobec czego czas przetwarzania znacznie się redukuje. Na podstawie obrazu binarnego uzyskuje się informacje niezbędne do rozpoznawania obiektów, przy czym otoczenie obiektów może być i jest odpowiednio kontrolowane. W podrozdziale tym omawiamy metody reprezentacji obszarów obiektów za pomocą: - długości serii elementów, - projekcji, - drzew czwórkowych i piramidy obrazów. 5.5.1 Reprezentacja obszaru za pomocą długości serii elementów Obszar obiektu może być przedstawiony za pomocą określenia długości serii elementów o wartości 1 w kolejnych liniach obrazu. Seria elementów obrazu może być określona poprzez (Rysunek 5.29): - podanie współrzędnej j pierwszego elementu 1 serii oraz długości serii w każdym i-tym wierszu obrazu; - podając tylko długość serii elementów 1. Zawsze rozpoczynamy od podania długości serii elementów 1 co oznacza, że jeżeli i-ta linia obrazu rozpoczyna się od elementów 0 to długość serii elementów 1 jest równa 0. Jeżeli wykorzystujemy drugą konwencję i jeżeli rik oznacza długość fc-tej serii w i-tym wierszu obrazu, a mi jest liczbą serii w i-tym wierszu, to powierzchnia wszystkich obiektów może być obliczona przez sumowanie wszystkich serii elementów 1 rrtj -1 71-1 2 A = E E r*,2fc+i (5.68) j=0 fc=0 5.5. Reprezentacja obszarów obiektów 129 0000000000 (0,0) 0,10 0001100111 (4,2) (8,3) 0,3,2,2,3 0011100110 (3,3) (8,2) 0,2,3,2,2,1 0010110111 (3,1) (5,2) (7,3) 0,2,1,1,2,1,3 1011100010 (1,1) (3,3) (9,1) 1,1,3,3,1,1 1101100000 (1,2) (4,2) 2,1,2,5 0110000000 (2,2) 0,1,2,7 01 00000000 (2,1) 0,1,1,8 1 100000000 (1,2) 2,8 0000000000 (0,0) 0,10 a) b) c) Rysunek 5.29: Określenie serii elementów obrazu Na podstawie długości serii elementów 1 można w łatwy sposób uzyskać różnego rodzaju projekcje obiektów (np. horyzontalną) (Rysunek 5.30). (0,0) 0 (4,2) (8,3) 5 (3,3) (8,2) 5 (3,1) (5,2) (7,3) 6 (1,1) (3,3) (9,1) 5 (1,2) (4,2) 4 (2,2) 2 (2,1) ?\ (1,2) z n (0,0) U Rysunek 5.30: Horyzontalna projekcja dla fragmentu obrazu z Rysunku 5.29a 5.5.2 Projekcje Projekcja elementów obrazu na pewną oś określona jest poprzez podanie liczby elementów obrazu wpadających do zadanego przedziału na tej linii. Projekcje są zwięzłą reprezentacją obrazu, zachowującą dużo informacji możliwych do wykorzystania na dalszych etapach przetwarzania obrazu, przy czym należy sobie zdawać sprawę, że wiele różnych obrazów może mieć takie same projekcje na określone osie. 130 Rozdział 5. Analiza obrazu Projekcja H[i] wzdłuż wierszy obrazu i projekcja V[j] wzdłuż kolumn są określone przez M N H[t\ = Y.Khi) ; V[j} = Y,b(i,j) (5.69) gdzie obraz ma wymiary M x N. Można pokazać, że moment pierwszego rzędu obrazu jest równy momentowi pierwszego rzędu jego projekcji. Ponieważ określenie położenia pewnego obiektu wymaga podania współrzędnych środka ciężkości, to możemy to zrobić na podstawie odpowiednich projekcji ,=S^;I=5kffi! (5.70) gdzie A = EV[j} = ±H\i] (5.71) j=i i=i Określenie orientacji obiektu wymaga znajomości momentów drugiego rzędu, które można określić na podstawie znajomości projekcji diagonalnej (Rysunek 5.31). Jeżeli PQ jest projekcją przekątnej AB obrazu na oś OR przy zadanym kącie 9k , to TQ = nV2cos(45°-8k) (5.72) Podzielimy odcinek PQ na n równych części P/a, Pk2- ? • ?, Pkn- Dowolny element obrazu (i,j) przydzielamy do zbioru D(k-i)N+u jeżeli projekcja Ptj tego elementu spełnia warunek (Z - l)V2cos(45° - ek) < Ptj < /V2cos(45° - dk) (5.73) 5.5.3 Reprezentacja hierarchiczna za pomocą drzew czwórkowych i piramidy obrazów Hierarchiczna struktura obrazu ma postać piramidy lub drzewa. Ujemną stroną takiej reprezentacji jest niezachowanie geometrycznych relacji między elementami obrazu. Jeżeli jednak na kolejnym etapie procesu przetwarzania obrazu, wykorzystujemy globalne parametry 5.5. Reprezentacja obszarów obiektów 131 Rysunek 5.31: Diagonalna projekcja elementów obrazu obrazu, ważne jest zachowanie struktury obrazu, a nie struktury indywidualnych elementów. Rozpatrujemy obraz o wymiarze 2n x 2n elementów przedstawiony na Rysunku 5.32i zdekomponujemy go na szereg podobrazów. Na danym poziomie przetwarzania możliwe są trzy przypadki: a) każdy element analizowanego podobrazu posiada zerową wartość jaskrawości, b) analizowany podobraz zawiera zarówno elementy o zerowej, jak i różnej od zera wartości jaskrawości, c) analizowany podobraz nie zawiera elementów o jaskrawości równej zero. W przypadku a) podobrazy nie są dalej poddawane procesowi dekompozycji i dalszego przetwarzania, w przypadku b) następuje dalsza dekompozycja podobrazu na kolejne podobrazy, natomiast podobraz spełniający warunek c) poddawany jest dalszemu przetwarzaniu (Rysunek 5.33 b) i c)). Innym sposobem hierarchicznej reprezentacji obrazu jest tzw. piramida obrazów. Obraz oryginalny 2n x 2(tm) elementowy jest dzielony na. niezachodzące na siebie bloki 2x2 elementowe. Każdy kolejny obraz o wymiarze o połowę mniejszym tworzy kolejny poziom piramidy (Rysunek 5.34) - elementy obrazu tego poziomu posiadają jaskrawość 132 Rozdział 5. Analiza obrazu Obraz Reprezentacja czwórkowa O 1 2 3 A AK <3)(c)(r) AK Rysunek 5.32: Zasada reprezentacji obrazu za pomocą drzew czwórkowych np. będącą średnią jaskrawością elementów każdego bloku 2x2 elementowego. Algorytm tworzenia piramidy obrazów jest następujący: 1. Obraz oryginalny tworzy poziom k piramidy i niech k = n czyli "k "ni 2. Tworzymy obraz poziomu fc - 1 *'ł_iittłii±i = j (5.74) gdzie i,j = 1,3,. ..,2* - 1. 3. Jeżeli k = k - lifc^Oto powtarzamy krok 1. Rekonstrukcja obrazu oryginalnego realizowana jest w następujący sposób: 1. Najwyższy poziom piramidy ma poziom fc, 2. Elementy obrazu poziomu fc + 1 posiadają wartości jaskrawości 1. j. Tekstury i parametry opisu tekstur 133 1 2 3 4 a) 12 3 4 c) Rysunek 5.33: Hierarchiczna reprezentacja obrazu metodą drzew czwórkowych określone przez Fk,i,j+i = ^fc-i,i±ł 2+1 Fk,i+i,j - Fk_ltti:i+i Fk,i+i,j+i = Fk_lti±iti±i (5.75) 3. Procedura kończy się jeżeli k = n 5.6 Tekstury i parametry opisu tekstur Teksturą określamy przestrzenną organizację elementów obrazu uwarunkowaną statystycznym rozkładem jaskrawości elementów w pewnym obszarze obrazu [51]. Tekstury można scharakteryzować za pomocą [52] 134 Rozdział 5. Analiza obrazu M7 k=0 k=1 k=2 Rysunek 5.34: Tworzenie piramidy obrazów przestrzennej funkcji autokorelacji Air ? -\ - ^(tm)=J-W ^ntj-w f(m, n)f(m -Cn-rj) {^hJ) ' S25-HrliSlirl/(m.")Ja (5.76) obliczanej w obszarze o wymiarach (2W + 1) x (2W + 1) dla każdego punktu obrazu o współrzędnych (i, k) i dla C,i/ = 0,±l,±2ł.... Przy ustalonym przesunięciu (?, 77) największe wartości A(C,,r];i,j) odpowiadają obszarowi największej ziarnistości tekstury T(ij)= E E cV^(c,w<,i) C=-hr)=-h (5.77) tj. rozmiar ziarna tekstury jest proporcjonalny do funkcji autokorelacji. parametrów wykorzystujących transformację Fouriera obrazu cyfrowego f(i,j) 'i 6. Tekstury i parametry opisu tekstur 135 i M N 1< u < M, 1 < u < iV (5.78) Ponieważ radialna reprezentacja widma mocy (\F\2 = FF*) jest zależna od ziarnistości obrazu, to system parametrów może składać się z wartości widma uśrednionych w przedziałach okręgów, środki których znajdują się w początku układu współrzędnych $n,r2=E\F(u'v)f rf < u2 + v2 < r2, 1 < u < M, 1 < w < iV (5.79) *^=i:i^("ł")is 0i• ?' 11 > ?' / J' / ii K:ittir~ W^ *l W' W S TT AX a #? im ii \0.n d f(x+Ax,y+Ay) 6 0 2 .< 5 0 5 \ 0 4 2 1 1 2 4 4 n D Rysunek 5.36: Macierz Ps,g(i,j). 2. moment drugiego rzędu (miara homogeniczności obrazu) V2= E E[Ps,e(ki,k2)}2 ki=Ik2=l 3. współczynnik korelacji (5.83) /*3 axay (5.84) gdzie /j,x, jj,y,ax,ay - wartości średnie i dyspersje obliczone dla wierszy i kolumn macierzy Ps,e(ki, k2) Tekstury i parametry opisu tekstur 137 4. entropia K K 1*4 = ~ E E psAkuk2)logPs,e(ki,k2) (5.85) 5. wariancja K K *i=l A2=l (5.86) 6. moment różnicowy ft"??i+ft-w (5-87) 7. średnia wartość sumy 2A" K K ^ = E k E E A,*(*i, fe2) ; *i + *2 = k (5.88) *=2 fci =1*2=1 8. wariancja sumy 2K K K ^8 = E^-^)2E T.PiAki-k-2) )kl + k2 = k (5.89) fc=2 ki=lk2=l 9. entropia sumy 2/T K K K K "9 = - E E E Ą."(*i, fc) iog[E E Ą#(*I. **)] k=2k!=lk2=l ki=lk2=l k\ + k2 = k (5.90) 10. wariancja różnicowa M10 = E [* - E ' E E fi*(*i. **)P E E Ąf(*i. W (5-9!) A:=0 i=0 fc1=lfc2=l fcl=lfc2=l l&i - &2I = ^ |^i - k2\ = k 138 Rozdział 5. Analiza obrazu 11. entropia różnicowa ry- i PC PC PC PC Cn = -EEE PsAkuh)log[Y: E PsAknki)} (5.92) fc=0 fcl = l fc2 = l fcl=l fc2 = l ^12 12. informacyjna miara korelacji HXY - HXY1 max{HX, HY} (5.93) 13. ^13 = (1 - exp[-2(HXY2 - HXY)}^ gdzie (5.94) HXY = (iA (5.95) K K K HX = ~ E [ E psAkx, k2)} log[ ? Pwfa, k2)} (5.96) fci=l fc2 = l fc2=l K K K HY = - E [ E Ą*(*i, *2)] log[ E *M*i, k2)} (5.97) fci = l 1(3=1 fe1 = l PC PC HXY1 = -J2 T,psAki,k2)- fc2=ifc1=i K PC iog[C?, PsAku k2))C? PsAh,k2))] ti=i fc2=i (5.98) /JXK2 = - E E (E ^M(*I. **))( E Ą#(*I, **)) • *i=l fca=l fci=i fc2=i A' A- • log[( E PsAh, k2))( E PsAh, k2))} (5.99) 5.6. Tekstury i parametry opisu tekstur 139 Tablica 5.4: Parametry tekstury obrazu Klucze Obraz Klucze Parametr e 6=1 5= 10 Kontrast Mi 0 1687918.3189735413 1.5658088891147614E7 90 631694.5310134888 1.997868569965744E7 180 1187326.409374237 1.6654923693756104E7 270 2837879.946910858 3.0519982911361694E7 Moment fJ-2 0 10250.04367494362 1388408.0167295139 90 15380.034707642539 1227618.0196717763 180 39330.04367536679 3558200.016760735 270 22626.034707747982 2064212.0196839531 Korelacja M3 0 -1341875.5303634775 -1.181355807458559E8 90 -1076049.7421851608 -1.2628679015749444E8 180 -659085.3497722034 -7.20737308227905E7 270 -877567.3507217962 -9.565040046810706E7 Entropia (i4 0 -1159.6366876635943 -23499.426078829212 90 -1417.5753383130366 -23601.10643640572 180 -1801.6054243677502 -28529.09537104104 270 -1508.9410457471784 -25961.340868643558 Moment różnicowy ^6 0 2.506153524619726 16.766814363691054 90 2.7692983520244936 17.510092993713638 180 2.2893923488876164 12.834270046549358 270 2.5545489990695622 15.310839924252956 (5.100) (5.101) (5.102) (5.103) Teksturę można charakteryzować poprzez długość serii, tj. liczbę elementów wiersza obrazu, posiadających stałą jaskrawość. Pg(k,l) oznacza w tym przypadku liczbę linii o długości Ij , zorientowanych pod kątem 6 , składających się z punktów o jaskrawości k . Mamy w tym przypadku następujące parametry Y.kil2Pe(k,l) LRE EkiPe(k,l) GLD ZkiZiPejkJ))2 ZkiPe(k,l) RLD = Ei(EkPe(k,l))2 ZkiPe(k,l) RPC = ZkiPe(k,l) M x N 140 Rozdział 5. Analiza obrazu Rysunek 5.37: Wkręty metalowe 5.7 Momenty geometryczne Momenty geometryczne mogą być z powodzeniem wykorzystane do określenia zarówno cech jak i orientacji obiektów w procesie ich rozpoznawania. Jak już wcześniej wspominaliśmy, rozpoznawanie obiektów na podstawie ich cech powinno być niezależne od położenia, rozmiaru i orientacji obiektu. Jedną z możliwości rozwiązania tego problemu jest wykorzystanie, w charakterze cech obiektów, ich momentów geometrycznych. Niech f(x, y) > 0 jest rzeczywistą funkcją reprezentującą jaskrawość obrazu w punkcie o współrzędnych (x,y). Moment rzędu (p + q) tej funkcji określamy przez r r+OO mpq= I J f(x,y)hpq{x,y)dxdy (5.104) gdzie hpq(x,y) jest pewnym wielomianem w którym x jest stopnia p, natomiast y stopnia q. Jeżeli hpq(x, y) = xvyq to rozpatrujemy momenty geometryczne funkcji f(x,y). Jeżeli funkcja generacji momentów jest określona przez r r+oo M(u,v)- l I f(x,y)exp(xu + yv)dxdy (5.105) J J-oc to momenty określamy wzorem mpq = ---y^- (5.106) p,q bv?8ifl 5.7. Momenty geometryczne 141 Tablica 5.5: Parametry tekstury obrazu Wkręty metalowe Obraz Wkręty metalowe Parametr e S=l 5 = 10 Kontrast fil 0 8537979.79075241 7.342371701238632E7 90 6959236.397964478 7.216099258395004E7 180 7669397.477386475 7.488239657678604E7 270 7253170.519229889 6.5469008056152344E7 Moment /"2 0 2438.000687827356 218804.0002363859 90 2694.000905335677 200476.00026824477 180 2488.0006878280838 201798.00023614196 270 2430.0009053318354 217144.00026848057 Korelacja #5 0 -3188904.3493224056 -3.917675330286808E8 90 -2933253.18384677 -4.2663539037669903E8 180 -3134217.606864619 -4.238191878949137E8 270 -3195615.7541388553 -3.9455927329559535E8 Entropia 0 -680.9025735642138 -18094.15549001349 90 -723.0171448672497 -17723.274771629625 180 -696.7102790046869 -17783.53946849112 270 -675.4424660570187 -18077.305592722176 Moment różnicowy ^6 0 0.23359607275883365 0.6830140240544869 90 0.3357769558003752 0.8444481491412067 180 0.2415447664385665 0.718393997624081 270 0.327523382860279 0.8670944749031664 Nieskończony zbiór momentów {mP:q, p,q = 0.1,...} jednoznacznie określa f(x, y) i odwrotnie. Mówimy, że jeżeli f(x, y) jest odcinkami ciągła i ma niezerowe wartości w pewnym obszarze płaszczyzny x - y, wtedy momenty wszystkich rzędów istnieją i sekwencja tych momentów jest jednoznacznie określona na podstawie f(x,y), jak również sekwencja {mp,q} jednoznacznie określa f(x,y). Mamy r r+oo f(x,y)= / / exp{-j27r(xu + yv)} -00 oo oo (5.107) Momenty centralne są określone przez r r+OO VP,q = j I (z~ x)P(y ~ V)qf(x, y)dxdy (5.108) 142 Rozdział 5. Analiza obrazu gdzie m00 m00 Dla obrazu cyfrowego HA = ? X> " *)*(" - P)V(*,") (5-110) Momenty centralne rzędu 3 przy wykorzystaniu zależności (5.104) określamy w następujący sposób A*oo = m0o (5.111) A*io = m0i ?(m00) = 0 (5.112) m00 Moi = m0i - (m00) = 0 (5.113) m00 "iiomoi _ (KI-,A\ /J-n=mu = mn-ym10 (5.114) m00 2m?0 m?0 m\Q _ ,_ ,,_. A*20 = m20 - H - = m20 - = m20 - xm10 (5.115) m0o m00 m0o Tfi A*02 = m02 - = m02 - ym0i (5.116) m00 ^30 = m30 - 3xm20 + 2mwx2 (5.117) Mi2 = mx2 - 2frmn - xm02 + 2y2mi0 (5.118) M21 = m2ł - 2xmn - ym-20 + 2x2ra0i (5.119) ^03 = m03 - 3ym0i + 2m0iy2 (5.120) natomiast znormalizowane momenty centralne otrzymujemy uwzględniając VPQ = ** (5-121) Ho gdzie 7 = \{p + q) + 1 dla p + q = 2, 3,.... 5.7. Momenty geometryczne 143 Znajomość momentów centralnych pozwala na określenie pewnych parametrów, będących kombinacją momentów centralnych, które okazują się inwariantne względem obrotu i translacji. Znormalizowane momenty centralne umożliwiają określenie parametrów, które są dodatkowo inwariantne względem zmiany skali. Zdefiniujemy pierwsze siedem kombinacji momentów centralnych rzędu 3, które w literaturze występują pod nazwą momentów Hu[38] 0i = 020 + 002 (5.122) 2 = [020 - 0o2]2 + 4tfi (5.123) 3 = [030 - 3yU02J2 + [3/i2i - 0o3]2 (5-124) 4 = [030 + 012]2 + [021 + 0O3]2 (5.125) 05 = [030 - 30i2][03O + 012][(030 + 012)2 - 3(^21 + 0O3)2] + /g ^ + [3021 - 0O3][021 + 0O3][3(03O + 012)2 ~ (021 + 0O3)2] 06 = [020 - 002] [(030 + 012 )2 - (021 + 003 )2] + +4011 [030 + 012] [021 + 003] (5.127) 07 = [3021 - 003] [030 + 012] [(030 + 012)2 - 3(02i + 0O3)2] /g 12g\ -[003 - 30i2][021 + 0O3][3(03O + 012)2 - (021 + 0O3)2] Należy zauważyć, że pojęcie parametrów inwariantnych dotyczy funkcji ciągłych, natomiast w przypadku obrazu dyskretnego in-wariantność względem translacji, obrotu i zmiany skali zachodzi z pewnym błędem, który został określony w [107]. W systemach komputerowej wizji często wykorzystuje się tzw. momenty Zernike[114], definiowane w następujący sposób - n + 1 -f*-nrn f[ f(x,y)V;m(p,8)dxdy (5.129) TT J Jx2+y gdzie f(x, y) jest jaskrawością obrazu w punkcie o współrzędnych (x,y), V^m(p,9) - Rnm(p)ejme we współrzędnych biegunowych 144 Rozdział 5. Analiza obrazu parzystą. (5.130) x = (p,0),n^Oin - \m\ jest liczbą całkowitą, dodatnią i Współrzędne biegunowe są określone przez pcosd i y = psinO Rnm{p) jest wielomianem zdefinio wanymwfll4jprzez (n-|m| Rnm{p)= ? -~iz})li(l>LZjRpn~2s Łatwo stwierdzić, że V;22(p,0)=p2ej20 (5.131) (5.132) mm*r ^"rzystywane " momemy 2espoione_ ^^ e na- J = \Z=T. C - -JDx+3vnx-3vmx,y)dxdy idzie p i q są nieujemnymi liczbami całkowitymi i 7 = \/-i We współrzędnych biegunowych /?27T /-OO , 0)pdpde Jo Jo gdzie /(/?, 9) = /(ar cos #, j/ sin (9). Dla obrazu dyskretnego (5.133) (5.134) Cpq = 27r22 PP+Q+1 0 gdzie cg-p(p) (5.135) J 2n P)P) (5.136) 5.7. Momenty geometryczne 145 Na bazie momentów zespolonych możemy określić parametry in-wariantne Tl - r2 x2 - c2 °11 #3 = r2 #4 = ^ #5 = c2 w °11 *6 Cu "V = S #8 = 5^ (5-137) cn Wi °n '-ii *13 Cu (5.138) (5.139) (5.140) CP, = ? Z P"+1 c°s tf/fo *) (5-141) p

f(p, 4>) S'pq cos q$ + Ćpq sin q9 EPE*f(p,<ł>) gdzie S' 9pq = arctg-^ 4 = EE/^ ^n (70/00, "*) (5-142) P 4> p = 0,1,2,..., 0<2 1.8?-009 1AE - 009 1.8E - 009 1.8^-009 h -6.0^-030 -7.1?-030 ~5.8?-030 -l^-OSO 06 5.5E - 020 4.8E - 020 -9.5?-020 2.2E - 020 07 8.2E - 030 8.6E - 030 3.9E - 030 1.4E - 030 5.8 Morfologiczne operacje przetwarzania obrazów Matematyczna morfologia jest teorią matematyczną wykorzystywaną do analizy i opisu kształtów oraz studiów nad formą i strukturą obiektów. W chwili obecnej daje się zauważyć wyraźna tendencja do wykorzystania teoretycznej bazy pojęciowej matematycznej morfologii w procesach przetwarzania obrazu. Podstawowymi operacjami matematycznej morfologii są operacje nad zbiorami - obrazy będą więc traktowane jako zbiory punktów w przestrzeni [91]. 5.8.1 Morfologiczne operacje przetwarzania obrazów binarnych Morfologiczne operacje przetwarzania obrazów można podzielić na : unarne, dyadyczne i tzw. geometryczne transformacje obrazów. Unarne morfologiczne operacje przetwarzania obrazów obejmują dopełnienie, odbicie zwierciadlane i translację (przesunięcie w danym kierunku) (Rysunek 5.39). Dyadyczne morfologiczne operacje przetwarzania obrazów polegają na przetworzeniu dwóch obrazów w jeden. Z teorii zbiorów wynika, że takimi podstawowymi operacjami są suma, iloczyn (przecięcie) i różnica zbiorów. Odpowiada to logicznym operacjom OR, AND i ExclusiveOr. Morfologiczne operacje określane jako tzw. geometryczne transformacje obrazów to m.in. operacje dilation i erosion. Podstawowe operacje matematycznej morfologii mogą być łączone w bardziej złożone sekwencje. Niech EK będzie K wymiarową przestrzenią euklidesową i A C EK 148 Rozdział 5. Analiza obrazu i B C EK są zbiorami w tej przestrzeni z elementami a i b odpowiednio a = (ty,..., OK) i 6 = (&i, &25 • • • j bx). Zbiór Ac nazywamy dopełnieniem zbioru A jeżeli AC = EK-A (5.144) Zachodzi więc aeAc = (aeAf = a^A (5.145) Translację, czyli przesunięcie zbioru A C ?7* o wielkość t będącą elementem EK definiujemy jak At - {y\dla pewnego a ? A, y = a + t} (5.146) Jeżeli t jest wektorem w przestrzeni EK , wtedy A jest przesunięciem wzdłuż wektora t. Dla A C EK i t pewnego rzeczywistego elementu EK, mnożenie skalarne określamy wzorem tA = {ta\a G A} (5.147) Odbiciem zwierciadlanym zbioru A jest zbiór określony przez (5.131) ~A = {-a\aeA} (5.148) Minkowski w 1903 roku [60] bez formalizmu matematycznego wprowadził operacje dodawania zbiorów, które w 1950 roku Ha-dwiger [32] nazwał operacjami "suma Minkowskiego" i "różnica Minkowskiego". W roku 1975 Matheron [58] wprowadził na określenie "sumy Minkowskiego" symbol (c), "różnicy Minkowskiego" symbol 0, zdefiniował operację przesunięcia zbioru A jak At - A (c) {t} i zmodyfikował definicję "różnicy Minkowskiego". Inną szkołą wprowadzającą swoją terminologię związaną z operacjami morfologicznymi to szkoła związana ze Sternbergiem oraz Haralickiem [112]. Dla dwóch obrazów A i B z EK operacja dodawania Minkowskiego (suma Minkowskiego) jest określona przez [120],[60],[58] • {a + b:aeA,beB} (5.149) • A(r)B = {a + b:a€A,beB} (5.150) • 5.8. Morfologiczne operacje przetwarzania obrazów 149 a) O=(0,0) ł * c) Rysunek 5.39: Unarne morfologiczne operacje przetwarzania obrazów: a) translacja, b) dopełnienie i c) odbicie zwierciadlane A(r)B= U Ab b€B (5.151) A (c) B jest więc sumą uogólnioną wszystkich wyników przesunięcia zbioru A o wartość każdego elementu zbioru B. Odejmowanie Minkowskiego (różnicę Minkowskiego) określamy przez • {z:z + beA,beB} (5.152) • AeB = {z: (-B)z cA} = {z:z-beA,beB} (5.153) A 9 B = {z : {B)z CA} = {z:z + beA,beB} (5.154) • AeB= f]Ab (5.155) b€B 150 Rozdział 5. Analiza obrazu A 0 B jest iloczynem uogólnionym wszystkich wyników translacji A o wartość każdego elementu zbioru B. Operacja dodawania Minkowskiego posiada właściwości przemiennośc i i łączności, i jest inwariantna względem przesunięcia. Operacja różnicy Minkowskiego jest również niezależna od przesunięcia. Operacje sumy Minkowskiego i różnicy Minkowskiego są operacjami dualnymi A(r)B=[AC QB]C (5.156) AQB = [AC (r)B]C (5.157) Będziemy rozpatrywali obrazy przedstawione na Rysunku 5.40. Rysunek 5.40: Obraz oryginalny a) i obraz binarny b) Operację erosion określamy jako[55],[97],[58] • A 0 {~B) = {z : Bz C A} = {z : z + b € A,b € B} (5.158) • e{A,B) = AQ{B)= p| A_b (5.159) b€B gdzie B jest elementem strukturalnym. Operację dilation określamy jako • A (c) (~B) = {z : A n Bz =? 0} = {a - b : o G A, b e B} (5.160) • Ó(A, B) = SB= U Ab = {z e EK : (-B)z n A ^ 0} (5.161) beB ') 8. Morfologiczne operacje przetwarzania obrazów 151 A9B AGB & d/8 B=B 0 ccc 1 1 E * 1 1 1 0 9 > i 1 1 1 o tl łl t • 0 0 5 i ii 1 s o o UD o c o o c o o o a o " 0 0 9 0 0 0 0 s co oo al O C O 6 O O O O O u o o o Rysunek 5.41: Operacja erosion Operacja dilation, w ogólności powoduje, że obiekt rozszerza się lub zwiększa rozmiar, operacja erosion powoduje zwężanie obiektu (Rysunki 5.41 i 5.42).Zakres rozszerzania i zwężania zależy od wyboru elementu strukturalnego, co więcej operacje te bez określenia obiektu strukturalnego nie mają sensu. Element strukturalny może być 4- lub 8-połączonym zbiorem A^4 lub JV8. (Jeżeli obiekt A jest L-połączony przy czym L = 4 , 6 lub 8, wtedy Ac jest obiektem połączonym 12 -L). Operacja dilation i operacja erosion mają następujące właściwości. Dla elementu strukturalnego B i dwóch obrazów obiektów Ax i A2, przy czym A± C A2, mamy: 6(Ai,B) C 6(A2,B) (5.162) 152 Rozdział 5. Analiza obrazu AeB A0B -B=B Symetryczny element strukturalny ,d/8 0 0 0 0 0 e 0 0 0 0 e 0 s 0 0 0 ; o o o o o 0 0 0 I' 0 0 S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000 00 00000 S i t 1 0 0 0 0 0 0 0 OJ oso DDE Ts i i 0000006 Ot u El n c c o o o o o o c 1 1 I li 1 : n r.H li t HL* f - ! 1 ! 11 1 BBŁ'1 ii > t " i I 1 1 1 1 ' D 0 "BI] 0 0 0 0 ' i j i i li 1 1 ! 1 < 0 0 0 0 0 0 o c-E T 111 1 0 0 0 0 0 0 ' ' 0 0 0 0 0 0 ? 11 11 1 U' 0 ?j I 0 0 0 0 0 0 0 0 M' ' 1 t 0 osoo ST 1 OC 0 0 0 0 o u lit u 0 0 0 0 0 i ' ' 1 ? 0 0 0 Bill 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ! ' ' 0 0 01 0 0 0 cl 1 t tTt • ! 1 i ' s 1 o o oj 0 0 0 'ii I 1 l| t 1 1 - i i : 1 0 0 01 0 0 0 0 0 0 C nnnn nn 0 0 0 0 0 1 ' s 1 o o oj 0 0 0 0 0 0 0 0 0 0 '• 0 0 0 1 0 i°t to: Rysunek 5.42: Operacja dilation e{Al,B)ce{A2,B) (5.163) Jeżeli mamy dwa elementy strukturalne Bi i B2, takie że Bi C B2. e(ĄB!)De(Ą52) (5.164) Przy tworzeniu efektywnych implementacji morfologicznych filtrów wykorzystywane są właściwości dekompozycji A(r)(B{JC) = {A(r)B)U(A(r)C) = {BUC)(r)A (5.165) Ae(Buc) = (AeB)n{Aec) (5.166) 5.8. Morfologiczne operacje przetwarzania obrazów 153 Bi j_ Hf i t 1 ? ;' 1 i"| EP-;JJ|I:":-WJBHI ii' i t Ff 1 : 'IB L i iii i .' UĄl iSjElf wł liii' t-fm Obraz oryginalny Obraz po operacji erosion Obraz po operacji opening i mi o .i o > o o nn o 3 DDDD ° * ł B ° :' ° ° ° ? -3 Q a i) oQ a i U Mmii 0 0 0 0 D 0 U 9 i} a a o i > BU u o u o flBfl " B o o ' '-' a a o o o o ił a o a ił ił n ? 'Di • * El 0 0 0 0 0 0 O O O ') O U BB D 0 0 0 0 0 • 9 ? 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 88 u > 0 0 0 0 o o B o 1 " ? ? 0 <ł fi 0 on IHI BOB o o U BU IUU uu UU Bflo o ' BD UU UU uu UU Bo aa DBB OD DB nu a a a o ? a n o o oni 0 0 0 0 o 0 OH o o o o Hall U o o o oD o a o o o DDI o o o o o o o BUDDO '? I -' a ł|l|| a o a o -? o BBBBDBI o o o o o O O O 0 O O O O O O O O O i b) Rysunek 5.43: Operacja opening a) i closing b) (A Q B) e c = A e (B e c) nB={B(r)B(r)B...(r)B) (5.167) (5.168) Operacje opening i closing definiujemy następująco (Rysunek 5.43): i) operacja opening o(A, B) = [Ae (-B)} (c) B ii) operacja closing c(A, B) = [A(r) (-B)] 0 B (5.169) (5.170) (5.171) (5.172) Uwzględniając wprowadzone wcześniej pojęcia operacji dilation i erosion, można wprowadzić następujące zależności: o(A,B)=6{?(A,B),B] c(A,B) =e[S(A,-B),-B] M 5.8. Morfologiczne operacje przetwarzania obrazów 155 Ml 0 Rysunek 5.45: Operacja dilation: a) , b) i c) przy wykorzystaniu elementu strukturalnego B - NĄ, odpowiednio dla B, 2B, 35; d), e) i f) przy wykorzystaniu elementu strukturalnego B = N% dla B, 25, 35. Odpowiednio dla operacji opening i operacji closing oraz elementu strukturalnego FZ? i obrazów A, A%, A2, gdzie ^ C ^42 mamy: (5.177) (5.178) I bo Rozdział 5. Analiza obrazu o(o(A, B),B) = o(A, B) (5.179) i ACc(A,B) (5.180) c(Ai,B) Cc(A2lB) (5.181) c(c(A,B),B) = c(A,B) (5.182) Kolejną operacją z grupy tzw. transformacji geometrycznych obrazu jest morfologiczna operacja hit-and-miss zdefiniowana przez Serra [91J. Dla obrazu A i dwóch elementów strukturalnych Ą i B2 operacja hit-and-miss jest zdefiniowana przez HitMiss(A, B1}B2) = e(A, Bx) D ?C(AC, B2) (5.183) gdzie B1!lB2 = 0. Operacja hit-and-miss jest morfologicznym ekwiwalentem operacji pasowania wzorców. Wynik powyższej operacji przedstawiono na Rysunku 5.46. Informacja o obiektach zawarta jest w ich konturach lub też obiekt może być też reprezentowany przez swój szkielet (zarys). Kontur obiektu (Rysunek 5.47) otrzymujemy przez zastosowanie następujących operacji a A = A - e(A, N4) (5.184) stna,wieW" " ,1--*CW*J J 'pusty- ** *w m s% f" * POd2blór S2kieIet Jest sumą pod2hin , <* Podzbiorów szkieletu Szkielet ,w".. '-eiA*?). &=0 (5.187) 158 Rozdział 5. Analiza obrazu Oryginalny obiekt może być odtworzony na podstawie podzbioru szkieletu Sk(A), elementu strukturalnego B i K: K A = \J(Sk(A)@kB) (5.188) fe+O a) b) Rysunek 5.48: a) Szkielet obrazu z Rysunku 5.40b; b) obraz odtworzony na podstawie szkieletu Innym podejściem do uzyskania informacji o obiektach jest ich pocienianie. Algorytm pocieniania wykorzystuje operację hit-and-miss Thin(A, BX)B2) = A- HitMiss{A, BX,B2) (5.189) Praktyczna implementacja procesu pocieniania może być zrealizowana przy wykorzystaniu elementu strukturalnego B = N%. Punkt centralny nie jest zastępowany przez element o wartości "0" jeśli i tylko jeśli: i) znaleziono punkt izolowany, ii) usunięcie pbcela zmienia sposób połączenia pozostałych pixeli (np. z 4- połączonych na 8-połączone), iii) usunięcie phcela zmienia długość linii. Jeżeli wszystkie powyższe warunki są spełnione, wtedy otrzymujemy "zupełny szkielet", jeżeli spełniony jest warunek i) oraz ii) obiekt jest redukowany do pojedynczego punktu (jeśli nie zawiera dziur) lub do zamkniętego pierścienia (jeśli zawiera dziury). Jeżeli spełniony jest tylko warunek i) każdy obiekt redukuje się do pojedynczego punktu, natomiast jeżeli jest spełniony tylko warunek ii) to nie zostaną znalezione dziury obiektu. 5.8. Morfologiczne operacje przetwarzania obrazów 159 5.8.2 Morfologiczne operacje przetwarzania obrazów o wielu poziomach jaskrawości Dotychczas rozważaliśmy obrazy binarne tj. obrazy o dwóch poziomach jaskrawości - 1 i 0. Obraz o wielu poziomach jaskrawości może być reprezentowany przez funkcję, której wartość jest jaskrawością w punkcie o określonych współrzędnych. Jeżeli f(i,j) jest obrazem o wielu poziomach jaskrawości i g(i, j) jest ustalonym wielopoziomowym obrazem-wzorcem, nazywanym wielopoziomowym elementem strukturalnym, to operacje erosion i dilation funkcji / i g są określone przez wyrażenia (5.190) (5.191) (5.192) EG(f, 9) = min {/(m +j, n + k) - g(j, k)} EG(f, g) - max {/(m - /, n - fc) + g(J, k)} Mamy EG{f,g) = -DG(-f,g) gdzie -/oznacza, że f(j, k) -* -f(-j, -k). (5.193) (5.194) Operacje opening i closing określamy następująco 0G(f,g) = DG(EG(f,g),g)) CG(f,g) = -0G(-f,-g) W wielu przypadkach morfologiczne operacje przetwarzania obrazów o wielu poziomach jaskrawości mogą być uproszczone przez przyjęcie symetrycznego elementu strukturalnego g(j, k) = g(-j, -k). Jeżeli B = const = 0 i (j. k) Cg, wtedy (5.195) (5.196) (5.197) (5.198) DG(f, 9) = max {f(m -j,n-k)} = max(/) (j,k)€g 9 EG(f, g) = mm {f(m + j,n + k)} = min(/) (j,k)eg 9 0G(f,g) - max(nun(/)) EG(f,g) = min(max(/)) 160 Rozdział 5. Analiza obrazu 5.8. Morfologiczne operacje przetwarzania obrazów 161 A e B 6 f 3 4 i 1 1 ^ 5 6 6 S i 2 1 2 1 6 4 3 2 i 1 l i i 6 4 5 3 A-m B-g{k.l) m/n 4-6 5 6 •i 4 4 6 5 3 4 Rysunek 5.49: Operacja erosion dla obrazu o wielu poziomach jaskrawości Wykorzystując powyższe definicje morfologicznych operacji przetwarzania obrazów o wielu poziomach jaskrawości definiujemy GradientU, g) = \(DG(f,g)-EG(f,g) = ^(max(/)-min(/))(5.199) Laplacian(f,g) = -((DG(f,g) -/)-(/- EG(f,g))) = \{DG{f,g) + EG(f,g) - 2/) = i(max(/) - min(/) - 2/) (5.200) Na Rysunku 5.51 przedstawiono wyniki zastosowania tych operacji dla obrazu testowego. f|7|2l3|0|3|6|5|2 2 19 Sygnał wejściowy ' El ' I Eternentstrukturalny Sygnał wyjściowy - 7 7 7 3 3 6 6 6 5 2 9 9 9 6 3 5 6 6 6 4 0 0 8 6 8 2 1 6 6 3 6 6 6 7 6 7 6 9 6 3 5 6 6 6 4 0 0 8 6 8 2 1 6 6 3 6 6 6 7 6 7 6 9 6 3 5 6 6 6 4 0 0 8 6 8 2 1 6 6 3 6 6 6 7 6 7 6 wielopoziomowa operacja dilation 9 9 9 9 9 6 6 6 9 6 6 5 6 8 8 8 8 6 8 7 8 7 6 7 7 7 7 7 Rysunek 5.50: Operacja dilation dla obrazu o wielu poziomach jaskrawości 162 Rozdział 5. Analiza obrazu e) Rysunek 5.51: Morfologiczne operacje przetwarzania obrazu o wielu poziomach jaskrawości dla elementu strukturalnego : a) operacja erosion, b) operacja dilation, c) operacja opening, d) operacja closing, e) operacja gradientu Rozdział 6 Rozpoznawanie obrazów 6.1 Wprowadzenie Systemy rozpoznawania klasyfikują obiekty występujące w rzeczywistym (Rysunek 6.1) lub sztucznym otoczeniu, wykorzystując modele tych obiektów znane a'priori. Problem rozpoznawania obiektów można rozpatrywać jako problem przyporządkowywania etykiet obiektom lub zbiorom obiektów w obrazie. Rysunek 6.1: Zadanie rozpoznawania Rozpoznawanie obiektu następuje poprzez przypisanie go do pojedynczej unikatowej klasy. Klasyfikacja natomiast to proces grupowania obiektów do klas względem postrzeganych podobieństw. Możemy więc powiedzieć, że rozpoznawanie to pewna forma wnioskowania, natomiast klasyfikacja to pewna forma uczenia. Rozpoznawanie obrazów, odbywa się w warunkach braku informacji a'priori na temat reguł przynależności obiektów do poszczególnych 164 Rozdział 6. Rozpoznawanie obrazów 6.1. Wprowadzenie 165 klas, a jedyna informacja wykorzystywana przez układ rozpoznający zawarta jest w ciągu uczącym. Ciąg uczący złożony jest z obiektów, dla których znana jest prawidłowa klasyfikacja. System rozpoznawania (Rys.6.2) zawiera następujące elementy: - bazę modeli, - detektor cech, - układ formowania i weryfikacji hipotez. CECHY OBRAZ KLASA OBIEKTÓW DETEKTOR CECH FORMOWANIE WERYFIKACJA W HIPOTEZ HIPOTEZ 1 1 BAZA MODELI Rysunek 6.2: Schemat ogólny systemu rozpoznawania Rozpoznawanie obrazu jest więc klasyfikacją danych wejściowych na jednoznacznie identyfikowalne klasy na podstawie wydzielonych cech (Rys. 6.3). Zazwyczaj brak jest informacji a'priori o przynależności obiektów do poszczególnych klas. Znany jest natomiast ciąg uczący złożony z obiektów, dla których klasyfikacja jest znana. Rozwiązanie zadania rozpoznawania wymaga: 1. Określenia liczby klas (liczba klas musi być skończona), 2. Określenia rozkładu a'priori klas, 3. Określenia cech klas, 4. Określenia rozkładu cech w klasach, 5. Określenie stopnia gradacji cech i dyskretyzacji obrazu, 6. Minimalizacji liczby cech tj. wyboru riy cech z n (ni < n) tak, żeby dokładność rozpoznawania nie zmniejszyła się, 7. Obliczenia prawdopodobieństwa błędu dla różnych cech i kryteriów rozpoznawania, 8. Końcowego ustalenia liczby cech. Rysunek 6.3: Przestrzenie cech i klas Proces rozpoznawania można podzielić na (Rys. 6.4)[75],[19] • pozyskiwanie cech, • selekcję cech - czyli wydzielanie cech, które zawierają najbardziej istotne informacje z punktu widzenia procesu rozpoznawania, • klasyfikację obrazu - wypracowanie decyzji o zakwalifikowaniu obrazu do konkretnej klasy. Systemy rozpoznawania ze względu na sposoby przetwarzania informacji (dla podjęcia decyzji) zawartej w cechach możemy podzielić na 1. systemy rozpoznawania strukturalnego, 2. systemy rozpoznawania metodami statystycznymi. Obraz można opisywać jako zbiór pewnych charakterystycznych jego właściwości (cech), które można pomierzyć i przedstawić w wielowymiarowym układzie współrzędnych. Obiekty obrazu reprezentowane są przez n cech. Cechy te tworzą n-wymiarową przestrzeń cech w której każda współrzędna reprezentuje odpowiednią cechę. Obiekt jest reprezentowany przez wektor X = [X\,X%,..., Xn]t i jest przedstawiany jako punkt w przestrzeni cech: X E Rn (Rys. 6.5). 166 Rozdział 6. Rozpoznawanie obrazów ".'?- -"-> • s-r-^ -, --. -?? f- *? lss m :r i Rysunek 6.4: System rozpoznawania xs X, Klasa 3 mm Klasa 1 xx* xkx<" Wektor cech Przestrzeń cech (3D) Cec/fc? 1 Klasy w przestrzeni cech. Obiekt jest reprezentowany przez punkt. Rysunek 6.5: Cechy i klasy. Zadanie rozpoznawania obrazu polega na przyporządkowaniu realizacji do odpowiedniej klasy. W prostym przypadku zadanie rozpoznawania obrazu może być rozwiązane metodami deterministycznymi. Wymaga to dokładnego podziału przestrzni X na części odpowiadające różnym klasom. Rozważamy problem przydzielenia pewnych obiektów obrazu do jednej z dwóch klas Cl - Wj gdzie i = 1,2. Trywialny algorytm rozwiązania tego problemu polega na przydzieleniu etykiet wszystkim możliwym obrazom i zapamiętaniu ich w odpowiedniej tablicy. Zakładając, że np. binarny obraz ma rozmiar 128 x 128 pbceli, to mamy 216384 6.1. Wprowadzenie 167 Graniu decyzyjna Waga (teł •} (wieki,waga 1) Pies 2 -> (wiek 2, waga 2) Najbliższa średnia Najbliższy sąsiad K-najbliźszych sąsiadów Klasyfikacja Bayesa Kot1 -> (wiekt.wagat) Kot 2 •* (wiek 2 , waga 2) I y Granica decyzyjna (Wiek x, Waga x) Dane testowe /N Kot Pies Rysunek 6.6: Podział na klasy na podstawie cech różnych obrazów. W takim przypadku zbiór uczący zawiera tysiące próbek. Rozwiązaniem tego problemu jest klasyfikacja na podstawie cech. Mamy c możliwych klas do których może należeć X. Oznaczmy zbiór klas przez Q = {ui\, LU2, ? ? ?, &c}, gdzie c - ogólna liczba klas.Dla danego obiektu X ? Rn należy znaleźć klasę u G fi do której prawdopodobnie należy X X ~ uik jeżeli Dk(X) = max Di, i = 1,..., c gdzie Di(X) jest funkcją dyskryminacyjną klasy w". (6.1) Tak więc klasyfikacja może być rozpatrywana jako podział przestrzeni cech na c obszarów każdy z których odpowiada klasie przy czym Di{X) = Dj(X), dla wszystkich i^j (6.2) 168 Rozdział 6. Rozpoznawanie obrazów Jeżeli X należy do klasy uDi(X) i,j = l,2,...,c j^i (6.3) Funkcją dyskryminacyjną (granicą decyzyjną) pomiędzy dwoma dowolnymi klasami i oraz j {i ^ j) jest Dij{X) = A(X) - Dj(X) - 0 (6.4) X należy do i-tej klasy jeżeli Dij(X) > 0, natomiast do j-tej klasy gdy Dy(X) < 0. Dla wspomnianego wcześniej zadania przydzielenia obiektów obrazu do jednej z dwóch klas, linia separująca klasy U\ i u;2 jest liniową lub nieliniową funkcją dyskryminacyjną (granicą decyzyjną) (Rys.6.6). Klasyczne metody rozpoznawania obrazów to: 1. metody odległościowe, 2. metody aproksymacyjne, 3. statystyczne. 6.2 Klasyfikatory odległościowe Zakładamy, że mamy przestrzeń cech X G Rn z odpowiednią metryką p : X x X -? R. Metryka spełnia następujące założenia dla wszystkich Xi G X , i = {1,2,...,} p(Xi,XJ) = P{XvXi) p(Xi,Xj) = 0=^Xi = Xj (6.5) p(Xi,X,) < p(Xi,Xfe) + p(Xfe,XJ) Metryki są miarami podobieństwa wektorów (większa wartość metryki to większa odległość i mniejsze podobieństwo). W procesie klasyfikacji obiektów wykorzystujemy następujące miary odległości: 1. odległość pomiędzy dwoma punktami w przestrzeni cech (dwoma obiektami) zdefiniowana przez metrykę DL{XtY) = \ f:\xi-Vi\L\l (6.6) i.2. Klasyfikatory odległościowe 169 gdzie L przyjmuje wartości 1,2, i oo. Dla L - 2 DE(X,Y) = \ 52(xi-Vi)2 = l(x-Y)\x-r)]k (6-7) 1=1 mamy metrykę (odległość) Euclidesa; dla L -1 Dc(x,Y) = Y,\xi-yi\ (6-8) i=l metrykę (odległość) city-block, natomiast dla L = oc mówimy o metryce Czebyszewa (maksimum) Dm(X,Y) = max\xi-yi\, t = l,...,n (6.9) 2. odległość pomiędzy punktem a rozkładem czyli pomiędzy obiektem X i klasą Wj której cechy mają rozkład owartości średniej A/, i macierz kowariancji Ei (odległość Mahalanobisa) DM(X,uji) = (X - Af,)'^ *(X - Af") (6.10) 3. odległość pomiędzy dwoma rozkładami czyli dwoma klasami u>j i Uj w której cechy mają rozkłady o wartościach średnich Mj i Mj oraz macierze kowariancji Ei i Ej (odległość Bhattacharrya) (I Et II Ej I)2 170 Rozdział 6. Rozpoznawanie obrazów Linie stałej odległości Rysunek 6.7: Linie stałej odległości 6.2.1 Klasyfikator najmniejszej odległości Załóżmy, że w A;-tej klasie uik cechy mają rozkład o wartości średniej: Mk = WEXlk) fe = l,2,...,c (6.12) K 1=1 gdzie JVfc jest liczbą elementów w klasie u;*, i macierz kowariancji 1 M* Ek = ir E(^(fc) - Mk)(x?] - Mky (6.13) Obiekt X nieznanej klasy będzie zakwalifikowany do klasy ujk jeśli jego odległość Mahalanobisa do klasy uk jest mniejsza aniżeli do innych klas tj. X ~ uk jeżeli DM(X,ujk) = mm{DM(X,Ui), i - l,...,c} (6.14) Dla uproszczenia można wykorzystać metrykę DL(X, A/J) zamiast DM{X,Ui). W takim przypadku nie posiadamy informacji jak klasy są rozłożone w przestrzeni cech. 62. Klasyfikatory odległościowe 171 Najbliższa średnia ? - m *' I 1 1 O 'o. o o o Rysunek 6.8: Najbliższa średnia Dla L = 2 czyli metryki euclidesowej otrzymujemy DE(X, Mt) = [{X - Mi)t(X - Mt)]ł, i = 1,2,... c (6.15) Obiekt X jest przydzielany do klasy ui^ jeżeli DE(X, Mi) jest najmniejszą odległością. Funkcja decyzyjna jest postaci DE(X, Mi) = X'Mt - ~M*Mi i = i, 2,... c (6.16) Granica decyzyjna pomiędzy klasami Ui i u)j jest określona przez DE(XtMi)~DE(X,Mj) = - X\Mi - Mj) - l{Mt - Mj)\Mi - Mf) = 0 (6.17) Miejsca geometryczne spełniające równanie (6.17) tworzą dla N = 2 prostą prostopadłą i dzielącą na pół odcinek łączący Mi i My, dla N = 3 płaszczyznę, natomiast dla N > 3 hiperpłaszczyznę. 6.2.2 K-najbliższych sąsiadów W tym algorytmie klasyfikacji mamy zbiór obiektów należących do znanych klas (w założeniu do wszystkich c klas): Ąk) W *lgh (*=-!,..., c) 5.18) 172 Rozdział 6. Rozpoznawanie obrazów Najbliższy sąsiad Nowa próbka klasyfikowana jako x XJ Oo°o o o X X X XX Rysunek 6.9: Najbliższy sąsiad Definiujemy odległość między obiektem X a klasą reprezentowaną przez obiekt należący do znanej klasy D(X,u;fc) = min{DL(X,Xl(fe)), i "!,...,#*} (6.19) Obiekt X należący do nieznanej klasy jest klasyfikowany do klasy z najbliższego sąsiedztwa: X ~ ujk jeżeli D{X,uk) = mm{D(X,ujj), j = 1,..., c} (6.20) K- Najbliższych sąsiadów N owa próbka klasyfikowana jako x Rysunek 6.10: K-najbliższych sąsiadów 6.3. Klasyfikatory statystyczne 173 6.3 Klasyfikatory statystyczne Teoria decyzyjna Bayesa jest fundamentalnym statystycznym podejściem do problemu rozpoznawania (klasyfikacji) obrazów. Niech: - P{uik) - prawdopodobieństwo a'priori, że arbitralny obiekt należy do klasy ujk, - P{ujk\X) - warunkowe prawdopodobieństwo a'posteriori, że określony obiekt X należy do klasy u>k, - p{X) - rozkład prawdopodobiństwa (gęstości) wszystkich obiektów, - p(X\uk) - rozkład warunkowy prawdopodobieństwa (gęstości) wszystkich obiektów należących do uik, p(X) = 5>(X|u/fc)P(w*) i=l (6.21) Reguła Bayesa PMX) = p(X\uk)P{u}k) p(X\uk)P(ujk) P(X) ZUP&MPM (6.22) Prawdopodobieństwo a'priori P(ujk) może być oszacowane na podstawie zbioru obiektów (próbek) uczących P{uJk) = Pź = ^ zakładając, że zbiór próbek uczących jest losowo wybrany ze zbioru wszystkich obiektów. Zakładając, rozkład normalny mamy p{X\ui) = N(X, Mt, ?.) = ] ieXp[-hx - Mi)\X - Mt)] (2TT)2|^|2 l (6.23) gdzie wektor wartości średnich M, i macierz kowariancji ?* s§ oszacowane na podstawie zbioru obiektów (próbek) uczących. 174 Rozdział 6. Rozpoznawanie obrazów ta2 Oj T\ * P2) i: 10(tm)** "" x ! / / 1 1 1 l"'l * 10 x H" Rysunek 6.11: Problem klasyfikacji do dwóch klas (a) i prawdopodobieństwo błędnej klasyfikacji (b). Funkcja dyskryminacyjna Wejście Akcja np. Klasyfikacja Rysunek 6.12: Klasyfikator. Obiekt X z nieznanej klasy jest klasyfikowany do klasy ujk jeśli ''jest bardzo prawdopodobne, że X należy do u;*", tj. X ~ uk jeżeli P(u;k\X) = max{P(cjk\X) i = 1,..., c} (6.24) Z równania 6.24 wynika, że P(u-'fc|X) może być wyrażona przez p(X\uk)P(ujk) (6.25) P(X) P(UH\X) = a ponieważ p(X) jest takie same dla wszystkich P(uk\X) to funkcja dyskryminacyj na Di(X) = p{X\u>k)P(ui) (6.26) określa proces klasyfikacji X ~ uk ieżeli Dk(X) = max{Di(X) i = l,...,c} (6.27) 6.3. Klasyfikatory statystyczne 175 W przypadku dwóch klas (c = 2) całkowite prawdopodobieństwo błędu (błędnej klasyfikacji) wynosi P(b\ędnej klasyfikacji) - P(X G R2 D X ~ ui) + +P(X e Ri n X ~ u2) = = P(X G R2\u1)P(u1) + P(X € RiMPM = (6.28) = / p(X\u1)dXP(u;1) + f p{X\u2)dXP{u2) JRz JRi gdzie P{X E Ri (~) X ~ Uj) jest prawdopodobieństwem łącznym, że X należy do klasy UJJ W obszarze Ą. W przypadku wielu klas P(poprawnej klasyfikacji) = E^ P(X G Ą (~l X ~ u/*) = = ? P(X G RM)P(uJi) = (6.29) "=i E^) / p(^k)^ Funkcja dyskryminacyjna może być przedstawiona w postaci Di{X) = Inppr|"j)P(wt) = lnp(X\ui) + lnP^) = n 1 --ktar--In|5^| + lnPM (6.30) Drugi składnik -nln^y jest stały dla wszystkich Z)< i może być pominięty. Możemy rozważać następujące przypadki: Wszystkie klasy mają równe prawdopodobieństwo a:priori: P(u?i) = P{oJj) dla wszystkich i,j (6.31) wtedy ostatni składnik równania (6.30) może być pominięty. 176 Rozdział 6. Rozpoznawanie obrazów Dla wszystkich klas mamy ?. = a2/ = dżag[a2,...,<72] (6.32) wtedy \Y,i\ = cr2n i w takim przypadku otrzymujemy (6.33) Di(X) = -lX 2(jfĄ2 +lnP(cui) Wyrażenie określające granicę w przestrzeni cech pomiędzy a^ i uij Di{X) = Dj(X) (6.34) można uprościć do postaci W*X - w = 0 (6.35) gdzie: W = Mi - Mj i w - -(M*Af, - M}M0) + 21)), i = 1,..., k gdzie ujj oznacza i-ty klaster obiektów ze środkiem M\ W I-tej iteracji. 6.4. Selekcja cech 179 3 Nowy środek klastra jest określony przez gdzie Nj jest liczbą obiektów w u/j w l-te] iteracji, i Suma odległości wszystkich punktów w Uj do nowego środka jest minimalna Zx^m DL(X, MJl+1)) -> min. (j = 1,..., A;) 4 Jeżeli MJ'+1) . Mf (j = 1,..., k) lub liczba iteracji przekracza założoną wtedy kończymy procedurę. W przeciwnym przypadku l *- l + 1 i przechodzimy do punktu 2 algorytmu. 6.4 Selekcja cech Głównym celem selekcji cech jest redukcja kosztu obliczeń przez wykorzystanie w procesie rozpoznawania/klasyfikacji tylko nx (ni < n) cech. ni cech może być bezpośrednio wybranych spośród n początkowych cech, lub poprzez ich liniową kombinację. Niech całkowita liczba elementów zbioru uczącego wynosi N = Y,Ni (6.45) gdzie Ni jest liczbą elementów w klasie u;,-. Wektor średni fr=jrZX=ltNĄZX^t%Mi = ±PiMi (6.46) iV X iV i=l iVJ X~Wj i=l JV i+1 gdzie Pi = jf jest prawdopodobieństwem a'priori klasy u/*. Zdefiniujemy następujące macierze rozrzutu: klasy Ui Si - ~ E <* - Afr)C* - **)* = E (6-47) 180 Rozdział 6. Rozpoznawanie obrazów • wewnątrzklasową c c i=l i=l i • międzyklasową 5B=EPi(Mi-M)(Mi-M)t i=i (6.48) (6.49) • całkowitą Sr = ±Y:(X-M)(z-My = ^EE (X-M)(X-Mf(6.50) X i=l X~0Ji Oczywiste jest, że ST = Sw + SB- Jako pewne kryteria w problemie selekcji cech możemy wykorzystać następujące miary Ja = tr^SwSe) Jb = det{SwlSB) (6.51) (6.52) gdzie tr() i det() są odpowiednio śladem i wyznacznikiem macierzy ()• 6.4.1 Wybór ni cech z n początkowych cech Wiadomo, że mamy ani = ni (n-ni)!ni! (6.53) sposobów wybrania ni cech spośród n cech. Musimy znaleźć ni najlepszych cech czyli takich, które pozwalają na dobrą separację (rozdzielenie) klas w ni wymiarowej przestrzeni cech. Kryteria określające stopień separowalności klas są następujące: Ji = Y^PiPjDB(u}i,u}j) (6.54) ?4 gdzie Pi and Pj są prawdopodobieństwami a 'priori odpowiednio klas uji i u/j. 6.4. Selekcja cech 181 J2 = tr(SwlSB) = tr(SB/w) (6.55) cdzie •SB/W = ^W ^S; [ SB = EU Pi(Mi - M)(Mi - My. 6.4.2 Wybór ni cech poprzez liniową kombinację n cech oryginalnych Jeżeli wybranie rt\ cech w sposób podany w podrozdziale (6.4.1) cech nie zapewnia zadawalającej separowalności klas, możemy wybrać rt\ nowych cech które będą liniową kombinacją początkowych n cech Y = A*X (6.56) gdzie A jest nxni macierzą utworzoną z i%\ n-wymiarowych wektorów kolumn Ai. A = [Ai,..., Ani\ Y jest ni-wymiarowym wektorem którego ni elementów Hi = A\X, i = 1,..., nj są nowymi cechami. Oczywiście, że po liniowej transformacji Y = AlX, mamy średnie wektory, macierze kowariancji i macierze rozrzutu określone przez M{P = A1M\X) (i = i, vfn (X) S-^Er* (z = 1" (6.57) (6.58) oraz si 0\\r si itc(X) S^> = AtS^'A (6.59) °B/W At MX) A 182 Rozdział 6. Rozpoznawanie obrazów 6.4. Selekcja cech 183 Główne metody redukcji cech to metoda PCA i metoda LDA (Rysunek 6.14). Cecha 1 Rysunek 6.14: Metody redukcji cech 6.4.3 Metoda PCA Metoda PCA została wprowadzona przez Pearsona w 1901 roku i uwzględniając szereg modyfikacji uogólniona przez Loeva w 1963 roku. Na Rysunku 6.15 przedstawiono istotę metody PCA. Jeżeli X ma rozkład gaussowski, to możemy zapisać (6.60) U2 X = X1Ui + X2U2 = (Xi, X2)ui Wtedy można znaleźć jednowymiarową reprezentację x' położoną w bliskiej odległości od x taką, że x' = yv = (y)v (6.61) przy czym miara bliskości określana jest przez błąd średniokwadra-towy (6.62) [y)v = min?|[x' - x] Problem redukcji wymiarowości przestrzeni cech metodą PCA można sformułować następująco: Optymalna aproksymacja losowego wektora X € R71 przez liniową kombinację m (m < n) niezależnych wektorów jest uzyskiwana przez projekcję losowego wektora X na wektory własne i ' wektorówwlasnycn j, " Krok 5. Odrzucenie małych wartości i ' wektorrjwwlasnych ' l Krok 6: Projekcja każdego wektora do odpowiedniej przestani "n* 2 Kroki Krok 4 \*ft Krok 5 Rysunek 6.16: PC A kolumny (Rys. 6.17). Dla tak przedstawionych obrazów możemy obliczyć wartość średnią jaskrawości (wektora cech bo w rozpatrywanym przypadku jaskrawość jest cechą), wektor obrazu po odjęciu wartości średniej jaskrawości, oraz macierz kowariancji Mk ?dzie: k k=l (6.64) X=(xi,x2,...,Xn)t, M=(MX)M2,...,Mn)\ "=("i,A2,...,Ąl)". 6.4. Selekcja cech 185 125 150 ... 130 128 138 ... 127 98 100 ... 129J 64x64 pikseli i [125 150 ...130 128 138 ... 127 .. . 98 100 ... 129 J 4096 zmiennych Rysunek 6.17: Konkatenacja wierszy obrazu - tworzenie wektora obrazu Główne osie znajdowane są poprzez obliczenie wektorów własnych k)- Znalezione wektory własne $ = (2, ? ? ? (finY są normowane, sortowane we wzrastającym porządku zgodnie z odpowiadającymi wartościami własnymi, transponowane i tworzą wektory-wiersze macierzy transformacji W. Następnie można zrealizować projekcję danych X na przestrzeń wektorów własnych zgodnie z Y = W(X - M) (6.65) erdzie X = (x1,x2,...,xn)t ; K*= (jft,i&,...,jfr.,0,...,0)*. Przy projekcji na przestrzeń wektorów własnych możemy wykorzystać nie wszystkie wektory własne, ale tylko te, które odpowiadają największym wartością własnym. Po projekcji obrazu do przestrzeni wektorów własnych otrzymujemy wektor Z=(zuza,..., zny = (2/1,2/2,---, gft gdzie rid jest liczbą cech. (6.66) W procesie rozpoznawania obliczamy odległość c2 pomiędzy wektorem cech Zi znanego obrazu i wektorem cech obrazu rozpoznawanego Zroz. Obraz jest zaliczany do klasy c = argminj(tj) na 186 Rozdział 6. Rozpoznawanie obrazów podstawie odpowiedniej miary odległości. Zilustrujemy metodę PCA rozpatrując 4 obrazy tworzące zbiór uczący i jeden obraz testowy (Rys. (6.18) [113]. 0'"-&&H Rysunek 6.18: Obrazy wykorzystywane w procesie PCA Obrazy przedstawione na Rys. 6.18 i ich średnie posiadają następujące wartości jaskrawości X,= [" 225 1 ' 10 1 r 196 i " 255 1 229 219 35 223 48 24 234 224 251 255 232 255 33 ; x2 = 18 ;*3 = 59 ; XĄ - 0 238 247 244 255 0 17 243 249 255 255 57 255 . 217 . 2 . . 226 . L 35 J M = 171,5 176,5 135,5 248,25 27,5 246 127,25 205, 5 170 (6.67) Obrazy po odjęciu wartości średniej są następujące M p H to to Ol en A 00 O H W-i^OiCn JiOłOMO-^tOWh--Ol-'OCOJiQOCOCO--I to CO 00 tO Ol W CO O) W OiOOWdOOM-JOl -Ji-^OOlOOiJ^Oi^W *--vlŁ0*i|-'OlO1~JCO ł-'• O) 5" I to oo oi oi rf^ to co ?k ?k tO I ~q co s oo ai OOiOiOOlOiOiOiOi 2 ts co to oo oi oi to ?f^ tO CO CO Ol O 4^ tO ** ~ tJ^ Oi -vj 00 to -4 Ol h-> i-'4^ ~4OlOl00OlOiOlOlOl OlOlOitOOlOiOiOiOi r> Ol ^ O OOOOlHtJlOCiMM occoooo**toQomtv> 00 ^J W 00 -I Cl -I Oł CO AlOi-1 -4U CO O -g -i^cn-ił-mto^-j CTiCOWCO-lWHCJiOO p i-i p' I- ?- Ol O ^ O) oo to CO to 00 CO -J OOiOiOOlOiOiOiOi & & Ol O ^ Ol hf=- O Ol ^ Ol oi oo to co oi o 4^ to -J to OOlOlOOlOlOlOlOl oo to CO oi co CO to -J -*1 Ol to Ol CO 4^ 00 Ol -a - OlOlOiCOOlOiOlOlOi OOOlOil-'OlOiOiOiOl I CO -J h* CA) "- U i-" Ol rf^ to Ol Ol CO 4*. 00 t-' Ol CO Oi CO tO S aiioffiK* to mtg fc oiccjisaHOioo -ltO(DUCiWUUO OOlOOlOlOiOlOlOl t^ tO IO fflUOM A O^COWtOtOOOCO 00WIOOHS-J-JH 00 *"? 00 Ol & cD00W--)W^lO0-J(fc OJ OJ 00 oo 188 Rozdział 6. Rozpoznawanie obrazów Uporządkujemy niezerowe wektory własne i odpowiednie wartości własne 0i = 0,356 -0,279 0,480 -0,031 0,035 -0,009 0,56 -0,296 0,402 J 02 = -0, 552 ' -0,264 -0,489 0,347 0,044 0,309 -0,048 0,064 0,105 03 = -0,222 -0,004 0,078 0,112 0,585 0,492 0,401 -0,432 L -0,391 (6.71) Xx = 153520 ; A2 = 50696 ; A3 = 22781 (6.72) $ = 0,356 -0,279 0,480 -0,031 0,035 -0,009 0,56 -0,296 0,402 -0,552 -0,489 0,044 -0,048 0,105 -0,004 0,112 0,492 -0,432 -0,264 0,347 0,309 0,064 -0,222 0,078 0,585 0,401 -0,391 (6.73) Mamy ' -103,09 " XX = $*fl! = -117,31 -96,57 -229, 76 ' x3 = $TR3 = 125,9 -46,14 X2 = &R2 X4 = $'#4 ' -265,92 " 98,29 47,45 ' 139,24 ' -106,88 95,26 (6.74) 6.4. Selekcja cech 189 Przedstawiamy obraz testowy r 201 - L51.5 1 244 44 246 67,5 -88,5 -2,25 n = 21 244 Y,= -6,5 -2 4 -123,25 255 2 . 49,5 -168 . •ojekcj a obrazu testowego Yi = < &TFX = ' -266 80 5 ,65 n ,75 0,6 (6.75) (6.76) Normy euklidesowe dla obrazu testowego Y\ i obrazów Xi, X2, X3 i X4 wynoszą odpowiednio 296, 18, 508 i 449. Widzimy, że Y\ najbardziej zbliżony jest do X2. Chociaż wartości własne są w ogólności zespolone, wartości własne rzeczywistej symetrycznej macierzy są zawsze rzeczywiste. Jest to fundamentalne stwierdzenie dla macierzy kowariancji stosowanej w wielowartościowej analizie statystycznej, ponieważ nie tylko wektory własne istnieją lecz także istnieje zupełny zbiór n wektorów własnych i ich odpowiednich wartości własnych. 6.4.4 LDA Zasada redukcji wymiarowości metodą LDA przedstawiona została na Rysunkach 6.19 oraz 6.20. Załóżmy, że mamy klasę u i zawierającą obrazy, a każdy obraz opisywany jest przez n-wymiarowy wektor cech, który można przedstawić jako punkt w przestrzeni (Rys. 6.21). Wtedy, zbiór wektorów cech, opisujący wszystkie klasy, jest następujący rti) T r(i,fc) {Xd,k) ii = i>2,...,c, fc = l,2,.. j?-(i,fc) ^1 i x2 t (6.77) 190 Rozdział 6. Rozpoznawanie obrazów Rysunek 6.19: Projekcja obiektów max[F = \^ Ajj , {MP-M?*) 3 ?? Rysunek 6.20: Separowalnosć klas obrazów Niech y = wlx , w = K; (6.78) gdzie W jest macierzą wag, a t oznacza operację transponowania macierzy. Macierze wewnątrzklasowa i międzyklasowa kowariancji cech są obliczane następująco ? = !>? w fe=l i (6.79) 6.4. Selekcja cech 191 Rysunek 6.21: Przykład trzech klas obrazów ni (6.80) b k-\ gdzie pi, M\, Mi, J2i oznaczają odpowiednio prawdopodobieństwo a'priori klasy u>it wektor wartości średniej klasy u>i, globalny wektor średni i macierz kowariancji klasy u>i. Optymalną macierz wagową W otrzymujemy poprzez rozwiązanie równania 52 W = ^2 W A , (WT J2 W = 1) (6.81) gdzie: A - diagonalna macierz wartości własnych, I - macierz jednostkowa, i j-ta kolumna W jest wektorem własnym odpowiadającym j-tej największej wartości własnej. Do rozpoznawania obrazu wykorzystujemy klasyfikator obliczający odległość między klasami Ob i odległość między różnymi obrazami tej samej klasy Ow. Odległość Ow obliczamy jak 1 c -i m -i ni ow = i-52-52 -- 521 \x(l'J) - x(i'h) 112 = 192 Rozdział 6. Rozpoznawanie obrazów -i c i ni -i ni n = ^E^IZ^TEE(4u)-4i'i))2 *c 1=1 ni j=\ >n J- fc=i /=i 1 c n -i ni i ni 1 c ni -i * y(r(i i=i i=i ni ~~ * fc=i c ni -i ni = Er^EP E(*P)2 - e E -!a))2l c i=i "i - * {=1 "i fc=i "i fe=i = ^EE^ng(^-^n2 (6.82) gdzie i ni MJi] = -J^x\i'k) (6.83) ni fc=i Odległość 0(, obliczamy następująco c i=l c i=l 1=1 °> = 7 E II**0 " MH2 = \ E E(M/° - M02 (6-84) gdzie i c -i ni ^ = ^E^E^ (6-85) c i=i ni fe=i Dobra separowalność klas oznacza, że mamy dużą odległość mię-dzyklasową Ob i małą odległość wewnątrzklasową Ow. Współczynnik ^- przyjmuje większe wartości dla lepszej cechy i może być kryterium jakości wektora cech. Dla n-wymiarowego wektora cech mamy j_0" .. ^=1E?=i(MW-M,)2 °" \ EU EU ii nu{xtk) - M?y W przypadku dwóch klas c = 2 z równania (6.86) uzyskujemy znane kryterium Fishera (M,'"-M,"')' F" ","+<,<*> <6'8?) gdzie i ni ^ ni W _ W"(">fc) Łf<*)\2 -E(*r -*n2 (6-88) ft=l Indeks Średnia wartość jaskrawości, 51 4-elementowe otoczenie, 99 8-elementowe otoczenie, 99 Akwizycja obrazu, 25 Analiza obrazu, 95 Baza modeli, 164 Cyfrowa reprezentacja obrazu, 34 Detektor cech, 164 Dyskretna transformacja Fouriera (DFT), 112 Entropia, 97 Filtracja obrazu, 61 filtr Kuwahara, 71 filtr medianowy, 68 filtry adaptacyjne, 64 filtry wygładzające, 67 splot, 63 funkcja dyskryminacyjna, 167 Funkcja sklejana, 113 Graf połączeń, 101 Granice obiektów, 104 Histogram, 47 histogram gradientu, 53 modyfikacja histogramu, 59 znormalizowany histogram, 51 Klasteryzacja, 177 algorytm Isodata, 177 algorytm k-średnich, 177 Klasyfikacja, 163 klasyfikacja obrazu, 165 Klasyfikatory K-najbliższych sąsiadów, 171 klasyfikator najmniejszej odległości, 170 klasyfikatory odległościowe, 168 klasyfikatory statystyczne, 173 Kod łańcuchowy, 106 Komputerowa wizja, 1 Kontrast, 16 Kontur obiektu, 110 Krzywe, 104 aproksymacja krzywej konturu, 113 interpolacja krzywej konturu, 113 krzywa a - s, 110 krzywa B-sklejana, 114 krzywa cyfrowa, 106 krzywa konturu obiektu współczynniki Fouriera, 112 Krzywizna, 106 Kwantowanie obrazu, 39 Linie konturowe, 104 194 Indeks Luminancja, 16 Metoda Otsu, 52 Metryka, 99, 168 metryka city-block, 169 metryka Czebyszewa, 169 metryka Euclidesa, 169 Mexican Hat, 78 Momenty, 97 bezwzględne momenty centralne, 97 kosinusowe, 144 momenty bezwzględne, 97 momenty centralne, 97, 140 momenty geometryczne, 139 momenty Hu, 142 momenty inwariantne, 144 momenty Zernike, 142 sinusowe, 144 Obraz cyfrowy, 42 funkcja obrazu, 43 macierz obrazu, 43 obrazy testowe, 47 Operacje morfologiczne, 146, 158 closing, 152 dilation, 146, 149 erosion, 146, 149 hit-and-miss, 155 opening, 152 różnica Minkowskiego, 147 suma Minkowskiego, 147 szkielet obiektu, 155 Próbkowanie obrazu, 35 Prawo Webera-Fechnera, 19 Przetwarzanie obrazów, 1 cyfrowe przetwarzanie obrazów, 1 Przetwarzanie wstępne obrazu cyfrowego, 47 Przetwornik obrazowy CID, 28 CTD, 28 optyczno-elektryczny, 25 telewizyjna lampa analizująca widikon, 27 Punkty charakterystyczne punkty o dużej krzywiźnie, 123 Redukcja cech LDA, 189 metoda PC, 182 Reguła Bayesa, 173 Reprezentacja obszarów obiektów, 127 długość serii elementów, 128 drzewa czwórkowe, 130 piramida obrazów, 130 projekcje, 129 Rozpoznawanie rozpoznawanie staty- styczne, 165 rozpoznawanie strukturalne, 165 Rozpoznawanie obrazów, 163 metody aproksymacyjne, 168 metody odległościowe, 168 metody statystyczne, 168 Ścieżka, 101 Segmentacja obrazu, 84 metoda relaksacyjna, 91 metoda rozmieszczanie punktów obrazu, 88 Indeks 195 metoda rozrostu obszarów, 89 metoda wydzielania granic obszarów, 86 Selekcja cech, 165, 179 System komputerowej wizji, 5 System wizyjny robota, 5 System wzrokowy człowieka - HVS (Humań Visual System), 8 Tekstury, 132 parametry opisujące tekstury, 134 entropia, 136 informacyjna miara korelacji, 137 kontrast, 134 miara homogeniczności obrazu, 135 współczynnik korelacji. 135 parametry opisujące tekstury dyspersja, 136 moment różnicowy, 136 Teoria decyzyjna Bayesa, 173 Transformację Fouriera, 63 Transformacja Fouriera, 36 Transformacja Hough'a, 117 tablica akumulatora, 120 Transformacja skali jaskrawości, 54 liniowa, 57 logarytmiczna, 58 wykładnicza, 59 Twierdzenie Whittakera - Ko-tielnikowa - Shannona, 35 zów, 98 Wariancja, 51 Wartość progowa, 47 Weryfikacja hipotez, 164 Widzenie barwne, 16 Współczynnik zgodności, 92 Współczynniki Fouriera, 113 Wydzielanie cech obrazu, 95 cechy histogramu, 95 Wydzielanie zmian jaskrawości operator Canny, 76 operator Kirscha, 76 operator laplasjanu, 77 operator Marr-Hildreth, 76 operator Prewitta, 77 operator Robertsa, 73 różnicowe, 74 Wykrywanie zmian jaskrawości, 71 operator Sobela, 77 Wrykrywaqnie zmian jaskrawości metoda Haralicka, 83 Zbiór uczący, 167 Właściwości topologiczne obra- > L Literatura [1] K.R. Castleman. Digital Image Processing. Prentice Hall, En-glewood Cliffs, NJ, USA, 1996. [2] R.C. Gonzalez, R.E. Woods. Digital Image Processing. Addison-Wesley, Reading, MA, USA, 3rd edition, 1992. [3] B. Jahne. Digital Image Processing: Concepts, Algorithms, and Scientific Applications. Springer-Verlag, London, 3rd edition, 1995. [4] A.K. Jain. Fundamentals of Digital Image Processing. Prentice Hall, Englewood Cliffs, NJ, USA, 1989. " [5] M. Minsky. Na drodze do stworzenia sztucznej inteligencji, w Maszyny matematyczne i myślenie red. E. Feigenbaum, J. Feldman. WNT, Warszawa, 1972. [6] E.B. Hunt. Artificial Intelligence. Academic Press, New York, 1975. [7] L.G. Roberts. Machinę perception of 3-d solids. Phd. thesis, MIT, Cambridge, Mass., 1963. [8] A. Guzman. Computer recognition of three-dimensional objects in a visual scenę. Phd. thesis, MIT, Cambridge, Mass., 1968. [9] G. Falk. Machinę analysis of multi-body scenes. Phd. thesis, Stanford University, Computer Science Department, 1970. [10] E.P. Putjatin, S.L Awjerin. Obrabotka izobrażenij w robototech-nikie. Maszinostrojenie, Moskwa, 1990. [11] A.N. Pisarjewskij, A.F. Czernjawskij (eds). Ststemy technicze-skogo zrenija. Maszinostrojenie, Leningrad, 1988. 198 Literatura [12] T.N. Cornsweet. Visual Perception. Academic Press, New York, 1970. [13] C. E. Shannon. A mathematical theory of communication. Bell Systems Technical Journal, 27:379.423, 1948. [14] N. Otsu. Discriminant and least sąuare threshold selection. Proc. 4th IJCPR, Tokyo, pages 592-596, 1978. [15] H.C. Andrews, CL. Patterson. Outer product expansions and their uses in digital image processing. IEEE Trans, on Compu-ters, C-25(2):140-148, 1976. [16] W. K. Pratt. Digital Image Processing. Wiley, New York, 2 edition, 1991. [17] M. Kuwahara. Digital Processing of Biomedical Images. K. Preston, M. Onoe (eds), chapter Processing of Rl-angio-cardiographic images, pages 187-203. Plenum Press, New York, NY, 1976. [18] R.J. Schalkoff. Digital Image Processing and Computer Vision. Wiley, New York, 1989. [19] R.C. Jain, R. Kasturi, B.G. Schunck. Machinę Vision. McGraw-Hill, New York, 1995. [20] E. Hildretli D. Marr,. Theory of edge detection. Proc. Royal Soc, B207:187 - 217, 1980. [21] J. Canny. A computational approach to edge detection. IEEE Trans, on PAMI, 8(6):769 - 789, 1986. [22] R. M. Haralick. Digital step edges from zero-crossings of second directional derivative. IEEE Trans, on PAMI, 6(l):58-68, 1984. [23] L.J. Galbiati Jr. Machinę Vision and Digital Image Processing Fundamentals. Prentice Hall Inc., Englewood Cliffs, 1990. [24] R. Deriche, O.D. Faugeras. 2-d curve matching using high cu-rvature points: application to stereo vision. In Wth Int. Conf. on Pattern Recogmtion, pages 240-242, Atlantic City, 1990. Literatura 199 [25] C. Harris, M. Stephens. A combined corner and edge detector. In Proc. Ąth Alvey Vision Conference, pages 189-192, Manchester. 1988. [26] L. Kitchen, A. Rosenfeld. Gray-level corner detection. Pattern Recognition Letters, pages 95-102, 1982. [27] J.A. Noble. Finding corners. Image and Vision Computing, 6(5):121-128, 1988. [28] R. Haralick, K. Shanmugam,, I. Dinstein. Textural features for image classification. IEEE Trans, on Systems, Man, and Cyber-netics, SMC-3(6):610-621, 1973. [29] R.M. Haralick, L.G. Shapiro. Computer and Robot Vision. Addison-Wesley, Reading, MA, 1993. [30] S. Mori, T. YamawakH. Tamura,. Texture features correspon-ding to visual perception. IEEE Transactions on Systems. Man. and Cybernetics, SMC-8(6):460-473, 1978. [31] M. Hu. Pattern recognition by moment invariants. Proc. I RE., 49:1428, 1969. [32] J. Flusser, T. Suk. Pattern recognition by affine moment inva-riants. Pattern Recognition, 26:167-174, 1993. [33] Y.H. Hong, A. Khotanzad,. Invariant image recognition by ze-rnike moments. IEEE Trans, on PAMI, 12(5):489-498, 1990. [34] J. Serra. Image Analysis and Mathematical Morphology. Acade-mic Press, New York, 1982. [35] H. Minkowski. Volumen und oberflache. Mathematische Anna-len, 57:447-495, 1903. [36] H. Hadwiger. Vorlesubgen 'uber inhalt. oberflache und isoperi-metrie. Springer-Verlag, Berlin, 1957. [37] G. Matheron. Random sets and integral geometry. Wiley, New York, 1975. [38] R. Haralick, S. Sternberg, X. Zhuang. Image analysis using mathematical morphology. IEEE Trans, on PAMI, 9(4):532-550, 1987. 200 Literatura [39] E.R. Dougherty, Ch.R. Giardina. Image Processing - Continuom to Discrete, vol.l, Geometrie, Transform, and Statistical Methods. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1987. [40] P. Maragos. Differential morphology and image-processing. Image Processing, 5(6):922-937, 1996. [41] P. Soille. Morphological Image Analysis: Pnnciples and Applications. Springer- Verlag, 1999. [42] R. O. Duda, P.E. Hart. Pattern Classification and Scenę Analysis. Wiley, New York, 1973. [43] R. O. Duda, P.E. Hart, D.G. Stork. Pattern Classification. Wiley, New York, 2nd edition, 2001. [44] W. S. Yambor. Analysis of pca-based and flsher discriminant-based image recognition algorithms. Technical Report CS-00-103, Computer Science Department, Colorado State University, July 2000. [45] D.P. Mukherjee, S.T. Acton. Area operators for edge detection. Pattern Recognition Letters, 21(6-7):771-777, 2000. [46] P. Bhattacharya, A. Rosenfeld, I. Weiss. Point-to-line mappings as hough transforms. Pattern Recognition Letters, 23(14): 1705-1710, 2002. [47] P. Bhattacharya, A. Rosenfeld, I. Weiss. Geometrie and alge-braic properties of point-to-line mappings. Pattern Recognition, 36(2):483-503, 2003. [48] H. Murase S. Baker, S.K. Nayar. Parametric feature detection. International Journal of Computer Vision, 27(l):27-50, 1998. [49] D.H. Ballard, CM. Brown. Computer Vision. Prentice Hall, Englewood Cliffs, NJ, 1982. [50] P.M. Chen. Variant codę transformations for linear ąuadtrees. Pattern Recognition Letters, 23(11): 1253-1262, 2002. [51] T. Chen, Q.H. Wu, R. Rahmani-Torkaman, J. Hughes. A pseudo top-hat mathematical morphological approach to edge detection in dark regions. Pattern Recognition, 35(1):199-210, 2002. Literatura 201 T. F. Cootes, G. J. Edwards, C. J. Taylor. Active appearance models. IEEE Trans, on PAML 23(6):681-685, 2001. E.R. Davies. Machinę Vision: Theory, Aigorithms, Practicali-ties. Academic Press, San Diego, 1990. E.R. Davies. Truncating the hough transform parameter space can be beneficial. Pattern Recognition Letters, 24(1-3): 129-135, 2003. A. Dorais, D. Sagi. Contrast masking effects change with prac-tice. Vision Research, 37:7'37-7'44, 1997. O.D. Faugeras. Three-Dimensional Computer Vision: A Geometrie Viewpoint. MIT Press, Cambridge, MA. 1993. J. Flusser. Refined moment calculation using image błock repre-sentation. Image Processing, 9(11): 1977-1978, 2000. J.M. Foley. Humań luminance pattern-vision mechanisms: masking experiments reąuire a new model. Journal of the Optical Society of America A, 11(6):1710-1719, 1994. D.A. Forsyth, J. Ponce. Computer Vision: A Modern Approach. Prentice-Hall, 2003. K. Fukunaga. Introduction to Statistical Pattern Recognition. Academic, New York, 2nd edition, 1990. A. Giblin. Area-based medial axis of planar curves. International Journal of Computer Viston, 60(3):203-224, 2004. R.H. Glendinning. Robust shape classification. Signal Processing, 77(2):121-138, 1999. J. Goutsias, L. Vincent, D.S. Błoomberg. Mathematical Mor-phology and Its Applications to Image and Signal Processing. Kluwer, 2000. G. H. Granlund, H. Knutsson. Signal Processing for Computer Vision. Kluwer Academic Publishers, Dordrecht, The Nether-lands, 1995. P. Hauptmann. Sensors: Principles and Applications. Prentice-Hall Inc., Englewood Cliffs, NJ, 1993. 202 Literatura [66] B.K.P. Hora. Robot Vision. MIT Press, Cambridge, 1986. [67] G.W. Wei, Z.J. Hou. A new approach to edge detection. Pattern Recognition, 35(7):1559-1570, 2002. [68] P.V.C. Hough. Method and means for recognizing complex pat-terns, 1962. US Patent3,069,654. [69] S. Impedovo. Progress in Image Analysis and Processing. World Scientific, Singapore, 1994. [70] E. Karabassis, M.E. Spetsakis. An analysis of image interpola-tion, differentiation, and reduction using local polynomial fits. Graphical Models and Image Processing, 57(3)".183-196, 1995. [71] A.L. Kesidis, N. Papamarkos. On the gray-scale inverse hough transform. Image and Vision Computing, 18(8)-.607-618, 2000. [72] A.L. Kesidis, N. Papamarkos. A window-based nwerse hough transform. Pattern Recognition, 33(6):1105-1117, 2000. [73] D.S. Kim, W.H. Lee, I.S. Kweon. Automatic edge detection using 3x3 ideał binary pixel patterns and fuzzy-based edge thre-sholding. Pattern Recognition Letters, 25(1):101-106, 2004. [74] W.-Y. Kim,Y.-S. Kim. A region-based shape descriptor using zemike moments. Signal Processing: Image Communication, 16:95-102, 2000. [75] R. Klette, K. Schluens, A. Koschan. Computer Vision. Springer, Singapore, 1998. [76] G.E. Legge, J.M. Foley. Constrast masking in human vision. Journal of the Optical Society of America, 70(12):1458-1471, December 1980. [77] J.S. Lim. Two-dimensional Signal and Image Processing. Pren-tice Hall Signal Processing Series. Prentice-Hall, Englewood Cliffs, NJ, USA, 1990. [78] S. Loncaric. A survey of shape analysis techniąues. Pattern Recognition, 31 (8)-.983-1001, 1998. Literatura 203 [79] P. Maragos, R.W. Schafer, M.A. Butt. Mathematical Morpho-logy and Its Applications to Image and Signal Processing. Klu-wer, 1996. [80] D. Marr. Vision: A Computational Investigation into the Humań Representation and Processing of Visual Information. W.H. Freeman and Co., 1982. [81] J. Sivaswamy L. Middleton,. Edge detection in a hexagonal-image processing framework. Image and Vision Computing, 19(14):1071-1081, 2001. [82] H.H. Nagel. Digitale Bildverarbeitung / Digital Image Processing. Springer-Verlag, Berlin, 1977. [83] R. Nevatia. Machinę Perception. Prentice Hall, Englewood Cliffs, NJ, 1982. [84] W. Niblack. An Introduction to Digital Image Processing. Prentice Hall, 1986. [85] J. P. Oakley, M. J. Cunningham. A function space model for di-gital image sampling and its application in image reconstruction. Computer Vision, Graphics and Image Processing, 49:171-97, 1990. [86] J. R. Ohm, F. B. Bunjamin, W. Liebsch, B. Makai, K. Muller, A. Somlic, D. Zier. A set of visual feature descriptors and their combination in a low-level description scheme. Signal Processing: Image Communication, 16(1-2): 157-179, 2000. [87] W. Osberger, A. J. Maeder. Automatic identification of per-ceptually important regions in an image using a model of the human visual system. In International Conference on Pattern Recognition, Brisbane, Australia, August 1998. Preprint. [88] J. R. Parker. Algorithms for Image Processing and Computer Vision. John Wiley & Sons, Inc., New York, USA, 1997. [89] F.A. Pellegrino, W. Vanzella, V. Torre. Edge detection revisited. IEEE Transactions on Systems. Man and Cybernetics, Part B, 34(3):1500-1518, 2004. 204 Literatura [90] M. Petrou, P. Bosdogianni. Image Processing: The Fundamen-tals. John Wiley& Sons, 1999. [91] I. Pitas. Digital Image Processing Algorithms and Applications. John Wiley & Sons, Inc., 2000. [92] W. K. Pratt. Vector space formulation of two-dimensional signal processing operations. Computer Graphics and Image Processing, 4(3):l-24, September 1975. [93] G.X. Ritter, J.N. Wilson. Handbook of computer Vision Algorithms in Image Algebra. CRC Press, Boca Raton, FL, 1996. [94] R. Owens B. Robbins,. 2d feature detection via local energy. Image and Vision Computing, 15(5):353-368, 1997. [95] R. A. Roberts, C.T. Mullis. Digital Signal Processing. Addison-Wesley, Reading, MA, USA, 1987. [96] A. Rosenfeld, A.C. Kak. Digital Picture Processing. Vol. 1 i 2. Academic Press, 2nd edition, 1982. [97] H. Samet. The ąuadtree and related hierarchical data structures. ACM Comput. Surv, 16(2): 187-260, 1984. [98] J.L.C. Sanz. Image Technology: Aduances in Image Processing, Multimedia, and Machinę Vision. Springer, Berlin, 1995. [99] I. Sanz, M.L. Calvo, M. Chevalier, V. Lakshminarayanan. Per-ception of high-contrast bmrred edges. Journal of Visual Com-munication and Image Representation, 12(3):240-254, 2001. [100] W.F. Schreiber. Fundamentals of Electronic Imaging Systems. Springer series in Information Sciences. Springer-Verlag, New York, NY, USA, 1986. [101] R. R. Schultz. R. L. Stevenson. A bayesian approach to image expansion for improved definition. IEEE Trans, on Image Proc, 3(3):233-242, May 1994. [102] Y. Shirai. Three-Dimensional Computer Vision. Springer-Yerlag, 1987. Literatura 205 [103] G. Ayala, A. Simó, E. de Ves. Resuming shapes with applica-tions. Journal of Mathematical Imaging and Vision, 20(3):209-222, 2004. [104] M. Sonka, V. Hlavac, R. Boyle. Image Processing, Analysis, and Machinę Vision. Chapman & Hall London, London, 1993. [105] T. N. Tan. Rotation invariant texture features and their use in automatic script identification. IEEE Trans, on PAMI, 20(7):751-756, 1998. [106] S.L. Tanimoto, A. Klinger. Structured Computer Vision: Machinę Perception through Hierarchical Computational Structu-res. Academic Press, New York, 1980. [107] CC. Teh, R.T. Chin. On image analysis by the methods of moments. IEEE Trans, on PAMI, 10:496-513, 1988. [108] CS. Tong, Y.W. Yeung. Boundary location from rangę data using hough transform. Pattern Recognition, 34(10):1975-1982, 2001. [109] C Torras. Computer Vision, Theory and Industrial Applications. Springer, New York, 1992. [110] J. Domingo, A. Simó, E. de Ves, M.E. Dfaz, G. Ayala. Robust descriptors of binary shapes with applications. International Journal of Computer Vision, 34(1):5-17, 1999. [111] A. B. Watson, J. A. Solomon. A model of visual contrast gain control and pattern masking. Journal of the Optical Society of America A, 14, 1997. [112] J. Biemond S. J. P. Westen, R. L. Lagendijk. Perceptual image ąuality based on a multiple channel hvs model. In Proceedings ICASSP-95 (IEEE International Conference on Acoustics. Speech and Signal Processing), volume 4, pages 2351-2354, 1995. [113] Y.H. Tsai Y.H. Yang, K.L. Chung. A compact improved quad-tree representation with image manipulations. Image and Yision Computing, 18(3):223-231, 2000. 206 Literatura [114] Z. Yu, C. Bajaj. A segmentation-free approach for skeletoni-zation of gray-scale images via anisotropic vector diffusion. In Proc. of 2004 IEEE International Conference on Computer Vi-sion and Pattern Recognition (CVPR 'OĄ), pages 415-420, Washington, DC, June 2004. [115] Cłi. T. Zahn, R. Z. Roskies. Fourier descriptors for piane closed curves. IEEE Trans, on Computer, C-21(3):269-281, 1972. [116] S. Zheng, J. Liu, J.W. Tian. A new efficient svm-based edge de-tection method. Pattern Recognition Letters, 25(10):1143-1154, 2004. [117] W. Skarbek. Metody reprezentacji obrazów cyfrowych. Akademicka Oficyna Wydawnicza, 1993. [118] W. Skarbek. Multimedia - Algorytmy i Standardy kompresji. Akademicka Oficyna Wydawnicza PLJ, 1998. [119] R. Tadeusiewicz, M. Flasiński. Rozpoznawanie obrazów. PWN, Warszawa, 1991. [120] W. Sobczak, W\ Malina. Metody selekcji i redukcji informacji. WNT, Warszawa, 1985. [121] M. Kurzyński. Rozpoznawanie obrazów. Metody statystyczne. Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław, 1997. [122] M. Nieniewski. Morfologia matematyczna w przetwarzaniu obrazów. Akademicka Oficyna Wydawnicza, Warszawa, 1998. [123] R. Tadeusiewicz, P. Korohoda. Komputerowa analiza i przetwarzanie obrazów. FPT, Kraków, 1997. [124] R. Tadeusiewicz. Komputerowa analiza i przetwarzanie obrazów. WrNT, Warszawa, 1992. [125] J. Woźnicki. Podstawowe techniki przetwarzania obrazu. WKŁ, Warszawa, 1996. [126] W. Malina, S. Ablameyko, W. Pawlak. Podstawy cyfrowego przetwarzania obrazów. Exit, Warszawa, 2002. [127] A. Materka. Elementy cyfrowego przetwarzania 1 analizy obrazów. PWN, Warszawa-Łódź, 1991. Literatura (128] H. Minkowski r Leip%-Berlin; uS"-* ^anilungen. ^^ 11 i* . 33 t PROBLEMY WSPÓŁCZESNEJ NAUKI TEORIA I ZASTOSOWANIA INFORMATYKA Przedstawiamy Państwu serię wydawniczą "Problemy Współczesnej Nauki. Teoria i Zastosowania", w której ukazują się publikacje prezentujące aktualny stan wiedzy w wybranych dziedzinach nauki: INFORMATYKA, STATYSTYKA, ZARZĄDZANIE, ROBOTYKA, AUTOMATYKA, INŻYNIERIA LINGWISTYCZNA oraz MEDYCYNA I INFORMATYKA. Monografie naukowe publikowane w naszej serii wydawniczej często są podstawą do uzyskania przez ich autorów stopnia naukowego doktora, doktora habilitowanego czy tytułu naukowego profesora w określonym zakresie nauki. Tytuły prezentowane jako podręczniki akademickie wielokrotnie wyróżniane są nagrodą Ministra Edukacji Narodowej. Wszystkie pozycje wydane w tej serii zostały wysoko ocenione przez Komitet Badań Naukowych przy ocenie efektywności polskich placówek naukowych. Nasze publikacje adresowane są do polskiego środowiska naukowego oraz do wszystkich, którzy pragną pogłębić swoją wiedzę i rozwinąć własne zainteresowania. W gronie autorów można znaleźć wybitne autorytety naukowe i znane nazwiska twórców współczesnej nauki - polskiej i światowej. Zapraszamy do współpracy - prof. dr hab. Leonard Bole, Instytut Podstaw Informatyki Polskiej Akademii Nauk, ul. Ordona 21, 01-237 Warszawa, tel. (O-prefiks-22) 836-28-41, e-mail: bolc@ipipan.w Informacje o książkach wydanych w naszej serii dostępne są pod adresem: http://www.ipipan.waw.pl/~bolc/aow.html Na stronie www.exit.pl znajdują się książki 9788387674892 dostępne w sprzedaży internetowej. Można ^u\\um\mumm również korzystać z adresu e-mail: lang@exit.pl