https://svn.lrde.epita.fr/svn/oln/trunk/milena
Index: ChangeLog
from Nicolas Ballas <ballas(a)lrde.epita.fr>
Continue documentation.
* sandbox/ballas/doc/image_tours.txt: Add run and lut image definition.
* sandbox/ballas/doc/draft.txt: Update.
draft.txt | 11 -
image_tours.txt | 368 +++++++++++++++++++++++++++++++++++++++++++++++++++-----
2 files changed, 345 insertions(+), 34 deletions(-)
Index: sandbox/ballas/doc/image_tours.txt
--- sandbox/ballas/doc/image_tours.txt (revision 1877)
+++ sandbox/ballas/doc/image_tours.txt (working copy)
@@ -282,11 +282,6 @@
io = read_only
speed = fast
---> properties related to values
-
-kind =??
-quant =??
-value = fixme
--> properties related to the pset
@@ -308,40 +303,188 @@
All the run based encoded images have their definition domains encoded by runs.
These images types are not morpher types since these do not lie on another
-image type.A run is a "continuous" (note this is wrong, cf graph index) set of
-sites.It is define by a site start, and a length. All the run based encoded
-image are templated by P, T where P is a site type and T a value type.
+image type.
+All the run based encoded images are templated by P, T where P is a site type
+and T a value type.
Note:
type one shot (const)!!!
Do we store the the null value in the rle encoding.
-(Do we compress all the images values, or only the image objects...)
+( <=> Do we compress all the images values, or only the image objects...)
Is there any restriction on P and T?
-How the properties are setted and to which values?
+*** Notation used:
+ (a, b) represents a pair composed by two elements..
+ {a, b, c...} represents a list of elements.
+
+*** What is a run?
+
+**** Definition
+
+// FIXME choose a better word than continuous.
+A run is a "continuous" succession of sites.
+All the sites encoded in a same run have the same value in the corresponding
+image.
+
+It is defined by a site "start", and a length.
+
+ex:
+ start length of
+ site the run
+ ((1, 2), 6 )
+
+
+ see the image:
+
+ 1 - 1 - 2
+ | | |
+ 2 - 2 - 2
+ | | |
+ 3 - 3 - 3
+
+Its corresponding runs are:
+{
+ ( (0, 0), 2 ),
+ ( (0, 2), 1 ),
+ ( (1, 0), 3 ),
+ ( (2, 0), 3 ),
+}
+
+Note: there is two different runs for the value 2:
+ ( (0, 2), 1 ),
+ ( (1, 0), 3 ).
+
+Indeed the points (0, 2) and (1, 0) are not "continuous".
+
+
+
+**** Difference between data stored in a linear way and runs.
+
+A run doesn't represent only a continuous memory zone.
+A run has also a localization aspect.
+From a run, we can get all the points which compose it.
+
+For instance, look at the following run:
+
+
+ i_run: 0 1 2 3
+ +-+-+-+-+
+ (0, 4) |1|1|1|1| <=> ( (0, 4), 4 )
+ +-+-+-+-+
+
+The points composing this run are:
+(0, 4), (0, 5), (0, 6), (0, 7)
+
+This property is really important to guarantee the interoperability
+between the different image types.
+
+**** PieceWise property
+
+The run is templated by a site type.
+But does we have any restriction on the type of site?
+
+The answer seems to be yes, the run must have a localization aspect.
+To allow this localization, we must be able to convert a p_run into its
+corresponding sites.
+So we must be able to convert a site and i_run index to another site.
+
+ex:
+
+(0, 4) + 3 give us the site (0, 7).
+
+It has two consequences:
+- a site must be convertible into a vector of coordinates
+- We must a know to which coordinate we add the i_run index to compute another
+ site. We will choose the coordinate which vary the most.
+
+This lead us to the PieceWise property:
+ The site can be represented by a vector of coordinates, and this vector has a
+coordinate which vary more than the other. (And we have an access to these
+coordinates).
+
-*** Criteria needed by images to be encoded in runs
+**** Why a run has to be a "continuous" succession of sites?
-Can we compress all the image types or only the piece wise image type
-(cf the on_the_same_line in the encode algorithm).
+We can imagine that a run is a succession of noncontinuous sites.
+For instance look at the following image:
-Currently, *encode function just work with image based on a **Point** set.
-cf:
-for (unsigned n = 0; same_line && n < dim - 1; ++n)
- same_line = (p1[n] == p2[n]);
+ 1 - 1 - 2
+ | | |
+ 2 - 2 - 2 This image is based on a grid which has its deltaX equal to 10
+ | | | and its deltaY equal to 30.
+ 1 - 1 - 1
-Problem generalization:
- A p_run take a Site as a parameter.
- a p_run must be able to be casted into the Site (actually, const Site).
- The only information that we have in the p_run is a len (integer).
- So we must be able to refind all the site in the run from the site start,
-and a addition with an integer.
+So the points localized on the grid are:
- How do we name this property?
+ (0, 0) - (10, 0) - (20, 0)
+ | | |
+ (0, 30) - (10, 30) - (20, 30)
+ | | |
+ (0, 60) - (10, 60) - (20, 60)
+The corresponding encoded image with "noncontinuous" runs will be:
+ { ((a,1), 2), ((b,2), 1), ((c,2), 3), ((c,3), 3) }
+
+with a = (0, 0), b = (20, 0), c = (0, 30), d = (0, 60).
+
+Another representation of the encoded image is:
+
+ i_run: 0 1 2
+ +-+-+
+ (0, 0) |1|1|
+ +-+-+
+ (20, 0) |2|
+ +-+-+-+
+ (0, 30) |2|2|2|
+ +-+-+-+
+ (0, 60) |1|1|1|
+ +-+-+-+
+
+Here, we loose the localization aspect of the psite.
+Indeed a psite (p_run) is represented by a site (pstart), and an integer
+(i_run). With these information, we can access to all the value in the encoded
+image. However we can not convert a psite (p_run) into a site (point2d).
+For instance:
+
+ psite -> site
+ (pstart: (0, 60) i_run: 2) -> (2, 60)
+
+However, the point (2, 60) doesn't belong to the image pset.
+The expected result here is (20, 60).
+This problem is an outcome of the holes present in the original image grid.
+So, this is an outcome of the "noncontinuous" aspect of the run.
+
+This approach implies one direct drawback: we loose the interoperability
+between the encoded image type and other image types (We cannot convert a
+p_run into the corresponding site).
+So, a run has to be a continuous succession set of points.
+
+Another solution is to store the deltaX of the grid inside the psite.
+This way, we have enough information to convert a p_run into a point2d.
+But encoding a graph image will not work either, even with the second
+solution. Indeed, nothing assure us that the site on a graph are "continuous".
+
+Do we need a property for that?.
+
+Another problem with "noncontinuous" run is the index access ambiguity.
+If the image provide an index access, the point represented by the indexes i,j
+is not necessarily the same point represented by the indexes i,j in the
+encoded image.
+
+
+**** Which kind of image can be encoded? / Conclusion
+
+We need two condition to encode an image type into a run encoded types.
+First the image psite type must be piece wise.
+Furthermore, the image must be based on a (regular) grid without any "holes".
+
+All image{1, 2, 3}d types can be encoded.
+Image based on a lut can be encoded too.
+Function image with a regular grid can be encoded.
+And morphers types based on a regular grid can be encoded too.
*** RLE Image
@@ -353,7 +496,6 @@
**** Associated types:
value = T
-
site = P
psite = runs_psite<P>
pset = p_runs_<P>
@@ -384,8 +526,32 @@
support = depend on P // The property setted in the milena code is wrong
+
+**** Example:
+
+Consider the following image on regular grid.
+
+ 1 - 1 - 2
+ | | |
+ 2 - 2 - 2
+ | | |
+ 1 - 1 - 1
+
+The encoded image is:
+
+{
+ psite value
+ ( ((0, 0), 2), 1 ),
+ ( ((0, 2), 1), 2 ),
+ ( ((1, 0), 3), 2 ),
+ ( ((2, 0), 3), 1 ),
+}
+
+
*** Compact RLE
+FIXME
+
*** Sparse Image
A RLE image can be defined as the following:
@@ -396,7 +562,6 @@
**** Associated types:
value = T
-
site = P
psite = runs_psite<P>
pset = p_runs_<P>
@@ -405,9 +570,157 @@
Same properties than the RLE Image type.
+**** Examples:
+
+Consider the following images:
+
+The empty case denote there is no data at this coordinate.
+
+ 1 - 2 - 3 - - -
+ | | | | | |
+ - - - 2 - 2 - 2
+ | | | | | |
+ - - - 4 - 5 - 8
+ | | | | | |
+ - - - - -
+
+
+Its sparse encoding is:
+
+{ psite values
+ ( ((0, 0), 3), {1, 2, 3}),
+ ( ((1, 3), 3), {2, 2, 2}),
+ ( ((2, 3), 3), {4, 5, 6}),
+}
+
+
*** Value encoded image
+**** Definition:
+
+A value image is an image which associate a value to its corresponding psite.
+So, we can easily get all the psites/site which have their (in O(1) complexity)
+
+{
+ (v, {runs})
+}
+
+**** Associate types:
+
+value = T
+site = P
+psite = runs_psite<P>
+pset = p_runs_<P>
+
+**** Properties:
+ Same as rle image.
+
+**** Example:
+
+
+See
+ 1 - 1 - 1 - - -
+ | | | | | |
+ - - - 2 - 2 - 2
+ | | | | | |
+ - - - 2 - 2 - 2
+ | | | | | |
+ 3 - 3 - 3 - 4 - 4 - 4
+
+The corresponding encoded image is:
+
+
+{
+ (1, {((0, 0), 3)} ),
+
+ (2, {((1, 3), 3),
+ ((2, 3), 3)} ),
+
+ (3, {((3, 0), 3)} ),
+
+ (4, {((3, 3), 3)} )
+}
+
+
+*** Image based on Lut
+
+**** Definition
+
+An image based on a lut is primitive image type.
+This kind of image use a look up table to retrieve a value
+associated to an image site.
+
+It can be defines as followed:
+
+ ({values}, {lut_values})
+
+
+FIXME: How do we deal with the dimensions of the images?
+
+
+
+**** Associated type
+
+site=P
+psite=P
+value=V
+pset=pset<P>
+
+
+**** Property:
+
+--> global properties
+
+category = primary
+border = none
+neighb: none
+data = stored
+io = read_write
+speed = fast
+
+--> properties related to values
+
+kind =
+quant =small
+value = V
+
+--> properties related to the pset
+
+access = browsing // Why the access property is set to browsing?
+space = pset<P>::space
+size = regular
+support = pset<P>::supper
+
+
+**** Example:
+
+Consider this image type:
+
+{ data =
+ +-----------+
+ | 0 2 1 0 2 |
+ | 0 0 3 2 1 |
+ | 2 1 2 2 0 |
+ +-----------+;
+ lut =
+ +---+---------------+
+ | 0 | (255, 0, 0) | red (r)
+ | 1 | (127,127,127) | medium grey (m)
+ | 2 | ( 0, 0,255) | blue (b)
+ | 3 | (127,127,127) | medium grey (m) again
+ +---+---------------+
+}
+
+This image is defined with a look-up table; its external
+representation actually is:
+
+ +-----------+
+ | r b m r b |
+ | r r m b m |
+ | b m b b r |
+ +-----------+
+
** Graph Image
@@ -415,9 +728,6 @@
**** Connectivity based on a graph.
-
-** Image based on Lut
-
** Morpher (Derived Image)
Mopher are Image types which transform an Image type into a new type. So, they
Index: sandbox/ballas/doc/draft.txt
--- sandbox/ballas/doc/draft.txt (revision 1877)
+++ sandbox/ballas/doc/draft.txt (working copy)
@@ -246,9 +246,6 @@
property of the grid are useless.
-
-
-
* Property that we need?
** has(p)
@@ -299,7 +296,7 @@
This function can be specialize for image/pset types that provide an access
time in O(1).
-In this case a method nsite will be present in the pset inteface:
+In this case a method nsite will be present in the pset interface:
return ima.pset().nsites();
So we need a pset property to define the complexity of accessing to the number
@@ -345,7 +342,7 @@
regular grid). An gbox is composed by point2d.
If the image is based on a grid, it can return a ibox. We can access to the
image values through a couple (i, j). But each couple (i, j) doesn't represent
-necessary a point2d (anystrope, unaligned grid...).
+necessary a point2d (anisotropic, unaligned grid...).
If the image localization is space, we can return a xbox (box which is not
based on a grid).
@@ -367,3 +364,7 @@
idea:
boxed : true,
false
+
+** pieceWise property
+
+see the image tours files.
URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena
ChangeLog:
2008-04-20 Matthieu Garrigues <garrigues(a)lrde.epita.fr>
Start to test another algorithm for FLLT.
* sandbox/garrigues/fllt/fllt_simple.cc: New.
---
fllt_simple.cc | 325 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 325 insertions(+)
Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc
===================================================================
--- trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 0)
+++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 1876)
@@ -0,0 +1,325 @@
+// Copyright (C) 2008 EPITA Research and Development Laboratory
+//
+// This file is part of the Olena Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License version 2 as published by the
+// Free Software Foundation.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING. If not, write to
+// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+// Boston, MA 02111-1307, USA.
+//
+// As a special exception, you may use this file as part of a free
+// software library without restriction. Specifically, if other files
+// instantiate templates or use macros or inline functions from this
+// file, or you compile this file and link it with other files to
+// produce an executable, this file does not by itself cause the
+// resulting executable to be covered by the GNU General Public
+// License. This exception does not however invalidate any other
+// reasons why the executable file might be covered by the GNU General
+// Public License.
+
+#include <iomanip>
+#include <iostream>
+#include <sstream>
+
+#include <mln/core/image2d.hh>
+#include <mln/core/sub_image.hh>
+#include <mln/core/neighb2d.hh>
+#include <mln/core/p_array.hh>
+#include <mln/core/clone.hh>
+
+#include <mln/value/int_u8.hh>
+
+#include <mln/io/pgm/load.hh>
+#include <mln/io/pgm/save.hh>
+
+#include <mln/level/fill.hh>
+#include <mln/debug/println.hh>
+#include <mln/labeling/regional_minima.hh>
+#include <mln/accu/bbox.hh>
+#include <mln/io/pgm/save.hh>
+
+
+#include <mln/core/cast_image.hh>
+
+namespace mln
+{
+ // Un autre version recursive de la fllt.
+
+ // Idee :
+ // Parcourir l'image en pratant d'un coin de preference,
+ // le parcour des pixels se fait dans un ordre conexe.
+ //
+
+ /*
+
+ fonction fllt_rec(racine R, domaine D, marques M, conexite C)
+ {
+ pour tout les points du domaine non marquees
+ recuperer la composante conexe A (en conexite C) qui inclut ce point :
+ Ceci est fait avec la methode de grossissement de region
+ pour avoir acces a la bordure externe et donc aux trous
+ de la composante.
+
+ Cette composante sera fille de R dans l'arbre d'inclusion.
+
+ Marquer les points de A (Peut etre fait en meme temps que la
+ construction de A)
+
+ Pour chaque trous T de A :
+ appel recursif : fllt_rec(A, T.domaine(), marques, inv(C))
+ T.domaine() sera calculer en recuperant la composante connexe
+ de la bordure de A lui correspondant (On recupere facilement
+ les segments horizontaux qui le composent -> parcour ok).
+
+ }
+ inv(c4) = c8
+ inv(c8) = c4
+
+
+ Autre version qui Marche sur les images hexagonales (Plus rapide et plus simple)
+ car il y a plus le probleme du theoreme de jordan non verifie.
+ FIXME: Est-ce que rendre l'image hexagonale altere vraiment le resultat?
+
+ pour tout les points du domaine non marquees
+ recuperer la composante conexe A qui inclut ce point :
+ Ceci est fait avec la methode de grossissement de region
+ pour avoir acces a la bordure externe et donc aux trous
+ de la composante.
+
+ Marquer les points de A (Peut etre fait en meme temps que la
+ construction de A)
+
+ Marquer les extremites des trou de A.
+
+ Si un point de A est l'extremite d'un trou,
+ alors on a facilement le pere de A (la forme qui inclue A).
+ Sinon
+ C'est qu'il y a une composante connexe adjacente qui
+ a deja ete construite, et qui a donc deja un pere, qui
+ est aussi celui de A.
+
+ continuer jusqu'a avoir marquer tout les points
+
+ */
+
+ namespace my
+ {
+
+
+ void save_u(const image2d<value::int_u8>& u,
+ const image2d<unsigned char>& is,
+ box2d R_box)
+ {
+ static int id = 0;
+ std::stringstream filename;
+ filename << "fllt_u_" << std::setw(5) << std::setfill('0')
+ << std::right << id++ << ".ppm";
+
+ image2d<value::int_u8> out = clone(u);
+ const unsigned in_R = 255;
+
+ mln_piter_(box2d) p(R_box);
+ for_all(p)
+ if (is(p) == in_R)
+ out(p) = 255;
+
+ io::pgm::save(out, filename.str());
+ }
+
+ void swap_arrays(p_array<point2d>*& A,
+ p_array<point2d>*& N)
+ {
+ p_array<point2d>* tmp = A;
+ A = N;
+ N = tmp;
+ }
+
+ template <typename I, typename Nbh>
+ void fllt(const Image<I>& input_, const Neighborhood<Nbh>& nbh_)
+ {
+ const I& input = exact(input_);
+ const Nbh& nbh = exact(nbh_);
+
+ // Variables.
+ I u = mln::clone(input);
+ mln_point(I) x0;
+ mln_value(I) g, gN;
+ image2d<unsigned char> is(input.domain());
+ image2d<bool> tagged(input.domain());
+ const unsigned in_R = 255, in_N = 2, in_O = 0;
+
+ typedef p_array<mln_point(I)> arr_t;
+ arr_t* A = new arr_t();
+ arr_t* N = new arr_t();
+
+ accu::bbox<mln_point(I)> R_box, N_box;
+
+ unsigned n_step_1 = 0, n_step_3 = 0;
+
+ level::fill(tagged, false);
+ mln_piter(I) min(input.domain());
+ min.start();
+ // Step 1.
+ step_1:
+ {
+#ifdef FLLTDEBUG
+ std::cout << "Step 1" << std::endl;
+#endif
+ ++n_step_1;
+ for(min.next(); min.is_valid(); min.next())
+ if (!tagged(min))
+ break;
+
+ if (!min.is_valid())
+ goto end;
+
+ x0 = min;
+ g = input(x0);
+ }
+
+ // Step 2.
+ step_2:
+ {
+#ifdef FLLTDEBUG
+ std::cout << "Step 2" << std::endl;
+#endif
+ if (N_box.is_valid())
+ level::fill(inplace(is | N_box.to_result()), in_O);
+
+ N_box.init();
+ R_box.init();
+ A->clear();
+ A->append(x0);
+ N->clear();
+ }
+
+ // Step 3.
+ step_3:
+ {
+ ++n_step_3;
+#ifdef FLLTDEBUG
+ std::cout << "Step 3" << std::endl;
+#endif
+ mln_piter(arr_t) a(*A);
+ mln_niter(Nbh) x(nbh, a);
+
+ // Stop.
+ if (A->npoints() == 0)
+ goto end;
+
+ // R <- R U A
+#ifdef FLLTDEBUG
+ std::cout << "Add To R : ";
+#endif
+ for_all(a)
+ {
+ tagged(a) = true;
+ is(a) = in_R;
+#ifdef FLLTDEBUG
+ std::cout << a;
+#endif
+ }
+#ifdef FLLTDEBUG
+ std::cout << std::endl;
+#endif
+
+
+#ifdef FLLTDEBUG
+ std::cout << "points of A : " << A->npoints() << std::endl;
+#endif
+ mln_assertion(A->npoints() > 0);
+ R_box.take(A->bbox());
+ mln_assertion(R_box.is_valid());
+
+#ifdef FLLTTRACE
+ save_u(u, is, R_box);
+#endif
+ // N <- N U { x in nbh of A and not in R / input(x) == g}
+#ifdef FLLTDEBUG
+ std::cout << "Add To N : ";
+#endif
+ for_all(a)
+ for_all(x)
+ if (u.has(x) && is(x) == in_O && input(x) == g)
+ {
+ mln_assertion(!tagged(x));
+ N_box.take(x);
+ is(x) = in_N;
+ N->append(x);
+#ifdef FLLTDEBUG
+ std::cout << x;
+#endif
+ }
+#ifdef FLLTDEBUG
+ std::cout << std::endl;
+#endif
+
+#ifdef FLLTDEBUG
+ std::cout << "g = " << g << std::endl;
+#endif
+
+ // Stop if N is empty.
+ if (N->npoints() == 0)
+ goto step_1;
+ else
+ {
+ swap_arrays(A, N);
+ N->clear();
+ goto step_3;
+ }
+ }
+
+ step_4:
+ {
+ // Follow N, find the holes, and browse it.
+ }
+
+ end:
+ {
+ std::cout << n_step_1 << ' ' << n_step_3 << std::endl;
+ }
+ }
+
+ } // end of namespace mln::my
+
+} // end of namespace mln
+
+
+int main()
+{
+ using namespace mln;
+ using value::int_u8;
+
+ image2d<int_u8> lena;
+
+ io::pgm::load(lena, "../../../img/lena.pgm");
+
+
+ // int_u8 vs[9][9] = {
+
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+ // { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
+
+ // };
+
+ //image2d<int_u8> lena = make::image2d(vs);
+
+ my::fllt(lena, c4());
+ io::pgm::save(lena, "./out.pgm");
+
+}
