Filter

Aufgabe

Die vielleicht einfachste Art, ein Bild darzustellen, ist ein Raster aus Pixeln (d. h. Punkten), von denen jeder eine andere Farbe haben kann. Für Schwarz-Weiß-Bilder benötigen wir daher 1 Bit pro Pixel, so dass 0 für Schwarz und 1 für Weiß stehen könnte, wie in der folgenden Abbildung.

In diesem Sinne ist ein Bild also nur ein Raster aus Bits - eine sogenannte Bitmap. Für buntere Bilder benötigt man einfach mehr Bits pro Pixel. Ein Dateiformat (wie BMP, JPEG oder PNG), das “24-Bit Farbtiefe” unterstützt, verwendet 24 Bits pro Pixel. (BMP unterstützt 1-, 4-, 8-, 16-, 24- und 32-Bit Farbtiefe.)

Eine 24-Bit BMP verwendet 8 Bits zur Angabe des Rotanteils eines Pixels, 8 Bits zur Angabe des Grünanteils eines Pixels und 8 Bits zur Angabe des Blauanteils eines Pixels. Wenn Sie schon einmal von RGB-Farben gehört haben, wissen Sie spätestens jetzt, was sich dahinter verbirgt: Rot, Grün, Blau.

Wenn die R-, G- und B-Werte eines Pixels in einem BMP, sagen wir, 0xff, 0x00 und 0x00 in Hexadezimal sind, ist dieser Pixel komplett rot, da 0xff (auch bekannt als 255 in Dezimal) “viel Rot” bedeutet, während 0x00 und 0x00 “kein Grün” bzw. “kein Blau” bedeuten.

In dieser Aufgabe werden wir die R-, G- und B-Werte einzelner Pixel manipulieren, um eigene Bildfilter zu erstellen, die wir auf BMP-Dateien anwenden können.

Demo

Aufgabenmaterial

Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen.

$

wget https://inf.zone/download/exercises/04/filter.zip

unzip filter.zip

rm filter.zip

cd filter

filter/ $

ls

Hintergrund

Etwas technischer

Wie Sie bereits gelernt haben, ist eine Datei nur eine Folge von Bits, die in irgendeiner Weise angeordnet sind. Eine BMP-Datei ist also im Wesentlichen auch nur eine Folge von Bits, von denen (fast) alle einfach die Farbe eines Pixels repräsentieren. Eine BMP-Datei enthält aber auch einige “Metadaten”, z.B. Informationen wie Höhe und Breite eines Bildes. Diese Metadaten werden am Anfang der Datei in Form von zwei Datenstrukturen gespeichert, die allgemein als “Header” bezeichnet werden - nicht zu verwechseln mit den Header-Dateien von C. (Diese Header haben sich übrigens im Laufe der Zeit weiterentwickelt. Wir verwenden in dieser Aufgabe die neueste Version des BMP-Formats von Microsoft, Version 4.0, die mit Windows 95 eingeführt wurde.)

Der erste dieser Header heißt BITMAPFILEHEADER und ist 14 Bytes lang. (Zur Erinnerung: 1 Byte entspricht 8 Bits.) Der zweite heißt BITMAPINFOHEADER und ist 40 Byte lang. Unmittelbar nach diesen Headern folgt die eigentliche Bitmap: ein Array von Bytes, von denen jedes Tripel die Farbe eines Pixels repräsentiert. BMP speichert diese Tripel jedoch rückwärts (d. h. als BGR). Im Falle einer 24-Bit-BMP mit 8 Bits für Blau, gefolgt von 8 Bits für Grün, gefolgt von 8 Bits für Rot. (Einige BMPs speichern auch die gesamte Bitmap rückwärts, wobei die oberste Zeile eines Bildes am Ende der BMP-Datei steht. Wir haben die BMPs dieser Aufgabe jedoch so gespeichert, wie hier beschrieben, d. h. die oberste Zeile jedes Bitmaps zuerst und die unterste Zeile zuletzt). Mit anderen Worten: Wenn wir den obigen 1-Bit-Smiley in einen 24-Bit-Smiley umwandeln und dabei Schwarz durch Rot ersetzen, würde eine 24-Bit-BMP diese Bitmap wie folgt speichern, wobei 0000ff für Rot und ffffff für Weiß steht (in der Abbildung sind alle Instanzen von 0000ff rot hervorgehoben).

Da wir diese Bits von links nach rechts, von oben nach unten in 8 Spalten dargestellt haben, können Sie den roten Smiley tatsächlich sehen, wenn Sie mit etwas Abstand darauf schauen.

Es sei noch daran erinnert, dass eine hexadezimale Ziffer 4 Bits repräsentiert. Dementsprechend wird ffffff (6 Ziffern) im Hexadezimalsystem bei der Umwandlung in das Binärsystem zu 111111111111111111111111 (24 Ziffern bzw. Bits, da 6 * 4 Bits = 24 Bits).

Abschließend ist es wichtig zu wissen, dass eine Bitmap als 2-dimensionales Array von Pixeln repräsentiert werden kann: Das Bild ist ein Array von Zeilen und jede Zeile ist ein Array von Pixeln. Auf diese Weise werden wir in dieser Aufgabe Bitmap-Bilder repräsentieren.

Bild Filter

Was bedeutet es überhaupt, ein Bild zu filtern? Das Filtern eines Bildes kann man sich so vorstellen, dass man die Pixel eines Originalbildes nimmt und jeden Pixel so verändert, dass ein bestimmter Effekt im resultierenden Bild sichtbar wird.

Überblick über den Code

Werfen wir nun einen Blick auf einige der bereitgestellten Dateien, um zu verstehen, was dort bereits vorimplementiert ist.

bmp.h

Öffnen Sie die Datei bmp.h und werfen Sie einen Blick hinein.

Sie finden darin Definitionen der bereits erwähnten Header (BITMAPINFOHEADER und BITMAPFILEHEADER). Außerdem definiert diese Datei BYTE, DWORD, LONG und WORD, Datentypen, die normalerweise in der Welt der Windows-Programmierung vorkommen. Beachten Sie, dass dies nur Aliase für Primitive sind, mit denen Sie (hoffentlich) bereits vertraut sind (siehe Aufgabe Lautstärke). Es scheint, dass BITMAPFILEHEADER und BITMAPINFOHEADER diese Typen verwenden.

Am interessantesten für Sie ist vielleicht, dass diese Datei auch eine struct namens RGBTRIPLE definiert, die drei Bytes “kapselt”: ein blaues, ein grünes und ein rotes (die Reihenfolge, in der wir erwarten, RGB-Tripel tatsächlich auf der Festplatte zu finden, siehe Abschnitt “Etwas Technischer”). Hier taucht auch der bereits zuvor erwähnte Datentyp BYTE auf. Wenn Sie am Anfang nachgeschaut haben, sollten Sie es bereits wissen - hinter dem BYTE steckt der Datentyp uint8_t (d.h. letztlich eben einfach ein Byte). Dieser wurde mit typedef lediglich hinsichtlich seines Namens umdefiniert.

Warum sind diese structs nützlich? Erinnern Sie sich daran, dass eine Datei nur eine Folge von Bytes (oder letztlich Bits) auf der Festplatte ist. Aber diese Bytes sind in der Regel so geordnet, dass die ersten Bytes für etwas stehen, die nächsten Bytes für etwas anderes, und so weiter. Es gibt “Dateiformate”, weil die Welt standardisiert hat, welche Bytes was bedeuten. Jetzt könnten wir einfach eine Datei von der Festplatte in den Arbeitsspeicher als ein großes Array von Bytes einlesen. Und wir könnten uns einfach merken, dass das Byte an array[i] für eine Sache steht, während das Byte an array[j] für eine andere steht. Aber warum sollten wir nicht einigen dieser Bytes Namen geben, damit wir sie leichter aus dem Speicher abrufen können? Genau das ermöglicht uns die struct in bmp.h. Anstatt eine Datei als eine lange Folge von Bytes zu betrachten, können wir sie stattdessen als eine Folge von structs` betrachten.

filter.c

Öffnen wir nun die Datei filter.c. Diese Datei wurde bereits für Sie geschrieben, aber es gibt ein paar wichtige Punkte, die Sie hier verstehen sollten.

Beachten Sie zunächst die Definition von filters in Zeile 10. Diese Zeichenkette teilt dem Programm mit, welche Befehlszeilenargumente für das Programm zulässig sind: b, g, r und s. Jedes dieser Argumente gibt einen anderen Filter an, den wir auf unsere Bilder anwenden können: Weichzeichnen, Graustufen, Spiegelung und Sepia.

Die nächsten Zeilen ab Zeile 34 öffnen eine Bilddatei, stellen sicher, dass es sich tatsächlich um eine BMP-Datei handelt, und lesen alle Pixelinformationen in ein 2D-Array namens image.

Scrollen Sie nach unten zur Anweisung switch, die in Zeile 101 beginnt. Beachten Sie, dass je nachdem, welchen filter wir gewählt haben, eine andere Funktion aufgerufen wird: Wenn der Benutzer den Filter b wählt, ruft das Programm die Funktion blur auf; wenn g, dann wird grayscale aufgerufen; wenn r, dann wird reflect aufgerufen; und wenn s, dann wird sepia aufgerufen. Beachten Sie auch, dass jede dieser Funktionen die Höhe des Bildes, die Breite des Bildes und das 2D-Array der Pixel als Argumente erhält.

Dies sind die Funktionen, die Sie (bald!) implementieren werden. Wie Sie sich vielleicht vorstellen können, besteht das Ziel jeder dieser Funktionen darin, das 2D-Pixel-Array (namens image) so zu bearbeiten, dass der gewünschte Filter auf das Bild angewendet wird.

Die restlichen Zeilen des Programms nehmen das überarbeitete image und schreiben es in eine neue Bilddatei.

helpers.h

Werfen Sie als nächstes einen Blick auf helpers.h. Diese Datei ist recht kurz und enthält nur die Funktionsprototypen für die Funktionen, die Sie zuvor gesehen haben.

Hier ist zu beachten, dass jede Funktion ein 2D-Array namens image als Argument nimmt, wobei image ein Array mit height Zeilen ist, und jede Zeile selbst ein weiteres Array mit width RGBTRIPLEs ist. Wenn also image das ganze Bild repräsentiert, dann repräsentiert image[0] die erste Zeile, und image[0][0] repräsentiert den Pixel in der oberen linken Ecke des Bildes.

helpers.c

Öffnen Sie nun helpers.c. Hier werden die in helpers.h deklarierten Funktionen implementiert. Diese Implementierungen fehlen aber noch! Dies ist Ihre Aufgabe.

Makefile

Zum Schluss wollen wir uns noch Makefile ansehen. Diese Datei legt fest, was passieren soll, wenn wir einen Terminalbefehl wie make filter ausführen. Während Programme, die Sie vorher geschrieben haben, auf eine einzige Datei beschränkt waren, nutzt filter nun mehrere Dateien: filter.c und helpers.c. Also müssen wir make sagen, wie es diese Datei kompilieren soll.

Versuchen Sie, filter selbst zu kompilieren, indem Sie in Ihrem Terminal folgendes ausführen:

make filter

Anschließend können Sie das Programm durch den folgenden Befehl starten:

./filter -g images/yard.bmp out.bmp

Dieser nimmt das Bild images/yard.bmp und erzeugt ein neues Bild namens out.bmp, nachdem die Pixel durch die Funktion grayscale gelaufen sind. Die Funktion grayscale ändert allerdings noch nichts, so dass das Ausgabebild genauso aussehen sollte wie das Originalbild.

Spezifikation

Implementieren Sie die Funktionen in helpers.c so, dass ein Benutzer Graustufen-, Sepia-, Spiegelungs- oder Unschärfefilter auf seine Bilder anwenden kann.

• Die Funktion grayscale sollte ein Bild in eine Schwarz-Weiß-Version desselben Bildes umwandeln.
• Die Funktion sepia sollte ein Bild in eine Sepia-Version desselben Bildes umwandeln.
• Die Funktion reflect sollte ein Bild nehmen und es horizontal spiegeln.
• Die Funktion blursollte ein Bild in eine unscharfe Version desselben Bildes umwandeln.

Sie sollten keine der Funktionssignaturen und auch keine anderen Dateien außer helpers.c ändern. Überdenken Sie stattdessen Ihr Vorgehen, falls dieses nur mit einer Änderung an einer anderen Stelle im Code funktioniert.

Details zur Umsetzung

Für die Bearbeitung dieser Aufgabe ist es nicht erforderlich, filter.c vollständig verstanden zu haben. Letztendlich müssen Sie nur die Funktionen für die einzelnen Filter implementieren. Es ist jedoch wichtig verstanden zu haben, welche Argumente den bereits angelegten Filterfunktionen übergeben werden und wie eine Bitmap und somit das übergebene 2-D-Array image des eigens definierten Typs RGBTRIPLE (welches letztlich eine Bitmap repräsentiert) aufgebaut ist.

Die Filter können unabhängig von einander implementiert werden. Beginnen sich jedoch am besten in der angegebenen Reihenfolge. Lesen Sie die entsprechenden Informationen zur Implementierung des jeweiligen Filters. Dort finden Sie auch eine kleine Einstiegshilfe.

void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all pixels

        // Take average of red, green, and blue

        // Update pixel values
}

void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all pixels
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Take average of red, green, and blue

            // Update pixel values
        }
    }
}

sepiaRed = .393 * originalRed + .769 * originalGreen + .189 * originalBlue
sepiaGreen = .349 * originalRed + .686 * originalGreen + .168 * originalBlue
sepiaBlue = .272 * originalRed + .534 * originalGreen + .131 * originalBlue

void sepia(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all pixels
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Compute sepia values

            // Update pixel with sepia values
        }
    }
}

void reflect(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all pixels
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Swap pixels
        }
    }
}

void blur(int height, int width, RGBTRIPLE image[height][width])
{
    // Create a copy of image
    RGBTRIPLE copy[height][width];
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            copy[i][j] = image[i][j];
        }
    }
}

Testen

Kompilieren Sie filter mit:

make filter

Anschließend können Sie das Programm z.B. durch den folgenden Befehl starten:

./filter -g images/yard.bmp out.bmp

Dieser nimmt das Bild images/yard.bmp und erzeugt ein neues Bild namens out.bmp, nachdem die Pixel durch die Funktion grayscale gelaufen sind.

Testen Sie unbedingt alle Ihre Filter an den mitgelieferten Bitmap-Beispieldateien! Wie oben erwähnt, können Sie b, r und s statt g verwenden, um auch die anderen Filter zu testen.

Korrektheit

Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen:

check50 -l cs50/problems/2024/x/filter/less

Style

Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit style50 zu analysieren:

style50 helpers.c