36 #ifndef VIGRA_SLIC_HXX
37 #define VIGRA_SLIC_HXX
39 #include "multi_array.hxx"
40 #include "multi_convolution.hxx"
41 #include "multi_labeling.hxx"
42 #include "numerictraits.hxx"
43 #include "accumulator.hxx"
44 #include "array_vector.hxx"
112 template <
unsigned int N,
class T,
class S1,
113 class Label,
class S2>
116 MultiArrayView<N, Label, S2> seeds,
117 unsigned int seedDist,
118 unsigned int searchRadius = 1)
120 typedef typename MultiArrayShape<N>::type Shape;
123 Shape shape(boundaryIndicatorImage.shape()),
124 seedShape(
floor(shape /
double(seedDist))),
125 offset((shape - (seedShape - Shape(1))*seedDist) / 2);
127 unsigned int label = 0;
128 MultiCoordinateIterator<N> iter(seedShape),
129 end = iter.getEndIterator();
130 for(; iter != end; ++iter)
133 Shape center = (*iter)*seedDist + offset;
134 Shape startCoord = max(Shape(0), center-Shape(searchRadius));
135 Shape endCoord = min(center+Shape(searchRadius+1), shape);
139 AccumulatorChain<CoupledArrays<N, T>,
140 Select<WeightArg<1>, Coord<ArgMinWeight> > > a;
141 extractFeatures(boundaryIndicatorImage.subarray(startCoord, endCoord), a);
144 Shape minCoord = get<Coord<ArgMinWeight> >(a) + startCoord;
145 if(seeds[minCoord] == 0)
146 seeds[minCoord] = ++label;
191 unsigned int sizeLimit;
196 template <
unsigned int N,
class T,
class Label>
201 typedef MultiArrayView<N, T> DataImageType;
202 typedef MultiArrayView<N, Label> LabelImageType;
204 typedef typename PromoteTraits<
205 typename NormTraits<T>::NormType,
206 typename NormTraits<MultiArrayIndex>::NormType
207 >::Promote DistanceType;
209 Slic(DataImageType dataImage,
211 DistanceType intensityScaling,
213 SlicOptions
const & options = SlicOptions());
215 unsigned int execute();
218 void updateAssigments();
219 unsigned int postProcessing();
221 typedef MultiArray<N,DistanceType> DistanceImageType;
224 DataImageType dataImage_;
225 LabelImageType labelImage_;
226 DistanceImageType distance_;
228 DistanceType normalization_;
229 SlicOptions options_;
232 typedef acc::AccumulatorChainArray<CoupledArrays<N, T, Label>, Statistics> RegionFeatures;
233 RegionFeatures clusters_;
238 template <
unsigned int N,
class T,
class Label>
239 Slic<N, T, Label>::Slic(
240 DataImageType dataImage,
242 DistanceType intensityScaling,
244 SlicOptions
const & options)
245 : shape_(dataImage.shape()),
246 dataImage_(dataImage),
247 labelImage_(labelImage),
249 max_radius_(maxRadius),
250 normalization_(
sq(intensityScaling) /
sq(max_radius_)),
253 clusters_.ignoreLabel(0);
256 template <
unsigned int N,
class T,
class Label>
257 unsigned int Slic<N, T, Label>::execute()
260 for(
size_t i=0; i<options_.iter; ++i)
270 return postProcessing();
273 template <
unsigned int N,
class T,
class Label>
275 Slic<N, T, Label>::updateAssigments()
278 distance_.init(NumericTraits<DistanceType>::max());
279 for(
unsigned int c=1; c<=clusters_.maxRegionLabel(); ++c)
281 if(get<Count>(clusters_, c) == 0)
284 typedef typename LookupTag<RegionCenter, RegionFeatures>::value_type CenterType;
285 CenterType center = get<RegionCenter>(clusters_, c);
288 ShapeType pixelCenter(
round(center)),
289 startCoord(max(ShapeType(0), pixelCenter - ShapeType(max_radius_))),
290 endCoord(min(shape_, pixelCenter + ShapeType(max_radius_+1)));
291 center -= startCoord;
294 typedef typename CoupledArrays<N, T, Label, DistanceType>::IteratorType Iterator;
295 Iterator iter = createCoupledIterator(dataImage_, labelImage_, distance_).
296 restrictToSubarray(startCoord, endCoord),
297 end = iter.getEndIterator();
300 for(; iter != end; ++iter)
303 DistanceType spatialDist =
squaredNorm(center-iter.point());
304 DistanceType colorDist =
squaredNorm(get<Mean>(clusters_, c)-iter.template get<1>());
305 DistanceType dist = colorDist + normalization_*spatialDist;
307 if(dist < iter.template get<3>())
309 iter.template get<2>() = static_cast<Label>(c);
310 iter.template get<3>() = dist;
316 template <
unsigned int N,
class T,
class Label>
318 Slic<N, T, Label>::postProcessing()
321 MultiArray<N,Label> tmpLabelImage(labelImage_);
324 unsigned int sizeLimit = options_.sizeLimit == 0
325 ? (
unsigned int)(0.25 * labelImage_.size() / maxLabel)
326 : options_.sizeLimit;
332 AccumulatorChainArray<CoupledArrays<N, Label>, Select<LabelArg<1>,
Count> > sizes;
335 typedef GridGraph<N, undirected_tag> Graph;
338 typedef typename Graph::NodeIt graph_scanner;
339 typedef typename Graph::OutBackArcIt neighbor_iterator;
341 ArrayVector<Label> regions(maxLabel+1);
344 for (graph_scanner node(graph); node != lemon::INVALID; ++node)
346 Label label = labelImage_[*node];
348 if(regions[label] > 0)
351 regions[label] = label;
353 if(get<Count>(sizes, label) < sizeLimit)
356 for (neighbor_iterator arc(graph, node); arc != lemon::INVALID; ++arc)
358 regions[label] = regions[labelImage_[graph.target(*arc)]];
365 unsigned int newMaxLabel = 0;
366 for(
unsigned int i=1; i<=maxLabel; ++i)
370 regions[i] = (Label)++newMaxLabel;
374 regions[i] = regions[regions[i]];
379 for (graph_scanner node(graph); node != lemon::INVALID; ++node)
381 labelImage_[*node] = regions[labelImage_[*node]];
465 template <
unsigned int N,
class T,
class S1,
466 class Label,
class S2,
470 MultiArrayView<N, Label, S2> labels,
471 DistanceType intensityScaling,
472 unsigned int seedDistance,
473 SlicOptions
const & options = SlicOptions())
477 typedef typename NormTraits<T>::NormType TmpType;
478 MultiArray<N, TmpType> grad(src.shape());
482 return detail::Slic<N, T, Label>(src, labels, intensityScaling, seedDistance, options).execute();
489 #endif // VIGRA_SLIC_HXX