Kodowanie Huffmana wypierane przez ANS pochodzące z Polski (m.in. Apple, Facebook, Google)

0

Jeśli chcesz zakodować wydajną implementację od zera to i tak zejdą ci z tym tygodnie albo i miesiące.

1
[exp4 napisał(a)]

Może przetestuję to jak należy, a wtedy zobaczymy... co to jest warte.

Dzieki!!! Wszyscy czekamy z niecierpliwoscią!

0
Wibowit napisał(a):

Jeśli chcesz zakodować wydajną implementację od zera to i tak zejdą ci z tym tygodnie albo i miesiące.

Ja takie banały w godzinkę robię zwykle - od zera.
No ale jeśli nie macie nawet algorytmu tego kodowania, no to sory i niestety -
ja nie będę się gimnastykował żeby wyręczyć autora (kolejnego głąba - pseudoteoretyka), który nie wie nawet co to jest algorytm.

0
exp5 napisał(a):
Wibowit napisał(a):

Jeśli chcesz zakodować wydajną implementację od zera to i tak zejdą ci z tym tygodnie albo i miesiące.

Ja takie banały w godzinkę robię zwykle - od zera.
No ale jeśli nie macie nawet algorytmu tego kodowania, no to sory i niestety -
ja nie będę się gimnastykował żeby wyręczyć autora (kolejnego głąba - pseudoteoretyka), który nie wie nawet co to jest algorytm.

Czy naprawdę potrzebne są tu anonimowe konta?

0

To może pokaż wzory i algorytmy które można zakodować wprost na przykładzie: https://en.wikipedia.org/wiki/Arithmetic_coding

0
Wibowit napisał(a):

To może pokaż wzory i algorytmy które można zakodować wprost na przykładzie: https://en.wikipedia.org/wiki/Arithmetic_coding

A co to za problem?
To jest znane i dawno opisane poprawnie w literaturze.
Po prostu obliczasz jedną długą liczbę z danych o dowolnej długości... no i to tyle.

0

Tutaj jest pełno materiałów, linki do różnych implementacji: https://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations

Benchmarki różnych entropy coderów z linkami do implementacji: https://sites.google.com/site/powturbo/entropy-coder

FSE z Facebook Zstandard (też np. w jądrze Linuxa): https://github.com/Cyan4973/FiniteStateEntropy

0

a swoją drogą (może palnę głupotę), przecież możnaby przechowywać dane np. w systemie szesnastkowym (4 razy krótsze ciągi zerojedynkowe), a resztę można zrobić na ciągach zerojedynkowych, convert mamy prosty :)

1

Szesnastkowo to 4 bity (nibble) na symbol, podczas gdy w kompresji ilość bitów na symbol jest zmienna - zależy od prawdopodobieństwa symbolu.
Huffman używa pełnych bitów na symbol, podczas gdy prawdziwe mogą nieść ułamkowe bity - z którymi radzi sobie kodowanie arytmetyczne i ANS.
Tutaj jest przystępnie opisane: http://www.nauka.uj.edu.pl/aktualnosci/-/journal_content/56_INSTANCE_Sz8leL0jYQen/74541952/135372600

1

hurgadion, ilość symboli w alfabecie (podstawa systemu liczbowego) może być różna, też 16.
Tutaj z https://en.wikipedia.org/wiki/Asymmetric_numeral_systems po prawej masz przykład zapisania "01111" w zwykłym dwójkowym (wyszło 47), na dole w asymetrycznym zoptymalizowanym do większego prawdopodobieństwa 1 - wyszło 18 czyli zapisaliśmy krócej:

title

2
hurgadion napisał(a):

a swoją drogą (może palnę głupotę), przecież możnaby przechowywać dane np. w systemie szesnastkowym (4 razy krótsze ciągi zerojedynkowe), a resztę można zrobić na ciągach zerojedynkowych, convert mamy prosty :)

Co to znaczy przechowywać dane w systemie szesnastkowym? Gdzie ma być z tego zysk?

Alfabet wejściowy w ANS nie musi mieć rozmiaru 2. Może mieć prawie dowolny rozmiar (ograniczany zużyciem pamięci). Na wejściu możesz mieć np bajty, które jak wiadomo mogą przyjąć jedną z 256 wartości.

0
Wibowit napisał(a):
hurgadion napisał(a):

a swoją drogą (może palnę głupotę), przecież możnaby przechowywać dane np. w systemie szesnastkowym (4 razy krótsze ciągi zerojedynkowe), a resztę można zrobić na ciągach zerojedynkowych, convert mamy prosty :)

Co to znaczy przechowywać dane w systemie szesnastkowym? Gdzie ma być z tego zysk?

Alfabet wejściowy w ANS nie musi mieć rozmiaru 2. Może mieć prawie dowolny rozmiar (ograniczany zużyciem pamięci). Na wejściu możesz mieć np bajty, które jak wiadomo mogą przyjąć jedną z 256 wartości.

Jemu chodzi o kompresję tekstu, gdzie zwykle jest 1Bajt = 1 znak,
zatem w przypadku liczb, znaczy zapisywanych tak wprost:
1234567890 - 10 cyfr czyli i bajtów w pliku tekstowym

no więc gdyby to zapisywać w hex, ale nadal w txt, wtedy będzie tego mniej... ile mniej?

Stąd pomysły z kodowaniem danych binarnych - obrazów na... 85 znakach, hehe!
co jest używane w postscripcie do zapisu bajtów map bitowych, ale nadal w postaci tekstowej.

0

Entropia danych generalnie nie zależy od sposobu ich zapisu. Sposób zapisu może za to wpłynąć na pracę kompresora. Przykładowo: kompresor wykrywa i specjalnie koduje liczby dziesiętne, ale wykłada się na heksach i nie kompresuje ich. W takim przypadku nie opłaca się zamieniać liczb dziesiętnych na szesnastkowe.

0
Wibowit napisał(a):

Entropia danych generalnie nie zależy od sposobu ich zapisu. Sposób zapisu może za to wpłynąć na pracę kompresora. Przykładowo: kompresor wykrywa i specjalnie koduje liczby dziesiętne, ale wykłada się na heksach i nie kompresuje ich. W takim przypadku nie opłaca się zamieniać liczb dziesiętnych na szesnastkowe.

Generalnie kompresja robiona w praktyce, znaczy to co robi zip, rar, itp. i tak nie polega na kodowaniu jakiejś tam entropii, co realizuje autor tego tematu.

Bo w praktyce tak to działa:
mamy dane np. w postaci tekstu:
'krowa idzie do rowa, ale nie o tym mowa'

i teraz taki program zip sprawdza ciągi, i wykrywa m.in.: owa - 3 sztuki,
no więc on to zakoduje na 1 bajcie (w praktyce na 2) po prostu, co możemy zapisać tak:

'kr1 idzie do r1, ale nie o tym m1'

'1' będzie w słowniku zapisane jako 'owa', co będzie potem rozwijane podczas dekompresji.

No, a samo to kodowanie 'entropii' jest niewiele warte w praktyce, bo daje to kilka procentów zaledwie dla tekstu;
zysk jest duży dla obrazów typu bmp, bo tam są zwykle same zera, albo 255, itp.

np. obrazek w stylu: O
co ma rozmiar 20x20 powiedzmy,
i tam jest z 30 pikseli o wartości: 0 = czerń (to kółeczko), a reszta to 255=biel - z 370 sztuk.

0

Przy okazji mam taki prosty problem dla autora, pewnie spotkał się z tym już nie raz:

mam gotowy obraz, taki zwyczajny np. w postaci fotki z aparatu, albo z teleskopu Hubble'a.
I niech ten obraz zajmuje z 10 MB, skompresowany w jpg.

Teraz biorę ten obrazek do paintshopa i robię sobie rozmycie - wygładzenie, za pomocą filtru gaussa.
Zapisuję to, z powrotem do jpg, i co się stanie? Otrzymuję z 20 MB!

Gdzie tu jest ta informacja - entropia?
Przecież wszelkie szumy - zwłaszcza rozmycie gaussa, redukują informację, a nie zwiększają!
No więc rozmiar pliku powinien się zmniejszać a nie zwiększać!

0

No, a samo to kodowanie 'entropii' jest niewiele warte w praktyce, bo daje to kilka procentów zaledwie dla tekstu;

Więcej niż kilka %. Wystarczy spojrzeć na: http://mattmahoney.net/dc/text.html#5586 Każdy koder z tej listy oprócz fpaq0f i fpaq0f2 traktuje wejściowe znaki jako niezależne, tzn nie analizuje sekwencji znaków. Zamiast tego jest tylko i wyłącznie rozkład prawdopodobieństwa symbolów w alfabecie. Dla przykładu:

  • enwik8 = 100 000 000 bajtów nieskompresowane
  • wynik fpaq0 = 63 391 013 - ten koder kompresuje bajt po bajcie
  • wynik fpaq0p = 61 457 810 - ten koder kompresuje bit po bicie ale kontekstem dla każdego bitu są poprzednie bity z danego bajtu

Jak widać koder kompresujący bit po bicie osiągnął większą kompresję niż koder kompresujący bajt po bajcie. Można by powiedzieć, że to wbrew intuicjom @hurgadion

I niech ten obraz zajmuje z 10 MB, skompresowany w jpg.
Teraz biorę ten obrazek do paintshopa i robię sobie rozmycie - wygładzenie, za pomocą filtru gaussa.
Zapisuję to, z powrotem do jpg, i co się stanie? Otrzymuję z 20 MB!

Nie musisz rozmywać. Wystarczy załadować JPG i zapisać go z wyższymi ustawieniami jakości. O ile program nie pokusi się o odgadnięcie oryginalnego algorytmu kompresji to nie przywróci oryginalnego JPGa, tylko będzie kompresował od nowa.

Typowy algorytm kompresji stratnej zwykle składa się z transformat, kwantyzacji i na samym końcu prostej kompresji bezstratnej typu algorytm Huffmana czy kodowanie arytmetyczne. W przypadku JPG najpierw mamy transformatę przestrzeni kolorów RGB -> YCbCr, potem transformatę DCT (discrete cosine transform) na blokach pikseli 8x8, potem kwantyzację (czyli zwykłe dzielenie całkowitoliczbowe bez reszty), a na końcu Huffman. Skwantyzowane liczby koduje się częściowo Huffmanem, a częściowo bity przekazuje się wprost. Dokładniej to Huffmanem kompresuje się znaczniki długości liczb i ich najwyższe bity, a niższe bity lecą na wyjście bez kompresji (bo i tak zwykle są niekompresowalne). Mniejsze dzielniki na etapie kwantyzacji = wyższa jakość pliku wynikowego, tzn wyjście bardziej przypomina wejście. Jeśli jednak na wejściu już jest obrazek niskiej jakości to jakość się nie zwiększy, a współczynniki uzyskane po etapie kwantyzacji i tak będą większe niż w oryginale. Większe współczynniki przekładają się wprost na większy rozmiar wyjściowy, bo najniższe ich bity nie są kompresowane.

Ogólnie rozmiar pliku JPG ma niewiele wspólnego z entropią, bo JPG jest kompresją stratną. W kompresji stratnej najważniejsze jest by człowiekowi podobał się efekt końcowy, tzn by nie widział zbyt wielu przekłamań w JPG, czy nie słyszał zbyt wielu przekłamań w MP3.

0

Generalnie kompresja robiona w praktyce, znaczy to co robi zip, rar, itp. i tak nie polega na kodowaniu jakiejś tam entropii, co realizuje autor tego tematu.

Rar i zip używają Lempel-Ziv ( https://en.wikipedia.org/wiki/LZ77_and_LZ78 ) oraz Huffmana - obecnie są zastępowane Facebook Zstandard (np. w Linux) używającego ANS:
https://en.wikipedia.org/wiki/Zstandard

0

Ogólnie rozmiar pliku JPG ma niewiele wspólnego z entropią, bo JPG jest kompresją stratną. W kompresji stratnej najważniejsze jest by człowiekowi podobał się efekt końcowy, tzn by nie widział zbyt wielu przekłamań w JPG, czy nie słyszał zbyt wielu przekłamań w MP3.

Możesz sobie jakość ustawić na max, i porównać rozmiary - przed i po wygładzeniu.

Albo skompresuje sobie bezstratnie, np. do gif, albo png, czy nawet algorytmem z tego tematu.

Rozmiar wzrośnie!

0
elenorf napisał(a):

Generalnie kompresja robiona w praktyce, znaczy to co robi zip, rar, itp. i tak nie polega na kodowaniu jakiejś tam entropii, co realizuje autor tego tematu.

Rar i zip używają Lempel-Ziv ( https://en.wikipedia.org/wiki/LZ77_and_LZ78 ) oraz Huffmana - obecnie są zastępowane Facebook Zstandard (np. w Linux) używającego ANS:
https://en.wikipedia.org/wiki/Zstandard

Na finalnym etapie tylko, co nie ma większego wpływu na wynik.

Podobnie jpg: gdyby tam od razu kompresować to Huffmanem, czy arytm, wyniki byłby żałosne.
Cały zysk wynika tam z tych transformacji cosinusowych - dct!

0

Rozmiar wzrośnie!

Niczego to nie dowodzi i niespecjalnie jest to skorelowane z entropią. Doszukiwanie się entropii w rozmiarze JPGa jest absurdalne.

0
Wibowit napisał(a):

Rozmiar wzrośnie!

Niczego to nie dowodzi i niespecjalnie jest to skorelowane z entropią. Doszukiwanie się entropii w rozmiarze JPGa jest absurdalne.

Niby dlaczego?

Czysto losowy ciąg danych w ogóle nie da się skompresować - zgadza się? (możesz zapytać autora - on w tym pracuje)

Zatem co to jest - ile informacji zawierza czysty szum losowy?
Nic zupełnie, a może to jest full - max? :)

0

W uproszczeniu - jeśli coś się da skompresować to nie jest całkowicie losowe. Precyzyjniej:
http://mattmahoney.net/dc/dce.html#Section_11

In fact, the vast majority of strings cannot be compressed by very much. The fraction of strings that can be compressed from n bits to m bits is at most 2m - n. For example, less than 0.4% of strings can be compressed by one byte.

0
Wibowit napisał(a):

W uproszczeniu - jeśli coś się da skompresować to nie jest całkowicie losowe. Precyzyjniej:
http://mattmahoney.net/dc/dce.html#Section_11

In fact, the vast majority of strings cannot be compressed by very much. The fraction of strings that can be compressed from n bits to m bits is at most 2m - n. For example, less than 0.4% of strings can be compressed by one byte.

Moje pytanie jest aktualne: co się dzieje z obrazem po zastosowaniu wygładzania: wzrasta, czy maleje entropia?

1

@exp6 wygładzanie, czy właściwie filtracja dolnoprzepustowa, będzie Ci usuwać wyższe częstotliwości. Rzecz w tym, że filtr to nie jest magiczne pudełko, które usuwa Ci to co chcesz ,ale niestety także wprowadza do odpowiedzi, swoją charakterystykę. Obrazowo mówiąc, jeśli na obrazie masz ostre krawędzie, silne kontrasty, to są to wymuszenia skokowe. One wchodzą na wejście filtru, który na nie odpowiada swoją odpowiedzią skokową "dodając" do obrazu swoje częstotliwości (zazwyczaj jest to tłumiona "sinusoida" o częstotliwości własnej filtru). Więc objętość obrazu kompresowanego jpeg będzie albo rosła lub malała w zależności od tego jaki to obraz. Jeśli obraz nie zawiera płaskich, jednokolorowych lub rozległych, rozmytych gradientów, ale jest dynamiczny, zawiera dużo wysokich częstotliwości, to po filtracji jego objętość będzie mniejsza. Jeśli obraz to np. obraz z teleskopu, w którym dominuje jednokolorowe tło z kontrastowymi plamkami, liniami, to po wygładzeniu obraz w jpeg będzie miał większą objętość. Wszystko zależy od częstotliwości filtru i jakie częstotliwości dominują w obrazie.

Z tego wniosek, że nie da się jednoznacznie odpowiedzieć, czy rozmycie zwiększa czy zmniejsza entropię. Raz będzie zmniejszać, gdy w obrazie filtr usunie szum, który zwiększa entropię, innym razem będzie zwiększać, jeśli częstotliwość filtru jest zbyt wysoka w stosunku do obrazu zawierającego choćby jeden kontrast, i pojawią się składowe filtru, które zdominują znaczące składowe obrazu.

0
cs napisał(a):

@exp6 wygładzanie, czy właściwie filtracja dolnoprzepustowa, będzie Ci usuwać wyższe częstotliwości. Rzecz w tym, że filtr to nie jest magiczne pudełko, które usuwa Ci to co chcesz ,ale niestety także wprowadza do odpowiedzi, swoją charakterystykę. Obrazowo mówiąc, jeśli na obrazie masz ostre krawędzie, silne kontrasty, to są to wymuszenia skokowe. One wchodzą na wejście filtru, który na nie odpowiada swoją odpowiedzią skokową "dodając" do obrazu swoje częstotliwości (zazwyczaj jest to tłumiona "sinusoida" o częstotliwości własnej filtru). Więc objętość obrazu kompresowanego jpeg będzie albo rosła lub malała w zależności od tego jaki to obraz. Jeśli obraz nie zawiera płaskich, jednokolorowych lub rozległych, rozmytych gradientów, ale jest dynamiczny, zawiera dużo wysokich częstotliwości, to po filtracji jego objętość będzie mniejsza. Jeśli obraz to np. obraz z teleskopu, w którym dominuje jednokolorowe tło z kontrastowymi plamkami, liniami, to po wygładzeniu obraz w jpeg będzie miał większą objętość. Wszystko zależy od częstotliwości filtru i jakie częstotliwości dominują w obrazie.

Z tego wniosek, że nie da się jednoznacznie odpowiedzieć, czy rozmycie zwiększa czy zmniejsza entropię. Raz będzie zmniejszać, gdy w obrazie filtr usunie szum, który zwiększa entropię, innym razem będzie zwiększać, jeśli częstotliwość filtru jest zbyt wysoka w stosunku do obrazu zawierającego choćby jeden kontrast, i pojawią się składowe filtru, które zdominują znaczące składowe obrazu.

Naprawdę? No to pokaż przykład obrazu, którego rozmiar (skompresowany) zmaleje po wygładzeniu.

Prawda jest tu raczej prozaiczna:
gdyby to wygładzanie byłoby możliwe do wycofania - za pomocą operacji odwrotnej -, wówczas ta entropia byłaby tu również zachowana!

Zatem mamy nowe pytanie: można cofnąć wygładzanie?

Pewnie że można, bo sam kiedyś z tym eksperymentowałem - operacje rozplotu, odejmowanie szumu, i inne tego typu sprawy.

W praktyce pełne wyczyszczenie 'szumów' jest jednak niemożliwe,
co nawet matematycznie łatwo uzasadnić:
najprostsza metoda wygładzania to macierz typu:
1 2 1
2 4 2
1 2 1

wyznacznik z tego wynosi: 4 + 4 + 4 - 4 -4 -4 = 0, czyli nie ma macierzy odwrotnej!

Niemniej można zrobić tu i tak dowolnie bliską odwrotnej, tylko że to wtedy strasznie dużo kosztuje,
bo taka prawie odwrotna macierz ma tu rozmiary: 100 x 100, a nie 3 x 3 zaledwie!

0

Do wyostrzania są pewne filtry nawet nieźle działające np:
https://www.cs.tut.fi/~foi/SA-DCT/results.html#ref_deblur
http://www.mdpi.com/1424-8220/17/1/174

Naprawdę? No to pokaż przykład obrazu, którego rozmiar (skompresowany) zmaleje po wygładzeniu.

Weźmy pierwszy z brzegu PNG (rozmiar 476195 bajtów):
image_Lena512rgb.png

Zapisany do formatu JPG przez GIMPa w ustawieniach: jakość = 90, podpróbkowanie = 40 (rozmiar 64562 bajty)
image_Lena512rgb.jpg

Zapisany jak wyżej ale z lekkim rozmazaniem (rozmiar 48437 bajtów):
image_Lena512rgb_blur.jpg

Spróbowałem jeszcze z formatem PNG i mocnym rozmazaniem (rozmiar 237399 bajtów):
image_Lena512rgb_blur5.png

Jak widać rozmazywanie zmniejsza rozmiar zarówno JPGa jak i PNG. Im silniejsze rozmazywanie tym mniejszy wynikowy rozmiar.

0

Jak widać rozmazywanie zmniejsza rozmiar zarówno JPGa jak i PNG. Im silniejsze rozmazywanie tym mniejszy wynikowy rozmiar.

Bez przesady - w tym przypadku tak tylko wyszło, bo ten obraz jest jakiś taki... zeszmacony - blady, kolory fałszywe, itd. czyli nierealistyczny;
formalnie: nie ma w nim zbyt dużo informacji, bo została już wcześniej zniszczona.

W 99.9% pozostałych przypadków rozmiar wrośnie. :)

0

Super kompresja?

Gdyby rozmiar malał istotnie podczas wygładzania obrazu, wówczas można zrobić prostą metodę, która pozwalałaby zwiększać kompresję:

  1. wygładzamy przed kompresją - i zyskujemy np. 50%, co zapisujemy i plus etykieta, informująca o operacji rozmycia
  2. podczas dekompresji: rozwijamy obraz, a potem go wyostrzamy - zgodnie z etykietą informującą o rozmyciu przed kompresją.
1

Polecam przetestować tę swoją metodę na super kompresję i porównać ze zwykłym JPGiem. Ciągle opowiadasz jakieś brednie, ale w taki sposób, że laik się nie połapie.

PS:
podaj obraz który będzie ważył więcej jeśli rozmyje się go przed zapisem do JPG.

0

To roszę i sprawdź sam pobierz (obraz rzeczywisty i niezeszmacony). Zastosuj rozmycie najpierw dla całego obrazu, a potem skadruj obrazek tak, aby był widoczny tylko kwiat, zapisz i ponownie rozmyj. Dostaniesz dwa różne efekty, dla całego obrazka rozmycie zwiększy objętość, a dla skadrowanego rozmycie zmniejszy objętość.

Zatem mamy nowe pytanie: można cofnąć wygładzanie?

To się nazywa odtwarzanie szeroko pojętych sygnałów w tym 2D czyli obrazów, no chyba, że chodzi Ci o Undo w Photoshopie ;-)

W praktyce pełne wyczyszczenie 'szumów' jest jednak niemożliwe,

Nawet w teorii nie jest to możliwe, o ile mi wiadomo

najprostsza metoda wygładzania to macierz typu:
1 2 1
2 4 2
1 2 1
wyznacznik z tego wynosi: 4 + 4 + 4 - 4 -4 -4 = 0, czyli nie ma macierzy odwrotnej!

Chcesz odtwarzać, znaczy rozplatać obrazy w dziedzinie przestrzennej?! Rozplatanie rzeczywistych obrazów możliwe jest tylko w dziedzinie częstotliwościowej.

W 99.9% pozostałych przypadków rozmiar wrośnie. :)

W 99,9% przypadków z każdego obrazka można wybrać taki fragment, który temu zaprzeczy ;-)

Bez przesady - w tym przypadku tak tylko wyszło, bo ten obraz jest jakiś taki... zeszmacony - blady, kolory fałszywe, itd. czyli nierealistyczny;
formalnie: nie ma w nim zbyt dużo informacji, bo została już wcześniej zniszczona.

Co do ilości informacji, to owszem, ale jej większość nie jest zniszczona co raczenie niewidoczna ;-)

0 użytkowników online, w tym zalogowanych: 0, gości: 0