Komprimierung von Schwarz-Weiß-Pixeldaten auf einem 8-Bit-Mikroprozessor

Question

Ich muss die Daten eines 102x64 Pixel großen schwarz-weißen LCD-Bildschirms mit einem 8-Bit-Mikroprozessor komprimieren. Die Daten kommen in Form eines Strom wie unten dargestellt:

unsigned char data[8][102] = 
        {
            {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x38, 0x28, 0xfe, 0x82, 0xba, 0xba, 0x82, 0xba, 0xba, 0x82, 0xba, 0xba, 0x82, 0xfe, 0x00, 
            0x00, 0x38, 0x44, 0x44, 0x38, 0x00, 0x40, 0x4c, 0x50, 0x60, 0x00, 0x28, 0x00, 0x40, 0x7c, 0x00, 
            0x4c, 0x54, 0x54, 0x24, 0x00, 0x00 },
            {0x00, 0x20, 0x20, 0x20, 0x3f, 0x3f, 0x20, 0x20, 0x20, 0x00, 0x6f, 0x6f, 0x00, 0x0f, 0x0f, 0x08, 
            0x08, 0x0f, 0x0f, 0x08, 0x08, 0x0f, 0x07, 0x00, 0x07, 0x0f, 0x0a, 0x0a, 0x0e, 0x06, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
            {0x00, 0x00, 0x00, 0x00, 0xc0, 0xcf, 0x0e, 0x0d, 0x0d, 0x0d, 0xce, 0xcf, 0x0d, 0xcd, 0xcd, 0x0d, 
            0x0c, 0xcf, 0xc0, 0x00, 0x00, 0xc0, 0xc2, 0x02, 0x83, 0xc0, 0x40, 0x40, 0x41, 0x42, 0x02, 0x02, 
            0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x03, 0x00, 0x00, 0x01, 0x02, 0x02, 
            0x02, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
            {0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0x07, 0xfb, 0xfb, 0xfb, 0x07, 0xff, 0xff, 0xfb, 0xc7, 0x3f, 
            0xff, 0xff, 0x00, 0x84, 0x00, 0x00, 0x04, 0x04, 0xfc, 0x04, 0x04, 0x00, 0x04, 0x0c, 0x14, 0x24, 
            0xc4, 0x00, 0x00, 0x84, 0x00, 0x00, 0x30, 0x50, 0x90, 0x10, 0xfc, 0x10, 0x00, 0xf8, 0x04, 0x04, 
            0x04, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
            {0x00, 0x3f, 0x3f, 0x20, 0x20, 0x30, 0x1f, 0x0f, 0x00, 0x01, 0x0b, 0x0a, 0x0a, 0x0f, 0x07, 0x00, 
            0x08, 0x3f, 0x3f, 0x08, 0x08, 0x00, 0x07, 0x0f, 0x0a, 0x0a, 0x0e, 0x06, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
            {0x00, 0xc0, 0xc0, 0x40, 0x40, 0xc0, 0x81, 0x02, 0x02, 0x82, 0xc1, 0x40, 0x42, 0xc2, 0xc3, 0x00, 
            0x00, 0xc0, 0xc0, 0x40, 0x40, 0x00, 0x81, 0xc2, 0x42, 0x42, 0x41, 0x40, 0x02, 0x02, 0x03, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x02, 0x02, 0x01, 0x00, 0x01, 0x02, 0x02, 0x02, 
            0x01, 0x00, 0x01, 0x02, 0x02, 0x02, 0x01, 0x00, 0x01, 0x02, 0x02, 0x02, 0x01, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
            {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0x04, 0x04, 0xfc, 0x04, 
            0x04, 0x00, 0x00, 0x04, 0x00, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0x04, 0x04, 0xfc, 0x04, 
            0x04, 0x00, 0x00, 0x04, 0x00, 0x00, 0x04, 0x0c, 0x14, 0x24, 0xc4, 0x00, 0xf8, 0x04, 0x04, 0x04, 
            0xf8, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
            {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }
        };

Aber ich bin unfähig um sie vollständig in den Arbeitsspeicher des Mikroprozessors zu integrieren. Ich kann nur in Abschnitten von 51 oder weniger Byte darauf zugreifen.

Für die Neugierigen unter Ihnen: Die Daten ergeben das folgende Bild:

Ich möchte die Daten über eine langsame serielle Schnittstelle übertragen. Es dauert viel zu lange, die Daten so zu senden. Mein Ziel ist es, die Geschwindigkeit zu verdoppeln, indem ich die Daten um den Faktor 2 verkleinere. Eine normale Zip-Kompression erreicht den Faktor 2,46, indem sie die 816 Byte auf 332 Byte komprimiert.

Meine erste Idee war, die Daten zu verkleinern, indem ich die Bytes, die den gleichen Wert haben, in einer Sequenz gruppiere. Zum Beispiel die Daten {0x20, 0x20, 0x20, 0x3f, 0x3f, 0x20, 0x20, 0x20} wird von 8 Byte auf 6 Byte komprimiert und in diese {{0x20, 0x03}, {0x3f, 0x02}, {0x20, 0x03}} .

Gibt es eine Methode, die besser für schwarz-weiße Pixeldaten und die begrenzten Möglichkeiten eines 8-Bit-Mikroprozessors geeignet ist?

Answer 1

Faxgeräte verwenden eine Kombination aus Huffman-Komprimierung für Zeilen, und die folgenden Zeilen kodieren nur die Unterschiede zur letzten vollständigen Zeile.

Das Prinzip ist dasselbe wie bei der Videokomprimierung: Man komprimiert ein Vollbild und komprimiert dann die Unterschiede für die nächsten paar Bilder (das ist natürlich nicht 100%ig korrekt).

Das sollte die Komprimierung verbessern, aber der Code wird dadurch etwas komplexer.

Ich würde mit der Huffman-Komprimierung beginnen, da das Bild definitiv nicht zufällig ist und sich gut komprimieren lassen sollte. Ich glaube nicht, dass Faxgeräte eine riesige Menge an Speicher haben, also könnte es möglich sein, es hineinzupressen.

Answer 2

Ich weiß nicht viel über Kompression, aber für etwas, das noch effektiver als RLE ist und speziell für ein LCD entwickelt wurde, würde ich vielleicht so etwas in Betracht ziehen (ich erfinde diesen Algorithmus, während ich schreibe):

{Tag, x-Koordinate, y-Koordinate, Daten, Daten, Daten, ..., Tag, x-Koordinate, ... und so weiter.

Dies basiert auf der Idee, dass alles auf dem LCD standardmäßig leer ist und Sie nur die Daten eingeben. So entfällt die Notwendigkeit der Speicherung einer Menge von 0x00. Stattdessen kann der Wert 0x00 als Markierung verwendet werden, um zu beschreiben, wo ein neues Datensegment beginnt und endet.

Sie würde folgendermaßen aussehen:

uint8_t data[N] = {0x00, 0x05, 0x01, 0xFF, 0xFF, 0x00, 0x01, 0x02, 0xAA, 0xBB, 0xCC };

Dadurch werden die Daten FFFF an den Stellen (5,1) bis (6,1) auf der LCD-Anzeige ausgegeben, und dann die Daten AABBCC an den Stellen (1,2) bis (3,2). Ein Umbruch am Ende der Zeile könnte leicht implementiert werden. 0x00 kann als eine der Koordinaten erscheinen, aber niemals als Daten.

Answer 3

Ich habe einen Test mit der RLE Methode (die wirklich einfach zu implementieren war) und komprimierte ein ähnliches Bild von 816 auf 446 Byte (Faktor 1,82) - das ist mehr, als ich von einer so einfachen Methode erwartet hatte.

Answer 4

Wenn Sie eine Huffman-Komprimierung in Betracht ziehen, können Sie eine Vorverarbeitung wie Delta-Code oder eine Verschiebung der Daten nach vorne versuchen. Ein Delta-Code zeichnet die Differenz zum nächsten Byte auf und ein mtf vertauscht die Daten mithilfe eines Wörterbuchs. Er kann die Kompressionsrate eines statistischen Kompressors verbessern. Wenn ein Huffman zu teuer ist, können Sie einen Golomb-Code in Betracht ziehen. Mtf wird in bzip2 vor einer BWT-Transformation verwendet.