[Olena-patches] 1930: Sandbox: Add a document which describes the images types in milena.

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Sandbox: Add a document which describes the images types in milena. * ballas/doc/image_types, * ballas/doc/image_types/include: New repository. * ballas/doc/image_types/include/image_tour.tex, * ballas/doc/image_types/doc.tex: New document describing the images. * ballas/doc/image_tours.txt: update. image_tours.txt | 5 image_types/doc.tex | 28 ++ image_types/include/image_tour.tex | 480 +++++++++++++++++++++++++++++++++++++ 3 files changed, 510 insertions(+), 3 deletions(-) Index: ballas/doc/image_types/include/image_tour.tex --- ballas/doc/image_types/include/image_tour.tex (revision 0) +++ ballas/doc/image_types/include/image_tour.tex (revision 0) @@ -0,0 +1,480 @@ +\chapter{Images Tour} + +This chapter intends to give a global overview of the image types present in +Milena. + + + +\section{Primary Image} + +Primitive image are images which are not based on another image. +They don't lie on an underlying image. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Image nD %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\subsection{Image $n$D} + +\begin{itemize} +\item{Short Description:} + +Image based on a regular grid (aligned and orthogonal) . +The grid nodes are points. +Milena provides three types of image $n$D: \verb+image1d+, \verb+image2d+ and +\verb+image3d+. +Depends on the dimension, the grid (so the image) can ether be linear +(in $1$D), rectangular (in $2$D) or cubic (in $3$D). + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+T+: the image value type. +\end{itemize} + + +\item{Memory management:} + +All the image values are stored in a linear buffer in the RAM. + +\item{Data access:} + + As these image types are based on a regular grid, and have their values +stored in a linear buffer in RAM, we can directly access to the image +values from the image points. +The read access at the point $p$ is + +$ima(p) \rightarrow data[p]$ and write access is + +$ima(p) \leftarrow data[p]$ \footnote{$data$ represents the image +values buffer, $p$ represents a point.}.\\ + + +But depends on the image dimension, $p$ canb be in $1$D, $2$D or $3$D. + + +\begin{itemize} +\item {$1$D:} + +$ima(p) \rightarrow data[p.row]$ + +$ima(p) \leftarrow data[p.row]$ +\item {$2$D:} + +$ima(p) \rightarrow data[p.row][p.col]$ + +$ima(p) \leftarrow data[p.row][p.col]$ +\item {$3$D:} + +$ima(p) \rightarrow data[p.row][p.col][p.sli]$ + +$ima(p) \leftarrow data[p.row][p.col][p.sli]$ +\end{itemize} + + +\item{Associated properties:} + +In order to increase access performance, an extended domain is added to the +images $n$D. +An extended domain add dummy values on the images borders. +This way, an user doesn't have to check if a neighbour of a point is inside the +image domain. +An extended domain speed up algorithms which use structuring elements. +Furthermore, the image values type have a pointer semantics. +(there are stored in a linear buffer). +So images $n$D provide access to pixter (iterator over image pixels). + +\end{itemize} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Image based on function %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\subsection{Image based on function} + +\subsubsection{Fun\_Image} + +\begin{itemize} + +\item{Short Description:} + +\verb+Fun_Image+ has been designed to define an image from a function site to +value (called $p2v$). + +The definition of a $p2v$ function f is: + +\begin{eqnarray*} +Psite\_Type & \rightarrow & Value\_Type \\ + p & \rightarrow & f(p) +\end{eqnarray*} + + + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+F+: $p2v$ function. +\item \verb+S+: Site Set type. +\end{itemize} + +\item{Memory management:} + +No data are stored in memory, since all the values are computed by the +function. + +\item{Data access:} + +$ima(p) \rightarrow f(p)$ where $f$ is the image associated function. + +\item{Associated properties:} + +\verb+Fun_Image+ are constant images since we can't modify the +\verb+Fun_Image+ values. +Indeed all the values are computed on the fly by the function associated to the +image. +So, the image values doesn't have a write access. +In addition the \verb+Fun_Image+ site set must be include in the domain of +the function associated to the image. + +\end{itemize} + +\subsubsection{Flat\_Image} + +\begin{itemize} + +\item{Short Description:} + +\verb+Flat_Image+ is a specialized version of the \verb+Fun_image+. +All the sites in the image share the same value. +So \verb+Flat_Image+ can be seen as a \verb+Fun_image+ which a constant +function. + +\begin{eqnarray*} +Psite\_Type & \rightarrow & Value\_Type \\ + p & \rightarrow & v +\end{eqnarray*} where $v$ is a constant value. + +\item{Type Parameters:} + +\begin{itemize} + +\item \verb+T+: Value type. +\item \verb+S+: Site Set type. + +\end{itemize} + +\item{Memory management:} + +The flat value $v$ is stored in the memory. + +\item{Data access:} + +$ima(p) \rightarrow v$ + +$ima(p) \leftarrow v$ +where v is the flat value associated to the image. + +\end{itemize} + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Image encoded by runs %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\subsection{Images encoded by run} + +\subsubsection{Definition of a run} + +A run is a ``continuous'' succession of points. +It is encoded by a point representing the beginning of the run +and an integer which is the length of the run. + +Example: +The run \verb+((1, 2), 4)+ represents the site \verb+(1, 2)+, \verb+(1, 3)+, +\verb+(1, 4)+ and \verb+(1, 5)+. + + +\subsubsection{rle\_image} + +\begin{itemize} +\item{Short Description:} + +A \verb+rle_image+ can be defined as couples $(r, v)$ where $r$ is a run of +point \verb+P+ and $v$ is a value of type \verb+T+. +A \verb+rle_image+ associates one value for all the points in the run $r$. + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+P+: Point type. +\item \verb+T+: Value type. +\end{itemize} + +\item{Memory management:} + +\begin{itemize} +\item \verb+runs+: a vector of run. +\item \verb+values+: a vector values. +\end{itemize} + +A run at the index i of the \verb+runs+ vector is associated to the value at +the index i of the \verb+values+ vector. + + +\item{Data access:} + +Due to the run encoding, we cannot access directly to the image values with +a point. +We need to handle the image implementation details. +That's why we use a psite (which is different from a point) to access to +the image values. +The psite type is just a wrapper of two integer which are the position of +the run (\verb+out_run_index+) inside the \verb+runs+ vector, and the position +of the point (\verb+in_run_index+) inside the run.\\ + + +Here is how we access to the image data. + +$ima(psite) \rightarrow values[psite.out\_run\_index]$ + +$ima(psite) \leftarrow values[psite.out\_run\_index]$ + + +\item{Associated properties:} + +Implementation details are necessary to access to the image value. +So this image type has its psite type different to site type. +This image type is ``one shot''. +We cannot add new points to the image once we created it. +\end{itemize} + + +\subsubsection{compact\_rle} +\begin{itemize} +\item{Short Description:} + +\verb+compact_rle+ type is similar to the \verb+rle_image+ type. +But \verb+compact_rle+ also encode the 0 values of the original image into +the encoded image (the \verb+rle_image+ just ignores the 0). +FIXME Can't we use \verb+rle_image+ (with a different encoding functions)? + +\end{itemize} + + +\subsubsection{sparse\_image} +\begin{itemize} +\item{Short Description:} + +A \verb+sparse_image+ can be defined as couples $(r, [v])$ where $r$ is a run +of points \verb+P+ and $v$ a vector of values of type \verb+T+. +A \verb+sparse_image+ associates a value to each points of the run $r$. + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+P+: Point type. +\item \verb+T+: Value type. +\end{itemize} + + +\item{Memory management:} +\begin{itemize} +\item \verb+runs+: a vector of run. +\item \verb+values+: a vector of vector of values. +\end{itemize} + +\item{Data access:} + +We use the same psite to access to \verb+sparse_image+ data than +\verb+rle_image+. + +$ima(psite) \rightarrow values[psite.out\_run\_index][psite.in\_run\_index]$ + +$ima(psite) \leftarrow values[psite.out\_run\_index][psite.in\_run\_index]$ + + +\item{Associated properties:} + +\verb+sparse_image+ has the same property than \verb+rle_image+. + +\end{itemize} + + +\subsubsection{value\_encoded\_image} +\begin{itemize} +\item{Short Description:} + + +In a \verb+value_encoded_image+ a value is associated to a set of runs. +A \verb+value_encoded_image+ can be seen as couples $(v, \{runs\})$ where +v is a value and $\{runs\}$ is a set of runs. +With this structure, all the runs (so, all the points) which have the same +value can be easily get (in a $O(1)$ complexity). + + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+T+ Value type. +\item \verb+P+ Point type. +\end{itemize} + +\item{Memory management:} + +\begin{itemize} +\item \verb+runs_array+ a vector which contains a set of run at each index. +\item \verb+values+ values vector. +\end{itemize} + +All the runs in a set at an index i, have \verb+values[i]+ as value. + +\item{Data access:} + +$ima(p) \rightarrow values[psite.index]$ + +$ima(p) \leftarrow values[psite.index]$ where $index$ represents the position +of the psite in the $runs\_array$ vector. + + +\item{Associated properties:} + +This image type is ``one shot''. +The psite type is different from the site type of the image. +Furthermore, in \verb+value_encoded_image+ it is possible to retrieve +the set of runs corresponding to a value. + +$ima.sites(v) \rightarrow runs\_array[v.index]$ + +$ima.sites(v) \leftarrow runs\_array[v.index]$ where $v$ is an image value +and $v.index$ the corresponding index in the $values$ vector. + +It is also possible to change all the values of a set of runs in the image. + +$ima.cell(v) \rightarrow values[v.index]$ FIXME: does it has any sens? + +$ima.cell(v) \leftarrow values[v.index]$ where $v$ is an image values +and $v.index$ the corresponding index in the $values$ vector. + + + +\end{itemize} + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% map_image by runs %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\subsection{map\_image} + +\begin{itemize} + +\item{Short Description:} + A \verb+map_image+ have it values stored in a std::map. + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+T+: Value type. +\item \verb+P+: Site type. +\end{itemize} + +\item{Memory management:} + + A std::map $m$ which use \verb+P+ as key type and \verb+V+ as value type. + +\item{Data access:} + +$ima(p) \rightarrow m[p]$ + +$ima(p) \leftarrow m[p]$ +where m is std::map associated to the image. + + +\item{Associated properties:} + +The data access are not in $O(1)$ since the image uses an underlying std::map. +So this image is \verb+slow+. + +\end{itemize} + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Image based on a lut %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\subsection{lut\_image} + +\begin{itemize} +\item{Short Description:} + +A \verb+lut_image+ uses a look up table to retrieve a value +associated to an image site. + + +\item{Type Parameters:} + +\begin{itemize} +\item \verb+P+: Point type. +\item \verb+T+: Value type. +\end{itemize} + +\item{Memory management:} + +\begin{itemize} +\item \verb+pset+: set of site composing the image. +\item \verb+values+: container associated a lut\_value to each site of the +image. +\item \verb+lut+: table translating the lut\_values to their real values. +\end{itemize} + +\item{Data access:} + +$ima(p) \rightarrow lut[value[p]]$ + +$ima(p) \leftarrow lut[value[p]]$ + +\item{Associated properties:} + + +It is possible to change all the values of a set of runs in the image. + +$ima.cell(v) \rightarrow lut[v.index]$ FIXME: does it has any sens? + +$ima.cell(v) \leftarrow lut[v.index]$ where $v$ is an image values +and $v.index$ the corresponding index in the $lut$. + + +\end{itemize} + + + + +\section{Morpher} + + + +%%% TEMPLATE +\begin{itemize} +\item{Short Description:} + + + +\item{Type Parameters:} + + +\item{Memory management:} + + +\item{Data access:} + + +\item{Associated properties:} + +\end{itemize} Index: ballas/doc/image_types/doc.tex --- ballas/doc/image_types/doc.tex (revision 0) +++ ballas/doc/image_types/doc.tex (revision 0) @@ -0,0 +1,28 @@ +\documentclass[8 pt,a4paper]{report} +\usepackage[english]{babel} +\usepackage{enumerate} +\usepackage{fancyhdr} +\usepackage{listings} +\usepackage{graphicx} +\usepackage[latin1]{inputenc} +\usepackage[linkcolor=black,colorlinks,pdftex]{hyperref} + +% \setlength{\oddsidemargin}{0.5cm} % Marge gauche sur pages impaires +% \setlength{\evensidemargin}{0.5cm} % Marge gauche sur pages paires +% \setlength{\textwidth}{15.5cm} + + + + +\title{ + Milena Documentation +} + + +\begin{document} + +\maketitle{} + +\include{include/image_tour} + +\end{document} Index: ballas/doc/image_tours.txt --- ballas/doc/image_tours.txt (revision 1929) +++ ballas/doc/image_tours.txt (working copy) @@ -31,7 +31,6 @@ ---------- / \ - | | | Image Type | | and | automatic -----> Props | associated| @@ -48,7 +47,7 @@ Some operators are only defined in special cases. Properties provide a way to check that the operator's input types respect the operator requirements. - +frf *** Specialization of an Algorithm Example: @@ -598,7 +597,7 @@ *** Sparse Image -A RLE image can be defined as the following: +A Sparse image can be defined as the following: {(p, [v])} where p is a run of P and v is a value of type T, and [v] is an array of size p.length().