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

Odpowiedz Nowy wątek
2016-11-26 12:24
4

Chyba wszyscy informatycy słyszeli o kodowaniu Huffmana - jest ono szybkie ale niedokładne (przybliża prawdopodobieństwa potęgami 1/2), lepszy stopień kompresji daje kodowanie arytmetyczne, tyle że jest znacznie bardziej kosztowne obliczeniowo (potrzebuje mnożenia).
Okazuje się że od 2014 nowe kompresory są oparte już na innym kodowaniu (ANS), które pochodzi z Uniwersytetu Jagiellońskiego - jest ono dokładne i tanie obliczeniowo (nie potrzebuje mnożenia):
Wikipedia: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
wiadomość z UJ: http://www.uj.edu.pl/wiadomos[...]_d82lKZvhit4m/10172/134381865
materiały: http://encode.ru/threads/2078[...]meral-Systems-implementations

Przykładowo obecnie domyślny kompresor Apple (LZFSE), czy open-source kompresor z Facebook (Zstandard), który ma aspiracje do wyparcia standardowego gzip/zlib (zip-y) jako że jest kilkukrotnie szybszy i pozwala na znacznie lepszą kompresję:
https://github.com/facebook/zstd
user image

tytuł jest dość niefortunny, dopisz tam "pochodzące" żeby to można było od razu dobrze zrozumieć - Wibowit 2016-11-26 12:33
a i możesz dodać obrazek jako załącznik - wtedy nie zniknie nawet gdy dropbox go usunie - Wibowit 2016-11-26 12:40

Pozostało 580 znaków

2018-09-07 23:10
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2018-09-08 00:32
exp6
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?

Pozostało 580 znaków

2018-09-13 09:23
cs
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.

Pozostało 580 znaków

2018-09-17 20:19
exp6
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!

Pozostało 580 znaków

2018-09-17 20:51
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 = 4:2:0 (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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2018-09-17 20:52

Pozostało 580 znaków

2018-09-17 21:13
exp6
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. :)

Pozostało 580 znaków

2018-09-17 21:22
exp6
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ą.

Pozostało 580 znaków

2018-09-17 21:25
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2018-09-17 21:26

Pozostało 580 znaków

2018-09-17 21:27
cs
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 ;-)

Pozostało 580 znaków

2018-09-17 21:27
0

Na tym obrazie poniżej widać że nie można przesadzać z kompresją - utrata obrazu w pewnym momencie stanie się zbyt zauważalna.


Szacuje się, że w Polsce brakuje 50 tys. programistów

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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

Robot: Googlebot, Xenu Link Sleuth (3x)