Herausforderung der Twitter-Bildkodierung

Question

Wenn ein Bild mehr als 1000 Worte sagt, wie viel von einem Bild kann man dann in 140 Zeichen unterbringen?

Nota : Das war's, Leute! Der Abgabetermin für das Kopfgeld ist da, und nach reiflicher Überlegung habe ich beschlossen, dass Boojum's Eintrag nur knapp verdrängt Sam Hocevar's . Ich werde ausführlichere Notizen veröffentlichen, sobald ich die Gelegenheit hatte, sie zu schreiben. Natürlich kann jeder auch weiterhin Lösungen einreichen und Lösungen verbessern, über die dann abgestimmt werden kann. Vielen Dank an alle, die einen Beitrag eingereicht haben; sie haben mir alle gefallen. Es hat mir sehr viel Spaß gemacht, diesen Wettbewerb zu leiten, und ich hoffe, dass er sowohl den Teilnehmern als auch den Zuschauern Spaß gemacht hat.

Ich stieß auf dieser interessante Beitrag über den Versuch, Bilder in einem Twitter-Kommentar zu komprimieren, und viele Leute in diesem Thread (und ein Thread auf Reddit ) hatte Vorschläge für verschiedene Möglichkeiten, wie man es machen könnte. Ich denke, das wäre eine gute Herausforderung für die Programmierung. Die Leute sollen zeigen, was sie drauf haben, und wie ihre Ideen zur Kodierung zu mehr Details auf dem begrenzten Platz führen können, der zur Verfügung steht.

Ich fordere Sie auf, ein allgemeines System zur Kodierung von Bildern in 140-Zeichen-Twitter-Nachrichten und deren Dekodierung in ein Bild zu entwickeln. Sie können Unicode-Zeichen verwenden, so dass Sie mehr als 8 Bit pro Zeichen erhalten. Aber selbst wenn Sie Unicode-Zeichen verwenden, müssen Sie die Bilder auf sehr kleinem Raum komprimieren. Dies wird sicherlich eine verlustbehaftete Komprimierung sein, so dass subjektiv beurteilt werden muss, wie gut jedes Ergebnis aussieht.

Hier ist das Ergebnis, dass der ursprüngliche Autor, Quasimondo aus seiner Kodierung (das Bild ist lizenziert unter einer Creative Commons Namensnennung-Nichtkommerzielle Lizenz ):

Können Sie es besser?

Regeln

1. Ihr Programm muss zwei Modi haben: Kodierung y Dekodierung .

2. Wenn Kodierung :

   1. Ihr Programm muss als Eingabe eine Grafik in einer beliebigen Raster Grafikformat Ihrer Wahl. Wir sagen, dass jedes Rasterformat, das von ImageMagick gilt als angemessen.
   2. Ihr Programm muss eine Nachricht ausgeben, die in 140 oder weniger Unicode-Codepunkten dargestellt werden kann; 140 Codepunkte im Bereich U+0000 - U+10FFFF ohne Nicht-Zeichen ( U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF wobei n es 1 - 10 hexadezimal, und der Bereich U+FDD0 - U+FDEF ) und Surrogat-Codepunkte ( U+D800 - U+DFFF ). Sie kann in jeder vernünftigen Kodierung Ihrer Wahl ausgegeben werden; jede Kodierung, die von GNU iconv wird als angemessen betrachtet, und die plattformeigene Kodierung oder die Kodierung des Gebietsschemas ist wahrscheinlich eine gute Wahl. Siehe Unicode-Hinweise unten für weitere Einzelheiten.

3. Wenn Dekodierung :

   1. Ihr Programm sollte als Eingabe die Ausgabe Ihrer Kodierung Modus.
   2. Ihr Programm muss ein Bild in jedem vernünftigen Format Ihrer Wahl ausgeben, wie oben definiert, obwohl für die Ausgabe auch Vektorformate in Ordnung sind.
   3. Die Bildausgabe sollte eine Annäherung an das Eingabebild sein; je näher man dem Eingabebild kommen kann, desto besser.
   4. Der Dekodierungsprozess darf keinen Zugriff auf eine andere Ausgabe des Kodierungsprozesses haben als die oben angegebene, d. h. Sie können das Bild nicht irgendwo hochladen und die URL ausgeben, damit der Dekodierungsprozess es herunterladen kann, oder etwas Ähnliches.

4. Um die Konsistenz der Benutzeroberfläche zu gewährleisten, muss sich Ihr Programm wie folgt verhalten:

   1. Ihr Programm muss ein Skript sein, das auf einer Plattform mit dem entsprechenden Interpreter ausgeführt werden kann, oder ein Programm, das zu einer ausführbaren Datei kompiliert werden kann.
   2. Ihr Programm muss als erstes Argument entweder encode o decode um den Modus einzustellen.

   3. Ihr Programm muss Eingaben auf eine oder mehrere der folgenden Arten entgegennehmen (wenn Sie diejenige implementieren, die Dateinamen entgegennimmt, können Sie auch von stdin und stdout lesen und schreiben, wenn keine Dateinamen vorhanden sind):

      1. Nimmt die Eingabe von Standard-In und gibt die Ausgabe auf Standard-Out aus.

         my-program encode <input.png >output.txt
         my-program decode <output.txt >output.png

      2. Nimmt die Eingabe aus einer Datei, die im zweiten Argument genannt wird, und erzeugt die Ausgabe in der Datei, die im dritten Argument genannt wird.

         my-program encode input.png output.txt
         my-program decode output.txt output.png

5. Für Ihre Lösung, bitte posten:

   1. Ihren vollständigen Code und/oder einen Link dazu, der an anderer Stelle gehostet wird (wenn er sehr lang ist oder viele Dateien zum Kompilieren benötigt oder ähnliches).
   2. Eine Erklärung, wie es funktioniert, wenn es nicht sofort aus dem Code ersichtlich ist oder wenn der Code lang ist und die Leute an einer Zusammenfassung interessiert sind.
   3. Ein Beispielbild mit dem Originalbild, dem Text, auf den es komprimiert wurde, und dem dekodierten Bild.
   4. Wenn Sie auf einer Idee aufbauen, die jemand anderes hatte, nennen Sie diese bitte. Es ist in Ordnung, wenn Sie versuchen, die Idee eines anderen zu verfeinern, aber Sie muss sie zuordnen.

Leitlinien

Dabei handelt es sich im Wesentlichen um Regeln, die gebrochen werden dürfen, Vorschläge oder Bewertungskriterien:

1. Ästhetik ist wichtig. Ich beurteile und schlage vor, dass andere Leute auf der Grundlage dieser Kriterien urteilen:
   1. Wie gut das ausgegebene Bild aussieht und wie sehr es dem Original ähnelt.
   2. Wie schön der Text aussieht. Völlig willkürliches Kauderwelsch ist in Ordnung, wenn Sie ein wirklich cleveres Komprimierungsschema haben, aber ich möchte auch Antworten sehen, die Bilder in mehrsprachige Gedichte verwandeln, oder etwas ähnlich Cleveres. Beachten Sie, dass der Autor der Originallösung beschlossen hat, nur chinesische Schriftzeichen zu verwenden, weil es so besser aussieht.
   3. Interessanter Code und clevere Algorithmen sind immer gut. Ich mag kurzen, prägnanten und klaren Code, aber wirklich clevere, komplizierte Algorithmen sind auch in Ordnung, solange sie gute Ergebnisse liefern.
2. Die Geschwindigkeit ist ebenfalls wichtig, wenn auch nicht so wichtig wie die Qualität der Komprimierung des Bildes. Ich habe lieber ein Programm, das ein Bild in einer Zehntelsekunde konvertieren kann, als eines, das tagelang genetische Algorithmen ausführt.
3. Ich ziehe kürzere Lösungen längeren vor, solange sie qualitativ einigermaßen vergleichbar sind; Kürze ist eine Tugend.
4. Ihr Programm sollte in einer Sprache implementiert sein, für die es eine frei verfügbare Implementierung unter Mac OS X, Linux oder Windows gibt. Ich würde die Programme gerne ausführen können, aber wenn Sie eine großartige Lösung haben, die nur unter MATLAB oder so etwas, das ist in Ordnung.
5. Ihr Programm sollte so allgemein wie möglich sein; es sollte für so viele verschiedene Bilder wie möglich funktionieren, obwohl einige vielleicht bessere Ergebnisse liefern als andere. Im Besonderen:
   1. Ein paar Bilder in das Programm einzubauen, die es abgleicht und einen Verweis darauf schreibt, und dann das passende Bild bei der Dekodierung zu erzeugen, ist ziemlich lahm und wird nur wenige Bilder abdecken.
   2. Ein Programm, das Bilder einfacher, flacher, geometrischer Formen in ein Vektorprimitiv zerlegen kann, ist ziemlich raffiniert, aber wenn es bei Bildern jenseits einer bestimmten Komplexität versagt, ist es wahrscheinlich nicht allgemein genug.
   3. Ein Programm, das nur Bilder eines bestimmten festen Seitenverhältnisses aufnehmen kann, aber gute Arbeit damit leistet, wäre auch OK, aber nicht ideal.
   4. Sie werden feststellen, dass ein Schwarz-Weiß-Bild mehr Informationen auf kleinerem Raum darstellen kann als ein Farbbild. Andererseits kann das die Art der Bilder einschränken, für die es geeignet ist. Gesichter kommen in Schwarzweiß gut zur Geltung, aber abstrakte Designs sind vielleicht nicht so gut.
   5. Es ist völlig in Ordnung, wenn das Ausgabebild kleiner ist als das Eingabebild, aber ungefähr die gleichen Proportionen aufweist. Es ist in Ordnung, wenn Sie das Bild vergrößern müssen, um es mit dem Original zu vergleichen; wichtig ist, wie es aussieht.
6. Ihr Programm sollte eine Ausgabe produzieren, die tatsächlich durch Twitter gehen und unbeschadet wieder herauskommen könnte. Dies ist nur eine Richtlinie und keine Regel, da ich keine Dokumentation über die genaue Menge der unterstützten Zeichen finden konnte, aber Sie sollten wahrscheinlich Steuerzeichen, seltsame unsichtbare Kombinationszeichen, Zeichen für den privaten Gebrauch und Ähnliches vermeiden.

Bewertungsrubrik

Als allgemeiner Leitfaden für die Einstufung von Lösungen bei der Auswahl der von mir akzeptierten Lösung kann man sagen, dass ich die Lösungen wahrscheinlich auf einer 25-Punkte-Skala bewerten werde (dies ist sehr grob und ich werde nichts direkt bewerten, sondern dies nur als grundlegende Richtlinie verwenden):

• 15 Punkte dafür, wie gut das Kodierungsschema eine breite Palette von Eingangsbildern wiedergibt. Dies ist ein subjektives, ästhetisches Urteil
  • 0 bedeutet, dass es überhaupt nicht funktioniert, sondern jedes Mal dasselbe Bild zurückgegeben wird, oder so ähnlich
  • 5 bedeutet, dass es ein paar Bilder kodieren kann, obwohl die dekodierte Version hässlich aussieht und bei komplizierteren Bildern möglicherweise gar nicht funktioniert
  • 10 bedeutet, dass es bei einer Vielzahl von Bildern funktioniert und angenehm aussehende Bilder erzeugt, die gelegentlich unterscheidbar sein können
  • 15 bedeutet, dass es perfekte Repliken einiger Bilder erzeugt und selbst bei größeren und komplexeren Bildern etwas Erkennbares liefert. Oder sie erzeugt vielleicht keine Bilder, die gut erkennbar sind, aber sie erzeugt schöne Bilder, die eindeutig vom Original abgeleitet sind.
• 3 Punkte für die geschickte Verwendung des Unicode-Zeichensatzes
  • 0 Punkte für die einfache Verwendung aller zulässigen Zeichen
  • 1 Punkt für die Verwendung einer begrenzten Anzahl von Zeichen, die sicher über Twitter oder in einer größeren Anzahl von Situationen übertragen werden können
  • 2 Punkte für die Verwendung einer thematischen Untergruppe von Zeichen, z. B. nur Han-Ideogramme oder nur Zeichen von rechts nach links
  • 3 Punkte für etwas wirklich Tolles, wie das Erstellen von lesbarem Text oder die Verwendung von Zeichen, die wie das betreffende Bild aussehen
• 3 Punkte für clevere algorithmische Ansätze und Code-Stil
  • 0 Punkte für etwas, das 1000 Zeilen Code umfasst, nur um das Bild zu verkleinern, es als 1 Bit pro Pixel zu behandeln und es mit base64 zu kodieren
  • 1 Punkt für etwas, das eine Standardkodierungstechnik verwendet und gut und kurz geschrieben ist
  • 2 Punkte für etwas, das eine relativ neue Kodierungstechnik einführt oder das überraschend kurz und sauber ist
  • 3 Punkte für einen One-Liner, der tatsächlich gute Ergebnisse liefert, oder etwas, das bei der Grafikkodierung Neuland betritt (falls dies als geringe Punktzahl für Neuland erscheint, bedenke, dass ein so gutes Ergebnis wahrscheinlich auch eine hohe Punktzahl für die Ästhetik hat)
• 2 Punkte für Geschwindigkeit. Alles andere ist gleich, schneller ist besser, aber die oben genannten Kriterien sind alle wichtiger als Geschwindigkeit
• 1 Punkt für die Ausführung auf freier (quelloffener) Software, da ich freie Software bevorzuge (beachten Sie, dass C# weiterhin für diesen Punkt in Frage kommt, solange es auf Mono läuft, ebenso wie MATLAB-Code in Frage kommt, wenn er auf GNU Octave läuft)
• 1 Punkt für die tatsächliche Einhaltung aller Regeln. Die Regeln sind etwas umfangreich und kompliziert geworden, daher werde ich wahrscheinlich auch ansonsten gute Antworten akzeptieren, bei denen ein kleines Detail falsch ist, aber ich gebe einen Extrapunkt für jede Lösung, die tatsächlich alle Regeln befolgt

Referenzbilder

Einige Leute haben um einige Referenzbilder gebeten. Hier sind ein paar Referenzbilder, die Sie ausprobieren können. Kleinere Versionen sind hier eingebettet, sie sind alle mit größeren Versionen des Bildes verlinkt, falls Sie diese benötigen:

Preis

Ich biete eine 500 Wiederholungsprämien (plus die 50, die StackOverflow beisteuert) für die Lösung, die mir auf der Grundlage der oben genannten Kriterien am besten gefällt. Natürlich ermutige ich alle anderen, hier ebenfalls für ihre Lieblingslösungen zu stimmen.

Hinweis zur Frist

Der Wettbewerb läuft, bis das Kopfgeld aufgebraucht ist, etwa am Samstag, den 30. Mai um 18 Uhr. Ich kann nicht genau sagen, wann es enden wird; es kann zwischen 17 und 19 Uhr sein. Ich garantiere, dass ich mir alle bis 14 Uhr eingereichten Beiträge ansehe, und ich werde mein Bestes tun, um mir alle bis 16 Uhr eingereichten Beiträge anzusehen; wenn Lösungen danach eingereicht werden, habe ich möglicherweise keine Chance, sie angemessen zu prüfen, bevor ich meine Entscheidung treffen muss. Je früher Sie Ihren Beitrag einreichen, desto größer ist die Chance, dass Sie an der Abstimmung teilnehmen und mir helfen, die beste Lösung zu finden.

Unicode-Hinweise

Es hat auch einige Verwirrung darüber gegeben, welche Unicode-Zeichen genau erlaubt sind. Der Bereich der möglichen Unicode-Codepunkte ist U+0000 a U+10FFFF . Es gibt einige Codepunkte, die niemals als Unicode-Zeichen in einem offenen Datenaustausch verwendet werden dürfen; dies sind die Nicht-Zeichen und die Surrogat-Codepunkte . Nicht-Zeichen werden im Abschnitt Unidode Standard 5.1.0 Abschnitt 16.7 als die Werte U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF wobei n es 1 - 10 hexadezimal, und der Bereich U+FDD0 - U+FDEF . Diese Werte sind für die anwendungsspezifische interne Verwendung vorgesehen, und konforme Anwendungen können diese Zeichen aus dem von ihnen verarbeiteten Text entfernen. Surrogat-Codepunkte, definiert in der Datei Unicode Standard 5.1.0 Abschnitt 3.8 als U+D800 - U+DFFF werden für die Kodierung von Zeichen jenseits der Basic Multilingual Plane in UTF-16 verwendet; daher ist es unmöglich, diese Codepunkte direkt in der UTF-16-Kodierung darzustellen, und es ist ungültig, sie in irgendeiner anderen Kodierung zu kodieren. Daher lasse ich für diesen Wettbewerb jedes Programm zu, das Bilder in eine Sequenz von nicht mehr als 140 Unicode-Codepunkten aus dem Bereich U+0000 - U+10FFFF mit Ausnahme aller Nicht-Zeichen und Surrogatpaare, wie oben definiert.

Ich werde lieber Lösungen, die nur zugewiesene Zeichen verwenden, und noch bessere Lösungen, die clevere Untermengen zugewiesener Zeichen verwenden oder etwas Interessantes mit dem verwendeten Zeichensatz anstellen. Eine Liste der zugewiesenen Zeichen finden Sie in der Unicode-Zeichen-Datenbank Beachten Sie, dass einige Zeichen direkt aufgeführt sind, während andere nur als Anfang und Ende eines Bereichs aufgeführt sind. Beachten Sie auch, dass Ersatzcodepunkte in der Datenbank aufgeführt sind, aber wie oben erwähnt verboten sind. Wenn Sie bestimmte Eigenschaften von Zeichen nutzen möchten, um den von Ihnen ausgegebenen Text interessanter zu gestalten, gibt es eine eine Vielzahl von Datenbanken mit Zeicheninformationen verfügbar, wie zum Beispiel ein Liste der benannten Codeblöcke y verschiedene Zeicheneigenschaften .

Da Twitter den genauen Zeichensatz, den es unterstützt, nicht angibt, werde ich nachsichtig mit Lösungen sein, die mit Twitter nicht funktionieren, weil bestimmte Zeichen extra zählen oder bestimmte Zeichen entfernt werden. Es ist wünschenswert, aber nicht erforderlich, dass alle kodierten Ausgaben unversehrt über Twitter oder einen anderen Microblogging-Dienst wie identi.ca . Ich habe einige Dokumentationen gesehen, die besagen, dass Twitter <, > und & verschlüsselt und somit als 4, 4 bzw. 5 Zeichen zählt, aber ich habe das nicht selbst getestet, und ihr JavaScript-Zähler scheint sie nicht auf diese Weise zu zählen.

Tipps und Links

• Die Definition der gültigen Unicode-Zeichen in den Regeln ist ein wenig kompliziert. Die Auswahl eines einzelnen Zeichenblocks, wie z. B. CJK Unified Ideographs (U+4E00-U+9FCF), ist möglicherweise einfacher.
• Sie können vorhandene Bildbibliotheken verwenden, wie ImageMagick o Python Bildgebungsbibliothek für Ihre Bildmanipulation.
• Wenn Sie Hilfe benötigen, um den Unicode-Zeichensatz und seine verschiedenen Kodierungen zu verstehen, lesen Sie diese Kurzanleitung o diese ausführliche FAQ zu UTF-8 unter Linux und Unix .
• Je früher Sie Ihre Lösung einreichen, desto mehr Zeit haben ich (und andere Abstimmende), sie zu prüfen. Sie können Ihre Lösung bearbeiten, wenn Sie sie verbessern wollen. Ich werde meine Prämie auf der Grundlage der aktuellsten Version berechnen, wenn ich die Lösungen zum letzten Mal durchsehe.
• Wenn Sie ein einfach zu parsendes und zu schreibendes Bildformat wünschen (und nicht einfach ein bestehendes Format verwenden wollen), würde ich vorschlagen, dass Sie die PPM-Format . Es handelt sich um ein textbasiertes Format, das sehr einfach zu handhaben ist, und Sie können ImageMagick für die Konvertierung in und aus ihm.

Answer 1

bilddateien und python-quelltext (Version 1 und 2)

Version 1 Hier ist mein erster Versuch. Ich werde es nach und nach aktualisieren.

Ich habe das SO-Logo fast verlustfrei auf 300 Zeichen reduzieren können. Meine Technik beruht auf der Konvertierung in SVG-Vektorgrafik, so dass sie am besten mit Strichgrafiken funktioniert. Es ist eigentlich ein SVG-Kompressor, es erfordert immer noch die ursprüngliche Kunst durch eine Vektorisierung Bühne gehen.

Für meinen ersten Versuch habe ich eine Online-Dienstleistung für die PNG-Spur, aber es gibt VIELE freie und unfreie Tools, die diesen Teil übernehmen können, darunter potrace (Open-Source).

Hier sind die Ergebnisse

Original SO Logo http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png Original Entschlüsseltes SO-Logo http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png Nach der Kodierung und Dekodierung

Zeichen : 300

Zeit : Nicht gemessen, aber praktisch sofort (ohne Vektorisierungs-/Rasterisierungsschritte)

Der nächste Schritt wird sein, 4 Symbole (SVG Pfad Punkte und Befehle) pro Unicode-Zeichen einzubetten. Im Moment meine Python Build hat keine breite Zeichen Unterstützung UCS4, die meine Auflösung pro Zeichen begrenzt. Ich habe auch den maximalen Bereich auf das untere Ende der Unicode reservierten Bereich 0xD800 jedoch, sobald ich eine Liste der zulässigen Zeichen und einen Filter, um sie zu vermeiden, kann ich theoretisch schieben die erforderliche Anzahl von Zeichen so niedrig wie 70-100 für das Logo oben begrenzt.

Eine Einschränkung dieser Methode besteht derzeit darin, dass die Größe der Ausgabe nicht festgelegt ist. Sie hängt von der Anzahl der Vektorknoten/Punkte nach der Vektorisierung ab. Um diese Begrenzung zu automatisieren, muss das Bild entweder verpixelt werden (was den Hauptvorteil von Vektoren aufhebt) oder die Pfade müssen wiederholt eine Vereinfachungsphase durchlaufen, bis die gewünschte Knotenanzahl erreicht ist (was ich derzeit manuell in Inkscape mache).

Version 2

UPDATE : v2 ist nun für den Wettbewerb qualifiziert. Änderungen:

• Befehlszeilensteuerung für Eingabe/Ausgabe und Debugging
• Verwendet XML-Parser (lxml) zur Verarbeitung von SVG anstelle von Regex
• Packt 2 Pfadsegmente pro Unicode-Symbol
• Dokumentation und Bereinigung
• Unterstützung von style="fill:color" und fill="color"
• Breite/Höhe des Dokuments in ein einziges Zeichen gepackt
• Pfadfarbe in ein einziges Zeichen gepackt
• Die Farbkompression wird erreicht durch 4bits Farbdaten pro Farbe weggeworfen Farbe weggeworfen und dann per Hex-Konvertierung in ein Zeichen gepackt werden.

Zeichen : 133

Zeit : Ein paar Sekunden

v2 entschlüsselt http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png Nach Kodierung und Dekodierung (Version 2)

Wie Sie sehen können, gibt es dieses Mal einige Artefakte. Das ist keine Einschränkung der Methode, sondern ein Fehler irgendwo in meinen Konvertierungen. Die Artefakte treten auf, wenn die Punkte außerhalb des Bereichs 0,0 - 127,0 liegen, und meine Versuche, sie einzuschränken, waren nicht sehr erfolgreich. Die Lösung ist einfach, um das Bild nach unten zu skalieren, aber ich hatte Probleme mit der Skalierung der tatsächlichen Punkte eher als die Zeichenfläche oder Gruppenmatrix und ich bin zu müde, jetzt zu kümmern. Kurz gesagt, wenn Ihre Punkte in den unterstützten Bereich sind es in der Regel funktioniert.

Ich glaube, der Knick in der Mitte entsteht dadurch, dass sich ein Griff auf die andere Seite eines Griffs bewegt, mit dem er verbunden ist. Im Grunde genommen liegen die Punkte von vornherein zu dicht beieinander. Das Ausführen eines Vereinfachungsfilters über das Quellbild vor der Komprimierung sollte dies beheben und einige unnötige Zeichen einsparen.

UPDATE : Diese Methode eignet sich gut für einfache Objekte. Ich brauchte also eine Möglichkeit, komplexe Pfade zu vereinfachen und Rauschen zu reduzieren. Ich benutzte Inkscape für diese Aufgabe. Ich habe etwas Glück mit der Pflege aus unnötigen Pfade mit Inkscape hatte aber nicht die Zeit, um zu versuchen, es zu automatisieren. Ich habe einige Beispiel-SVGs mit der Inkscape-Funktion "Simplify" gemacht, um die Anzahl der Pfade zu reduzieren.

Simplify funktioniert gut, aber bei so vielen Pfaden kann es langsam sein.

autotrace Beispiel http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png cornell box 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

Thumbnails verfolgt http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png

Hier sind ein paar Bilder mit extrem niedriger Auflösung. Diese würden näher an die 140-Zeichen-Grenze heranreichen, obwohl auch hier eine clevere Pfadkomprimierung erforderlich sein könnte.

Gepflegt http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png Vereinfacht und entschlackt.

dreieckig http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_triangulated.png Vereinfacht, entschlackt und trianguliert.

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

ABOVE: Vereinfachte Pfade mit autotrace .

Leider kann mein Parser die Autotrace-Ausgabe nicht verarbeiten, so dass ich nicht weiß, wie viele Punkte verwendet werden oder wie weit man vereinfachen kann, und leider bleibt nur wenig Zeit, um es vor Ablauf der Frist zu schreiben. Es ist aber viel einfacher zu parsen als die Inkscape-Ausgabe.

Answer 2

Also gut, hier ist meine: nanocrunch.cpp und die CMakeLists.txt Datei, um sie mit CMake. Sie stützt sich auf die Zauberei++ ImageMagick API für die meisten seiner Bildbearbeitung. Es benötigt auch die GMP Bibliothek für Bignum-Arithmetik für ihre String-Kodierung.

Ich habe meine Lösung auf der Grundlage der fraktalen Bildkompression entwickelt, allerdings mit ein paar speziellen Anpassungen. Die Grundidee besteht darin, das Bild zu nehmen, eine Kopie auf 50 % zu verkleinern und nach Teilen in verschiedenen Ausrichtungen zu suchen, die nicht überlappenden Blöcken im Originalbild ähnlich sehen. Bei dieser Suche wird sehr brutal vorgegangen, aber das macht es nur einfacher, meine Änderungen einzuführen.

Die erste Änderung besteht darin, dass mein Programm nicht nur 90-Grad-Drehungen und -Spiegelungen berücksichtigt, sondern auch 45-Grad-Ausrichtungen. Das ist zwar ein Bit mehr pro Block, aber es verbessert die Bildqualität immens.

Außerdem ist die Speicherung einer Kontrast-/Helligkeitsanpassung für jede Farbkomponente eines jeden Blocks viel zu teuer. Stattdessen speichere ich eine stark quantisierte Farbe (die Palette hat nur 4 * 4 * 4 = 64 Farben), die einfach in einem bestimmten Verhältnis überblendet wird. Mathematisch gesehen ist dies gleichbedeutend mit einer variablen Helligkeits- und konstanten Kontrasteinstellung für jede Farbe. Leider bedeutet dies auch, dass es keinen negativen Kontrast gibt, um die Farben zu spiegeln.

Nach der Berechnung von Position, Ausrichtung und Farbe für jeden Block wird dieser in eine UTF-8-Zeichenfolge kodiert. Zunächst wird ein sehr großes Bignum erzeugt, um die Daten in der Blocktabelle und die Bildgröße darzustellen. Der Ansatz hierfür ist ähnlich wie bei Sam Hocevars Lösung - eine Art große Zahl mit einem Radix, der je nach Position variiert.

Dann wandelt es diese in eine Basis um, die der Größe des verfügbaren Zeichensatzes entspricht. Standardmäßig wird der zugewiesene Unicode-Zeichensatz vollständig verwendet, abzüglich der Zeichen "kleiner als", "größer als", "kaufmännisches Und", "Steuerzeichen", "Kombinationszeichen", "Ersatzzeichen" und "private Zeichen". Das ist nicht schön, aber es funktioniert. Sie können die Standardtabelle auch auskommentieren und stattdessen druckbare 7-Bit-ASCII-Zeichen (wiederum ohne die Zeichen <, > und &) oder CJK Unified Ideographs auswählen. Die Tabelle mit den verfügbaren Zeichencodes wird in einer Lauflängenkodierung mit abwechselnden Läufen von ungültigen und gültigen Zeichen gespeichert.

Wie auch immer, hier sind einige Bilder und Zeiten (gemessen auf meinem alten 3.0GHz P4), und komprimiert auf 140 Zeichen in dem oben beschriebenen, vollständig zugewiesenen Unicode-Set. Insgesamt bin ich ziemlich zufrieden damit, wie sie alle ausgefallen sind. Wenn ich mehr Zeit hätte, würde ich wahrscheinlich versuchen, die Blockigkeit der dekomprimierten Bilder zu verringern. Dennoch denke ich, dass die Ergebnisse für den extremen Kompressionsgrad ziemlich gut sind. Die dekomprimierten Bilder sind etwas impressionistisch, aber ich finde es relativ einfach zu erkennen, wie die Bits dem Original entsprechen.

Stack Overflow Logo (8,6s zum Kodieren, 7,9s zum Dekodieren, 485 Bytes):
http://i44.tinypic.com/2w7lok1.png

Lena (32,8s zum Kodieren, 13,0s zum Dekodieren, 477 Bytes):
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png

Mona Lisa (43,2s zum Kodieren, 14,5s zum Dekodieren, 490 Bytes):
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png

Bearbeiten: CJK Unified Characters

Sam fragte in den Kommentaren nach der Verwendung mit CJK. Hier ist eine auf 139 Zeichen komprimierte Version der Mona Lisa aus dem CJK Unified Zeichensatz:

http://i43.tinypic.com/2yxgdfk.png

Die Abstimmungsparameter am Anfang des Programms, die ich dafür verwendet habe, waren: 19, 19, 4, 4, 3, 10, 11, 1000, 1000. Außerdem habe ich die erste Definition von number_assigned und codes auskommentiert und die letzten Definitionen auskommentiert, um den CJK-Unified-Zeichensatz auszuwählen.

Answer 3

Meine vollständige Lösung finden Sie unter http://caca.zoy.org/wiki/img2twit . Es hat die folgenden Merkmale:

• Angemessene Komprimierungszeit (etwa 1 Minute für hohe Qualität)
• Schnelle Dekomprimierung (Bruchteil einer Sekunde)
• Beibehaltung der ursprünglichen Bildgröße (nicht nur des Seitenverhältnisses)
• Anständige Rekonstruktionsqualität (IMHO)
• Nachrichtenlänge und Zeichensatz (ASCII, CJK, Symbole) können zur Laufzeit gewählt werden
• Nachrichtenlänge und Zeichensatz werden bei der Dekomprimierung automatisch erkannt
• Sehr effizientes Verpacken von Informationen

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

Hier ist ein grober Überblick über den Verschlüsselungsprozess:

• Die Anzahl der verfügbaren Bits errechnet sich aus der gewünschten Nachrichtenlänge und dem verwendbaren Zeichensatz
• Das Quellbild wird in so viele quadratische Zellen unterteilt, wie es die verfügbaren Bits erlauben.
• Auf jede Zelle wird eine feste Anzahl von Punkten (derzeit 2) mit Anfangskoordinaten und Farbwerten angewendet
• Die folgenden Schritte werden wiederholt, bis eine Qualitätsbedingung erfüllt ist:
  • Ein Punkt wird zufällig ausgewählt
  • An diesem Punkt wird eine zufällige Operation durchgeführt (Verschiebung innerhalb der Zelle, Änderung der Farbe)
  • Wenn das resultierende Bild (siehe den Dekodierungsprozess unten) näher am Ausgangsbild liegt, wird der Vorgang beibehalten
• Die Bildgröße und die Liste der Punkte sind in UTF-8 kodiert

Und das ist der Entschlüsselungsprozess:

• Die Bildgröße und die Punkte werden aus dem UTF-8-Stream gelesen
• Für jedes Pixel des Zielbildes:
  • Die Liste der natürlichen Nachbarn wird berechnet
  • Die endgültige Farbe des Pixels wird als gewichteter Durchschnitt der Farben seiner natürlichen Nachbarn festgelegt

Was ich für den originellsten Teil des Programms halte, ist der Bitstrom. Anstatt bit-ausgerichtete Werte zu packen ( stream <<= shift; stream |= value ), packe ich willkürliche Werte, die nicht in Zweierpotenzbereichen liegen ( stream *= range; stream += value ). Dies erfordert Bignum-Berechnungen und ist natürlich viel langsamer, aber es liefert mir 2009,18 Bits anstelle von 1960, wenn ich die 20902 CJK-Hauptzeichen verwende (das sind drei Punkte mehr, die ich in die Daten einfügen kann). Und wenn ich ASCII verwende, erhalte ich 917,64 Bits statt 840.

Ich entschied mich gegen eine Methode für die anfängliche Bildberechnung, die schwere Geschütze aufgefahren hätte (Eckenerkennung, Merkmalsextraktion, Farbquantisierung...), weil ich mir anfangs nicht sicher war, ob sie wirklich helfen würde. Jetzt weiß ich, dass die Konvergenz langsam ist (1 Minute ist akzeptabel, aber trotzdem langsam), und ich werde versuchen, das zu verbessern.

Die Hauptanpassungsschleife ist lose an den Direct Binary Seach Dithering-Algorithmus angelehnt (bei dem Pixel nach dem Zufallsprinzip vertauscht oder umgedreht werden, bis ein besserer Halbton erzielt wird). Die Energieberechnung ist eine einfache Root-mean-square-Distanz, aber ich führe zuerst einen 5x5 Medianfilter auf dem Originalbild durch. Ein Gaußscher Weichzeichner würde das Verhalten des menschlichen Auges wahrscheinlich besser wiedergeben, aber ich wollte keine scharfen Kanten verlieren. Ich habe mich auch gegen simuliertes Glühen oder andere schwierig einzustellende Methoden entschieden, weil ich nicht die Zeit habe, den Prozess zu kalibrieren. Das Qualitätsmerkmal gibt also nur die Anzahl der Iterationen an, die für jeden Punkt durchgeführt werden, bevor der Encoder endet.

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

Auch wenn nicht alle Bilder gut komprimiert werden können, bin ich von den Ergebnissen überrascht und frage mich, welche anderen Methoden es gibt, um ein Bild auf 250 Byte zu komprimieren.

Ich habe auch kleine Filme von der Entwicklung des Encoderstatus aus einem zufälligen Ausgangszustand y von einem "guten" Ausgangszustand .

bearbeiten Hier sehen Sie, wie die Komprimierungsmethode im Vergleich zu JPEG aussieht. Links das obige Bild von jamoes mit 536 Byte. Rechts die Mona Lisa, die mit der hier beschriebenen Methode auf 534 Bytes komprimiert wurde (die hier erwähnten Bytes beziehen sich auf Datenbytes, d. h. die durch die Verwendung von Unicode-Zeichen verschwendeten Bits werden nicht berücksichtigt):

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

bearbeiten : Der CJK-Text wurde durch die neuesten Versionen der Bilder ersetzt.

Answer 4

Das Folgende ist keine formale Einreichung, da meine Software in keiner Weise auf die angegebene Aufgabe zugeschnitten ist. DLI kann als optimierender, verlustbehafteter Allzweck-Bildcodec beschrieben werden. Er ist der PSNR- und MS-SSIM-Rekordhalter für Bildkomprimierung, und ich dachte, es wäre interessant zu sehen, wie er bei dieser speziellen Aufgabe abschneidet. Ich habe das bereitgestellte Referenzbild der Mona Lisa verwendet und es auf 100x150 skaliert und dann mit DLI auf 344 Bytes komprimiert.

Mona Lisa DLI http://i40.tinypic.com/2md5q4m.png

Zum Vergleich mit den JPEG- und IMG2TWIT-komprimierten Beispielen habe ich DLI verwendet, um das Bild ebenfalls auf 534 Byte zu komprimieren. Das JPEG ist 536 Byte groß, IMG2TWIT 534 Byte. Die Bilder wurden zum einfachen Vergleich auf ungefähr die gleiche Größe skaliert. JPEG ist das linke Bild, IMG2TWIT ist das mittlere Bild und DLI ist das rechte Bild.

Vergleich http://i42.tinypic.com/302yjdg.png

Auf dem DLI-Bild sind einige der Gesichtszüge erhalten geblieben, vor allem das berühmte Lächeln :).

Answer 5

Der allgemeine Überblick über meine Lösung wäre folgender:

1. Ich beginne mit der Berechnung der maximalen Menge an Rohdaten, die in 140 utf8-Zeichen passen.
   • (Ich gehe davon aus, dass utf8, das ist, was das Original Website behauptete, Twitter speichere seine Nachrichten in. Dies unterscheidet sich von der obigen Problemstellung, die nach utf16 fragt).
   • Verwendung von diese utf8-FAQ Ich habe errechnet, dass ein einzelnes utf8-Zeichen aus maximal 31 Bits bestehen kann. Um dies zu erreichen, würde ich alle Zeichen verwenden, die im Bereich U-04000000 - U-7FFFFFFF liegen. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, es gibt 31 x's, also könnte ich bis zu 31 Bits kodieren).
   • 31 Bits mal 140 Zeichen ergibt 4340 Bits. Teilen Sie das durch 8, um 524,5 zu erhalten, und runden Sie es ab auf 542 Bytes .
   • (Wenn wir uns auf utf16 beschränken, könnten wir nur 2 Bytes pro Zeichen speichern, was 280 Bytes entsprechen würde).
2. Komprimieren Sie das Bild mit der standardmäßigen jpg-Komprimierung.
   • Ändern Sie die Größe des Bildes auf ca. 50x50px und versuchen Sie dann, es in verschiedenen Komprimierungsstufen zu komprimieren, bis Sie ein Bild haben, das so nah wie möglich an 542 Bytes herankommt, ohne sie zu überschreiten.
   • Dies ist ein Beispiel der Mona Lisa auf 536 Bytes komprimiert.
3. Kodiert die Rohbits des komprimierten Bildes in utf-8-Zeichen.
   • Ersetzen Sie jedes x in den folgenden Bytes: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, mit den Bits aus dem Bild.
   • Für diesen Teil müsste wahrscheinlich der größte Teil des Codes geschrieben werden, da es derzeit nichts gibt, was dies tut.

Ich weiß, dass Sie nach Code gefragt haben, aber ich möchte nicht wirklich die Zeit aufwenden, um dies tatsächlich zu programmieren. Ich dachte, dass ein effizientes Design zumindest jemand anderen dazu inspirieren könnte, es zu programmieren.

Ich denke, der Hauptvorteil der von mir vorgeschlagenen Lösung ist, dass sie so viel wie möglich bestehende Technologie wiederverwendet. Es mag Spaß machen, einen guten Kompressionsalgorithmus zu schreiben, aber es gibt garantiert einen besseren Algorithmus, der höchstwahrscheinlich von Leuten geschrieben wurde, die einen Abschluss in höherer Mathematik haben.

Ein weiterer wichtiger Hinweis ist, dass diese Lösung nicht funktioniert, wenn utf16 die bevorzugte Kodierung ist. jpegs funktionieren nicht wirklich, wenn sie auf 280 Bytes komprimiert sind. Vielleicht gibt es aber auch einen besseren Komprimierungsalgorithmus als jpg für diese spezielle Problemstellung.