Entropia obrazu

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 .K p k

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

1. 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.P ( X 1 = x 1 , X 2 = x 2 ) B P ( X 1 = x 1 , . . . , X B = x B ) ~ 1 / N B → H M $(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}$
2. 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).

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

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

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

Dlatego entropia jest:

Nie dotyczy to jednak drugiego obrazu.

Entropię można nadal obliczyć jako:

ale nie można po prostu powiedzieć, że , ponieważ gdy że jest wartością, wiesz, że to ta sama wartość.p1p2,p3,p4…pman$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.

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.I p $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$

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.