Niech S,E będzie nieskierowanym grafem. Wyobraźmy sobie, że elementy s∈S 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”:

• S — zbiór miejsc,

• s,t∈E — miejsca s i t sąsiadują — będziemy wtedy pisać s∼t,

• ∂⁡t=s:s∼t — zbiór sąsiadów miejsca t.

Niech Λ=1,…,l będzie skończonym zbiorem. Powiedzmy, że elementy a∈Λ są ,,kolorami” które mogą być przypisane elementom zbioru S. Konfiguracją nazywamy dowolną funkcję x:S→Λ. Będziemy mówić że xs=x⁢s jest s-tą współrzędną konfiguracji x i stosować oznaczenia podobne jak dla wektorów:

x=(xs)=(xs:s∈S).

(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 Λ=0,1 lub λ=[0,∞[. 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 X=ΛS. Dla konfiguracji x i miejsca t, niech

• x-t=(xs:s≠t)=(xs:s∈S∖{t}) — konfiguracja z pominiętą t-tą współrzędną,

• x∂⁡t=(xs:s∈∂t) — konfiguracja ograniczona do sąsiadów miejsca t.

Jeśli H:X→R i β⩾0 to rozkładem Gibbsa nazywamy rozkład prawdopodobieństwa na przestrzeni konfiguracji dany wzorem

πβ⁢x=1Z⁢β⁢exp⁡-β⁢H⁢x.

Ze względu na inspiracje pochodzące z fizyki statystycznej, funkcję H nazywamy energią, β jest (z dokładnością do stałej) odwrotnością temperatury. Stała normująca wyraża się wzorem

Z⁢β=∑x∈Xexp⁡-β⁢H⁢x.

(13.2)

i jest typowo niemożliwa do obliczenia.

Oczywiście, każdy rozkład prawdopodobieństwa π na X dale się zapisać jako rozkład Gibbsa, jeśli położyć H⁢x=-log⁡π⁢x, β=1 i umownie przyjąć, że -log⁡0=∞ (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

H⁢x=∑s∼tV⁢xs,xt+∑sUs⁢xs,

(13.3)

dla pewnych funkcji V:Λ×Λ→R i Us:Λ→R. Funkcja V⁢xs,xt opisuje ,,potencjał interakcji pomiędzy s i t”, zaś Us⁢a jest wielkością związaną z ,,tendencją miejsca s do przybrania koloru a. Zwróćmy uwagę, że potencjał V jest jednorodny (V⁢a,b zależy tylko od ,,kolorów” a,b∈Λ ale nie od miejsc), zaś Us⁢a może zależeć zarówno od a∈Λ jak i od s∈S. W modelach fizyki statystycznej zazwyczaj Us⁢a=U⁢a jest jednorodnym ,,oddziaływaniem zewnętrznym” ale w modelach rekonstrukcji obrazów nie można tego zakładać.

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.

Zauważmy, że obliczenie Hs⁢x jest łatwe, bo suma ∑t∈∂⁡s⋯ zawiera tylko tyle składników, ile jest sąsiadów miejsca s. Obliczenie Zs⁢β też jest łatwe, bo suma ∑a∈Λ⋯ zawiera tylko l=Λ składników. Ale nawet nie musimy obliczać stałej normującej Zs⁢β żeby generować z rozkładu

π(xs=a|x∂⁡s)∝exp-β(∑t:t∼sV(a,xt)+Us(a)).

(13.7)

Na tym opiera się implementacja próbnika Gibbsa. Wersję PG z ,,systemstycznym przeglądem miejsc” można zapisać tak:

Faktycznie już ten algorytm spotkaliśmy w Podrozdziale 12.2, dla szczególnego przypadku modelu auto-logistycznego.

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 X=ΛS, zdefiniowanej w Podrozdziale 13.1. Przyjmijmy, że ,,idealny obraz”, czyli to co chcielibyśmy zrekonstruować jest konfiguracją x∈X. Niestety, obraz jest ,,zakłócony” lub ,,zaszumiony”. Możemy tylko obserwować konfigurację y reprezentującą zakłócony obraz. Zbiór kolorów w obrazie y nie musi być identyczny jak w obrazie x. Powiedzmy, że y∈Y=ΓS. Ważne jest to, że zniekształcenie modelujemy probabilistycznie przy pomocy rodziny rozkładów warunkowych f(y|x). Dodatkowo zakładamy, że obraz x pojawia się losowo, zgodnie z rozkładem prawdopodobieństwa π⁢x. Innymi słowy, ,,idealny” obraz x oraz ,,zniekształcony” obraz y traktujemy jako realizacje zmiennych losowych X:Ω→X i Y:Ω→Y,

π(x)=P(X=x),f(y|x)=P(Y=y|X=x).

(13.8)

W ten sposób buduje się statystyczny model bayesowski, w którym

• Y jest obserwowaną zmienną losową,

• x jest nieznanym parametrem traktowanym jako zmienna losowa X.

Oczywiście, π gra rolę rozkładu a priori, zaś f jest wiarogodnością. Być może użycie literki x 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.

πy(x)=P(X=x|Y=y)∝f(y|x)π(x).

(13.9)

Pomysł Gemana i Gemana polegał na tym, żeby modelować rozkład a priori π jako MPL. Załóżmy, że π jest rozkładem Gibbsa,

π⁢x∝exp⁡-H⁢x,

(13.10)

gdzie

H⁢x=J⁢∑s∼tV⁢xs,xt.

(13.11)

Energia ,,a priori” zawiera tu tylko składniki reprezentujące oddziaływania między parami miejsc sąsiednich. Funkcja V⁢a,b zazwyczaj ma najmniejszą wartość dla a=b i rośnie wraz z ,,odległością” między a i b (jakkolwiek tę odległość zdefiniujemy). W ten sposób ,,nagradza” konfiguracje w których sąsiedznie miejsca są podobnie pokolorowane. Im większy parametr J>0, tym bardziej prawdopodobne są obrazy zawierające jednolite plamy kolorów.

Trzeba jeszcze założyć coś o ,,wiarogodności” f. Dla uproszczenia opiszę tylko najprostszy model, w którym kolor ys na obserwowanym obrazie zależy tylko od koloru xs na obrazie idealnym. Intuicyjnie znaczy to, że ,,zaszumienie” ma ściśle lokalny charakter. Matematycznie znaczy to, że

f(y|x)=∏sf(ys|xs)

(13.12)

(pozwolę sobie na odrobinę nieścisłości aby uniknąć nowego symbolu na oznaczenie f(ys|xs)). Zapiszemy teraz ,,wiarogodność” f w postaci zlogarytmowanej. Jeśli położymy -logf(ys|xs)=Us(xs) pamiętając, że y jest w świecie bayesowskim ustalone, to otrzymujemy następujący wzór:

πy⁢x∝exp⁡-Hy⁢x,

(13.13)

gdzie

Hy(x)=J∑s∼tV(xs,xt)-∑slogf(ys|xs).

(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 Us(xs)=-logf(ys|xs). Pamiętajmy przy tym, że y jest w świecie bayesowskim ustalone. W modelu rekonstrukcji obrazów ,,oddziaływania zewnętrzne” zależą od y 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.

Jeszcze lepiej to samo widać na przykładzie tak zwanego ,,szumu gaussowskiego”.