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

multi_localminmax.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2012-2013 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
37 #ifndef VIGRA_MULTI_LOCALMINMAX_HXX
38 #define VIGRA_MULTI_LOCALMINMAX_HXX
39
40 #include <vector>
41 #include <functional>
42 #include "multi_array.hxx"
43 #include "localminmax.hxx"
44 #include "multi_gridgraph.hxx"
45 #include "multi_labeling.hxx"
46 #include "metaprogramming.hxx"
47
48 namespace vigra {
49
50 namespace boost_graph {
51
52 // Attempt without LValue propmaps, using only the free functions
53 // to access ReadablePropertyMap (input) and WritablePropertyMap (label)
54 template <class Graph, class T1Map, class T2Map, class Compare>
55 unsigned int
56 localMinMaxGraph(Graph const &g,
57 T1Map const &src,
58 T2Map &dest,
59 typename property_traits<T2Map>::value_type marker,
60 typename property_traits<T1Map const>::value_type threshold,
61 Compare const &compare,
62 bool allowAtBorder = true)
63 {
64 typedef typename graph_traits<Graph>::vertex_iterator graph_scanner;
65 typedef typename graph_traits<Graph>::adjacency_iterator neighbor_iterator;
66
67 typedef typename property_traits<T1Map const>::value_type T1;
68
69 graph_scanner node, srcend;
70 neighbor_iterator arc, nbend;
71
72 unsigned int count = 0;
73 tie(node, srcend) = vertices(g);
74 for (; node != srcend; ++node)
75 {
76 const T1 current = get(src, *node);
77
78 if (!compare(current, threshold))
79 continue;
80
81 if(!allowAtBorder && node.atBorder())
82 continue;
83
84 tie(arc, nbend) = adjacent_vertices(*node, g);
85 for (;arc != nbend; ++arc)
86 if (!compare(current, get(src, *arc)))
87 break;
88
89 if (arc == nbend)
90 {
91 put(dest, *node, marker);
92 ++count;
93 }
94 }
95 return count;
96 }
97
98 } // namespace boost_graph
99
100 namespace lemon_graph {
101
102 template <class Graph, class T1Map, class T2Map, class Compare>
103 unsigned int
104 localMinMaxGraph(Graph const &g,
105 T1Map const &src,
106 T2Map &dest,
107 typename T2Map::value_type marker,
108 typename T1Map::value_type threshold,
109 Compare const &compare,
110 bool allowAtBorder = true)
111 {
112 typedef typename Graph::NodeIt graph_scanner;
113 typedef typename Graph::OutArcIt neighbor_iterator;
114
115 unsigned int count = 0;
116 for (graph_scanner node(g); node != INVALID; ++node)
117 {
118 typename T1Map::value_type current = src[*node];
119
120 if (!compare(current, threshold))
121 continue;
122
123 if(!allowAtBorder && node.atBorder())
124 continue;
125
126 neighbor_iterator arc(g, node);
127 for (; arc != INVALID; ++arc)
128 if (!compare(current, src[g.target(*arc)]))
129 break;
130
131 if (arc == INVALID)
132 {
133 dest[*node] = marker;
134 ++count;
135 }
136 }
137 return count;
138 }
139
140 template <class Graph, class T1Map, class T2Map, class Compare, class Equal>
141 unsigned int
142 extendedLocalMinMaxGraph(Graph const &g,
143 T1Map const &src,
144 T2Map &dest,
145 typename T2Map::value_type marker,
146 typename T1Map::value_type threshold,
147 Compare const &compare,
148 Equal const &equal,
149 bool allowAtBorder = true)
150 {
151 typename Graph::template NodeMap<unsigned int> regions(g);
152
153 int max_region_label = labelGraph(g, src, regions, equal);
154
155 // assume that a region is a extremum until the opposite is proved
156 std::vector<unsigned char> isExtremum(max_region_label+1, (unsigned char)1);
157
158 typedef typename Graph::NodeIt graph_scanner;
159 typedef typename Graph::OutArcIt neighbor_iterator;
160
161 unsigned int count = max_region_label;
162 for (graph_scanner node(g); node != INVALID; ++node)
163 {
164 unsigned int label = regions[*node];
165
166 if(!isExtremum[label])
167 continue;
168
169 typename T1Map::value_type current = src[*node];
170
171 if (!compare(current, threshold) ||
172 (!allowAtBorder && node.atBorder()))
173 {
174 isExtremum[label] = 0;
175 --count;
176 continue;
177 }
178
179 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
180 {
181 if (label != regions[g.target(*arc)] && compare(src[g.target(*arc)], current))
182 {
183 isExtremum[label] = 0;
184 --count;
185 break;
186 }
187 }
188 }
189 for (graph_scanner node(g); node != INVALID; ++node)
190 {
191 if(isExtremum[regions[*node]])
192 dest[*node] = marker;
193 }
194 return count;
195 }
196
197 } // namespace lemon_graph
198
199 template <unsigned int N, class T1, class C1,
200 class T2, class C2,
201 class Compare,
202 class EqualityFunctor>
203 unsigned int
204 localMinMax(MultiArrayView<N, T1, C1> const & src,
205 MultiArrayView<N, T2, C2> dest,
206 T1 threshold,
207 Compare const & compare,
208 EqualityFunctor const & equal,
209 LocalMinmaxOptions const & options = LocalMinmaxOptions())
210 {
211 vigra_precondition(src.shape() == dest.shape(),
212 "localMinMax(): shape mismatch between input and output.");
213
214 NeighborhoodType neighborhood = DirectNeighborhood;
215
216 if(options.neigh == 0 || options.neigh == 2*N)
217 neighborhood = DirectNeighborhood;
218 else if(options.neigh == 1 || options.neigh == MetaPow<3, N>::value - 1)
219 neighborhood = IndirectNeighborhood;
220 else
221 vigra_precondition(false,
222 "localMinMax(): option object specifies invalid neighborhood type.");
223
224 T2 marker = (T2)options.marker;
225
226 GridGraph<N, undirected_tag> graph(src.shape(), neighborhood);
227 if(options.allow_plateaus)
228 return lemon_graph::extendedLocalMinMaxGraph(graph, src, dest, marker, threshold,
229 compare, equal, options.allow_at_border);
230 else
231 return lemon_graph::localMinMaxGraph(graph, src, dest, marker, threshold,
232 compare, options.allow_at_border);
233 }
234
235 /********************************************************/
236 /* */
237 /* localMinima */
238 /* */
239 /********************************************************/
240
241 // documentation is in localminmax.hxx
242 template <unsigned int N, class T1, class C1, class T2, class C2>
243 inline unsigned int
244 localMinima(MultiArrayView<N, T1, C1> const & src,
245 MultiArrayView<N, T2, C2> dest,
246 LocalMinmaxOptions const & options = LocalMinmaxOptions())
247 {
248 T1 threshold = options.use_threshold
249 ? std::min(NumericTraits<T1>::max(), (T1)options.thresh)
250 : NumericTraits<T1>::max();
251 return localMinMax(src, dest, threshold, std::less<T1>(), std::equal_to<T1>(), options);
252 }
253
254
255 template <unsigned int N, class T1, class S1,
256 class T2, class S2,
257 class EqualityFunctor>
258 inline unsigned int
259 extendedLocalMinima(MultiArrayView<N, T1, S1> const & src,
260 MultiArrayView<N, T2, S2> dest,
261 EqualityFunctor const & equal,
262 LocalMinmaxOptions options = LocalMinmaxOptions())
263 {
264 options.allowPlateaus();
265 T1 threshold = options.use_threshold
266 ? std::min(NumericTraits<T1>::max(), (T1)options.thresh)
267 : NumericTraits<T1>::max();
268 return localMinMax(src, dest, threshold, std::less<T1>(), equal, options);
269 }
270 /********************************************************/
271 /* */
272 /* localMaxima */
273 /* */
274 /********************************************************/
275
276 // documentation is in localminmax.hxx
277 template <unsigned int N, class T1, class C1, class T2, class C2>
278 inline unsigned int
279 localMaxima(MultiArrayView<N, T1, C1> const & src,
280 MultiArrayView<N, T2, C2> dest,
281 LocalMinmaxOptions const & options = LocalMinmaxOptions())
282 {
283 T1 threshold = options.use_threshold
284 ? std::max(NumericTraits<T1>::min(), (T1)options.thresh)
285 : NumericTraits<T1>::min();
286 return localMinMax(src, dest, threshold, std::greater<T1>(), std::equal_to<T1>(), options);
287 }
288
289
290 template <unsigned int N, class T1, class S1,
291 class T2, class S2,
292 class EqualityFunctor>
293 inline unsigned int
294 extendedLocalMaxima(MultiArrayView<N, T1, S1> const & src,
295 MultiArrayView<N, T2, S2> dest,
296 EqualityFunctor const & equal,
297 LocalMinmaxOptions options = LocalMinmaxOptions())
298 {
299 options.allowPlateaus();
300 T1 threshold = options.use_threshold
301 ? std::max(NumericTraits<T1>::min(), (T1)options.thresh)
302 : NumericTraits<T1>::min();
303 return localMinMax(src, dest, threshold, std::greater<T1>(), equal, options);
304 }
305
306 } // namespace vigra
307
308 #endif // VIGRA_MULTI_LOCALMINMAX_HXX
boost::put
void put(vigra::MultiArrayView< N, T, Stride > &pmap, typename vigra::MultiArrayView< N, T, Stride >::difference_type const &k, U const &val)
Put value val at key k in the property map pmap (API: boost).
Definition: multi_gridgraph.hxx:2847
boost::adjacent_vertices
std::pair< typename vigra::GridGraph< N, DirectedTag >::adjacency_iterator, typename vigra::GridGraph< N, DirectedTag >::adjacency_iterator > adjacent_vertices(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the neighbor vertices of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2706
vigra::extendedLocalMinima
void extendedLocalMinima(...)
Find local minimal regions (plateaus) in an array.
vigra::localMinima
void localMinima(...)
Find local minima in an image or multi-dimensional array.
vigra
Definition: accessor.hxx:43
vigra::localMaxima
void localMaxima(...)
Find local maxima in an image or multi-dimensional array.
vigra::IndirectNeighborhood
use direct and indirect neighbors
Definition: multi_shape.hxx:254
vigra::extendedLocalMaxima
void extendedLocalMaxima(...)
Find local maximal regions in an array.
boost::vertices
std::pair< typename vigra::GridGraph< N, DirectedTag >::vertex_iterator, typename vigra::GridGraph< N, DirectedTag >::vertex_iterator > vertices(vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the vertices of graph g (API: boost).
Definition: multi_gridgraph.hxx:2683
vigra::DirectNeighborhood
use only direct neighbors
Definition: multi_shape.hxx:253
vigra::NeighborhoodType
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition: multi_shape.hxx:252

© 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.10.0