March 2008 - Olena-patches

[Olena] #130: Don not pass neighborhoods as argument to algorithms
by Olena 14 May '09

14 May '09

#130: Don not pass neighborhoods as argument to algorithms ----------------------+----------------------------------------------------- Reporter: levill_r | Owner: Olena Team Type: defect | Status: new Priority: major | Milestone: Olena 1.0ß Component: Milena | Version: 1.0 Keywords: | ----------------------+----------------------------------------------------- Neighborhoods shall be bound to images: they are a property of them. Hence an algorithm (at least a facade) shall not accept an image along with an ''external'' neighborhood. Most of the time, these algorithms are based on windows improperly called neighborhoods. Here is the list of files to revamp, as of revision 1663: * source:trunk/labeling/level.spe.hh * source:trunk/labeling/regional_maxima.hh * source:trunk/labeling/regional_minima.hh * source:trunk/make/voronoi.hh * source:trunk/milena/mln/geom/labeling/blobs.hh * source:trunk/milena/mln/geom/seeds2tiling_roundness.hh * source:trunk/milena/mln/labeling/background.hh * source:trunk/milena/mln/labeling/flat_zones.hh * source:trunk/milena/mln/labeling/foreground.hh * source:trunk/milena/mln/labeling/level.hh * source:trunk/morpho/Rd.hh * source:trunk/morpho/dilation.hh * source:trunk/morpho/opening_area.hh * source:trunk/morpho/opening_attribute.hh -- Ticket URL: <https://trac.lrde.org/olena/ticket/130> Olena <http://olena.lrde.epita.fr> Olena, a generic and efficient C++ image library.

2 11

[Olena] #127: Generalize the definition of the Sobel gradient
by Olena 17 Jun '08

17 Jun '08

#127: Generalize the definition of the Sobel gradient -------------------------+-------------------------------------------------- Reporter: levill_r | Owner: Olena Team Type: enhancement | Status: new Priority: trivial | Milestone: Component: Milena | Version: 1.0 Keywords: | -------------------------+-------------------------------------------------- For the moment (rev. 1656), the Sobel gradient only works on 2-D images. We could generalize its definition to n-D (regular) images. For instance, a 3-D version is mentioned in http://www.aravind.ca/cs788h_Final_Project/gradient_estimators.htm. -- Ticket URL: <https://trac.lrde.org/olena/ticket/127> Olena <http://olena.lrde.epita.fr> Olena, a generic and efficient C++ image library.

1 1

[Olena] #135: Name Confilts between util::node and util::node.
by Olena 08 Jun '08

08 Jun '08

#135: Name Confilts between util::node and util::node. -----------------------+---------------------------------------------------- Reporter: garrigues | Owner: Olena Team Type: defect | Status: new Priority: major | Milestone: Olena 1.0ß Component: Milena | Version: 1.0 Keywords: | -----------------------+---------------------------------------------------- We have two util::node : one for the graph implementation and also one for the tree. see source:/trunk/milena/mln/util/tree.hh and source:/trunk/milena/mln/util/internal/graph_base.hh -- Ticket URL: <https://trac.lrde.org/olena/ticket/135> Olena <http://olena.lrde.epita.fr> Olena, a generic and efficient C++ image processing library.

1 4

[Olena] #137: Write more attribute (connected) filters
by Olena 03 Jun '08

03 Jun '08

#137: Write more attribute (connected) filters ----------------------+----------------------------------------------------- Reporter: levill_r | Owner: Olena Team Type: task | Status: new Priority: major | Milestone: Olena 1.0 Component: Milena | Version: 1.0 Keywords: | ----------------------+----------------------------------------------------- For instance, * a volume opening/closing; * a filter based on the height of a component; * etc. -- Ticket URL: <https://trac.lrde.org/olena/ticket/137> Olena <http://olena.lrde.epita.fr> Olena, a generic and efficient C++ image processing library.

1 1

[Olena] #123: Revamp general graph-based images (aka badly named « mesh images »)
by Olena 09 Apr '08

09 Apr '08

#123: Revamp general graph-based images (aka badly named « mesh images ») ----------------------+----------------------------------------------------- Reporter: levill_r | Owner: levill_r Type: task | Status: new Priority: major | Milestone: Olena 1.0ß Component: Milena | Version: 1.0 Keywords: | ----------------------+----------------------------------------------------- For starters, * Use `graph_based` prefix instead of `mesh`. * Improve the graph structure; possibly provide a BGL-based version of the graph-based image. Then later: * Create a « add_neighborhood » morpher, and adjust window-based morpho algorithms so that they can work on images with neighborhoods. * Rename « mesh elementary window » as « graph elementary neighborhood » (or adjacency? Check formal definitions to choose the right term.). * Revamp this elementary neighborhood too (currently, the graph-based piters ignore them, and assume they always work on elementary neighborhoods). These latest tasks might deserve their own ticket, as their scope is beyond graph-based images. -- Ticket URL: <https://trac.lrde.org/olena/ticket/123> Olena <http://olena.lrde.epita.fr> Olena, a generic and efficient C++ image library.

1 7

1817: Start a doc about the Milena images types and their properties.
by Nicolas Ballas 31 Mar '08

31 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Start a doc about the Milena images types and their properties. * sandbox/ballas/doc: New. * sandbox/ballas/doc/image_tours.txt: New. image_tours.txt | 486 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 486 insertions(+) Index: sandbox/ballas/doc/image_tours.txt --- sandbox/ballas/doc/image_tours.txt (revision 0) +++ sandbox/ballas/doc/image_tours.txt (revision 0) @@ -0,0 +1,486 @@ +-*- outline -*- + +* Introduction + + +* What is a property? + +** Two types of properties + + +*** Declaratif mode: (find an exemple). + + +Here, the properties must be define by the image type programmer. They cannot +be deduce from the image associated type. So we can't find the properties by +introspecting the image type (with introspection). + + + declaration definition ..... I check + ------- ---------- +| | / \ +| Props | ----> | Image Type | +| | \ ___________/ + ------- + + + +*** Automatic mode: (find an exemple). + +Here, we get the image properties from the image associated type +(site, pset...). + + + ----------- + / \ + | Image Type | automatic + and associated -----> Props + type + \ ___________/ + + + +** Semantic + +Properties are a way to classify the images depends or their type. + +*** Static Checking + + Some operators are only define in special cases. Properties provide a way to +check that the operator input type respect the operator requirement. + +*** Specialization of an Algorithm + (ex: dilatation/erosion). +TODO: detail the example. + +*** Implementation inherentence + +Milena image types are property driven. +It is possible to get a special behavior (not describe in the Image Concept) +depends on the property define in the property associated for the image +type. So, it is possible to recover some piece of interface depending on the +image type properties. +For instance an Image2d has the bidimensional, and random value access. + properties. Hence, Image2d automatically provides a row/column access: +V at(Point2d<T>::coord x, Point2d<T>::coord y). + + + + +*** Difference between a property and its values + +*** Hierarchie of property (scalar/integer) + +** Implementation of properties in Milena + +* Algorithm and Properties + +** Specialization + +** Static checking + + +* Image Properties: + +** global Properties: + category: primary, + { domain_morpher, value_morpher, identity_morpher } < morpher + + border: none, + { stored, computed } < some + + neighb: none, + some + + data: stored, + linear < stored + raw < linear, + computed + + io: read, + write, + read_only < read, + write_only < write, + read_write < both read'n write + + speed: slow, + fast, + fastest + + +** Properties related to I::value + kind: color, + gray, + label, + logic < label, + binary < logic, + data + + quant: low, + high + + value: scalar, + vectorial, + structed, + pointer + + +** Properties related to I::pset + access: random, + browsing + + space: one_d, + two_d, + three_d + + size: huge, + regular + + support: irregular, + regular + aligned < regular + + +* Values Properties: + nature: scalar, + { integer, floating } < scalar, + vectorial, + matric, + symbolic, + strutured, + unknow + + kind: color, + grey, + label, + logic < label, + binary < logic, + data + + quant: low, + high + + + +* Image types and their associated properties + +** Primitive Image + +Primitive image are image which are not based on another image type. + +A primitive image type property can be either declared or automatically get +back with the help of associated types. + + +FIXME: find a good notation... + +** Image nD + +Image on regular grid where grides nodes are points. +To gain efficienty, Images nD have a virtual borders. +All these image are templated by T, the image value type. + +*** Image1d<T> + +**** Associated types: + +value = T + +site = point1d +psite = point1d == point_<tick,int> +pset = box1d + +**** Properties: + +--> global properties + +category = primary +border = stored +neighb: none +data = raw +io = read_write +speed = fastest + +--> properties related to values + +// Depend on T FIXME, where the property are defined?? +kind = +quant = +value = + +--> properties related to the pset + +access = random +space = one_d +size = regular +support = aligned + +**** Specific interface: + FIXME.... + + + + + + +*** Image2d<T> + +**** Associated types: + +value = T + +site = point2d +psite = point2d == point_<square,int> +pset = box2d + +**** Properties: + +--> global properties + +category = primary +border = stored +neighb: none +data = raw +io = read_write +speed = fastest + +--> properties related to values + +// Depend on T FIXME, where the property are defined?? +kind = +quant = +value = + +--> properties related to the pset + +access = random +space = two_d +size = regular +support = aligned + +**** Specific interface: + FIXME.... + + + +*** Image3d<T> + +**** Associated types: + +value = T + +site = point3d +psite = point3d == point_<cube,int> +pset = box3d + +**** Properties: + +--> global properties + +category = primary +border = stored +neighb: none +data = raw +io = read_write +speed = fastest + +--> properties related to values + +// Depend on T FIXME, where the property are defined?? +kind = +quant = +value = + +--> properties related to the pset + +access = random +space = three_d +size = regular +support = aligned + +**** Specific interface: + FIXME.... + + + + +** Image based on function + +The images based on function are templated by F and P, where +F is p2v function type and P a psite + +Question: Is there any restriction on F and S ?? +-> S must be include in the definition set of F + +*** pw::image<F, S> + +**** Associated types: + +value = F::result + +site = S::site +psite = S::pset +pset = S + +**** Properties: + +--> global properties + +category = primary +border = none +neighb: none +data = computed // computed => read_only! +io = read_only +speed = fast + +--> properties related to values + +kind =?? +quant =?? +value = fixme + +--> properties related to the pset + +access = browsing // Why the access property is set to browsing? +space = fixme_ +size = regular +support = fixme + +FIXME: see how to fix all the fixme in the pw::image properties. +How to deal with the lvalue?? + +Is there any lvalue for image with computed data? +lvalue just for image with stored//read_only data? + +**** Specific interface: + FIXME.... + + + + +** Run based Encoded image + +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. + + + +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...) +Is there any restriction on P and T? +Can we compress all the image types or only the point wise image type +(cf the on_the_same_line in the encode algorithm). + +How the properties are setted and to which values? + +Depend on the PointWise property ?? + +*** RLE Image + +A RLE image can be defined as the following: +{(p, v)} where p is a run of P and v is a value of type T. + + +**** Associated types: + +value = T + +site = P +psite = runs_psite +pset = p_runs_ + +**** Properties: + +--> global properties + +category = primary +border = none +neighb: none +data = linear +io = read_only +speed = slow + +--> properties related to values + +// Depend on T FIXME, where the property are defined?? +kind = +quant = +value = + +--> properties related to the pset + +access = browsing +space = depend on P //FIXME the property setted in the milena code is wrong. +size = regular // Should we say compressed? +support = depend on P // The property setted in the milena code is wrong + + +*** Compact RLE + +*** Sparse Image + +A RLE image can be defined as the following: +{(p, [v])} where p is a run of P and v is a value of type T, and [v] is an +array of size p.length(). + + +**** Associated types: + +value = T + +site = P +psite = runs_psite +pset = p_runs_ + +**** Properties: + +Same properties than the RLE Image type. + + +*** Value encoded image + + +** Graph Image + +FIXME: See with roland + +**** Connectivity based on a graph. + + +** Morpher (Derived Image) + +Mopher are Image types which transform an Image type into a new type. So, they +rest upon another images types. Most of the mopher properties are +transformation of the input image type properties. + +A morpher image type property can be declared, automatically get back with +the help of the associated type or be a transformation of a property of the +input image type. + +*** Identity morpher + +*** Domain morpher + +*** Value morpher + + +*** Image_if + +??? + + + + +Note: +The different grid (retrieve from point_ class): + - tick, + - square, + - hexa, + - cube

1 0

1793: Add a benchmark on run_image types compression efficiency.
by Nicolas Ballas 31 Mar '08

31 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Add a benchmark on run_image types compression efficiency. * doc/benchmark: New. * doc/benchmark/compression.txt: New, doc. * img/space_debris.pgm: a new image. doc/benchmark/compression.txt | 47 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) Index: doc/benchmark/compression.txt --- doc/benchmark/compression.txt (revision 0) +++ doc/benchmark/compression.txt (revision 0) @@ -0,0 +1,47 @@ + -*- outline -*- + +* Compression ratio benchmarks: + +** Test process: + - Load the initial image. + - Label the image using the labelling::blobs algorithm. + - Do a fold transformation on the loaded image. + - Encode the loaded image into the destination type. + - Compute the compression ratio of the encoded image. + +** Compression ratio: +The compression ratio is computed the following way: + CR = image_memory_size / size_of(point) * number_of_image_points + +** Tested images: + +--- Images - Size --- +trunk/img/small.pgm 4.1K +trunk/img/space_debris.pgm 1.3M + + +** rle_image: + +--- Images - Compression Ratio - Time --- +trunk/img/small.pgm 0.494708 0.052s +trunk/img/space_debris.pgm 0.112602 34.440s + + +** sparse_image: + +--- Images - Compression Ratio - Time --- +trunk/img/small.pgm 0.596522 0.054s +trunk/img/space_debris.pgm 0.144853 34.637 + + +** mono_rle_image: + +--- Images - Compression Ratio - Time --- +trunk/img/small.pgm 0.610811 0.044s +trunk/img/space_debris.pgm 0.000688533 10.604s + +** mono_obased_rle_image: + +--- Images - Compression Ratio - Time --- +trunk/img/small.pgm 0.955393 0.067s +trunk/img/space_debris.pgm 0.216746 40.001 Index: img/space_debris.pgm Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Property changes on: img/space_debris.pgm ___________________________________________________________________ Name: svn:mime-type + application/octet-stream

1 0

1816: Sandbox: ICP: 'lazy'_map.
by Ugo Jardonnet 31 Mar '08

31 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Sandbox: ICP: 'lazy'_map. * sandbox/jardonnet/test/icp.cc: Update. * sandbox/jardonnet/test/reduce.cc: New: image scaling. * sandbox/jardonnet/test/01.pbm, * sandbox/jardonnet/test/02.pbm: New: test images. * sandbox/jardonnet/registration/icp.hh: Use type lazy_map instead of std::pair, in order to use sp�cific constructors. * sandbox/jardonnet/registration/projection.hh: update. * sandbox/jardonnet/registration/tools.hh: Add tools for boxes (to include in Milena?). registration/icp.hh | 25 +++++++++-------- registration/projection.hh | 27 ++++-------------- registration/tools.hh | 66 +++++++++++++++++++++++++++++++++++++++++++++ test/reduce.cc | 26 +++++++++++++++++ 4 files changed, 113 insertions(+), 31 deletions(-) Index: sandbox/jardonnet/test/icp.cc Index: sandbox/jardonnet/test/reduce.cc --- sandbox/jardonnet/test/reduce.cc (revision 0) +++ sandbox/jardonnet/test/reduce.cc (revision 0) @@ -0,0 +1,26 @@ +#include <mln/core/image2d.hh> + +#include <mln/io/pbm/load.hh> +#include <mln/io/pbm/save.hh> + +#include <mln/subsampling/subsampling.hh> + + +int main(int argc, char*argv[]) +{ + if (argc != 3) + { + std::cout << "usage : " << argv[0] << " in.pbm out.pbm" << std::endl; + } + + using namespace mln; + + image2d<bool> img; + + io::pbm::load(img, argv[1]); + + image2d<bool> output = subsampling::subsampling(img, make::dpoint2d(2,2), argc); + + io::pbm::save(output, argv[2]); +} + Index: sandbox/jardonnet/test/01.pbm Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Property changes on: sandbox/jardonnet/test/01.pbm ___________________________________________________________________ Name: svn:mime-type + application/octet-stream Index: sandbox/jardonnet/test/02.pbm Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Property changes on: sandbox/jardonnet/test/02.pbm ___________________________________________________________________ Name: svn:mime-type + application/octet-stream Index: sandbox/jardonnet/registration/icp.hh --- sandbox/jardonnet/registration/icp.hh (revision 1815) +++ sandbox/jardonnet/registration/icp.hh (working copy) @@ -66,24 +66,24 @@ namespace impl { - template <typename P, typename T1, typename T2> + template <typename P, typename T> inline p_array icp_(p_array& C, const p_array& X, - std::pair<T1,T2>&) + lazy_map<T>& map) { trace::entering("registration::impl::icp_"); unsigned int k; quat7<P::dim> old_qk, qk; float err; - float err_bis; + //float err_bis; p_array Ck(C), Xk(C); //FIXME: Xk copy C algebra::vec<P::dim,float> mu_C = center(C), mu_Xk; - const float epsilon = 1e-2; + const float epsilon = 1;//1e-3; //// step 1 k = 0; @@ -91,7 +91,7 @@ //// step 2 //err_bis = projection::fill_Xk(Ck, map, Xk); //projection::de_base(Ck, X, Xk, err_bis); - projection::memo(Ck, X, Xk, err_bis); + projection::memo(Ck, X, Xk, map); mu_Xk = center(Xk); @@ -104,12 +104,11 @@ //// err = d(Ck+1,Xk) err = rms(Ck, Xk); - std::cout << "error :" << err << std::endl; + std::cout << k << ' ' << err << std::endl; //plot file ++k; } while (k < 3 || (qk - old_qk).sqr_norm() > epsilon); - std::cout << "nb of iterations : " << k << std::endl; trace::exiting("registration::impl::icp_"); return Ck; } @@ -120,8 +119,8 @@ //Only for 2d and 3d image template <typename I, typename J> inline - mln_concrete(I) - icp(Image& cloud_, + mln_concrete(I) //FIXME: should return something else ? qk ? + icp(const Image& cloud_, const Image<J>& surface_) { trace::entering("registration::icp"); @@ -142,7 +141,7 @@ fun::cham<point3d> fun; w_window<mln_dpoint(I3d), float> chamfer = make::w_window(win3d, fun); */ - std::pair<mln_ch_value(I3d,float), mln_ch_value(I3d,mln_point(I3d)) > maps;// = + //std::pair<mln_ch_value(I3d,float), mln_ch_value(I3d,mln_point(I3d)) > maps;// = //dt::chamfer(surface, chamfer); @@ -150,7 +149,11 @@ p_array<mln_point(I3d)> c = convert::to_p_array(cloud); p_array<mln_point(I3d)> x = convert::to_p_array(surface); - p_array<mln_point(I3d)> res = impl::icp_(c, x, maps); + //build closest point map + //lazy_map<I3d> map(enlarge(bigger(c.bbox(),x.bbox()),50)); + lazy_map<I3d> map(1000,1000,50); + + p_array<mln_point(I3d)> res = impl::icp_(c, x, map); //to 2d : projection (FIXME:if 3d) //mln_concrete(I) output = convert::to_image2d(res)? Index: sandbox/jardonnet/registration/projection.hh --- sandbox/jardonnet/registration/projection.hh (revision 1815) +++ sandbox/jardonnet/registration/projection.hh (working copy) @@ -67,27 +67,18 @@ } - template <typename P> - void memo(// input - const p_array& Ck, + template <typename P, typename T> + void memo(const p_array& Ck, const p_array& X, - // inout p_array& Xk, - float& err) + lazy_map<T>& map) // first: closest points, second: is_computed { - //FIXME: remove static - //FIXME: domain generated by X and C's domain? - static image3d<point3d> map(1000,1000,10); - static image3d<bool> mapset(1000,1000,10); - assert(Ck.npoints() == Xk.npoints()); - err = 0.f; - for (size_t i = 0; i < Ck.npoints(); ++i) { float best_d; - if (mapset(Ck[i]) == false) + if (map.known(Ck[i]) == false) { algebra::vec<P::dim,float> Cki = Ck[i]; algebra::vec<P::dim,float> best_x = X[0]; @@ -103,16 +94,12 @@ } } Xk.hook_()[i] = algebra::to_point(best_x); - map(Ck[i]) = Xk[i]; - mapset(Ck[i]) = true; + map.map(Ck[i]) = Xk[i]; + map.known(Ck[i]) = true; } else - { - Xk.hook_()[i] = map(Ck[i]); - } - err += best_d; + Xk.hook_()[i] = map.map(Ck[i]); } - err /= Ck.npoints(); } } // end of namespace projection Index: sandbox/jardonnet/registration/tools.hh --- sandbox/jardonnet/registration/tools.hh (revision 1815) +++ sandbox/jardonnet/registration/tools.hh (working copy) @@ -6,9 +6,75 @@ # include <mln/algebra/mat.hh> # include <mln/core/p_array.hh> + namespace mln { + + //FIXME: Shall we use something *really* lazy + template <typename I> + struct lazy_map + { + template <typename P> + lazy_map(const box_& domain) + : map(domain), known(domain) + { } + + lazy_map(int nrows, int ncols, int bdr = 3) + : map(nrows, ncols, bdr), known(nrows,ncols,bdr) + { } + + mln_ch_value(I, mln_point(I)) map; + mln_ch_value(I, bool) known; + }; + + + // Point + + template <typename P> + P min(const P& a, const P& b) + { + if (a > b) + return b; + return a; + } + + template <typename P> + P max(const P& a, const P& b) + { + if (a < b) + return b; + return a; + } + + + // Box + + template <typename P> + inline + const box_& //dif + enlarge(const box_& box, unsigned b) + { + for (unsigned i = 0; i < P::dim; ++i) + { + box.pmin()[i] -= b; + box.pmax()[i] += b; + } + return box; + } + + template <typename P> + box_ bigger(box_ a, box_ b) + { + P pmin,pmax; + + pmin = min(a.pmin(), b.pmin()); + pmax = max(a.pmax(), b.pmax()); + + return box_(pmin, pmax); + } + + //FIXME: move? namespace convert {

1 0

1815: Sandbox: ICP : projection::memo.
by Ugo Jardonnet 29 Mar '08

29 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <jardonnet(a)lrde.epita.fr> Sandbox: ICP : projection::memo. * sandbox/jardonnet/test/icp.cc: Update. * sandbox/jardonnet/test/check: Test projection techniques. * sandbox/jardonnet/TODO: Update. * sandbox/jardonnet/registration/quat7.hh: Correction. * sandbox/jardonnet/registration/cloud.hh: Correction. * sandbox/jardonnet/registration/jacobi.hh: Add FIXME (nD). * sandbox/jardonnet/registration/icp.hh: Improvment. * sandbox/jardonnet/registration/projection.hh: Add a projection technique "memo" computing closest point only if needed. * sandbox/jardonnet/registration/tools.hh: Gather together tools to add to milena. mln/make/window3d.hh | 2 sandbox/jardonnet/TODO | 14 ++ sandbox/jardonnet/registration/cloud.hh | 4 sandbox/jardonnet/registration/icp.hh | 117 +++++++---------------- sandbox/jardonnet/registration/jacobi.hh | 2 sandbox/jardonnet/registration/projection.hh | 57 ++++++++++- sandbox/jardonnet/registration/quat7.hh | 50 ++------- sandbox/jardonnet/registration/tools.hh | 137 +++++++++++++++++++++++++++ sandbox/jardonnet/test/check | 13 ++ 9 files changed, 273 insertions(+), 123 deletions(-) Index: mln/make/window3d.hh --- mln/make/window3d.hh (revision 1814) +++ mln/make/window3d.hh (working copy) @@ -62,7 +62,7 @@ inline mln::window3d window3d(bool (&values)[M]) { - int h = unsigned(std::pow(float(M), 1 / 3)) / 2; + int h = unsigned(std::pow(float(M), float(1. / 3.))) / 2; mln_precondition((2 * h + 1) * (2 * h + 1) * (2 * h + 1) == M); mln::window3d tmp; unsigned i = 0; Index: sandbox/jardonnet/test/icp.cc Index: sandbox/jardonnet/test/check --- sandbox/jardonnet/test/check (revision 0) +++ sandbox/jardonnet/test/check (revision 0) @@ -0,0 +1,13 @@ +#!/bin/zsh + +touch log + +echo "### report : projection" >> log +echo "*** maps ***" >> log +time ./+icp_maps.exe +01.pbm +02.pbm >> log +echo "*** de_base ***" >> log +time ./+icp_base.exe +01.pbm +02.pbm >> log +echo "*** memo ***" >> log +time ./+icp_memo.exe +01.pbm +02.pbm >> log + +cat log Property changes on: sandbox/jardonnet/test/check ___________________________________________________________________ Name: svn:executable + * Index: sandbox/jardonnet/TODO --- sandbox/jardonnet/TODO (revision 1814) +++ sandbox/jardonnet/TODO (working copy) @@ -6,3 +6,17 @@ gaussian.cc:22: error: no match for 'operator==' in 'img == out' - - +adapt test for threshold (old thresholding) +- - + +- Enlever static dans projection::memo + +Note: ++01.bmp: 943 pts +30 itérations : 30*943 = 28290 calcul de ppp +Domaine +02.bmp: 777x480 = 362082 +nb de ppp calculé memo = 11749 + +map 1:40 +de_base 10.5 +memo 9.5 \ No newline at end of file Index: sandbox/jardonnet/registration/quat7.hh --- sandbox/jardonnet/registration/quat7.hh (revision 1814) +++ sandbox/jardonnet/registration/quat7.hh (working copy) @@ -15,37 +15,9 @@ # include <mln/trait/all.hh> +# include <mln/make/vec.hh> -// FIXME : move elsewhere -namespace mln -{ - namespace algebra - { - - template<unsigned n, unsigned m, typename T> - mat<m,n,T> - trans(const mat<n,m,T>& matrice) - { - mat<m,n,T> tmp; - for (unsigned i = 0; i < n; ++i) - for (unsigned j = 0; j < m; ++j) - tmp(j,i) = matrice(i,j); - return tmp; - } - - // trace - - template<unsigned n, typename T> inline - float tr(const mat<n,n,T>& m) - { - float f = 0.f; - for (unsigned i = 0; i < n; ++i) - f += m(i,i); - return f; - } - - } -} +# include "tools.hh" namespace mln { @@ -89,10 +61,15 @@ assert(input.npoints() == output.npoints()); assert(_qR.is_unit()); - //FIXME utiliser equivalent pour p_array - //std::transform(input.begin(), input.end(), - // output.begin(), - // *this); + for (size_t i = 0; i < input.npoints(); i++) + output.hook_()[i] = algebra::to_point((*this)(input[i])); + } + + friend std::ostream& operator << (std::ostream& os, quat7& q) + { + std::cout << q._qR << std::endl; + std::cout << q._qT << std::endl; + return os; } }; @@ -121,8 +98,6 @@ // 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) { @@ -131,12 +106,11 @@ 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 <...> + const algebra::mat<3,1,float> D = make::mat<3,1,3,float>(v); algebra::mat<4,4,float> Qk; Index: sandbox/jardonnet/registration/cloud.hh --- sandbox/jardonnet/registration/cloud.hh (revision 1814) +++ sandbox/jardonnet/registration/cloud.hh (working copy) @@ -51,7 +51,7 @@ return f / a1.npoints(); } - } -} + } // end of namespace registration +} // end of namespace mln #endif // ndef CLOUD_HH Index: sandbox/jardonnet/registration/jacobi.hh --- sandbox/jardonnet/registration/jacobi.hh (revision 1814) +++ sandbox/jardonnet/registration/jacobi.hh (working copy) @@ -11,7 +11,7 @@ namespace mln { - + //FIXME: nD ? #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 1814) +++ sandbox/jardonnet/registration/icp.hh (working copy) @@ -35,7 +35,10 @@ # include <mln/algebra/quat.hh> # include <mln/algebra/vec.hh> -# include <mln/core/w_window.hh> +# include <mln/make/w_window.hh> +# include <mln/make/window3d.hh> + +# include "tools.hh" # include "cloud.hh" # include "quat7.hh" @@ -66,49 +69,47 @@ template <typename P, typename T1, typename T2> inline p_array - icp_(const p_array& C, - const p_array&, - std::pair<T1,T2>& map) + icp_(p_array& C, + const p_array& X, + std::pair<T1,T2>&) { trace::entering("registration::impl::icp_"); unsigned int k; quat7<P::dim> old_qk, qk; - float err, err_bis; - p_array Ck(C), Xk(C); + float err; + float err_bis; + p_array Ck(C), Xk(C); //FIXME: Xk copy C algebra::vec<P::dim,float> mu_C = center(C), mu_Xk; - const float epsilon = 1e-3; + const float epsilon = 1e-2; - //step 1 + //// step 1 k = 0; - Ck = C; - do { - std::cout << "step2: projection" << std::endl; - //step 2 - err_bis = projection::fill_Xk(Ck, map, Xk); + //// step 2 + //err_bis = projection::fill_Xk(Ck, map, Xk); + //projection::de_base(Ck, X, Xk, err_bis); + projection::memo(Ck, X, Xk, err_bis); - std::cout << "step2.1: center" << std::endl; mu_Xk = center(Xk); - std::cout << "step3: Compute qk" << std::endl; - // step 3 + //// step 3 old_qk = qk; qk = match(C, mu_C, Xk, mu_Xk); - std::cout << "step4: apply qk" << std::endl; - // step 4 + //// step 4 qk.apply_on(C, Ck); // Ck+1 = qk(C) - // err = d(Ck+1,Xk) + //// err = d(Ck+1,Xk) err = rms(Ck, Xk); + std::cout << "error :" << err << std::endl; ++k; - std::cout << "error is " << err << std::endl; } while (k < 3 || (qk - old_qk).sqr_norm() > epsilon); + std::cout << "nb of iterations : " << k << std::endl; trace::exiting("registration::impl::icp_"); return Ck; } @@ -116,42 +117,6 @@ } // end of namespace mln::registration::impl - //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 @@ -163,44 +128,38 @@ mln_precondition(exact(cloud_).has_data()); mln_precondition(exact(surface_).has_data()); - 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_)); - - std::cout << "chamfer" << std::endl; - - //FIXME: not a chamfer. etienne? + /* //create a pair (distance map, closest point) - // 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); + bool w[27] = {true, true, true, true, true, true, true, true, true, + true, true, true, true, true, true, true, true, true, + true, true, true, true, true, true, true, true, true}; + window<mln_dpoint(I3d)> win3d = make::window3d(w); + fun::cham<point3d> fun; + w_window<mln_dpoint(I3d), 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. - 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); + //build p_arrays. + p_array<mln_point(I3d)> c = convert::to_p_array(cloud); + p_array<mln_point(I3d)> x = convert::to_p_array(surface); - std::cout << "Start ICP" << std::endl; p_array<mln_point(I3d)> res = impl::icp_(c, x, maps); //to 2d : projection (FIXME:if 3d) + //mln_concrete(I) output = convert::to_image2d(res)? mln_concrete(I) output(exact(cloud_).domain()); - for (unsigned i; i < res.npoints(); i++) + for (size_t i = 0; i < res.npoints(); i++) { point2d p(res[i][0], res[i][1]); + //FIXME: not necessary if output(res.bbox()) + //if (output.has(p)) output(p) = true; } Index: sandbox/jardonnet/registration/projection.hh --- sandbox/jardonnet/registration/projection.hh (revision 1814) +++ sandbox/jardonnet/registration/projection.hh (working copy) @@ -21,16 +21,18 @@ for (size_t i = 0; i < Ck.npoints(); ++i) { + //FIXME: bof + //if (map.second.has(Ck[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, @@ -63,7 +65,58 @@ } err /= Ck.npoints(); } + + + template <typename P> + void memo(// input + const p_array& Ck, + const p_array& X, + // inout + p_array& Xk, + float& err) + { + //FIXME: remove static + //FIXME: domain generated by X and C's domain? + static image3d<point3d> map(1000,1000,10); + static image3d<bool> mapset(1000,1000,10); + + assert(Ck.npoints() == Xk.npoints()); + + err = 0.f; + + for (size_t i = 0; i < Ck.npoints(); ++i) + { + float best_d; + if (mapset(Ck[i]) == false) + { + algebra::vec<P::dim,float> Cki = Ck[i]; + algebra::vec<P::dim,float> best_x = X[0]; + best_d = norm::l2(Cki - best_x); + for (size_t j = 1; j < X.npoints(); ++j) + { + algebra::vec<P::dim,float> Xj = X[j]; + float d = norm::l2(Cki - Xj); + if (d < best_d) + { + best_d = d; + best_x = Xj; } } + Xk.hook_()[i] = algebra::to_point(best_x); + map(Ck[i]) = Xk[i]; + mapset(Ck[i]) = true; + } + else + { + Xk.hook_()[i] = map(Ck[i]); + } + err += best_d; + } + err /= Ck.npoints(); + } + + } // end of namespace projection + +} // end of namespace mln #endif // ndef PROJECTION_HH Index: sandbox/jardonnet/registration/tools.hh --- sandbox/jardonnet/registration/tools.hh (revision 0) +++ sandbox/jardonnet/registration/tools.hh (revision 0) @@ -0,0 +1,137 @@ +#ifndef REGISTRATION_TOOL_HH +# define REGISTRATION_TOOL_HH + +// temporary + +# include <mln/algebra/mat.hh> +# include <mln/core/p_array.hh> + +namespace mln +{ + + //FIXME: move? + namespace convert + { + + template <typename I> + inline + p_array<mln_point(I)> + to_p_array(const Image& img_) + { + const I& img = exact(img_); + + p_array<mln_point(I)> a; + + mln_piter(I) p(img.domain()); + for_all(p) + if (img(p)) + a.append(p); + return a; + } + + //FIXME: to write + /* + template <typename A> + inline + image2d<mln_value(A)> + to_image2d(const A& a) + { + image2d<mln_value(A)> img(a.bbox()); + for (size_t i = 0; i < a.npoints(); i++) + { + point2d p(res[i][0], res[i][1]); + //FIXME: BOF + //if (output.has(p)) + output(p) = true; + } + } + */ + + template <typename T> + inline + 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> + inline + image3d<T> + to_image_3d(const image2d<T>& img) + { + point3d pmin(img.domain().pmin()[0], img.domain().pmin()[1], -1); + point3d pmax(img.domain().pmax()[0], img.domain().pmax()[1], 1); + 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; + } + + } // end of namespace convert + + + + namespace fun + { + //FIXME: temporary + template <typename C, typename T= float> + struct cham : public Function_p2v< cham<C,T> > + { + typedef T result; + //bad + T operator()(dpoints_fwd_piter<mln::dpoint_<mln::grid::cube, int> >& v) const + { + C o = C::origin; + if (v < o) + return 1.; + else + return 0.; + } + }; + } // end of namespace fun + + + + namespace algebra + { + + template<unsigned n, unsigned m, typename T> + mat<m,n,T> + trans(const mat<n,m,T>& matrice) + { + mat<m,n,T> tmp; + for (unsigned i = 0; i < n; ++i) + for (unsigned j = 0; j < m; ++j) + tmp(j,i) = matrice(i,j); + return tmp; + } + + // trace + + template<unsigned n, typename T> inline + float tr(const mat<n,n,T>& m) + { + float f = 0.f; + for (unsigned i = 0; i < n; ++i) + f += m(i,i); + return f; + } + + } // end of namespace algebra + +} // end of namespace mln + +#endif // REGISTRATION_TOOLS_HH

1 0

1814: Have piters on line graph windows and neighborhoods actually use them.
by Roland Levillain 28 Mar '08

28 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena All the duplicated code is the source of all those repetitive changes. My next patches will be about factoring all those guys. Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have piters on line graph windows and neighborhoods actually use them. * mln/core/line_graph_window_piter.hh (mln::line_graph_window_fwd_piter<P, W>) (mln::line_graph_window_bkd_piter<P, W>): Have these class templates take a window type as second, additional parameter. (mln::line_graph_window_fwd_piter<P, W>::nbh_) (mln::line_graph_window_bkd_piter<P, W>::nbh_): New attributes. (line_graph_window_fwd_piter) (line_graph_window_bkd_piter): Adjust ctors. (mln::line_graph_window_fwd_piter<P, W>::first_) (mln::line_graph_window_fwd_piter<P, W>::step_) (mln::line_graph_window_bkd_piter<P, W>::first_) (mln::line_graph_window_bkd_piter<P, W>::step_): New methods. (mln::line_graph_window_fwd_piter<P, W>::start) (mln::line_graph_window_fwd_piter<P, W>::next_) (mln::line_graph_window_bkd_piter<P, W>::start) (mln::line_graph_window_bkd_piter<P, W>::next_): Delegate the body of the routine to the window. * mln/core/line_graph_elt_window.hh (mln::line_graph_elt_window::fwd_qiter) (mln::line_graph_elt_window::bkd_qiter): Adjust typedefs. (mln::line_graph_elt_window::psite): New typedef. (mln::line_graph_elt_window::start) (mln::line_graph_elt_window::next_): New methods. * mln/core/line_graph_neighborhood_piter.hh (mln::line_graph_neighborhood_fwd_piter<P, N>) (mln::line_graph_neighborhood_bkd_piter<P, N>): Have these class templates take a neighborhood type as second, additional parameter. (mln::line_graph_neighborhood_fwd_piter<P, N>::nbh_) (mln::line_graph_neighborhood_bkd_piter<P, N>::nbh_): New attributes. (line_graph_neighborhood_fwd_piter) (line_graph_neighborhood_bkd_piter): Adjust ctors. (mln::line_graph_neighborhood_fwd_piter<P, N>::first_) (mln::line_graph_neighborhood_fwd_piter<P, N>::step_) (mln::line_graph_neighborhood_bkd_piter<P, N>::first_) (mln::line_graph_neighborhood_bkd_piter<P, N>::step_): New methods. (mln::line_graph_neighborhood_fwd_piter<P, N>::start) (mln::line_graph_neighborhood_fwd_piter<P, N>::next_) (mln::line_graph_neighborhood_bkd_piter<P, N>::start) (mln::line_graph_neighborhood_bkd_piter<P, N>::next_): Delegate the body of the routine to the neighborhood. * mln/core/line_graph_elt_neighborhood.hh (mln::line_graph_elt_neighborhood::fwd_qiter) (mln::line_graph_elt_neighborhood::bkd_qiter): Adjust typedefs. (mln::line_graph_elt_neighborhood::psite): New typedef. (mln::line_graph_elt_neighborhood::start) (mln::line_graph_elt_neighborhood::next_): New methods. * tests/core/line_graph_elt_window.cc: Update test. * tests/core/line_graph_elt_neighborhood.cc: New test. mln/core/line_graph_elt_neighborhood.hh | 92 +++++++--- mln/core/line_graph_elt_window.hh | 90 ++++++---- mln/core/line_graph_neighborhood_piter.hh | 260 ++++++++++++++++------------- mln/core/line_graph_window_piter.hh | 263 ++++++++++++++++-------------- tests/core/line_graph_elt_neighborhood.cc | 43 +++- tests/core/line_graph_elt_window.cc | 29 +++ 6 files changed, 479 insertions(+), 298 deletions(-) Index: mln/core/line_graph_window_piter.hh --- mln/core/line_graph_window_piter.hh (revision 1813) +++ mln/core/line_graph_window_piter.hh (working copy) @@ -57,16 +57,16 @@ template <typename P> class line_graph_psite; - /*---------------------------------. - | line_graph_window_fwd_piter. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_fwd_piter<P, W>. | + `------------------------------------*/ /// \brief Forward iterator on line graph window. - template <typename P> + template <typename P, typename W> class line_graph_window_fwd_piter : - public Point_Iterator< line_graph_window_fwd_piter > // or Iterator<...>? + public Point_Iterator< line_graph_window_fwd_piter<P, W> > { - typedef line_graph_window_fwd_piter self_; + typedef line_graph_window_fwd_piter<P, W> self_; typedef Point_Iterator< self_ > super_; public: @@ -83,8 +83,9 @@ public: /// Construction. /// \{ - template <typename W, typename Pref> - line_graph_window_fwd_piter(const W& win, const Point_Site<Pref>& p_ref); + template <typename Pref> + line_graph_window_fwd_piter(const Window<W>& win, + const Point_Site<Pref>& p_ref); /// \} /// Manipulation. @@ -117,11 +118,23 @@ coord operator[](unsigned i) const; /// \} + /// Internals, used by the window. + /// \{ + 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 edges of the underlying graph. + util::edge_id id_; + /// \} + private: + /// The window. + const W& win_; /// The ``central'' psite of the window. const psite& p_ref_; - /// An internal iterator on the set of edges of the underlying graph. - util::edge_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -134,22 +147,22 @@ the general mechanism provided by Point_Site. But then again, we need to refine/adjust the interface of Point_Site w.r.t. the mandatory conversions to points. */ - template <typename P> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_fwd_piter& p); + operator<<(std::ostream& ostr, const line_graph_window_fwd_piter<P, W>& p); - /*---------------------------------. - | line_graph_window_bkd_piter. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_bkd_piter<P, W>. | + `------------------------------------*/ /// \brief Backward iterator on line graph window. - template <typename P> + template <typename P, typename W> class line_graph_window_bkd_piter : - public Point_Iterator< line_graph_window_bkd_piter > // or Iterator<...>? + public Point_Iterator< line_graph_window_bkd_piter<P, W> > { - typedef line_graph_window_bkd_piter self_; + typedef line_graph_window_bkd_piter<P, W> self_; typedef Point_Iterator< self_ > super_; public: @@ -166,8 +179,9 @@ public: /// Construction. /// \{ - template <typename W, typename Pref> - line_graph_window_bkd_piter(const W& win, const Point_Site<Pref>& p_ref); + template <typename Pref> + line_graph_window_bkd_piter(const Window<W>& win, + const Point_Site<Pref>& p_ref); /// \} /// Manipulation. @@ -200,11 +214,23 @@ coord operator[](unsigned i) const; /// \} + /// Internals, used by the window. + /// \{ + 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 edges of the underlying graph. + util::edge_id id_; + /// \} + private: + /// The window. + const W& win_; /// The ``central'' psite of the window. const psite& p_ref_; - /// An internal iterator on the set of edges of the underlying graph. - util::edge_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -217,26 +243,26 @@ the general mechanism provided by Point_Site. But then again, we need to refine/adjust the interface of Point_Site w.r.t. the mandatory conversions to points. */ - template <typename P> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_bkd_piter& p); + operator<<(std::ostream& ostr, const line_graph_window_bkd_piter<P, W>& p); # ifndef MLN_INCLUDE_ONLY - /*---------------------------------. - | line_graph_window_fwd_piter. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_fwd_piter<P, W>. | + `------------------------------------*/ - // FIXME: Currently, argument win is ignored. - template <typename P> - template <typename W, typename Pref> + template <typename P, typename W> + template <typename Pref> inline - line_graph_window_fwd_piter::line_graph_window_fwd_piter(const W& /* win */, + line_graph_window_fwd_piter<P, W>::line_graph_window_fwd_piter(const Window<W>& win, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : win_(exact(win)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() { @@ -244,10 +270,10 @@ invalidate(); } - template <typename P> + template <typename P, typename W> inline bool - line_graph_window_fwd_piter::is_valid() const + line_graph_window_fwd_piter<P, W>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -255,52 +281,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter::invalidate() + line_graph_window_fwd_piter<P, W>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter::start() + line_graph_window_fwd_piter<P, W>::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_(). */ + win_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter::next_() + line_graph_window_fwd_piter<P, W>::next_() { - /* FIXME: This is inefficient. The graph structure should be able - to produce the set of adjacent edges fast. Boost Graphs - probably provides adequates structures to fetch these - neighbors in constant time. */ - /* FIXME: Moreover, the behavior of next shall depend on the - window, which is not the case now! (Currently, next_() behaves - as win was always an elementary window.) */ - do - ++id_; - while (is_valid() && !adjacent_or_equal_to_p_ref_()); + win_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> + inline + void + line_graph_window_fwd_piter<P, W>::first_() + { + id_ = 0; + } + + template <typename P, typename W> + inline + void + line_graph_window_fwd_piter<P, W>::step_() + { + ++id_; + } + + + template <typename P, typename W> inline bool - line_graph_window_fwd_piter::adjacent_or_equal_to_p_ref_() const + line_graph_window_fwd_piter<P, W>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -330,68 +359,69 @@ return false; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter::update_() + line_graph_window_fwd_piter<P, W>::update_() { // Update psite_. psite_ = line_graph_psite(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename W> inline const P& - line_graph_window_fwd_piter::to_point() const + line_graph_window_fwd_piter<P, W>::to_point() const { return p_; } - template <typename P> + template <typename P, typename W> inline const line_graph_psite& - line_graph_window_fwd_piter::to_psite() const + line_graph_window_fwd_piter<P, W>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename W> inline - line_graph_window_fwd_piter::operator line_graph_psite () const + line_graph_window_fwd_piter<P, W>::operator line_graph_psite () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename W> inline mln_coord(P) - line_graph_window_fwd_piter::operator[](unsigned i) const + line_graph_window_fwd_piter<P, W>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_fwd_piter& p) + operator<<(std::ostream& ostr, const line_graph_window_fwd_piter<P, W>& p) { return ostr << p.to_psite(); } - /*---------------------------------. - | line_graph_window_bkd_piter. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_bkd_piter<P, W>. | + `------------------------------------*/ // FIXME: Currently, argument win is ignored. - template <typename P> - template <typename W, typename Pref> + template <typename P, typename W> + template <typename Pref> inline - line_graph_window_bkd_piter::line_graph_window_bkd_piter(const W& /* win */, + line_graph_window_bkd_piter<P, W>::line_graph_window_bkd_piter(const Window<W>& win, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : win_(exact(win)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() { @@ -399,10 +429,10 @@ invalidate(); } - template <typename P> + template <typename P, typename W> inline bool - line_graph_window_bkd_piter::is_valid() const + line_graph_window_bkd_piter<P, W>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -410,52 +440,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter::invalidate() + line_graph_window_bkd_piter<P, W>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter::start() + line_graph_window_bkd_piter<P, W>::start() { - id_ = p_ref_.plg().gr_->nedges() - 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_(). */ + win_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter::next_() + line_graph_window_bkd_piter<P, W>::next_() { - /* FIXME: This is inefficient. The graph structure should be able - to produce the set of adjacent edges fast. Boost Graphs - probably provides adequates structures to fetch these - neighbors in constant time. */ - /* FIXME: Moreover, the behavior of next shall depend on the - window, which is not the case now! (Currently, next_() behaves - as win was always an elementary window.) */ - do - --id_; - while (is_valid() && !adjacent_or_equal_to_p_ref_()); + win_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> + inline + void + line_graph_window_bkd_piter<P, W>::first_() + { + id_ = p_ref_.plg().gr_->nedges() - 1; + } + + template <typename P, typename W> + inline + void + line_graph_window_bkd_piter<P, W>::step_() + { + --id_; + } + + + template <typename P, typename W> inline bool - line_graph_window_bkd_piter::adjacent_or_equal_to_p_ref_() const + line_graph_window_bkd_piter<P, W>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -485,52 +518,52 @@ return false; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter::update_() + line_graph_window_bkd_piter<P, W>::update_() { // Update psite_. psite_ = line_graph_psite(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename W> inline const P& - line_graph_window_bkd_piter::to_point() const + line_graph_window_bkd_piter<P, W>::to_point() const { return p_; } - template <typename P> + template <typename P, typename W> inline const line_graph_psite& - line_graph_window_bkd_piter::to_psite() const + line_graph_window_bkd_piter<P, W>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename W> inline - line_graph_window_bkd_piter::operator line_graph_psite () const + line_graph_window_bkd_piter<P, W>::operator line_graph_psite () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename W> inline mln_coord(P) - line_graph_window_bkd_piter::operator[](unsigned i) const + line_graph_window_bkd_piter<P, W>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_bkd_piter& p) + operator<<(std::ostream& ostr, const line_graph_window_bkd_piter<P, W>& p) { return ostr << p.to_psite(); } Index: mln/core/line_graph_elt_window.hh --- mln/core/line_graph_elt_window.hh (revision 1813) +++ mln/core/line_graph_elt_window.hh (working copy) @@ -28,13 +28,11 @@ #ifndef MLN_CORE_LINE_GRAPH_ELT_WINDOW_HH # define MLN_CORE_LINE_GRAPH_ELT_WINDOW_HH -/*! \file mln/core/line_graph_elt_window.hh - * - * \brief Definition of the elementary ``window'' on a line graph. - * - * \todo Make naming coherent: we have window (without '_') but - * point_, neighb_, etc. - */ +/// \file mln/core/line_graph_elt_window.hh +/// \brief Definition of the elementary ``window'' on a line graph. + +/* FIXME: Have a consistent naming: we have window (without '_') but + point_, neighb_, etc. */ /* FIXME: Factor those classes: - mln::graph_elt_window @@ -50,14 +48,11 @@ namespace mln { // Fwd decls. - template <typename P> class line_graph_window_fwd_piter; - template <typename P> class line_graph_window_bkd_piter; + template <typename P, typename W> class line_graph_window_fwd_piter; + template <typename P, typename W> class line_graph_window_bkd_piter; - /*! \brief Elementary window on line graph class. - * - * FIXME: Doc. - */ + /// \brief Elementary window on line graph class. template <typename P> class line_graph_elt_window : public Window< line_graph_elt_window > { @@ -66,23 +61,21 @@ public: /// Associated types. /// \{ - /// The type of point stored into the window. - // FIXME: Is this right, if we consider that this window stores - // psites, not points? + /// The type of point corresponding to the window. typedef P point; + /// The type of psite corresponding to the window. + typedef line_graph_psite psite; // FIXME: This is a dummy value. typedef void dpoint; - /*! \brief Point_Iterator type to browse the points of a generic window - * w.r.t. the ordering of delta-points. - */ - typedef line_graph_window_fwd_piter fwd_qiter; - - /*! \brief Point_Iterator type to browse the points of a generic window - * w.r.t. the reverse ordering of delta-points. - */ - typedef line_graph_window_bkd_piter bkd_qiter; + /// \brief Point_Iterator type to browse the psites of the window + /// w.r.t. the ordering of edges. + typedef line_graph_window_fwd_piter<P, self_> fwd_qiter; + + /// \brief Point_Iterator type to browse the psites of the window + /// w.r.t. the reverse ordering of edges. + typedef line_graph_window_bkd_piter<P, self_> bkd_qiter; /// The default qiter type. typedef fwd_qiter qiter; @@ -91,16 +84,25 @@ /// Construct an elementary line_graph window. line_graph_elt_window(); + /// Services for iterators. + /// \{ + /// Move \a piter to the beginning of the iteration on this window. + template <typename Piter> + void start(Point_Iterator<Piter>& piter) const; + /// Move \a piter to the next site on this window. + template <typename Piter> + void next_(Point_Iterator<Piter>& piter) const; + /// \} + + /// Interface of the concept Window. + /// \{ /// Is the window is empty? bool is_empty() const; - /// Is the window centered? bool is_centered() const; - /// Is the window symmetric? - // FIXME: We should defin this more precisely. + // FIXME: We should define this more precisely. bool is_symmetric() const; - /// Return the maximum coordinate gap between the window center /// and a window point. /* FIXME: This method returns a dummy value (0), since the delta @@ -114,9 +116,9 @@ It raises another question: should delta() be part of the concept ``Window''? */ unsigned delta() const; - /// Apply a central symmetry to the target window. self_& sym(); + /// \} }; @@ -129,6 +131,34 @@ } template <typename P> + template <typename Piter> + inline + void + line_graph_elt_window::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 + line_graph_elt_window::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_()); + } + + template <typename P> inline bool line_graph_elt_window::is_empty() const Index: mln/core/line_graph_neighborhood_piter.hh --- mln/core/line_graph_neighborhood_piter.hh (revision 1813) +++ mln/core/line_graph_neighborhood_piter.hh (working copy) @@ -57,16 +57,16 @@ template <typename P> class line_graph_psite; - /*---------------------------------------. - | line_graph_neighborhood_fwd_piter. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_fwd_piter<P, N>. | + `------------------------------------------*/ /// \brief Forward iterator on line graph neighborhood. - template <typename P> + template <typename P, typename N> class line_graph_neighborhood_fwd_piter : - public Point_Iterator< line_graph_neighborhood_fwd_piter > // or Iterator<...>? + public Point_Iterator< line_graph_neighborhood_fwd_piter<P, N> > { - typedef line_graph_neighborhood_fwd_piter self_; + typedef line_graph_neighborhood_fwd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -83,8 +83,8 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> - line_graph_neighborhood_fwd_piter(const N& nbh, + template <typename Pref> + line_graph_neighborhood_fwd_piter(const Neighborhood<N>& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -119,11 +119,23 @@ 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 edges of the underlying graph. + util::edge_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 edges of the underlying graph. - util::edge_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -136,23 +148,23 @@ the general mechanism provided by Point_Site. But then again, we need to refine/adjust the interface of Point_Site w.r.t. the mandatory conversions to points. */ - template <typename P> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_fwd_piter& p); + const line_graph_neighborhood_fwd_piter<P, N>& p); - /*---------------------------------------. - | line_graph_neighborhood_bkd_piter. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_bkd_piter<P, N>. | + `------------------------------------------*/ /// \brief Backward iterator on line graph neighborhood. - template <typename P> + template <typename P, typename N> class line_graph_neighborhood_bkd_piter : - public Point_Iterator< line_graph_neighborhood_bkd_piter > // or Iterator<...>? + public Point_Iterator< line_graph_neighborhood_bkd_piter<P, N> > { - typedef line_graph_neighborhood_bkd_piter self_; + typedef line_graph_neighborhood_bkd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -169,8 +181,8 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> - line_graph_neighborhood_bkd_piter(const N& nbh, + template <typename Pref> + line_graph_neighborhood_bkd_piter(const Neighborhood<N>& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -205,11 +217,23 @@ 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 edges of the underlying graph. + util::edge_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 edges of the underlying graph. - util::edge_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -222,27 +246,28 @@ the general mechanism provided by Point_Site. But then again, we need to refine/adjust the interface of Point_Site w.r.t. the mandatory conversions to points. */ - template <typename P> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_bkd_piter& p); + const line_graph_neighborhood_bkd_piter<P, N>& p); # ifndef MLN_INCLUDE_ONLY - /*---------------------------------------. - | line_graph_neighborhood_fwd_piter. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_fwd_piter<P, N>. | + `------------------------------------------*/ // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + template <typename P, typename N> + template <typename Pref> inline - line_graph_neighborhood_fwd_piter::line_graph_neighborhood_fwd_piter(const N& /* nbh */, + line_graph_neighborhood_fwd_piter<P, N>::line_graph_neighborhood_fwd_piter(const Neighborhood<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_() { @@ -250,10 +275,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - line_graph_neighborhood_fwd_piter::is_valid() const + line_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 @@ -261,52 +286,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter::invalidate() + line_graph_neighborhood_fwd_piter<P, N>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter::start() + line_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 - line_graph_neighborhood_fwd_piter::next_() + line_graph_neighborhood_fwd_piter<P, N>::next_() { - /* FIXME: This is inefficient. The graph structure should be able - to produce the set of adjacent edges 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 + line_graph_neighborhood_fwd_piter<P, N>::first_() + { + id_ = 0; + } + + template <typename P, typename N> + inline + void + line_graph_neighborhood_fwd_piter<P, N>::step_() + { + ++id_; + } + + + template <typename P, typename N> inline bool - line_graph_neighborhood_fwd_piter::adjacent_or_equal_to_p_ref_() const + line_graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -336,69 +364,70 @@ return false; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter::update_() + line_graph_neighborhood_fwd_piter<P, N>::update_() { // Update psite_. psite_ = line_graph_psite(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename N> inline const P& - line_graph_neighborhood_fwd_piter::to_point() const + line_graph_neighborhood_fwd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const line_graph_psite& - line_graph_neighborhood_fwd_piter::to_psite() const + line_graph_neighborhood_fwd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - line_graph_neighborhood_fwd_piter::operator line_graph_psite () const + line_graph_neighborhood_fwd_piter<P, N>::operator line_graph_psite () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - line_graph_neighborhood_fwd_piter::operator[](unsigned i) const + line_graph_neighborhood_fwd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_fwd_piter& p) + const line_graph_neighborhood_fwd_piter<P, N>& p) { return ostr << p.to_psite(); } - /*---------------------------------------. - | line_graph_neighborhood_bkd_piter. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_bkd_piter<P, N>. | + `------------------------------------------*/ // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + template <typename P, typename N> + template <typename Pref> inline - line_graph_neighborhood_bkd_piter::line_graph_neighborhood_bkd_piter(const N& /* nbh */, + line_graph_neighborhood_bkd_piter<P, N>::line_graph_neighborhood_bkd_piter(const Neighborhood<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_() { @@ -406,10 +435,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - line_graph_neighborhood_bkd_piter::is_valid() const + line_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 @@ -417,52 +446,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter::invalidate() + line_graph_neighborhood_bkd_piter<P, N>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter::start() + line_graph_neighborhood_bkd_piter<P, N>::start() { - id_ = p_ref_.plg().gr_->nedges() - 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 - line_graph_neighborhood_bkd_piter::next_() + line_graph_neighborhood_bkd_piter<P, N>::next_() { - /* FIXME: This is inefficient. The graph structure should be able - to produce the set of adjacent edges 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 + line_graph_neighborhood_bkd_piter<P, N>::first_() + { + id_ = p_ref_.plg().gr_->nedges() - 1; + } + + template <typename P, typename N> + inline + void + line_graph_neighborhood_bkd_piter<P, N>::step_() + { + --id_; + } + + + template <typename P, typename N> inline bool - line_graph_neighborhood_bkd_piter::adjacent_or_equal_to_p_ref_() const + line_graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -492,53 +524,53 @@ return false; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter::update_() + line_graph_neighborhood_bkd_piter<P, N>::update_() { // Update psite_. psite_ = line_graph_psite(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename N> inline const P& - line_graph_neighborhood_bkd_piter::to_point() const + line_graph_neighborhood_bkd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const line_graph_psite& - line_graph_neighborhood_bkd_piter::to_psite() const + line_graph_neighborhood_bkd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - line_graph_neighborhood_bkd_piter::operator line_graph_psite () const + line_graph_neighborhood_bkd_piter<P, N>::operator line_graph_psite () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - line_graph_neighborhood_bkd_piter::operator[](unsigned i) const + line_graph_neighborhood_bkd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_bkd_piter& p) + const line_graph_neighborhood_bkd_piter<P, N>& p) { return ostr << p.to_psite(); } Index: mln/core/line_graph_elt_neighborhood.hh --- mln/core/line_graph_elt_neighborhood.hh (revision 1813) +++ mln/core/line_graph_elt_neighborhood.hh (working copy) @@ -28,17 +28,11 @@ #ifndef MLN_CORE_LINE_GRAPH_ELT_NEIGHBORHOOD_HH # define MLN_CORE_LINE_GRAPH_ELT_NEIGHBORHOOD_HH -/*! \file mln/core/line_graph_elt_neighborhood.hh - * - * \brief Definition of the elementary ``window'' on a line graph. - * - * \todo Make naming coherent: we have window (without '_') but - * point_, neighb_, etc. - */ +/// \file mln/core/line_graph_elt_neighborhood.hh +/// \brief Definition of the elementary ``window'' on a line graph. -# include <mln/core/concept/neighborhood.hh> -# include <mln/core/line_graph_psite.hh> -# include <mln/core/line_graph_neighborhood_piter.hh> +/* FIXME: Have a consistent naming: we have window (without '_') but + point_, neighb_, etc. */ /* FIXME: Factor those classes: - mln::graph_elt_window @@ -46,17 +40,19 @@ - mln::line_graph_elt_window - mln::line_graph_elt_neighborhood. */ +# include <mln/core/concept/neighborhood.hh> +# include <mln/core/line_graph_psite.hh> +# include <mln/core/line_graph_neighborhood_piter.hh> + + namespace mln { // Fwd decls. - template <typename P> class line_graph_neighborhood_fwd_piter; - template <typename P> class line_graph_neighborhood_bkd_piter; + template <typename P, typename N> class line_graph_neighborhood_fwd_piter; + template <typename P, typename N> class line_graph_neighborhood_bkd_piter; - /*! \brief Elementary neighborhood on line graph class. - * - * FIXME: Doc. - */ + /// \brief Elementary neighborhood on line graph class. template <typename P> class line_graph_elt_neighborhood : public Neighborhood< line_graph_elt_neighborhood > @@ -66,29 +62,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 line_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 line_graph_neighborhood_fwd_piter fwd_niter; - - /*! \brief Point_Iterator type to browse the points of a generic - * neighborhood w.r.t. the reverse ordering of delta-points. - */ - typedef line_graph_neighborhood_bkd_piter bkd_niter; + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the ordering of edges. + typedef line_graph_neighborhood_fwd_piter<P, self_> fwd_niter; + + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the reverse ordering of edges. + typedef line_graph_neighborhood_bkd_piter<P, self_> bkd_niter; /// The default qiter type. typedef fwd_niter niter; /// \} + + /// 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 + line_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 + line_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/line_graph_elt_window.cc --- tests/core/line_graph_elt_window.cc (revision 1813) +++ tests/core/line_graph_elt_window.cc (working copy) @@ -49,6 +49,20 @@ | Graph. | `--------*/ + /* The graph is as follows and its corresponding line graph are as + follows: + + 0 1 2 3 4 0 1 2 3 4 + .----------- .----------- + | | + 0 | 0 2 0 | * * + 1 | \ / | 1 | 0 1 | + 2 | 1 | 2 | * 4 + 3 | \ | 3 | 2 | + 4 | 3-4 4 | *3* + + */ + // Points associated to nodes. std::vector<p_t> points; points.push_back(make::point2d(0,0)); // Point associated to node 0. @@ -76,7 +90,18 @@ // Line graph psite set. p_line_graph<p_t> plg(g); // Line graph point site. - line_graph_psite<p_t> psite(plg, 0); + line_graph_psite<p_t> p(plg, 1); // ``Sliding'' window of a psite of PLG. - line_graph_elt_window<p_t> win; + typedef line_graph_elt_window<p_t> win_t; + win_t win; + + mln_fwd_qiter_(win_t) fq(win, p); + for_all(fq) + std::cout << fq << " "; + std::cout << std::endl; + + mln_bkd_qiter_(win_t) bq(win, p); + for_all(bq) + std::cout << bq << " "; + std::cout << std::endl; } Index: tests/core/line_graph_elt_neighborhood.cc --- tests/core/line_graph_elt_neighborhood.cc (revision 1813) +++ tests/core/line_graph_elt_neighborhood.cc (working copy) @@ -25,15 +25,15 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/line_graph_elt_window.cc +/*! \file tests/core/line_graph_elt_neighborhood.cc * - * \brief Tests on mln::line_graph_elt_window. + * \brief Tests on mln::line_graph_elt_neighborhood. */ #include <vector> #include <mln/core/point2d.hh> -#include <mln/core/line_graph_elt_window.hh> +#include <mln/core/line_graph_elt_neighborhood.hh> #include <mln/debug/iota.hh> #include <mln/debug/println.hh> @@ -49,6 +49,20 @@ | Graph. | `--------*/ + /* The graph is as follows and its corresponding line graph are as + follows: + + 0 1 2 3 4 0 1 2 3 4 + .----------- .----------- + | | + 0 | 0 2 0 | * * + 1 | \ / | 1 | 0 1 | + 2 | 1 | 2 | * 4 + 3 | \ | 3 | 2 | + 4 | 3-4 4 | *3* + + */ + // Points associated to nodes. std::vector<p_t> points; points.push_back(make::point2d(0,0)); // Point associated to node 0. @@ -69,14 +83,25 @@ g.add_edge(3, 4); g.add_edge(4, 2); - /*------------------. - | Graph and window. | - `------------------*/ + /*-------------------------. + | Graph and neighborhood. | + `-------------------------*/ // Line graph psite set. p_line_graph<p_t> plg(g); // Line graph point site. - line_graph_psite<p_t> psite(plg, 0); - // ``Sliding'' window of a psite of PLG. - line_graph_elt_window<p_t> win; + line_graph_psite<p_t> p(plg, 1); + // ``Sliding'' neighborhood of a psite of PLG. + typedef line_graph_elt_neighborhood<p_t> nbh_t; + nbh_t nbh; + + mln_fwd_niter_(nbh_t) fq(nbh, p); + for_all(fq) + std::cout << fq << " "; + std::cout << std::endl; + + mln_bkd_niter_(nbh_t) bq(nbh, p); + for_all(bq) + std::cout << bq << " "; + std::cout << std::endl; }

1 0