ściąga_KiK.pdf

(558 KB) Pobierz
Entropia
Zbiór prawdopodobieństw generowania przez źródło symboli (czyli rozkład
prawdopodobieństwa) P = {p1, p2,...,pn}. Def. entropię rozkładu P jako:
wynika
Entropia
rozkładu prawdopodobieństwa jest
wartością oczekiwaną
informacji
określonej tym rozkładem.
Własności entropii
1. H >= 0
2. Dla alfabetu o N -elementach entropia będzie maksymalna i równa log N jeśli
prawdopodobieństwa wystąpienia wszystkich liter alfabetu będą jednakowe
(p=1/N).
Zbiór symboli użytych przez źródło do generowania strumienia symboli
nazywamy
alfabetem źródła,
a symbole
literami.
Niech alfabetem źródła będzie zbiór symboli {a b}a prawdopodobieństwo
wystąpienia litery
a
wynosi
p.
Obliczmy entropię tego źródła:
H = -p log p -(1-p) log (1-p)
Wykres entropii w zależności od prawdopodobieństwa.
Wartość entropi jest najwyższa kiedy prawdopodobieństwa są różne, natomiast
najniższa kiedy prawdopodobieństwa są najbardziej zróżnicowane.
Modele Markowa
Źródło Markowa m-tego rzędu jest to źródło generujące ciąg symboli
{x
n
},w którym pojawienie się symbolu x
i
zależy od
m symboli
uprzednio
wygenerowanych przez to źródło. Wiedza o ostatnio wygenerowanych
m
symbolach
jest równoważna wiedzy o całej historii procesu.
Zbiór wartości {x
n-1
,..., x
n-m
} nazywa się stanami procesu. Jeśli rozmiar
m
alfabetu źródła wynosi L to liczba stanów jest równa L .
Najczęściej wykorzystywanym modelem jest model Markowa pierwszego
rzędu (m=1), dla którego:
p (x
n
|x
n
-1) = p (x
n
| x
n
-1, x
n-2
,..., x
1
)
Modele Markowa (dwustanowy)
Obraz przedstawiający konkretną rzecz złożony jest z czarnych i białych
pikseli. Możemy tu wykorzystać łańcuch Markowa pierwszego rzędu, gdyż
to czy następny piksel w obrazie będzie biały czy czarny zależy w dużym
stopniu od bieżącego piksela.
Stany:
Sb-bieżący piksel jest biały i Sc-bieżący piksel jest czarny.
Prawdopodobieństwa przejść:
p(b|c) i p(c|b).
Entropia obrazu binarnego dla dwóch modeli:
Dla obrazu binarnego możemy przyjąć następujące wartości
prawdopodobieństw:
p(Sb) = 0.97, p(Sc) = 0.03 oraz p(b|b) = 0.99, p(c|b) = 0.01, p(c|c) = 0.7,
p(b|c) = 0.3.
1)model
probabilistyczny: poszczególne piksele są generowane niezależnie
z identycznym rozkładem prawdopodobieństwa,
H1= -0.97 * log (0.97) -0.03 * log (0.03) =
0.21bita/piksel
2)model
Markowa pierwszego rzędu: prawdopodobieństwo koloru
bieżącego piksela jest uzależnione od koloru poprzedniego.
H(Sb) = -0.01 log (0.01) -0.99 log (0.99) = 0.08 bita
H(Sc) = -0.3 log (0.3) -0.3 log (0.3) = 0.88 bita

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin