Basierend auf der sehr erfolgreichen Twitter Image Encoding Challenge bei Stack Overflow.
Wenn ein Bild 1000 Wörter wert ist, wie viel von einem Bild können Sie in 114,97 Bytes passen?
Ich fordere Sie auf, eine allgemeine Methode zum Komprimieren von Bildern in einen Twitter-Standardkommentar zu entwickeln, der nur druckbaren ASCII-Text enthält .
Regeln:
- Sie müssen ein Programm schreiben, das ein Bild aufnehmen und den codierten Text ausgeben kann.
- Der vom Programm erstellte Text darf höchstens 140 Zeichen lang sein und darf nur Zeichen enthalten, deren Codepunkte im Bereich von 32 bis einschließlich 126 liegen.
- Sie müssen ein Programm (möglicherweise dasselbe Programm) schreiben, das den codierten Text aufnimmt und eine decodierte Version des Fotos ausgibt.
- Ihr Programm kann externe Bibliotheken und Dateien verwenden, jedoch keine Internetverbindung oder Verbindung zu anderen Computern erfordern.
- Der Dekodierungsprozess kann in keiner Weise auf die Originalbilder zugreifen oder diese enthalten.
- Ihr Programm muss Bilder in mindestens einem der folgenden Formate (nicht unbedingt mehr) akzeptieren: Bitmap, JPEG, GIF, TIFF, PNG. Wenn einige oder alle Beispielbilder nicht im richtigen Format vorliegen, können Sie sie vor der Komprimierung durch Ihr Programm selbst konvertieren.
Bewertung:
Dies ist eine etwas subjektive Herausforderung, daher wird der Gewinner (irgendwann) von mir beurteilt. Ich werde mich auf einige wichtige Faktoren konzentrieren, die im Folgenden in abnehmender Wichtigkeit aufgeführt sind:
- Möglichkeit, eine Vielzahl von Bildern sinnvoll zu komprimieren, auch solche, die nicht als Beispielbild aufgeführt sind
- Fähigkeit, die Umrisse der Hauptelemente in einem Bild beizubehalten
- Möglichkeit, die Farben der Hauptelemente in einem Bild zu komprimieren
- Fähigkeit, Konturen und Farben der kleinen Details in einem Bild beizubehalten
- Kompressionszeit. Obwohl es nicht so wichtig ist, wie gut ein Bild komprimiert ist, sind schnellere Programme besser als langsamere Programme, die dasselbe tun.
Ihre Einreichung sollte die resultierenden Bilder nach der Dekomprimierung zusammen mit dem generierten Twitter-Kommentar enthalten. Wenn möglich, können Sie auch einen Link zum Quellcode angeben.
Antworten:
Ich habe meine Methode durch Hinzufügen der eigentlichen Komprimierung verbessert. Es funktioniert jetzt iterativ wie folgt:
Verkleinern Sie das Bild unter Beibehaltung des Seitenverhältnisses (wenn das Bild farbig ist, wird die Farbsättigung mit 1/3 der Breite und Höhe der Luminanz abgetastet).
Reduzieren Sie die Bittiefe auf 4 Bits pro Sample
Wenden Sie die Medianvorhersage auf das Bild an, um die Probenverteilung gleichmäßiger zu gestalten
Wenden Sie die adaptive Bereichskomprimierung auf das Bild an.
Überprüfen Sie, ob die Größe des komprimierten Bildes <= 112 ist
Das größte Bild, das in die 112 Bytes passt, wird dann als endgültiges Bild verwendet, wobei die verbleibenden zwei Bytes zum Speichern der Breite und Höhe des komprimierten Bildes sowie eines Flags verwendet werden, das angibt, ob das Bild farbig ist. Bei der Dekodierung wird der Vorgang umgekehrt und das Bild so skaliert, dass die kleinere Abmessung 128 beträgt.
Es gibt einiges an Verbesserungspotenzial, da normalerweise nicht alle verfügbaren Bytes verwendet werden. Ich bin jedoch im Begriff, die Renditen für das Downsampling und die verlustfreie Komprimierung erheblich zu verringern.
Schnelle und schmutzige C ++ - Quelle
Windows exe
Mona Lisa (13x20 Luminanz, 4x6 Chroma)
Hindenburg (21x13 Luminanz)
Berge (19x14 Luminanz, 6x4 Chroma)
2D-Formen (21 x 15 Luminanz, 7 x 5 Chroma)
quelle
Gehen
Arbeitet, indem das Bild rekursiv in Regionen unterteilt wird. Ich versuche, Regionen mit hohem Informationsgehalt zu unterteilen und die Trennlinie auszuwählen, um den Farbunterschied zwischen den beiden Regionen zu maximieren.
Jede Unterteilung wird unter Verwendung einiger Bits zum Codieren der Trennlinie codiert. Jeder Blattbereich ist als einzelne Farbe codiert.
Das Hindenburg-Bild sieht ziemlich beschissen aus, aber die anderen mag ich.
quelle
Python
Für die Codierung sind Numpy , SciPy und Scikit-Image erforderlich .
Für die Dekodierung ist nur PIL erforderlich .
Dies ist eine Methode, die auf Superpixel-Interpolation basiert. Zu Beginn wird jedes Bild in 70 Bereiche mit ähnlicher Größe und ähnlicher Farbe unterteilt. Beispielsweise ist das Landschaftsbild folgendermaßen unterteilt:
Der Schwerpunkt jeder Region befindet sich (zum nächsten Rasterpunkt in einem Raster mit nicht mehr als 402 Punkten) sowie die durchschnittliche Farbe (aus einer 216-Farben-Palette), und jede dieser Regionen ist als Zahl von 0 codiert bis 86832 , in der Lage, in 2,5 druckbaren ASCII-Zeichen gespeichert zu werden (tatsächlich 2,497 , so dass gerade genug Platz für die Codierung eines Graustufenbits bleibt ).
Wenn Sie aufmerksam sind, haben Sie vielleicht bemerkt, dass 140 / 2,5 = 56 Regionen und nicht 70, wie ich zuvor angegeben habe. Beachten Sie jedoch, dass jede dieser Regionen ein eindeutiges, vergleichbares Objekt ist, das in beliebiger Reihenfolge aufgeführt werden kann. Aus diesem Grund können wir die Permutation der ersten 56 Regionen verwenden, um für die anderen 14 zu codieren , und wir können auch ein paar Bits übrig haben, um das Seitenverhältnis zu speichern.
Insbesondere wird jede der zusätzlichen 14 Regionen in eine Zahl umgewandelt und dann jede dieser Zahlen miteinander verkettet (der aktuelle Wert wird mit 86832 multipliziert und die nächste addiert). Diese (gigantische) Zahl wird dann in eine Permutation für 56 Objekte umgewandelt.
Zum Beispiel:
wird ausgeben:
Die resultierende Permutation wird dann auf die ursprünglichen 56 Regionen angewendet . Die ursprüngliche Nummer (und damit die zusätzlichen 14 Regionen) kann ebenfalls extrahiert werden, indem die Permutation der 56 codierten Regionen in ihre numerische Darstellung umgewandelt wird.
Wenn die
--greyscale
Option mit dem Encoder verwendet wird, werden stattdessen 94 Regionen (getrennt 70 , 24 ) mit 558 Rasterpunkten und 16 Graustufen verwendet.Bei der Dekodierung wird jede dieser Regionen als 3D-Kegel behandelt, der sich von oben betrachtet bis ins Unendliche erstreckt und dessen Scheitelpunkt sich im Schwerpunkt der Region befindet (auch als Voronoi-Diagramm bezeichnet). Die Ränder werden dann zusammengemischt, um das Endprodukt zu erzeugen.
Zukünftige Verbesserungen
Die Abmessungen der Mona Lisa sind etwas unterschiedlich, da ich das Seitenverhältnis speichere. Ich muss ein anderes System verwenden.Behoben, indem angenommen wird, dass das ursprüngliche Seitenverhältnis irgendwo zwischen 1:21 und 21: 1 liegt, was ich für eine vernünftige Annahme halte.Die Hindenburg könnte stark verbessert werden. Die von mir verwendete Farbpalette enthält nur 6 Graustufen. Wenn ich einen Nur-Graustufen-Modus einführen würde, könnte ich die zusätzlichen Informationen verwenden, um die Farbtiefe, die Anzahl der Regionen, die Anzahl der Rasterpunkte oder eine beliebige Kombination der drei zu erhöhen.Ich habe--greyscale
dem Encoder eine Option hinzugefügt , die alle drei unterstützt.2d Shapes würden wahrscheinlich besser aussehen, wenn die Überblendung deaktiviert ist. Ich werde wahrscheinlich eine Flagge dafür hinzufügen.Es wurde eine Encoder-Option zur Steuerung des Segmentierungsverhältnisses und eine Decoder-Option zur Deaktivierung der Überblendung hinzugefügt.und
Das zweite ist mit der
--greyscale
Option verschlüsselt .Kodiert mit der
--greyscale
Option.Codiert mit
--ratio 60
und decodiert mit--no-blending
Optionen.encoder.py
decoder.py
my_geom.py
quelle
PHP
OK, ich habe eine Weile gebraucht, aber hier ist es. Alle Bilder in Graustufen. Farben brauchten zu viele Bits, um sie für meine Methode zu codieren: P
Mona Lisa
47 Colors Monochrome
101- Byte-Zeichenfolge.
2D-Formen
36 Farben Monochrome
105- Byte-Zeichenfolge.
Hindenburg
62 Colors Monochrome
112 Zeichen.
Berge
63 Farben Monochrom
122 Zeichen.
Meine Methode
Ich codiere meinen Bitstream mit einer Art Base64-Codierung. Bevor es in lesbaren Text kodiert wird, geschieht Folgendes.
Ich lade das Quellbild und verändere es auf eine maximale Höhe oder Breite (je nach Ausrichtung, Hoch- / Querformat) von 20 Pixel.
Als nächstes färbe ich jedes Pixel des neuen Bildes auf einer 6-Farben-Graustufen-Palette neu ein, um die bestmögliche Übereinstimmung zu erzielen.
Danach erstelle ich eine Zeichenfolge mit jeder durch die Buchstaben [AF] dargestellten Pixelfarbe.
Ich berechne dann die Verteilung der 6 verschiedenen Buchstaben in der Zeichenfolge und wähle den optimierten Binärbaum für die Codierung basierend auf den Buchstabenhäufigkeiten aus. Es gibt 15 mögliche binäre Bäume.
Ich starte meinen Bitstream mit einem einzelnen Bit,
[1|0]
je nachdem, ob das Bild groß oder breit ist. Ich benutze dann die nächsten 4 Bits im Stream, um dem Decoder mitzuteilen, welcher Binärbaum zum Decodieren des Bildes verwendet werden soll.Was folgt, ist der Bitstrom, der das Bild darstellt. Jedes Pixel und seine Farbe wird durch 2 oder 3 Bits dargestellt. Auf diese Weise kann ich für jedes gedruckte ASCII-Zeichen mindestens 2 bis 3 Pixel an Informationen speichern. Hier ist ein Beispiel eines Binärbaums
1110
, der von der Mona Lisa verwendet wird:Die Buchstaben E
00
und F10
sind die häufigsten Farben in der Mona Lisa. A010
, B011
, C110
und D111
sind am seltensten.Binäre Bäume funktionieren wie folgt: Von Bit zu Bit
0
gehen , heißt nach links gehen,1
heißt nach rechts gehen. Fahren Sie fort, bis Sie ein Blatt am Baum oder eine Sackgasse treffen. Das Blatt, auf dem Sie landen, ist der Charakter, den Sie wollen.Wie auch immer, ich codiere den Binärstich in base64-Zeichen. Beim Dekodieren der Zeichenfolge erfolgt der Vorgang in umgekehrter Reihenfolge, wobei alle Pixel der entsprechenden Farbe zugewiesen werden. Anschließend wird das Bild doppelt so groß wie die kodierte Größe skaliert (maximal 40 Pixel, entweder X oder Y, je nachdem, welcher Wert größer ist). Anschließend wird eine Faltungsmatrix erstellt auf das Ganze aufgetragen, um die Farben zu glätten.
Wie auch immer, hier ist der aktuelle Code: " Pastebin Link "
Es ist hässlich, aber wenn Sie Raum für Verbesserungen sehen, lassen Sie es mich wissen. Ich habe es zusammen gehackt, wie ich es will. I GELERNT VIEL VON DIESER CHALLENGE. Vielen Dank, dass Sie OP für die Veröffentlichung!
quelle
Mein erster Versuch. Dies ist verbesserungswürdig. Ich denke, dass das Format selbst tatsächlich funktioniert, das Problem liegt im Encoder. Das, und ich vermisse einzelne Bits in meiner Ausgabe ... meine (etwas höhere Qualität als hier) Datei endete mit 144 Zeichen, wenn noch einige übrig sein sollten. (und ich wünschte wirklich, es gäbe - die Unterschiede zwischen diesen und diesen sind spürbar). Ich habe jedoch gelernt, niemals zu überschätzen, wie groß 140 Zeichen sind ...
Ich habe es auf eine modifizierte Version der RISC-OS-Palette gebracht - im Grunde genommen, weil ich eine 32-Farben-Palette brauchte, und das schien ein guter Anfang zu sein. Ich denke, das könnte sich auch ändern.
Ich zerlege es in die folgenden Formen: und teile das Bild in Palettenblöcke (in diesem Fall 2x2 Pixel) einer Vorder- und Rückseite.
Ergebnisse:
Es folgen die Tweets, die Originale und wie der Tweet dekodiert wird
Ich weiß, dass die Farben falsch sind, aber ich mag die Monalisa. Wenn ich die Unschärfe entfernt hätte (was nicht zu schwer wäre), hätte ich einen vernünftigen kubistischen Eindruck: p
Ich muss daran arbeiten
Ich werde später versuchen, diese Probleme zu beheben und den Encoder zu verbessern. Diese zusätzlichen 20 Charaktere machen einen gewaltigen Unterschied. Ich würde sie gerne zurückhaben.
Die C # -Quelle und die Farbpalette befinden sich unter https://dl.dropboxusercontent.com/u/46145976/Base96.zip - obwohl dies im Nachhinein möglicherweise nicht einwandfrei funktioniert, wenn sie separat ausgeführt werden (da Leerzeichen in Argumenten für Programme nicht erforderlich sind) Gut).
Der Encoder benötigt auf meinem durchschnittlichen Rechner weniger als ein paar Sekunden.
quelle
Ich gab den Versuch auf, die Farbe zu behalten und wurde schwarz und weiß, da alles, was ich mit Farbe versuchte, nicht wiederzuerkennen war.
Im Grunde ist alles, was es tut, Pixel in 3 ungefähr gleiche Teile zu teilen: Schwarz, Grau und Weiß. Es hält auch nicht die Größe.
Hindenburg
Mona Lisa
Berge
Formen
Hier ist das Programm.
python compress.py -c img.png
komprimiertimg.png
und druckt den Tweet.python compress.py -d img.png
Nimmt den Tweet von stdin und speichert das Bild inimg.png
.quelle
Mein bescheidener Beitrag in R:
Die Idee ist einfach, das Raster (Datei muss in png sein) auf eine Matrix zu reduzieren, deren Zellenzahl niedriger als 140 ist. Die Tweets sind dann eine Reihe von Farben (in 64 Farben), denen zwei Zeichen vorangestellt sind, die die Anzahl der Zeilen angeben und Spalten des Rasters.
quelle
Keine vollständige Lösung, sondern nur die Methode. (Matlab)
Ich habe eine 16-Farben-Palette und eine 40-Positionen-Palette verwendet, um ein gewichtetes Voronoi-Diagramm zu erstellen . Verwendet einen genetischen Algorithmus und einen einfachen Algorithmus zum Bergsteigen, um das Bild anzupassen.
Album mit Originalbild und ich habe auch eine 16 Byte Version mit 4 Farben und festen Positionen dort. :)
(Kann ich hier die Bildgröße ändern?)
quelle
C #
Update - Version 2
Ich habe einen weiteren Versuch unternommen und jetzt MagickImage.NET ( https://magick.codeplex.com/ ) zum Codieren der JPEG-Daten verwendet. Ich habe auch einige grundlegende Codes geschrieben, um JPEG-Header-Daten besser zu verarbeiten (wie von primo vorgeschlagen) hat GuassianBlur für die Ausgabe verwendet, um die JPEG-Komprimierung etwas abzumildern. Da die neue Version besser funktioniert, habe ich meinen Beitrag aktualisiert, um die neue Methode widerzuspiegeln.
Methode
Ich habe (hoffentlich) etwas Einzigartiges ausprobiert, anstatt zu versuchen, die Farbtiefe oder Kantenidentifikation zu manipulieren oder die Bildgröße auf unterschiedliche Weise zu reduzieren. Ich habe den JPEG-Algorithmus bei maximaler Komprimierung für verkleinerte Versionen von verwendet die Bilder, dann durch Eliminieren von allem, außer dem "StartOfScan" ( http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure ) und ein paar wichtigen Header-Elementen, kann ich die Größe auf einen akzeptablen Wert reduzieren. Die Ergebnisse sind für 140 Zeichen tatsächlich ziemlich beeindruckend, was mir neuen Respekt für JPEGs verschafft:
Hindenburg
Berge
Mona Lisa
Formen
Code
Version 2 - http://pastebin.com/Tgr8XZUQ
Ich fange wirklich an, ReSharper zu verpassen + Ich habe eine Menge Dinge zu verbessern, immer noch viel hartes Programmieren, aber interessant, damit es in VS läuft.
Original (veraltet) - http://pastebin.com/BDPT0BKT
Immer noch ein bisschen chaotisch.
quelle
Python 3
Methode
Zunächst verkleinert das Programm das Bild und verkleinert es erheblich.
Zweitens wandelt es die RGB-Werte in Binärwerte um und schneidet die letzten Ziffern ab.
Dann konvertiert es die Daten der Basis 2 in die Basis 10, wo es die Abmessungen des Bildes hinzufügt.
Dann konvertiert es die Daten in der Basis 10 in die Basis 95 und verwendet dabei alle gefundenen ASCII-Werte. Allerdings konnte ich / x01 und ähnliches nicht verwenden, da es die Funktion negieren konnte, mit der die Textdatei geschrieben wurde.
Und (aus Gründen der Mehrdeutigkeit) erfolgt die Dekodierung in umgekehrter Reihenfolge.
compress.py
decode.py
Der Schrei
Mona Lisa
Kugeln
quelle