Jeśli zdjęcie ma 1000 słów, ile można zmieścić w 140 znakach?
Uwaga : To wszystko ludzie! Termin nagrody jest już za nami i po trudnych naradach zdecydowałem, że wpis Boojuma ledwo wykoleił się przed Samem Hocevarem . Opublikuję bardziej szczegółowe notatki, gdy będę miał okazję je napisać. Oczywiście wszyscy powinni swobodnie przesyłać rozwiązania i ulepszać rozwiązania umożliwiające głosowanie. Dziękujemy wszystkim, którzy przesłali i zgłosili; Podobało mi się wszystkie. To była dla mnie świetna zabawa i mam nadzieję, że zarówno uczestnicy, jak i widzowie byli zadowoleni.
Natknąłem się na ten interesujący post o próbie kompresji obrazów w komentarz na Twitterze, a wiele osób w tym wątku (i wątku na Reddit ) miało sugestie dotyczące różnych sposobów, w jaki możesz to zrobić. Myślę więc, że byłoby to dobre wyzwanie w kodowaniu; pozwól ludziom wkładać pieniądze tam, gdzie są ich usta, i pokaż, w jaki sposób ich pomysły na temat kodowania mogą prowadzić do uszczegółowienia na ograniczonej przestrzeni, którą masz do dyspozycji.
Rzucam ci wyzwanie, abyś opracował system ogólnego przeznaczenia do kodowania obrazów w 140 znakowych wiadomościach na Twitterze i dekodowania ich ponownie w obraz. Możesz używać znaków Unicode, aby uzyskać więcej niż 8 bitów na znak. Jednak nawet uwzględniając znaki Unicode, będziesz musiał skompresować obrazy do bardzo małej ilości miejsca; będzie to z pewnością kompresja stratna, dlatego trzeba będzie subiektywnie oceniać, jak dobrze każdy wynik wygląda.
Oto wynik, który oryginalny autor Quasimondo uzyskał ze swojego kodowania (zdjęcie jest licencjonowane na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne ):
Czy potrafisz lepiej?
Zasady
- Twój program musi mieć dwa tryby: kodowania i dekodowania .
- Podczas kodowania :
- Twój program musi przyjąć jako dane wejściowe grafikę w dowolnym rozsądnym wybranym formacie graficznym rastrowym . Powiemy, że każdy format rastrowy obsługiwany przez ImageMagick liczy się jako rozsądny.
- Twój program musi wyświetlić komunikat, który może być reprezentowany w 140 lub mniej punktach kodu Unicode; 140 punktów kodu w zakresie
U+0000
-U+10FFFF
, Z wyłączeniem znaków (U+FFFE
,U+FFFF
,U+
nFFFE
,U+
nFFFF
, gdzie n jest1
-10
szesnastkowym, a zakresU+FDD0
-U+FDEF
) i zastępcze punkty kodowe (U+D800
-U+DFFF
). Może być wyprowadzany w dowolnym rozsądnym wybranym kodowaniu; każde kodowanie obsługiwane przez GNUiconv
zostanie uznane za rozsądne, a kodowanie natywne platformy lub kodowanie regionalne prawdopodobnie będzie dobrym wyborem. Aby uzyskać więcej informacji, zobacz uwagi do Unicode poniżej.
- Podczas dekodowania :
- Twój program powinien pobierać dane wejściowe z trybu kodowania .
- Twój program musi wyprowadzać obraz w dowolnym rozsądnym formacie wybranym przez ciebie, jak określono powyżej, chociaż dla formatów wyjściowych wektorów również są OK.
- Obraz wyjściowy powinien być przybliżeniem obrazu wejściowego; im bliżej można dostać się do obrazu wejściowego, tym lepiej.
- Proces dekodowania może nie mieć dostępu do żadnych innych danych wyjściowych procesu kodowania innych niż dane wyjściowe określone powyżej; oznacza to, że nie można przesłać gdzieś obrazu i podać adresu URL procesu dekodowania do pobrania, ani niczego takiego głupiego.
W celu zachowania spójności interfejsu użytkownika program musi zachowywać się w następujący sposób:
- Twój program musi być skryptem, który można ustawić na wykonywalny na platformie za pomocą odpowiedniego interpretera, lub programem, który można skompilować w plik wykonywalny.
- Twój program powinien brać jako pierwszy argument albo
encode
czydecode
ustawienie trybu. Twój program musi pobierać dane wejściowe na jeden lub więcej z następujących sposobów (jeśli zaimplementujesz ten, który pobiera nazwy plików, możesz także czytać i zapisywać ze stdin i stdout, jeśli brakuje nazw plików):
Pobierz dane wejściowe ze standardowego wejścia i uzyskaj dane wyjściowe ze standardowego wyjścia.
my-program encode <input.png >output.txt my-program decode <output.txt >output.png
Pobierz dane wejściowe z pliku wymienionego w drugim argumencie i wygeneruj dane wyjściowe w pliku wymienionym w trzecim argumencie.
my-program encode input.png output.txt my-program decode output.txt output.png
- Dla swojego rozwiązania prosimy o opublikowanie:
- Twój kod w całości i / lub link do niego hostowany gdzie indziej (jeśli jest bardzo długi lub wymaga wielu plików do skompilowania, lub coś takiego).
- Wyjaśnienie, jak to działa, jeśli nie jest to bezpośrednio oczywiste z kodu lub jeśli kod jest długi, a ludzie będą zainteresowani podsumowaniem.
- Przykładowy obraz z oryginalnym obrazem, tekstem do którego jest skompresowany i zdekodowanym obrazem.
- Jeśli opierasz się na pomyśle, który miał ktoś inny, przypisz go. Możesz spróbować dopracować czyjś pomysł, ale musisz go przypisać.
Wytyczne
Są to w zasadzie reguły, które mogą zostać złamane, sugestie lub kryteria punktacji:
- Estetyka jest ważna. Będę oceniać i sugerować, aby inni ludzie osądzali na podstawie:
- Jak dobrze wygląda obraz wyjściowy i jak bardzo przypomina oryginał.
- Jak ładnie wygląda tekst. Całkowicie losowy gobbledigook jest OK, jeśli masz naprawdę sprytny schemat kompresji, ale chcę również zobaczyć odpowiedzi, które zamieniają obrazy w wielojęzyczne wiersze lub coś sprytnego. Zauważ, że autor oryginalnego rozwiązania zdecydował się używać tylko chińskich znaków, ponieważ w ten sposób wyglądał ładniej.
- Ciekawy kod i sprytne algorytmy są zawsze dobre. Lubię krótko, rzeczowo i przejrzysty kod, ale naprawdę sprytne, skomplikowane algorytmy są OK, o ile dają dobre wyniki.
- Szybkość jest również ważna, choć nie tak ważna, jak dobra praca kompresuje obraz. Wolę mieć program, który może konwertować obraz w ciągu jednej dziesiątej sekundy, niż coś, co będzie działało algorytmy genetyczne przez wiele dni.
- Wolę krótsze rozwiązania niż dłuższe, o ile są one stosunkowo porównywalne pod względem jakości; zwięzłość jest zaletą.
- Twój program powinien być implementowany w języku, który ma swobodnie dostępną implementację w systemie Mac OS X, Linux lub Windows. Chciałbym móc uruchamiać programy, ale jeśli masz świetne rozwiązanie, które działa tylko pod MATLABem lub coś w tym stylu, to w porządku.
- Twój program powinien być jak najbardziej ogólny; powinien działać na jak najwięcej różnych obrazów, chociaż niektóre mogą dawać lepsze wyniki niż inne. W szczególności:
- Posiadanie kilku obrazów wbudowanych w program, do którego pasuje i zapisuje odniesienie, a następnie po zdekodowaniu tworzy pasujący obraz, jest dość kulawe i obejmie tylko kilka obrazów.
- Program, który może robić zdjęcia prostych, płaskich, geometrycznych kształtów i rozkładać je na prymitywny wektor, jest całkiem sprytny, ale jeśli zawodzi na obrazach o określonej złożoności, prawdopodobnie nie jest wystarczająco ogólny.
- Program, który może robić zdjęcia tylko o określonym stałym współczynniku proporcji, ale wykonuje z nimi dobrą robotę, również byłby OK, ale nie idealny.
- Może się okazać, że obraz czarno-biały może uzyskać więcej informacji na mniejszej przestrzeni niż obraz kolorowy. Z drugiej strony może to ograniczać rodzaje obrazów, których dotyczy; twarze wyglądają dobrze w czerni i bieli, ale abstrakcyjne wzory mogą nie wyglądać tak dobrze.
- Jest całkowicie w porządku, jeśli obraz wyjściowy jest mniejszy niż wejście, przy mniej więcej takiej samej proporcji. W porządku, jeśli musisz przeskalować obraz w celu porównania z oryginałem; ważne jest, jak to wygląda.
- Twój program powinien generować dane wyjściowe, które mogłyby faktycznie przejść przez Twitter i wyjść bez szwanku. Jest to jedynie wytyczna, a nie reguła, ponieważ nie mogłem znaleźć żadnej dokumentacji na temat obsługiwanego dokładnego zestawu znaków, ale prawdopodobnie powinieneś unikać znaków kontrolnych, funky niewidocznych łączących znaki, znaków prywatnych i tym podobnych.
Punktacja rubryki
Jako ogólny przewodnik po tym, jak będę oceniać rozwiązania przy wyborze zaakceptowanego rozwiązania, powiedzmy, że prawdopodobnie będę oceniać rozwiązania w 25-punktowej skali (jest to bardzo szorstkie i nie będę oceniać niczego bezpośrednio, po prostu używając to jako podstawowa wytyczna):
- 15 punktów za to, jak dobrze schemat kodowania odtwarza szeroki zakres obrazów wejściowych. To subiektywny, estetyczny osąd
- 0 oznacza, że w ogóle nie działa, za każdym razem zwraca ten sam obraz lub coś w tym rodzaju
- 5 oznacza, że może zakodować kilka obrazów, chociaż dekodowana wersja wygląda brzydko i może nie działać w ogóle na bardziej skomplikowanych obrazach
- 10 oznacza, że działa na szerokiej gamie obrazów i tworzy przyjemnie wyglądające obrazy, które czasami mogą być rozpoznawalne
- 15 oznacza, że tworzy doskonałe repliki niektórych obrazów, a nawet w przypadku większych i bardziej złożonych obrazów daje coś, co można rozpoznać. A może nie tworzy obrazów, które są całkiem rozpoznawalne, ale tworzy piękne obrazy, które wyraźnie pochodzą z oryginału.
- 3 punkty za sprytne użycie zestawu znaków Unicode
- 0 punktów za zwykłe użycie całego zestawu dozwolonych znaków
- 1 punkt za użycie ograniczonego zestawu znaków, które można bezpiecznie przesyłać przez Twitter lub w wielu różnych sytuacjach
- 2 punkty za korzystanie z podzbioru tematycznego, takiego jak tylko ideogramy Hana lub tylko postacie od prawej do lewej
- 3 punkty za zrobienie czegoś naprawdę porządnego, na przykład wygenerowanie czytelnego tekstu lub użycie znaków, które wyglądają jak dany obraz
- 3 punkty za sprytne podejście algorytmiczne i styl kodu
- 0 punktów za coś, co zawiera 1000 linii kodu tylko w celu zmniejszenia skali obrazu, traktowania go jako 1 bit na piksel, a kodowanie base64 to
- 1 punkt za coś, co wykorzystuje standardową technikę kodowania, jest dobrze napisane i krótkie
- 2 punkty za coś, co wprowadza stosunkowo nową technikę kodowania lub jest zaskakująco krótkie i czyste
- 3 punkty za jedną linijkę, która faktycznie daje dobre wyniki, lub coś, co przełamuje nowy grunt w kodowaniu grafiki (jeśli wydaje się, że to mała liczba punktów za przełamanie nowej płaszczyzny, pamiętaj, że wynik tego dobra będzie prawdopodobnie miał wysoką ocenę za estetykę także)
- 2 punkty za prędkość. Gdy wszystko inne jest równe, szybsze jest lepsze, ale wszystkie powyższe kryteria są ważniejsze niż prędkość
- 1 punkt za uruchomienie na wolnym oprogramowaniu (open source), ponieważ wolę wolne oprogramowanie (pamiętaj, że C # będzie nadal kwalifikował się do tego punktu, dopóki będzie działał na Mono, podobnie kod MATLAB byłby kwalifikowany, gdyby działał na GNU Octave)
- 1 punkt za faktyczne przestrzeganie wszystkich zasad. Te zasady stały się nieco duże i skomplikowane, więc prawdopodobnie zaakceptuję dobre odpowiedzi, które pomylą jeden mały szczegół, ale dam dodatkowy punkt każdemu rozwiązaniu, które faktycznie spełnia wszystkie zasady
Obrazy referencyjne
Niektórzy ludzie prosili o obrazy referencyjne. Oto kilka obrazów referencyjnych, które możesz wypróbować; osadzone są tutaj mniejsze wersje, wszystkie prowadzą do większych wersji obrazu, jeśli potrzebujesz:
Nagroda
Oferuję nagrodę w wysokości 500 powtórzeń (plus 50, które uruchamia StackOverflow) za rozwiązanie, które lubię najbardziej, w oparciu o powyższe kryteria. Oczywiście zachęcam wszystkich innych do głosowania również na ich ulubione rozwiązania.
Uwaga na termin
Konkurs potrwa, dopóki nagroda się nie skończy, około 18:00 w sobotę 30 maja. Nie mogę powiedzieć, kiedy dokładnie się skończy; może być w dowolnym miejscu od 17:00 do 19:00. Gwarantuję, że przejrzę wszystkie zgłoszenia przesłane do 14.00 i dołożę wszelkich starań, aby zobaczyć wszystkie zgłoszenia przesłane do 16:00; jeśli później zostaną przedstawione rozwiązania, może nie będę miał szansy rzucić im sprawiedliwego spojrzenia, zanim będę musiał podjąć decyzję. Ponadto, im wcześniej prześlesz, tym większa szansa, że będziesz mieć możliwość głosowania, aby pomóc mi wybrać najlepsze rozwiązanie, więc spróbuj przesłać je wcześniej niż w wyznaczonym terminie.
Notatki Unicode
Nastąpiło również pewne zamieszanie co do tego, jakie dokładnie znaki Unicode są dozwolone. Zakres możliwych punktów kodowych Unicode jest U+0000
do U+10FFFF
. Istnieją pewne punkty kodowe, których nigdy nie można używać jako znaków Unicode w dowolnej otwartej wymianie danych; są to znaki niebędące znakami i punkty kodu zastępczego . Noncharacters zdefiniowano w Unidode standardowa 5.1.0 16,7 części jako wartości U+FFFE
, U+FFFF
, U+
nFFFE
, U+
nFFFF
, gdzie n jest 1
- 10
szesnastkowym, a zakres U+FDD0
-U+FDEF
. Wartości te są przeznaczone do użytku wewnętrznego specyficznego dla aplikacji, a zgodne aplikacje mogą usunąć te znaki z przetwarzanego przez nich tekstu. Zastępcze punkty kodowe, zdefiniowane w Unicode Standard 5.1.0 sekcja 3.8 jako U+D800
- U+DFFF
, są używane do kodowania znaków poza podstawową płaszczyzną wielojęzyczną w UTF-16; dlatego niemożliwe jest reprezentowanie tych punktów kodowych bezpośrednio w kodowaniu UTF-16, a kodowanie ich w jakimkolwiek innym kodowaniu jest nieprawidłowe. Dlatego na potrzeby tego konkursu zezwalam na dowolny program, który koduje obrazy w sekwencji nie więcej niż 140 punktów kodu Unicode z zakresu U+0000
- z U+10FFFF
wyłączeniem wszystkich znaków niebędących znakami i par zastępczych, jak zdefiniowano powyżej.
Ja preferuję rozwiązań, które wykorzystują tylko przypisanych znaków, a nawet lepsze te, które wykorzystują sprytnych podzbiory przypisanych znaków lub zrobić coś ciekawego z zestawu znaków, których używają. Aby uzyskać listę przypisanych znaków, zobacz bazę znaków znaków Unicode ; zwróć uwagę, że niektóre znaki są wymienione bezpośrednio, a niektóre tylko na początku i na końcu zakresu. Należy również pamiętać, że punkty kodu zastępczego są wymienione w bazie danych, ale są zabronione, jak wspomniano powyżej. Jeśli chcesz skorzystać z niektórych właściwości znaków, aby tekst był bardziej interesujący, istnieje wiele baz danych z informacjami o znakach , takich jak lista nazwanych bloków kodu i różne właściwości znaków.
Ponieważ Twitter nie określa dokładnego zestawu znaków, które obsługują, nie będę tolerować rozwiązań, które w rzeczywistości nie działają z Twitterem, ponieważ niektóre znaki liczą dodatkowe lub niektóre znaki są usuwane. Preferowane jest, ale nie wymagane, aby wszystkie zakodowane wyjścia mogły być przesyłane bez szwanku przez Twitter lub inną usługę mikroblogowania, taką jak identi.ca . Widziałem trochę dokumentacji stwierdzającej, że encje Twittera kodują <,> i &, i dlatego liczą je odpowiednio jako 4, 4 i 5 znaków, ale sam tego nie przetestowałem, a ich licznik znaków JavaScript nie wydaje się policzyć je w ten sposób.
Wskazówki i linki
- Definicja prawidłowych znaków Unicode w regułach jest nieco skomplikowana. Wybór pojedynczego bloku znaków, takiego jak CJK Unified Ideographs (U + 4E00 – U + 9FCF) może być łatwiejszy.
- Do manipulacji obrazami możesz używać istniejących bibliotek obrazów, takich jak ImageMagick lub Python Imaging Library .
- Jeśli potrzebujesz pomocy w zrozumieniu zestawu znaków Unicode i jego różnych kodowań, zapoznaj się z tym krótkim przewodnikiem lub szczegółowymi często zadawanymi pytaniami na temat UTF-8 w systemach Linux i Unix .
- Im wcześniej dostaniesz swoje rozwiązanie, tym więcej czasu będę musiał (ja i inne osoby) głosować na to. Możesz edytować swoje rozwiązanie, jeśli je ulepszysz; Opłacę moją nagrodę za najnowszą wersję, kiedy po raz ostatni przejrzę rozwiązania.
- Jeśli chcesz, aby prosty format obrazu był analizowany i zapisywany (i nie chcesz po prostu używać istniejącego formatu), sugeruję użycie formatu PPM . Jest to format tekstowy, który jest bardzo łatwy w obsłudze, i możesz użyć ImageMagick do konwersji do iz niego.
źródło
Odpowiedzi:
Dobra, oto moje: nanocrunch.cpp i CMakeLists.txt plik budować go przy użyciu CMake. Opiera się na Magick ++ ImageMagick API przez większość swojej obsługi obrazów. Wymaga również biblioteki GMP do arytmetyki bignum do kodowania łańcucha.
Oparłem swoje rozwiązanie na kompresji fraktali z kilkoma wyjątkowymi zwrotami akcji. Podstawową ideą jest zrobienie zdjęcia, zmniejszenie kopii do 50% i poszukiwanie kawałków w różnych orientacjach, które wyglądają podobnie do nie nakładających się bloków na oryginalnym obrazie. To podejście wymaga bardzo brutalnej siły, ale to po prostu ułatwia wprowadzenie moich modyfikacji.
Pierwsza modyfikacja polega na tym, że zamiast patrzeć tylko na obroty i przerzuty o 90 stopni, mój program uwzględnia również orientacje 45 stopni. Jest to jeden bit na blok, ale ogromnie poprawia jakość obrazu.
Inną rzeczą jest to, że przechowywanie regulacji kontrastu / jasności dla każdego składnika koloru każdego bloku jest o wiele za drogie. Zamiast tego przechowuję mocno skwantowany kolor (paleta ma tylko 4 * 4 * 4 = 64 kolory), które po prostu mieszają się w pewnej proporcji. Matematycznie jest to równoważne zmiennej jasności i stałej regulacji kontrastu dla każdego koloru. Niestety oznacza to również, że nie ma negatywnego kontrastu do odwrócenia kolorów.
Po obliczeniu położenia, orientacji i koloru dla każdego bloku koduje to w ciągu UTF-8. Po pierwsze, generuje bardzo duży bignum do reprezentowania danych w tabeli bloków i rozmiaru obrazu. Podejście do tego jest podobne do rozwiązania Sama Hocevara - rodzaj dużej liczby z podstawką różną w zależności od położenia.
Następnie konwertuje to na bazę dowolnej wielkości dostępnego zestawu znaków. Domyślnie w pełni wykorzystuje przypisany zestaw znaków Unicode, pomniejszony o znak mniejszy niż, większy niż, znak ampersand, sterowanie, łączenie oraz znaki zastępcze i prywatne. To nie jest ładne, ale działa. Możesz także skomentować domyślną tabelę i zamiast tego wybrać 7-bitowe ASCII do wydruku (ponownie z wyłączeniem znaków <,> i &) lub CJK Unified Ideographs. Tabela, w której dostępne są kody znaków, jest przechowywana w postaci szeregu zakodowanego naprzemiennymi seriami nieprawidłowych i prawidłowych znaków.
Tak czy inaczej, oto niektóre obrazy i czasy (mierzone na moim starym 3,0 GHz P4) i skompresowane do 140 znaków w pełnym przypisanym zestawie Unicode opisanym powyżej. Ogólnie jestem całkiem zadowolony z tego, jak się wszystko potoczyło. Gdybym miał więcej czasu, by nad tym popracować, prawdopodobnie spróbowałbym zmniejszyć blokadę zdekompresowanych obrazów. Mimo to uważam, że wyniki są całkiem dobre w przypadku ekstremalnego współczynnika kompresji. Zdekompresowane obrazy są nieco impresjonistyczne, ale uważam, że stosunkowo łatwo jest zobaczyć, jak bity odpowiadają oryginałowi.
Logo przepełnienia stosu (kodowanie 8,6s, dekodowanie 7,9s, 485 bajtów):
http://i44.tinypic.com/2w7lok1.png
Lena (32,8s do zakodowania, 13,0s do odkodowania, 477 bajtów):
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png
Mona Lisa (43.2s do kodowania, 14.5s do dekodowania, 490 bajtów):
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png
Edycja: Znaki ujednolicone CJK
Sam zapytał w komentarzach o używaniu tego z CJK. Oto wersja Mona Lisa skompresowana do 139 znaków z zestawu znaków CJK Unified:
http://i43.tinypic.com/2yxgdfk.png 咏 璘 驞 凄 脒 鵚 据 蛥 鸂 拗 朐 朖 朖 辿 韩 瀦 魷 痫 栘 璯 璯 緍 脲 蕜 蕜 揎 頻 蓼 債 鑡 鑡 嗞 靊 寞 柮 嚛 嚛 嚛 籥隤 慛 絖 銓 馿 渫 櫰 矍 昀 鰛 掾 撄 撄 粂 牙 蔍 螎 螎 葙 峬 峬 覧 絀 蹔 抆 惫 冧 笻 哜 搀 澐 澐 芯 芯 辍 澮 澮 黟 黟 偞 媄 童 童 竽 梀 韠 韠 镰伆 杇 婣 唆 鐤 諽 鷍 鴞 駫 搶 毤 埙 埙 誖 愿 萗 勹 勹 鈱 哳 哳 垬 濅 鬒 秀 瞛 洆 认 気 狋 異 異 闥 闥 珵 仾 仾 熜 熜 謋 繴 茴 茴 晋 髭 杍 杍 嚖擸 萿
Parametry strojenia u góry programu, których użyłem w tym celu, to: 19, 19, 4, 4, 3, 10, 11, 1000, 1000. Skomentowałem również pierwszą definicję liczby przypisanej i kodów oraz odkomentowałem ich ostatnie definicje, aby wybrać zestaw znaków Unified CJK.
źródło
pliki obrazów i źródła python (wersja 1 i 2)
Wersja 1 Oto moja pierwsza próba. Będę aktualizować, gdy idę.
Mam logo SO do 300 znaków prawie bezstratne. Moja technika wykorzystuje konwersję do grafiki wektorowej SVG, więc najlepiej działa w grafice liniowej. W rzeczywistości jest to kompresor SVG, wciąż wymaga oryginalnej sztuki przejścia przez etap wektoryzacji.
Do mojej pierwszej próby użyłem usługi online do śledzenia PNG, ale istnieje WIELE darmowych i niewolnych narzędzi, które mogą obsłużyć tę część, w tym potrace (open-source).
Oto wyniki
Oryginalne logo SO http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png Oryginalne zdekodowane logo SO http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png Po kodowaniu i rozszyfrowanie
Znaki : 300
Czas : Nie mierzony, ale praktycznie natychmiastowy (nie obejmuje etapów wektoryzacji / rasteryzacji)
Następnym etapem będzie osadzenie 4 symboli (punktów ścieżki SVG i poleceń) na znak Unicode. W tej chwili moja kompilacja Pythona nie ma szerokiej obsługi znaków UCS4, co ogranicza moją rozdzielczość na znak. Ograniczyłem również maksymalny zasięg do dolnego końca zarezerwowanego zakresu Unicode 0xD800, jednak po utworzeniu listy dozwolonych znaków i filtru, aby ich uniknąć, teoretycznie mogę przesunąć wymaganą liczbę znaków na 70-100 logo powyżej.
Ograniczeniem tej metody jest obecnie to, że wielkość wyjściowa nie jest stała. Zależy to od liczby węzłów / punktów wektorowych po wektoryzacji. Automatyzacja tego limitu będzie wymagać albo pikselowania obrazu (co usuwa główną zaletę wektorów), albo powtarzania przebiegania ścieżek przez etap uproszczenia, aż do osiągnięcia pożądanej liczby węzłów (co obecnie robię ręcznie w Inkscape).
Wersja 2
AKTUALIZACJA : v2 ma teraz kwalifikacje do konkurowania. Zmiany:
Znaki : 133
Czas : kilka sekund
v2 dekodowane http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png Po kodowaniu i dekodowaniu (wersja 2)
Jak widać, tym razem jest kilka artefaktów. Nie jest to ograniczenie metody, ale błąd w moich konwersjach. Artefakty zdarzają się, gdy punkty wykraczają poza zakres 0,0 - 127,0, a moje próby ograniczenia ich zakończyły się mieszanym sukcesem. Rozwiązaniem jest po prostu przeskalowanie obrazu, ale miałem problem ze skalowaniem rzeczywistych punktów, a nie matrycy obszaru roboczego lub grupy i jestem teraz zbyt zmęczony, żeby się tym przejmować. Krótko mówiąc, jeśli punkty znajdują się w obsługiwanym zakresie, to na ogół działa.
Wydaje mi się, że załamanie w środku wynika z przesunięcia się uchwytu na drugą stronę uchwytu, z którym jest połączony. Zasadniczo punkty są przede wszystkim zbyt blisko siebie. Uruchomienie filtra upraszczającego przed obrazem źródłowym przed kompresją powinno to naprawić i ogolić niektóre niepotrzebne znaki.
AKTUALIZACJA : Ta metoda jest odpowiednia dla prostych obiektów, więc potrzebowałem sposobu na uproszczenie skomplikowanych ścieżek i zmniejszenie hałasu. Użyłem Inkscape do tego zadania. Miałem trochę szczęścia w przygotowaniu niepotrzebnych ścieżek za pomocą Inkscape, ale nie miałem czasu na zautomatyzowanie go. Zrobiłem kilka przykładowych plików svg przy użyciu funkcji „Uproszczenia” programu Inkscape w celu zmniejszenia liczby ścieżek.
Uproszczenie działa dobrze, ale przy wielu ścieżkach może być powolne.
przykład autotrace http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png pole Cornell http://www.warriorhut.com/graphics/svg_to_unicode/cornell_box_simplified.png lena http://www.warriorhut.com/graphics /svg_to_unicode/lena_std_washed_autotrace.png
śledzone miniatury http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png
Oto kilka ujęć o bardzo niskiej rozdzielczości. Byłyby one bliżej limitu 140 znaków, choć może być również potrzebna sprytna kompresja ścieżki.
groomed http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png Uproszczony i zrozpaczony.
trianglulated http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_triangulated.png Uproszczony, zrozpaczony i triangulowany.
POWYŻEJ: Uproszczone ścieżki za pomocą automatycznego śledzenia .
Niestety mój parser nie obsługuje danych wyjściowych automatycznego śledzenia, więc nie wiem, jak mogą być używane punkty ani jak daleko się uprościć, niestety nie ma czasu na napisanie go przed upływem terminu. Jest jednak znacznie łatwiejsze do przeanalizowania niż wynik wyjściowy inkscape.
źródło
Moje pełne rozwiązanie można znaleźć pod adresem http://caca.zoy.org/wiki/img2twit . Ma następujące funkcje:
Oto ogólny zarys procesu kodowania:
A to jest proces dekodowania:
To, co uważam za najbardziej oryginalną część programu, to strumień bitów. Zamiast pakować wartości wyrównane do bitów (
stream <<= shift; stream |= value
), pakuję dowolne wartości, które nie są w potędze dwóch zakresów (stream *= range; stream += value
). Wymaga to obliczeń bignum i jest oczywiście dużo wolniejsze, ale daje mi 2009.18 bitów zamiast 1960, gdy używam głównych znaków CJK 20902 (to trzy dodatkowe punkty, które mogę umieścić w danych). A przy użyciu ASCII daje mi 917,64 bitów zamiast 840.Zdecydowałem się na metodę obliczania obrazu początkowego, która wymagałaby ciężkiej broni (wykrywanie narożników, ekstrakcja cech, kwantyzacja kolorów ...), ponieważ początkowo nie byłem pewien, czy to naprawdę pomoże. Teraz zdaję sobie sprawę, że konwergencja jest powolna (1 minuta jest dopuszczalna, ale mimo to jest powolna) i mogę spróbować to poprawić.
Główna pętla dopasowywania jest luźno zainspirowana algorytmem ditheringu Direct Binary Seach (w którym piksele są losowo zamieniane lub odwracane, aż do uzyskania lepszego półtonu). Obliczenie energii to prosta odległość średnia kwadratowa, ale najpierw wykonuję filtr mediany 5x5 na oryginalnym obrazie. Rozmycie gaussowskie prawdopodobnie lepiej reprezentuje zachowanie ludzkiego oka, ale nie chciałem tracić ostrych krawędzi. Zdecydowałem się także na symulację wyżarzania lub inne trudne do dostrojenia metody, ponieważ nie mam miesięcy na kalibrację tego procesu. Zatem flaga „jakości” reprezentuje tylko liczbę iteracji, które są wykonywane w każdym punkcie przed końcem enkodera.
Chociaż nie wszystkie obrazy kompresują się dobrze, jestem zaskoczony wynikami i naprawdę zastanawiam się, jakie istnieją inne metody, które mogą kompresować obraz do 250 bajtów.
Mam też małe filmy przedstawiające ewolucję stanu enkodera od losowego stanu początkowego i od „dobrego” stanu początkowego .
Edycja : oto jak metoda kompresji porównuje się z JPEG. Z lewej strony jamoes ma powyżej 536 bajtów. Po prawej stronie Mona Lisa skompresowała do 534 bajtów przy użyciu opisanej tutaj metody (wspomniane tutaj bajty odnoszą się do bajtów danych, dlatego ignorują bity zmarnowane przy użyciu znaków Unicode):
Edycja : właśnie zastąpiłem tekst CJK najnowszymi wersjami obrazów.
źródło
Poniższe informacje nie są formalne, ponieważ moje oprogramowanie nie zostało w żaden sposób dostosowane do wskazanego zadania. DLI można opisać jako optymalizujący kodek stratny obrazu ogólnego przeznaczenia. Jest to posiadacz rekordów PSNR i MS-SSIM do kompresji obrazu i pomyślałem, że byłoby ciekawe zobaczyć, jak sobie radzi w tym konkretnym zadaniu. Użyłem referencyjnego obrazu Mona Lisa i przeskalowałem go do 100x150, a następnie użyłem DLI do skompresowania go do 344 bajtów.
Mona Lisa DLI http://i40.tinypic.com/2md5q4m.png
Dla porównania ze skompresowanymi próbkami JPEG i IMG2TWIT użyłem DLI również do kompresji obrazu do 534 bajtów. JPEG ma 536 bajtów, a IMG2TWIT 534 bajtów. Obrazy zostały skalowane do mniej więcej tego samego rozmiaru dla łatwego porównania. JPEG to lewy obraz, IMG2TWIT jest środkowy, a DLI to prawy obraz.
Porównanie http://i42.tinypic.com/302yjdg.png
Obraz DLI zachowuje niektóre rysy twarzy, a zwłaszcza słynny uśmiech :).
źródło
Ogólny przegląd mojego rozwiązania byłby następujący:
Wiem, że prosiłeś o kod, ale tak naprawdę nie chcę tracić czasu na jego kodowanie. Uznałem, że wydajny projekt może przynajmniej zainspirować kogoś innego do napisania tego.
Myślę, że główną zaletą mojego proponowanego rozwiązania jest to, że ponownie wykorzystuje tyle istniejących technologii, ile to możliwe. Zabawne może być napisanie dobrego algorytmu kompresji, ale na pewno istnieje lepszy algorytm, prawdopodobnie napisany przez osoby posiadające wyższe wykształcenie matematyczne.
Jeszcze jedna ważna uwaga jest taka, że jeśli zdecyduje się, że utf16 jest preferowanym kodowaniem, wówczas rozwiązanie to się rozpada. Pliki JPEG nie działają tak naprawdę, gdy są skompresowane do 280 bajtów. Chociaż może istnieje lepszy algorytm kompresji niż jpg dla tego konkretnego problemu.
źródło
Okej, spóźniłem się na grę, ale mimo to zrobiłem swój projekt.
Jest to zabawkowy algorytm genetyczny, który wykorzystuje półprzezroczyste kolorowe koła do odtworzenia początkowego obrazu.
Funkcje:
Mis-feautres:
Oto przykładowy twit, który reprezentuje Lena: 犭 楊 谷 杌 蒝 螦 螦 界 匘 玏 扝 匮 俄 归 晃 客 猘 猘 摈 澹 澹 簜 摃 摃 斢 砠 砠 偑 偑 偑 婊 內 團 團 揕 揕 義 倨 襠 襠 凁 梡岂 掂 戇 耔 攋 斘 眐 奡 萛 狂 昸 箆 箆 亲 廙 塅 受 受 橯 恰 恰 应 戞 优 猫 僘 瑩 吱 賾 卣 朸 朸 杈 杈 綍 蝘 蝘 屐 屐 稱 悡 詬 詬 來 噩 压 压 罍 尕 熚 嫐 厥 厥虲 兙 罨 縨 炘 排 叁 抠 堃 從 弅 慌 慌 螎 標 柢 橙 橙 拃 丨 丨 蜊 缩 昔 儻 舭 勵 癳 冂 囤 璟 璟 彔 彔 兠 摈 摈 蒖 蒖 孂 埮 槃 槃 姠 璐 哠 哠 眛 嫡 琠 暬 訜 訜仔 廩 焛 瀻 严 啘 刱 垫 仔
Kod znajduje się w repozytorium Mercurial na bitbucket.org. Sprawdź http://bitbucket.org/tkadlubo/circles.lua
źródło
Oto moje podejście do problemu i muszę przyznać, że był to całkiem interesujący projekt, nad którym zdecydowanie nie pracuję, i dał mi coś nowego do nauczenia się.
Podstawowa idea mojego jest następująca:
Okazuje się, że to działa, ale tylko w ograniczonym zakresie, jak widać na przykładowych obrazach poniżej. Pod względem wydajności poniżej znajduje się tweet próbny, specjalnie dla obrazu Leny pokazanego w próbkach.
Jak widać, próbowałem trochę ograniczyć zestaw znaków; napotkałem jednak problemy podczas zapisywania danych koloru obrazu. Ponadto ten schemat kodowania ma tendencję do marnowania wielu bitów danych, które mogłyby zostać wykorzystane do uzyskania dodatkowych informacji o obrazie.
Jeśli chodzi o czasy działania, w przypadku małych obrazów kod jest niezwykle szybki, około 55 ms dla dostarczonych przykładowych obrazów, ale czas rośnie wraz z większymi obrazami. Dla obrazu referencyjnego Lena 512 x 512 czas działania wyniósł 1182 ms. Powinienem zauważyć, że szanse są całkiem dobre, że sam kod nie jest zbyt zoptymalizowany pod kątem wydajności (np. Wszystko działa jak mapa bitowa ), więc czasy mogą nieco spaść po pewnym refaktoryzacji.
Prosimy o sugestie dotyczące tego, co mogłem zrobić lepiej lub co może być nie tak z kodem. Pełny wykaz czasów działania i przykładowych danych wyjściowych można znaleźć w następującej lokalizacji: http://code-zen.info/twitterimage/
Zaktualizuj jeden
Zaktualizowałem kod RLE użyty podczas kompresji ciągu tweet, aby wykonać podstawowe spojrzenie wstecz, a jeśli tak, użyj go dla wyjścia. Działa to tylko dla par wartości liczbowych, ale pozwala zaoszczędzić kilka znaków danych. Czas wyświetlania jest mniej więcej taki sam, jak jakość obrazu, ale tweety są zwykle nieco mniejsze. Zaktualizuję tabelę na stronie po zakończeniu testów. Poniżej znajduje się jeden z przykładowych ciągów tweetów, ponownie dla małej wersji Leny:
Zaktualizuj drugą
Kolejna mała aktualizacja, ale zmodyfikowałem kod, aby spakować odcienie kolorów do grup po trzy w przeciwieństwie do czterech, to zajmuje więcej miejsca, ale chyba, że coś mi brakuje, powinno to oznaczać, że „dziwne” znaki nie pojawiają się już tam, gdzie kolor dane są. Ponadto zaktualizowałem kompresję nieco bardziej, aby mogła teraz działać na cały ciąg, a nie tylko na blok liczenia kolorów. Nadal testuję czasy działania, ale wydają się one nominalnie poprawione; jednak jakość obrazu jest nadal taka sama. Poniżej znajduje się najnowsza wersja tweeta Lena:
Logo StackOverflow http://code-zen.info/twitterimage/images/stackoverflow-logo.bmp Cornell Box http://code-zen.info/twitterimage/images/cornell-box.bmp Lena http: // code-zen .info / twitterimage / images / lena.bmp Mona Lisa http://code-zen.info/twitterimage/images/mona-lisa.bmp
źródło
Ten algorytm genetyczny napisany przez Rogera Alsinga ma dobry współczynnik kompresji kosztem długich czasów kompresji. Powstały wektor wierzchołków można dalej kompresować za pomocą algorytmu stratnego lub bezstratnego.
http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
Byłby ciekawy program do wdrożenia, ale spóźnię się.
źródło
W pierwotnym wyzwaniu limit rozmiaru jest zdefiniowany jako to, co Twitter nadal umożliwia wysyłanie, jeśli wkleisz tekst w polu tekstowym i naciśniesz „aktualizuj”. Niektóre osoby prawidłowo zauważyły, że różni się to od wiadomości SMS z telefonu komórkowego.
To, czego nie wymieniono wyraźnie (ale moją osobistą zasadą) jest to, że powinieneś być w stanie wybrać tweetowaną wiadomość w przeglądarce, skopiować ją do schowka i wkleić ją do pola wprowadzania tekstu twojego dekodera, aby mógł ją wyświetlić. Oczywiście są też wolne, aby zapisać wiadomość jako plik tekstowy i odczytać go z powrotem lub napisać narzędzie, które uzyskuje dostęp do API Twittera i odfiltrowuje każdej wiadomości, która wygląda jak kod obrazka (specjalne markery ktoś? Wink wink ). Ale reguła jest taka, że wiadomość musi przejść przez Twitter, zanim będzie można ją odkodować.
Powodzenia z 350 bajtami - wątpię, abyś mógł z nich skorzystać.
źródło
Opublikowanie obrazu monochromatycznego lub w skali szarości powinno poprawić rozmiar obrazu, który można zakodować w tym miejscu, ponieważ nie zależy Ci na kolorze.
Być może zwiększyło się wyzwanie przesłania trzech zdjęć, które po ponownym połączeniu dają obraz w pełnym kolorze, zachowując jednocześnie wersję monochromatyczną na każdym osobnym zdjęciu.
Dodaj trochę kompresji do powyższego i może zacząć wyglądać opłacalnie ...
Miły!!! Teraz wzbudziliście moje zainteresowanie. Przez resztę dnia nie będzie żadnej pracy ...
źródło
Odnośnie części kodowania / dekodowania tego wyzwania. base16b.org to moja próba określenia standardowej metody bezpiecznego i wydajnego kodowania danych binarnych w wyższych płaszczyznach Unicode.
Niektóre funkcje :
Przepraszamy, ta odpowiedź przychodzi o wiele za późno na oryginalne zawody. Rozpocząłem projekt niezależnie od tego postu, który odkryłem w połowie.
źródło
Pomysł przechowywania wielu zdjęć referencyjnych jest interesujący. Czy tak źle byłoby przechowywać powiedzmy 25 Mb przykładowych obrazów i zlecić enkoderowi skomponowanie obrazu przy użyciu ich fragmentów? Przy tak niewielkiej rurze maszyneria na obu końcach z konieczności będzie znacznie większa niż ilość przesyłanych danych, więc jaka jest różnica między 25 Mb kodu a 1 Mb kodu i 24 Mb danych?
(zauważ, że oryginalne wytyczne wykluczyły ograniczanie wprowadzania do obrazów znajdujących się już w bibliotece - nie sugeruję tego).
źródło
Głupi pomysł, ale
sha1(my_image)
spowodowałby „idealną” reprezentację każdego obrazu (ignorowanie kolizji). Oczywistym problemem jest to, że proces dekodowania wymaga nadmiernej ilości brutalnego wymuszania.1-bitowy monochromatyczny byłby nieco łatwiejszy. Każdy piksel staje się 1 lub 0, więc masz 1000 bitów danych dla obrazu 100 * 100 pikseli. Ponieważ skrót SHA1 ma 41 znaków, możemy zmieścić trzy w jednym komunikacie, musimy tylko brutalnie wymusić 2 zestawy 3333 bitów i jeden zestaw 3334 (chociaż nawet to prawdopodobnie nadal jest zbyt duże)
To nie jest do końca praktyczne. Nawet przy 1-bitowym obrazie o stałej długości 100 * 100px istnieje .., zakładając, że nie mylę obliczeń, 49995000 kombinacji lub 16661667, gdy podzielony na trzy.
źródło
Tutaj ta kompresja jest dobra.
http://www.intuac.com/userport/john/apt/
http://img86.imageshack.us/img86/4169/imagey.jpg http://img86.imageshack.us/img86/4169/imagey.jpg
Użyłem następującego pliku wsadowego:
Wynikowy rozmiar pliku to 559 bajtów.
źródło
Pomysł: czy możesz użyć czcionki jako palety? Spróbuj rozbić obraz w szeregu wektorów, próbując je opisać za pomocą kombinacji zestawów wektorów (każdy znak jest zasadniczo zbiorem wektorów). To używa czcionki jako słownika. Mógłbym na przykład użyć al do linii pionowej i - do linii poziomej? Po prostu pomysł.
źródło