[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

skeleton.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2013-2014 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35
36 #ifndef VIGRA_SKELETON_HXX
37 #define VIGRA_SKELETON_HXX
38
39 #include <vector>
40 #include <set>
41 #include <map>
42 #include "vector_distance.hxx"
43 #include "iteratorfacade.hxx"
44 #include "pixelneighborhood.hxx"
45 #include "graph_algorithms.hxx"
46
47 namespace vigra
48 {
49
50 namespace detail {
51
52 template <class Node>
53 struct SkeletonNode
54 {
55 Node parent, principal_child;
56 double length, salience;
57 MultiArrayIndex partial_area;
58 bool is_loop;
59
60 SkeletonNode()
61 : parent(lemon::INVALID)
62 , principal_child(lemon::INVALID)
63 , length(0.0)
64 , salience(1.0)
65 , partial_area(0)
66 , is_loop(false)
67 {}
68
69 SkeletonNode(Node const & s)
70 : parent(s)
71 , principal_child(lemon::INVALID)
72 , length(0.0)
73 , salience(1.0)
74 , partial_area(0)
75 , is_loop(false)
76 {}
77 };
78
79 template <class Node>
80 struct SkeletonRegion
81 {
82 typedef SkeletonNode<Node> SNode;
83 typedef std::map<Node, SNode> Skeleton;
84
85 Node anchor, lower, upper;
86 Skeleton skeleton;
87
88 SkeletonRegion()
89 : anchor(lemon::INVALID)
90 , lower(NumericTraits<MultiArrayIndex>::max())
91 , upper(NumericTraits<MultiArrayIndex>::min())
92 {}
93
94 void addNode(Node const & n)
95 {
96 skeleton[n] = SNode(n);
97 anchor = n;
98 lower = min(lower, n);
99 upper = max(upper, n);
100 }
101 };
102
103 template <class Graph, class Node, class NodeMap>
104 inline unsigned int
105 neighborhoodConfiguration(Graph const & g, Node const & n, NodeMap const & labels)
106 {
107 typedef typename Graph::OutArcIt ArcIt;
108 typedef typename NodeMap::value_type LabelType;
109
110 LabelType label = labels[n];
111 unsigned int v = 0;
112 for(ArcIt arc(g, n); arc != lemon::INVALID; ++arc)
113 {
114 v = (v << 1) | (labels[g.target(*arc)] == label ? 1 : 0);
115 }
116 return v;
117 }
118
119 template <class Node, class Cost>
120 struct SkeletonSimplePoint
121 {
122 Node point;
123 Cost cost;
124
125 SkeletonSimplePoint(Node const & p, Cost c)
126 : point(p), cost(c)
127 {}
128
129 bool operator<(SkeletonSimplePoint const & o) const
130 {
131 return cost < o.cost;
132 }
133
134 bool operator>(SkeletonSimplePoint const & o) const
135 {
136 return cost > o.cost;
137 }
138 };
139
140 template <class CostMap, class LabelMap>
141 void
142 skeletonThinning(CostMap const & cost, LabelMap & labels,
143 bool preserve_endpoints=true)
144 {
145 typedef GridGraph<CostMap::actual_dimension> Graph;
146 typedef typename Graph::Node Node;
147 typedef typename Graph::NodeIt NodeIt;
148 typedef typename Graph::OutArcIt ArcIt;
149
150 Graph g(labels.shape(), IndirectNeighborhood);
151 typedef SkeletonSimplePoint<Node, double> SP;
152 // use std::greater because we need the smallest distances at the top of the queue
153 // (std::priority_queue is a max queue by default)
154 std::priority_queue<SP, std::vector<SP>, std::greater<SP> > pqueue;
155
156 bool isSimpleStrong[256] = {
157 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1,
158 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
159 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
160 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0,
161 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1,
162 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
163 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
164 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
165 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1,
166 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
167 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0,
168 };
169
170 bool isSimplePreserveEndPoints[256] = {
171 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
172 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1,
173 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
174 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
175 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
176 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
177 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
178 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
179 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
180 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0,
181 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
182 };
183
184 bool * isSimplePoint = preserve_endpoints
185 ? isSimplePreserveEndPoints
186 : isSimpleStrong;
187
188 int max_degree = g.maxDegree();
189 double epsilon = 0.5/labels.size(), offset = 0;
190 for (NodeIt node(g); node != lemon::INVALID; ++node)
191 {
192 Node p = *node;
193 if(g.out_degree(p) == max_degree &&
194 labels[p] > 0 &&
195 isSimplePoint[neighborhoodConfiguration(g, p, labels)])
196 {
197 // add an offset to break ties in a FIFI manner
198 pqueue.push(SP(p, cost[p]+offset));
199 offset += epsilon;
200 }
201 }
202
203 while(pqueue.size())
204 {
205 Node p = pqueue.top().point;
206 pqueue.pop();
207
208 if(labels[p] == 0 ||
209 !isSimplePoint[neighborhoodConfiguration(g, p, labels)])
210 {
211 continue; // point already deleted or no longer simple
212 }
213
214 labels[p] = 0; // delete simple point
215
216 for (ArcIt arc(g, p); arc != lemon::INVALID; ++arc)
217 {
218 Node q = g.target(*arc);
219 if(g.out_degree(q) == max_degree &&
220 labels[q] > 0 &&
221 isSimplePoint[neighborhoodConfiguration(g, q, labels)])
222 {
223 pqueue.push(SP(q, cost[q]+offset));
224 offset += epsilon;
225 }
226 }
227 }
228 }
229
230 template <class Label, class Labels>
231 struct CheckForHole
232 {
233 Label label;
234 Labels const & labels;
235
236 CheckForHole(Label l, Labels const & ls)
237 : label(l)
238 , labels(ls)
239 {}
240
241 template <class Node>
242 bool operator()(Node const & n) const
243 {
244 return labels[n] == label;
245 }
246 };
247
248 } // namespace detail
249
250 /** \addtogroup DistanceTransform
251 */
252 //@{
253
254 /** \brief Option object for \ref skeletonizeImage()
255 */
256 struct SkeletonOptions
257 {
258 enum SkeletonMode {
259 DontPrune = 0,
260 Prune = 1,
261 Relative = 2,
262 PreserveTopology = 4,
263 Length = 8,
264 Salience = 16,
265 PruneCenterLine = 32,
266 PruneLength = Length + Prune,
267 PruneLengthRelative = PruneLength + Relative,
268 PruneSalience = Salience + Prune,
269 PruneSalienceRelative = PruneSalience + Relative,
270 PruneTopology = PreserveTopology + Prune
271 };
272
273 SkeletonMode mode;
274 double pruning_threshold;
275
276 /** \brief construct with default settings
277
278 (default: <tt>pruneSalienceRelative(0.2, true)</tt>)
279 */
280 SkeletonOptions()
281 : mode(SkeletonMode(PruneSalienceRelative | PreserveTopology))
282 , pruning_threshold(0.2)
283 {}
284
285 /** \brief return the un-pruned skeletong
286 */
287 SkeletonOptions & dontPrune()
288 {
289 mode = DontPrune;
290 return *this;
291 }
292
293 /** \brief return only the region's center line (i.e. skeleton graph diameter)
294 */
295 SkeletonOptions & pruneCenterLine()
296 {
297 mode = PruneCenterLine;
298 return *this;
299 }
300
301 /** \brief Don't prune and return the length of each skeleton segment.
302 */
303 SkeletonOptions & returnLength()
304 {
305 mode = Length;
306 return *this;
307 }
308
309 /** \brief prune skeleton segments whose length is below the given threshold
310
311 If \a preserve_topology is <tt>true</tt> (default), skeleton loops
312 (i.e. parts enclosing a hole in the region) are preserved even if their
313 length is below the threshold. Otherwise, loops are pruned as well.
314 */
315 SkeletonOptions & pruneLength(double threshold, bool preserve_topology=true)
316 {
317 mode = PruneLength;
318 if(preserve_topology)
319 mode = SkeletonMode(mode | PreserveTopology);
320 pruning_threshold = threshold;
321 return *this;
322 }
323
324 /** \brief prune skeleton segments whose relative length is below the given threshold
325
326 This works like <tt>pruneLength()</tt>, but the threshold is specified as a
327 fraction of the maximum segment length in the skeleton.
328 */
329 SkeletonOptions & pruneLengthRelative(double threshold, bool preserve_topology=true)
330 {
331 mode = PruneLengthRelative;
332 if(preserve_topology)
333 mode = SkeletonMode(mode | PreserveTopology);
334 pruning_threshold = threshold;
335 return *this;
336 }
337
338 /** \brief Don't prune and return the salience of each skeleton segment.
339 */
340 SkeletonOptions & returnSalience()
341 {
342 mode = Salience;
343 return *this;
344 }
345
346 /** \brief prune skeleton segments whose salience is below the given threshold
347
348 If \a preserve_topology is <tt>true</tt> (default), skeleton loops
349 (i.e. parts enclosing a hole in the region) are preserved even if their
350 salience is below the threshold. Otherwise, loops are pruned as well.
351 */
352 SkeletonOptions & pruneSalience(double threshold, bool preserve_topology=true)
353 {
354 mode = PruneSalience;
355 if(preserve_topology)
356 mode = SkeletonMode(mode | PreserveTopology);
357 pruning_threshold = threshold;
358 return *this;
359 }
360
361 /** \brief prune skeleton segments whose relative salience is below the given threshold
362
363 This works like <tt>pruneSalience()</tt>, but the threshold is specified as a
364 fraction of the maximum segment salience in the skeleton.
365 */
366 SkeletonOptions & pruneSalienceRelative(double threshold, bool preserve_topology=true)
367 {
368 mode = PruneSalienceRelative;
369 if(preserve_topology)
370 mode = SkeletonMode(mode | PreserveTopology);
371 pruning_threshold = threshold;
372 return *this;
373 }
374
375 /** \brief prune such that only the topology is preserved
376
377 If \a preserve_center is <tt>true</tt> (default), the eccentricity center
378 of the skeleton will not be pruned, even if it is not essential for the topology.
379 Otherwise, the center is only preserved if it is essential. The center is always
380 preserved (and is the only remaining point) when the region has no holes.
381 */
382 SkeletonOptions & pruneTopology(bool preserve_center=true)
383 {
384 if(preserve_center)
385 mode = PruneTopology;
386 else
387 mode = Prune;
388 return *this;
389 }
390 };
391
392 template <class T1, class S1,
393 class T2, class S2,
394 class ArrayLike>
395 void
396 skeletonizeImageImpl(MultiArrayView<2, T1, S1> const & labels,
397 MultiArrayView<2, T2, S2> dest,
398 ArrayLike * features,
399 SkeletonOptions const & options)
400 {
401 static const unsigned int N = 2;
402 typedef typename MultiArrayShape<N>::type Shape;
403 typedef GridGraph<N> Graph;
404 typedef typename Graph::Node Node;
405 typedef typename Graph::NodeIt NodeIt;
406 typedef typename Graph::EdgeIt EdgeIt;
407 typedef typename Graph::OutArcIt ArcIt;
408 typedef typename Graph::OutBackArcIt BackArcIt;
409 typedef double WeightType;
410 typedef detail::SkeletonNode<Node> SNode;
411 typedef std::map<Node, SNode> Skeleton;
412
413 vigra_precondition(labels.shape() == dest.shape(),
414 "skeleton(): shape mismatch between input and output.");
415
416 MultiArray<N, MultiArrayIndex> squared_distance;
417 dest = 0;
418 T1 maxLabel = 0;
419 // find skeleton points
420 {
421 using namespace multi_math;
422
423 MultiArray<N, Shape> vectors(labels.shape());
424 boundaryVectorDistance(labels, vectors, false, OuterBoundary);
425 squared_distance = squaredNorm(vectors);
426
427 ArrayVector<Node> ends_to_be_checked;
428 Graph g(labels.shape());
429 for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
430 {
431 Node p1 = g.u(*edge),
432 p2 = g.v(*edge);
433 T1 l1 = labels[p1],
434 l2 = labels[p2];
435 maxLabel = max(maxLabel, max(l1, l2));
436 if(l1 == l2)
437 {
438 if(l1 <= 0) // only consider positive labels
439 continue;
440
441 const Node v1 = vectors[p1],
442 v2 = vectors[p2],
443 dp = p2 - p1,
444 dv = v2 - v1 + dp;
445 if(max(abs(dv)) <= 1) // points whose support points coincide or are adjacent
446 continue; // don't belong to the skeleton
447
448 // among p1 and p2, the point which is closer to the bisector
449 // of the support points p1 + v1 and p2 + v2 belongs to the skeleton
450 const MultiArrayIndex d1 = dot(dv, dp),
451 d2 = dot(dv, v1+v2);
452 if(d1*d2 <= 0)
453 {
454 dest[p1] = l1;
455 if(squared_distance[p1] == 4)
456 ends_to_be_checked.push_back(p1);
457 }
458 else
459 {
460 dest[p2] = l2;
461 if(squared_distance[p2] == 4)
462 ends_to_be_checked.push_back(p2);
463 }
464 }
465 else
466 {
467 if(l1 > 0 && max(abs(vectors[p1] + p1 - p2)) > 1)
468 dest[p1] = l1;
469 if(l2 > 0 && max(abs(vectors[p2] + p2 - p1)) > 1)
470 dest[p2] = l2;
471 }
472 }
473
474
475 // add a point when a skeleton line stops short of the shape boundary
476 // FIXME: can this be solved during the initial detection above?
477 Graph g8(labels.shape(), IndirectNeighborhood);
478 for (unsigned k=0; k<ends_to_be_checked.size(); ++k)
479 {
480 // The phenomenon only occurs at points whose distance from the background is 2.
481 // We've put these points into ends_to_be_checked.
482 Node p1 = ends_to_be_checked[k];
483 T2 label = dest[p1];
484 int count = 0;
485 for (ArcIt arc(g8, p1); arc != lemon::INVALID; ++arc)
486 {
487 Node p2 = g8.target(*arc);
488 if(dest[p2] == label && squared_distance[p2] < 4)
489 ++count;
490 }
491 if(count == 0) // point p1 has no neighbor at the boundary => activate one
492 dest[p1+vectors[p1]/2] = label;
493 }
494
495 // from here on, we only need the squared DT, not the vector DT
496 }
497
498 // The true skeleton is defined by the interpixel edges between the
499 // Voronoi regions of the DT. Our skeleton detection algorithm affectively
500 // rounds the interpixel edges to the nearest pixel such that the result
501 // is mainly 8-connected and thin. However, thick skeleton pieces may still
502 // arise when two interpixel contours are only one pixel apart, i.e. a
503 // Voronoi region is only one pixel wide. Since this happens rarely, we
504 // can simply remove these cases by thinning.
505 detail::skeletonThinning(squared_distance, dest);
506
507 if(options.mode == SkeletonOptions::PruneCenterLine)
508 dest = 0;
509
510 // Reduce the full grid graph to a skeleton graph by inserting infinite
511 // edge weights between skeleton pixels and non-skeleton pixels.
512 if(features)
513 features->resize((size_t)maxLabel + 1);
514 ArrayVector<detail::SkeletonRegion<Node> > regions((size_t)maxLabel + 1);
515 Graph g(labels.shape(), IndirectNeighborhood);
516 WeightType maxWeight = g.edgeNum()*sqrt(N),
517 infiniteWeight = 0.5*NumericTraits<WeightType>::max();
518 typename Graph::template EdgeMap<WeightType> weights(g);
519 for (NodeIt node(g); node != lemon::INVALID; ++node)
520 {
521 Node p1 = *node;
522 T2 label = dest[p1];
523 if(label <= 0)
524 continue;
525
526 // FIXME: consider using an AdjacencyListGraph from here on
527 regions[(size_t)label].addNode(p1);
528
529 for (ArcIt arc(g, p1); arc != lemon::INVALID; ++arc)
530 {
531 Node p2 = g.target(*arc);
532 if(dest[p2] == label)
533 weights[*arc] = norm(p1-p2);
534 else
535 weights[*arc] = infiniteWeight;
536 }
537 }
538
539 ShortestPathDijkstra<Graph, WeightType> pathFinder(g);
540 // Handle the skeleton of each region individually.
541 for(std::size_t label=1; label < regions.size(); ++label)
542 {
543 Skeleton & skeleton = regions[label].skeleton;
544 if(skeleton.size() == 0) // label doesn't exist
545 continue;
546
547 // Find a diameter (longest path) in the skeleton.
548 Node anchor = regions[label].anchor,
549 lower = regions[label].lower,
550 upper = regions[label].upper + Shape(1);
551
552 pathFinder.run(lower, upper, weights, anchor, lemon::INVALID, maxWeight);
553 anchor = pathFinder.target();
554 pathFinder.reRun(weights, anchor, lemon::INVALID, maxWeight);
555 anchor = pathFinder.target();
556
557 Polygon<Shape> center_line;
558 center_line.push_back_unsafe(anchor);
559 while(pathFinder.predecessors()[center_line.back()] != center_line.back())
560 center_line.push_back_unsafe(pathFinder.predecessors()[center_line.back()]);
561
562 if(options.mode == SkeletonOptions::PruneCenterLine)
563 {
564 for(unsigned int k=0; k<center_line.size(); ++k)
565 dest[center_line[k]] = (T2)label;
566 continue; // to next label
567 }
568
569 // Perform the eccentricity transform of the skeleton
570 Node center = center_line[roundi(center_line.arcLengthQuantile(0.5))];
571 pathFinder.reRun(weights, center, lemon::INVALID, maxWeight);
572
573 bool compute_salience = (options.mode & SkeletonOptions::Salience) != 0;
574 ArrayVector<Node> raw_skeleton(pathFinder.discoveryOrder());
575 // from periphery to center: create skeleton tree and compute salience
576 for(int k=raw_skeleton.size()-1; k >= 0; --k)
577 {
578 Node p1 = raw_skeleton[k],
579 p2 = pathFinder.predecessors()[p1];
580 SNode & n1 = skeleton[p1];
581 SNode & n2 = skeleton[p2];
582 n1.parent = p2;
583
584
585 // remove non-skeleton edges (i.e. set weight = infiniteWeight)
586 for (BackArcIt arc(g, p1); arc != lemon::INVALID; ++arc)
587 {
588 Node p = g.target(*arc);
589 if(weights[*arc] == infiniteWeight)
590 continue; // edge never was in the graph
591 if(p == p2)
592 continue; // edge belongs to the skeleton
593 if(pathFinder.predecessors()[p] == p1)
594 continue; // edge belongs to the skeleton
595 if(n1.principal_child == lemon::INVALID ||
596 skeleton[p].principal_child == lemon::INVALID)
597 continue; // edge may belong to a loop => test later
598 weights[*arc] = infiniteWeight;
599 }
600
601 // propagate length to parent if this is the longest subtree
602 WeightType l = n1.length + norm(p1-p2);
603 if(n2.length < l)
604 {
605 n2.length = l;
606 n2.principal_child = p1;
607 }
608
609 if(compute_salience)
610 {
611 const double min_length = 4.0; // salience is meaningless for shorter segments due
612 // to quantization noise (staircasing) of the boundary
613 if(n1.length >= min_length)
614 {
615 n1.salience = max(n1.salience, (n1.length + 0.5) / sqrt(squared_distance[p1]));
616
617 // propagate salience to parent if this is the most salient subtree
618 if(n2.salience < n1.salience)
619 n2.salience = n1.salience;
620 }
621 }
622 else if(options.mode == SkeletonOptions::DontPrune)
623 n1.salience = dest[p1];
624 else
625 n1.salience = n1.length;
626 }
627
628 // from center to periphery: propagate salience and compute twice the partial area
629 for(int k=0; k < (int)raw_skeleton.size(); ++k)
630 {
631 Node p1 = raw_skeleton[k];
632 SNode & n1 = skeleton[p1];
633 Node p2 = n1.parent;
634 SNode & n2 = skeleton[p2];
635
636 if(p1 == n2.principal_child)
637 {
638 n1.length = n2.length;
639 n1.salience = n2.salience;
640 }
641 else
642 {
643 n1.length += norm(p2-p1);
644 }
645 n1.partial_area = n2.partial_area + (p1[0]*p2[1] - p1[1]*p2[0]);
646 }
647
648 // always treat eccentricity center as a loop, so that it cannot be pruned
649 // away unless (options.mode & PreserveTopology) is false.
650 skeleton[center].is_loop = true;
651
652 // from periphery to center: * find and propagate loops
653 // * delete branches not reaching the boundary
654 detail::CheckForHole<std::size_t, MultiArrayView<2, T1, S1> > hasNoHole(label, labels);
655 int hole_count = 0;
656 double total_length = 0.0;
657 for(int k=raw_skeleton.size()-1; k >= 0; --k)
658 {
659 Node p1 = raw_skeleton[k];
660 SNode & n1 = skeleton[p1];
661
662 if(n1.principal_child == lemon::INVALID)
663 {
664 for (ArcIt arc(g, p1); arc != lemon::INVALID; ++arc)
665 {
666 Node p2 = g.target(*arc);
667 SNode * n2 = &skeleton[p2];
668
669 if(n1.parent == p2)
670 continue; // going back to the parent can't result in a loop
671 if(weights[*arc] == infiniteWeight)
672 continue; // p2 is not in the tree or the loop has already been handled
673 // compute twice the area exclosed by the potential loop
674 MultiArrayIndex area2 = abs(n1.partial_area - (p1[0]*p2[1] - p1[1]*p2[0]) - n2->partial_area);
675 if(area2 <= 3) // area is too small to enclose a hole => loop is a discretization artifact
676 continue;
677
678 // use Dijkstra to find the loop
679 weights[*arc] = infiniteWeight;
680 pathFinder.reRun(weights, p1, p2);
681 Polygon<Shape2> poly;
682 {
683 poly.push_back_unsafe(p1);
684 poly.push_back_unsafe(p2);
685 Node p = p2;
686 do
687 {
688 p = pathFinder.predecessors()[p];
689 poly.push_back_unsafe(p);
690 }
691 while(p != pathFinder.predecessors()[p]);
692 }
693 // check if the loop contains a hole or is just a discretization artifact
694 if(!inspectPolygon(poly, hasNoHole))
695 {
696 // it's a genuine loop => mark it and propagate salience
697 ++hole_count;
698 total_length += n1.length + n2->length;
699 double max_salience = max(n1.salience, n2->salience);
700 for(decltype(poly.size()) p=1; p<poly.size(); ++p)
701 {
702 SNode & n = skeleton[poly[p]];
703 n.is_loop = true;
704 n.salience = max(n.salience, max_salience);
705 }
706 }
707 }
708 // delete skeleton branches that are not loops and don't reach the shape border
709 // (these branches are discretization artifacts)
710 if(!n1.is_loop && squared_distance[p1] >= 4)
711 {
712 SNode * n = &n1;
713 while(true)
714 {
715 n->salience = 0;
716 // remove all of p1's edges
717 for(ArcIt arc(g, p1); arc != lemon::INVALID; ++arc)
718 {
719 weights[*arc] = infiniteWeight;
720 }
721 if(skeleton[n->parent].principal_child != p1)
722 break;
723 p1 = n->parent;
724 n = &skeleton[p1];
725 }
726 }
727 }
728
729 if(n1.is_loop)
730 skeleton[n1.parent].is_loop = true;
731 }
732
733 bool dont_prune = (options.mode & SkeletonOptions::Prune) == 0;
734 bool preserve_topology = (options.mode & SkeletonOptions::PreserveTopology) != 0 ||
735 options.mode == SkeletonOptions::Prune;
736 bool relative_pruning = (options.mode & SkeletonOptions::Relative) != 0;
737 WeightType threshold = (options.mode == SkeletonOptions::PruneTopology ||
738 options.mode == SkeletonOptions::Prune)
739 ? infiniteWeight
740 : relative_pruning
741 ? options.pruning_threshold*skeleton[center].salience
742 : options.pruning_threshold;
743 // from center to periphery: write result
744 int branch_count = 0;
745 double average_length = 0;
746 for(int k=0; k < (int)raw_skeleton.size(); ++k)
747 {
748 Node p1 = raw_skeleton[k];
749 SNode & n1 = skeleton[p1];
750 Node p2 = n1.parent;
751 if(n1.principal_child == lemon::INVALID &&
752 n1.salience >= threshold &&
753 !n1.is_loop)
754 {
755 ++branch_count;
756 average_length += n1.length;
757 total_length += n1.length;
758 }
759 if(dont_prune)
760 dest[p1] = n1.salience;
761 else if(preserve_topology)
762 {
763 if(!n1.is_loop && n1.salience < threshold)
764 dest[p1] = 0;
765 }
766 else if(p1 != center && n1.salience < threshold)
767 dest[p1] = 0;
768 }
769 if(branch_count > 0)
770 average_length /= branch_count;
771
772 if(features)
773 {
774 (*features)[label].diameter = center_line.length();
775 (*features)[label].total_length = total_length;
776 (*features)[label].average_length = average_length;
777 (*features)[label].branch_count = branch_count;
778 (*features)[label].hole_count = hole_count;
779 (*features)[label].center = center;
780 (*features)[label].terminal1 = center_line.front();
781 (*features)[label].terminal2 = center_line.back();
782 (*features)[label].euclidean_diameter = norm(center_line.back()-center_line.front());
783 }
784 }
785
786 if(options.mode == SkeletonOptions::Prune)
787 detail::skeletonThinning(squared_distance, dest, false);
788 }
789
790 class SkeletonFeatures
791 {
792 public:
793 double diameter, total_length, average_length, euclidean_diameter;
794 UInt32 branch_count, hole_count;
795 Shape2 center, terminal1, terminal2;
796
797 SkeletonFeatures()
798 : diameter(0)
799 , total_length(0)
800 , average_length(0)
801 , euclidean_diameter(0)
802 , branch_count(0)
803 , hole_count(0)
804 {}
805 };
806
807 /********************************************************/
808 /* */
809 /* skeletonizeImage */
810 /* */
811 /********************************************************/
812
813 /*
814 To compute the skeleton reliably in higher dimensions, we have to work on
815 a topological grid. The tricks to work with rounded skeletons on the
816 pixel grid probably don't generalize from 2D to 3D and higher. Specifically:
817
818 * Compute Voronoi regions of the vector distance transformation according to
819 identical support point to make sure that disconnected Voronoi regions
820 still get only a single label.
821 * Merge Voronoi regions whose support points are adjacent.
822 * Mark skeleton candidates on the interpixel grid after the basic merge.
823 * Detect skeleton segments simply by connected components labeling in the interpixel grid.
824 * Skeleton segments form hyperplanes => use this property to compute segment
825 attributes.
826 * Detect holes (and therefore, skeleton segments that are critical for topology)
827 by computing the depth of each region/surface in the homotopy tree.
828 * Add a pruning mode where holes are only preserved if their size exceeds a threshold.
829
830 To implement this cleanly, we first need a good implementation of the topological grid graph.
831 */
832 // template <unsigned int N, class T1, class S1,
833 // class T2, class S2>
834 // void
835 // skeletonizeImage(MultiArrayView<N, T1, S1> const & labels,
836 // MultiArrayView<N, T2, S2> dest,
837 // SkeletonOptions const & options = SkeletonOptions())
838 // {
839
840 /** \brief Skeletonization of all regions in a labeled 2D image.
841
842 <b> Declarations:</b>
843
844 \code
845 namespace vigra {
846 template <class T1, class S1,
847 class T2, class S2>
848 void
849 skeletonizeImage(MultiArrayView<2, T1, S1> const & labels,
850 MultiArrayView<2, T2, S2> dest,
851 SkeletonOptions const & options = SkeletonOptions());
852 }
853 \endcode
854
855 This function computes the skeleton for each region in the 2D label image \a labels
856 and paints the results into the result image \a dest. Input label
857 <tt>0</tt> is interpreted as background and always ignored. Skeletons will be
858 marked with the same label as the corresponding region (unless options
859 <tt>returnLength()</tt> or <tt>returnSalience()</tt> are selected, see below).
860 Non-skeleton pixels will receive label <tt>0</tt>.
861
862 For each region, the algorithm proceeds in the following steps:
863 <ol>
864 <li>Compute the \ref boundaryVectorDistance() relative to the \ref OuterBoundary of the region.</li>
865 <li>Mark the raw skeleton: find 4-adjacent pixel pairs whose nearest boundary points are neither equal
866 nor adjacent and mark one pixel of the pair as a skeleton candidate. The resulting raw skeleton
867 is 8-connected and thin. Skip the remaining steps when option <tt>dontPrune()</tt> is selected.</li>
868 <li>Compute the eccentricity transform of the raw skeleton and turn the skeleton into a tree
869 whose root is the eccentricity center. When option <tt>pruneCenterLine()</tt> is selected,
870 delete all skeleton points that do not belong to the two longest tree branches and
871 skip the remaining steps.</li>
872 <li>For each pixel on the skeleton, compute its <tt>length</tt> attribute as the depth of the
873 pixel's longest subtree. Compute its <tt>salience</tt> attribute as the ratio between
874 <tt>length</tt> and <tt>distance</tt>, where <tt>distance</tt> is the pixel's distance to
875 the nearest boundary point according to the distance transform. It holds that <tt>length >= 0.5</tt>
876 and <tt>salience >= 1.0</tt>.</li>
877 <li>Detect skeleton branching points and define <i>skeleton segments</i> as maximal connected pieces
878 without branching points.</li>
879 <li>Compute <tt>length</tt> and <tt>salience</tt> of each segment as the maximum of these
880 attributes among the pixels in the segment. When options <tt>returnLength()</tt> or
881 <tt>returnSalience()</tt> are selected, skip the remaining steps and return the
882 requested segment attribute in <tt>dest</tt>. In this case, <tt>dest</tt>'s
883 <tt>value_type</tt> should be a floating point type to exactly accomodate the
884 attribute values.</li>
885 <li>Detect minimal cycles in the raw skeleton that enclose holes in the region (if any) and mark
886 the corresponding pixels as critical for skeleton topology.</li>
887 <li>Prune skeleton segments according to the selected pruning strategy and return the result.
888 The following pruning strategies are available:
889 <ul>
890 <li><tt>pruneLength(threshold, preserve_topology)</tt>: Retain only segments whose length attribute
891 exceeds the given <tt>threshold</tt>. When <tt>preserve_topology</tt> is true
892 (the defult), cycles around holes are preserved regardless of their length.
893 Otherwise, they are pruned as well.</li>
894 <li><tt>pruneLengthRelative(threshold, preserve_topology)</tt>: Like <tt>pruneLength()</tt>,
895 but the threshold is specified as a fraction of the maximum segment length in
896 the present region.</li>
897 <li><tt>pruneSalience(threshold, preserve_topology)</tt>: Retain only segments whose salience attribute
898 exceeds the given <tt>threshold</tt>. When <tt>preserve_topology</tt> is true
899 (the defult), cycles around holes are preserved regardless of their salience.
900 Otherwise, they are pruned as well.</li>
901 <li><tt>pruneSalienceRelative(threshold, preserve_topology)</tt>: Like <tt>pruneSalience()</tt>,
902 but the threshold is specified as a fraction of the maximum segment salience in
903 the present region.</li>
904 <li><tt>pruneTopology(preserve_center)</tt>: Retain only segments that are essential for the region's
905 topology. If <tt>preserve_center</tt> is true (the default), the eccentricity
906 center is also preserved, even if it is not essential. Otherwise, it might be
907 removed. The eccentricity center is always the only remaining point when
908 the region has no holes.</li>
909 </ul></li>
910 </ol>
911
912 The skeleton has the following properties:
913 <ul>
914 <li>It is 8-connected and thin (except when two independent branches happen to run alongside
915 before they divert). Skeleton points are defined by rounding the exact Euclidean skeleton
916 locations to the nearest pixel.</li>
917 <li>Skeleton branches terminate either at the region boundary or at a cycle. There are no branch
918 end points in the region interior.</li>
919 <li>The salience threshold acts as a scale parameter: Large thresholds only retain skeleton
920 branches characterizing the general region shape. When the threshold gets smaller, ever
921 more detailed boundary bulges will be represented by a skeleton branch.</li>
922 </ul>
923
924 Remark: If you have an application where a skeleton graph would be more useful
925 than a skeleton image, function <tt>skeletonizeImage()</tt> can be changed/extended easily.
926
927 <b> Usage:</b>
928
929 <b>\#include</b> <vigra/skeleton.hxx><br/>
930 Namespace: vigra
931
932 \code
933 Shape2 shape(width, height);
934 MultiArray<2, UInt32> source(shape);
935 MultiArray<2, UInt32> dest(shape);
936 ...
937
938 // Skeletonize and keep only those segments that are at least 10% of the maximum
939 // length (the maximum length is half the skeleton diameter).
940 skeletonizeImage(source, dest,
941 SkeletonOptions().pruneLengthRelative(0.1));
942 \endcode
943
944 \see vigra::boundaryVectorDistance()
945 */
946 doxygen_overloaded_function(template <...> void skeletonizeImage)
947
948 template <class T1, class S1,
949 class T2, class S2>
950 void
951 skeletonizeImage(MultiArrayView<2, T1, S1> const & labels,
952 MultiArrayView<2, T2, S2> dest,
953 SkeletonOptions const & options = SkeletonOptions())
954 {
955 skeletonizeImageImpl(labels, dest, (ArrayVector<SkeletonFeatures>*)0, options);
956 }
957
958 template <class T, class S>
959 void
960 extractSkeletonFeatures(MultiArrayView<2, T, S> const & labels,
961 ArrayVector<SkeletonFeatures> & features,
962 SkeletonOptions const & options = SkeletonOptions())
963 {
964 MultiArray<2, float> skeleton(labels.shape());
965 skeletonizeImageImpl(labels, skeleton, &features, options);
966 }
967
968 //@}
969
970 } //-- namespace vigra
971
972 #endif //-- VIGRA_SKELETON_HXX
vigra::UInt32
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
vigra::SkeletonOptions::pruneLengthRelative
SkeletonOptions & pruneLengthRelative(double threshold, bool preserve_topology=true)
prune skeleton segments whose relative length is below the given threshold
Definition: skeleton.hxx:329
vigra
vigra::doxygen_overloaded_function
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
vigra::sqrt
SquareRootTraits< FixedPoint< IntBits, FracBits > >::SquareRootResult sqrt(FixedPoint< IntBits, FracBits > v)
square root.
Definition: fixedpoint.hxx:616
vigra::operator>
bool operator>(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
greater
Definition: fixedpoint.hxx:530
vigra::SkeletonOptions::pruneSalienceRelative
SkeletonOptions & pruneSalienceRelative(double threshold, bool preserve_topology=true)
prune skeleton segments whose relative salience is below the given threshold
Definition: skeleton.hxx:366
vigra::SkeletonOptions::SkeletonOptions
SkeletonOptions()
construct with default settings
Definition: skeleton.hxx:280
vigra::SkeletonOptions
Option object for skeletonizeImage()
Definition: skeleton.hxx:256
vigra::squaredNorm
FFTWComplex< R >::SquaredNormType squaredNorm(const FFTWComplex< R > &a)
squared norm (= squared magnitude)
Definition: fftw3.hxx:1044
vigra::SkeletonOptions::dontPrune
SkeletonOptions & dontPrune()
return the un-pruned skeletong
Definition: skeleton.hxx:287
vigra::skeletonizeImage
void skeletonizeImage(...)
Skeletonization of all regions in a labeled 2D image.
vigra::SkeletonOptions::pruneSalience
SkeletonOptions & pruneSalience(double threshold, bool preserve_topology=true)
prune skeleton segments whose salience is below the given threshold
Definition: skeleton.hxx:352
vigra::roundi
Int32 roundi(FixedPoint16< IntBits, OverflowHandling > v)
rounding to the nearest integer.
Definition: fixedpoint.hxx:1775
vigra::OuterBoundary
Pixels just outside of each region.
Definition: multi_distance.hxx:836
vigra::IndirectNeighborhood
use direct and indirect neighbors
Definition: multi_fwd.hxx:188
vigra::SkeletonOptions::returnSalience
SkeletonOptions & returnSalience()
Don't prune and return the salience of each skeleton segment.
Definition: skeleton.hxx:340
vigra::SkeletonOptions::pruneLength
SkeletonOptions & pruneLength(double threshold, bool preserve_topology=true)
prune skeleton segments whose length is below the given threshold
Definition: skeleton.hxx:315
vigra::SkeletonOptions::pruneTopology
SkeletonOptions & pruneTopology(bool preserve_center=true)
prune such that only the topology is preserved
Definition: skeleton.hxx:382
vigra::boundaryVectorDistance
void boundaryVectorDistance(...)
Compute the vector distance transform to the implicit boundaries of a multi-dimensional label array.
vigra::SkeletonOptions::pruneCenterLine
SkeletonOptions & pruneCenterLine()
return only the region's center line (i.e. skeleton graph diameter)
Definition: skeleton.hxx:295
vigra::operator<
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition: fixedpoint.hxx:512
vigra::SkeletonOptions::returnLength
SkeletonOptions & returnLength()
Don't prune and return the length of each skeleton segment.
Definition: skeleton.hxx:303
vigra::MultiArrayIndex
std::ptrdiff_t MultiArrayIndex
Definition: multi_fwd.hxx:60
vigra::dot
PromoteTraits< V1, V2 >::Promote dot(RGBValue< V1, RIDX1, GIDX1, BIDX1 > const &r1, RGBValue< V2, RIDX2, GIDX2, BIDX2 > const &r2)
dot product
Definition: rgbvalue.hxx:906
vigra::abs
FFTWComplex< R >::NormType abs(const FFTWComplex< R > &a)
absolute value (= magnitude)
Definition: fftw3.hxx:1002
vigra::norm
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition: fftw3.hxx:1037
vigra::MultiArrayShape::type
TinyVector< MultiArrayIndex, N > type
Definition: multi_shape.hxx:272

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.11.1