March 2008 - Olena-patches

1813: Fix naive DT in Etienne's sandbox.
by Thierry Geraud 27 Mar '08

27 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix naive DT in Etienne's sandbox. * milena/sandbox/folio/naive.cc: Fix. naive.cc | 35 +++++++++++++---------------------- 1 files changed, 13 insertions(+), 22 deletions(-) Index: milena/sandbox/folio/naive.cc --- milena/sandbox/folio/naive.cc (revision 1812) +++ milena/sandbox/folio/naive.cc (working copy) @@ -35,6 +35,7 @@ # define MLN_DT_NAIVE_HH # include <mln/core/concept/image.hh> +# include <mln/core/concept/function.hh> # include <mln/literal/zero.hh> # include <mln/accu/min.hh> @@ -56,8 +57,8 @@ */ template <typename I, typename F> inline - mln_ch_value(I, typename F::ret) - naive(const Image& input_, F& fun_); + mln_ch_value(I, mln_result(F)) + naive(const Image& input_, const Function_v2v<F>& fun_); # ifndef MLN_INCLUDE_ONLY @@ -66,14 +67,15 @@ template <typename I, typename F> inline - mln_ch_value(I, typename F::ret) - naive(const Image& input_, F& fun_) + mln_ch_value(I, mln_result(F)) + naive(const Image& input_, const Function_v2v<F>& fun_) { const I& input = exact(input_); + const F& fun = exact(fun_); mln_precondition(input.has_data()); - mln_ch_value(I, typename F::ret) output; - initialize(input.domain()); + mln_ch_value(I, mln_result(F)) output; + initialize(output, input); mln_piter(I) p(input.domain()); for_all(p) @@ -83,7 +85,7 @@ else { // p is in the background so the distance has to be computed. - accu::min_<typename F::ret> min; + accu::min_<mln_result(F)> min; min.init(); mln_piter(I) q(input.domain()); @@ -93,7 +95,7 @@ // q is in the object. // metal::vec<2, int> vp = p.to_point(), vq = q.to_point(); // min.take(fun_(vp, vq)); - min.take(fun_(p, q)); + min.take(fun(p - q)); } output(p) = min; } @@ -114,18 +116,7 @@ #include <mln/debug/println.hh> #include <mln/core/image2d.hh> #include <mln/level/fill.hh> -#include <mln/norm/l2.hh> - -struct l2norm -{ - typedef float ret; - template <typename C, typename D> - D - operator()(C a, C b) - { - return mln::norm::l2(a, b); - } -}; +#include <mln/fun/v2v/norm.hh> int main() { @@ -142,8 +133,8 @@ level::fill(ima, vals); debug::println(ima); - l2norm fun; - image2d<float> out = dt::naive(ima, fun); + typedef fun::v2v::l2_norm< algebra::vec<2,float>, float > L2; + image2d<float> out = dt::naive(ima, L2()); std::cerr << "Distance:" << std::endl; debug::println(out);

1 0

1812: Sandbox: ICP: use of projection maps
by Ugo Jardonnet 27 Mar '08

27 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <jardonnet(a)lrde.epita.fr> Sandbox: ICP: use of projection maps. * mln/binarization/thresholding.hh: Renamed as * mln/binarization/threshold.hh. * sandbox/jardonnet/test/icp.cc: Update: maps. * sandbox/jardonnet/registration/icp.hh: . * sandbox/jardonnet/registration/projection.hh: . mln/binarization/threshold.hh | 18 +++---- sandbox/jardonnet/registration/icp.hh | 63 +++++++++++---------------- sandbox/jardonnet/registration/jacobi.hh | 2 sandbox/jardonnet/registration/projection.hh | 25 +++++++++- sandbox/jardonnet/test/icp.cc | 4 - 5 files changed, 61 insertions(+), 51 deletions(-) Index: mln/binarization/threshold.hh --- mln/binarization/threshold.hh (revision 1811) +++ mln/binarization/threshold.hh (working copy) @@ -25,10 +25,10 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_BINARIZATION_THRESHOLDING_HH -# define MLN_BINARIZATION_THRESHOLDING_HH +#ifndef MLN_BINARIZATION_THRESHOLD_HH +# define MLN_BINARIZATION_THRESHOLD_HH -/*! \file mln/binarization/thresholding.hh +/*! \file mln/binarization/threshold.hh * * \brief Threshold the contents of an image into another binary one. */ @@ -55,7 +55,7 @@ */ template <typename I> mln_concrete_ch_value(I, bool) - thresholding(const Image& input, const mln_value(I) threshold); + threshold(const Image& input, const mln_value(I) threshold); # ifndef MLN_INCLUDE_ONLY @@ -63,9 +63,9 @@ template <typename I> inline mln_concrete_ch_value(I, bool) - thresholding(const Image& input, const mln_value(I) threshold) + threshold(const Image& input, const mln_value(I) value) { - trace::entering("binarization::thresholding"); + trace::entering("binarization::threshold"); mln_precondition(exact(input).has_data()); mlc_is(mln_trait_value_nature(mln_value(I)), @@ -73,10 +73,10 @@ mln_concrete_ch_value(I, bool) output(exact(input).domain()); - fun::v2b::threshold< mln_value(I) > f(threshold); + fun::v2b::threshold< mln_value(I) > f(value); output = binarization::binarization(exact(input), f); - trace::exiting("binarization::thresholding"); + trace::exiting("binarization::threshold"); return output; } @@ -87,4 +87,4 @@ } // end of namespace mln -#endif // ! MLN_BINARIZATION_THRESHOLDING_HH +#endif // ! MLN_BINARIZATION_THRESHOLD_HH Index: sandbox/jardonnet/test/icp.cc --- sandbox/jardonnet/test/icp.cc (revision 1811) +++ sandbox/jardonnet/test/icp.cc (working copy) @@ -15,8 +15,6 @@ io::pbm::load(img1, argv[1]); io::pbm::load(img2, argv[2]); - image2d< bool > res(img1.domain()); - - io::pbm::save(registration::icp(img1,img2,res), "./+registred.pbm"); + io::pbm::save(registration::icp(img1,img2), "./+registred.pbm"); } Index: sandbox/jardonnet/registration/jacobi.hh --- sandbox/jardonnet/registration/jacobi.hh (revision 1811) +++ sandbox/jardonnet/registration/jacobi.hh (working copy) @@ -7,9 +7,11 @@ // from num. rec. in C + namespace mln { + #define rotateJacobi(a,i,j,k,l) g=a(i,j);h=a(k,l);a(i,j)=g-s*(h+g*tau); \ a(k,l)=h+s*(g-h*tau); Index: sandbox/jardonnet/registration/icp.hh --- sandbox/jardonnet/registration/icp.hh (revision 1811) +++ sandbox/jardonnet/registration/icp.hh (working copy) @@ -54,10 +54,9 @@ */ template <typename I, typename J> inline - I + mln_concrete(I) icp(const Image& cloud, - const Image<J>& surface, - I& r); + const Image<J>& surface); # ifndef MLN_INCLUDE_ONLY @@ -66,23 +65,17 @@ template <typename P, typename T1, typename T2> inline - void + p_array icp_(const p_array& C, - const p_array& X, - std::pair<T1,T2>&, - p_array& Ck) + const p_array&, + std::pair<T1,T2>& map) { trace::entering("registration::impl::icp_"); unsigned int k; quat7<P::dim> old_qk, qk; float err, err_bis; - - assert(Ck.npoints() == C.npoints()); - p_array Xk(C); //FIXME:is it correct? - /// Ck.reserve(C.npoints()); - //Xk.reserve(C.npoints()); - //assert(C.npoints() != 0); + p_array Ck(C), Xk(C); algebra::vec<P::dim,float> mu_C = center(C), mu_Xk; @@ -93,19 +86,19 @@ Ck = C; do { - std::cout << "step2" << std::endl; - //step 2 FIXME : etienne - projection::de_base(Ck, X, Xk, err_bis); + std::cout << "step2: projection" << std::endl; + //step 2 + err_bis = projection::fill_Xk(Ck, map, Xk); - std::cout << "step2.1 center" << std::endl; + std::cout << "step2.1: center" << std::endl; mu_Xk = center(Xk); - std::cout << "step3" << std::endl; + std::cout << "step3: Compute qk" << std::endl; // step 3 old_qk = qk; qk = match(C, mu_C, Xk, mu_Xk); - std::cout << "step4" << std::endl; + std::cout << "step4: apply qk" << std::endl; // step 4 qk.apply_on(C, Ck); // Ck+1 = qk(C) @@ -113,10 +106,11 @@ err = rms(Ck, Xk); ++k; - std::cout << err << std::endl; + std::cout << "error is " << err << std::endl; } while (k < 3 || (qk - old_qk).sqr_norm() > epsilon); trace::exiting("registration::impl::icp_"); + return Ck; } } // end of namespace mln::registration::impl @@ -161,10 +155,9 @@ //Only for 2d and 3d image template <typename I, typename J> inline - I + mln_concrete(I) icp(Image& cloud_, - const Image<J>& surface_, - I& r) + const Image<J>& surface_) { trace::entering("registration::icp"); mln_precondition(exact(cloud_).has_data()); @@ -178,15 +171,13 @@ std::cout << "chamfer" << std::endl; - /* + //FIXME: not a chamfer. etienne? //create a pair (distance map, closest point) - w_window<mln_dpoint(I3d), float> chamfer; - */ - std::pair<mln_ch_value(I3d,float), mln_ch_value(I3d,mln_point(I3d)) > maps; - /* + // window<dpoint3d> win3d; + w_window<dpoint3d, float> chamfer; // = make::w_window(win3d, fun); + std::pair<mln_ch_value(I3d,float), mln_ch_value(I3d,mln_point(I3d)) > maps = dt::chamfer(surface, chamfer); - */ std::cout << "Build p_array" << std::endl; //build p_arrays. @@ -203,18 +194,18 @@ x.append(p2); std::cout << "Start ICP" << std::endl; + p_array<mln_point(I3d)> res = impl::icp_(c, x, maps); - p_array<mln_point(I3d)> res(c); - impl::icp_(c, x, maps, res); - - //to 2d - for (unsigned e; e < res.npoints(); e++) + //to 2d : projection (FIXME:if 3d) + mln_concrete(I) output(exact(cloud_).domain()); + for (unsigned i; i < res.npoints(); i++) { - point2d p(res[e][0], res[e][1]); - r(p) = true; + point2d p(res[i][0], res[i][1]); + output(p) = true; } trace::exiting("registration::icp"); + return output; } # endif // ! MLN_INCLUDE_ONLY Index: sandbox/jardonnet/registration/projection.hh --- sandbox/jardonnet/registration/projection.hh (revision 1811) +++ sandbox/jardonnet/registration/projection.hh (working copy) @@ -10,6 +10,27 @@ namespace projection { + template <typename P, typename T1, typename T2> + float fill_Xk(const p_array& Ck, + std::pair<T1,T2>& map, + p_array& Xk) + { + assert(Ck.npoints() == Xk.npoints()); + + float err = 0.f; + + for (size_t i = 0; i < Ck.npoints(); ++i) + { + //x[i] := Ck[i] closest point in X + Xk.hook_()[i] = map.second(Ck[i]); + //err := Distance between Ck[i] and its closest point + err += map.first(Ck[i]); + } + return err /= Ck.npoints(); + } + + + template <typename P> void de_base(// input const p_array& Ck, @@ -18,7 +39,7 @@ p_array& Xk, float& err) { - // assert(Ck.npoints() == Xk.npoints()); + assert(Ck.npoints() == Xk.npoints()); err = 0.f; @@ -37,13 +58,11 @@ best_x = Xj; } } - if (i < Xk.npoints()) // FIXME:double hack Xk.hook_()[i] = algebra::to_point(best_x); err += best_d; } err /= Ck.npoints(); } - } }

1 0

1811: Augment doc about image types.
by Thierry Geraud 27 Mar '08

27 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Augment doc about image types. * milena/doc/tutorial/image_types.txt: Augment. image_types.txt | 220 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 216 insertions(+), 4 deletions(-) Index: milena/doc/tutorial/image_types.txt --- milena/doc/tutorial/image_types.txt (revision 1810) +++ milena/doc/tutorial/image_types.txt (working copy) @@ -24,10 +24,141 @@ signature is "ima(p : psite) : rvalue" -** about domain and destination +** about domain, site, and psite -ima.domain is usually a mathematical set. Yet it can be a -multiset (a bag) but then weird things might happen... +*** need for psite + +Sometimes, accessing a value in constant-time complexity, O(1), is not +possible with a site object. + +Example with a run-length encoded image : + + c 6 7 8 9 + r + +-+-+-+ + 3 | |x| | + +-+-+-+-+ + 4 | | | + +-+-+ + +The site x is the point (3, 7). The image values are stored in a +multi-array where the first index is the one of the run and the second +index the offset of the cell from the beginning of the run. The site +x thus corresponds to the cell (0, 1). + + j= 0 1 2 + +-+-+-+ +i= 0 | |x| | + +-+-+-+-+ +i= 1 | | | + +-+-+ + j= 0 1 + +Here we have: + + I::site = point2d but I::psite = run_point2d + +where, roughly, run_point2d = { i_of_run, i_in_run, run_ptr }. + + +*** from psite to site + +Consider that we have an image type I such as I::site != I::psite. In +that case, an object of type I::psite is convertible towards an object +of type I::site. Furthermore, a psite shall behave as if it was a +site. + +Design note: it seems impossible to offer through the interface of +some psite what is expected from its corresponding site. For +instance, when a site has a given feature, say a method "m", then this +method has to appear in the psite interface. Idea: thanks to +inheritance, we fetch an interface + an implementation that delegates +to the site. + +Example: run_point2d has a method ::row() because point2d provides +such a method. How it works: a psite inherits from +internal::site_impl<site> which is specialized for every site type; +for instance, internal::site_impl<point2d> owns the method "coord +row() const" which is defined as "return exact(this)->to_site().row()" + +This is of course only true for read-only methods. + + +*** site location + +A point of a space (the 2D plane or 3D space) is about equivalent to a +vector. We do not distinguish between those two notions: a point M is +like the vector OM where O is the origin of the space. + +We have mln::vec<dim,coord> (space vector) built over +metal::array<n,T> (static container). When dim = 2, we have vec::x() +and vec::y() to access the coordinates, in addition to the more +general method vec::op[](i). On the other side, we have +array::element() to access the i-th element. + +We do not ambiguity: grid point 2d (i,j) v. 2D plane point +(x,y) v. 2D vector (x,y) + +ideas: gpoint2d v. spoint2d !!! + + +*** iterating and ordering + +The iteration mechanism for images is directly derived from the +mechanism for site set. A site set is iterable in a forward way. +This way depends on the structure of the set; Cf. the documentation. +The reserve iteration way, called backward, can always be defined +because we only provide bidirectional containers. The ordering +relationship corresponding to the forward iteration browsing is +"fwd_less". + +The basic iterator has the only property of browsing every site once. +It is often identical to the forward iterator but it is not a +requirement. FIXME: find an example where it is not the case. + +When sites are localized, a special ordering between such sites is +defined, based on the site localization. More precisely, it is a +lexicographical ordering considering the coordinates going from the +first component (at index 0) to the last one (at index dim - 1). This +is location_less. In most cases, we cannot provide an iterator that +follows this spatial ordering because the underlying structures are +usually not suited for such an iterator to be efficient. + +FIXME: hypothesis and property for superior_window and inferior_window. + + +*** arithmetics over sites + +psite + dpsite -> psite when compatible (?) + site + dpsite = (re-written) site + dsite (when possible) -> site +psite + dsite = (re-written) site + dsite (when possible) -> site + +Example: +run_psite2d + dpoint2d -> point2d + + +FIXME: more examples + + +** about value, rvalue, and lvalue + +Image types provide a method to access values, namely "operator() const". +Yet, its signature is NOT "value operator()(const site& p) const" +but "rvalue operator()(const psite& p) const" + +For instance, with I being image2d<int_u8>, we have : + + I::value = int_u8 but I::rvalue = const int_u8& + +so copying the value when the call "f(p)" returns is avoided. +In that case, it is a low-level implementation issue that makes rvalue +be different from value. In some other cases, the difference can be +more fundamental. For instance, a proxy is returned so that some extra +code is performed if this value is eventually read (FIXME: take a better +example). + + +** about destination ima.destination is a set. Every value, that is ima(p) with p in ima.domain, is taken from this set. For instance, a color image can @@ -215,6 +346,8 @@ ** associated types +*** list of associated types + mesh (? support) pset (? domain_t) site @@ -233,6 +366,41 @@ skeleton +*** value +Type of values enclosed in the image container. +By copie; not by reference (not T&). +Might be a pointer (T*). +Assignable and copiable (not a shallow copy). + +Ex: int_u8, etc. + +*** site +Type of the cell containing a value. + +*** required for implementation purpose +rvalue, lvalue, and psite; see later. + +*** location +A site can be localized into a given space, e.g., the 2D plane and can +be point-wise. In that case, the associated type "location" gives the +corresponding type of space vector. For instance, with a classical 2D +image, a site is a 2D point (node of the regular square grid) and the +location is trivially a vector of the 2D plane. + +When a site is not point-wise, some implementation can also provide a +location; this can be convenient in order to get a spacial +representation of sites and images. For instance, consider that we +have a tesselation computed from point seeds (a Voronoi diagram for +instance) and a structure (the corresponding Delaunay triangulation) +where a site is a tile of this tesselation. A tile can be identified +without ambiguity through its seed; this seed point is then the +representative point for that tile. By extension, we can state that +the location of a tile is its seed. + +For some image types, sites are not localized and a special type is +used to define ::location. + + ** methods @@ -551,6 +719,13 @@ ** image2d<T> +regular square grid where grid nodes are objects of type point2d +(row, col), a couple of integer coordinates + +psite = point2d = point_<grid2d,int> +site = point2d +location = vec<2,int> (more precise than vec<2,float>) + ** fun_image<S,F> pset = S @@ -558,6 +733,43 @@ read_only +** geometrical transformation (morpher) + +An image computed on the fly from another image on which a geometrical +transformation is applied. A geometrical transformation is either a +function + + site_set -> site_set + site |-> site + +or a function + + site_set_in -> site_set_out + site_in |-> site_out + +In the first case, the resulting image has the same point set as the +initial image (example : clock-wise rotation of 90Â°, translation of a +vector with integral coordinates). + +In the second case, the resulting image has a different point set, +reflecting a possibly different domain or topology (example: arbitrary +rotation). + + +images (f, T) -> g + + +g(p) = f( T(p) ) +so : +g( T_1(p) ) = f(p) + +or : + +g( T(p) ) = f(p) + + +FIXME: to be continued. + * value morpher -pset is \ No newline at end of file +FIXME

1 0

1810: Sandbox: ICP: draft improvment.
by Ugo Jardonnet 26 Mar '08

26 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Sandbox: ICP: draft improvment. * sandbox/jardonnet/test/Makefile: -O3 version. * sandbox/jardonnet/test/icp.cc: image loading. * sandbox/jardonnet/registration/quat7.hh: Update. * sandbox/jardonnet/registration/chamfer.hh: Etienne's. * sandbox/jardonnet/registration/cloud.hh: Correction. * sandbox/jardonnet/registration/icp.hh: Update. * sandbox/jardonnet/registration/projection.hh: To be removed. * sandbox/jardonnet/registration/quat/rotation.hh: s/3/n/. mln/make/mat.hh | 2 sandbox/folio/naive.cc | 14 + sandbox/jardonnet/registration/chamfer.hh | 189 ++++++++++++++++++++++++ sandbox/jardonnet/registration/cloud.hh | 7 sandbox/jardonnet/registration/icp.hh | 124 +++++++++++++-- sandbox/jardonnet/registration/projection.hh | 3 sandbox/jardonnet/registration/quat/rotation.hh | 7 sandbox/jardonnet/registration/quat7.hh | 5 sandbox/jardonnet/test/Makefile | 3 sandbox/jardonnet/test/icp.cc | 16 +- 10 files changed, 334 insertions(+), 36 deletions(-) Index: mln/make/mat.hh --- mln/make/mat.hh (revision 1809) +++ mln/make/mat.hh (working copy) @@ -71,7 +71,7 @@ { algebra::mat<n,1,T> tmp; for (unsigned i = 0; i < n; i++) - tmp(i,1) = v[i]; + tmp(i,0) = v[i]; return tmp; } Index: sandbox/jardonnet/test/icp.cc --- sandbox/jardonnet/test/icp.cc (revision 1809) +++ sandbox/jardonnet/test/icp.cc (working copy) @@ -1,16 +1,22 @@ #include <mln/core/image3d.hh> -#include <mln/io/ppm/load.hh> -#include <mln/io/ppm/save.hh> +#include <mln/io/pbm/load.hh> +#include <mln/io/pbm/save.hh> #include <sandbox/jardonnet/registration/icp.hh> -int main(int, char*) +int main(int, char* argv[]) { using namespace mln; - image3d< value::rgb8 > img; + image2d< bool > img1; + image2d< bool > img2; - registration::icp(img,img); + io::pbm::load(img1, argv[1]); + io::pbm::load(img2, argv[2]); + + image2d< bool > res(img1.domain()); + + io::pbm::save(registration::icp(img1,img2,res), "./+registred.pbm"); } Index: sandbox/jardonnet/test/Makefile --- sandbox/jardonnet/test/Makefile (revision 1809) +++ sandbox/jardonnet/test/Makefile (working copy) @@ -16,6 +16,9 @@ icp: g++ icp.cc $(FLAG) -o '+icp.exe' +icp++: + g++ icp.cc -I../../.. -O3 -o '+icp.exe' + run: time ./+sub.exe . . ; time ./+gsub.exe . . Index: sandbox/jardonnet/registration/quat7.hh --- sandbox/jardonnet/registration/quat7.hh (revision 1809) +++ sandbox/jardonnet/registration/quat7.hh (working copy) @@ -122,20 +122,23 @@ // qR //FIXME : use P::dim ? + std::cout << "loop" << std::endl; algebra::mat<P::dim,P::dim,float> Mk; for (unsigned i = 0; i < C.npoints(); ++i) { algebra::vec<P::dim,float> Ci = C[i]; - algebra::vec<P::dim,float> Xki = Xki; + algebra::vec<P::dim,float> Xki = Xk[i]; Mk += make::mat(Ci - mu_C) * trans(make::mat(Xki - mu_Xk)); } Mk /= C.npoints(); + std::cout << "loop end" << std::endl; const algebra::mat<P::dim,P::dim,float> Ak = Mk - trans(Mk); const float v[3] = {Ak(1,2), Ak(2,0), Ak(0,1)}; const algebra::mat<3,1,float> D = make::mat<3,1,3,float>(v); // FIXME why <...> + algebra::mat<4,4,float> Qk; Qk(0,0) = tr(Mk); put(trans(D), 0,1, Qk); Index: sandbox/jardonnet/registration/chamfer.hh --- sandbox/jardonnet/registration/chamfer.hh (revision 0) +++ sandbox/jardonnet/registration/chamfer.hh (revision 0) @@ -0,0 +1,189 @@ +// Copyright (C) 2007 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. + +#ifndef MLN_DT_CHAMFER_HH +# define MLN_DT_CHAMFER_HH + +# include <mln/core/concept/image.hh> +# include <mln/make/w_window.hh> + +namespace mln +{ + + namespace dt + { + + /*! Distance tranform by chamfer application. + * + * \param[in] input_ The input image. + * \param[in] chamfer The chamfer window to use for distance calcul. + * \return A pair (distance map, nearest point map). + * + * \pre \p img has to be initialized. + */ + template<typename I, typename T> + std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + chamfer(const Image& input_, + w_window<mln_dpoint(I), T> chamfer); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + /*! Computes a pass of the chamfer DT algorithm. + * + * \param[in] p Iterator on the input image to use. + * \param[in] chamfer The chamfer window to use for distance calcul. + * \param[in] input The input image. + * \param[out] outputDistance The distance map updated. + * \param[out] outputnearest The nearest points map updated. + */ + template<typename Q, typename I, typename T> + inline + void + chamfer_pass(const w_window<mln_dpoint(I), T> chamfer, + const I& input, + mln_ch_value(I, T)& outputDistance, + mln_ch_value(I, mln_point(I))& outputNearest) + { + typedef w_window<mln_dpoint(I), T> W; + + Q p(input.domain()); + mln_qiter(W) q(chamfer, p); + for_all(p) + { + std::pair<T, mln_point(I)> min(mln_max(T), p); + + for_all(q) + if (input.has(q) && outputDistance(q) != mln_max(T)) + { + T v = outputDistance(q) + q.w(); + + if (v < min.first) + { + min.first = v; + min.second = outputNearest(q); + } + } + + if (min.first < outputDistance(p)) + { + outputDistance(p) = min.first; + outputNearest(p) = min.second; + } + } + } + + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename T> + inline + std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + chamfer(const Image& input_, + w_window<mln_dpoint(I), T> chamfer) + { + typedef w_window<mln_dpoint(I), T> W; + + const I& input = exact(input_); + mln_precondition(input.has_data()); + + mln_ch_value(I, T) outputDistance; + initialize(outputDistance, input); + + mln_ch_value(I, mln_point(I)) outputNearest; + initialize(outputNearest, input); + + // Initialization. + { + mln_fwd_piter(I) p(input.domain()); + for_all(p) + { + outputDistance(p) = input(p) ? literal::zero : mln_max(T); + outputNearest(p) = p; + } + } + + // First pass. + impl::chamfer_pass<mln_fwd_piter(I)> + (chamfer, input, outputDistance, outputNearest); + + chamfer.sym(); + + // Second pass. + impl::chamfer_pass<mln_bkd_piter(I)> + (chamfer, input, outputDistance, outputNearest); + + return std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + (outputDistance, outputNearest); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_CHAMFER_HH + +// #include <iostream> +// #include <mln/debug/println.hh> +// #include <mln/core/image2d.hh> +// #include <mln/make/win_chamfer.hh> +// #include <mln/level/fill.hh> + +// int main() +// { +// using namespace mln; + +// w_window2d_int chamfer = make::mk_chamfer_3x3_int<3, 4>(); + +// { +// image2d<bool> ima(5,5); +// bool vals[] = { 1, 1, 1, 0, 0, +// 0, 0, 1, 0, 0, +// 0, 0, 1, 0, 0, +// 0, 0, 0, 0, 0, +// 0, 0, 0, 0, 0 }; + +// level::fill(ima, vals); +// debug::println(ima); + +// std::pair<image2d<int>, image2d<mln_point_(image2d<bool>)> > +// out = dt::chamfer(ima, chamfer); + +// std::cerr << "Distance:" << std::endl; +// debug::println(out.first); +// std::cerr << "PPP:" << std::endl; +// debug::println(out.second); +// } +// } Index: sandbox/jardonnet/registration/cloud.hh --- sandbox/jardonnet/registration/cloud.hh (revision 1809) +++ sandbox/jardonnet/registration/cloud.hh (working copy) @@ -32,9 +32,12 @@ // FIXME : move //exist for P? template <typename P> - float sqr_norm(const P& v) + mln_coord(P) sqr_norm(const P& v) { - return v[1] * v[1] + v[2] * v[2] + v[3] * v[3]; + mln_coord(P) tmp = 0; + for (unsigned i = 0; i < P::dim; i++) + tmp += v[i] * v[i]; + return tmp; } template <typename P> Index: sandbox/jardonnet/registration/icp.hh --- sandbox/jardonnet/registration/icp.hh (revision 1809) +++ sandbox/jardonnet/registration/icp.hh (working copy) @@ -35,14 +35,12 @@ # include <mln/algebra/quat.hh> # include <mln/algebra/vec.hh> - - -//typedef mln::algebra::vec<3, float> vec3f; -//typedef mln::p_array< vec3f > vecs_t; +# include <mln/core/w_window.hh> #include "cloud.hh" #include "quat7.hh" #include "projection.hh" +# include "chamfer.hh" namespace mln { @@ -56,20 +54,23 @@ */ template <typename I, typename J> inline - void + I icp(const Image& cloud, - const Image<J>& surface); + const Image<J>& surface, + I& r); # ifndef MLN_INCLUDE_ONLY namespace impl { - template <typename P> + template <typename P, typename T1, typename T2> inline void icp_(const p_array& C, - const p_array& X) + const p_array& X, + std::pair<T1,T2>&, + p_array& Ck) { trace::entering("registration::impl::icp_"); @@ -77,9 +78,12 @@ quat7<P::dim> old_qk, qk; float err, err_bis; - p_array Ck, Xk; - Ck.reserve(C.npoints()); - Xk.reserve(Ck.npoints()); + assert(Ck.npoints() == C.npoints()); + p_array Xk(C); //FIXME:is it correct? + /// Ck.reserve(C.npoints()); + //Xk.reserve(C.npoints()); + //assert(C.npoints() != 0); + algebra::vec<P::dim,float> mu_C = center(C), mu_Xk; const float epsilon = 1e-3; @@ -89,15 +93,19 @@ Ck = C; do { + std::cout << "step2" << std::endl; //step 2 FIXME : etienne projection::de_base(Ck, X, Xk, err_bis); + std::cout << "step2.1 center" << std::endl; mu_Xk = center(Xk); + std::cout << "step3" << std::endl; // step 3 old_qk = qk; qk = match(C, mu_C, Xk, mu_Xk); + std::cout << "step4" << std::endl; // step 4 qk.apply_on(C, Ck); // Ck+1 = qk(C) @@ -105,6 +113,7 @@ err = rms(Ck, Xk); ++k; + std::cout << err << std::endl; } while (k < 3 || (qk - old_qk).sqr_norm() > epsilon); trace::exiting("registration::impl::icp_"); @@ -113,20 +122,97 @@ } // end of namespace mln::registration::impl - // this version could convert image cloud in a vector of point? + //FIXME: move? + namespace convert + { + template <typename T> + const image3d<T>& + to_image_3d(const image3d<T>& img) + { + return img; + } + + template <typename T> + image3d<T>& + to_image_3d(image3d<T>& img) + { + return img; + } + + template <typename T> + image3d<T> + to_image_3d(const image2d<T>& img) + { + point3d pmin(img.domain().pmin()[0], img.domain().pmin()[1], -10); + point3d pmax(img.domain().pmax()[0], img.domain().pmax()[1], 10); + image3d<T> img3d(box3d(pmin,pmax)); + + mln_piter(image3d<T>) p(img3d.domain()); + for_all(p) + { + if (p[2] == 0) + img3d(p) = exact(img)(point2d(p[0],p[1])); + } + return img3d; + } + } + + + //Only for 2d and 3d image template <typename I, typename J> inline - void - icp(const Image& cloud, - const Image<J>& surface) + I + icp(Image& cloud_, + const Image<J>& surface_, + I& r) { trace::entering("registration::icp"); - mln_precondition(exact(cloud).has_data()); - mln_precondition(exact(surface).has_data()); + mln_precondition(exact(cloud_).has_data()); + mln_precondition(exact(surface_).has_data()); - p_array<mln_point(I)> a,b; // FIXME : to built. + std::cout << "convert to image3d" << std::endl; + //convert to image: time consuming + typedef image3d<mln_value(I)> I3d; + I3d cloud = convert::to_image_3d(exact(cloud_)); + const I3d surface = convert::to_image_3d(exact(surface_)); - impl::icp_(a, b); + + std::cout << "chamfer" << std::endl; + /* + //FIXME: not a chamfer. etienne? + //create a pair (distance map, closest point) + w_window<mln_dpoint(I3d), float> chamfer; + */ + std::pair<mln_ch_value(I3d,float), mln_ch_value(I3d,mln_point(I3d)) > maps; + /* + dt::chamfer(surface, chamfer); + */ + + std::cout << "Build p_array" << std::endl; + //build p_arrays. + p_array<mln_point(I3d)> c,x; + + mln_piter(I3d) p1(cloud.domain()); + for_all(p1) + if (exact(cloud)(p1)) + c.append(p1); + + mln_piter(I3d) p2(surface.domain()); + for_all(p2) + if (exact(surface)(p2)) + x.append(p2); + + std::cout << "Start ICP" << std::endl; + + p_array<mln_point(I3d)> res(c); + impl::icp_(c, x, maps, res); + + //to 2d + for (unsigned e; e < res.npoints(); e++) + { + point2d p(res[e][0], res[e][1]); + r(p) = true; + } trace::exiting("registration::icp"); } Index: sandbox/jardonnet/registration/projection.hh --- sandbox/jardonnet/registration/projection.hh (revision 1809) +++ sandbox/jardonnet/registration/projection.hh (working copy) @@ -18,7 +18,7 @@ p_array& Xk, float& err) { - assert(Ck.npoints() == Xk.npoints()); + // assert(Ck.npoints() == Xk.npoints()); err = 0.f; @@ -37,6 +37,7 @@ best_x = Xj; } } + if (i < Xk.npoints()) // FIXME:double hack Xk.hook_()[i] = algebra::to_point(best_x); err += best_d; } Index: sandbox/jardonnet/registration/quat/rotation.hh --- sandbox/jardonnet/registration/quat/rotation.hh (revision 1809) +++ sandbox/jardonnet/registration/quat/rotation.hh (working copy) @@ -35,9 +35,14 @@ assert(q.is_unit()); algebra::vec<n,float> tmp = make::vec(rand(), rand(), rand()), - p = tmp / norm::l2(tmp), + p; + float nl2= norm::l2(tmp); + if(nl2 != 0) + p = tmp / nl2; + algebra::vec<n,float> p_rot_1 = rotate(q, p), p_rot_2 = mat * p; + return about_equal(norm::l2(p_rot_1 - p_rot_2), 0.f); } Index: sandbox/folio/naive.cc --- sandbox/folio/naive.cc (revision 1809) +++ sandbox/folio/naive.cc (working copy) @@ -54,8 +54,9 @@ * * \fixme Use instead of R the result type of F::operator(). */ - template <typename I, typename F, typename R> - mln_ch_value(I, R) + template <typename I, typename F> + inline + mln_ch_value(I, typename F::ret) naive(const Image& input_, F& fun_); @@ -63,15 +64,15 @@ // Facade. - template <typename I, typename F, typename R> + template <typename I, typename F> inline - mln_ch_value(I, R) + mln_ch_value(I, typename F::ret) naive(const Image& input_, F& fun_) { const I& input = exact(input_); mln_precondition(input.has_data()); - mln_ch_value(I, R) output; + mln_ch_value(I, typename F::ret) output; initialize(input.domain()); mln_piter(I) p(input.domain()); @@ -82,7 +83,7 @@ else { // p is in the background so the distance has to be computed. - accu::min_<R> min; + accu::min_<typename F::ret> min; min.init(); mln_piter(I) q(input.domain()); @@ -117,6 +118,7 @@ struct l2norm { + typedef float ret; template <typename C, typename D> D operator()(C a, C b)

1 0

1808: Enable tests/core/graph_elt_neighborhood.
by Roland Levillain 26 Mar '08

26 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Enable tests/core/graph_elt_neighborhood. * tests/core/Makefile.am (check_PROGRAMS): Add graph_elt_neighborhood. (graph_elt_neighborhood_SOURCES): New. Makefile.am | 2 ++ 1 file changed, 2 insertions(+) Index: tests/core/Makefile.am --- tests/core/Makefile.am (revision 1808) +++ tests/core/Makefile.am (working copy) @@ -8,6 +8,7 @@ exact \ h_vec \ initialize \ + graph_elt_neighborhood \ graph_elt_window \ graph_image \ line_graph_elt_window \ @@ -33,6 +34,7 @@ exact_SOURCES = exact.cc h_vec_SOURCES = h_vec.cc initialize_SOURCES = initialize.cc +graph_elt_neighborhood_SOURCES = graph_elt_neighborhood.cc graph_elt_window_SOURCES = graph_elt_window.cc graph_image_SOURCES = graph_image.cc line_graph_elt_window_SOURCES = line_graph_elt_window.cc

1 0

1807: Have piters on graph neighborhoods actually use the neighborhood.
by Roland Levillain 26 Mar '08

26 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have piters on graph neighborhoods actually use the neighborhood. * mln/core/graph_neighborhood_piter.hh (mln::graph_neighborhood_fwd_piter<P, W>) (mln::graph_neighborhood_bkd_piter<P, W>): Have these class templates take a neighborhood type as second, additional parameter. (mln::graph_neighborhood_fwd_piter<P, W>::nbh_) (mln::graph_neighborhood_bkd_piter<P, W>::nbh_): New attributes. (mln::graph_neighborhood_fwd_piter<P, W>::graph_neighborhood_fwd_piter) (mln::graph_neighborhood_bkd_piter<P, W>::graph_neighborhood_bkd_piter): Adjust ctors. (mln::graph_neighborhood_fwd_piter<P, W>::first_) (mln::graph_neighborhood_fwd_piter<P, W>::step_) (mln::graph_neighborhood_bkd_piter<P, W>::first_) (mln::graph_neighborhood_bkd_piter<P, W>::step_): New methods. (mln::graph_neighborhood_fwd_piter<P, W>::start) (mln::graph_neighborhood_fwd_piter<P, W>::next_) (mln::graph_neighborhood_bkd_piter<P, W>::start) (mln::graph_neighborhood_bkd_piter<P, W>::next_): Delegate the body of the routine to the neighborhood. * mln/core/graph_elt_neighborhood.hh (mln::graph_elt_neighborhood::fwd_qiter) (mln::graph_elt_neighborhood::bkd_qiter): Adjust typedefs. (mln::graph_elt_neighborhood::psite): New typedef. (mln::graph_elt_neighborhood::start) (mln::graph_elt_neighborhood::next_): New methods. * tests/core/graph_elt_neighborhood.cc: New test. mln/core/graph_elt_neighborhood.hh | 70 +++++++-- mln/core/graph_neighborhood_piter.hh | 250 +++++++++++++++++++---------------- tests/core/graph_elt_neighborhood.cc | 22 +-- 3 files changed, 205 insertions(+), 137 deletions(-) Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1807) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -57,16 +57,15 @@ template <typename P> class graph_psite; - /*----------------------------------. - | graph_neighborhood_fwd_piter. | - `----------------------------------*/ + /*-------------------------------------. + | graph_neighborhood_fwd_piter<P, N>. | + `-------------------------------------*/ - /// \brief Forward iterator on graph neighborhood. - template <typename P> + template <typename P, typename N> class graph_neighborhood_fwd_piter : - public Point_Iterator< graph_neighborhood_fwd_piter > // or Iterator<...>? + public Point_Iterator< graph_neighborhood_fwd_piter<P, N> > { - typedef graph_neighborhood_fwd_piter self_; + typedef graph_neighborhood_fwd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -83,7 +82,7 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> + template <typename Pref> graph_neighborhood_fwd_piter(const N& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -115,11 +114,23 @@ /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; + /// Internals, used by the neighborhood. + /// \{ + public: + /// Set the iterator to the first site of the graph. + void first_(); + /// Advance the position of the iterator by one step. + void step_(); + + /// An internal iterator on the set of nodes of the underlying graph. + util::node_id id_; + /// \} + private: + /// The neighborhood. + const N& nbh_; /// The ``central'' psite of the neighborhood. const psite& p_ref_; - /// An internal iterator on the set of nodes of the underlying graph. - util::node_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -127,16 +138,15 @@ }; - /*----------------------------------. - | graph_neighborhood_bkd_piter. | - `----------------------------------*/ + /*-------------------------------------. + | graph_neighborhood_bkd_piter<P, N>. | + `-------------------------------------*/ - /// \brief Backward iterator on graph neighborhood. - template <typename P> + template <typename P, typename N> class graph_neighborhood_bkd_piter : - public Point_Iterator< graph_neighborhood_bkd_piter > // or Iterator<...>? + public Point_Iterator< graph_neighborhood_bkd_piter<P, N> > { - typedef graph_neighborhood_bkd_piter self_; + typedef graph_neighborhood_bkd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -153,7 +163,7 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> + template <typename Pref> graph_neighborhood_bkd_piter(const N& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -185,11 +195,23 @@ /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; + /// Internals, used by the neighborhood. + /// \{ + public: + /// Set the iterator to the first site of the graph. + void first_(); + /// Advance the position of the iterator by one step. + void step_(); + + /// An internal iterator on the set of nodes of the underlying graph. + util::node_id id_; + /// \} + private: + /// The neighborhood. + const N& nbh_; /// The ``central'' psite of the neighborhood. const psite& p_ref_; - /// An internal iterator on the set of nodes of the underlying graph. - util::node_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -200,17 +222,17 @@ # ifndef MLN_INCLUDE_ONLY - /*----------------------------------. - | graph_neighborhood_fwd_piter. | - `----------------------------------*/ - - // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + /*-------------------------------------. + | graph_neighborhood_fwd_piter<P, N>. | + `-------------------------------------*/ + + template <typename P, typename N> + template <typename Pref> inline - graph_neighborhood_fwd_piter::graph_neighborhood_fwd_piter(const N& /* nbh */, + graph_neighborhood_fwd_piter<P, N>::graph_neighborhood_fwd_piter(const N& nbh, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : nbh_(exact(nbh)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_(), p_() @@ -219,10 +241,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - graph_neighborhood_fwd_piter::is_valid() const + graph_neighborhood_fwd_piter<P, N>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -230,60 +252,63 @@ return p_ref_.is_valid() && id_ < p_ref_.pg().gr_->nnodes(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter::invalidate() + graph_neighborhood_fwd_piter<P, N>::invalidate() { - id_ = -1 + id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter::start() + graph_neighborhood_fwd_piter<P, N>::start() { - id_ = 0; - if (!adjacent_or_equal_to_p_ref_()) - next_(); - /* FIXME: This is redundant with the end of next_(), but we might - change the implementation of start_() when we'll fix it later, - and no longer use next_(). */ + nbh_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter::next_() + graph_neighborhood_fwd_piter<P, N>::next_() { - /* FIXME: This is inefficient. The graph structure should be able - to produce the set of adjacent nodes fast. Boost Graphs - probably provides adequates structures to fetch these - neighbors in constant time. */ - /* FIXME: Moreover, the behavior of next shall depend on the - neighborhood, which is not the case now! (Currently, next_() behaves - as nbh was always an elementary neighborhood.) */ - do - ++id_; - while (is_valid() && !adjacent_or_equal_to_p_ref_()); + nbh_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> + inline + void + graph_neighborhood_fwd_piter<P, N>::first_() + { + id_ = 0; + } + + template <typename P, typename N> + inline + void + graph_neighborhood_fwd_piter<P, N>::step_() + { + ++id_; + } + + + template <typename P, typename N> inline bool - graph_neighborhood_fwd_piter::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter::update_() + graph_neighborhood_fwd_piter<P, N>::update_() { // Update psite_. psite_ = graph_psite(p_ref_.pg(), id_); @@ -291,51 +316,51 @@ p_ = p_ref_.pg().gr_->node_data(id_); } - template <typename P> + template <typename P, typename N> inline const P& - graph_neighborhood_fwd_piter::to_point() const + graph_neighborhood_fwd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const graph_psite& - graph_neighborhood_fwd_piter::to_psite() const + graph_neighborhood_fwd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - graph_neighborhood_fwd_piter::operator graph_psite() const + graph_neighborhood_fwd_piter<P, N>::operator graph_psite() const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - graph_neighborhood_fwd_piter::operator[](unsigned i) const + graph_neighborhood_fwd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - /*----------------------------------. - | graph_neighborhood_bkd_piter. | - `----------------------------------*/ - - // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + /*-------------------------------------. + | graph_neighborhood_bkd_piter<P, N>. | + `-------------------------------------*/ + + template <typename P, typename N> + template <typename Pref> inline - graph_neighborhood_bkd_piter::graph_neighborhood_bkd_piter(const N& /* nbh */, + graph_neighborhood_bkd_piter<P, N>::graph_neighborhood_bkd_piter(const N& nbh, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : nbh_(nbh), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_(), p_() @@ -344,10 +369,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - graph_neighborhood_bkd_piter::is_valid() const + graph_neighborhood_bkd_piter<P, N>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -355,60 +380,63 @@ return p_ref_.is_valid() && id_ < p_ref_.pg().gr_->nnodes(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter::invalidate() + graph_neighborhood_bkd_piter<P, N>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter::start() + graph_neighborhood_bkd_piter<P, N>::start() { - id_ = p_ref_.pg().gr_->nnodes() - 1; - if (!adjacent_or_equal_to_p_ref_()) - next_(); - /* FIXME: This is redundant with the end of next_(), but we might - change the implementation of start_() when we'll fix it later, - and no longer use next_(). */ + nbh_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter::next_() + graph_neighborhood_bkd_piter<P, N>::next_() { - /* FIXME: This is inefficient. The graph structure should be able - to produce the set of adjacent nodes fast. Boost Graphs - probably provides adequates structures to fetch these - neighbors in constant time. */ - /* FIXME: Moreover, the behavior of next shall depend on the - neighborhood, which is not the case now! (Currently, next_() behaves - as nbh was always an elementary neighborhood.) */ - do - --id_; - while (is_valid() && !adjacent_or_equal_to_p_ref_()); + nbh_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> + inline + void + graph_neighborhood_bkd_piter<P, N>::first_() + { + id_ = p_ref_.pg().gr_->nnodes() - 1; + } + + template <typename P, typename N> + inline + void + graph_neighborhood_bkd_piter<P, N>::step_() + { + --id_; + } + + + template <typename P, typename N> inline bool - graph_neighborhood_bkd_piter::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter::update_() + graph_neighborhood_bkd_piter<P, N>::update_() { // Update psite_. psite_ = graph_psite(p_ref_.pg(), id_); @@ -416,34 +444,34 @@ p_ = p_ref_.pg().gr_->node_data(id_); } - template <typename P> + template <typename P, typename N> inline const P& - graph_neighborhood_bkd_piter::to_point() const + graph_neighborhood_bkd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const graph_psite& - graph_neighborhood_bkd_piter::to_psite() const + graph_neighborhood_bkd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - graph_neighborhood_bkd_piter::operator graph_psite() const + graph_neighborhood_bkd_piter<P, N>::operator graph_psite() const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - graph_neighborhood_bkd_piter::operator[](unsigned i) const + graph_neighborhood_bkd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; Index: mln/core/graph_elt_neighborhood.hh --- mln/core/graph_elt_neighborhood.hh (revision 1807) +++ mln/core/graph_elt_neighborhood.hh (working copy) @@ -50,8 +50,8 @@ namespace mln { // Fwd decls. - template <typename P> class graph_neighborhood_fwd_piter; - template <typename P> class graph_neighborhood_bkd_piter; + template <typename P, typename W> class graph_neighborhood_fwd_piter; + template <typename P, typename W> class graph_neighborhood_bkd_piter; /*! \brief Elementary neighborhood on graph class. @@ -67,29 +67,69 @@ public: /// Associated types. /// \{ - /// The type of point stored into the neighborhood. - // FIXME: Is this right, if we consider that this neighborhood stores - // psites, not points? + /// The type of point corresponding to the neighborhood. typedef P point; + /// The type of psite corresponding to the neighborhood. + typedef graph_psite psite; // FIXME: This is a dummy value. typedef void dpoint; - /*! \brief Point_Iterator type to browse the points of a generic - * neighborhood w.r.t. the ordering of delta-points. - */ - typedef graph_neighborhood_fwd_piter fwd_qiter; + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the ordering of vertices. + typedef graph_neighborhood_fwd_piter<P, self_> fwd_niter; + + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the ordering of vertices. + typedef graph_neighborhood_bkd_piter<P, self_> bkd_niter; - /*! \brief Point_Iterator type to browse the points of a generic - * neighborhood w.r.t. the reverse ordering of delta-points. - */ - typedef graph_neighborhood_bkd_piter bkd_qiter; + /// The default niter type. + typedef fwd_niter niter; + /// \} - /// The default qiter type. - typedef fwd_qiter qiter; + /// Services for iterators. + /// \{ + /// Move \a piter to the beginning of the iteration on this neighborhood. + template <typename Piter> + void start(Point_Iterator<Piter>& piter) const; + /// Move \a piter to the next site on this neighborhood. + template <typename Piter> + void next_(Point_Iterator<Piter>& piter) const; /// \} }; +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + template <typename Piter> + inline + void + graph_elt_neighborhood::start(Point_Iterator<Piter>& piter_) const + { + Piter& piter = exact(piter_); + piter.first_(); + if (!piter.adjacent_or_equal_to_p_ref_()) + next_(piter); + } + + template <typename P> + template <typename Piter> + inline + void + graph_elt_neighborhood::next_(Point_Iterator<Piter>& piter_) const + { + Piter& piter = exact(piter_); + /* FIXME: This is inefficient. The graph structure should be able + to produce the set of adjacent nodes fast. Boost Graphs + probably provides adequates structures to fetch these + neighbors in constant time. */ + do + piter.step_(); + while (piter.is_valid() && !piter.adjacent_or_equal_to_p_ref_()); + } + +# endif // ! MLN_INCLUDE_ONLY + } // end of namespace mln Index: tests/core/graph_elt_neighborhood.cc --- tests/core/graph_elt_neighborhood.cc (revision 1806) +++ tests/core/graph_elt_neighborhood.cc (working copy) @@ -25,9 +25,9 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/graph_elt_window.cc +/*! \file tests/core/graph_elt_neighborhood.cc * - * \brief Tests on mln::graph_elt_window. + * \brief Tests on mln::graph_elt_neighborhood. */ #include <iostream> @@ -35,7 +35,7 @@ #include <vector> #include <mln/core/point2d.hh> -#include <mln/core/graph_elt_window.hh> +#include <mln/core/graph_elt_neighborhood.hh> #include <mln/debug/iota.hh> #include <mln/debug/println.hh> @@ -84,24 +84,24 @@ g.add_edge(3, 4); g.add_edge(4, 2); - /*------------------. - | Graph and window. | - `------------------*/ + /*-------------------------. + | Graph and neighborhood. | + `-------------------------*/ // Graph psite set. p_graph<p_t> pg(g); // Graph point site. graph_psite<p_t> p(pg, 1); - // ``Sliding'' window of a psite of PG. - typedef graph_elt_window<p_t> win_t; - win_t win; + // ``Sliding'' neighborhood of a psite of PG. + typedef graph_elt_neighborhood<p_t> nbh_t; + nbh_t nbh; - mln_fwd_qiter_(win_t) fq(win, p); + mln_fwd_niter_(nbh_t) fq(nbh, p); for_all(fq) std::cout << fq << " "; std::cout << std::endl; - mln_bkd_qiter_(win_t) bq(win, p); + mln_bkd_niter_(nbh_t) bq(nbh, p); for_all(bq) std::cout << bq << " "; std::cout << std::endl;

1 0

1807: Fix a bug in graph_neighborhood_bkd_piter.
by Roland Levillain 26 Mar '08

26 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Fix a bug in graph_neighborhood_bkd_piter. * mln/core/graph_neighborhood_piter.hh (mln::graph_neighborhood_bkd_piter::start): Typo. graph_neighborhood_piter.hh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1806) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -368,7 +368,7 @@ void graph_neighborhood_bkd_piter::start() { - id_ = p_ref_.plg().gr_->nnodes() - 1; + id_ = p_ref_.pg().gr_->nnodes() - 1; if (!adjacent_or_equal_to_p_ref_()) next_(); /* FIXME: This is redundant with the end of next_(), but we might

1 0

scool r56: Work on concepts
by Maxime van Noppen 26 Mar '08

26 Mar '08

URL: https://svn.lrde.epita.fr/svn/scool/trunk ChangeLog: 2008-03-26 Maxime van Noppen <yabo(a)lrde.epita.fr> Work on concepts * src/pp-cxx/CxxFun.str: Pretty-print C++ constructors correctly. * src/pp-cxx/CxxDecl.str: Fix bug in access blocks pretty-print. * src/pp-cxx/CxxType.str: Remove useless comment. * src/scoolt/Concept.str: New. * src/scoolt/Decl.str: Handle Concept constructor. pp-cxx/CxxDecl.str | 4 ++-- pp-cxx/CxxFun.str | 11 +++++++++++ pp-cxx/CxxType.str | 2 -- scoolt/Concept.str | 34 ++++++++++++++++++++++++++++++++++ scoolt/Decl.str | 19 +++++++++++++++++-- 5 files changed, 64 insertions(+), 6 deletions(-) Index: trunk/src/pp-cxx/CxxFun.str =================================================================== --- trunk/src/pp-cxx/CxxFun.str (revision 55) +++ trunk/src/pp-cxx/CxxFun.str (revision 56) @@ -16,6 +16,17 @@ ] CxxTopLevelToAbox: + CxxFun(params, None(), idf, args) -> + V vs=0 + [ + ~<CxxParamsToAbox> params + H hs=0 + [ + H hs=1 [ ~<CxxIdToAbox> idf ] "(" H hs=1 [ ~*<CxxListToAbox(CxxArgDefToAbox|",")> args ] ")" ";" + ] + ] + + CxxTopLevelToAbox: CxxFun(params, t, idf, args, body) -> V vs=0 [ Index: trunk/src/pp-cxx/CxxDecl.str =================================================================== --- trunk/src/pp-cxx/CxxDecl.str (revision 55) +++ trunk/src/pp-cxx/CxxDecl.str (revision 56) @@ -49,7 +49,7 @@ CxxPublic(b) -> V is=2 [ "public:" V [ ~*<map(CxxTopLevelToAbox)> b ] ] CxxBodyToAbox: - CxxProtected(b) -> V is=2 [ "private:" V [ ~*<map(CxxTopLevelToAbox)> b ] ] + CxxProtected(b) -> V is=2 [ "protected:" V [ ~*<map(CxxTopLevelToAbox)> b ] ] CxxBodyToAbox: CxxPrivate(b) -> V is=2 [ "private:" V [ ~*<map(CxxTopLevelToAbox)> b ] ] @@ -62,7 +62,7 @@ H hs=1 [ "class" ~<CxxIdToAbox> idf ] ~<CxxParentsToAbox> parents ] - V vs=0 is=2 [ "{" V vs=1 [ ~*<map (CxxBodyToAbox)> body ] ] + V vs=0 is=2 [ "{" V vs=0 [ ~*<map (CxxBodyToAbox <+ CxxTopLevelToAbox)> body ] ] H hs=0 [ "}" ";" ] ] Index: trunk/src/pp-cxx/CxxType.str =================================================================== --- trunk/src/pp-cxx/CxxType.str (revision 55) +++ trunk/src/pp-cxx/CxxType.str (revision 56) @@ -19,7 +19,5 @@ CxxTypeToAbox: Typename -> S("typename") - /* These functions are actually macros */ - CxxTypeToAbox: CxxFunCall(idf, args) -> H hs=0 [ ~<CxxIdToAbox>idf "(" H hs=1 [ ~*<CxxListToAbox(CxxTypeToAbox <+ CxxExpToAbox|",")>args ] ")"] Index: trunk/src/scoolt/Concept.str =================================================================== --- trunk/src/scoolt/Concept.str (revision 0) +++ trunk/src/scoolt/Concept.str (revision 56) @@ -0,0 +1,34 @@ +module Concept + +imports libstratego-lib Cxx AsFix Scool + +rules + + TypeToStr: + Var(t) -> "typedef" + where <eq> (t, "type") + + TypeToStr: + FunType(_, Var(t)) -> t + + ArgsToStr: + FunType([], _) -> "" + + ArgsToStr: + FunType([ e | []], _) -> "" + + ArgsToStr: + FunType([e | l], _) -> <concat-strings> [ e, ", ", <ArgsToStr> l ] + + ConceptBodyToCxx: + ConstDec([], idf, None(), t) -> CxxComment(<concat-strings>[ <TypeToStr> t, " ", idf, ";" ]) + + ConceptBodyToCxx: + ConstDec(["decl"], idf, None(), t) -> + CxxComment(<concat-strings>[ <TypeToStr> t, " ", idf, "(", <ArgsToStr> t, ")", ";"]) + + ConceptAddCxxConstructor: + idf -> CxxProtected([CxxFun([], None(), idf, [])]) + +// ConceptAddCxxConstructor(| idf): +// _ -> CxxProtected([CxxFun([(Typename, "E")], "", <concat-strings>[ idf, "<E>::", idf], [], [])]) Index: trunk/src/scoolt/Decl.str =================================================================== --- trunk/src/scoolt/Decl.str (revision 55) +++ trunk/src/scoolt/Decl.str (revision 56) @@ -1,6 +1,6 @@ module Decl -imports libstratego-lib Cxx Type Exp Stm Tools AsFix Scool Access +imports libstratego-lib Cxx Type Exp Stm Tools AsFix Scool Access Concept rules @@ -158,7 +158,7 @@ * Grammar: idf ":" "class" "<" parent ";" */ DeclToCxx: - ConstDec([], idf, cs, Class(parent)) -> CxxClassDecl([], idf, [("public", <TypeToCxx> parent)]) + ConstDec([], idf, cs, Class(Var(parent))) -> CxxClassDecl([], idf, [("public", CxxType(parent))]) where <conc-strings> (idf, "_") => nidf /* @@ -189,6 +189,21 @@ DeclToCxx: BiFunDec(l, idf, params, args, t, ExpStm(body)) -> CxxFun(<map (ParamToCxx)> params, <TypeToCxx> t, idf, <map (ArgDefToCxx)> args, [<StmToCxx> Return(body)]) + + /* + * Handle concept declarations + * Grammar : idf ":" "concept" "{" body "}" + */ + DeclToCxx: + Concept(idf, body) -> CxxClassDecl([(Typename, "E")], idf, [], + <conc> + ( + [ CxxComment("To be provided by classes that models this concept\n") ], + <map (ConceptBodyToCxx)> body, + [ <ConceptAddCxxConstructor> idf ] + )) + + ParamToCxx: (idf, Var(t), wclause) -> <if <eq> (t, "type") then -- \__/ \__/ (00) Maxime `yabo` van Noppen (00) ___) \ Epita 2009 / (___ (_____/ Président de Prologin \_____)

1 0

scool r55: Update some tests
by Maxime van Noppen 26 Mar '08

26 Mar '08

URL: https://svn.lrde.epita.fr/svn/scool/trunk ChangeLog: 2008-03-26 Maxime van Noppen <yabo(a)lrde.epita.fr> Update some tests * input/sample_1.scl, * input/wiki1.scl, * parser/sample_1.ref, * parser/wiki1.ref, * transformer/sample_1.ref, * transformer/wiki1.ref: Replace int16 by int. input/sample_1.scl | 4 ++-- input/wiki1.scl | 4 ++-- parser/sample_1.ref | 2 +- parser/wiki1.ref | 2 +- transformer/sample_1.ref | 4 ++-- transformer/wiki1.ref | 4 ++-- 6 files changed, 10 insertions(+), 10 deletions(-) Index: trunk/tests/input/sample_1.scl =================================================================== --- trunk/tests/input/sample_1.scl (revision 54) +++ trunk/tests/input/sample_1.scl (revision 55) @@ -1,9 +1,9 @@ f : () -> void = { - i : int16 = 3; + i : int = 3; i := 4; - var j : int16 := 3; + var j : int := 3; j := 4; } Index: trunk/tests/input/wiki1.scl =================================================================== --- trunk/tests/input/wiki1.scl (revision 54) +++ trunk/tests/input/wiki1.scl (revision 55) @@ -1,9 +1,9 @@ f : () -> void = { - i : int16 = 3; + i : int = 3; i := 4; - var j : int16 := 3; + var j : int := 3; j := 4; } \ No newline at end of file Index: trunk/tests/transformer/wiki1.ref =================================================================== --- trunk/tests/transformer/wiki1.ref (revision 54) +++ trunk/tests/transformer/wiki1.ref (revision 55) @@ -1,7 +1,7 @@ void f() { - const int16 i = 3; + const int i = 3; i = 4; - int16 j = 3; + int j = 3; j = 4; } Index: trunk/tests/transformer/sample_1.ref =================================================================== --- trunk/tests/transformer/sample_1.ref (revision 54) +++ trunk/tests/transformer/sample_1.ref (revision 55) @@ -1,7 +1,7 @@ void f() { - const int16 i = 3; + const int i = 3; i = 4; - int16 j = 3; + int j = 3; j = 4; } Index: trunk/tests/parser/wiki1.ref =================================================================== --- trunk/tests/parser/wiki1.ref (revision 54) +++ trunk/tests/parser/wiki1.ref (revision 55) @@ -1 +1 @@ -Program([FunDec([],"f",[],Var("void"),[ConstDec([],"i",Var("int16"),Int("3")),ExpStm(Affect(Var("i"),Int("4"))),VarDec([],"j",Var("int16"),Int("3")),ExpStm(Affect(Var("j"),Int("4")))])]) +Program([FunDec([],"f",[],Var("void"),[ConstDec([],"i",Var("int"),Int("3")),ExpStm(Affect(Var("i"),Int("4"))),VarDec([],"j",Var("int"),Int("3")),ExpStm(Affect(Var("j"),Int("4")))])]) Index: trunk/tests/parser/sample_1.ref =================================================================== --- trunk/tests/parser/sample_1.ref (revision 54) +++ trunk/tests/parser/sample_1.ref (revision 55) @@ -1 +1 @@ -Program([FunDec([],"f",[],Var("void"),[ConstDec([],"i",Var("int16"),Int("3")),ExpStm(Affect(Var("i"),Int("4"))),VarDec([],"j",Var("int16"),Int("3")),ExpStm(Affect(Var("j"),Int("4")))])]) +Program([FunDec([],"f",[],Var("void"),[ConstDec([],"i",Var("int"),Int("3")),ExpStm(Affect(Var("i"),Int("4"))),VarDec([],"j",Var("int"),Int("3")),ExpStm(Affect(Var("j"),Int("4")))])]) -- \__/ \__/ (00) Maxime `yabo` van Noppen (00) ___) \ Epita 2009 / (___ (_____/ Président de Prologin \_____)

1 0

1804: Have Meyer's WST depend less on the old code base.
by Roland Levillain 25 Mar '08

25 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have Meyer's WST depend less on the old code base. * mln/morpho/meyer_wst.hh: Use labeling::regional_minima instead of morpho::minima_components. * mln/morpho/extrema_components.hh, * mln/morpho/level_components.hh: Remove. * mln/canvas/labeling.hh: s/point/psite/. canvas/labeling.hh | 35 +++++++++++++++++++++++------------ morpho/meyer_wst.hh | 15 ++++++++------- 2 files changed, 31 insertions(+), 19 deletions(-) Index: mln/morpho/meyer_wst.hh --- mln/morpho/meyer_wst.hh (revision 1803) +++ mln/morpho/meyer_wst.hh (working copy) @@ -43,11 +43,10 @@ # include <mln/trait/ch_value.hh> +// FIXME: See below. # include <mln/util/greater_psite.hh> # include <mln/morpho/includes.hh> -// FIXME: See below. -// # include <mln/labeling/regional_minima.hh> -# include <mln/morpho/extrema_components.hh> +# include <mln/labeling/regional_minima.hh> @@ -120,13 +119,15 @@ limitation. As soon as labeling::regional_minima work, get rid of - mln/morpho/level_components.hh, and - mln/morpho/extrema_components.hh. */ -// mln_ch_value(I, marker) markers = -// labeling::regional_minima (input, nbh, nbasins); mln_ch_value(I, marker) markers = - minima_components(input, convert::to_window(nbh), nbasins); + labeling::regional_minima (input, nbh, nbasins); - // Ordered queue. typedef mln_psite(I) psite; + + // Ordered queue. + /* FIXME: Milena probably already provides an ordered queue + facility via the mln::p_priority_queue class. Try to use it + instead, and get rid of mln/util/greater_psite.hh. */ typedef std::priority_queue< psite, std::vector<psite>, util::greater_psite > ordered_queue_type; Index: mln/canvas/labeling.hh --- mln/canvas/labeling.hh (revision 1803) +++ mln/canvas/labeling.hh (working copy) @@ -59,11 +59,11 @@ typedef typename F::S S; // Local type. - typedef mln_psite(I) point; + typedef mln_psite(I) psite; // Auxiliary data. mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, point) parent; + mln_ch_value(I, psite) parent; // Output. mln_ch_value(I, L) output; @@ -82,17 +82,19 @@ // Auxiliary methods. - void make_set(const point& p); + void make_set(const psite& p); - bool is_root(const point& p) const; + bool is_root(const psite& p) const; - point find_root(const point& x); + psite find_root(const psite& x); - void do_union(const point& n, const point& p); + void do_union(const psite& n, const psite& p); }; + // Fastest version. + template <typename F> struct labeling_fastest { @@ -132,6 +134,10 @@ # ifndef MLN_INCLUDE_ONLY + /*-------------------. + | canvas::labeling. | + `-------------------*/ + template <typename F> labeling<F>::labeling(F& f) : f(f) @@ -204,7 +210,7 @@ template <typename F> void - labeling<F>::make_set(const point& p) + labeling<F>::make_set(const psite& p) { parent(p) = p; f.init_attr(p); @@ -212,14 +218,14 @@ template <typename F> bool - labeling<F>::is_root(const point& p) const + labeling<F>::is_root(const psite& p) const { return parent(p) == p; } template <typename F> - typename labeling<F>::point - labeling<F>::find_root(const point& x) + typename labeling<F>::psite + labeling<F>::find_root(const psite& x) { if (parent(x) == x) return x; @@ -229,9 +235,9 @@ template <typename F> void - labeling<F>::do_union(const point& n, const point& p) + labeling<F>::do_union(const psite& n, const psite& p) { - point r = find_root(n); + psite r = find_root(n); if (r != p) { parent(r) = p; @@ -239,6 +245,11 @@ } } + + /*---------------------------. + | canvas::labeling_fastest. | + `---------------------------*/ + template <typename F> labeling_fastest<F>::labeling_fastest(F& f) : f(f)

1 0