Jaki jest limit danych bezstratnej kompresji? (jeśli istnieje taki limit)

Ostatnio miałem do czynienia z algorytmami związanymi z kompresją i zastanawiałem się, który jest najlepszy współczynnik kompresji, jaki można osiągnąć dzięki kompresji danych bezstratnych.

Jak dotąd jedynym źródłem, jakie mogłem znaleźć na ten temat, była Wikipedia:

Bezstratna kompresja danych cyfrowych, takich jak wideo, filmy cyfrowe i dźwięk, zachowuje wszystkie informacje, ale rzadko może być lepsza niż kompresja 1: 2 z powodu wewnętrznej entropii danych.

Niestety artykuł Wikipedii nie zawiera referencji ani cytatów na poparcie tego twierdzenia. Nie jestem ekspertem od kompresji danych, więc doceniłbym wszelkie informacje, które możesz podać na ten temat, lub gdybyś mógł wskazać mi bardziej wiarygodne źródło niż Wikipedia.

Nie jestem pewien, czy ktoś jeszcze wyjaśnił, dlaczego magiczna liczba wydaje się dokładnie 1: 2, a nie na przykład 1: 1.1 lub 1:20.

Jednym z powodów jest to, że w wielu typowych przypadkach prawie połowa danych cyfrowych to szum , a szumu (z definicji) nie można skompresować.

Zrobiłem bardzo prosty eksperyment:

• Wziąłem szarą kartę . Dla ludzkiego oka wygląda jak zwykły, neutralny kawałek szarego kartonu. W szczególności nie ma informacji .

• A potem wziąłem normalny skaner - dokładnie taki rodzaj urządzenia, którego ludzie mogliby użyć do digitalizacji swoich zdjęć.

• Przeskanowałem szarą kartę. (Właściwie zeskanowałem szarą kartę wraz z pocztówką. Pocztówka była tam, aby sprawdzić zdrowie psychiczne, aby upewnić się, że oprogramowanie skanera nie robi nic dziwnego, na przykład automatycznie dodaje kontrast, gdy widzi szarą kartę bez cech.)

• Skadrowałem część szarej karty o wymiarach 1000 x 1000 pikseli i przekonwertowałem ją na skalę szarości (8 bitów na piksel).

To, co mamy teraz, powinno być dość dobrym przykładem tego, co dzieje się, gdy studiujesz pozbawioną cech część zeskanowanego czarno-białego zdjęcia , na przykład czyste niebo. Zasadniczo nie powinno być nic do zobaczenia.

Jednak przy większym powiększeniu wygląda to tak:

Nie ma wyraźnie widocznego wzoru, ale nie ma jednolitego szarego koloru. Część z nich jest najprawdopodobniej spowodowana niedoskonałościami szarej karty, ale przypuszczam, że większość z nich to po prostu szum wytwarzany przez skaner (szum termiczny w celi czujnikowej, wzmacniaczu, przetworniku A / D itp.). Wygląda prawie jak szum Gaussa; oto histogram (w skali logarytmicznej ):

Teraz, jeśli założymy, że każdy piksel ma wybrany odcień w tym rozkładzie, ile mamy entropii? Mój skrypt w Pythonie powiedział mi, że mamy aż 3,3 bity entropii na piksel . I to dużo hałasu.

Gdyby tak było naprawdę, oznaczałoby to, że niezależnie od używanego algorytmu kompresji mapa bitowa 1000 x 1000 pikseli zostałaby skompresowana, w najlepszym przypadku, do pliku 412500 bajtów. A co się dzieje w praktyce: mam plik PNG o wielkości 432018 bajtów, całkiem blisko.

Jeśli nieco nadmiernie uogólnimy, wydaje się, że bez względu na to, które czarno-białe zdjęcia skanuję za pomocą tego skanera, otrzymam sumę następujących rzeczy:

• „przydatne” informacje (jeśli istnieją),
• hałas, ok. 3 bity na piksel.

Teraz nawet jeśli algorytm kompresji wyciska użyteczne informacje na << 1 bit na piksel, nadal będziesz mieć aż 3 bity na piksel nieściśliwego szumu. Wersja nieskompresowana ma 8 bitów na piksel. Tak więc współczynnik kompresji będzie wynosił 1: 2, bez względu na to, co robisz.

Kolejny przykład z próbą znalezienia zbyt wyidealizowanych warunków:

• Nowoczesna lustrzanka cyfrowa, wykorzystująca najniższe ustawienie czułości (najmniej szumów).
• Ujęcie nieostrej szarej karty (nawet jeśli na szarej karcie były widoczne informacje, zostałyby zamazane).
• Konwersja pliku RAW na 8-bitowy obraz w skali szarości, bez dodawania kontrastu. Użyłem typowych ustawień w komercyjnym konwerterze RAW. Konwerter domyślnie próbuje zredukować hałas. Co więcej, zapisujemy wynik końcowy jako plik 8-bitowy - w zasadzie wyrzucamy bity najniższego rzędu odczytów czujnika!

A jaki był wynik końcowy? Wygląda znacznie lepiej niż to, co dostałem ze skanera; hałas jest mniej wyraźny i nic nie można zobaczyć. Niemniej hałas gaussowski jest obecny:

A entropia? 2,7 bitów na piksel . Rozmiar pliku w praktyce? 344923 bajtów dla 1M pikseli. W naprawdę najlepszym scenariuszu, z pewnym oszustwem, zwiększyliśmy współczynnik kompresji do 1: 3.

Oczywiście wszystko to nie ma nic wspólnego z badaniami TCS, ale myślę, że dobrze jest pamiętać, co naprawdę ogranicza kompresję danych cyfrowych w świecie rzeczywistym. Postępy w projektowaniu bardziej zaawansowanych algorytmów kompresji i surowej mocy procesora nie pomogą; jeśli chcesz bezstratnie zaoszczędzić cały hałas, nie możesz zrobić nic lepszego niż 1: 2.

Czy wiesz już o bezgłośnym twierdzeniu Shannona o kodowaniu ? Twierdzenie to ustanawia teoretyczne ograniczenia kompresji bezstratnej. Niektóre komentarze innych wydają się zakładać, że wiesz o tym twierdzeniu, ale z pytania, myślę, że może to być odpowiedź, której szukasz.

Kompresja jest po prostu oportunistycznym sposobem kodowania rzeczy, a gdy pytasz o „najlepszy współczynnik kompresji, który można osiągnąć dzięki bezstratnej kompresji danych”, musisz bardziej szczegółowo określić kontekst kompresji: współczynnik kompresji jest stosunkiem między rozmiar kompresji i rozmiar „surowego” kodowania, ale rozmiar „surowego” kodowania zależy od hipotezy o twoim obiekcie (tj. wielkości jego domeny lub „wielkości torby, z której pochodzi”) ). Jako uproszczony przykład rozważ zadanie kodowania dodatniej liczby całkowitej :$n>0$

1. Możesz użyć tylko jednego bitu, jeśli jest jedyną liczbą całkowitą, jaką kiedykolwiek kodujesz, i musisz tylko pamiętać, że ją zakodowałeś.$n$

2. Powszechnym praktycznym rozwiązaniem jest użycie 8 bitów, jeśli jedynymi liczbami całkowitymi, które kiedykolwiek kodujesz, są między 1 a 256 (uogólnij na 16, 32 i 64 bity, jeśli chcesz).

3. Jeśli nie masz żadnej hipotezy na temat zakresu, w którym mieści się liczba całkowita, którą będziesz musiał zakodować, naiwnym rozwiązaniem jest użycie bitów ( zer, po których następuje jeden), aby zakodować je w jedności. To może jeszcze nie wyglądać na kompresję, ale ma oportunistyczny aspekt kompresji: im mniejsza wartość , tym mniejszy rozmiar jej jednoargumentowego kodowania.n $n+1$$n$$n$

4. Bardziej poważnym, ogólnym celem kodowania liczb całkowitych jest kod gamma : wartość w jedności za pomocą bitów, a następnie w binarnie, używając (nie potrzebujesz najbardziej wysuniętego w lewo bitu, który zawsze jest jeden, ponieważ znasz już wartość ). To kodowanie używa łącznie bitów i jest użyteczną kompresją , często używaną w praktyce. (Zauważ, że w literaturze znajdziesz te wyniki zanotowane aby skrócić notacje.)$\lceil\log_2 n\rceil$$\lceil\log_2 n\rceil+1$$n$$\lceil\log_2 n\rceil-1$$\lceil\log_2 n\rceil$$2\lceil\log_2 n\rceil-1$$n$$\lg n=\max(1,\lceil\log_2 n\rceil)$

5. Kod gamma nie jest optymalny w tym sensie, że istnieją inne kody, które zajmują mniej miejsca na dowolnie wiele liczb całkowitych, a więcej na tylko skończoną ilość. Bardzo dobrym odczytem na ten temat jest „Prawie optymalny algorytm do wyszukiwania nieograniczonego” autorstwa Jona Louisa Bentleya i Andrew Chi-Chiha Yao z 1976 roku (szczególnie podoba mi się ich związek między złożonością algorytmów wyszukiwania a rozmiarem kodowania liczb całkowitych: I znaleźć jeden z najprostszych i najpiękniejszych wyników TCS, jakie znam). Najważniejsze jest to, że bitów mieści się w współczynniku dwa z optymalnych, co większość zgadza się, że wystarczy w praktyce, biorąc pod uwagę złożoność lepszych rozwiązań.$2\lceil\log_2 n\rceil-1$

6. Jednak biorąc pod uwagę „oportunistyczne” podejście do jego granicy, istnieje nieskończona liczba schematów kompresji wykorzystujących różne hipotezy. Jednym ze sposobów radzenia sobie z tą nieskończonością kodowań oportunistycznych (tj. Schematem kompresji) jest wymaganie kodowania samej hipotezy i uwzględnienie rozmiaru kodowania hipotezy w całkowitym rozmiarze kompresji. Formalnie odpowiada to kodowaniu zarówno skompresowanych danych, jak i dekodera , lub bardziej ogólnie kodowaniu programu, który po uruchomieniu generuje nieskompresowany obiekt: najmniejszy rozmiar takiego programu nazywa się złożonością Kołmogorowa . Jest to bardzo teoretyczna konstrukcja w tym sensie, że bez ograniczenia czasu wykonania programu$K$$K$nie jest obliczalny. Łatwe obejście tego pojęcia daje samoograniczające się programy Levina , w których bierze się pod uwagę tylko programy z ograniczonym czasem wykonania (na przykład w ramach stałego współczynnika długości oryginalnej instancji, który jest dolną granicą złożoność algorytmu, który musi zapisać każdy symbol).

Istnieje cała społeczność pracująca nad złożonością Kołmogorowa i jego wariantami, a inna społeczność pracuje nad kompresją bezstratną (przykład na liczbach całkowitych, których użyłem, ma odpowiednik na wielu innych typach danych), ledwo zarysowałem powierzchnię, a inni mogą dodać dokładności (Kołmogorow nie jest tak naprawdę moją specjalnością), ale mam nadzieję, że może to pomóc w wyjaśnieniu pytania, jeśli niekoniecznie da odpowiedź, na którą liczyłeś :)

(tylko rozszerzenie mojego komentarza)

(Jak wskazał Joe w swojej odpowiedzi) Shannon - w swoim artykule z 1948 r. „ Matematyczna teoria komunikacji ” sformułował teorię kompresji danych i ustalił, że istnieje fundamentalna granica bezstratnej kompresji danych. Limit ten, zwany współczynnikiem entropii, oznaczony jest przez H. Dokładna wartość H zależy od źródła informacji --- dokładniej od statystycznej natury źródła. Możliwe jest skompresowanie źródła w bezstratny sposób, ze stopniem kompresji zbliżonym do H. Niemożliwe jest matematycznie wykonanie lepszej niż H.

Jednak niektóre klasy obrazów (na przykład medyczne obrazy w skali szarości) bez krawędzi o wysokim kontraście i z płynnymi przejściami poziomów mogą być kompresowane (nie tak skutecznie).

JPEG-LS i JPEG2000 wydają się być standardami bezstratnego przechowywania obrazów medycznych. Tabela ta zawiera porównanie współczynników kompresji (JPEG-LS osiąga nieco lepszą kompresję).

Korzystając z „bezstratnej kompresji obrazu medycznego” znalazłem następujące artykuły, które mogą ci pomóc:

Niedawna ankieta (2011) na temat technik kompresji obrazu medycznego: dwuwymiarowe techniki kompresji obrazu medycznego - ankieta

... W tym artykule omówiono różne techniki kompresji oparte na DCT, DWT, ROI i sieciach neuronowych dla dwuwymiarowych (2D) nieruchomych obrazów medycznych.

Szczegółowa prezentacja dwóch standardowych algorytmów kompresji bezstratnej: JPEG-LS i JPG2000 w trybie bezstratnym: Bezstratna kompresja obrazów medycznych w skali szarości - skuteczność metod tradycyjnych i najnowocześniejszych

... Przetestowano trzy tysiące sześćset siedemdziesiąt dziewięć (3679) pojedynczych klatek w skali szarości z wielu obszarów anatomicznych, modalności i dostawców. ...

Kolejna ankieta: Przegląd współczesnych technik kompresji obrazu medycznego

EDYTOWAĆ

Być może nadal zastanawiasz się „Czym do diabła jest entropia obrazu?” ... OK, to ilość informacji zawartych w obrazie ... ale aby lepiej to zrozumieć, powinieneś przeczytać coś o 3 fazach zwykle używanych w kompresji obrazu :

• transformacja (na przykład dyskretna transformacja falkowa)
• kwantyzacja
• kodowanie entropijne

Możesz użyć Google, aby wyszukać samouczek lub książkę na temat kompresji obrazu (na przykład szybki samouczek ) lub spróbować obejrzeć techniczny film online (na przykład Wykład 16 - Wprowadzenie do kodowania obrazu i wideo ).

Pomyśl o pliku jako o łańcuchu.

Nigdy nie da się lepiej niż złożoność łańcucha Kołmogorowa (z definicji złożoności Komogorowa).

Napraw długość łańcucha. Więc teraz patrzymy tylko na ciągi długości n.

Połowę wszystkich takich ciągów można skompresować maksymalnie o 1 bit. 1/4 wszystkich łańcuchów można skompresować maksymalnie o 2 bity. 1/8 wszystkich takich ciągów może być skompresowana maksymalnie o 3 bity.

Jaką część łańcuchów (obrazów, plików itp.) Można skompresować w stosunku 2: 1 - bardzo, bardzo niewiele. Dlaczego więc kiedykolwiek działa kompresja? Ponieważ prawie wszystkie dane, które prawdziwi ludzie próbują skompresować, mają bardzo uporządkowaną strukturę - nie wygląda jak losowy plik. Im bardziej losowo wyglądają dane, tym trudniej je skompresować. Idą w parze. Większość łańcuchów wygląda losowo.

Aby zobaczyć to w akcji, wygeneruj losowy plik przy użyciu losowego procesu. Mam na myśli naprawdę losowy plik. Teraz spróbuj skompresować go za pomocą swojego ulubionego algorytmu kompresji. Przez cały czas będzie albo utrzymywał ten sam rozmiar, albo się powiększy.

Z drugiej strony znajdują się wysoce ściśliwe sznurki. Weź następujący ciąg: 100000..000 (1, po którym następuje milion zer). Jego opis mieści się w poprzednim zdaniu, a komputer może go zrekonstruować na podstawie tego opisu (lub jednego bardzo podobnego). Jednak ten opis nie ma prawie miliona cyfr.

Faktem jest, że ciągi o tej właściwości (charakteryzujące się wysoką ściśliwością) są niezwykle rzadkie wśród wszystkich możliwych ciągów. Drugi fakt jest taki, że prawie wszystkie dane generowane przez ludzi są super, super ściśliwe, ponieważ mają taką strukturę.