Wyzwanie kodowania obrazu na Twitterze [zamknięte]


597

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 ): Mona Lisa

Czy potrafisz lepiej?

Zasady

  1. Twój program musi mieć dwa tryby: kodowania i dekodowania .
  2. Podczas kodowania :
    1. 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.
    2. 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 jest 1- 10szesnastkowym, a zakres U+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.
  3. Podczas dekodowania :
    1. Twój program powinien pobierać dane wejściowe z trybu kodowania .
    2. 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.
    3. Obraz wyjściowy powinien być przybliżeniem obrazu wejściowego; im bliżej można dostać się do obrazu wejściowego, tym lepiej.
    4. 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.
  4. W celu zachowania spójności interfejsu użytkownika program musi zachowywać się w następujący sposób:

    1. 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.
    2. Twój program powinien brać jako pierwszy argument albo encodeczy decodeustawienie trybu.
    3. 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):

      1. 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
        
      2. 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
        
  5. Dla swojego rozwiązania prosimy o opublikowanie:
    1. 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).
    2. 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.
    3. Przykładowy obraz z oryginalnym obrazem, tekstem do którego jest skompresowany i zdekodowanym obrazem.
    4. 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:

  1. Estetyka jest ważna. Będę oceniać i sugerować, aby inni ludzie osądzali na podstawie:
    1. Jak dobrze wygląda obraz wyjściowy i jak bardzo przypomina oryginał.
    2. 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.
    3. 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.
  2. 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.
  3. 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ą.
  4. 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.
  5. 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:
    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
  6. 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:

Lena Mona Lisa Pudełko Cornella Logo StackOverflow

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+0000do 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- 10szesnastkowym, 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+10FFFFwyłą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.

Zapraszam do sugestii na temat zasad, które napisałem w komentarzach; Z pewnością chętnie je poprawię, jeśli ludzie poczują, że potrzebują wyjaśnienia lub są zbyt zawężeni.
Brian Campbell

6
Prawdopodobnie powinieneś powiedzieć, że przesłanie obrazu na serwer i opublikowanie na nim adresu URL jest nieprawidłowe.
Shay Erlichmen

2
@Shay Czy już tego nie powiedziałem? „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; to znaczy, że nie można przesłać gdzieś obrazu i podać adresu URL procesu dekodowania do pobrania, ani niczego takiego głupiego . ”
Brian Campbell

1
@Konrad Rudolph Zgadzam się; Nie miałem na myśli „głupiego” z praktycznego punktu widzenia (oczywiście cały ten konkurs jest głupi z praktycznego punktu widzenia), miałem na myśli „głupi” w kontekście tego konkursu. Korzystanie z identyfikatora URI nie jest tak naprawdę algorytmem kompresji w sensie teorii informacji, ponieważ nie pozwala na przesłanie żadnych dodatkowych informacji bez korzystania z alternatywnego kanału. Możesz nadać koderowi i dekoderowi dużą bazę obrazów i nazwać to kompresją, która działa tylko na ograniczonym zestawie obrazów, ale określiłem, że musisz być w stanie obsłużyć dowolny obraz.
Brian Campbell

2
Oto kilka linków, na które natknąłem się, które mogą pomóc ludziom: azillionmonkeys.com/qed/unicode.html w celu wyjaśnienia prawidłowego zakresu znaków Unicode. Zauważ, że kodowanie UTF to takie, które mogą kodować cały zakres Unicode; UCS-4 jest nadzbiorem Unicode, a UCS-2 i ASCII to podzbiory. A na froncie kompresji, jest podobna technika jak w oryginalnym poście, choć pozwala sobie na 1k zamiast 350 bajtów: screamingduck.com/Article.php?ArticleID=46&Show=ABCE
Brian Campbell

Odpowiedzi:


244

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.


Łał! Dobra robota. Byłem sceptycznie nastawiony do fraktalnej kompresji obrazów dla tak małych obrazów, ale w rzeczywistości daje całkiem przyzwoite rezultaty. Kompilacja i uruchomienie były również dość łatwe.
Brian Campbell

1
Dzięki chłopaki! Sam, masz na myśli wyniki z zaledwie 140 znakami CJK? Jeśli tak, to tak, musisz dostroić liczby u góry. Ostateczny rozmiar w bitach wynosi około log2 (steps_in_x steps_in_y steps_in_red steps_in_green steps_in_blue) * blocks_in_x blocks_in_y + log2 (maximum_width maximum_height).
Boojum

Edycja: W pierwszym log2 () jest * 16, które pominąłem. To dotyczy możliwych orientacji.
Boojum

20
Czy ktoś jeszcze używa tego obrazu na Twitterze?
dbr

288

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:

  • Wejścia / wyjścia sterujące z wiersza poleceń i debugowanie
  • Używa parsera XML (lxml) do obsługi SVG zamiast wyrażenia regularnego
  • Pakuje 2 segmenty ścieżki na symbol Unicode
  • Dokumentacja i porządek
  • Styl wsparcia = „fill: color” i fill = „color”
  • Szerokość / wysokość dokumentu zapakowana w pojedynczy znak
  • Kolor ścieżki zapakowany w pojedynczy znak
  • Kompresję kolorów uzyskuje się przez wyrzucenie 4 bitów danych koloru na kolor, a następnie upakowanie go w postaci poprzez konwersję szesnastkową.

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.

autotrace --output-format svg --output-file cornell_box.svg --despeckle-level 20 --color-count 64 cornell_box.png

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.


2
Świetny! Na początku chciałem stworzyć hybrydowe rozwiązanie wektorowe z zarówno ostrymi krawędziami, jak i gładkimi obszarami, ale okazało się, że jest to zbyt złożone bez użycia biblioteki śledzenia (z której nie chciałem korzystać). Nie mogę się doczekać, aby zobaczyć, jak daleko możesz zajść dzięki swojej metodzie!
sam hocevar

Miły! Miałem nadzieję, że zobaczymy kilka prób niemal bezstratnego podejścia do wektoryzacji. Oznacza to, że ma niższą ogólność, ale wyższą jakość obrazów, które obejmuje. Można użyć usługi online do wektoryzacji. Powodzenia w dalszym zmniejszaniu rozmiaru!
Brian Campbell

Uważałbym kompresję obrazu i kodowanie znaków za dwa różne etapy - technika Sama wydaje się być optymalna do kodowania i może być łatwo wbudowana w samodzielny program. Dostaniesz więcej za swoje pieniądze, koncentrując się na unikalnej części swojego rozwiązania (tj. Części kompresji) i po prostu generując ciąg bitów.
Mark Ransom

70
Łał. Te obrazy wyglądają naprawdę stylowo.
Rinat Abdullin

199

Moje pełne rozwiązanie można znaleźć pod adresem http://caca.zoy.org/wiki/img2twit . Ma następujące funkcje:

  • Rozsądny czas kompresji (około 1 minuty dla wysokiej jakości)
  • Szybka dekompresja (ułamek sekundy)
  • Zachowuje oryginalny rozmiar obrazu (nie tylko proporcje)
  • Przyzwoita jakość rekonstrukcji (IMHO)
  • Długość komunikatu i zestaw znaków (ASCII, CJK, symbole) można wybrać w czasie wykonywania
  • Długość i zestaw znaków są automatycznie wykrywane w czasie dekompresji
  • Bardzo wydajne pakowanie informacji

http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png

蜥 秓 鋖 筷 聝 诿 缰 偺 腶 漷 庯 祩 祩 皙 谪 幻 寤 寤 厎 趆 趆 脘 搇 梄 踥 桻 理 戂 溥 欇 渹 渹 裏 裏 骿 苸 苸 骟 骟 市 簶 璨 璨 粭 浧 鱉 鱉 捕 弫 潮 岚 蚙 蚙玧 霫 鏓 蓕 戲 債 鼶 襋 躻 弯 袮 足 足 庭 旍 驅 據 據 嘛 掔 掔 倾 诗 籂 阉 嶹 婻 椿 糢 墤 渽 渽 緛 緛 更 儅 儅 武 武 婩 縑 逡 逡 荨 璙 杯 杯 翉 珸 齸 憫 颗 颗擲 舥 攩 寉 鈶 兓 庭 璱 篂 鰀 乾 丕 丕 庁 錸 努 樀 肝 亖 弜 喆 喆 蝞 躐 葌 熲 谎 蛪 曟 暙 刍 镶 媏 媏 嘝 驌 慸 盂 氤 缰 缰 殾 譑

Oto ogólny zarys procesu kodowania:

  • Liczba dostępnych bitów jest obliczana na podstawie pożądanej długości komunikatu i użytecznego zestawu znaków
  • Obraz źródłowy jest podzielony na tyle komórek kwadratowych, na ile pozwalają dostępne bity
  • Na każdą komórkę wpływa ustalona liczba punktów (obecnie 2), z początkowymi współrzędnymi i wartościami kolorów
  • Czynności powtarzane są do momentu spełnienia warunku jakości:
    • Punkt jest wybierany losowo
    • Operacja wykonywana jest losowo w tym punkcie (przeniesienie jej do komórki, zmiana koloru)
    • Jeśli obraz wynikowy (patrz proces dekodowania poniżej) jest bliżej obrazu źródłowego, operacja zostanie zachowana
  • Rozmiar obrazu i lista punktów są zakodowane w UTF-8

A to jest proces dekodowania:

  • Rozmiar obrazu i punkty są odczytywane ze strumienia UTF-8
  • Dla każdego piksela na obrazie docelowym:
    • Obliczana jest lista naturalnych sąsiadów
    • Ostateczny kolor piksela jest ustawiony jako średnia ważona kolorów naturalnych sąsiadów

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.

http://caca.zoy.org/raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter2.png

苉 憗 揣 嶕 繠 剳 腏 篮 濕 茝 霮 墧 墧 蒆 杚 樟 赒 赒 肴 飗 飗 噹 砃 燋 任 朓 峂 釰 靂 陴 貜 貜 犟 犟 喗 讄 讄 砙 砙 矺 敨 鷾 鷾 瓔 亨 髎 髎 芟 氲 簵 俇 嫤 嫤激 躙 憮 鄴 甮 槺 骳 佛 愚 猪 駪 惾 惾 嫥 珏 堭 颽 颽 箽 赭 赭 飉 訥 偁 箝 窂 蹻 熛 漧 衆 橼 橼 愀 愀 玴 毡 毡 頢 頢 羔 恺 墎 墎 嬔 鑹 楄 楄 瑥 鶼 呍 秓 抲 抲苾 绒 酯 嵞 脔 婺 污 囉 酼 俵 菛 琪 琪 则 辩 曚 鸸 職 銛 蒝 礭 礭 鱚 蟺 稿 纡 醾 陴 鳣 尥 蟀 惘 鋁 鋁 髚 忩 祤 脤 养 趯 趯 沅 况

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):

http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png

Edycja : właśnie zastąpiłem tekst CJK najnowszymi wersjami obrazów.


Właściwie nie muszę być w stanie uruchomić kodu (umieszczam część dotyczącą uruchamiania go w wytycznych, jako sugestię, a nie zasady); Wolałbym móc go uruchomić, ale ocenię to bardziej na podstawie jakości generowanych obrazów, kodu i wszelkich interesujących sztuczek lub algorytmów. Jeśli chcę go uruchomić i wymaga on pakietów, których nie mam lub nie chcę instalować w głównym systemie, mogę po prostu uruchomić instancję Amazon EC2 i zainstalować ją. Tak długo, jak pracujesz z bibliotekami spakowanymi dla jednej z głównych dystrybucji, powinienem móc go uruchomić. Zachęcamy do korzystania z CGAL.
Brian Campbell,

2
Dobra, oto moje rozwiązanie (kod źródłowy): caca.zoy.org/browser/libpipi/trunk/examples/img2twit.cpp Moja próba wyjaśnienia i kilka przykładów znajduje się na caca.zoy.org/wiki/img2twit
sam hocevar

2
Naprawdę podoba mi się twoje rozwiązanie. Powinieneś spróbować zmniejszyć liczbę wartości przypisanych do niebieskiego kanału, ponieważ ludzkie oko nie potrafi bardzo dobrze rozróżnić niebieskiego: nfggames.com/games/ntsc/visual.shtm ; pozwoli to uzyskać więcej szczegółów kosztem utraty niektórych informacji o kolorze. A może przypisać go do zielonego?
rpetrich

5
Słuszna uwaga. Wypróbowałem kilka wariantów tego pomysłu (patrz komentarze przed definicją RANGE_X), ale niezbyt dokładnie. Jak widać, użycie 5 niebieskich wartości zamiast 6 zwiększyło błąd nieco mniej niż użycie 7 wartości zielonych zmniejszyło go. Nie próbowałem robić obu z lenistwa. Innym problemem jest to, że nie mam bardzo dobrej funkcji błędu. Obecnie używam ∑ (∆r² + ∆g² + ∆b²) / 3, co działa OK. Próbowałem ∑ (0.299∆r² + 0.587∆g² + 0.114∆b²), w oparciu (bez fizycznego uzasadnienia) na składowej YUV YUV, ale było to zbyt tolerancyjne z niebieskimi błędami. Spróbuję znaleźć artykuły na ten temat.
sam hocevar

2
@rpetrich: Zmodyfikowałem program, aby dynamicznie zwiększał zakresy r / g / b, o ile dostępnych jest wystarczających bitów. To gwarantuje, że nigdy nie marnujemy więcej niż 13 bitów w całym strumieniu bitów (ale w praktyce jest to zwykle 1 lub 2). Obrazy wyglądają nieco lepiej.
sam hocevar

45

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 :).


6
Ups Powyższe należy przypisać Dennisowi Lee, który złożył je pierwotnie. Właśnie go edytowałem, aby osadzić obrazy w wierszu i link do odsyłacza znalezionego przez Googlinga. I muszę powiedzieć, wow, jestem pod wrażeniem kompresji. Będę musiał sprawdzić kompresję DLI.
Brian Campbell

1
Nawiasem mówiąc, autor DLI wspomina o „długim czasie przetwarzania”. Ponieważ nie jestem w stanie uruchomić jego oprogramowania, czy możesz podać nam przybliżone czasy kompresji?
sam hocevar

1
Używając procesora AMD Athlon64 2,4 GHz, kompresja obrazu Mona Lisa 100 x 150 zajmuje 38 sekund, a dekompresja 6 sekund. Kompresja do maksymalnie 251 bajtów jest trudniejsza, a jakość wyjściowa jest znacznie obniżona. Używając referencyjnego obrazu Mona Lisa, zmniejszyłem go do 60x91, a następnie użyłem DLI do skompresowania go do 243 bajtów (najbliżej 251 bez przekraczania). To jest wynik i43.tinypic.com/2196m4g.png Szczegół nie znajduje się w pobliżu DLI 534 bajtów, mimo że szybkość transmisji bitów została zmniejszona tylko o ~ 50%. Struktura obrazu została jednak zachowana dość dobrze.

1
Postanowiono ułatwić porównanie 250 skompresowanych próbek. 243 bajtowy DLI został przeskalowany i umieszczony obok próbki IMG2TWIT. IMG2TWIT po lewej, DLI po prawej. Oto zdjęcie i40.tinypic.com/30ndks6.png

1
DLI korzysta z parametru jakości, takiego jak JPEG, więc jeśli wymagana jest docelowa wielkość wyjściowa, wymagana jest metoda prób i błędów.

21

Ogólny przegląd mojego rozwiązania byłby następujący:

  1. Zaczynam od obliczenia maksymalnej ilości surowych danych, które można zmieścić w 140 znakach utf8.
    • (Zakładam, że utf8, w którym oryginalna witryna twierdziła, że ​​Twitter przechowuje wiadomości. Różni się to od powyższego opisu problemu, który pyta o utf16.)
    • Korzystając z tego utf8 , obliczam, że maksymalna liczba bitów, którą można zakodować w jednym znaku utf8, wynosi 31 bitów. Aby to zrobić, użyłbym wszystkich znaków z zakresu U-04000000 - U-7FFFFFFF. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, jest 31 x, więc mógłbym zakodować do 31 bitów).
    • 31 bitów razy 140 znaków to 4340 bitów. Podziel to przez 8, aby uzyskać 524,5, i zaokrąglij w dół do 542 bajtów .
    • (Jeśli ograniczymy się do utf16, moglibyśmy przechowywać tylko 2 bajty na znak, co równałoby się 280 bajtom).
  2. Skompresuj obraz za pomocą standardowej kompresji jpg.
    • Zmień rozmiar obrazu na około 50 x 50 pikseli, a następnie spróbuj go skompresować na różnych poziomach kompresji, aż uzyskasz obraz o wielkości maksymalnie 542 bajtów, bez przekraczania.
    • Jest to przykład mona lisa skompresowanego do 536 bajtów.
  3. Zakoduj nieprzetworzone bity skompresowanego obrazu do znaków utf-8.
    • Zastąp każdy x w następujących bajtach: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, bitami z obrazka.
    • Ta część prawdopodobnie byłaby częścią, w której większość kodu musiałaby zostać napisana, ponieważ obecnie nie istnieje nic, co by to robiło.

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.


Jestem teraz w pracy, ale definitywnie wdrażam to rozwiązanie po powrocie do domu.
Paulo Santos

2
Z moich eksperymentów wynika, że ​​UTF-16 jest rzeczywiście sposobem, w jaki Twitter liczy znaki; Znaki BMP liczą się jako 1, a znaki wyższej płaszczyzny liczą się jako 2. Nie jest to udokumentowane, ale tak liczy się ich licznik znaków JavaScript po wpisaniu w polu wprowadzania. Jest to również wspomniane w komentarzach w oryginalnym wątku. Nie próbowałem przesyłać za pośrednictwem interfejsu API, aby sprawdzić, czy licznik jest uszkodzony; jeśli tak, zaktualizuję problem pod kątem rzeczywistych ograniczeń. Prawdopodobnie nie będziesz w stanie użyć dowolnego UTF-8, ponieważ wiele z tych dłuższych sekwencji, które możesz zakodować, nie jest prawidłowym Unicode.
Brian Campbell

4
Po przetestowaniu za pomocą interfejsu API okazuje się, że liczą według znaków Unicode (punktów kodowych), a nie jednostek kodu UTF-16 (licznik znaków JavaScript liczy się przez UTF-16, ponieważ najwyraźniej tak robi metoda długości JavaScript) . Możesz więc uzyskać tam trochę więcej informacji; prawidłowe znaki Unicode mieszczą się w zakresie od U + 0000 do U + 10FFFF (nieco więcej niż 20 bitów na znak; 2 ^ 20 + 2 ^ 16 możliwych wartości na znak). UTF-8 pozwala na kodowanie większej liczby wartości niż jest to dozwolone w Unicode, więc jeśli ograniczysz się do Unicode, możesz uzyskać około 350 bajtów miejsca, a nie 542.
Brian Campbell

3
Ta 536-bajtowa Mona Lisa wygląda zaskakująco dobrze, biorąc pod uwagę ekstremalną kompresję!
Chris

3
Obecnie możemy zakodować 129 775 różnych (przypisanych, niekontrolujących, nieprywatnych) znaków Unicode. Jeśli ograniczymy się do tego podzbioru, będzie to w sumie 2377 bitów lub 297 bajtów. Kod tutaj: porg.es/blog/what-can-we-fit-in-140-characters
porges

20

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:

  • czysty Lua. Działa w dowolnym miejscu, w którym działa interpreter Lua.
  • używa formatu Netpbm P3
  • pochodzi z kompleksowym pakietem testów jednostkowych
  • zachowuje oryginalny rozmiar obrazu

Mis-feautres:

  • powolny
  • przy tych ograniczeniach przestrzeni zachowuje jedynie podstawowy schemat kolorów obrazu początkowego i ogólny zarys kilku jego cech.

Oto przykładowy twit, który reprezentuje Lena: 犭 楊 谷 杌 蒝 螦 螦 界 匘 玏 扝 匮 俄 归 晃 客 猘 猘 摈 澹 澹 簜 摃 摃 斢 砠 砠 偑 偑 偑 婊 內 團 團 揕 揕 義 倨 襠 襠 凁 梡岂 掂 戇 耔 攋 斘 眐 奡 萛 狂 昸 箆 箆 亲 廙 塅 受 受 橯 恰 恰 应 戞 优 猫 僘 瑩 吱 賾 卣 朸 朸 杈 杈 綍 蝘 蝘 屐 屐 稱 悡 ​​詬 詬 來 噩 压 压 罍 尕 熚 嫐 厥 厥虲 兙 罨 縨 炘 排 叁 抠 堃 從 弅 慌 慌 螎 標 柢 橙 橙 拃 丨 丨 蜊 缩 昔 儻 舭 勵 癳 冂 囤 璟 璟 彔 彔 兠 摈 摈 蒖 蒖 孂 埮 槃 槃 姠 璐 哠 哠 眛 嫡 琠 暬 訜 訜仔 廩 焛 瀻 严 啘 刱 垫 仔

oryginalna lena zakodowana Lena

Kod znajduje się w repozytorium Mercurial na bitbucket.org. Sprawdź http://bitbucket.org/tkadlubo/circles.lua


2
Niesamowite! Tworzy schludne, artystycznie wyglądające obrazy. Cieszę się, że ludzie wciąż nad tym pracują; fajnie było zobaczyć wszystkie różne podejścia.
Brian Campbell

1
Chciałbym zobaczyć, że jest to używane jako przezroczysta nakładka na oryginał, dająca efekt bokeh.
Nick Radford,

19

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:

  1. Próbkuj obraz w dół w skali szarości, tak aby w sumie było 16 różnych odcieni
  2. Preform RLE na obrazie
  3. Spakuj wyniki do znaków UTF-16
  4. Wykonaj RLE na zapakowanych wynikach, aby usunąć wszelkie powielanie znaków

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.

乤 乤 万 乐 唂 伂 倂 倁 企 儂 企 2 企 倁 3 企 倁 2 企 伂 8 企 伂 3 企 伂 5 企 倂 倃 伂 倁 3 倁 儁 企 企 企 2 伂 倃 5 企 倁 3 企 倃 4 企 倂 企 企 倁 企伂 2 企 伂 5 企 倁 企 伂 쥹 皗 鞹 鐾 鐾 䦽 阹 럆 䧜 椿 籫 릹 靭 靭 욶 옷뎷 歩 㰷 歉 䴗 鑹 㞳 鞷 㬼 㬼 獴 鏙 돗 鍴 祳 㭾 뤶 뤶 殞 焻 乹 Ꮛ Ꮛ 靆 䍼

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:

乤 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 ウ 伂 8 企 伂 エ 伂 伂 企 5 企 倂 倃 伂 倁 グ 儁 企 企 2 伂 倃 ガ 倁 ジ 倃 倃 4 企 倂 企 倁 企 伂 伂 ツ 伂 ス 倁企 伂 쥹 皗 鞹 鐾 륶 䦽 阹 럆 䧜 椿 椿 릹 靭 욶 옷뎷 歩 㰷 歉 䴗 鑹 鑹 㞳 鞷 㬼 獴 鏙 돗 鍴 祳 㭾 뤶 뤶 焻 乹 Ꮛ 靆 䍼

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:

2 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 ウ 伂 8 企 伂 エ 伂 伂 5 企 倂 倃 伂 倁 グ 儁 企 企 2 伂 倃 ガ 倁 ジ 倃 4 倃 倃 企 倁 企 伂 伂 ツ ス 倁 倁企 伂 坹 坼 坶 坻 刾 啩 容 力 吹 婩 婩 劝 圿 妛 啭 啭 奩 嗆 嗆 婣 冷 咛 啫 凃 奉 佶 坍 均 喳 喳 女 女 决 兴宗 兴宗 喓 夽 兴 兴 唹 屹 冷 圶 圶 埫 埫 唓 似 喝 喝商 嗉 乃

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


1
Świetnie, dziękuję za zgłoszenie! Skala szarości w rzeczywistości działa dość dobrze dla większości z nich, choć Lena jest nieco trudna do zrozumienia. Szukałem twojego źródła, ale dostałem 404; czy możesz się upewnić, że tam jest?
Brian Campbell

Sprawdź to teraz teraz, aktualizowałem witrynę, więc mogłeś mnie złapać między aktualizacjami.
rjzii

Tak, mogę go teraz pobrać. Teraz oczywiście muszę dowiedzieć się, czy mogę zmusić Mono do jego skompilowania.
Brian Campbell

Tak! Działa pod Mono, skompilowałem z „gmcs -r System.Drawing TwitterImage.cs Program.cs” i uruchomiłem z „mono TwitterImage.exe encode lena.png lena.txt”
Brian Campbell

Fajne! Zrobiłem podwójne sprawdzenie, aby upewnić się, że biblioteki, których używam, znajdują się na liście Mono, ale tak naprawdę jeszcze nie pracowałem z Mono, więc nie byłem pewien, czy tak będzie.
rjzii


12

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ć.


1
Tak, dodałem rubrykę punktacji, która wskazuje, że zaostrzone ograniczenia zestawu znaków są preferowane, ale nie wymagane. Chciałbym mieć regułę, która wymaga, aby wiadomości przechodziły przez Twitter bez szwanku, ale wymagałoby to wielu prób i błędów, aby ustalić dokładne szczegóły tego, co działa, i chciałem zostawić trochę swobody, aby umożliwić kreatywne wykorzystanie przestrzeń kodu. Zatem jedynym wymaganiem w moim wyzwaniu jest 140 prawidłowych znaków Unicode. Nawiasem mówiąc, dzięki za zatrzymanie się! Naprawdę podoba mi się twoje rozwiązanie i chcę zobaczyć, czy któryś z kibitzerów rzeczywiście może go ulepszyć.
Brian Campbell

12

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 ...


9
s / peaked / piqued / g
jedenaście81

1
Podoba mi się pomysł trzech zdjęć, powinno być możliwe zaimplementowanie takiego pomysłu na Twitterze, a wynik byłby całkiem niezły.
Makis

9

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 :

  • Wykorzystuje tylko prywatne obszary użytkownika Unicode
  • Koduje do 17 bitów na znak; prawie trzy razy wydajniejszy niż Base64
  • Dostarczono referencyjną implementację Javascript kodowania / dekodowania
  • Uwzględniono niektóre przykładowe kodowania, w tym Twitter i Wordpress

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.


8

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).


1
Byłoby dobrze, pod warunkiem, że masz stałą, skończoną ilość danych w dowolnym punkcie końcowym. Oczywiście musisz wykazać, że działa on z obrazami, których nie ma w zestawie szkoleniowym, tak jak w przypadku każdego statystycznego problemu z językiem naturalnym. Chciałbym zobaczyć coś, co przyjmuje statystyczne podejście do kodowania obrazu.
Brian Campbell

16
Ja, na przykład, chciałbym zobaczyć, jak Mona Lisa jest przerobiona, używając wyłącznie dzieł fanowskich Boba Fett jako źródła.
Nosredna

Zgadzam się - podejście fotomozaiczne wydaje się być zgodne z regułami i byłoby niezwykle interesujące zobaczyć, jak ktoś się dźga.
An̲̳̳drew

8

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.

def fact(maxu):
        ttl=1
        for i in range(1,maxu+1):
                ttl=ttl*i
        return ttl

def combi(setsize, length):
    return fact(length) / (fact(setsize)*fact(length-setsize))

print (combi(2, 3333)*2) + combi(2, 3334)
# 16661667L
print combi(2, 10000)
# 49995000L

10
Problem z sha1 (my_image) polega na tym, że jeśli spędzasz swój brutalny czas na zmuszaniu go, prawdopodobnie znajdziesz wiele kolizji, zanim znajdziesz prawdziwy obraz; i oczywiście brutalne zmuszanie sha1 jest praktycznie niewykonalne obliczeniowo.
Brian Campbell

5
Nawet lepsza niż kompresja SHA1: mój algorytm kompresji „flickr”! Krok 1: Prześlij obraz do Flickr. Krok 2: opublikuj link do niego na Twitterze. Tadda! Używa tylko 15 bajtów!
niXar

2
niXar: Nie, reguła 3.4: „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; to znaczy, że nie można przesłać gdzieś obrazu i podać adresu URL procesu dekodowania do pobieranie lub cokolwiek głupiego takiego ”.
dbr

6
Wiem, że byłem sarkastyczny.
niXar


0

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ł.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.