next up previous contents index
Next: Mächtigkeit von Fib Up: Theoretische Aussagen zur Fib-Multimediabeschreibungssprache Previous: Theoretische Aussagen zur Fib-Multimediabeschreibungssprache   Contents   Index


Mächtigkeit der Fib-Multimediasprache auf Bilder

Mit der Fib-Multimediasprache können alle als Rastergrafik darstellbaren Bilder dargestellt werden. Bilder, die als Rastergrafik darstellbar sind, sind die am häufigsten verwendeten Bilder in der elektronischen Datenverarbeitung. Dazu gehören unter anderem Windows Bitmap (BMP, Dateiendung: .bmp), JPEG File Interchange Format (JFIF, Dateiendung: .jpg) und Portable Network Graphics (PNG, Dateiendung: .png).

Allein mit dem Punktelement und dem Listenelement lassen sich bereits alle möglichen Rastergrafiken darstellen.


Beweis: Eine Rastergrafik (euklidisch, zweidimensional, diskret) kann als Matrix dargestellt werden, in der die Spalte die x-Koordinate, die Zeile die y-Koordinate des Punktes angibt und die Werte die Farben der Punkte angeben. Die Anzahl der Punkte in der Rastergrafik ist endlich. Um diese Punkte durch Fib-Multimediasprache darzustellen, ist ein root-Element zu erzeugen, das die Eigenschaften der Rastergrafik enthält (Größe bzw. Dimensionsdefinitionsbereich usw.). In diesem root-Element ist als Haupt-Fib-Objekt ein Listenelement einzufügen, welches für jeden Punkt des Bildes ein Unterobjekt enthält. Dieses Unterobjekt besteht nur aus einem Eigenschaftselement, das die Farbe des Punktes kodiert, und einem enthaltenden Punktelement, welches die Position des Punktes kodiert. So gibt es für jeden Punkt in der Rastergrafik einen entsprechenden Punkt im erzeugten Fib-Objekt, womit das Fib-Objekt die Rastergrafik repräsentiert.

Eine Abbildung in die Fib-Multimediasprache kann beispielsweise mit dem im Listing 3 dargestellten Algorithmus geschehen (Pseudo-C).

Dabei beginnt die Indizierung der Matrix mit (0,0).

Der Farbwert der Koordinate (x,y) kann mit matrix[ x, y] bestimmt werden. Mit der Funktion getColorVector() wird aus dem Matrix-Farbwert ein Fib-Farbvektor generiert.

Die Syntax der Fib-Objekte entspricht der im Abschnitt III auf Seite [*] angesprochenen möglichen Syntax.


\begin{lstlisting}[language=C, numbers=left, frame=single, caption={Algorithmus ...
...rty( getColorVector( matrix[x,y] ) , p( (x,y) ) ) );
};
};
};
\end{lstlisting}


Da die Erweiterung mit Funktionen und anderen Elementen optional ist, wird mit dem angegebenen Algorithmus ein korrektes Fib-Objekt erzeugt.


Zu jedem Punkt in der Matrix gibt es einen gleichfarbigen Punkt im Fib-Objekt mit der entsprechenden Koordinate, aber es gibt keinen Punkt im Fib-Objekt, der nicht in der Matrix vorhanden ist, denn jede Koordinate der Matrix wird mit den zwei for-Schleifen durchlaufen. Dadurch wird für jede Koordinate und damit auch für jeden Punkt in der Rastergrafik ein Punkt im Fib-Objekt eingefügt. Somit gibt es für jeden Punkt in der Rastergrafik einen entsprechenden Punkt in dem Fib-Objekt. Da nur Koordinaten der Matrix in den for-Schleifen durchlaufen werden und nur für diese die entsprechenden Punkte in das Fib-Objekt eingefügt werden, existieren nur Punkte die auch in der Matrix auftauchen und damit auch nur Punkte im Fib-Objekt die auch in der Rastergrafik vorkommen. Es gibt also nur die Punkte aus der Originalrastergrafik im Fib-Objekt und nur diese. Damit repräsentieren das Fib-Objekt und die Originalrastergrafik die gleiche Rastergrafik. Deshalb können alle Rastergrafiken auch mit der Fib-Multimediasprache dargestellt werden.

Ein mit dem Algorithmus generiertes Fib-Objekt, das einer Originalrastergrafik entspricht, stellt eine obere Grenze der minimalen Größe möglicher entsprechender Fib-Objekte da. Das heißt, jede Rastergrafik kann durch ein Fib-Objekt repräsentiert werden, das genauso groß ist, wie ein Fib-Objekt für die Rastergrafik, das mit dem oben aufgeführten Algorithmus generiert wurde, nämlich das generierte Fib-Objekt. Es gibt aber wahrscheinlich noch kürzere Fib-Objekte für die Rastergrafik.

Damit ist die minimale Größe eines Fib-Objekts für eine Rastergrafik maximal:

$Fib\_max_{min}$ = (Anzahl der Pixel im Bild) $* [$(Größe eines Punktelements) + (Größe eines Eigenschaftselements für das entsprechende Farbschema)$]$ + (Größe eines Listenelements)+ (Größe eines root-Elements mit gesetzten Werten)


Beispiel: Dargestellt werden soll ein Bild 8 x 8 = 256 Pixel mit 3 Byte für die Farbe (RGB), 1 Byte für die Position (für jede Richtung x und y 4 Bit = 8 mögliche Werte) und 1 Byte für den Objektnamen (z. B. "l" für Listelemente und "p" für Punktelemente). Klammern werden nicht benötigt, da alle Teile eine feste Länge haben. (Die Annahmen über die Größen der Fib-Objekt-Elemente wird hier abgeschätzt. Bei einer Implementierung sind sicherlich bessere (/kleinere) Werte möglich.)


Rechnung: $256 (Pixel) * (2 Bytes + 4 Bytes) + 9 Bytes + 256 Bytes = 1801 Bytes$


Das Bild kann also auf jeden Fall mit einem 1801 Byte großen Fib-Objekt dargestellt werden. Es sind davon abweichende kürzere Fib-Objekt-Darstellungen möglich. Die 1801 Byte sind also die Obergrenze für die minimale Größe, mit der das Bild mit einem Fib-Objekt dargestellt werden kann.


Zum Vergleich: Der Speicherbedarf einer Rastergrafik als Bitmap (nur Punkt-Informationen) beträgt mindestens (Anzahl der Pixel im Bild) * (Größe eines Farbwertes)


Für das obige Beispiel ergibt sich: $256 (Pixel) * 3 Bytes = 768 Bytes$


Das ist ungefähr die Hälfte der 1801 Byte der Obergrenze für die minimale Fib-Objekt-Darstellung.


Indem die Matrix auf 3 Dimensionen erweitert wird, kann die Aussage über die Darstellbarkeit aller Rastergrafiken leicht auf Sequenzen von Rastergrafiken (z. B. die Bilder von Filmen) erweitert werden.


next up previous contents index
Next: Mächtigkeit von Fib Up: Theoretische Aussagen zur Fib-Multimediabeschreibungssprache Previous: Theoretische Aussagen zur Fib-Multimediabeschreibungssprache   Contents   Index
Betti Österholz 2013-02-13