https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena Index: ChangeLog from Nicolas Ballas <ballas@lrde.epita.fr> Add documentation about the image properties. * doc/tutorial/design: New. * doc/tutorial/design/include: New. * doc/tutorial/design/include/properties.tex, * doc/tutorial/design/include/imagetours.tex, * doc/tutorial/design/design.tex: New documentation files. * doc/tutorial/design/Makefile: New. * doc/tutorial/images_tour.txt: Update. * sandbox/ballas/doc/image_tours.txt: Fix typo mistakes. doc/tutorial/design/Makefile | 29 ++ doc/tutorial/design/design.tex | 52 +++ doc/tutorial/design/include/imagetours.tex | 299 +++++++++++++++++++++ doc/tutorial/design/include/properties.tex | 402 +++++++++++++++++++++++++++++ sandbox/ballas/doc/image_tours.txt | 2 5 files changed, 783 insertions(+), 1 deletion(-) Index: doc/tutorial/design/include/properties.tex --- doc/tutorial/design/include/properties.tex (revision 0) +++ doc/tutorial/design/include/properties.tex (revision 0) @@ -0,0 +1,402 @@ +\section{Properties} + + +\subsection{Notation} + +A property has several values. +Furthermore the values of a property can be seen as a hierarchy. +Hence, we need to define a notation to represent these hierarchies. +\begin{itemize} + +\item \verb+category: primary+ means that \verb+primary+ is a value of the +property category. + +\item +\begin{verbatim} +category: any + | + +--- primary + | + +--- morpher +\end{verbatim} +\end{itemize} It means that \verb+primary+ and \verb+morpher+ inherit from +\verb+any+ + +\subsection{Properties defining the image} + +%%%%%%%%%%%%%%%%%% +% Category % +%%%%%%%%%%%%%%%%%% +\subsubsection{category} +\index{Property: category} + + +\begin{verbatim} + category: any + | + +--- primary + | + +--- morpher + | + +--- domain_morpher + | + +--- value_morpher + | + +--- identity_morpher +\end{verbatim} + + +This property specifies the category of an image type. +Primary images are instantiated in the first place; they don't need any +prior image type definition. +Morpher images transform an image type into another one. +Morphers are a non-intrusive way to add or modify some behaviors in an +existing class. + + +%% FIXME image morpher + +%%%%%%%%%%%%%%%%%% +% Size % +%%%%%%%%%%%%%%%%%% +\subsubsection{size} +\index{Property: size} + +\begin{verbatim} + size: any + | + +--- regular + | + +--- huge +\end{verbatim} + + +The size property gives an indication about the memory needed by an image. +A $huge$ image is an image which cannot be fully stored in the RAM. +Accessing a $huge$ image is slower than accessing a $regular$ image. +Indeed, to access to a $huge$ image, we first need to load in the RAM a part of +the image from another storage device. + +\subsection{Properties related to the image localization} + +%%%%%%%%%%%%%%%%%% +% Localization % +%%%%%%%%%%%%%%%%%% +\subsubsection{localization} +\index{Property: localization} + +\begin{verbatim} + localization: /any/ + | + + -- none + | + + -- space + | + + -- /grid/ + | + + -- isotropic_grid + | | + | + -- basic_grid + | + + -- anisotropic_grid + +\end{verbatim} + +This property defines the underlying support of the images. +The support of an image describes the image geometry and the relationship +between its sites. +An image on a non-localized space has this property set to $none$. +An image on a localized space has this property set to $space$. +An image based on a isotropic grid has this property set to $isotropic\_gride$ +An image based on a anisotropic grid has this property set to +$anisotropic\_gride$ +An image based on a aligned and orthogonal grid has its property set to +$basic\_grid$ + +%% FIXME: Is it true? +If an image has its \verb+localization+ set to $space$, the user must define +the neighborhood relationships between the sites. +Otherwise, the image underlying grid defines the neighborhood relationships. + + +%% FIXME Image de different type de grid + +%%%%%%%%%%%%%%%%%% +% Space % +%%%%%%%%%%%%%%%%%% +\subsubsection{space} +\index{Property: space} + +\begin{verbatim} + dimension: any + | + +--- none + | + +--- some + | + +--- one_d + | + +--- two_d + | + +--- three_d + + +\end{verbatim} + +This property specifies the dimension of the image. +An image in Milena can either be in one dimension, two dimensions or three dimensions. +An image can also have no dimension specified. + + + +\subsection{Property related to the image values} + + +%%% +%%% Data storage +%%% +\subsubsection{value\_access} +\index{Property: value\_access} + +\begin{verbatim} +value\_access: any + | + +--- direct + | + +--- indirect + | + +--- computed +\end{verbatim} + + +Image values can either be computed on the fly by a function or stored in +memory. If an image type has a direct acces on the values in memory, it is +possible to take a reference of them. In this case, this property is set to +$direct$. In the other case, this property is set $indirect$. When an image +computes its values on the fly, this property is refined to $computed$. + + +\subsubsection{vw\_storage} +\index{Property: vw\_storage} + +\begin{verbatim} +vw_storage: any + | + +--- /ram/ + | | + | +--- singleton + | | + | +--- one_block + | | + | +--- piecewise + +--- irrelevant +\end{verbatim} + + +%%%%%%%%%%%%%%%%%%%%%%%% +% access % +%%%%%%%%%%%%%%%%%%%%%%%% + +\subsubsection{pw\_io} +\index{Property: pw\_io} + +\begin{verbatim} + + pw_io: any + | + +--- read + | + +--- read_write +\end{verbatim} + + +All the image types in Milena provide an access to its values through +\verb+ima(p)+ where \verb+ima+ is an image and \verb+p+ a site. + +This property describes the read/write accessibility of this access. +If the image is read only, \verb+pw_io+ is set to $read$. +If the image is readable and writable, \verb+pw_io+ is set to $read\_write$.\\ + + +%%%%%%%%%%%%%%%%%%%%%%%% +% Speed % +%%%%%%%%%%%%%%%%%%%%%%%% + +%% FIXME detais fast image..., add normal image +\subsubsection{speed} +\index{Property: speed} + +\begin{verbatim} + + speed: any + | + +--- slow + | + +--- fast + | + +--- fastest +\end{verbatim} + + This property gives some information about the time needed to access a +value from a site through \verb+ima(p)+ where \verb+ima+ is an image and +\verb+p+ a site. + +If the \verb+speed+ property is equal to $slow$, $ima(p)$ complexity is greater +than $O(1)$. +If this property is equal to $fast$, $ima(p)$ complexity is in +$O(1)$ +If this property is equal to $fastest$, $ima(p)$ complexity is +in $O(1)$. Furthermore, in this case, $ima$ has an extended domain, and $ima$ +values have a pointer semantics (it is possible to directly iterate on the +image pixels). + +\subsubsection{vw\_io} +\index{Property: vw\_io} + +%% FIXME functions that modify globaly all the values... +\begin{verbatim} + + vw_io: any + | + +--- /vm_some/ + | | + | +--- vw_read + | | + | +--- vw_read_write + +--- vw_none +\end{verbatim} + +\subsubsection{vw\_set} +\index{Property: vw\_set} + +\begin{verbatim} + + vw_io: any + | + +--- /some/ + | | + | +--- uni + | | + | +--- multi + +--- none +\end{verbatim} + + + + + +\subsection{Properties related to the extended domain} + +%%%%%%%%%%%%%%%%%%%%%%%% +% ext_domain % +%%%%%%%%%%%%%%%%%%%%%%%% +\subsubsection{ext\_domain} +\index{Property: ext\_domain} + +\begin{verbatim} + ext_domain: any + | + +--- none + | + +--- some + | + +--- fixed + | + +--- infinite + | + +--- extendable +\end{verbatim} + +This property indicates if the image has an extended domain. +An extended domain grows the image domain by adding dummy values +on the image border. +\begin{table}[!h] + \begin{center} + \begin{tabular}{c|c|c|c|c|c} + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}}\\ + \hline + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}}\\ + \hline + {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{red}{12}}} & + {\textbf{\textcolor{red}{2}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}}\\ + \hline + {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{red}{2}}} & + {\textbf{\textcolor{red}{15}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}}\\ + \hline + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}}\\ + \hline + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}} & + {\textbf{\textcolor{green}{1}}} & {\textbf{\textcolor{green}{1}}}\\ + \end{tabular} + The values equal to {\textbf{\textcolor{green}{1}}} represent the extended domain. + \end{center} + \label{tab:pprop01}\caption{Image with an extended domain of size 2.} +\end{table} +An extended domain increases the performances of the image processing +algorithms. +Indeed, image processing algorithms often use the neighbors of the image +sites. +With an extended border it isn't necessary to test if the neighbors of an image +site are included in the image domain. +The size of the extended domain can differ (\verb+fixed+, \verb+infinite+ or +\verb+extendable+). + + + +%% FIXME illustration + + +%%%%%%%%%%%%%%%%%%%%%%%% +% ext_value % +%%%%%%%%%%%%%%%%%%%%%%%% +\subsubsection{ext\_value} +\index{Property: ext\_value} + +\begin{verbatim} + ext_value: any + | + +--- undefined + | + +--- single + | + +--- multiple +\end{verbatim} + +If all the extended domain sites share the same value (in memory), this property +is set to ``single''. +If each site of the image extended domain has its proper value, this property +is set to ``multiple''. +Otherwise, this property is set to ``undefined''. + + +%%%%%%%%%%%%%%%%%%%%%%%% +% ext_io % +%%%%%%%%%%%%%%%%%%%%%%%% +\subsubsection{ext\_io} +\index{Property: ext\_io} + +\begin{verbatim} + + ext_io: any + | + +--- /some/ + | | + | +--- read + | | + | +--- read_write + +--- none +\end{verbatim} + +This property describes the read/write accessibility of the image extended +border values. Index: doc/tutorial/design/include/imagetours.tex --- doc/tutorial/design/include/imagetours.tex (revision 0) +++ doc/tutorial/design/include/imagetours.tex (revision 0) @@ -0,0 +1,299 @@ +%% Outline: +%% This file gives a quick overview of the following image types: + +%% image2d<T> +%% mmap_image2d<T> +%% file_image2d<T> +%% tiled_image +%% fun_image<S,F> +%% flat_image<S,T> +%% pkey_image<P,T> +%% pvkeys_image<P,T> + +%% graph-based images... + +%% rle_image<P,T> +%% sparse_image<P, T> +%% value_enc_image<P, T> + +%% f_image<F,I> +%% f_images<F,n,I> +%% lut_image<I,T> + +%% sub_image +%% image_if +%% hexa<I> +%% translated_image + + +\section{Images tour} + +\subsection{Introduction} + + +In the Milena library, an image can be seen as an application +$site$ to $value$. +A $site$ is a localized object in space. +Points in $1D$, $2D$ or $3D$, are the sites objects commonly used in the +library. +However, the $site$ concept allows Milena to deal with complicated image type +(for instance see the \verb+graph_image+ type). + +So, an image is composed by a set of localized objects, $sites$, that +compose the definition domain of the image. +A value is associated to each site of the image. This is the destination domain +of the image. +To access to a value of an image nammed $ima$ localized at the point p, we +just use the mathematic notation: \verb+ima(p)+. + +Obviously, every image types of Milena provide an access $site$ to $value$, +through \verb+ima(p)+. Yet, depending on the image type, the values can be +stored in different way in memory. +For instance, in the \verb+image2d+, all the values are stored directly in a +memory buffer. +On the contrary, some images compress the space taken by the destination set +like the \verb+rle_image+. +These images use runs. +A run is a succession of points that share the same value. It is encoded by +a point (the beginning of the run), and an integer (the length of the run). +Runs allows \verb+rle_image+ to gain space in memory.\\ + +%% Explain what is a run + +%% Explain the different template parameters T/S/F... +All the image types are parametrized by different static parameters. +In this document, we will used the following namming convention for the +image types parameters: +\begin{itemize} +\item{\verb+T+:} represents an image value type. +\item{\verb+S+:} represents a type of a $sites$ set. +\item{\verb+F+:} is a type of a function $site$ to $value$. +\item{\verb+P+:} represents a $site$ type. +\item{\verb+I+:} represents an image type. +\end{itemize} + +\subsection{Primary images} + +%% Primary image definition + +Primary images are a major category of Milena image type. +Primary images are not based on another image type. +They are sufficient to define themselves. +Thus, a primary image types directly holds in memory its data (values). + + +\begin{itemize} + +\item{\verb+image2d<T>+}: rectangular images based on a 2d grid with all its +values stored in a buffer in memory. An extended domain is added to the image +domain. + +Related image type: \verb+image1d<T>+, \verb+image3d<T>+. + + +\item{\verb+mmap_image2d<T>+:} this image2d-like type has its values data +``memory mapped''. + +Related image types: \verb+mmap_image1d<T>+, \verb+mmap_image3d<T>+. + +\item{\verb+file_image2d<T>+:} this image2d-like type has its values data +stored in a file. + +Related image types: \verb+file_image1d<T>+, \verb+file_image3d<T>+. + +\item{\verb+tiled_image<T>+:} FIXME. + +\item{\verb+fun_image<S, F>+:} image type defined by a domain \verb+S+ and a +function f of type \verb+F+: $site \rightarrow value$. +f associates some values to each site composing the image. + +\item{\verb+flat_image<S, T>+:} defined by a domain and a value $v$. +All the sites composing a flat image share the same value $v$. + +\item{\verb+pkey_image<P, T>+:} defined by couples $(p,v)$ where the $site$ p +is a key to retrieve the values v. A map, a sorted associative container, is +used to store the couples $(p,v)$. + +\item{\verb+pvkeys_image<P, T>+:} defined by couples $(p,v)$ where the site p is a key, and at the same time, coherently maintaining couples +($v$, list of $p$) where the value v is the key. + + +%% FIXME Graph Image +\item{\verb+graph_image+:} FIXME + +%% FIXME what is a run... +\item{\verb+rle_image<P, T>+:} defined by couples $(r, v)$, where $r$ is a run +and $v$ a value. A value is associated to each run. + +\item{\verb+sparse_image<P, T>+:} defined by couples ($r$, list of $v$) where a +run $r$ is associated to a list of values. A value is associated to each +point composing a run. + +\item{\verb+value_enc_image<P, T>+:} defined by couples ($v$, list of $r$). +A list of run is associated to every values composing the image. This is a +value-driven image. + +\end{itemize} + +\subsection{Morphers} + +%% Morpher definition +A morpher transforms a type into another one. +It can be seen as an extension of the decorator design pattern. +Morphers are a non-intrusive way to add or modify some behaviors in an +existing class. +Here, the image morphers rest upon another image (the input image(s) which +will be transformed). +Since, it extends an image, an image morpher is also an image type. + +The Milena library provide different kinds of morphers. +Domain morphers only modify the domain (the set of points/sites composing the image) of the input image. +Value morphers only change the input image values (cast the values into another +type\ldots{}) +Identity morphers don't modify either the definition domain or the image +values. + + + +\subsubsection{Domain morphers} + +\begin{itemize} + +\item{\verb+sub_image<I, S>+:} restrict an image to a given sites set. + +\item{\verb+image_if<I, F>+:} restrict the input image domain to all the image +sites that satisfy a condition expressed by a function. + +\item{\verb+hexa<I>+:} make a hexagonal mesh of the input image (the input +image must be an image in two dimension). + +\item{\verb+translated image<I, T>+:} apply a translation of $dp$, a given +delta-point to all the sites composing the input image. +\end{itemize} + +\subsubsection{Value morphers} + +\begin{itemize} + +\item{\verb+f_image<F, I>+:} transform the image values through a "function". + +\item{\verb+f_images<F, n, I>+:} takes $n$ values from $n$ input images, +and transform them through a function (that return only one value). + +\item{\verb+lut_image<I, T>+:} use a translation table, to do a binding between the input image values and the morpher output values. + +\end{itemize} + + +\subsubsection{Identity morphers} + +\begin{itemize} +\item FIXME... +\end{itemize} + + +\subsection{Data access:} + +\begin{tabular}{ccl} + +image type & ima(p) & Details\\ +\hline + +\verb+image2d<T>+ & +\lstinline+values[p.row][p.col]+ & +\verb+values+ is a buffer containing all the image\\ +& +& +values.\\ + +\\ + +\verb+fun_image<S, F>+ & +\lstinline+f(p)+ & +\verb+f+ is the function associated to the image.\\ + +\verb+flat_image<T>+ & +\lstinline+v+ & +\verb+v+ is the flat value.\\ + +\\ + +\verb+pkey_image<P, T>+ & +\lstinline+map[p]+ & +\verb+map+ is a table that associates a value to\\ +& +& +each key \verb+p+.\\ + +\verb+pkeys_image<P, T>+ & +\lstinline+map[p]+ & +same as \verb+pkey_image<P, T>+.\\ + +\\ + +\verb+rle_image<P, T>+ & +\lstinline+values[r.in_index()]+ & +\verb+values+ is an array that associates a value\\ +& +& +to each run.\\ +& +& +\verb+in_index+ returns the index of the run in\\ +& +& +the image.\\ + +\verb+sparse_image<P, T>+ & +\lstinline+values[r.in_index()][r.out_index()]+ & +\verb+values+ is an 2D array that associates a\\ +& +& +value to each point in a run.\\ +& +& +\verb+in_index+ returns the index of the run in\\ +& +& +the image.\\ +& +& +\verb+out_index+ returns the index of the current\\ +& +& +point in the run.\\ + +\verb+value_enc_image<P, T>+ & +\lstinline+values[r.in_index()]+ & +\verb+values+ is an array that associates a values\\ +& +& +to each run.\\ + +\\ + +\verb+f_image<F, I>+ & +\lstinline+f(ref(p))+ & +\verb+f+ is the function associated to the morpher.\\ +& +& +\verb+ref+ is the underlying image.\\ + +\verb+f_images<F, n, I>+ & +\lstinline+f(ref_1(p), ref_2(p), ... ref_n(p))+ & +\verb+f+ is the function associated to the morpher.\\ +& +& +\verb+ref_n+ are the underlying images.\\ + + +\verb+lut_image<I, T>+ & +\lstinline+lut[ref(p)]+ & +\verb+lut+ is the morpher translation table.\\ +& +& +\verb+ref_n+ are the underlying images.\\ + +\end{tabular} + + Index: doc/tutorial/design/design.tex --- doc/tutorial/design/design.tex (revision 0) +++ doc/tutorial/design/design.tex (revision 0) @@ -0,0 +1,52 @@ +\documentclass{article} + +%% Packages +\usepackage{latexsym} +\usepackage{exscale} +\usepackage{amssymb} +\usepackage{amsbsy} +\usepackage{epstopdf} +\usepackage{graphicx} +\usepackage{makeidx} +%%\usepackage{placeins} +\usepackage{amsmath} +\usepackage{color} +\usepackage{listings} +%%\usepackage[all]{hypcap} + +\title{Milena - Images and properties} +\author{LRDE} +\date{} + +\makeindex +%%\usepackage[nottoc, notlof, notlot]{tocbibind} + +\lstset{ + frame=single, + basicstyle=\ttfamily, + framexleftmargin=1mm, + xleftmargin=1mm, + framexrightmargin=1mm, + xrightmargin=1mm, + language=C++, + basicstyle=\small, + keywordstyle=\color{blue}\bfseries, + commentstyle=\color{red}\textit, + stringstyle=\color{green}\ttfamily +} + +%%%LISTINGS SETTINGS + + + + +\begin{document} + +\maketitle + +\tableofcontents + +\include{include/imagetours} +\include{include/properties} + +\end{document} Index: doc/tutorial/design/Makefile --- doc/tutorial/design/Makefile (revision 0) +++ doc/tutorial/design/Makefile (revision 0) @@ -0,0 +1,29 @@ +FILE = design.tex +FILEGEN = $(FILE:.tex=.pdf) +SOURCE = +PDFLATEX = pdflatex + +FIND=find . +RM=rm +RMOPT=-rf + +all: pdf + +light: $(FILE) $(SOURCE) + $(PDFLATEX) $(FILE) + +pdf: $(FILE) $(SOURCE) + $(PDFLATEX) $(FILE) + $(PDFLATEX) $(FILE) + $(PDFLATEX) $(FILE) + +clean: + $(FIND) \( -name '*.toc' -o -name '*.aux' -o -name '*.bat' \) \ + -exec $(RM) $(RMOPT) {} \; + $(FIND) \( -name '*.glo' -o -name '*.log' -o -name '*.out' \) \ + -exec $(RM) $(RMOPT) {} \; + $(FIND) \( -name '#*' -o -name '*.aux' -o -name '*~' \ + -o -name '*.idx' \) -exec $(RM) $(RMOPT) {} \; + +distclean: clean + $(RM) $(RMOPT) $(FILEGEN) Index: doc/tutorial/images_tour.txt Index: sandbox/ballas/doc/image_tours.txt --- sandbox/ballas/doc/image_tours.txt (revision 2528) +++ sandbox/ballas/doc/image_tours.txt (working copy) @@ -47,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: