A.I.M.S algorithms


bucketblob_d.h
Go to the documentation of this file.
1 /* This software and supporting documentation are distributed by
2  * Institut Federatif de Recherche 49
3  * CEA/NeuroSpin, Batiment 145,
4  * 91191 Gif-sur-Yvette cedex
5  * France
6  *
7  * This software is governed by the CeCILL-B license under
8  * French law and abiding by the rules of distribution of free software.
9  * You can use, modify and/or redistribute the software under the
10  * terms of the CeCILL-B license as circulated by CEA, CNRS
11  * and INRIA at the following URL "http://www.cecill.info".
12  *
13  * As a counterpart to the access to the source code and rights to copy,
14  * modify and redistribute granted by the license, users are provided only
15  * with a limited warranty and the software's author, the holder of the
16  * economic rights, and the successive licensors have only limited
17  * liability.
18  *
19  * In this respect, the user's attention is drawn to the risks associated
20  * with loading, using, modifying and/or developing or reproducing the
21  * software by the user in light of its specific status of free software,
22  * that may mean that it is complicated to manipulate, and that also
23  * therefore means that it is reserved for developers and experienced
24  * professionals having in-depth computer knowledge. Users are therefore
25  * encouraged to load and test the software's suitability as regards their
26  * requirements in conditions enabling the security of their systems and/or
27  * data to be ensured and, more generally, to use and operate it in the
28  * same conditions as regards security.
29  *
30  * The fact that you are presently reading this means that you have had
31  * knowledge of the CeCILL-B license and that you accept its terms.
32  */
33 
34 
35 #ifndef AIMS_SCALESPACE_BUCKETBLOB_D_H
36 #define AIMS_SCALESPACE_BUCKETBLOB_D_H
37 
39 
40 namespace aims
41 {
42 
43  template <typename T>
45  bool keepallblobs,
46  BlobsMerger* m )
47  : _stop( sc ), _merger( m ), _minima( minima ),
48  _keepallblobs( keepallblobs ),
49  _connectivity( Connectivity::CONNECTIVITY_6_XYZ )
50  {
51  if( !m )
52  _merger = new BlobsMerger;
53  }
54 
55 
56  template <typename T>
58  {
59  delete _stop;
60  delete _merger;
61  }
62 
63 
64  template <typename T>
65  void BucketBlobExtractor<T>::neighborBlobs( std::set<int> & blobs,
66  const Point3d & p,
67  const BlobStruct & bs )
68  {
69  BucketMap<Void>::const_iterator ib, eb = bs.blobs->end();
70  Connectivity c( 0, 0, _connectivity );
71  int i, n = c.nbNeighbors(), b;
72  std::map<int, int>::const_iterator im, em = bs.mergemap.end();
73  std::set<int>::iterator notdone = blobs.end();
74  std::map<int, Point3d>::const_iterator notdead = bs.deadblobs.end();
75 
76  for( ib=bs.blobs->begin(); ib!=eb; ++ib )
77  {
78  b = ib->first;
79  for( im=bs.mergemap.find( b ); im!=em; im=bs.mergemap.find( b ) )
80  b = im->second;
81  if( bs.deadblobs.find( b ) == notdead && blobs.find( b ) == notdone )
82  for( i=0; i<n; ++i )
83  if( ib->second.find( p + c.xyzOffset(i) ) != ib->second.end() )
84  {
85  blobs.insert( ib->first );
86  break;
87  }
88  }
89  }
90 
91 
92  template <typename T>
95  {
96  BlobStruct bs;
97  bs.keepallblobs = _keepallblobs;
98  bs.blobs = new BucketMap<Void>;
99  bs.blobs->setSizeXYZT( valuemap.sizeX(), valuemap.sizeY(),
100  valuemap.sizeZ(), valuemap.sizeT() );
101 
102  // re-order voxels in increasing/decreasing value
103  std::multimap<T, Point3d> orderedb;
104  const typename BucketMap<T>::Bucket & bk = valuemap.begin()->second;
105  typename BucketMap<T>::Bucket::const_iterator ibk, ebk = bk.end();
106  for( ibk=bk.begin(); ibk!=ebk; ++ibk )
107  orderedb.insert( std::pair<T, Point3d>( ibk->second, ibk->first ) );
108 
109  typename std::multimap<T, Point3d>::iterator im, em = orderedb.end();
110  for( im=orderedb.begin(); im!=em; ++im )
111  {
112  const Point3d & p = im->second;
113  std::set<int> blobs;
114  neighborBlobs( blobs, p, bs );
115  switch( blobs.size() )
116  {
117  case 0: // new blob
118  (*bs.blobs)[ bs.newblobnum ][ p ] = Void();
119  ++bs.newblobnum;
120  break;
121  case 1: // inside a blob
122  (*bs.blobs)[ *blobs.begin() ][ p ] = Void();
123  break;
124  default: // blobs merge
125  _merger->merge( blobs, bs, p );
126  }
127  if( _stop->stops( p, bs ) )
128  break;
129  }
130 
131  BucketMap<Void> *res = bs.blobs;
132  if( !_keepallblobs )
133  {
134  res = new BucketMap<Void>;
135  res->setSizeXYZT( valuemap.sizeX(), valuemap.sizeY(),
136  valuemap.sizeZ(), valuemap.sizeT() );
137  std::map<int, int> trans;
138  std::map<int, int>::const_iterator
139  im, em = bs.mergemap.end(), em2 = trans.end();
140  int b, nb = 0;
141  BucketMap<Void>::const_iterator ib, eb = bs.blobs->end();
142  for( ib=bs.blobs->begin(); ib!=eb; ++ib )
143  {
144  b = ib->first;
145  for( im=bs.mergemap.find( b ); im!=em; im=bs.mergemap.find( b ) )
146  b = im->second;
147  if( _stop->doesKeepBlob( b, bs ) )
148  {
149  im = trans.find( b );
150  if( im == em2 )
151  {
152  trans[b] = nb;
153  b = nb;
154  ++nb;
155  }
156  else
157  b = im->second;
158  (*res)[b].insert( ib->second.begin(), ib->second.end() );
159  }
160  }
161  delete bs.blobs;
162  }
163 
164  return res;
165  }
166 
167  //
168 
169  template <typename T>
171  ( const std::set<Point3d, BucketMapLess> & toJoin )
172  : StopCriterion(), pointsToJoin( toJoin ), mainblob( -1 )
173  {
174  }
175 
176 
177  template <typename T>
180  {
181  }
182 
183 
184  template <typename T>
186  ( const Point3d &, const BlobStruct & bs )
187  {
188  BucketMap<Void>::const_iterator ib, eb = bs.blobs->end();
189  std::set<Point3d, BucketMapLess> active = pointsToJoin;
190  std::set<Point3d, BucketMapLess>::iterator ip, ip2, ep = active.end();
191  std::map<int, int>::const_iterator im, em = bs.mergemap.end();
192  int comp = -1, c;
193  for( ib=bs.blobs->begin(); ib!=eb && !active.empty(); ++ib )
194  {
195  for( ip=active.begin(); ip!=ep; )
196  {
197  if( ib->second.find( *ip ) != ib->second.end() )
198  {
199  c = ib->first;
200  for( im=bs.mergemap.find( c ); im!=em; im=bs.mergemap.find( c ) )
201  c = im->second;
202  if( comp < 0 )
203  {
204  comp = c;
205  mainblob = c;
206  }
207  else if( c != comp )
208  {
209  return false;
210  }
211 
212  ip2 = ip;
213  ++ip;
214  active.erase( ip2 );
215  }
216  else
217  ++ip;
218  }
219  }
220  return active.empty();
221  }
222 
223 
224  template <typename T>
226  int blob, const BlobStruct & )
227  {
228  return blob == mainblob;
229  }
230 
231  //
232 
233  template <typename T>
235  {
236  }
237 
238 
239  template <typename T>
240  void BucketBlobExtractor<T>::BlobsMerger::merge( const std::set<int> & blobs,
241  BlobStruct & bs,
242  const Point3d & p )
243  {
244  std::set<int>::iterator i = blobs.begin(), e = blobs.end();
245  int b0 = *i;
246  if( bs.keepallblobs )
247  {
248  b0 = bs.newblobnum;
249  ++bs.newblobnum;
250  }
251  else
252  ++i;
253  for( ; i!=e; ++i )
254  bs.mergemap[*i] = b0;
255  (*bs.blobs)[b0][p] = Void();
256  }
257 
258  //
259 
260  template <typename T>
262  : BlobsMerger()
263  {
264  }
265 
266 
267  template <typename T>
269  {
270  }
271 
272 
273  template <typename T>
275  const std::set<int> & blobs, BlobStruct & bs, const Point3d & p )
276  {
277  std::set<int>::iterator i, e = blobs.end();
278  for( i=blobs.begin(); i!=e; ++i )
279  if( *i != bs.background )
280  bs.deadblobs[*i] = p;
281  (*bs.blobs)[bs.background][p] = Void();
282  }
283 
284 }
285 
286 #endif
287 
BucketBlobExtractor(StopCriterion *sc, bool minima, bool keepallblobs=false, BlobsMerger *m=0)
Definition: bucketblob_d.h:44
virtual void merge(const std::set< int > &tomerge, BlobStruct &bs, const Point3d &p)
Definition: bucketblob_d.h:240
virtual bool stops(const Point3d &, const BlobStruct &bs)
Definition: bucketblob_d.h:186
float sizeX() const
const Point3d & xyzOffset(int n) const
float sizeT() const
OneComponentStopCriterion(const std::set< Point3d, BucketMapLess > &toJoin)
Definition: bucketblob_d.h:171
std::map< Point3d, T, BucketMapLess > Bucket
float sizeZ() const
BucketMap< Void > * extractBlobs(const BucketMap< T > &valuemap)
Extracts blobs or watershed.
Definition: bucketblob_d.h:94
void setSizeXYZT(float sizex, float sizey, float sizez, float sizet)
void neighborBlobs(std::set< int > &, const Point3d &, const BlobStruct &)
Definition: bucketblob_d.h:65
std::map< int, Point3d > deadblobs
Definition: bucketblob.h:59
virtual bool doesKeepBlob(int blob, const BlobStruct &)
Definition: bucketblob_d.h:225
int nbNeighbors() const
float sizeY() const
virtual void merge(const std::set< int > &tomerge, BlobStruct &bs, const Point3d &p)
Definition: bucketblob_d.h:274