Choraś komputerowa wizja, School, informatyka

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

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

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

Rozdział 1. Wprowadzenie w problematykę komputerowej wizji

Tablica 1.1: Przetwarzanie obrazów i zagadnienia pokrewne

ObrazOpisObrazPrzetwarzanie obrazów Komputerowa wizjaRozpoznawanie obrazów Komputerowa wizjaOpisGrafika komputerowaTransformacja opisukomputerowej 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

Wynik4_

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

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

?/,>???

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,

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

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-

< )<lbieramy, zatem tylko światło, które mieści się w zakresie tzw.

i optycznego. Okno optyczne to przedział długości fali elektroma-

rznej (światła) od ok. Ą00 nm, (co odpowiada światłu o barwie

d"l. iowcj) do ok. 100 nm, (co odpowiada światłu o barwie czerwo-

Kysunek 2.4). Powyżej długości 100 nm znajduje się niewidoczna

lowieka podczerwień, a poniżej Ą00 nm, również niewidoczny,

<liolet. Do fal elektromagnetycznych zaliczamy także niewidoczne

złowieka promienie gamma, promienie X i inne. Promieniowanie

u długości fali spoza okna optycznego nie jest przepuszczane przez ro-

i'/ oka. Promieniowanie, które wniknie do oka w różnym stopniu

• luje reakcje elektrochemiczne w czopkach i pręcikach stając się

rodłem bodźców. Ze względu na różną budowę czopków i pręcików

? 'pują różne właściwości widzenia ciemnego (przy małym oświe-

? i• r 1111) i jasnego (przy dużym oświetleniu). Przyjmuje się maksimum

i ilości czopków jako 550 nm, a pręcików jako 510 nm. ulżenia techniczne mogą tylko w większym lub mniejszym przy-tiiu naśladować oko ludzkie i złożony proces percepcji bodźców 11 Łych przez narząd wzroku człowieka. Najbardziej wewnętrzną warstwę oka stanowi siatkówka, zbu-ma z wielu warstw komórek nerwowych. Jedną z tych warstw iowią komórki światłoczułych receptorów - pręciki i czopki. Pełnią ?•nr zasadniczo odrębne funkcje w procesach postrzegania światła, niskich poziomach oświetlenia poniżej 0,0llx czynne są jedynie i ki i wtedy zachodzi widzenie skotopowe. Intkówka jako odbiornik promieniowania elektromagnetycznego I uulowana jest z dwóch rodzajów komórek światłoczułych: czopków

I pręcików połączonych za pomocą nerwów z mózgiem. Czopki

II względnie niskiej czułości przeznaczone są do obserwacji przy

i le dziennym. Ich maksymalne zagęszczenie występuje w dołku

lalkowym. Jeśli zatem obraz obserwowanego przedmiotu znajdzie

• dokładnie w tym obszarze uzyskujemy wtedy najlepsza zdolność

dzielczą. Wraz ze spadkiem natężenia światła wpadającego do

rośnie średnica źrenicy. W momencie, gdy czułość czopków jest

niewystarczająca do prowadzenia obserwacji, mimo dużych wymiarów

Rozdział 2-System

wzrokowy człowieka

W|.t..wadzenie

fotonu (eleWronowoKy)

r» t<r*

Energi* jednego

ltr, t(r* v* wr* ««* w

W* 10*

CzetotfiwoieCHz) 0 rf „V if łf

l0- * «r rj2U?J? 10"

Długość fali (metry) rf 10J

Fale radiowe

„., ,„-, ,.» »- -• »- ** T" '• "

podczerwień

ES^lJ?— |?"-Ł^«—"

Ultrafiolet

Rysunek 2.3: Widmo elektromagnetyczne

światło wtoa^ 400-700nm

100

Czułość względna

1000

400

(Z** «*•* M*»—U-"* ""

600

500

d^™ t^- podczerwień Promieniowania c,amma /widmo widzia.ne

400

Odpowfedż fticfckfego oka (fc/m/r-ancja)

bodziec świetlny ludzkiego oka i

Rysunek 2-4: Widmo wHrf-1-^^owego

• ,;„ pręciki Pręciki znajdują się

źrenicy, funkcje receptorów g*™" « zagęszczenie znajduje sie

poza dołkiem środkowym J"^ od jego środka, (dlatego wdzeme

. odleglośei ^to»V\Xry?^ym). Przy dużym nat,zenm

nocne nazywamy wmzenem P™^«. światla przy uzycm

świat.a pręciki ^^ mo4emy zaobserwować prze-

specjalnego barwnika. Jego

ciemnego pomieszczenia do jasnego lub odwrotnie (efekt lin) Proces przystosowania wzroku do warunków oświetlenia 'in\ adaptacją.

Iowiek postrzega jedynie różnice jasności (nie ma wrażeń

li). Kiedy poziom oświetlenia przekracza ok. 30lx mamy

liienia z widzeniem fotopowym czyli widzeniem barwnym.

nu nem procesu tego widzenia jest tzw. zjawisko metameryzmu

11 u'rozróżniania składu spektralnego promieniowania świetl-

Bodziec świetlny zostaje w warstwie komórek światłoczułych

ilorów przetworzony na impulsy elektryczne, które są następnie

wane wypustkami nerwowymi do komórek dwubiegunowych,

ii/pnie do komórek zwojowych. Długie wypustki komórek zwo-

li l/w. aksony, tworzą nerw wzrokowy kończący się w ośrodku

? iłowym drogi wzrokowej. Sygnał stamtąd jest przekazywany do

i potylicznej kory mózgowej. Jak już wspomniano wcześniej, w

iwce oka ludzkiego istnieją dwa rodzaje fotoreceptorów, pręciki i

i| 'li w przybliżeniu Ibrnln 4- I50mln pręcików i ok. 5mln -J- 7mln

ków. Czopki są rozmieszczone najgęściej w środkowej części

• wki - w plamce i są czynne tylko w świetle. W tej okolicy każda

komórka receptora łączy się z osobnym włóknem nerwu wzrokowego

daje możliwość dokładnego przenoszenia bodźców do mózgu.

i akiej budowie plamki, uzyskiwana jest wysoce precyzyjna

i oglądanego obrazu. Przy widzeniu dziennym ostrość wzroku jest

nialna w centrum siatkówki w wycinku objętym kątem 1° -=-2°.

W i nz ?/, przesuwaniem się obrazów ku obwodowi ostrość wzroku szybko

je osiągając | wartości w odległości odpowiadającej kątowi 5° i

odległości odpowiadającej kątowi 20° . Dzieje się tak, gdyż na

•dzie siatkówki tylko ok. 100 -f- 200 receptorów łączy się z jednym

nem nerwowym, przez co nie ma dostatecznego odbierania

i'wodzenia bodźców świetlnych. Proces widzenia zachodzi w

sposób, ponieważ w fotoreceptorach znajdują się substancje

itłoczułe. Światłoczułe elementy siatkówki zostają odtwarzane

? u'inności, a ulegają rozpadowi w świetle. Ciągłe odtworzenia w

mości i rozpad w świetle ustalają stan zależności siatkówki, a tym

mi viii i wrażeń wzrokowych, od stanu oświetlenia.

I 'rzekształcenia i redukcja informacji w siatkówce nie ogranicza się

I ko do przekształceń i przenoszenia potencjałów w jednym kanale

nloiinacyjnym, jaki tworzy ciąg kolejnych komórek nerwowych.

Proces redukcji informacji odbywa się też w strukturach poziomych powierzchni siatkówki. Receptor oświetlony silniej wywiera hamujący wpływ na znajdujący się obok słabiej oświetlony receptor, co w konsekwencji powoduje zwiększenie kontrastu, ale zmniejsza ilość informacji. Proces widzenia nie jest jeszcze poznany w całości, w każdym razie jego faza początkowa ma charakter zmian fotochemicznych.

Jeden z produktów rozpadu światłoczułej substancji zmienia potencjał elektryczny przewodzących neuronów siatkówki i energia świetlna zostaje przetworzona w energię elektryczną. Komórki receptorów stają się wówczas jakby mikroogniwem. Wskutek tego następuje wyładowanie impulsów elektrycznych z obu gałek ocznych w postaci bioprądów do włókien nerwu wzrokowego, a następnie impulsy zostają przekazane do dróg wzrokowych w mózgu i do potylicznej części kory mózgowej. W mózgu impulsy elektryczne są analizowane i przetwarzane w jeden obraz. Siatkówka odbiera bodźce barwne fal świetlnych, ale to od funkcji mózgu zależy, jakie barwy spostrzegamy. Widzenie barwne wg. teorii Younga-Helmholtza, przedstawiono schematycznie na Rysunku 2.5. Mózg analizuje sygnały r, g, b i od ich wzajemnego stosunku zależy wrażenie barwy. Od wartości sumy tych sygnałów zależy odczucie jasności (luminancji) bodźca świetlnego. Im większa jest suma (r + g + b) tym wrażenie jasności bodźca świetlnego jest większe. Dla stosunku r : g: b = 1:1:1 mamy wrażenie bieli lub szarości.

Narząd wzroku charakteryzuje się właściwością dostosowywania do poziomu oświetlenia, czyli adaptacją do jasności oraz właściwością dostosowywania się do składu widmowego oświetlenia, czyli adaptacją do barwy. Oprócz tego występują takie zjawiska jak zjawisko powidokowe (kontrast barwny następny) i tzw. kontrast barwny równoczesny polegający na tym, że odbieramy różnicę barwności dwóch pól barwnych o identycznych właściwościach spektralnych oświetlonych jednym źródłem światła, o ile każde z tych pól znajduje się w otoczeniu o innej barwie. Analogicznie występuje też kontrast równoczesny luminancji polegający na tym, że z dwóch rozważanych pól to jest odbierane jako jaśniejsze, które znajduje się na ciemniejszym tle (Rysunek 2.6). Możemy więc scharakteryzować bodziec świetlny jak na Rys. 2.7.

W|>n iw.nl/rmr

Uktad zobrazowania

E{A)

Jk Współczynnik

ttgljr uwzględniający

R( X ) zjawiska

absorpcji i odbicia

Układ zobrazowania

* r

* b

SM) 1I *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.

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

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

Rysunek 2.8: Kontrast C = ^r

c =

(L0b — Lt\a) _ AL

tla

Hla

(2.3)

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. ' '-'minlubC ={Lob — Ltla)(Lot + Lt\a)

(2.4)

(2.5)

'-»»?'-»,>

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

I.+Al.

..?:,&

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

l 11 iikt my systemu wzrokowego człowieka.

Czułość kontrastowa

Cykle na stopień

Rysunek 2.13: Charakterystyka czułości HVS

OTYCZWy

SYSTEM

OKACHARAKTERYSTYKAKOMÓRKI LATERALNE•..u.*.

SIATKÓWKI

' ' ' *WYFILTR m.cz.TRANSFORMACJA LOGARYTMICZNAFILTR

Vi.CZ.***M

k-ty

IKZeSTRZENNY

KANAŁTPROGOWANtEEXCLUSNE OR

-JSZUM

linek 2.14: Model systemu wizyjnego człowieka. Model analizatora widzenia model techniczny HVS (b) i mechanizm wykrywania bodźców (c)

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^^

Tablica 3

/orników obrazowych elektro

.1: Charakterystyki pewnych przetw optycznych

1'f/etworniki obrazowe optyczno-elektryczne

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.

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

Rozdział^^Ś^-^^

rdworniki obrazowe optyczno-elektryczne

+ 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

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

Kondensatory złączowe

Ogniwo rejestru

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.

<P1°-

Rysunek 3.5: Schemat rejestru przesuwającego BBD

?łi

tiMiM

tr1

L l l ii

ił

? *-

li i

* i * i * i

m*m

-»1T|T|T|T| | iTiTiTiTl

1 ił ł liii

Rejestr wyjściowy

,8r<r

(3-1)

I 1 1 / ' ]~F

F jest ogniskową soczewki.

obrazem tworzonym jak na Rysunku 3.7 związany jest układ ? lnyeh przedstawiony na Rysunku 3.8.

Rysunek 3.7: Idealna kamera i jej geometria

Rysunek 3.8: Układ współrzędnych z punktem widzenia w O

Układ współrzędnych XY Z powiązany jest z rozpatrywaną sceną, płaszczyzna Z — j traktowana jest jak płaszczyzna obrazu. Punkt i' sceny rzutowany jest na płaszczyznę obrazu tworząc, w miejscu przecięcia płaszczyzny obrazu z promieniem łączącym punkt P z początkiem układu współrzędnych O, obraz punktu P. Jest to rzutowani* (projekcja) perspektywiczne (centralna).

(3.1

Niech będzie dany układ współrzędnych kartezjańskich xy w płasz czyźnie obrazu, w taki sposób, że osie x i y są odpowiednio równolegli do osi X i Y. Punktem początkowym płaszczyzny obrazu jest punki (0,0, /) wyznaczony przez przecięcie osi Z z płaszczyzną obrazu. Zgod nie z Rysunkiem 3.8, punkt sceny o współrzędnych (X, Y, Z) jest rzn towany na płaszczyznę obrazu tworząc punkt o współrzędnych obraz' (x, y) określonych przez:

y =

x z

deometria systemu przetwornika obrazu

I '"i< >\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

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)}®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

f(x.y)

cowBru.vj= — v v j(u-k^,v-r-*)

' ab ~~ — *? »' /V

Model

f(x,y)

Próbkowanie

comb(x.y)

-®

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

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)® E S ^

0,0 fc=-Co!=-CO

i oo oo i

afefc^oo^oo

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)

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)

Rozdział 3. Akwizycja

obrazu

i I /linwa reprezentacja obrazów

«„ 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

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

Rozdział 3. Akwizycja obrazu

.«__

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'.

J-1

r0 r1 r2

Syg. wyjściowy l

'LIZ

~ d,i n

<L/2)-\ r,

J I L

d! ^ *,,n

{L i 1) -1 Syg. wejściowy

dj - poziomy decyzyjne r - poziomy odtwarzania

L/2

unek 3.16: Położenie poziomów decyzyjnych i odtwarzania w reprezentacji liniowej i dwuwymiarowej

Uwzględniając, że optymalny poziom odtwarzania leży w środku iledzy każdą parą poziomów decyzyjnych możemy otrzymać

j-i

:r = 77;Y,P(rj)ldj+i-d3?

(3.21)

1 >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)

+ 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-%^<f<iM)

j=0

W szczególnym przypadku jednostkowej gęstości prawdopodobieństwa minimalny błąd średniokwadratowy wynosi

(3.28)

Smin 10

> 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

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=l

(3.33)

dział 3 Akwizycja obrazu H Cyfrowa reprezentacja obrazów

[T]= fU ° < ' < M , ° < / < w

N-1

M \

0 1 2

w*s; r

9410010411912 51361431531571581031041069610311914115515516010!136136123li7811714915516011013014414912 8789715116115810913717816711S78101185193161100143167134373513 421620917210412316616115516020 522921918112513117217919020823323722320013114 S172175199228Ul2382292G616116$162163193228230237220199 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:

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

I I łistogram obrazu i jego modyfikacje 49

(4.1)

9i.i= T<fi.i ^

Operator T działa na pojedynczym elemencie obrazu

Metody przetwarzania obszarów (masek)

Obraz wyjściowy

Obraz wejściowy

I Operator działa na

] otoczeniu

1 przetwarzanego elementu

1 obrazu

Metody przetwarzania pojedynczych punktów obrazu

Obraz wejściowy Obraz wyjściowy

Rysunek 4.1: Operacje wstępnego przetwarzania obrazu

- obraz zawiera tylko dwa obszary (obiekt i tło),

- rozkład poziomów jaskrawości w każdym obszarze jest rozkładem

gaussowskim (Rysunek 4.3b), możemy określić prawdopodobieństwo, że rozpatrywany pbcel ma poziom jaskrawości k

1 iĄ

e ól

P(fe) = p(fc|ó0)P(<$o) + p(k\Si)P(Si)

P(fc) = P5oPs0{k) + PsrPsAk)

c) d)

Rysunek 4.2: Obrazy testowe i ich histogramy

Prawdopodobieństwo błędu przy wybranym progu t wynosi

8(t) = PSl?Sl + P5o?5o (4.2)

= J-ocPs1{k) - prawdopodobieństwo klasyfikacji pbcela należącego do obiektu jako pixela należącego do tła,

- ft°Ph(k) - prawdopodobieństwo klasyfikacji pbcela należącego do tła jako pbcela należącego do obiektu.

gdzie:

Minimum 8(i) (^p = 0) uzyskujemy dla wartości progowej

P6n(k)iP6i(k) - rozkład prawdopodobieństwa pbceli tła i obiektu,

M5o> 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)

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

(i-DN+j

l>|W |

—*?

255

l V

••"••?•I ^*

255

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

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)

I Ha wartości progowej t mamy (qs0(t) + %(*) = 1)

</*(*) = EWO (4-7)

lfc(*)= E hnor(k) (4.8)

? dnie wartości jaskrawości odpowiednio dla elementów obrazu K ych do tła i obiektu określamy następująco

^-Tfa^f-SSjŚ^ (4'9)

"«, w = S"+1 W(M = Ar ? '*--<*) (4-10)

natomiast wartość średnią jaskrawości obrazu przez

z^fc=i n>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

<(t) = Sfc=t^ ^\yfc) = Z7AT. (* - ^)27w(*0(4.13)

%(*) fe=

fe=t+l

Z-ife=t+l hnorik)

a2 = 52(ż-iLł)2/inor(fc). Mamy

(4.14)

gdzie afv(t) jest wariancją wewnątrz klas, natomiast <y2M{t) między klasami.

Globalna wariancja (4.1) nie zależy od wartości progowej t, więc wartość progowa t (Rysunek 4.4) minimalizująca ^(t) będzie jednocześnie wartością maksymalizującą (ĄAt)

o*u(t)

Qs0{t)qs1{t)

(4.16)

100

200 f

Rysunek 4.4: Wybór wartości progowej wg metody Otsu

W rzeczywistości granice pomiędzy obszarami obrazu są rozmyte, dlatego też nie uzyskuje się modalnej struktury histogramu. Oprócz tego, w wielu przypadkach, także wtedy kiedy uzyskuje się modalną strukturę histogramu, bardzo trudno jest zlokalizować wartość progową jaskrawości, ponieważ „minima" są bardzo szerokie i płaskie.

i i Histogram obrazu i jego modyfikacje 53

I tnieje wiele metod pokonania wymienionych trudności. Jedną z

jest określenie wartości progowej jaskrawości na podstawie hi-

11 mi gradientu hi : {0,1,..., K"} —> 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)

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

201105512215775

512660710107

126622710107

2662105775

66215obraz 1

obraz 2

r a

1234560110011111001020100105100012724000210010003

Rysunek 4.6: Zasada tworzenia dwuwymiarowego histogramu obrazu

Niech M(/) będzie funkcją określającą zawartość informacji obrazowej w obrazie daną przez

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

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)

out

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

\K a) + kmin —

n , "smaż® ^min®

b — a

(4.23)

Transformacja powyższa rozszerza skalę jaskrawości do zakresu

[*mini ™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

Negacja

14-1

kouł m

Pierwiastek / / j

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)

<=uiP^fp

—*=T^T9/1a

1 1a 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

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:8IM'\J

\'»\

\!8d\

\s150sS126s90

^>60s1

•»30±s

sj '*.~rs •

30 60 90 120 150 '80 2W 240 ZS5'

240002200020 088'8000168601400C12 ODO10088 8066|6080 48882080 0LmJLI0 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

(4.26)

Transformacja skali jaskrawości obrazu 59

150 W 25B

Rysunek 4.13: Logarytmiczna transformacja jaskrawości obrazu

Xlim

210 189

12B 90

°8

30SD 30 120 130 180 210 2«0255

nm"160 BOB5000640 ODO3000020000mon0 50<00«02002SS

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™ - 1

"rmt

(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-/ <lo określenia nowej wartości każdego elementu obrazu, czyli T(kin) , to uzyskujemy nowy histogram h (k^t) ? Jeżeli rozpa-i\ histogram jako funkcję ciągłych zmiennych wtedy

/ h (u)du = / h(u)du

/o Jo

(4.29)

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

4 ł Filtracja obrazu

«s_.3a_^:-J-A if~\-7 q«Mti,7Hi)ań :- ?296ABOIW/^j2Z _?^y*z* 30 60 90 120 133 188 2H> aa)**

~*,2 :«HHH|? tU iTlft*~ .:2W- 1 ?<t l.'*ićnF 1: Z |!j1SBi^iflZ Btt, .j-*»'???'GO, _-*==" "a a 9 ta,50 180 J.0 MO255

Mson12300Bwas93000i ?'::::::9389340000235005-hi

9«B 19JOO :;.

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)

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-

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

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).

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

Fittr dolnopizepu stówy

Filtr górnoprzepustowy

i-i -i

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

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

M-lN-l

2/(fc> 0=EE a(m' n^^k -™,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^fcJeżeli wektor- AWT -, Ai,kea =L ni,k Jl2x

(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

i macierz

Ci,* 0 0 C,k

(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

©/,* = ©/,*-! + 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.

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.

1111 1 11111 1 11 2 191 1 1101 1 11612 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

.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<ktywność przy eliminacji szumu impulsowego.

Dwuwymiarowy FM (Rysunek 4.23) obrazu {fij, (i,j) € R} jest <I' liniowany jak

yitj = mediana Atfij = mediana[fi+rj+s ; (r,s)C.Ai\ (4.60)

gdzie Ai określa tzw. okno FM.

Obraz wejściowy f(x,y)

1023'-'-15»J202 0252C-i-

Obraz \wyściowyg(x.ypo

10 20 20 15 39 20 20 15 20

Sortowanie

[ 10 15 20 20 '|oj20 20 20 99 j

Mediana

g(x,y)=T[f(x,y)]

Rysunek 4.23: Filtracja medianowa FM

Na Rysunku 4.24 przedstawiono zasadę filtracji FM dla jedno-indnego pod względem jaskrawości fragmentu obrazu (a), obrazu z

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

i Filtracja obrazu

szumem impulsowym (b) oraz bloku obrazu zawierającego krawędzie

(c).

(455566678)

| 6 | 3 | 8 j S I 7 j 6 4 6 I 5"

(4555666873)

73 1 6

(353 323 8 8 8)

33 i S33 ! 833 1 Sc)

Rysunek 4.24: Zasada filtracji medianowej dla różnych bloków obrazu

Przykładowe kształty Ai przedstawiono na Rysunku 4.25.

? II

A4 A5

Rysunek 4.25: Przykładowe kształty okien FM

Niech obraz będzie obrazem skoku jaskrawości tzn. zawierającym dwa zbiory elementów o jaskr awościach a i b, (b > 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

-' 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ą:

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

(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

(4.71)

Maksymalna wartość d->^,y> i wynosi

rM(x,y) 2 + (5f(x,y))2]h

óx

(4.72)

i i Wykrywanie zmian jaskrawości

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

Sf,

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

Tablica 4.1: Różnicowe operatory gradientu

NMW* opera-Wyrażenia do obliczeniaWektory wagowe WqOknoi< 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 . -1i W2 =-1 -1

12X2Mwl.nrtsadlij = fi.j - fi+l,j + l **IJ = fi + l,j - fi,j+lWi =1 0 0

-1i W2 =0

-1

02x2M«« Róż-dlij =

max (/ij./i+ij./i.j+iJi+ij+i)

d2itj =

-min {fi,j,fi+i,j, ftj+l, fi+lj+llNie ma2x2l*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 ?

-1 1

. -1 .; W-2 =-1 -1

0 0 0

1 1

. 1 .3X3dU.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+llWX =- 1 -

-1

2 0

-2 1 0

. -1 .; W2 =-2 -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,

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

h 4 Wykrywanie zmian jaskrawości

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

(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)

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

f5Uf

7U'«Vu\%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,!

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

00-1000-1-2-10-1-216-2-10-1-2-1000-100 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

< »i>t,ymalna aproksymacja dla cr2 = 1,6 • <j\.

Operator Canny jest optymalnym detektorem pozwalającym wyki vwać skoki jaskrawości w obrazie w obecności białego szumu. Ce-• Im je się tym, że wydziela tylko znaczące krawędzie (zmiany jaskrawości), minimalizuje odległość pomiędzy rzeczywistym położeniem /iniany jaskrawości, a uzyskaną odpowiedzią określającą położenie tej •niiany oraz daje tylko jedną odpowiedź odpowiadającą zmianie ja-

iwości. W przypadku dwuwymiarowym wymagane jest określenie orientacji krawędzi

V(f*o) ,

*=m4\ <4-9l)

gdzie ń jest normalną do krawędzi, / obrazem, a g filtrem gaus-?< iwskim.

.vędź jest lokalizowana gdy

/ * 9 = 0 (4.92)

dn2

Algorytm wykrywania zmian jaskrawości z wykorzystaniem operatora Canny (Rysunek 4.32) jest następujący:

1. Realizujemy splot obrazu / z filtrem Gausasa g o współczynniku skali a. Obliczamy

|(/*p) = /*^ = /*ft=>/*-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),

Rozdział 4. Pr^twarranie wstępne obrazu cyfrowego

I I Wykrywanie zmian jaskrawości

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 pocienianiaFiltr Gaussowskii—*?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

•132 7?»-13! 217 2217•>T*!j 722 27227j 217" 22i72• 132 7 21.1

31-5-17-5?11-44-62-68?m.4400li01)H6208m44?31.117i)-:!1

fc,

31-11044-31-5-621)62517-6*iim17i -5•62i)62~i: :il-44044•31

->2222-i-1.i-1.-1_2_2_2_2.2-1-1_ s.i-1?»2?»22

12U_2-421U-1„200I)00-2-1012-1.'»li'1f

*-,

fc,

2-1 1-2 1-1?>2-1-2 -1>>2-1 -2 i -122-11-2 1 -S2•>-1[-2| -i2

1-1-1-1-1i

Hi)?4-202i2•>222

210-1„?)U0U00

120.9.4_?>.-.»_2_'>_2

2ii)-1„->1I1ł1

•1-2u•)4

I 11(1

-i212-4.'}1•}1. ?>00i)1)02-1Ji•121-24_2ł

-121)„\>i-1?>i)-21-1•>U„*>l-1•>U-11-1?>(ł-21

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.

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

4.5. Segmentacja obrazu

(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ów3 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ówMetody relaksacyjneRysunek 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

ś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)<T1 (4.112)

( XK 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

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

cechz —*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|<T (4.H5)

[ jaisz w przypadku przeciwnym

gdzie /, średnia wartość jaskrawości punktów obszaru Si , ustalona wartość progowa.

Rozdział 4. Pr7etwarzanie wstępne obrazu cyfrowego

Średnia jaskrawość pn elementów obrazu należących do obszaru S< i standardowe odchylenie Oi są określone jak następuje

(4.116)

=4 E Mfl

(s,t)eSj

*-tf

? {f(s,t)-l«f

(s,t)6Si

(4.117)

gdzie iV liczba elementów obszaru S*.

Analizę rozpoczynamy od lewego górnego elementu obrazu, przy czym w chwili początkowej wszystkie elementy obrazu mają zerowi)

etykietę.

Algorytm segmentacji obrazu jest następujący:

1. Analizujemy kolejne punkty linii obrazu od lewej do prawej i kolejne linie z góry w dół. Dla każdego analizowanego punktu {s,t) stosujemy punkty 2-7 algorytmu.

2. Obliczamy wartości \ii i ai dla każdego obszaru będącego obszarem sąsiednim do elementu (/i, k)

' _J_[/(h,fc) + AT/Xi]

(4.118)

»i- vZT (/(M) + *)2 + ? (/(M)-*)a (4.119)

/Lij i a- są odpowiednio wartością średnią i odchyleniem standardowym jaskrawości obszaru zawierającego nowy element (h.k).

3. Obliczamy wartość progową T obszaru Si

'-l-^*

(4.120)

gdzie t0 jest stałą wartością progową.

^J. Segmentacja obrazu 93

i I )la każdego obszaru obliczamy

Am = |/(/», k)-in\ (4.121)

leżeli A^ij < T , wtedy etykieta obszaru Si jest możliwą etykietą elementu (h, k).

Jeżeli jest więcej niż jeden obszar sąsiedni do elementu (/i, k) to etykieta punktu (h, k) jest etykietą obszaru, dla którego różnica A/Li, jest minimalna.

7. Jeżeli żaden z obszarów nie spełnia warunków określonych w p.5 i p.6, elementowi (h, k) przydzielana jest nowa etykieta i staje się on pierwszym elementem nowego obszaru.

Należy, jednak zdawać sobie sprawę, że algorytm segmentacji wy-Uutzystujący „wartość średnią" tj. bazujący na kryterium (4.115) ma prwne niedostatki, a mianowicie:

zależność wyników segmentacji od porządku przeglądania punktów obrazu,

konieczność stosowania powtórnego przeglądania w celu likwidacji „ztych obszarów" lub połączenia kilku mniejszych obszarów w jeden,

Wrak teoretycznych podstaw wyboru progu T.

Metoda relaksacyjna

iest to interaktywny adaptacyjny proces pozwalający w optymalny iposób przydzielić punktom obrazu etykiety obszarów, odpowiednio ilo lokalnych właściwości tych punktów i do ogólnej struktury jaskrawości obrazu.

Niech A = {A\, A2,..., Am} oznacza zbiór obiektów, A = {Ai, A2, • • •, Au} to zbiór etykiet dla obiektów z A. Przez B^ określimy zdarzenie {obiekt Aj należy do klasy (ma etykietę) Aj }, a przez P^ prawdopodobieństwo tego zdarzenia. Niech CV,mfc będzie współczynnikiem zgodności pary zdarzeń By i Bmk (np. ilościowo oceniana korelacyjna zgodność zdarzeń). Prawdopodobieństwo P^ iteracyjnie adaptuje się na podstawie innych prawdopodobieństw Pmk i współczynników zgodności Cijmk tak, żeby otrzymać graniczną wartość prawdo-

Rozdział 4. Przetwarzanie wstępne obrazu cyfrowego

podobieństwa przynależności obiektów Ai do klasy Xj. Te graniczne wartości dla ustalonego i mają postać

_ f 1 przy j = k0

Pk°-\0 przy i + ko (412-'

Warunek (4.122) oznacza, że obiekt A{ ma jednoznaczną interprc tację, określoną przez etykietę A^0.

Współczynnik zgodności, zwykle jest normalizowany i przyjmuje wartości — 1 < Cijmk < +1 przy czym: + 1 oznacza silną zgodność zdarzeń Py i Pmfc, — 1 oznacza słabą zgodność zdarzeń Py i Bmk, 0 brak wpływu tych zdarzeń na siebie.

Proces adaptacji przebiega następująco:

1. Jeżeli prawdopodobieństwa Pmk są duże i współczynnik zgodności Cijmk jest bliski +1, to Py- będzie rosło;

2. Jeżeli prawdopodobieństwa Pmk są duże, a Cijmk Jest bliskie —1, to Pij będzie zmniejszać się;

3. Jeżeli Pmk są małe i Cijmk ~ 0 to Py- będzie niezmienne.

Takim warunkom odpowiada wyrażenie

p(„+l) = ^3 l1 + % ) u 123)

gdzie

M K

% = H 12 CijmkPmk (4.124)

m=l fe=l

Do zbieżności procesu wystarczy

hrn P^ = Plfe0 (4.125)

dla każdego i, gdzie K0 - numer etykiety, v - numer iteracji.

Praktyczna realizacja tej metody segmentacji zależy od tego, jak dobrze na podstawie liczbowych charakterystyk punktów obrazu, udało się określić współczynnik zgodności.

Rozdział 5

Analiza obrazu

iiym zagadnieniem komputerowej wizji jest wydzielanie cech ob-na podstawie których może być zrealizowany opis, interpretacja i 11 i/poznawanie sceny obrazowej przez maszynę. Systemy komputerowej wizji (Rysunek 5.1) interpretują wyniki analizy obrazu i paranie itry opisu różnych obiektów obrazu oraz ich wzajemnych relacji w i • nie. Wynikiem procesu analizy obrazu są liczbowe parametry opisu-

obiekty obrazu i decyzja, jakie obiekty zawiera scena, oraz jakie są i jemne relacje pomiędzy tymi obiektami. Analiza obrazu różni się w iposób zasadniczy od innych operacji przetwarzania obrazu, takich jak np. restauracja i poprawianie jakości obrazu, kodowanie obrazu itp., których wynikiem jest obraz. W przypadku idealnym, parametry (ce-i liy) opisujące obiekty powinny być niezależne od położenia i orientacji Obiektu, i powinny umożliwiać rozróżnienie poszczególnych obiektów Obrazu. Do określenia parametrów opisujących obiekty w systemach komputerowej wizji wykorzystuje się informację o jaskrawości i kształ-?e obiektów. W celu uzyskania tych informacji wykorzystujemy tzw. podejście obszarowe (globalne) i/lub bazujące na liniach konturowych. W tym rozdziale skoncentrujemy się na metodach wydzielania cech obiektów oraz operacjach przetwarzania obrazów specyficznych dla procesu analizy obrazu (Rysunek 5.2).

5.1 Reprezentacja obrazu na podstawie jaskrawości -cechy histogramu

Cechy histogramu obliczane są na podstawie histogramu jaskrawości pewnego obszaru obrazu. Jeżeli u jest zmienną losową reprezentującą

Rozdział 5. Analiza obrazu

SYSTEM ANALIZY OBRAZUANALIZA OBRAZUWNIOSKI Z ANALIZYPrzetwarzanie wstępneWydzielanie cechSegmentacjaWydzielanie cechKlasyfikacja OpisAw SYSTEM IN i tKKKt i AUJI, ROZPOZNAWANIE, ROZUMIENIEReprezentacja symbolicznaInterpretacja OpisOBRAZU

Rysunek 5.1: System analizy obrazu

METODY ANALIZY OBRAZU

REPREZENTACJA I WYDZIELANIE CECH

KLASYFIKACJA

- CECHY HISTOGRAMU

CECHY OKREŚLANE NA PODSTAWIE GRANIC OBIEKTÓW

REPREZENTACJA PRZESTRZENNA

?ANALIZA TEKSTURY

? MOMENTY

• CECHY KSZTAŁTU

? PARAMETRY MORFOLOGICZNE

KLASYFIKACJA STATYSTYCZNA

- PASOWANIE

- DRZEWA DECYZYJNE

Rysunek 5.2: Metody analizy obrazu

poziom jaskrawości w określonym obszarze obrazu to prawdopodobieństwo, że zmienna przyjmie określony poziom jaskrawości wyrażamy następująco

{5.1)

hu(k) = P[u = k} =

ogólna liczba punktów obrazu w rozpatrywanym obszarze

liczba punktów obrazu o wartości jaskrawości k

;$< *t^^5S#^^SJ^«>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).

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

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))<l} (5.12)

N8(i,j) = {(h,k); d8((i,j),(h,k))<l} (5.13)

j-1 j j+1 j-1 j j+1

? M ? ? ?

? i*1 ? ? ?

4- elementowe sąsiedztwo 8- elementowe sąsiedztwo

Rysunek 5.3: 4-elementowe i 8-elementowe sąsiedztwo elementu

Dla wszystkich punktów P,Q G R sekwencja punktów P = Po, Pi,..., Pp, Pr,..., Pt = Q (PP = (ip,jp)) jest nazywana 4-ścieżką (8-ścieżką) jeżeli Pp G NĄ(PP_I) (Pp G Ns(Pp-i)) , przy czym 1 < p < t, gdzie t jest długością ścieżki. Ścieżka jest nazywana łukiem, jeżeli wszystkie punkty P są różne, a Pp i Pr są punktami sąsiednimi, tj. \p — r\ = 1.

Jeżeli (i,j) i (h, k) są współrzędnymi punktów podzbioru 5" obrazu (tj. punkty te posiadają jednakową wartość jaskrawości), to (i,j)

100

Rozdział 5. Analiza obra/n

będzie połączone z (h, k) (4-połączone lub 8-połączone w S) jeżeli istnieje ścieżka od (i,j) do (h, k) mająca początkowy punkt w S. 1 )|| pewnego punktu (i, j) ? S zbiór punktów S, które są 4-połączoin z (i,j), nazywamy 4-składnikiem w S. 8-składnik definiowany jefl analogicznie. 4-składnik lub 8-składnik punktów obrazu o wartości 0(1) nazywamy 0-składnikiem (l-składnikiem).

Przez określenie „punkty obrazu połączone" rozumiemy relacja

(i, j) jest połączone z (i, j) - ścieżka długości zero,

(i,j) jest połączone z (h,k), wtedy (h,k) jest połączone z (i, j),

(i,j) jest połączone z (h, k), a (h, k) z (l,p), wtedy (i,j) jest połączone z (/,p) - konkatenacja dwóch ścieżek jest ścieżką.

Niech S — R — S będzie dopełnieniem zbioru 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 obszaru, należą do pewnego składnika w S. Składnik ten nazywamy tłem S. Wszystkie inne składniki S (jeżeli istnieją) są nazywane dziurami w S. Granica podzbioru S jest zbiorem punktów 5, które mają punkty sąsiednie w S. Mamy więc

35 takiego, że S n S = 0; i N4(i,j)US^0

(5.14)

Zbiór punktów granicznych obszaru S oznaczamy przez G(S). Otoczenie pewnego podzbioru obrazu (pewnego obszaru obrazu) i wnętrze podzbioru obrazu definiowane są następująco:

Niech S i D będą rozłącznymi podzbiorami obrazu. D będzie otoczeniem S lub S będzie wnętrzem D, jeżeli ścieżka od punktu podzbioru 5 do granicy obrazu (R) musi „przeciąć" D. Tło zbioru 5 oczywiście otacza S. Inne składniki C zbioru S są dziurami w S i są otoczone przez S (jeżeli nie, to musi istnieć ścieżka w S od C do granicy obrazu taka, że C będzie identyczne z tłem). Termin „otoczenie" określa pewną relację taką, że:

- jeżeli S otacza T, wtedy T nie otacza S,

- jeżeli S otacza T i T otacza W, wtedy S otacza W.

Właściwości topologiczne obrazów

101

Inaczej mówiąc, dla podzbiorów U,V,W i Z mówimy, że V ida U od W, jeżeli ścieżka od U do W musi przeciąć V; czyli że teza T, jeżeli oddziela T od granicy G zbioru R.

Grafem połączeń nazywamy graf, w którym wierzchołkami są

IIM.IV Si obrazu oraz istnieją krawędzie pomiędzy Si a Sj, o ile tylko

i • i. 11 y Si i Sj są zbiorami przyległymi (tj. istnieje ścieżka od Ą do

i łraf ten jest drzewem. Punkt (i,j) zbioru S jest punktem izolo-

iii, jeżeli nie posiada punktów sąsiednich w S. Liczba połączeń

l.i.u /o jest określona jako

Wo) = ? (/* - fkh+ifw) (5-15)

fce/i

Wo) = ? (7* - 7 J*+i7»«) (5-i6)

fcC/l

dzie oznaczenia 4 i 8 określają 4-elementowe i 8-elementowe oto-? tonie punktu obrazu (Rysunek 5.4), /fe oznacza zmienną binarną l'i/.vjmującą wartość 1 lub 0, h oznacza zbiór liczb całkowitych ( 1, 3, 5, 7}. Kiedy wskaźnik 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}.

Uuuuuf,uf.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

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 /00punkt wewnętrzny (W) lub izolowany (I)1punkt końcowy (K)2punkt połączenia (P)3punkt rozgałęzienia (R)4punkt 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ść NcWartość KKlasyfikacja punktu /o00szyb o

1szczyt •1>Tlkrawędź +

<T2wąwóz x

pozostałestok —>2przełę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 (5.22)

f i = l-fi lei

Elementy obrazu półtonowego klasyfikujemy zgodnie z Tablicą 5.2 (Rysunek 5.7).

5.3 Reprezentacja linii konturowych i granic obiektów

Obiekty znajdujące się w obrazie są całkowicie określone przez swoje kontury. Oznacza to, że kontur obiektu zawiera istotną informację pozwalającą na opis obiektu, a także na obliczenie szeregu parametrów (cech) umożliwiających rozpoznanie obiektu. Właściwości reprezentacji konturów (granic) obiektów są ważne z punktu widzenia analizy i syntezy kształtów obiektów występujących w obrazie. Analiza kształtów obiektów jest niezbędna w procesie detekcji i rozpoznawania obiektów obrazu.

5.3.1 Lokalne elementy krzywej

Krzywą płaską można przedstawić analitycznie

- w postaci wyraźnej y — f(x) lub uwikłanej f(x, y) — 0,

- w postaci parametrycznej x ~ x{t), y = y(t).

Postać wyraźna krzywej praktycznie nie jest wykorzystywana w systemach komputerowej wizji, ponieważ krzywa na płaszczyźnie

Reprezentacja linii konturowych i granic obiektów 105

"cfen rffrl rJ

? Punkt wewnętrzny

? Punkt końcowy

0 Punkt połączenia

u Punkt rozgałęzienia

s Punkt skrzyżowania

Rysunek 5.6: Fragment obrazu oryginalnego i klasyfikacja elementów obrazu na

podstawie wartości N%

i—y może mieć więcej niż jeden punkt odpowiadający danemu x. Parametr t występujący w parametrycznej postaci opisu krzywej pkreśla bieżący punkt krzywej.

Załóżmy, że krzywa płaska przedstawiona jest w postaci parametrycznej [x(t),y(t)\ a < t < b. Dla pewnego t, długość łuku s(t) od \s(a),y(a)] do [x(t),y(t)} jest określona przez

'dx(u) du

'dy(u) du

(5.23)

Styczna do krzywej w danym punkcie jest prostą, będącą granicznym położeniem siecznej, przechodzącej przez dany punkt krzywej i

106

Rozdział 5. Analiza obrazu

8511123358 .+OooQ+0-

8322112579 +-- + 00

7432113799 -++-00+++-

853312589,4 +-- + 0+ + +--

9 7 5 4 3 2 5 8 8,4 + + + + +_ + _.<>

+ + + - + -- + 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.i3

/ /

/2* » 04. : '- ? 0'r/ \

5 1 7364 - kierunkowy kod łańcuchowy8 - kierunkowy kod łańcuchowya)iVRysunek 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

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

• • •

? ? •

• • •

p • • *

i u- r

* •

? •

71 \~

1 0.1

"\7

211

2^2

0303333232312121011011

3\/S

076666553321212

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

>-* ::?;"; ik?'Tj *:

-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

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, =

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

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

TransformacjaKonturWspółczynniki FourieraTranslacjau(n) = u(n) + UQa(k) = a(k) + u05(k)Skalowanieu(n) = au(n)a(k) = aa(k)Obrótu{n) = u(n)ema(k) = a{k)e1^()db. zwierciadlaneu(n) = u*(n)eiW + 2a(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

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<t<tl+1

' I 0 w przypadku pozostałym y

Bi,m(t) = t *1 g«,m-i(*)+, *i+1 _/ gi+i,m-i(t) m = 2,3(5.47)

n+m—1 H H+m W+l

5. ]TĄ,m(i) = l (5.48)

Parametry ^ z = 0,1,... są nazywane punktami załamania, natomiast punkty krzywej dla tych wartości nazywane są węzłami. Na Rysunku 5.18 przedstawiono pewne znormalizowane B-sklejane funkcje dla 0 < B^m{t) < 1 i przedziału [^,^+m).

Punkty p, są współczynnikami równania (5.45) i definiują wierzchołki wieloboku przez które przechodzi funkcja aproksymująca (Rysunek 5.19). Liczba punktów kontrolnych konieczna do odtworzenia danej krzywej jest zwykle dużo mniejsza niż liczba punktów oryginalnej krzywej.

Funkcja B-sklejana aproksymująca krzywą może być poddana transformacjom geometrycznym

5,3. Reprezentacja linii konturowych i granic obiektów

117

Translacji:

Pi = Pi + xo, xo = [x0,yo?

(5.49)

Skalowaniu:

p, = api, a — jest skalarem,

(5.50)

Obrotowi:

Pi = Rpi

gdzie

R =

cos $o — sin 90 sin $o cos 00

(5.51)

Na podstawie punktów kontrolnych można obliczać wiele parametrów opisujących kształty obiektów np. środek ciężkości, powierzchnię, obwód.

1i«

-; i i i_

Vi *M *i*3

-»;

B (ł)

i. 3

*i Vi WVi

rf;

Rysunek 5.18: Funkcje B-sklejane: a) i?j,i(?) rzędu 1 (stalą), b)Sii2(?) rz?du 2 (liniowa), c) Bi^{t) rzędu 3 (kwadratowa), d) Bi^(t) rzędu 4 (sześcienna)

5.3.5 Transformacja Hough'a

Kontury obiektów składają się z odcinków linii prostych i fragmentów okręgów lub elips. Można je opisywać zarówno w przestrzeni współrzędnych obrazu jak i w przestrzeni parametrów. Odwzorowanie do

118

Rozdział 5. Analiza obrazu

Punkty kontrolne

Rysunek 5.19: Funkcje B-sklejane przechodzące przez oryginalne punkty konturowe: a) krzywa odtworzona na podstawie b), b) punkty kontrolne

przestrzeni parametrów realizowane jest za pomocą transformacji Hough'a, która wykorzystywana jest do detekcji linii konturowych (prostych i krzywych) w obrazie.

Linia prosta opisywana jest przez równanie

y = mx + b (5.52)

gdzie (x, y) określają przestrzeń współrzędnych obrazu, natomiast (ra, b) przestrzeń parametrów.

Jeżeli mamy punkt (x , y) w obrazie to wszystkie linie, które przechodzą przez ten punkt mają równanie (Rysunek 5.20a)

y = mx + b (5.53)

dla zadanych wartości m i b. Równanie to można zapisać w postaci

b — —x m + y (5.54)

gdzie x i y są rozważane jako stałe, natomiast m i b jako zmienne (Rysunek 5.20b). Każda linia przechodząca przez punkt (x , y) odpowiada pojedynczemu punktowi na linii w przestrzeni (m,b).

ł Reprezentacja linii konturowych i granic obiektów 119

Rysunek 5.20: Reprezentacja linii prostej

Rozważmy dwa punkty o współrzędnych odpowiednio (x ,y) i (./• , y ) w przestrzeni (x, y) leżące na tej samej prostej. Mamy (Rysu-nek 5.21)

b = —mx + y (5.55)

b = —mx + y (5.56)

co oznacza, że

- wszystkie punkty, które leżą na pewnej linii w przestrzeni (x, y) są

reprezentowane przez linie przechodzące przez pojedynczy punkt w przestrzeni (m, 6),

- pojedynczy punkt przez który przechodzą wszystkie linie wyznacza

wartości m i b w równaniu prostej y = mx + b.

W przedstawionych rozważaniach, zarówno m jak i b, mogą przyjmować wartości oc, dlatego stosuje się inną formę parametryzacji krzywych.

Prosta przedstawiona w kartezjańskim układzie współrzędnych może być analitycznie opisana za pomocą równania normalnego prostej

x cos 9 + y sin 9 = p (5.57)

gdzie 9 oznacza kąt utworzony przez dodatni kierunek osi Ox z półprostą poprowadzoną z początku współrzędnych prostopadle do danej prostej, przy czym 0 < 9 < 27T , a p jest odległością danej

120

Rozdział 5. Analiza obrazu

b= -tnx"+y"

(x'.y)

(x".y").

vt:

Rysunek 5.21: Reprezentacja dwóch punktów leżących na tej samej linii

prostej od początku układu współrzędnych (Rysunek 5.22). Każdy punkt (x,y) jest teraz reprezentowany przez krzywą w przestrzeni (p,9) (Rysunek 5.22).

/ V"/'??? \/\

\/\/ /\,v_/n. Ol-2 9 o

P = -3aw(t) |ł-5«o(«! P = 4cos(*)+4sn{S)

Rozwiązanie dla p i 8

r =4 5255

Rysunek 5.22: Prosta przechodząca przez punkty Pi i Po w kartezjańskim układzie współrzędnych i w przestrzeni parametrów (przestrzeni Hough'a)

Załóżmy, że mamy dane punkty linii konturowej obiektu (xi, Di) i = 1,..., N. Kwantujemy przestrzeń parametrów (p, 6) tworząc tzw. tablicę akumulatora Ak (Rysunek 5.23). Początkowo wszystkie wartości elementów tablicy Ak są równe zero. Następnie każdy

') 3 Reprezentacja linii konturowych i granic obiektów

121

punkt (xi,yi) transformujemy do przestrzeni parametrów, przy czym [p, 9) przyjmują wartości skwantowane. Zliczana jest liczba punktów ,\k(p,9), która odpowiada położeniu (p,9) tak, że

Ak(pk,9i) = Ak(pk,6i) + l jeżeli

Xi cos 0 + tfi sin 6 — pk dla 8 = 9k

(5.58)

(5.59)

Pmm

"imis

*- $

Pmsx

Rysunek 5.23: Przestrzeń parametrów transformacji Hough'a

Lokalne maksima Ak(p, 6) określają różne odcinki linii prostych tworzących linie konturowe obiektów.

Na Rysunkach 5.24 - 5.25 przedstawiono efekty działania transformacji Hougha dla różnych obrazów testowych.

Transformacja Hough'a może być wykorzystana do detekcji dowolnych krzywych (np. okręgów, elips), przy czym w takim przypadku zwiększają się zarówno wymiar przestrzeni parametrów, jak i złożoność obliczeniowa. W przypadku detekcji okręgów

(x - xQ)2 + (y - y0f = r2

mamy 3D przestrzeń parametrów z trzema parametrami: (XQ, gfo), r.

W przypadku ogólnym dowolna krzywa może być zapisana w postaci

122

Rozdział 5. Analiza obrazu

W tym miejscu znajduje sie pojedynczy punkt obrazu

Rysunek 5.24: Transformacja Hougha. Obraz wejściowy (pojedynczy piksel obrazu) - (a), kontur (b), przestrzeń parametrów (c), obraz odtworzony (d).

g(w,P) (w — wektor współrzędnych, P — parametry). Z Rysunku 5.27 wynika, że

y' = rcos(7r — a) = — r sin (a) ; x' = rsin(7r — a) = — r cos(a:)(5.60)

czyli

xc = x + rcos(a) ; yc = y + r sin (a) (5.61)

Punkt (xc, yc) jest funkcją ó, tak że możemy utworzyć tzw. R -tablicę (dla każego obiektu w obrazie)

W,*}), (r.>*),

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 <C S $*. Smax

obliczamy

xc = x — (rcos(a) cos(#) — r sin(o;)'sin(^))s,

yc = y — (r cos(a) sin(0) + r sin (a) cos(0))s.

Znajdując lokalne maksima w P[xc][j/C], możemy określić położenie konturu obiektu - jeżeli JP[?C][2/C][#][SJ > 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

C =

Ylw fi

12W fifj

Siy fifj Ylw fj

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

. fi/j Jj .

(5.65)

a / oznacza obraz / po filtracji filtrem gaussowskim czyli f = e -&-®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.

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,100001100111(4,2) (8,3)0,3,2,2,30011100110(3,3) (8,2)0,2,3,2,2,10010110111(3,1) (5,2) (7,3)0,2,1,1,2,1,31011100010(1,1) (3,3) (9,1)1,1,3,3,1,11101100000(1,2) (4,2)2,1,2,50110000000(2,2)0,1,2,701 00000000(2,1)0,1,1,81 100000000(1,2)2,80000000000(0,0)0,10a) 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™ 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

1 2 3 A

<3)©<S>®

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

j. Tekstury i parametry opisu tekstur

133

1234

12 3 4

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

k=0

k=1

k=2

Rysunek 5.34: Tworzenie piramidy obrazów

przestrzennej funkcji autokorelacji

Air ? -\ - ^™=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<axctg{*}<0a , .

1 < u < M, 1 < u < N l ;

Skoncentrujemy się na parametrach opisujących tekstury wykorzystujących statystyczny rozkład jaskrawości elementów obrazu. Określimy bezwzględną różnicę poziomów jaskrawości dla dwóch elementów obrazu lub bezwzględną różnicę uśrednionych wartości jaskrawości dla dwóch grup elementów obrazu. Rozpatrujemy dwa elementy obrazu o współrzędnych (x, y) i (x + Ax, y + Ay) (Rysunek 5.35). Różnica poziomów jaskrawości wynosi

fs(x,y) = \f(x,y) - f(x + Ax,y + Ay)\ (5.81)

gdzie S = y/Ax2 + Ay2 jest odległością pomiędzy rozpatrywanymi elementami obrazu.

Będziemy obliczać gęstość prawdopodobieństwa zdarzenia polegającego na tym, że para elementów obrazu odległa o 5 i usytuowana względem siebie pod kątem 9 posiada jaskrawości odpowiednio (ki,k2)- Obliczone gęstości prawdopodobieństw tworzą macierz Ps,d{ki,k2) (Rysunek 5.36)[102]. Wykorzystując macierz P5,e{ki,k2) można obliczyć następujące parametry opisujące tekstury [51],[52]:

1. kontrast

^i = E E (** - hfPsAki, h) (5.82)

fc1=ifc2=i

136

Rozdział 5. Analiza obrazu

Ay=5sine

oooooo

oooo

AX=5COS0

Rysunek 5.35: Elementy obrazu tekstury.

'Jw

>•

?' 11 > ?' / J' / ii K:ittir~

\0.n

f(x+Ax,y+Ay)

602.<505\04211244n 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

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 KluczeObraz KluczeParametre6=15= 10Kontrast Mi01687918.31897354131.5658088891147614E7

90631694.53101348881.997868569965744E7

1801187326.4093742371.6654923693756104E7

2702837879.9469108583.0519982911361694E7Moment

fJ-2010250.043674943621388408.0167295139

9015380.0347076425391227618.0196717763

18039330.043675366793558200.016760735

27022626.0347077479822064212.0196839531Korelacja

M30-1341875.5303634775-1.181355807458559E8

90-1076049.7421851608-1.2628679015749444E8

180-659085.3497722034-7.20737308227905E7

270-877567.3507217962-9.565040046810706E7Entropia (i40-1159.6366876635943-23499.426078829212

90-1417.5753383130366-23601.10643640572

180-1801.6054243677502-28529.09537104104

270-1508.9410457471784-25961.340868643558Moment różnicowy

^602.50615352461972616.766814363691054

902.769298352024493617.510092993713638

1802.289392348887616412.834270046549358

2702.554548999069562215.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 metaloweParametreS=l5 = 10Kontrast fil08537979.790752417.342371701238632E7

906959236.3979644787.216099258395004E7

1807669397.4773864757.488239657678604E7

2707253170.5192298896.5469008056152344E7Moment

/"202438.000687827356218804.0002363859

902694.000905335677200476.00026824477

1802488.0006878280838201798.00023614196

2702430.0009053318354217144.00026848057Korelacja

#50-3188904.3493224056-3.917675330286808E8

90-2933253.18384677-4.2663539037669903E8

180-3134217.606864619-4.238191878949137E8

270-3195615.7541388553-3.9455927329559535E8Entropia0-680.9025735642138-18094.15549001349

90-723.0171448672497-17723.274771629625

180-696.7102790046869-17783.53946849112

270-675.4424660570187-18077.305592722176Moment różnicowy

^600.233596072758833650.6830140240544869

900.33577695580037520.8444481491412067

1800.24154476643856650.718393997624081

2700.3275233828602790.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)

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

<?w = / / /+?exp(7(p - <?)#)/(/>, 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 —r2x2 — c2

°11#3 =r2#4 = ^#5 =c2

°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 <p

Innymi momentami są tzw. momenty kosinusowe i sinusowe określone odpowiednio przez

Zp?*f(p,<p)EP L<t> 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<<?<p.

146

Rozdział 5. Analiza obrazu

Zależności pomiędzy momentami S'PQ i C'PQ a momentami central

nymi są następujące

Coo = //00 SQO = 0 Cu = fiio Sn = i^i C20 = H20 + /J-02 S20 = 0 C22 = ^20 - ^02 ^22 = 2JIU

^31 = /i30 + fl12 S31 = ^03 + f,12

<-33 - ^30 ~ 3^12 533 = 3/Z21 - ^

(5.143)

Na Rysunku 5.38 przedstawiono obraz oryginalny oraz obrazy uzyskane w wyniku pewnych przekształceń afinicznych obrazu oryginalnego, natomiast w Tablicy 5.6 wartości momentów Hu obliczonych dla wszystkich obrazów. Różnice pomiędzy wartościami odpowiednich momentów dla zastosowanych przekształceń wynikają z cyfrowego charakteru obrazu.

Rysunek 5.38: Obraz oryginalny (a), obrazy uzyskane po obrocie obrazu oryginalnego o kąt 90° (b) i 32, 727° (c); obraz oryginalny po zmianie skali (d)

V8. Morfologiczne operacje przetwarzania obrazów 147

Tablica 5.6: Wartości momentów Hu dla obrazów z Rysunku 5.38

Momenty HuRysunki

5.38a5.38b5.38c5.38d0i6.8E - 0046.8E - 0046.8E - 0046.8E - 004</>21.8?-0091AE - 0091.8E - 0091.8^-009<h2.3E - 0152.2E - 0152.0E - 0153.5E - 016043.6E - 0153.8? - 0152.9E - 0152.1?" - 0154>h-6.0^-030-7.1?-030~5.8?-030-l^-OSO065.5E - 0204.8E - 020-9.5?-0202.2E - 020078.2E - 0308.6E - 0303.9E - 0301.4E - 0305.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 ©, "różnicy Minkowskiego" symbol 0, zdefiniował operację przesunięcia zbioru A jak At — A © {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®B = {a + b:a€A,beB} (5.150)

•

5.8. Morfologiczne operacje przetwarzania obrazów

149

O=(0,0)

Rysunek 5.39: Unarne morfologiczne operacje przetwarzania obrazów: a) translacja, b) dopełnienie i c) odbicie zwierciadlane

A®B= U Ab

b€B

(5.151)

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®B=[AC QB]C (5.156)

AQB = [AC ®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, 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

0ccc11

E *11 109 > i11 1otl łl t•0

05i ii 1s

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 00 0e0 0 00e0s0 0 0; o o o o o0 00I' 00 S00 00 0 00 0 00 0 0 0 0 0 0 0 0 0 000 00 00000

S i t 1

0 0 0 0 0 0 0 OJosoDDE

Ts i i0000006 Otu Eln c c o o o o o o c1 1 Ili 1: n r.Hli tHL*f-! 1 !111BBŁ'1 ii >t

« iI

1 1 11'

D 0 "BI] 0 0 0 0'i j iili

1 1 !1<

0 0 0 0 0 0o c-ET11110 0 0

0 0 0''0 0 0 0 0 0? 11 11 1U'0

?jI0 00 0 0 0 0 0M' '1t0osoo

ST1OC 00 0 0o ulitu0 0 0 0 0i ' '1?0 0 0Bill0 00 0 0 0 0 0 0 0 0 0 0 0! ' '0 0 010 0 0cl1t tTt•!1

i ' s1o o oj0 0 0'iiI1 l| t11-

i i :10 0 010 0 00 0 0 Cnnnnnn0 0 0 0 01 ' s1o o oj0 0 0

0 0 0 0 0 00'•0 0 0

10i°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®(B{JC) = {A®B)U(A®C) = {BUC)®A (5.165)

Ae(Buc) = (AeB)n{Aec) (5.166)

5.8. Morfologiczne operacje przetwarzania obrazów

153

Bij_

Hf i t 1 ? ;' 1 i»|EP-;JJ|I:":-WJBHI

ii' i t Ff

1 : 'IB

Liiii i

.'UĄliSjElf

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

• * El0 0 0 0 0 0 O O O ') O UBB D0 0 0 0 0 • 9 ?10 0 0

0 0 0 00 0 0 0 0 0 0 088u >0 0 0 0

o o B o1 » ? ?0 <ł fi 0onIHIBOBo o UBUIUUuuUUBflo o' BDUUUUuuUUBo aaDBBODDBnua a a o ? an o o oni0 00 0 o 0OH 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

Rysunek 5.43: Operacja opening a) i closing b)

(A Q B) e c = A e (B e c)

nB={B®B®B...®B)

(5.167) (5.168)

Operacje opening i closing definiujemy następująco (Rysunek 5.43):

i) operacja opening

ii) operacja closing

c(A, B) = [A® (-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]

5.8. Morfologiczne operacje przetwarzania obrazów

155

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)

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)

<jA = A-s(A,Ni) (5.185)

gdzie NĄ i N8 oznaczają odpowiednio 4- i 8-elementowe sąsiedztwo rozpatrywanego elementu obrazu.

Szkielet (zarys) obiektu powinien posiadać następujące właściwości:

- szerokość 1 elementu,

- przechodzić przez ,,środek" obiektu, i,

- zachowywać topologię obiektu.

Ą» -

1 -

%suneJc 5.46: Op,

eracja hit-and-

B2= 1 _ j,

"*» dla elementów

- 1 -

i i Bo

strukturalnych Ą i

%sunek 5 47- &-„ *

7" Kontu'y obiektów w .

wg- wzoru 5.185

° "wiu 0.185 ^ Jednak oczywiste i* * •

i2te*>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:

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

AeB6f34

i11^566S

i21

216432

i1l

ii6453

A-m

B-g{k.l)

m/n

4-6

56•i

446534Rysunek 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 -

777336665299963566640086821663666767696356664008682166366676769635666400868216636667676wielopoziomowa operacja dilation

9999966696656888868787677777

Rysunek 5.50: Operacja dilation dla obrazu o wielu poziomach jaskrawości

162 Rozdział 5. Analiza obrazu

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 CECHFORMOWANIEWERYFIKACJA

WHIPOTEZHIPOTEZ

BAZA MODELIRysunek 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- *?lssm: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

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 u<i to

Di(X)>Di(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

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

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

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

* P<x|o,)/"

\P(x!o,j

P«-,)/

/T\

P(X',C>2)

10™** "" 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) + 2<r2 In {^J.

Równanie to reprezentuje hiperpłaszczyznę między dwoma punktami Mj i Mj prostopadłą do lini prostej przechodzącej przez te punkty.

Wtedy, kiedy wszystkie klasy maja prawdopodobieństwa P(tjj), mamy

Dt{X) = -|X-M|2 = -{X-Mif{X-Mi) = D2(X, Mi). (6.36)

- Wszystkie klasy mają rozkłady o takich samych macierzach kowariancji 5Zi = 12 (i — 1) • ? • ic) lecz różnych Mj. Wtedy

-i

(X - Mj)4 ?(X - Mj) + In P(oJi)

(6.37)

oraz

*Vj)'

W = Y7\Mi~M3)

" - -^(A^E"1^ - ^?~X) + In '

(6.38) (6.39)

Równanie to reprezentuje hiperpłaszczyznę między dwoma punktami Mj i Mj i prostopadłą do lini prostej ?i(A*» ~ Mj)

6.3. Klasyfikatory statystyczne

177

- Wszystkie klasy mają różne Yli Jest to najbardziej ogólny przypadek i granica między dwoma klasami

Uli i U!j

Di(X) = Dj(X) (6.40)

jest wyznaczona przez równanie kwadratowe

X*WX + W*X + w = 0 (6.41)

gdzie W jest macierzą wymiaru n x n

W^-^E^-E;1) (6-42)

Granice te w n wymiarowej przestrzeni cech są w ogólności hi-perpłaszczyznami takimi jak hiper-sfera, hiper-elipsoida, hiper-parabola i itp..

6.3.1 Klasteryzacja

Zbiór obiektów Xi, i = 1,2,..., N (gdzie każdy X, = [x[ ,..., x$]* jest wektorem kolumnowym reprezentującym punkt w n-wymiarowej przestrzeni cech), grupujemy do zbioru klastrów zgodnie z ich naturalnymi rozkładami w przestrzeni cech.

Klasteryzacja jest klasyfikacją bez uczenia ponieważ nie mamy wiedzy a 'priori jakie obiekty należą do określonej klasy.

Najpopularniejsze algorytmy klasteryzacji to algorytm k-średnich i algorytm Isodata, z których przedstawimy pierwszy z wymienionych.

178

Rozdział 6. Rozpoznawanie obrazów

Granice decyzyjne

Rysunek 6.13: Jedno i dwuwymiarowe obszary decyzyjne.

Algorytm k-średnich

ków klastrów Aff0), M.f,..., Af?0) (np. pierwsze k próbek zbioru

1 Arbitralnie wybieramy ze zbioru obiektów k początkowych śród ków klastrów M[' , D/Ą0 obiektów). Niech l = 0;

2 Przydzielamy każdy obiekt Xi, i = 1,..., N do jednego z klastrów na podstawie odległości między obiektem i środkiem klastra: X ~ u, jeżeli DŁ{X, Mf) = min DL{X, M*>1)), 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 =

(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)

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)

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 <pi odpowiadające największym wartością własnym Aj macierzy kowariancji J2x-

"1 U H

Rysunek 6.15: Zasada redukcji wymiarowości metodą PCA

Przedstawimy zarys metody redukcji cech polagającej na wyznaczeniu składowych głównych wektora cech. Składowe główne są osiami maksymalnej wariancji i mogą byc wyznaczone z macierzy kowariancji (Rys. 6.16).

Rozpatrujemy obrazy cyfrowe f(i,j) ze średnią wartością jaskrawości równą zero oraz znormalizowaną do wartości 1 energią tj.

U N

EE(/(^-))2 = l (6-63)

Niech Xk będzie MN elementowym jednokolumnowym obrazem, przy czym zakładamy, że mamy r takich obrazów k = (1,..., r). Jednowymiarowy obraz-kolumna X tworzony jest z dwuwymiarowego obrazu poprzez konkatenację wierszy obrazu i zapisanie ich jako wektora

184

Rozdział 6. Rozpoznawanie obrazów

/'.;

Krok t: Octanie wartości średniej

wektora cech

Krok 2: Odejmowanie wartości średniej od '

każdego wektora cech

Krok 3: Obliczenie macierzy kowariancji , ,

Krok (Obliczenie wartości własnych i > 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

?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

[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 <fii i wartości własnych A; macierzy kowariancji ? (X) <Pi = ^i4>k)-

Znalezione wektory własne $ = (<fi\, 4>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 1r 196 i" 255 122921935223482423422425125523225533; x2 =18;*3 =59; XĄ —023824724425501724324925525557255. 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

A 00 O H W-i^OiCn JiOłOMO-^tOWh--Ol-'OCOJiQOCOCO--I

CO 00 tO Ol W CO O) W

OiOOWdOOM-JOl -Ji-^OOlOOiJ^Oi^W *--vlŁ0*i|-'OlO1~JCO

ł—'•

I to oo oi oi

rf^ to co

?k ?k tO I

~q co s oo ai

OOiOiOOlOiOiOiOi

to oo oi oi

?f^ tO CO

CO Ol O 4^ tO ** ~

tJ^ Oi

-vj

-4

h-> i—'4^ ~4OlOl00OlOiOlOlOl

OlOlOitOOlOiOiOiOi

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

i-i

I— ?—

Ol O ^ O)

oo to

00 CO

-J

OOiOiOOlOiOiOiOi

Ol O ^ Ol

hf=- O

Ol ^ Ol

oi oo

co oi o 4^ to

-J

OOlOlOOlOlOlOlOl

oo to

oi co

-J

-*1

to Ol CO 4^ 00

-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

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,4890,3470,0440,309-0,0480,0640,10503 =-0,222-0,0040,0780,1120,5850,4920,401-0,432L -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,2947,45' 139,24 '-106,8895,26

(6.74)

6.4. Selekcja cech 189

Przedstawiamy obraz testowy

r 201-L51.5 1244

246 67,5 -88,5 -2,25n = 21 244Y,=-6,5 -24-123,25255 2 . 49,5 -168 .•ojekcja obrazu testowegoYi = <&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)

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?*)

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

(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

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-

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

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

Wyszukiwarka