Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 00025 00026 #ifndef MLN_CANVAS_LABELING_SORTED_HH 00027 # define MLN_CANVAS_LABELING_SORTED_HH 00028 00032 00033 00034 # include <mln/core/concept/image.hh> 00035 # include <mln/data/fill.hh> 00036 # include <mln/literal/zero.hh> 00037 # include <mln/extension/adjust_fill.hh> 00038 00039 # include <mln/data/sort_psites.hh> 00040 # include <mln/data/sort_offsets.hh> 00041 00042 # include <mln/canvas/labeling/generic.hh> 00043 # include <mln/canvas/labeling/internal/tests.hh> 00044 # include <mln/canvas/labeling/internal/find_root_fastest.hh> 00045 00046 00047 00048 namespace mln 00049 { 00050 00051 namespace canvas 00052 { 00053 00054 namespace labeling 00055 { 00056 00057 template <typename I, typename N, typename L, typename F> 00058 inline 00059 mln_ch_value(I, L) 00060 sorted(const Image<I>& input, const Neighborhood<N>& nbh, 00061 L& nlabels, F& functor, bool increasing); 00062 00063 00064 # ifndef MLN_INCLUDE_ONLY 00065 00066 00067 // Implementations. 00068 00069 namespace impl 00070 { 00071 00072 // Fastest sorted version 00073 00074 template <typename I, typename N, typename L, 00075 typename S, typename F> 00076 mln_ch_value(I, L) 00077 sorted_fastest(const Image<I>& input_, 00078 const Neighborhood<N>& nbh_, L& nlabels, 00079 const S& s, F& f) 00080 { 00081 trace::entering("canvas::impl::labeling::sorted_fastest"); 00082 00083 // FIXME: Test?! 00084 00085 const I& input = exact(input_); 00086 const N& nbh = exact(nbh_); 00087 00088 extension::adjust(input, nbh); 00089 00090 // Local type. 00091 typedef mln_psite(I) P; 00092 00093 // Auxiliary data. 00094 mln_ch_value(I, bool) deja_vu; 00095 mln_ch_value(I, unsigned) parent; 00096 00097 // Output. 00098 mln_ch_value(I, L) output; 00099 bool status; 00100 00101 // Initialization. 00102 { 00103 initialize(deja_vu, input); 00104 mln::data::fill(deja_vu, false); 00105 extension::fill(deja_vu, false); // So that the extension is ignored. 00106 00107 initialize(parent, input); 00108 00109 initialize(output, input); 00110 mln::data::fill(output, L(literal::zero)); 00111 nlabels = 0; 00112 00113 f.init_(); // Client initialization. 00114 } 00115 00116 util::array<int> dp = offsets_wrt(input, nbh); 00117 const unsigned n_nbhs = dp.nelements(); 00118 00119 const unsigned n_points = s.nelements(); 00120 00121 // First Pass. 00122 { 00123 for (int i = n_points - 1; i >=0; --i) // Backward. 00124 { 00125 unsigned p = s[i]; 00126 if (! f.handles_(p)) 00127 continue; 00128 00129 // Make-Set. 00130 parent.element(p) = p; 00131 f.init_attr_(p); 00132 00133 for (unsigned j = 0; j < n_nbhs; ++j) 00134 { 00135 unsigned n = p + dp[j]; 00136 if (! deja_vu.element(n)) 00137 continue; 00138 00139 if (f.equiv_(n, p)) 00140 { 00141 // Do-Union. 00142 unsigned r = internal::find_root_fastest(parent, n); 00143 if (r != p) 00144 { 00145 parent.element(r) = p; 00146 f.merge_attr_(r, p); 00147 } 00148 } 00149 else 00150 f.do_no_union_(n, p); 00151 } 00152 deja_vu.element(p) = true; 00153 } 00154 } 00155 00156 // Second Pass. 00157 { 00158 for (unsigned i = 0; i < n_points; ++i) // Forward. 00159 { 00160 unsigned p = s[i]; 00161 if (! f.handles_(p)) 00162 continue; 00163 00164 if (parent.element(p) == p) // if p is root 00165 { 00166 if (f.labels_(p)) 00167 { 00168 if (nlabels == mln_max(L)) 00169 { 00170 status = false; 00171 trace::warning("labeling aborted! Too many labels \ 00172 for this label type: nlabels > \ 00173 max(label_type)."); 00174 return output; 00175 } 00176 output.element(p) = ++nlabels; 00177 } 00178 } 00179 else 00180 output.element(p) = output.element(parent.element(p)); 00181 } 00182 status = true; 00183 } 00184 00185 trace::exiting("canvas::impl::labeling::sorted_fastest"); 00186 return output; 00187 } 00188 00189 } // end of namespace mln::canvas::impl 00190 00191 00192 // Dispatch. 00193 00194 namespace internal 00195 { 00196 00197 template <typename I, typename N, typename L, typename F> 00198 inline 00199 mln_ch_value(I, L) 00200 sorted_dispatch(metal::false_, 00201 const Image<I>& input, 00202 const Neighborhood<N>& nbh, L& nlabels, 00203 F& functor, bool increasing) 00204 { 00205 p_array<mln_psite(I)> s = 00206 increasing ? 00207 data::sort_psites_increasing(input) : 00208 data::sort_psites_decreasing(input); 00209 return impl::generic::labeling(input, nbh, nlabels, s, 00210 functor); 00211 } 00212 00213 template <typename I, typename N, typename L, typename F> 00214 inline 00215 mln_ch_value(I, L) 00216 sorted_dispatch(metal::true_, 00217 const Image<I>& input, 00218 const Neighborhood<N>& nbh, L& nlabels, 00219 F& functor, bool increasing) 00220 { 00221 util::array<unsigned> s = 00222 increasing ? 00223 data::sort_offsets_increasing(input) : 00224 data::sort_offsets_decreasing(input); 00225 return impl::sorted_fastest(input, nbh, nlabels, s, 00226 functor); 00227 } 00228 00229 template <typename I, typename N, typename L, typename F> 00230 inline 00231 mln_ch_value(I, L) 00232 sorted_dispatch(const Image<I>& input, 00233 const Neighborhood<N>& nbh, L& nlabels, 00234 F& functor, bool increasing) 00235 { 00236 enum { 00237 test = mlc_equal(mln_trait_image_speed(I), 00238 trait::image::speed::fastest)::value 00239 && 00240 mln_is_simple_neighborhood(N)::value 00241 }; 00242 return sorted_dispatch(metal::bool_<test>(), 00243 input, nbh, nlabels, 00244 functor, increasing); 00245 } 00246 00247 00248 } // end of namespace mln::canvas::internal 00249 00250 00251 00252 // Facades. 00253 00254 00255 template <typename I, typename N, typename L, typename F> 00256 inline 00257 mln_ch_value(I, L) 00258 sorted(const Image<I>& input, const Neighborhood<N>& nbh, 00259 L& nlabels, F& functor, bool increasing) 00260 { 00261 trace::entering("canvas::labeling::sorted"); 00262 00263 internal::labeling_tests(input, nbh, nlabels, functor); 00264 00265 mln_ch_value(I, L) output; 00266 output = internal::sorted_dispatch(input, nbh, nlabels, 00267 functor, increasing); 00268 00269 trace::exiting("canvas::labeling::sorted"); 00270 return output; 00271 } 00272 00273 00274 # endif // ! MLN_INCLUDE_ONLY 00275 00276 } // end of namespace mln::canvas::labeling 00277 00278 } // end of namespace mln::canvas 00279 00280 } // end of namespace mln 00281 00282 00283 #endif // ! MLN_CANVAS_LABELING_SORTED_HH