Histogramm eines Bildes in einen Barcode verwandeln.

Auf der Suche nach Rätseln für meinen Mystery-Adventskalender stellte ich mir die Frage, ob es möglich sei, das Histogramm eines Bildes so zu verändern, dass ein verwertbares Muster entsteht, beispielsweise Morsecode, oder eben ein Barcode. Wie ich herausfand ist dies tatsächlich möglich und soll nachfolgend erläutert werden.

Exkurs: Histogramm

Ein Histogramm ist nichts weiter, als eine grafische Darstellung der Häufigkeit verschiedener Merkmale. In unserem konkreten Fall geht es um die Häufigkeit der verschiedenen Grau- bzw. Farbwerte eines Bildes.

Betrachten wir z.B. das nachfolgende Bild eines Pandas:

pandaUnschwer erkennt man, dass das Bild zum Großteil aus weißen und schwarzen Flächen besteht und nur wenige Graustufen dazwischen. Entsprechend sieht das dazugehörige Histogramm aus:

Im schwarzen (dunklen) Bereich (links) haben wir einen Peak, sowie im rechten (hellen) Bereich.

Die Idee

Wie wir nun wissen, stellt ein Histogramm die Häufigkeitsverteilung (der Graustufen) dar. Möchten wir der Sache nun eine Form verleihen, die weiter verarbeitet werden kann – z.B. die eines Barcodes – so müssen wir dafür sorgen, dass wir an bestimmten Stellen einen Maximalausschlag haben und an anderen Stellen muss die Häufigkeit Null betragen.

So soll unser Histogramm später einmal aussehen.
So soll unser Histogramm später einmal aussehen.

D.h. alles was wir tun müssen, ist die Verteilung der Farben so zu manipulieren, dass ein entsprechendes Histogramm entsteht. Alternativ kann natürlich auch ein passendes Bild generiert werden, allerdings ist es deutlich spannender, ein bereits bestehendes Bild zu nehmen und selbiges zu verändern.

Algorithmus

Nachfolgend soll der Algorithmus zur Erstellung eines gewünschten Histograms grob skizziert werden. Es gibt sicherlich hier und da Optimierungspotential, aber hier geht es nicht um die perfekte Lösung, sondern das Prinzip soll verdeutlicht werden. Weiter unten im Artikel wurden alle Schritte mittels Python-Scripte realisiert, wer sich also für eine Implementation interessiert, der kann dort gerne nachschauen.

Genauso wie in meinem Adventskalender verwende ich nachfolgend dieses Bild: https://commons.wikimedia.org/wiki/File:Frischer_neuschnee.jpg

Sämtliche Projektdateien können hier heruntergeladen werden: Projektdateien

Schritt 1: Vorbereiten des Barcodes

Da wir später mit einem 8-Bit Graustufen-Bild arbeiten werden, stehen uns 256 Abstufungen zur Verfügung, was ein ebenso breites Histogramm (256 Pixel) erzeugt. Dies ist die Vorgabe für unseren Barcode. Haben wir einen größeren Barcode muss dieser verkleinert werden und es ist möglich, dass Informationen verloren gehen, haben wir einen kleineren Barcode, kann es ebenso vorkommen, dass Striche ungleichmäßig skaliert werden und je nach Scanner nicht mehr erkannt werden. Wir sollten also penibel darauf achten, dass unser gewünschter Barcode eine Breite von 256 Pixeln besitzt, bzw. testen, in wie weit sich der Barcode vergrößern/verkleinern lässt. Alternativ kann ein kleinerer Barcode auch rechts und links mit weißen Flächen aufgefüllt werden. Zu beachten ist, dass wir einen Barcode wählen sollten, der in etwa die Farbverteilung des Originalbildes widerspiegelt, da es sonst zu starkem Rauschen kommen kann, aber dazu später mehr.

Für diese Anleitung verwende ich folgenden Barcode:

barcode_1.png
barcode_1.png

Haben wir den gewünschten Barcode in Form gebracht, so müssen wir noch die schwarzen Pixel zählen, also wie viele schwarze Pixel der Barcode pro Zeile besitzt. Dies ist nicht zu verwechseln mit der Anzahl der schwarzen Balken, da ein Balken durchaus mehrere Pixel breit sein kann! In diesem Fall sind es 129 schwarze Pixel pro Zeile.

Schritt 2: Vorbereiten des Originalbildes

Da wir in unserem Histogramm später einmal gleichhohe Balken haben möchten, muss die Anzahl der Pixel pro Farbwert gleich sein. D.h. wollen wir z.B. am rechten Ende (weiß) und am linken Ende (schwarz) unseres Histogramms einen Balken haben, so muss die Anzahl der schwarzen Pixel exakt genauso groß sein, wie die Anzahl der weißen Pixel und natürlich müssen auch alle Graustufen dazwischen, die später mit einem Balken versehen werden sollen, die gleiche Anzahl an Pixeln besitzen. Kurzum: Grundvoraussetzung ist, dass die Anzahl der Pixel unseres Originalbildes ganzzahlig durch die Anzahl der schwarzen Pixel im Barcode teilbar ist.

Rechenbeispiel:

Unser Originalbild hat – so wie wir es auf Wikipedia herunterladen – eine Abmessung von 3264 x 2448 Pixeln, besteht also aus insgesamt 7.990.272 Pixeln. Teilen wir dies nun durch die Anzahl der schwarzen Pixel im Barcode (129), erhalten wir 61940,093. Das geht, wie wir sehen, nicht auf und wir müssen das Bild so beschneiden, bzw. verkleinern, dass es passt. Da wir ohnehin nicht mit einem solch großen Bild arbeiten wollen, verkleinern wir das Bild ein wenig auf  1290 x 968 Pixel. Die Gegenprobe ergibt nun: (1290 * 968) / 129 = 9680.

Somit wissen wir nun, dass jeder Farbwert im Bild genau 9680mal vorkommen muss.

Schritt 3: Farbwerte zählen

Nun müssen wir die Ausgangssituation ermitteln. Wie viele Pixel sind momentan von jeder Farbe vorhanden? Spätestens hier benötigen wir ein Tool, denn das macht von Hand keinen Spaß mehr 😉

Nach der Auswertung ergibt sich folgendes Bild:

Auswertung

Wie man gut erkennen kann gibt es keinen einzigen Farbwert, der bereits in der gewünschten Menge (9680) vorliegt. Das müssen wir im nächsten Schritt ändern.

Schritt 4: Anzahl der Pixel anpassen

Im letzten Schritt gehen wir nun noch einmal alle Pixel durch und schauen pro Pixel nach, wie viele weitere Pixel mit dem selben Farbwert vorhanden sind und ob dieser Farbwert überhaupt gewünscht ist. Sind es weniger Pixel als der Soll-Wert, so ist dies vorläufig ok und wir gehen zum nächsten Pixel weiter. Sind es allerdings mehr als der Sollwert, müssen wir dem Pixel eine andere Farbe verpassen.

Fraglich ist nun, wie wir einen Farbwert finden, mit welchem wir den aktuellen ersetzen können. Ganz einfach: Wir schauen uns die anderen Farben in der Umgebung des Farbwertes an und wählen eine Farben, die so dicht wie möglich an der Farbe liegt, die ersetzt werden soll.

Beispielhaft soll dies an Farbwert 171 (siehe Tabelle oben) erklärt werden:

Angenommen wir finden beim Durchlauf nun einen Pixel mit dem Farbwert 171, so schauen wir in unserer Soll-Spalte nach und stellen fest, dass wir keine Pixel in dieser Farbe wünschen. Wir schauen uns deshalb die benachbarten Farbwerte, also 170 und 172, an und stellen fest, dass diese auch nicht erwünscht sind. Wir gehen also einen Schritt weiter und schauen uns den Farbwert 169 an. Diesen wollen wir im Ausgabebild haben (Sollwert 9680). Er kommt also als Austauschfarbwert in Frage. Zu klären ist noch, ob wir noch genügend Kapazitäten haben, um 171 durch 169 zu ersetzen. Deshalb schauen wir nun in der Ist-Tabelle nach und sehen, dass wir erst 3380 Pixel mit diesem Farbwert haben, also deutlich weniger als 9680 und wir können das Pixel an der aktuellen Stelle mit einem Wert von 169 füllen.

Unsere Tabelle sieht dann hinterher so aus:

Dies machen wir nun für jedes Pixel im Bild und sobald wir einmal durch sind, sind wir auch schon fertig.

Kapitel 5: Das große ABER

So einfach sich das ganze nun in der Theorie anhören mag, so schwer ist es in Wirklichkeit! Denn die größte Herausforderung, die man bewältigen muss besteht darin, dass nicht jedes Bild optimal für den gewünschten Barcode geeignet ist und so teilweise Pixel mit deutlich anderen Farbwerten genommen werden müssen. Zudem tritt je nach Bild ein weiteres Problem unterschiedlich stark zu Tage: Zu Ende hin, also am unteren Rand des Bildes sind benachbarte Farben ‚verbraucht‘ und es müssen weit entfernte Farben genommen werden, was sich in hässlichen Balken niederschlägt:

Am unteren Rand des Bildes kann man gut die entstehenden "Streifen" erkennen.
Am unteren Rand des Bildes kann man gut die entstehenden „Streifen“ erkennen.

Nun gibt es mehrere Möglichkeiten, diesem Problem entgegenzuwirken. Eine Möglichkeit besteht z.B. darin, das Ausgangsbild nachzubearbeiten, sodass die Verteilung der Farben besser passt. Eine weitere Möglichkeit besteht darin, eine ganze Reihe an Bildern durchzutesten und das mit dem geringsten Fehler herauszupicken. Sicherlich gibt es noch weitere – ambitioniertere – Möglichkeiten, aber dazu fehlte mir die Muse. Stattdessen wählte ich einen ganz anderen Weg: Anstatt Reihe für Reihe, Zeile für Zeile durch das Bild zu gehen, randomisierte ich die Reihenfolge der Abarbeitung und verteilte so den Fehler über das ganze Bild. Heraus kam ein ‚verrauschtes‘ aber ansonsten ‚fehlerfreies‘ Bild:

out_shuffled

Anhang: Python-Scripte

Für sämtliche Scripte benötigen wir die Bibliothek PIL (Pillow)

Script 1: Schwarze Pixel zählen

Script 2: Bildgröße überprüfen

Script 3: Farbwerte zählen

Script 4b: Histogramm anpassen (sequentiell)

Script 4b: Histogramm anpassen (randomisiert)

No comments have been made. Use this form to start the conversation :)

Leave a Reply

Facebook
Facebook