Beispiel 1 - Bildverarbeitung
Übersicht: Beispiel 1 - Bildverarbeitung
Einleitung
Dieses Beispiel soll Listen zur Repräsentation, Verarbeitung und Darstellung von Bildern nutzen. Dabei soll soweit wie möglich von der Implementierung und der tatsächlichen Datenrepräsentation abstrahiert werden. Konkretes Ergebnis soll dabei eine Bibliothek von Bildverarbeitungsfunktionen sein.
Bilder bestehen aus Zeilen (sind eine Liste von Zeilen), Zeilen wiederum sind nichts anderes als eine Folge von Bildelementen (eine Liste von Bildelementen). Wenn wir uns als Bildelement einfach auf eine Darstellung mit Zeichen (Datentyp Char) festlegen, können wir unter Zuhilfenahme von Listen Bilder direkt modellieren.
01 type Row = [Char]
02 type Picture = [Row]
03
04 white = ´.´
05 black = ´#´
|
1-1.txt |
Codebeispiel 1
Wir beschränken uns in diesem Beispiel auf Schwarz/Weiß-Bilder, die wir mit ´.´ für Weiß bzw. mit ´#´ für Schwarz darstellen. Es sei an dieser Stelle erwähnt, daß die Festlegung auf diese beiden Zeichen (wie an anderer Stelle auch die Festlegung, daß alle Zeilen eines Bildes gleich lang sein müssen) informeller Natur ist und nicht durchgesetzt wird. Nachfolgend definieren wir zwei einfache Funktionen zur Bestimmung von Höhe und Breite eines Bildes:
01 -- Breite eines Bildes
02 width :: Picture -> Int
03 width x
04 | null x = 0
05 | otherwise = length (x!!0)
06
07 -- Höhe eines Bildes
08 height :: Picture -> Int
09 height = length
10
11 -- Ein Bild darstellen
12 printPicture :: Picture -> IO ()
13 printPicture = putStr . concat . map (++"\n")
|
1-2.txt |
Codebeispiel 2
Die Breite eines Bildes entspricht der Länge der Zeilen eines Bildes - da die Zeilen per Definition alle gleich lang sein sollen, können wir einfach die Länge der ersten Zeile berechnen. Problematisch wird dies bei der Darstellung eines leeren Bildes - dieses könnte gleichermaßen mit [] (ein leeres Bild) als auch mit [[]] (ein Bild mit einer einzigen leeren Zeile) repräsentiert werden. Um bei [] einen Fehler zu vermeiden (in Ermangelung einer ersten Zeile würde length (x!!0) hier fehlschlagen), wurde der Fall null x eingeführt. Die Höhe eines Bildes ist trivialerweise die Anzahl seiner Zeilen. Das Darstellen eines Bildes mittels Zeichen (printPicture) besteht aus dem Erweitern jeder Zeile (die Zeilen sind typgleich mit Strings) um das Zeilensprungsymbol (map (++"\n")), dem Konkatenieren aller Zeilen (Strings) zu einem einzigen String und schließlich dessen Ausgabe.
Unäre Bildoperationen (Picture -> Picture)
Die folgenden Funktionen dienen der Transformation eines Bildes in ein anderes Bild.
01 -- Bild an der horizontalen Achse spiegeln
02 flipH :: Picture -> Picture
03 flipH = reverse
04
05 -- Bild an der vertikalen Achse spiegeln
06 flipV :: Picture -> Picture
07 flipV pic = [ reverse line | line <- pic ]
08 oder
09 flipV = map reverse
|
1-3.txt |
Codebeispiel 3
Das Spiegeln eines Bildes an der horizontalen Achse ist trivial - es entspricht der Umkehrung der Reihenfolge der Zeilen des Bildes, was sich mit der reverse-Funktion unter vollständiger Abstraktion von den Listenelementen realisieren läßt. Das Spiegeln an der vertikalen Achse entspricht der Umkehr der Reihenfolge aller Elemente jeder Zeile, also gerade der Anwendung der reverse-Funktion auf jede Zeile (mit map). Alternativ kann flipV mit einem Erzeugungsschema umgesetzt werden, das über alle Zeilen des Ausgangsbildes traversiert und sie für das neue Bild jeweils umdreht.
01 -- Drehen des Bildes um 180 Grad
02 rotate :: Picture -> Picture
03 rotate pic = flipV (flipH pic)
04 oder
05 rotate = flipV . flipH
06
07 -- Drehen eines Bildes um 90 Grad
08 rotate90 :: Picture -> Picture
09 rotate90 p
10 = flipV [[ x!!y | x <- p ] | y <- [0..width p-1]]
|
1-4.txt |
Codebeispiel 4
Das Drehen um 180 Grad ist wieder ein triviales Beispiel, es ist äquivalent zum Spiegeln an den horizontalen und vertikalen Achsen (in beliebiger Reihenfolge). Dies ist ein weiteres Beispiel für weitreichende Abstraktion, wir führen die rotate-Funktion auf zwei andere Funktionen zurück und müssen über die Darstellung der Bildelemente und die Implementierung der flip-Funktionen nichts wissen. Die Drehung um 90 Grad ist komplexer: Hier müssen wir die Zeilen des Ausgangsbildes zu Spalten des neuen Bildes machen. Dazu erzeugen wir im Beispiel eine Liste von 0 bis zur Breite des Ausgangsbildes (also eine Liste von Spalteindices) und traversieren für jeden Index aus dieser Liste über die Zeilen des Ausgangsbildes. Die Zeilen des neuen Bildes werden durch Anwendung des aktuellen Index auf die Ausgangszeilen berechnet - für die erste Zeile nehmen wir den Index 0 aller Zeilen ab Zeile 0. Ein Problem bleibt dabei: Normalerweise müßte bei einer 90 Grad-Drehung das links unterste Bildelement zum links obersten Element werden, bisher jedoch würde es nach rechts oben verschoben (es gehört zur letzten Zeile, diese wird als letztes verarbeitet und erzeugt somit das letzte Element der ersten Zeile). Dies wird einfach durch eine Spiegelung an vertikalen Achse korrigiert.
01 -- Skalieren eines Bildes um einen Ganzzahlwert
02 scale :: Int -> Picture -> Picture
03 scale x
04 | (x >= 0)
05 = concat . map (replicate x . concat . map (replicate x))
06 | otherwise = error "Negative scaling factor"
07
08 -- Invertieren eines Bildes
09 invert :: Picture -> Picture
10 invert pic = [ [ invertChar ch | ch <- line] | line <- pic ]
11 oder
12 invert pic = [ invertLine line | line <- pic ]
13 oder
14 invert = map (map invertChar)
15
16 -- Invertieren eines Zeichens
17 invertChar :: Char -> Char
18 invertChar ch = if ch == ´.´ then ´#´ else ´.´
|
1-5.txt |
Codebeispiel 5
Das Skalieren vergrößert ein Bild um einen positiven Ganzzahlfaktor x. Dazu müssen alle Bildelemente horizontal um x vervielfacht werden und die entstehenden Elementfolgen müssen vertikal um x vervielfacht werden (für x=4: [[#]] -> [[####]] -> [[####],[####],[####],[####]]). Dazu wird auf jede Zeile eine Funktion angewandt, die a) jedes Bildelement um den Skalierungsfaktor vervielfacht (map (replicate x)), b) die entstehenden Elementlisten wieder zu einer einzigen Liste zusammenfaßt (concat) und c) die gesamte Zeile um x vervielfacht. Abschließend werden die entstandenen Zeilenlisten wieder zu einer einzigen Zeilenliste (dem fertigen Bild) zusammengefaßt.
Das Invertieren eines Bildes wird auf die invertChar-Funktion zurückgeführt, die aus einem ´.´ ein ´#´ macht und vice versa. Diese Funktion muß auf jedes Bildelement angewendet werden, entweder mit map (map ...) oder aber mit einem Erzeugungsschema, das über die Zeilen und anschließend für jede Zeile über die Zeichen traversiert.
Binäre Bildoperationen (Picture -> Picture -> Picture)
Die folgenden Funktionen dienen der Erzeugung eines neuen Bildes aus zwei Ausgangsbildern.
01 -- zwei Bilder übereinander positionieren und konkatenieren
02 above :: Picture -> Picture -> Picture
03 above = (++)
04
05 -- zwei Bilder nebeneinander positionieren und zu einem neuen zusammenfügen
06 sideBySide :: Picture -> Picture -> Picture
07 sideBySide picL picR
08 = [ lineL ++ lineR | (lineL,lineR) <- zip picL picR ]
09 oder
10 sideBySide = zipWith (++)
|
1-6.txt |
Codebeispiel 6
above läßt sich analog zu flipH leicht auf eine einzige Listenfunktion zurückführen, hier die Konkatenation - die Zeilen des zweiten Bildes werden den Zeilen des ersten einfach "angehängt". sideBySide kann wieder auf zwei Weisen implementiert werden: Ein Erzeugungsmuster kann über eine mittels zip erzeugte Liste von Tupeln aus korrespondierenden Zeilen der Ausgangsbilder laufen und die Zeilen eines jeden Tupels zu den Zeilen des Ergebnisbildes konkatenieren; alternativ können zip und Konkatenation auch zusammengefaßt werden zu zipWith (++), nichts anderem als dem Verknüpfen aller korrespondierenden Zeilen über die Konkatenation.
01 -- zwei Bilder überlagern
02 superimpose :: Picture -> Picture -> Picture
03 superimpose = zipWith (zipWith superimposeChar)
04
05 -- zwei Zeichen addieren
06 superimposeChar :: Char -> Char -> Char
07 superimposeChar ´.´ ´.´ = ´.´
08 superimposeChar _ _ = ´#´
09
10 -- Zwei Bilder überlagern
11 superimposePic :: Picture -> Picture -> Picture
12 superimposePic = zipWith superimposeLine
13
14
15 -- Zwei Zeilen überlagern
16 superimposeLine :: Row -> Row -> Row
17 superimposeLine = zipWith superimposeChar
|
1-7.txt |
Codebeispiel 7
superimpose entspricht der Addition von zwei Bildern, superimposeChar liefert dazu stets Schwarz (#), außer beide Ausgangszeichen sind Weiß (.). Die Umsetzung für ganze Bilder ist simpel und entspricht prinzipiell dem sideBySide, es werden jedoch statt ganzer Zeilen einzelne Bildelemente verknüpft. Dazu wird lediglich eine Schachtelung für das zipWith benötigt ("Verknüpfe zwei Zeilen zu einer Zielzeile, indem Du alle Elemente der Quellzeilen über superimposeChar verknüpfst").
Bilder mit Position
Es soll eine Erweiterung des ursprünglichen Bildmodells betrachtet werden, die eine Positionsinformation beinhaltet. Die neue Repräsentation wird bildtechnisch vollständig auf das bereits erarbeitete Modell zurückgeführt und lediglich um ein Ganzzahl-Tupel bereichert, das die Position x/y speichert.
01 type Position = (Int,Int)
02 type Image = (Picture,Position)
03
04 -- Ein Bild mit Positionsinformation konstruieren
05 makeImage :: Position -> Picture -> Image
06 makeImage x y = (y,x)
07
08 -- Die Position eines positionierten Bildes neu definieren
09 changePosition :: Position -> Image -> Image
10 changePosition z (x,y) = (x,z)
11
12 -- Die Position eines Bildes um dx und dy verändern
13 moveImage :: Int -> Int -> Image -> Image
14 moveImage dx dy (p,(x,y)) = (p,(x+dx,y+dy))
15
16 -- Ein positioniertes Bild darstellen
17 printImage :: Image -> IO()
18 printImage (p,(x,y)) = (printPicture . padout y 0 0 x) p
|
1-8.txt |
Codebeispiel 8
Die gezeigten Beispiele sind bis auf printImage trivialer Natur. printImage führt die Darstellung eines positioniertes Bildes auf printPicture zurück, in dem es zuvor das Bild analog zur Positionsinformation um weiße Zeilen und Spalten erweitert. Dazu dient padout, eine Funktion, die ein Bild um definierte Anzahlen an Zeilen/Spalten nach oben, rechts, unten und links erweitert.
Alternative Repräsentation von Bildern
In den vorangegangenen Beispielen war zu erkennen, daß die meisten Funktionen keine Abhängigkeiten vom Typ der Bildelemente aufweisen, sondern lediglich Listenoperationen verwenden, die sich gegenüber dem Elementtyp polymorph verhalten. Das legt den Versuch nahe, unsere Bildbeschreibung polymorph zu definieren. In der Konsequenz müssen wir zusätzlich eine Typklasse für die Bildelemente einführen, die den Funktionen, die auf den Bildelementen selber arbeiten und somit von ihrer Implementierung abhängig sind (z.B. invert), eine definierte Schnittstelle zur Verfügung stellen. Der Nutzen der Modifikationen: Wir können fortan jeden Datentyp, den wir in dieser Typklasse installieren, als Bildelement für unsere Bilder verwenden, ohne die oben besprochenen Funktionen zu modifizieren. Nachfolgend eine Definitionsskizze für das neue Modell:
01 type Row a = [a]
02 type Picture a = [Row a]
03
04 class (Eq a, Enum a) => Pixel a where
05 toString :: a -> String -- Umwandlung des Bildelementes für die (zeichenorientierte) Bildschirmausgabe
06 whitePixel :: a -- ein weißer Pixel in der Repräsentation des jeweiligen Datentyps, dient der Erzeugung weißer Flächen (z.B. padout)
07 invertPixel :: a -> a -- Invertieren eines Bildelementes
08 superimposePixel :: a -> a -> a -- Addieren zweier Bildelemente
09 ...
|
1-9.txt |
Codebeispiel 9
Wir können nun beispielsweise die invert/superimpose-Funktionen leicht verändern, um sie polymorph zu machen (man beachte die ebenfalls angepassten Typsignaturen):
01 superimpose :: Pixel a => Picture a -> Picture a -> Picture a
02 superimpose = zipWith (zipWith superimposePixel)
03
04 invert :: Pixel a => Picture a -> Picture a
05 invert = map (map invertPixel)
|
1-10.txt |
Codebeispiel 10
Die invert-Funktion läßt leicht einen weiteren Gedanken keimen: Ist die Generierung eines Pixels aus einem anderen Pixel ein Muster? Mithin möchte man vielleicht später eine gamma-Funktion definieren, die ebenfalls die Signatur (Pixel a => Picture a -> Picture a) aufweisen würde. Die Erweiterung der Pixel-Typklasse für jede Funktion dieser Art erscheint unflexibel. Ein Vorschlag zur Lösung dieses Problems wäre, die Funktionen zur Modifikation von Pixeln zu standardisieren und auf eine Zwischendarstellung zurückzuführen - z.B. Double-Werte zwischen 0.0 (Schwarz) und 1.0 (Weiß):
01 -- Erweiterung der Pixel-Typklasse
02 normalize :: a -> Double
03 denormalize :: Double -> a
04 shader :: (Double -> Double) -> a -> a
05 shader f = denormalize . f . normalize
|
1-11.txt |
Codebeispiel 11
Die normalize/denormalize-Funktionen würden für jede Instanz der Pixel-Klasse zu definieren sein und erlaubten die Transformation des jeweiligen Datentyps in das beschriebene Double-Format sowie die Transformation des Ergebnisses zurück in den Datentyp. Die shader-Funktion bettet die Double-Funktionen in die normalize/denormalize-Funktionen ein und kann defaultmäßig definiert werden. Fortan kann eine einzige Definition einer solchen Shaderfunktion polymorph für alle denkbaren Pixeltypen (und damit Bildtypen) eingesetzt werden:
01 -- Ein Bild mit einem Shader verarbeiten
02 shade :: Pixel a =>(Double->Double) -> Picture a -> Picture a
03 shade f = map (map (shader f))
04
05 -- Invertieren eines Bildes
06 invert :: Pixel a => Picture a -> Picture a
07 invert = shade (\x -> 1.0 - x)
08
09 -- Gammakorrektur eines Bildes
10 gamma :: Pixel a => Double -> Picture a -> Picture a
11 gamma g = shade (\x -> if x == 0 then 0 else x ** (1/g))
|
1-12.txt |
Codebeispiel 12
Zum Abschluß soll ein Beispiel für einen selbstdefinierten Datentyp für 5 Graustufen und dessen Installation in der Pixel-Typklasse gezeigt werden.
01 -- Pixelinstanz Mehrfarbig mit eigenem Datentypen
02 data UglyColor = B | NB | G | QW | W
03 deriving (Eq, Enum, Show)
04
05 instance Pixel UglyColor where
06 toString W = [´ ´]
07 toString QW = [´.´]
08 toString G = [´:´]
09 toString NB = [´+´]
10 toString B = [´#´]
11 whitePixel = W
12 invertPixel pix = ...
13 superimposePixel p1 p2 = ...
|
1-13.txt |
Codebeispiel 13
In den zu diesem Seminar gehörenden Haskell-Quellen und den Beispielen werden mit einem Bild "smile" im UglyColor-Format die oben genannten Eigenschaften demonstriert.
Code generated with AusarbeitungGenerator Version 1.1, weblink