Na podstawie bardzo udanego wyzwania kodowania obrazów na Twitterze w Stack Overflow.
Jeśli obraz jest wart 1000 słów, ile obrazu można zmieścić w 114,97 bajtach?
Rzucam ci wyzwanie, abyś zaproponował metodę ogólnego zastosowania do kompresji obrazów w standardowy komentarz na Twitterze, który zawiera tylko tekst ASCII do wydrukowania .
Zasady:
- Musisz napisać program, który może zrobić zdjęcie i wyprowadzić zakodowany tekst.
- Tekst utworzony przez program musi mieć maksymalnie 140 znaków i może zawierać tylko znaki, których punkty kodowe mieszczą się w zakresie od 32 do 126 włącznie.
- Musisz napisać program (prawdopodobnie ten sam program), który może pobrać zakodowany tekst i wydrukować zdekodowaną wersję zdjęcia.
- Twój program może korzystać z zewnętrznych bibliotek i plików, ale nie może wymagać połączenia z Internetem ani połączenia z innymi komputerami.
- Proces dekodowania nie może w żaden sposób uzyskać dostępu ani zawierać oryginalnych obrazów.
- Twój program musi akceptować obrazy w co najmniej jednym z tych formatów (niekoniecznie więcej): Bitmapa, JPEG, GIF, TIFF, PNG. Jeśli niektóre lub wszystkie przykładowe obrazy nie mają prawidłowego formatu, możesz je przekonwertować przed kompresją w programie.
Oceniając:
Jest to dość subiektywne wyzwanie, więc zwycięzca zostanie (ostatecznie) oceniony przeze mnie. Skoncentruję swoją ocenę na kilku ważnych czynnikach, wymienionych poniżej w malejącym znaczeniu:
- Zdolność do wykonania rozsądnej pracy polegającej na kompresji szerokiej gamy obrazów, w tym obrazów niewymienionych jako przykładowe
- Zdolność do zachowania konturów głównych elementów obrazu
- Możliwość kompresji kolorów głównych elementów obrazu
- Możliwość zachowania konturów i kolorów drobnych szczegółów na obrazie
- Czas kompresji. Chociaż nie tak ważne, jak dobrze obraz jest skompresowany, szybsze programy są lepsze niż wolniejsze programy, które robią to samo.
Twoje zgłoszenie powinno zawierać powstałe obrazy po dekompresji, wraz z wygenerowanym komentarzem na Twitterze. Jeśli to możliwe, możesz również podać link do kodu źródłowego.
Odpowiedzi:
Udoskonaliłem moją metodę, dodając rzeczywistą kompresję. Teraz działa iteracyjnie, wykonując następujące czynności:
Zmniejsz rozmiar obrazu zachowując proporcje (jeśli obraz jest kolorowy, próbkowanie barwy odbywa się w 1/3 szerokości i wysokości luminancji)
Zmniejsz głębokość bitów do 4 bitów na próbkę
Zastosuj prognozę mediany do obrazu, dzięki czemu rozkład próbki będzie bardziej jednolity
Zastosuj kompresję zakresu adaptacyjnego do obrazu.
Sprawdź, czy rozmiar skompresowanego obrazu wynosi <= 112
Największy obraz, który mieści się w 112 bajtach, jest następnie używany jako obraz końcowy, a pozostałe dwa bajty służą do przechowywania szerokości i wysokości skompresowanego obrazu, plus flaga wskazująca, czy obraz jest kolorowy. W przypadku dekodowania proces jest odwracany, a obraz skalowany w górę, aby mniejszy wymiar wynosił 128.
Jest trochę miejsca na ulepszenia, mianowicie nie wszystkie dostępne bajty są zwykle używane, ale wydaje mi się, że jestem na etapie znacznie zmniejszających się zwrotów za próbkowanie w dół + kompresję bezstratną.
Szybkie i brudne źródło C ++
Exe systemu Windows
Mona Lisa (luminancja 13x20, barwa 4x6)
Hindenburg (luminancja 21x13)
Góry (luminancja 19x14, barwa 6x4)
Kształty 2D (luminancja 21x15, barwa 7x5)
źródło
Iść
Działa poprzez rekurencyjne dzielenie obrazu na regiony. Staram się dzielić regiony z dużą zawartością informacji i wybieram linię podziału, aby zmaksymalizować różnicę kolorów między dwoma regionami.
Każdy podział jest kodowany za pomocą kilku bitów do kodowania linii podziału. Każdy region liścia jest kodowany jako jeden kolor.
Zdjęcie Hindenburga wygląda dość kiepsko, ale inne lubię.
źródło
Pyton
Kodowanie wymaga numpy , SciPy i scikit-image .
Dekodowanie wymaga tylko PIL .
Jest to metoda oparta na interpolacji superpikseli. Na początek każdy obraz jest podzielony na 70 podobnej wielkości regionów o podobnym kolorze. Na przykład obraz krajobrazu jest podzielony w następujący sposób:
Środek ciężkości każdego regionu znajduje się (do najbliższego punktu rastrowego na siatce zawierającej nie więcej niż 402 punkty), a także jego średni kolor (z palety 216 kolorów), a każdy z tych regionów jest zakodowany jako liczba od 0 do 86832 , który można zapisać w postaci 2,5 znaków ascii do wydrukowania (w rzeczywistości 2,497 , pozostawiając wystarczająco dużo miejsca do zakodowania dla bitu w skali szarości).
Jeśli jesteś uważny, być może zauważyłeś, że 140 / 2,5 = 56 regionów, a nie 70, jak powiedziałem wcześniej. Zauważ jednak, że każdy z tych regionów jest unikalnym, porównywalnym obiektem, który może być wymieniony w dowolnej kolejności. Z tego powodu możemy użyć permutacji pierwszych 56 regionów, aby zakodować pozostałe 14 , a także mieć kilka bitów pozostałych do przechowywania współczynnika kształtu.
Mówiąc dokładniej, każdy z dodatkowych 14 regionów jest przekształcany na liczbę, a następnie każda z tych liczb jest łączona razem (mnożąc bieżącą wartość przez 86832 i dodając następny). Ta (gigantyczna) liczba jest następnie przekształcana w permutację na 56 obiektach.
Na przykład:
wyświetli:
Otrzymana permutacja jest następnie stosowana do oryginalnych 56 regionów. Pierwotny numer (a zatem dodatkowe 14 regionów) można również wyodrębnić, przekształcając permutację 56 zakodowanych regionów w jego reprezentację liczbową.
Gdy
--greyscale
opcja jest używana z koderem, zamiast tego używane są 94 regiony (oddzielone 70 , 24 ), z 558 punktami rastrowymi i 16 odcieniami szarości.Podczas dekodowania każdy z tych obszarów jest traktowany jako stożek 3D rozciągnięty do nieskończoności, którego wierzchołek znajduje się w środku ciężkości regionu, patrząc od góry (aka diagram Voronoi). Obramowania są następnie mieszane, aby utworzyć produkt końcowy.
Przyszłe ulepszenia
Wymiary Mona Lisa są nieco inne, ze względu na sposób przechowywania proporcji. Będę musiał użyć innego systemu.Naprawiono, zakładając, że oryginalny współczynnik kształtu mieści się w przedziale od 1:21 do 21: 1, co uważam za rozsądne założenie.Hindenburg można znacznie poprawić. Paleta kolorów, której używam, ma tylko 6 odcieni szarości. Gdybym wprowadził tryb tylko w skali szarości, mógłbym użyć dodatkowych informacji, aby zwiększyć głębię kolorów, liczbę regionów, liczbę punktów rastrowych lub dowolną kombinację tych trzech.Dodałem--greyscale
opcję do enkodera, która wykonuje wszystkie trzy.Kształty 2d prawdopodobnie wyglądałyby lepiej przy wyłączonym mieszaniu. Prawdopodobnie dodam do tego flagę.Dodano opcję enkodera do kontroli współczynnika segmentacji oraz opcję dekodera, aby wyłączyć mieszanie.i
Drugi kodowany z
--greyscale
opcją.Zakodowane z
--greyscale
opcją.Kodowane
--ratio 60
i dekodowane z--no-blending
opcjami.encoder.py
decoder.py
my_geom.py
źródło
PHP
OK, zajęło mi to trochę czasu, ale oto jest. Wszystkie obrazy w skali szarości. Kolory zajęły zbyt wiele bitów do zakodowania dla mojej metody: P
Ciąg Mona Lisa
47 kolorów Monochrome
101 bajtów.
Kształty 2D
36 kolorów Monochromatyczny Ciąg
105 bajtów.
Hindenburg
62 kolory Monochromatyczny
112 znaków.
Góry
63 kolory Monochromatyczne
122 znaki.
Moja metoda
Koduję mój strumień bitów przy użyciu rodzaju kodowania base64. Zanim zostanie zakodowany w czytelnym tekście, oto co się stanie.
Ładuję obraz źródłowy i zmieniam jego rozmiar do maksymalnej wysokości lub szerokości (w zależności od orientacji, pionowej / poziomej) wynoszącej 20 pikseli.
Następnie ponownie koloruję każdy piksel nowego obrazu do jego najbliższego dopasowania na palecie 6 kolorów w skali szarości.
Po tym utworzę ciąg z każdym kolorem piksela reprezentowanym przez litery [AF].
Następnie obliczam rozkład 6 różnych liter w ciągu i wybieram najbardziej zoptymalizowane drzewo binarne do kodowania na podstawie częstotliwości liter. Istnieje 15 możliwych drzew binarnych.
Strumień bitów zaczynam od jednego bitu, w
[1|0]
zależności od tego, czy obraz jest wysoki czy szeroki. Następnie używam 4 kolejnych bitów w strumieniu, aby poinformować dekoder, którego drzewa binarnego należy użyć do zdekodowania obrazu.Poniżej znajduje się strumień bitów reprezentujących obraz. Każdy piksel i jego kolor są reprezentowane przez 2 lub 3 bity. To pozwala mi przechowywać informacje o wartości od 2 do 3 pikseli dla każdej drukowanej postaci ascii. Oto próbka drzewa binarnego
1110
, z którego korzysta Mona Lisa:Litery E
00
i F10
są najczęstszymi kolorami w Mona Lisa. A010
, B011
, C110
i D111
są najmniej częste.Drzewa binarne działają w następujący sposób: przechodzenie z jednego kawałka na drugi
0
oznacza przejście w lewo,1
oznacza przejście w prawo. Idź dalej, dopóki nie trafisz w liść na drzewo lub ślepy zaułek. Liść, na którym kończysz, to postać, którą chcesz.W każdym razie koduję binarne żądło na znaki base64. Podczas dekodowania łańcucha proces odbywa się w odwrotnej kolejności, przypisując wszystkie piksele do odpowiedniego koloru, a następnie obraz jest skalowany dwukrotnie w stosunku do zakodowanego rozmiaru (maksymalnie 40 pikseli X lub Y, w zależności od tego, który jest większy), a następnie matryca splotowa jest zastosowane do całości, aby wygładzić kolory.
Tak czy inaczej, oto obecny kod: „ link do pastebin ”
To brzydkie, ale jeśli widzisz miejsce na ulepszenia, daj mi znać. Zhakowałem go razem, jak chcę. Dowiedziałem WIELE Z tym wyzwaniem. Dziękujemy OP za opublikowanie go!
źródło
Moja pierwsza próba. To daje pole do poprawy. Myślę, że sam format faktycznie działa, problem tkwi w koderze. I brakuje mi pojedynczych bitów z mojego wyjścia ... mój (nieco wyższej jakości niż tutaj) plik skończył się na 144 znakach, kiedy powinno być trochę. (i naprawdę żałuję, że nie było - zauważalne są różnice między nimi a tymi). Nauczyłem się jednak, nigdy nie przeceniaj, jak duże jest 140 znaków ...
Sprowadzam to do zmodyfikowanej wersji palety RISC-OS - w zasadzie, ponieważ potrzebowałem palety 32 kolorów, i wydawało się, że to wystarczająco dobre miejsce do rozpoczęcia. Myślę, że przydałoby się to też trochę zmienić.
Rozbijam go na następujące kształty: i dzielę obraz na bloki palety (w tym przypadku 2x2 piksele) koloru przedniego i tylnego.
Wyniki:
Poniżej znajdują się tweety, oryginały i sposób ich dekodowania
Wiem, że kolory są niewłaściwe, ale tak naprawdę podoba mi się Monalisa. Jeśli usunę rozmycie (co nie byłoby zbyt trudne), jest to rozsądne kubistyczne wrażenie: str
Muszę popracować
Dam później trochę pracy, aby spróbować je naprawić i ulepszyłem koder. Te dodatkowe 20 lub więcej postaci stanowią ogromną różnicę. Chciałbym je z powrotem.
Źródło i paleta kolorów C # znajdują się na https://dl.dropboxusercontent.com/u/46145976/Base96.zip - chociaż z perspektywy czasu może nie działać idealnie, gdy są uruchamiane osobno (ponieważ spacje w argumentach programów nie idą tak dobrze).
Enkoder zajmuje mniej niż kilka sekund na mojej dość przeciętnej maszynie.
źródło
Zrezygnowałem z prób utrzymania koloru i zrobiłem się czarno-biały, ponieważ wszystko, czego próbowałem z kolorem, było nierozpoznawalne.
Zasadniczo dzieli tylko piksele na 3 w przybliżeniu równe części: czarny, szary i biały. Nie zachowuje również rozmiaru.
Hindenburg
Mona Lisa
Góry
Kształty
Oto program.
python compress.py -c img.png
kompresujeimg.png
i drukuje tweet.python compress.py -d img.png
pobiera tweet ze standardowego wejścia i zapisuje obraz w folderzeimg.png
.źródło
Mój skromny wkład w R:
Pomysł polega po prostu na zmniejszeniu rastra (plik musi być w png) do macierzy, której liczba komórek jest mniejsza niż 140, tweety to seria kolorów (w 64 kolorach) poprzedzona dwoma znakami wskazującymi liczbę wierszy i kolumny rastra.
źródło
Nie jest to kompletne rozwiązanie, wystarczy wprowadzić tę metodę. (Matlab)
Użyłem 16 palety kolorów i 40 pozycji, aby stworzyć ważony diagram voronoi . Zastosowano algorytm genetyczny i prosty algorytm wspinaczki, aby dopasować obraz.
Album z oryginalnym obrazem, a także mam 16-bajtową wersję z 4 kolorami i ustalonymi pozycjami. :)
(Czy mogę tutaj zmienić rozmiar obrazu?)
źródło
DO#
Aktualizacja - wersja 2
Podjąłem kolejną próbę, teraz używając MagickImage.NET ( https://magick.codeplex.com/ ) do kodowania danych JPEG, napisałem również podstawowy kod do lepszego przetwarzania danych nagłówka JPEG (jak sugerował primo), ja również użyłem GuassianBlur na wyjściu, co pomaga złagodzić część kompresji JPEG. Ponieważ nowa wersja działa lepiej, zaktualizowałem swój post, aby odzwierciedlić nową metodę.
metoda
Próbowałem czegoś wyjątkowego (mam nadzieję), zamiast próbować manipulować głębią kolorów lub identyfikacją krawędzi, lub próbować samodzielnie użyć innych sposobów zmniejszenia rozmiaru obrazu. Użyłem algorytmu JPEG przy maksymalnej kompresji w zmniejszonych wersjach zdjęcia, a następnie eliminując wszystko oprócz „StartOfScan” ( http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure ) i kilku kluczowych elementów nagłówka, jestem w stanie sprowadzić rozmiar do dopuszczalnej wielkości. Wyniki są naprawdę imponujące dla 140 znaków, daje mi nowy szacunek dla plików JPEG:
Hindenburg
Góry
Mona Lisa
Kształty
Kod
Wersja 2 - http://pastebin.com/Tgr8XZUQ
Naprawdę zaczynam tęsknić za ReSharper +. Mam wiele rzeczy do poprawienia, wciąż mam tu sporo twardego kodowania, choć interesuje mnie bałagan (pamiętaj, że potrzebujesz dll MagickImage, aby uruchomić to w VS)
Oryginał (przestarzałe) - http://pastebin.com/BDPT0BKT
Nadal trochę bałaganu.
źródło
Python 3
metoda
To, co program najpierw robi, to zmniejszenie obrazu, znacznie zmniejszając jego rozmiar.
Po drugie, konwertuje wartości rgb na binarne i odcina ostatnie kilka cyfr.
Następnie konwertuje dane bazy 2 na bazę 10, gdzie dodaje wymiary obrazu.
Następnie konwertuje dane z bazy 10 na bazę 95, używając wszystkich ascii, jakie udało mi się znaleźć. Nie mogłem jednak użyć / x01 i tym podobnych z powodu jego zdolności do zanegowania funkcji, która zapisała plik tekstowy.
I (dla dodatkowej niejednoznaczności) funkcja dekodowania robi to w odwrotnej kolejności.
compress.py
decode.py
Krzyk
Mona Lisa
Kule
źródło