Entropia obrazu

21

Jaki jest najbardziej poprawny pod względem teoretycznym / informacyjnym sposób obliczenia entropii obrazu? W tej chwili nie dbam o wydajność obliczeniową - chcę, aby teoretycznie była jak najbardziej poprawna.

Zacznijmy od obrazu w skali szarości. Jednym intuicyjnym podejściem jest rozważenie obrazu jako worka pikseli i obliczenie gdzie jest liczbą poziomów szarości, a jest prawdopodobieństwem związanym z poziomem szarości .

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

K

$K$

p_{k}

$p_k$

k

$k$

Z tą definicją wiążą się dwa problemy:

Działa dla jednego pasma (tj. W skali szarości), ale jak należy rozszerzyć go w statystycznie poprawny sposób na wiele pasm? Na przykład, w przypadku 2 pasm należy oprzeć się na a zatem na PMF, używając ? Jeśli jeden ma wiele pasm ( >> 2), to , co wydaje się błędne. $(X_1,X_2)$ $P(X_1=x_1,X_2=x_2)$ $B$ $P(X_1=x_1, ..., X_B=x_B) \sim 1/N^B \rightarrow H_{MAX}$
Informacje przestrzenne nie są brane pod uwagę. Na przykład poniższe zdjęcia (opieka Johna Loomisa ) mają tę samą , chociaż wyraźnie nie przekazują tych samych informacji. $H$

Czy ktoś chce wyjaśnić lub udzielić porady lub skierować mnie do jakiegoś przyzwoitego materiału referencyjnego na ten temat? Interesuje mnie głównie teoretycznie poprawne podejście do drugiego problemu (tj. Informacji przestrzennej).

spatial entropy image-processing Davor Josipovic
źródło

2

Myślę, że powinieneś spojrzeć na losowe pola markowa,

seanv507

1

także matryce koegzystencji graylevel

seanv507

@ seanv507, tak, rzeczywiście. Studiuję teraz bezkierunkowe modele graficzne lub losowe pola Markowa. Odeśle, gdy dowiem się więcej.

Davor Josipovic

17

„Jaki jest najbardziej poprawny teoretycznie / informacyjnie i fizycznie sposób obliczenia entropii obrazu?”

Doskonałe i aktualne pytanie.

Wbrew powszechnemu przekonaniu rzeczywiście można intuicyjnie (i teoretycznie) zdefiniować naturalną entropię informacji dla obrazu.

Rozważ następujący rysunek:

Widzimy, że obraz różnicowy ma bardziej zwarty histogram, dlatego jego entropia informacji Shannona jest niższa. Możemy więc uzyskać niższą redundancję, stosując entropię Shannona drugiego rzędu (tj. Entropię uzyskaną z danych różnicowych). Jeśli możemy rozszerzyć ten pomysł izotropowo na 2D, możemy spodziewać się dobrych oszacowań dla entropii informacji obrazu.

Dwuwymiarowy histogram gradientów umożliwia rozszerzenie 2D.

Możemy sformalizować argumenty i rzeczywiście zostało to niedawno zakończone. Podsumowując krótko:

Obserwacja, że prosta definicja (patrz na przykład definicja entropii obrazu MATLAB) ignoruje strukturę przestrzenną, jest kluczowa. Aby zrozumieć, co się dzieje, warto krótko powrócić do skrzynki 1D. Od dawna wiadomo, że użycie histogramu sygnału do obliczenia jego informacji / entropii Shannona ignoruje strukturę czasową lub przestrzenną i daje słabą ocenę wewnętrznej ściśliwości lub nadmiarowości sygnału. Rozwiązanie było już dostępne w klasycznym tekście Shannona; użyj właściwości drugiego rzędu sygnału, tj. prawdopodobieństwa przejścia. Obserwacja z 1971 r. (Rice & Plaunt), że najlepszym predyktorem wartości piksela w skanie rastrowym jest wartość poprzedzającego piksela, co natychmiast prowadzi do predyktora różnicowego i entropii Shannona drugiego rzędu, która jest zgodna z prostymi pomysłami kompresji, takimi jak kodowanie długości przebiegu. Pomysły te zostały dopracowane pod koniec lat 80-tych, co zaowocowało pewnymi klasycznymi technikami bezstratnego (różnicowego) kodowania, które są nadal w użyciu (PNG, bezstratny JPG, GIF, bezstratny JPG2000), podczas gdy falki i DCT są używane tylko do kodowania stratnego.

Przejście teraz do 2D; badaczom bardzo trudno było rozszerzyć pomysły Shannona na wyższe wymiary bez wprowadzania zależności orientacyjnej. Intuicyjnie możemy oczekiwać, że entropia informacji Shannona obrazu będzie niezależna od jego orientacji. Oczekujemy również, że obrazy o skomplikowanej strukturze przestrzennej (jak na przykład przypadkowy szum pytającego) będą miały wyższą entropię informacji niż obrazy o prostej strukturze przestrzennej (jak na przykład gładka skala szarości pytającego). Okazuje się, że powodem, dla którego tak trudno było rozszerzyć pomysły Shannona z 1D na 2D, jest fakt (jednostronna) asymetria w oryginalnej formule Shannona, która uniemożliwia symetryczną (izotropową) formułę w 2D. Po skorygowaniu asymetrii 1D rozszerzenie 2D może przebiegać łatwo i naturalnie.

Przejdźmy do sedna (zainteresowani czytelnicy mogą sprawdzić szczegółową ekspozycję w preprint arXiv na https://arxiv.org/abs/1609.01117 ), gdzie entropia obrazu jest obliczana z histogramu 2D gradientów (funkcja gęstości prawdopodobieństwa gradientu).

Najpierw obliczany jest pdf 2D na podstawie binningu szacunków obrazów x i y pochodnych. Przypomina to operację binowania stosowaną do generowania bardziej powszechnego histogramu intensywności w 1D. Pochodne można oszacować na podstawie 2-pikselowych różnic skończonych obliczonych w kierunku poziomym i pionowym. Dla kwadratowego obrazu NxN f (x, y) obliczamy wartości NxN pochodnej cząstkowej fx i wartości NxN fy. Skanujemy obraz różnicowy i dla każdego używanego piksela (fx, fy) znajdujemy dyskretny pojemnik w docelowej tablicy (2D pdf), która jest następnie zwiększana o jeden. Powtarzamy dla wszystkich pikseli NxN. Wynikowy plik pdf 2D musi zostać znormalizowany, aby mieć ogólne prawdopodobieństwo jednostkowe (wystarczy podzielić przez NxN). Plik 2D pdf jest teraz gotowy do następnego etapu.

Obliczenie entropii informacji Shannona 2D z gradientu pdf pdf jest proste. Klasyczna formuła sumowania logarytmicznego Shannona ma zastosowanie bezpośrednio, z wyjątkiem istotnego współczynnika wynoszącego połowę, który pochodzi ze specjalnych rozważań o ograniczonym paśmie dla obrazu gradientowego (szczegóły w artykule arXiv). Współczynnik połowiczny sprawia, że obliczona entropia 2D jest jeszcze niższa w porównaniu do innych (bardziej redundantnych) metod szacowania entropii 2D lub kompresji bezstratnej.

Przepraszam, że nie zapisałem tutaj niezbędnych równań, ale wszystko jest dostępne w tekście przedruku. Obliczenia są bezpośrednie (nie iteracyjne), a złożoność obliczeniowa jest uporządkowana (liczba pikseli) NxN. Ostateczna obliczona entropia informacji Shannona jest niezależna od rotacji i odpowiada dokładnie liczbie bitów wymaganej do zakodowania obrazu w nie redundantnej reprezentacji gradientowej.

Nawiasem mówiąc, nowa miara entropii 2D przewiduje (intuicyjnie przyjemną) entropię 8 bitów na piksel dla obrazu losowego i 0,000 bitów na piksel dla obrazu z gładkim gradientem w pierwotnym pytaniu.

Kieran Larkin
źródło

1

Ciekawa praca. Teraz Razlighi dokonał porównania kilku algorytmów entropii w tym artykule . Zastanawiam się, jak twój by się porównał, szczególnie na syntetycznym obrazie, który tam wykorzystuje. Może warto to zbadać.

Davor Josipovic,

Dziękujemy za wzmiankę o artykule Razlighiego. Najważniejsze wyniki testu pokazano na ryc. 2. Uważam, że moja miara delentropii 2D miałaby entropię znormalizowaną jednostkowo dla korelacji 0,0, a następnie spadłaby do bliskiej znormalizowanej entropii dla korelacji 1,0. Tak naprawdę nie obliczałem tych wartości, ale wynika to bezpośrednio z sekcji 3.2 mojej przedruku arXiv, ponieważ wysoka korelacja odpowiada niskiej szerokości pasma widmowego, a zatem niskiej entropii.

Kieran Larkin,

Lubię to podejście. Wydaje mi się to intuicyjne. Dodatkowy krok obliczania gradientu przed obliczeniem entropii wydaje się intuicyjnie kodować informacje przestrzenne. Starałem się bawić i obliczyć ją Pythonie tutaj . Ale starałem się odtworzyć zasady z twojego papieru (patrz kod, ostatni przykład). Mogę je reprodukować tylko za pomocą pływaków! To dlatego, że przy liczbach całkowitych gradienty są w [-6,6] dla mojego obrazu testowego, nawet przy użyciu 16 bitów, co daje tylko 49 niezerowych przedziałów dla histogramu.

mxmlnkn

czy twój artykuł kiedykolwiek został opublikowany? Czy ty lub ktoś inny kontynuowałeś pracę?

Andrei

Przykładowy kod Matlaba byłby świetny.

Pedro77

8

Nie ma, wszystko zależy od kontekstu i twoich wcześniejszych informacji. Entropia ma wiele interpretacji, takich jak „pomiar porządku” lub „pomiar informacji”, ale zamiast patrzeć na interpretacje, wystarczy spojrzeć na to, co w rzeczywistości jest. Entropia jest tylko sposobem wyrażenia liczby stanów systemu. System z wieloma stanami ma wysoką entropię, a system z kilkoma stanami ma niską entropię.

Ty i artykuł, do którego linkujesz, stwierdza, że oba obrazy mają tę samą entropię. To nie jest poprawne (dla mnie).

Artykuł poprawnie oblicza entropię.

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

Dla pierwszego obrazu dowolny piksel może mieć dowolną szarą wartość,

p_{k} = \frac{1}{M} = 2^{- n}

$p_k = \frac{1}{M} = 2^{-n}$

Dlatego entropia jest:

H = - \sum_{k} p_{k} l o g_{2} (p_{k}) = - \sum_{k} 2^{- n} l o g_{2} (2^{- n}) = - l o g_{2} (2^{- n}) = n

$H = - \sum_k p_k log_2(p_k) = - \sum_k 2^{-n} log_2(2^{-n}) = - log_2(2^{-n}) = n$

Nie dotyczy to jednak drugiego obrazu.

Entropię można nadal obliczyć jako:

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

ale nie można po prostu powiedzieć, że , ponieważ gdy że jest wartością, wiesz, że to ta sama wartość. $p_k = \frac{1}{M} = 2^{-n}$ $p_1$ $p_2, p_3, p_4 \ldots p_{many}$

Dlatego te dwa obrazy nie mają tej samej entropii.

Może to zabrzmieć intuicyjnie, że entropia zależy od tego, jak spojrzysz na problem. Prawdopodobnie znasz to jednak z kompresji. Maksymalna kompresja pliku jest podyktowana twierdzeniem Shannona o kodowaniu źródłowym, które określa górną granicę skuteczności kompresji pliku przez algorytm kompresji. Limit ten zależy od entropii pliku. Wszystkie nowoczesne kompresory skompresują plik zbliżony do tego limitu.

Jeśli jednak wiesz, że plik jest plikiem audio, możesz go skompresować za pomocą FLAC zamiast zwykłego kompresora. FLAC jest bezstratny, więc wszystkie informacje są zachowane. FLAC nie może obejść twierdzenia o kodowaniu źródłowym Shannona, to jest matematyka, ale może patrzeć na plik w sposób, który zmniejsza entropię pliku, a tym samym zapewnia lepszą kompresję.

Identycznie, kiedy patrzę na ciebie drugi obraz, widzę, że piksele są sortowane według wartości szarości, a zatem nie ma dla mnie takiej samej entropii jak obraz z przypadkowym szumem.

bottiger
źródło

Myślę, że OP jest tego świadomy - prosi o modele probabilistyczne, które zawierają informacje przestrzenne

seanv507 16.09.16

@ seanv507 Ponownie przeczytałem pytanie. Nie jestem pewien, czy się z tobą zgadzam, czy nie. Wierzę, że OP szuka czegoś, co nie istnieje.

bottiger

@bottiger, dziękuję za odpowiedź. Myślę, że wszyscy zgadzamy się, że 2 obrazy powinny / nie mają tej samej entropii. To, co chcę wiedzieć, to poprawny (koncepcyjnie / teoretycznie) sposób jego obliczenia. Prosta formuła podana dla wydaje się nie uwzględniać informacji przestrzennej. Pytanie dotyczy tego, jak prawidłowo go rozszerzyć. Wrócę, kiedy będę wiedział więcej.

H

$H$

Davor Josipovic

@bottiger FLAC nie może zmniejszyć entropii pliku audio, ponieważ z definicji byłaby to kompresja stratna. Osiąga kompresję poprzez wyeliminowanie nadmiarowości.

Paul Uszak

Może słusznie jest powiedzieć, że klasyczna formuła entropii jest poprawna tylko wtedy, gdy wartości pikseli są stastycznie niezależne?

volperossa

2

Zasadniczo idea entropii jest czymś w rodzaju „liczby mikro-stanów zgodnych z makrostatem”.

Myślę, że zarówno komentarz sean507, jak i odpowiedź bottiger wskazują na wspólne ramy. Jeśli reprezentują przestrzeń obrazu przez generatywnej modelu , , to dla danego obrazu można (w zasadzie) obliczyć posterior nad ukrytym stanów (patrz także tutaj ). Następnie możesz (w zasadzie) obliczyć entropię tylnej części ciała. $p[\,I,h\,]$ $I$ $p[\,h\mid I\,]$

Zgadzam się więc, że jakakolwiek „entropia”, nawet w „najbardziej teoretycznie poprawnym znaczeniu”, wydaje się zależeć zarówno od zastosowanej reprezentacji , jak i modelu generatywnego łączącego „mikrostaty” ( ) z „makrostatami” ( ). $h$ $I$

GeoMatt22
źródło

1

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

ma nie działać w praktyce, z tego prostego powodu, że jest to prawie niemożliwe do określenia PK. Myślisz, że możesz to zrobić, tak jak zrobiłeś to, biorąc pod uwagę liczbę szarych poziomów. Pk to nie to. Pk to wszystkie możliwe kombinacje poziomów szarości. Musisz więc stworzyć wielowymiarowe drzewo prawdopodobieństwa, biorąc pod uwagę 1, 2, 3 ... kombinacje pikseli. Jeśli czytasz pracę Shannona, widzisz, jak wykonuje obliczenia dla zwykłego angielskiego, biorąc pod uwagę głębokość drzewa wynoszącą 3 litery. Wtedy staje się nieporęczny bez komputera.

Udowodniłeś to sam ze stwierdzeniem 2. Dlatego obliczenia entropii zwracają ten sam poziom entropii dla dwóch obrazów, nawet jeśli jeden jest wyraźnie mniej uporządkowany niż drugi.

Nie ma również takiej koncepcji rozkładu przestrzennego w ramach obliczania entropii. Gdyby tak było, musiałbyś również obliczyć entropię inaczej dla próbek dystrybuowanych czasowo. A co byś zrobił dla 11-wymiarowej tablicy danych? Do entropii informacyjnej; jest mierzony w bajtach.

Wystarczy skompresować obrazy za pomocą algorytmu kompresji. Wyprowadzi oszacowanie entropii w bajtach. Będzie to robić dla każdego obrazu lub dosłownie wszystkiego innego, co można zdigitalizować, takiego jak muzyka lub sztuki Szekspira.

Więc. Twój losowy obraz zawiera około 114 KB, a zamówiony obraz zawiera około 2,2 KB. Tego można się spodziewać, ale już to znaliście, ponieważ widzieliście, że rozmiary plików graficznych były tej wielkości. Zmniejszyłem rozmiar skompresowanego o 33%, aby umożliwić przyszłe ulepszenia algorytmów kompresji. Nie widzę, aby poprawiały się one poza tym, ponieważ krzywa poprawy staje się asymptotyczna do prawdziwej wartości bazowej.

PS Dla zainteresowania Szekspir wytworzył tylko 1 MB entropii w całym swoim życiu, obliczonym tą techniką. Większość jest jednak całkiem dobra.

Paweł Uszak
źródło

Entropia obrazu

Odpowiedzi: