%
% Copyright (c) 2008 Betti "Osterholz
%
% Permission is granted to copy, distribute and/or modify this document
% under the terms of the GNU Free Documentation License, Version 1.2 or
% any later version published by the Free Software Foundation;
% with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
%
% A copy of the license is included in the file ``fdl.tex'' .
%


\section{Theoretical statements for the Fib multimedia description language}
\label{secTheoreticFib}

Some theoretical statements for the Fib multimedia description language will follow, for wich, because of lack of time, usually not a complete proof is given. With these statements a better understanding of the Fib multimedia language should be provided.


\subsection{Power of the Fib multimedia language on images}
\label{secPowerOfFibOnPictures}

With the Fib multimedia language all as raster graphics displayable images can be represented. Images, that are displayed as raster graphics, are the most commonly used images in the digital data processing. These include Windows bitmap (BMP; file extension: .bmp), JPEG File Interchange Format (JFIF, file extension: .jpg) and Portable Network Graphics (PNG, File Extension: .png).

With using only the point element and the list element alone all possible raster graphics can (already) be represented.

\bigskip\noindent
\textbf{Proof:}
A raster graphic (euclidean, two dimensional, discrete) can be represented as a matrix, the column indicats the x coordinate, the lines the y coordinate of the point and the values specify the colors of the points. The number of dots in the raster image is finite. To represent these points in the Fib multimedia language, a root-element have to be created that contains the properties of the raster graphic (size and dimension domain etc.). In this root-element a main Fib object, wich is a list element, is inserted, which contains for each point of the image a subobject. This subobject consists only of a property element, which encodes the color of the point, and one contained point element, which encodes the position of the point. So there is for every point in the raster graphic a corresponding point in the generated Fib object, so that the Fib object represents the raster image.

A mapping into the Fib multimedia language can for example be implemented by the algorithm shown in listing \ref{alleBild} (pseudo-C).

\begin{flushleft}
The indexing of the matrix begins with (0.0).

The color value of coordinates (x, y) can be determined with \verb|matrix[ x, y ]|. With the function \verb|getColorVector()| a Fib color vector is generated from the matrix color value.

The syntax of the Fib objects corresponds to the in section \ref{partFibLanguage} on page \pageref{partFibLanguage} discussed possible syntax.

\end{flushleft}

\begin{lstlisting}[language=C, numbers=left, frame=single, caption={Algorithm to generate a correct Fib object from an image matrix}, label={alleBild}, breaklines, basicstyle=\footnotesize\ttfamily, numberstyle=\tiny]
void translate( matrix ){

   int xmax = number of columns of the matrix;
   int ymax = number of lines of the matrix;
   Fib_Object_Pointer obj = new root();

   //set the properties of the raster graphic
   obj->setPicture( xmax, ymax, colorScheme );

   list mainList = new list()

   obj->insertMainObject( mainList )

   for( int x = 0; x == xmax; x = x + 1 ){

      for( int y = 0; y == xmax; y = y + 1 ){
         mainList->insertObject( property( getColorVector( matrix[x,y] ) , p( (x,y) ) ) );
      };
   };
};
\end{lstlisting}
\bigskip\noindent
Since the expansion with functions and other elements is optional, a correct Fib object is generated with the specified algorithm.

\bigskip\noindent
For each point in the matrix there is a same-colored point in the Fib object with the corresponding coordinate, but there are no points in Fib object that are not present in the matrix, because each coordinate of the matrix is traverse with the two ``for'' loops. Thereby a point in the Fib object is added for each coordinate and thus for every point in the raster graphic. Thus for every point in the raster graphic a corresponding point in the Fib object exists.
Since only coordinates of the matrix are traverse in the ``for'' loops and only for them corresponding points are included in the Fib object, there are only points that appear in the matrix and hence only points in the Fib object, which also occur in the raster graphic.
So there are only the points from the original raster graphic in the Fib object and no more.
Thus the Fib object and the original the raster graphic represent (/shows) the same raster graphic. Therefore, all raster graphics are representable with the Fib multimedia language.

A Fib object generated by the algorithm, that represents an original raster graphic, is an upper limit to the minimum size of possible corresponding Fib objects. This means, each raster graphic can be represented by a Fib object, that is as big as the Fib object for the raster graphics that was generated with the above algorithm, that is the Fib object generated. But there are likely even shorter Fib objects for raster graphics.

\begin{flushleft}
With that the minimum size of a Fib object for a raster graphic is maximal:

$Fib\_max_{min}$ = (number of pixels in the image) $* [$(size of a point element) + (size of a property element for the appropriate color scheme)$]$ + (size of a list element)+ (size of a root-element with values set)

\bigskip\noindent
Example: You want to shown an image of 8 x 8 = 256 pixels with 3 bytes for the color (RGB), 1 byte for the position (for each direction x and y 4 bits = 8 possible values) and 1 byte for the object name (for example ``l'' for the list elements and ``p'' for the point elements). Parentheses are not needed, because all parts have a fixed length. (The assumptions about the sizes of the Fib object elements are estimated here. In a implementation, better (/smaller) values are more likely.)

\begin{itemize}
 \item A point element requires 2 bytes (1 byte position + 1 byte element name).
 \item For a property element 4 bytes are needed (3 bytes color + 1 byte element name).
 \item For a list element 9 bytes are needed (8 bytes for specifying the number of subobjects + 1 byte element name).
 \item The root-element requires 256 bytes. (Since many parts of the root-element are empty and only the domain for two dimensions and the RGB color domain must be specified, 256 bytes should be enough.)
\end{itemize}

\bigskip\noindent
Calculation:
$256 (pixel) * (2 bytes + 4 bytes) + 9 bytes + 256 bytes = 1801 bytes$

\bigskip\noindent
So the image can definitely be displayed with a 1801 byte long Fib object. But there are other shorter Fib object representations possible. The 1801 bytes are thus the upper limit for the minimum size with which the image can be represented by a Fib object.

\bigskip\noindent
For comparison: The memory requirements of a raster image as a bitmap (only point information) is at least
(Number of pixels in the image) * (size of a color value)

\bigskip\noindent
For the above example it results in: $256 (pixel) * 3 bytes = 768 bytes$

\bigskip\noindent
That's about half of the 1801 byte limit on the minimum Fib object representation.

\bigskip\noindent
In that the matrix is extended to three dimensions, the statement about the representability of all raster images can be easily extended to sequences of raster images (such as the images of movies).

\end{flushleft}


\subsection{Cardinality of Fib}

\textbf{Theorem: The set of possible Fib objects is countable infinite.}

\bigskip\noindent
Sketch of proof for ``countable'':

\noindent
Every Fib object can be represented with a finite number of letters, and thus bits or numbers, and the amount of these is countable.
This follows from the fact, that the number of Fib elements in a Fib object is always countable and every Fib element consists of countably many parts, which are themselves countable, there are for example only integer or rational numbers, and also the number of variables is countable.

\bigskip\noindent
Sketch of proof for ``infinite'':

\noindent
All natural numbers can be represented by Fib objects. In the following a possible representation of any natural number with a Fib object is described.

A point object itself is the natural number 0 .
If a Fib object is inserted in a new function element the resulting Fib object is the successor of the original Fib object.
In this manner the 0 and the successor function can be reproduced in the Fib multimedia language, and all natural numbers can be represented. Since the set of natural numbers is infinite, the amount of Fib objects is also infinite.

\bigskip\noindent
Even every multimedia object can be represented by a countable infinite set of Fib objects, because to a Fib object, that represents a multimedia object, any Fib object can be attached with the help of a list element, as long as the multimedia object representation is not changed. For example, to a Fib object a copy of itself using a list element can be as often attached as needed, without changing the multimedia object.


\subsection{Any complete Fib object can be represented as a multimedia object}
\label{alleBilder}

It is shown in this section, that it is always possible to interpret (to translate into a multimedia object) any complete Fib object (see section \ref{secFullFibObject} on page \pageref{secFullFibObject}) in a way, that only valid multimedia objects of a certain type (e. g. RGB images with 100 x 100 pixels) can result. In which the limitations with regard to the multimedia data, as already mentioned, are assumed, that the multimedia data can be represented as properties of points of a finite, euclidean and discrete (there are smallest units) space. This restriction is not very large, because they (almost) excludes non of the presently common multimedia data. The multimedia data may therefore represent images, sound or movies.

With the restriction that the distance / difference between two properties of the same type can always be determined as a numerical value, two multimedia objects with the same dimensions can be always compared. Two multimedia objects have the same dimensions, if for each point in the first multimedia object exactly one corresponding point in the other multimedia object exists.

The requirement of the complete Fib object is necessary to ensure that the Fib object can be always evaluated. Since the completeness of an Fib object can be check with the syntax shown in part \ref{partFibLanguage}, if a Fib object is complete can always be determined. Incomplete Fib objects should not be generated by the algorithms or the genetic operators.

If the dimensions of a Fib object are adapted to that of a multimedia object (this should be always possible), the Fib object is always comparable with the multimedia object, because it can itself be always presented as a multimedia object, and two multimedia objects with the same dimensions can always be compared to each other and the similarity to each other can be evaluated.

Note: This is advantageous for genetic algorithms. In some other forms of representation that are generated by genetic algorithms, invalid objects (e. g. programs) arise, where a more accurate evaluation / comparison is not possible. A population in this format can contain, for example, a large class of objects that are invalid, which are all equally bad and are therefore considered same in the selection process. If the population consists only of invalid individuals, the selection of a better individual is impossible. The genetic algorithm is then on a (fitness) plane, from which it can only find away with great difficulty.

\bigskip\noindent
Proof that every correct Fib object can be represented as a multimedia object (of a specific type, such as a picture):
The starting point is that a multimedia object (euclidean, two-dimensional, discrete) can be represented as a finite set of points with their (finitely many) properties. Since there are only finitely many points with only finitely many properties, such a finite set is always constructible.

Such a finite set of points with their (finitely many) properties is also generated by a correct Fib object. Points of the set that are too much to represent a multimedia object, will be deleted from the set. Points that are missing in the set to represent a multimedia object are inserted into the set. Properties of the points that are too much to represent a multimedia object will be deleted. Properties, which are missing at points to represent a multimedia object, are added and set with their default values (e. g. the zero values of their domains). In this way a finite set of points is created with their (finite many) properties that can be represented as a multimedia object.

\bigskip\noindent
Example: The Fib object should represent an RGB image with 100 x 100 pixels. For this the dimensions of the Fib object are adjusted to cover these 100 x 100 pixels in horizontal and vertical direction. That is, if the dimension (horizontal or vertical) already exists, the domain of each direction is adjusted, so that it covers at least 100 values at regular intervals. So that to each pixel a value is assigned. If a dimension (/ direction) is missing, it will be created with the appropriate domain and in all points for the dimension the standard value of 0 will be set. In this case there is no point with other values than the default value for this dimension. Dimensions that are too much, are deleted from the root elements and the points. The evaluation of the resulting Fib object produces a set of points with their properties. During evaluation, the smallest value of $W_{min}$ of each dimension in the Fib object is assigned to the value 0 as the coordinate in the set, the second smallest one to 1 as the coordinate, etc.

From this set now all points are deleted that are not within the 100 x 100 pixels boundary (points for which a coordinate respectively value is less than 0 or greater than 99). For all coordinates, which are still missing (missing points, where the values respectively the coordinates is between [including] 0 and 99), points are inserted. All properties that are not RGB colors will be deleted. To all points that have no property for RGB colors, the default color $(0, 0, 0)_{colorRGB}$ is assigned. The resulting set contains for each point in the RGB image with 100 x 100 pixels a point with RGB color, but no other points or properties, and thus represents an RGB image with 100 x 100 pixels.

This can then be compared with other RGB images with 100 x 100 pixels and rated in relation to them.












