Niech będzie nieskierowanym grafem. Wyobraźmy sobie, że elementy
reprezentują ,,miejsca”
w przestrzeni lub na płaszczyźnie, zaś krawędzie grafu łączą miejsca ,,sąsiadujące” ze sobą. Taka
interpretacja jest związana z zastosowaniami do statystyki ,,przestrzennej” i przetwarzania obrazów.
Model, który przedstawimy ma również zupełnie inne interpretacje, ale pozostaniemy przy sugestywnej terminologii
,,przestrzennej”:
— zbiór miejsc,
— miejsca
i
sąsiadują — będziemy wtedy pisać
,
— zbiór sąsiadów miejsca
.
Niech będzie skończonym zbiorem. Powiedzmy, że elementy
są ,,kolorami”
które mogą być przypisane elementom zbioru
. Konfiguracją nazywamy dowolną funkcję
.
Będziemy mówić że
jest
-tą współrzędną konfiguracji
i stosować oznaczenia podobne jak dla wektorów:
![]() |
(13.1) |
W zadaniach przetwarzania obrazów, miejsca są pikslami na ekranie i konfigurację utożsamiamy z ich pokolorowaniem,
a więc z cyfrową reprezentacją obrazu. Zbiór gra rolę ,,palety kolorów”. Niekiedy założenie o skończoności
zbioru
staje się niewygodne. Dla czarno-szaro-białych obrazów ,,pomalowanych” różnymi odcieniami szarości,
wygodnie przyjąć, że
lub
. Tego typu modyfikacje są dość oczywiste i
nie będę się nad tym zatrzymywał. Dla ustalenia uwagi, wzory w tym podrozdziale dotyczą przypadku skończonego zbioru
,,kolorów”. Przestrzenią konfiguracji jest zbiór
. Dla konfiguracji
i miejsca
, niech
— konfiguracja z pominiętą
-tą współrzędną,
— konfiguracja ograniczona do sąsiadów miejsca
.
Jeśli i
to rozkładem Gibbsa nazywamy rozkład prawdopodobieństwa na przestrzeni konfiguracji dany
wzorem
![]() |
Ze względu na inspiracje pochodzące z fizyki statystycznej, funkcję nazywamy energią,
jest (z dokładnością do stałej)
odwrotnością temperatury. Stała normująca wyraża się wzorem
![]() |
(13.2) |
i jest typowo niemożliwa do obliczenia.
Oczywiście, każdy rozkład prawdopodobieństwa na
dale się zapisać jako rozkład Gibbsa, jeśli położyć
,
i
umownie przyjąć, że
(czyli konfiguracje niemożliwe mają nieskończoną energię). Nie o to jednak chodzi. Ciekawe są rozkłady
Gibbsa, dla których fukcja energii ma specjalną postać związaną z topologią grafu ,,sąsiedztw”. Ograniczymy się do ważnej podklasy
markowowskich pól losowych (MPL), mianowicie do sytuacji gdy energia jest sumą ,,oddziaływań” lub ,,interakcji” między parami
miejsc sąsiadujących i składników zależnych od pojedynczych miejsc. Dokładniej, założymy że
![]() |
(13.3) |
dla pewnych funkcji i
. Funkcja
opisuje ,,potencjał interakcji
pomiędzy
i
”, zaś
jest wielkością związaną z ,,tendencją miejsca
do przybrania koloru
.
Zwróćmy uwagę, że potencjał
jest jednorodny (
zależy tylko od ,,kolorów”
ale nie od miejsc),
zaś
może zależeć zarówno od
jak i od
. W modelach fizyki statystycznej zazwyczaj
jest jednorodnym ,,oddziaływaniem zewnętrznym” ale w modelach rekonstrukcji obrazów nie można tego zakładać.
Niech będzie zbiorem skończonym i
![]() |
Ta funkcja opisuje ,,tendencję sąsiednich miejsc do przybierania tego samego koloru”. Jeśli to preferowane są konfiguracje
złożone z dużych, jednobarwnych plam.
Użyteczność MPL w różnorodnych zastosowaniach związana jest z istnieniem efektywnych algorytmów symulacyjnych. Wszystko opiera się na próbniku Gibbsa i następującym prostym fakcie.
Jeżeli jest rozkładem Gibbsa z energią daną wzorem (13.3), to
![]() |
(13.4) |
gdzie
![]() |
(13.5) |
. Symbol
oznacza konfigurację
powstałą z
przez wpisanie koloru
w miejscu
.
Skorzystamy z elementarnej definicji prawdopodobieństwa warunkowego (poniżej piszemy ,
bo parametr
jest ustalony):
![]() |
(13.6) |
Ponieważ otrzymany wynik zależy tylko od i
, więc
.
Ten wniosek jest pewną formą własności Markowa.
Zauważmy, że obliczenie jest łatwe, bo suma
zawiera tylko tyle składników,
ile jest sąsiadów miejsca
. Obliczenie
też jest łatwe, bo suma
zawiera tylko
składników. Ale nawet nie musimy obliczać stałej normującej
żeby generować z rozkładu
![]() |
(13.7) |
Na tym opiera się implementacja próbnika Gibbsa. Wersję PG z ,,systemstycznym przeglądem miejsc” można zapisać tak:
for ![]() |
begin |
Gen ![]() |
![]() |
end |
Bayesowski model rekonstrukcji obrazów został zaproponowany w pracy Gemana i Gemana w 1987 roku. Potem zdobył dużą
popularność i odniósł wiele sukcesów. Model łączy idee zaczerpnięte ze statystyki bayesowskiej i fizyki
statystycznej. Cyfrową reprezentację obrazu utożsamiamy z konfiguracją kolorów na wierzchołkach
grafu, czyli z elementem przestrzeni , zdefiniowanej w Podrozdziale 13.1.
Przyjmijmy, że ,,idealny obraz”, czyli to co chcielibyśmy zrekonstruować jest konfiguracją
.
Niestety, obraz jest ,,zakłócony” lub ,,zaszumiony”. Możemy tylko obserwować konfigurację
reprezentującą
zakłócony obraz. Zbiór kolorów w obrazie
nie musi być identyczny jak w obrazie
. Powiedzmy, że
. Ważne jest to, że zniekształcenie modelujemy probabilistycznie przy pomocy rodziny rozkładów
warunkowych
.
Dodatkowo zakładamy, że obraz
pojawia się losowo, zgodnie z rozkładem prawdopodobieństwa
. Innymi słowy,
,,idealny” obraz
oraz ,,zniekształcony” obraz
traktujemy jako realizacje zmiennych losowych
i
,
![]() |
(13.8) |
W ten sposób buduje się statystyczny model bayesowski, w którym
jest obserwowaną zmienną losową,
jest nieznanym parametrem traktowanym jako zmienna losowa
.
Oczywiście, gra rolę rozkładu a priori, zaś
jest wiarogodnością.
Być może użycie literki
na oznaczenie parametru jest niezgodne z tradycyjnymi oznaczeniami statystycznymi, ale
z drugiej strony jest wygodne. Wzór Bayesa mówi, że rozkład a posteriori jest następujący.
![]() |
(13.9) |
Pomysł Gemana i Gemana polegał na tym, żeby modelować rozkład a priori jako MPL. Załóżmy,
że
jest rozkładem Gibbsa,
![]() |
(13.10) |
gdzie
![]() |
(13.11) |
Energia ,,a priori” zawiera tu tylko składniki reprezentujące oddziaływania między parami miejsc sąsiednich.
Funkcja zazwyczaj ma najmniejszą wartość dla
i rośnie wraz z ,,odległością” między
i
(jakkolwiek tę odległość zdefiniujemy). W ten sposób ,,nagradza” konfiguracje w których sąsiedznie miejsca są podobnie
pokolorowane. Im większy parametr
, tym bardziej prawdopodobne są obrazy zawierające jednolite plamy kolorów.
Trzeba jeszcze założyć coś o ,,wiarogodności” . Dla uproszczenia opiszę tylko najprostszy model, w którym
kolor
na obserwowanym obrazie zależy tylko od koloru
na obrazie idealnym. Intuicyjnie znaczy to, że
,,zaszumienie” ma ściśle lokalny charakter. Matematycznie znaczy to, że
![]() |
(13.12) |
(pozwolę sobie na odrobinę nieścisłości aby uniknąć nowego symbolu na oznaczenie ).
Zapiszemy teraz ,,wiarogodność”
w postaci zlogarytmowanej. Jeśli położymy
pamiętając, że
jest w świecie bayesowskim ustalone, to otrzymujemy następujący wzór:
![]() |
(13.13) |
gdzie
![]() |
(13.14) |
Okazuje się zatem, że rozkład a posteriori ma podobną postać do rozkładu a priori. Też jest
rozkładem Gibbsa, a różnica polega tylko na dodaniu składników reprezentujących oddziaływania zewnętrzne
. Pamiętajmy przy tym, że
jest w świecie bayesowskim ustalone.
W modelu rekonstrukcji obrazów ,,oddziaływania zewnętrzne” zależą od
i ,,wymuszają podobieństwo”
rekonstruowanego obrazu do obserwacji. Z kolei ,,oddziaływania między parami” są odpowiedzialne za
wygładzenie obrazu. Lepiej to wyjaśnimy na przykładzie.
Załóżmy, że jest naprawdę paletą kolorów, na przykład
.
Przypuśćmy, że mechanizm losowego ,,przekłamania” polega na tym, że w każdym pikslu, kolor obecny w idealnym obrazie
jest z prawdopodobieństwem
niezmieniony, a z prawdopodobieństwem
zmienia się na losowo wybrany inny kolor.
Tak więc zarówno
jak i
należą do tej samej przestrzeni
,
![]() |
(13.15) |
Można za rozkład a priori przyjąć rozkład Pottsa z Przykładu 13.1. Rozkład a posteriori ma funkcję
energii daną następującym wzorem (z ):
![]() |
(13.16) |
Pierwszy składnik w tym wzorze pochodzi od rozkładu a priori (z modelu Pottsa) i ,,nagradza” konfiguracje w których dużo
sąsiednich punktów jest pomalowanych na ten sam kolor. Powoduje to, że obrazy składające się z jednolotych dużych ,,plam”
są preferowane. Drugi składnik pochodzi od obserwowanegj konfiguracji
i jest najmniejszy dla
. Powoduje to, ze
obrazy
mało się różniące od
są bardziej prawdopodobne. Rozkład a posteriori jest pewnym kompromisem
pomiędzy tymi dwoma konkurującymi składnikami. Parametr
jest ,,wagą” pierwszego składnika i dlatego odgrywa rolę ,,parametru
wygładzającego”. Im większe
tym odtwarzany obraz będzie bardziej regularny (a tym mnie będzie starał się upodobnić do
).
I odwrotnie, małe
powoduje ściślejsze dopasowanie
do
ale mniejszą ,,regularność”
.
Jeszcze lepiej to samo widać na przykładzie tak zwanego ,,szumu gaussowskiego”.
Załóżmy, że jest konfiguracją ,,poziomów szarości” czyli, powiedzmy,
. Mechanizm
losowego ,,zaszumienia” polega na tym, że zamiast poziomu szarości
obserwujemy
.
Innymi słowy,
![]() |
(13.17) |
Przestrzenią obserwaowanych konfiguracji jest tutaj (formalnie)
(faktycznie, raczej
).
Rozkład a posteriori ma funkcję
energii daną następującym wzorem:
![]() |
(13.18) |
Jeśli rozpatrujemy model ze skończoną liczbą poziomów szarości dla konfiguracji to można pierwszy składnik określić tak
jak w poprzednim przykładzie, czyli zapożyczyć z modelu Pottsa. Bardziej naturalne jest określenie
w taki sposób, aby większe różnice pomiędzy poziomami
i
były silniej karane. parametr
jest,
jak poprzednio, odpowiedzialny zaa stopień wygładzenia.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.