1930: Sandbox: Add a document which describes the images types in milena.

7 May 2008

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox


Index: ChangeLog
from  Nicolas Ballas  <ballas@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().

    

Nicolas Ballas

tags

participants (1)