W jaki sposób PNG jest bezstratny, skoro ma parametr kompresji?

Mówi się, że pliki PNG używają bezstratnej kompresji. Jednak za każdym razem, gdy jestem w edytorze obrazów, takim jak GIMP, i próbuję zapisać obraz jako plik PNG, prosi on o parametr kompresji, który zawiera się w przedziale od 0 do 9. Jeśli ma parametr kompresji, który wpływa na precyzję wizualną skompresowany obraz, w jaki sposób sprawia, że ​​PNG jest bezstratny?

Czy uzyskuję zachowanie bezstratne tylko po ustawieniu parametru kompresji na 9?

PNG jest bezstratny. GIMP najprawdopodobniej po prostu nie używa najlepszego słowa w tym przypadku. Pomyśl o tym jako o „jakości kompresji” lub innymi słowy „poziomie kompresji”. Przy niższej kompresji otrzymujesz większy plik, ale tworzenie zajmuje mniej czasu, podczas gdy przy wyższej kompresji otrzymujesz mniejszy plik, który zajmuje więcej czasu. Zwykle uzyskujesz malejące zwroty (tj. Nie tak duży spadek wielkości w porównaniu ze wzrostem czasu, jaki to zajmuje), gdy osiągasz najwyższe poziomy kompresji, ale to zależy od ciebie.

PNG jest skompresowany, ale bezstratny

Poziom kompresji jest kompromisem między rozmiarem pliku a prędkością kodowania / dekodowania. Aby nadmiernie uogólnić, nawet formaty inne niż obrazy, takie jak FLAC, mają podobne koncepcje.

Różne poziomy kompresji, ta sama dekodowana moc wyjściowa

Chociaż rozmiary plików są różne, ze względu na różne poziomy kompresji, rzeczywiste zdekodowane dane wyjściowe będą identyczne.

Możesz porównać skróty MD5 zdekodowanych danych wyjściowych za ffmpegpomocą multipleksera MD5 .

Najlepiej pokazuje to kilka przykładów:

Utwórz pliki PNG:

$ ffmpeg -i input -vframes 1 -compression_level 0 0.png
$ ffmpeg -i input -vframes 1 -compression_level 100 100.png

• Domyślnie ffmpegużyje -compression_level 100do wyjścia PNG.

Porównaj rozmiar pliku:

$ du -h *.png
  228K    0.png
  4.0K    100.png

Dekoduj pliki PNG i wyświetl skróty MD5:

$ ffmpeg -loglevel error -i 0.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

$ ffmpeg -loglevel error -i 100.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

Ponieważ oba skróty są takie same, możesz mieć pewność, że dekodowane wyjścia (nieskompresowane, surowe wideo) są dokładnie takie same.

Kompresja PNG odbywa się w dwóch etapach.

1. Wstępna kompresja reorganizuje dane obrazu, dzięki czemu będzie bardziej kompresowalny dzięki algorytmowi kompresji ogólnego przeznaczenia.
2. Rzeczywista kompresja jest wykonywana przez DEFLATE, który wyszukuje i eliminuje duplikaty sekwencji bajtów, zastępując je krótkimi tokenami.

Ponieważ krok 2 jest zadaniem bardzo czasochłonnym / zasobowym, podstawowa biblioteka zlib (enkapsulacja surowego DEFLATE) przyjmuje parametr kompresji od 1 = najszybsza kompresja, 9 = najlepsza kompresja, 0 = brak kompresji. Stąd pochodzi zakres 0–9, a GIMP po prostu przekazuje ten parametr do zlib. Zauważ, że na poziomie 0 twój png będzie nieco większy niż równoważna mapa bitowa.

Jednak poziom 9 jest tylko „najlepszym”, który spróbuje zlib, i nadal jest bardzo kompromisowym rozwiązaniem .
Aby naprawdę to poczuć, jeśli chcesz wydać 1000 razy więcej mocy obliczeniowej na wyczerpujące wyszukiwanie, możesz zyskać o 3-8% większą gęstość danych, używając zopfli zamiast zlib.
Kompresja jest nadal bezstratna, jest to po prostu bardziej optymalna reprezentacja DEFLATE danych. To zbliża się do granic bibliotek kompatybilnych z zlib, a zatem jest prawdziwą „najlepszą” kompresją, jaką można osiągnąć przy użyciu PNG.

Główną motywacją dla formatu PNG było stworzenie zamiennika dla GIF-a, który byłby nie tylko darmowy, ale również ulepszenie w stosunku do niego zasadniczo pod każdym względem. W rezultacie kompresja PNG jest całkowicie bezstratna - to znaczy oryginalne dane obrazu mogą być odtwarzane dokładnie, bit po bicie - tak jak w GIF i większości form TIFF.

PNG wykorzystuje 2-etapowy proces kompresji:

1. Kompresja wstępna: filtrowanie (prognoza)
2. Kompresja: DEFLATE (patrz wikipedia )

Etap wstępnej kompresji nazywa się filtrowaniem, czyli metodą odwracalnej transformacji danych obrazu, dzięki czemu główny silnik kompresji może działać wydajniej.

Jako prosty przykład rozważ sekwencję bajtów równomiernie rosnącą od 1 do 255:

1, 2, 3, 4, 5, .... 255

Ponieważ w sekwencji nie ma powtórzeń, kompresuje się albo bardzo słabo, albo wcale. Ale trywialna modyfikacja sekwencji - mianowicie pozostawienie pierwszego bajtu w spokoju, ale zastępowanie każdego kolejnego bajtu różnicą między nim a jego poprzednikiem - przekształca sekwencję w niezwykle ściśliwy zestaw:

1, 1, 1, 1, 1, .... 1

Powyższa transformacja jest bezstratna, ponieważ nie pominięto bajtów i jest całkowicie odwracalna. Skompresowany rozmiar tej serii zostanie znacznie zmniejszony, ale oryginalną serię nadal można doskonale odtworzyć.

Rzeczywiste dane obrazu rzadko są tak doskonałe, ale filtrowanie poprawia kompresję obrazów w skali szarości i trójwymiarowych, a także może pomóc w niektórych obrazach paletowych. PNG obsługuje pięć typów filtrów, a koder może wybrać inny filtr dla każdego rzędu pikseli na obrazie:

Algorytm działa na bajtach, ale w przypadku dużych pikseli (np. 24-bitowy RGB lub 64-bitowy RGBA) porównywane są tylko odpowiadające bajty, co oznacza, że ​​czerwone komponenty kolorów pikseli są obsługiwane osobno od zielonych i niebieskich pikseli.

Aby wybrać najlepszy filtr dla każdego wiersza, koder musiałby przetestować wszystkie możliwe kombinacje. Jest to oczywiście niemożliwe, ponieważ nawet 20-wierszowy obraz wymagałby przetestowania ponad 95 bilionów kombinacji, przy czym „testowanie” wymagałoby filtrowania i kompresji całego obrazu.

Poziomy kompresji są zwykle definiowane jako liczby od 0 (brak) do 9 (najlepszy). Odnoszą się one do kompromisów między prędkością a rozmiarem i odnoszą się do liczby kombinacji filtrów wierszy, które należy wypróbować. Nie ma żadnych standardów dotyczących tych poziomów kompresji, więc każdy edytor obrazów może mieć własne algorytmy określające, ile filtrów należy wypróbować, optymalizując rozmiar obrazu.

Poziom kompresji 0 oznacza, że ​​filtry w ogóle nie są używane, co jest szybkie, ale marnotrawstwo. Wyższe poziomy oznaczają, że coraz więcej kombinacji jest wypróbowywanych w wierszach obrazu i zachowywane są tylko te najlepsze.

Sądzę, że najprostszym podejściem do najlepszej kompresji jest stopniowe testowanie kompresji każdego wiersza z każdym filtrem, zapisanie najmniejszego wyniku i powtórzenie dla następnego wiersza. Sprowadza się to do pięciokrotnego filtrowania i kompresji całego obrazu, co może być rozsądnym kompromisem dla obrazu, który będzie transmitowany i dekodowany wiele razy. Niższe wartości kompresji zrobią mniej, według uznania twórcy narzędzia.

Oprócz filtrów, poziom kompresji może również wpływać na poziom kompresji zlib, który jest liczbą od 0 (bez deflacji) do 9 (maksymalna deflacja). Jak określone poziomy 0–9 wpływają na użycie filtrów, które są główną funkcją optymalizacji PNG, nadal zależy od autora narzędzia.

Wniosek jest taki, że PNG ma parametr kompresji, który może znacznie zmniejszyć rozmiar pliku, a wszystko to bez utraty nawet jednego piksela.

Źródła:

Dokumentacja libpng Wikipedii Portable Portable Graphics
Rozdział 9 - Kompresja i filtrowanie

OK, spóźniłem się na nagrodę, ale i tak oto moja odpowiedź.

PNG jest zawsze bezstratny . Wykorzystuje algorytm Deflate / Inflate, podobny do tych używanych w programach zip.

Algorytm Deflate wyszukuje powtarzające się sekwencje bajtów i zastępuje je tagami. Ustawienie poziomu kompresji określa, ile wysiłku włożony jest program, aby znaleźć optymalną kombinację sekwencji bajtów i ile pamięci jest na to zarezerwowane. Jest to kompromis między zużyciem czasu i pamięci a wielkością skompresowanego pliku. Jednak współczesne komputery są tak szybkie i mają wystarczającą ilość pamięci, że rzadko trzeba używać innego niż najwyższe ustawienie kompresji.

Wiele implementacji PNG używa biblioteki zlib do kompresji. Zlib ma dziewięć poziomów kompresji, 1-9. Nie znam wewnętrznych funkcji Gimp, ale ponieważ ma on ustawienia poziomu kompresji 0–9 (0 = brak kompresji), zakładam, że to ustawienie po prostu wybiera poziom kompresji zlib.

Algorytm deflacji jest algorytmem kompresji ogólnego przeznaczenia , nie został zaprojektowany do kompresji zdjęć. W przeciwieństwie do większości innych formatów plików bezstratnych format PNG nie jest do tego ograniczony. Kompresja PNG wykorzystuje wiedzę, że kompresujemy obraz 2D . Osiąga się to dzięki tak zwanym filtrom .

(Filtr jest tutaj trochę mylącym określeniem. W rzeczywistości nie zmienia zawartości obrazu, po prostu koduje go inaczej. Dokładniejsza nazwa to koder delta.)

Specyfikacja PNG określa 5 różnych filtrów (w tym 0 = brak). Filtr zastępuje bezwzględne wartości pikseli z różnicą od poprzednich pikseli do lewej, w górę, po przekątnej lub ich kombinacji. Może to znacznie poprawić współczynnik kompresji. Każda linia skanowania na obrazie może używać innego filtra. Koder może zoptymalizować kompresję, wybierając najlepszy filtr dla każdej linii.

Aby uzyskać szczegółowe informacje na temat formatu pliku PNG, zobacz Specyfikacja PNG .

Ponieważ istnieje praktycznie nieskończona liczba kombinacji, nie można wypróbować ich wszystkich. Dlatego opracowano różne strategie znalezienia skutecznej kombinacji. Większość edytorów obrazów prawdopodobnie nawet nie próbuje optymalizować filtrów linia po linii, ale zamiast tego używała tylko filtra stałego (najprawdopodobniej Paeth).

Program pngcrush z linii poleceń próbuje kilku strategii, aby znaleźć najlepszy wynik. Może znacznie zmniejszyć rozmiar pliku PNG utworzonego przez inne programy, ale na większych obrazach może zająć sporo czasu. Zobacz Source Forge - pngcrush .

Poziom kompresji w bezstratnych rzeczach zawsze polega na wymianie zasobów kodowania (zwykle czas, czasem także pamięć RAM) vs. bitrate. Jakość jest zawsze w 100%.

Oczywiście bezstratne sprężarki NIGDY nie gwarantują żadnej rzeczywistej kompresji. Losowe dane są nieściśliwe, nie ma wzorca do znalezienia ani podobieństwa. Teoria informacji Shannona i tak dalej. Chodzi o to, że bezstratna kompresja danych polega na tym, że ludzie zwykle pracują z wysoce nieprzypadkowymi danymi, ale w celu transmisji i przechowywania możemy spakować je do jak najmniejszej liczby bitów. Mamy nadzieję, że będzie tak blisko jak najbardziej złożoności oryginału Kołmogorowa .

Niezależnie od tego, czy jest to zip, czy ogólne dane 7z, obrazy png, dźwięk flac lub wideo w formacie h.264 (w trybie bezstratnym), to to samo. W przypadku niektórych algorytmów kompresji, takich jak lzma (7zip) i bzip2, zwiększenie ustawienia kompresji zwiększy czas pracy dekodera (bzip2) lub częściej tylko potrzebną ilość pamięci RAM (lzma i bzip2 oraz h.264 z większą liczbą ramek odniesienia) . Często dekoder musi zapisać więcej zdekodowanych danych wyjściowych w pamięci RAM, ponieważ dekodowanie następnego bajtu może odnosić się do bajtu zdekodowanego wiele megabajtów temu (np. Klatka wideo najbardziej podobna do jednej sprzed pół sekundy temu zostałaby zakodowana z odniesieniem do 12 klatek wstecz ). To samo dotyczy bzip2 i wybrania dużego rozmiaru bloku, ale to również wolniej dekompresuje. lzma ma słownik o zmiennym rozmiarze i możesz tworzyć pliki, które wymagałyby 1.

Po pierwsze, PNG jest zawsze bezstratny. Pozorny paradoks wynika z faktu, że możliwe są dwa różne rodzaje kompresji (dla dowolnego rodzaju danych): stratny i bezstratny.

Bezstratna kompresja ściska dane (tj. Rozmiar pliku) przy użyciu różnych sztuczek, zachowując wszystko i bez przybliżania. W rezultacie możliwe jest, że kompresja bezstratna w ogóle nie będzie w stanie kompresować rzeczy. (Dane techniczne z wysoką entropią mogą być bardzo trudne lub nawet niemożliwe do skompresowania w przypadku metod bezstratnych.) Kompresja stratna przybliża rzeczywiste dane, ale aproksymacja jest niedoskonała, ale to „wyrzucenie” precyzji pozwala zazwyczaj na lepszą kompresję.

Oto trywialny przykład bezstratnej kompresji: jeśli masz obraz wykonany z 1000 czarnych pikseli, zamiast przechowywać wartość czerni 1000 razy, możesz zapisać liczbę (1000) i wartość (czarny), kompresując w ten sposób 1000 pikseli „ obraz ”w zaledwie dwie liczby. (Jest to surowa forma bezstratnej metody kompresji zwanej kodowaniem długości przebiegu).