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

multi_histogram.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2002-2003 by Ullrich Koethe, Hans Meine */
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_MULTI_HISTOGRAMM_HXX
37 #define VIGRA_MULTI_HISTOGRAMM_HXX
38
39 #include "multi_array.hxx"
40 #include "tinyvector.hxx"
41 #include "multi_gridgraph.hxx"
42 #include "multi_convolution.hxx"
43
44
45 namespace vigra{
46
47
48 template< unsigned int DIM , class T_DATA ,unsigned int CHANNELS, class T_HIST >
49 void multiGaussianHistogram(
50 const MultiArrayView<DIM, TinyVector<T_DATA,CHANNELS> > & image,
51 const TinyVector<T_DATA,CHANNELS> minVals,
52 const TinyVector<T_DATA,CHANNELS> maxVals,
53 const size_t bins,
54 const float sigma,
55 const float sigmaBin,
56 MultiArrayView<DIM+2 , T_HIST> histogram
57 ){
58 typedef vigra::GridGraph< DIM , undirected_tag> Graph;
59 typedef typename Graph::NodeIt graph_scanner;
60 typedef typename Graph::Node Node;
61 typedef T_HIST ValueType;
62 typedef TinyVector<ValueType,CHANNELS> ChannelsVals;
63 typedef typename MultiArrayView<DIM+2 , T_HIST>::difference_type HistCoord;
64 const Graph g(image.shape());
65 const ChannelsVals nBins(bins);
66 histogram.init(1.0);
67 // iterate over all nodes (i.e. pixels)
68 for (graph_scanner n(g); n != lemon::INVALID; ++n){
69 const Node node(*n);
70 ChannelsVals binIndex = image[node];
71 binIndex -=minVals;
72 binIndex /=maxVals;
73 binIndex *=nBins;
74 HistCoord histCoord;
75 for(size_t d=0;d<DIM;++d){
76 histCoord[d]=node[d];
77 }
78 for(size_t c=0;c<CHANNELS;++c){
79 const float fi = binIndex[c];
80 const size_t bi = std::floor(fi+0.5);
81 histCoord[DIM]=std::min(bi,static_cast<size_t>(bins-1));
82 histCoord[DIM+1]=c;
83 histogram[histCoord]+=1.0;
84 }
85 }
86
87 //MultiArray<DIM+2 , T_HIST> histogramBuffer(histogram);
88 Kernel1D<float> gauss,gaussBin;
89 gauss.initGaussian(sigma);
90 gaussBin.initGaussian(sigmaBin);
91 for(size_t c=0;c<CHANNELS;++c){
92
93 // histogram for one channel
94 MultiArrayView<DIM+1,T_HIST> histc = histogram.bindOuter(c);
95 //MultiArrayView<DIM+1,T_HIST> histcBuffer = histogram.bindOuter(c);
96
97 ConvolutionOptions<DIM+1> opts;
98 TinyVector<double, DIM+1> sigmaVec(sigma);
99 sigmaVec[DIM] = sigmaBin;
100 opts.stdDev(sigmaVec);
101
102 // convolve spatial dimensions
103 gaussianSmoothMultiArray(histc, histc, opts);
104
105 }
106
107 }
108
109 template< unsigned int DIM , class T_DATA, class T_HIST >
110 void multiGaussianCoHistogram(
111 const MultiArrayView<DIM, T_DATA > & imageA,
112 const MultiArrayView<DIM, T_DATA > & imageB,
113 const TinyVector<T_DATA,2> & minVals,
114 const TinyVector<T_DATA,2> & maxVals,
115 const TinyVector<int,2> & nBins,
116 const TinyVector<float,3> & sigma,
117 MultiArrayView<DIM+2, T_HIST> histogram
118 ){
119 typedef vigra::GridGraph< DIM , undirected_tag> Graph;
120 typedef typename Graph::NodeIt graph_scanner;
121 typedef typename Graph::Node Node;
122 typedef typename MultiArrayView<DIM+2 , T_HIST>::difference_type HistCoord;
123 const Graph g(imageA.shape());
124 histogram.init(0.0);
125 // iterate over all nodes (i.e. pixels)
126 for (graph_scanner n(g); n != lemon::INVALID; ++n){
127
128 const Node node(*n);
129 T_DATA binIndexA = imageA[node];
130 T_DATA binIndexB = imageA[node];
131
132 binIndexA -=minVals[0];
133 binIndexA /=maxVals[0];
134 binIndexA *=nBins[0];
135
136 binIndexB -=minVals[1];
137 binIndexB /=maxVals[1];
138 binIndexB *=nBins[1];
139
140 HistCoord histCoord;
141 for(size_t d=0;d<DIM;++d)
142 histCoord[d]=node[d];
143
144 histCoord[DIM]=binIndexA;
145 histCoord[DIM+1]=binIndexB;
146
147 const float fiA = binIndexA;
148 const unsigned int biA = std::floor(fiA+0.5);
149 const float fiB = binIndexB;
150 const unsigned int biB = std::floor(fiA+0.5);
151 histCoord[DIM]=std::min(biA,static_cast<unsigned int>(nBins[0]-1));
152 histCoord[DIM+1]=std::min(biB,static_cast<unsigned int>(nBins[1]-1));
153 histogram[histCoord]+=1.0;
154
155 }
156
157 MultiArray<DIM+2 , T_HIST> histogramBuffer(histogram);
158 Kernel1D<float> gaussS,gaussA,gaussB;
159 gaussS.initGaussian(sigma[0]);
160 gaussA.initGaussian(sigma[1]);
161 gaussB.initGaussian(sigma[2]);
162
163 if(DIM==2){
164 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 0, gaussS);
165 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 1, gaussS);
166 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 2, gaussA);
167 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 3, gaussB);
168 }
169 else if(DIM==3){
170 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 0, gaussS);
171 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 1, gaussS);
172 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 2, gaussS);
173 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 3, gaussA);
174 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 4, gaussB);
175 histogram=histogramBuffer;
176 }
177 else if(DIM==4){
178 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 0, gaussS);
179 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 1, gaussS);
180 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 2, gaussS);
181 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 3, gaussS);
182 convolveMultiArrayOneDimension(srcMultiArrayRange(histogram), destMultiArray(histogramBuffer), 4, gaussA);
183 convolveMultiArrayOneDimension(srcMultiArrayRange(histogramBuffer), destMultiArray(histogram), 5, gaussA);
184 }
185 else{
186 throw std::runtime_error("not yet implemented for arbitrary dimension");
187 }
188
189 }
190
191
192
193
194 template< unsigned int DIM , class T, class V, class U>
195 void multiGaussianRankOrder(
196 const MultiArrayView<DIM, T > & image,
197 const T minVal,
198 const T maxVal,
199 const size_t bins,
200 const TinyVector<double, DIM+1> sigmas,
201 const MultiArrayView<1, V> & ranks,
202 MultiArrayView<DIM+1, U> out
203 ){
204 typedef MultiArray<DIM, T> ImgType;
205 typedef typename ImgType::difference_type ImgCoord;
206
207 typedef MultiArray<DIM+1, float> HistType;
208 typedef typename HistType::difference_type HistCoord;
209
210 typedef MultiArray<DIM+1, U> OutType;
211 typedef typename OutType::difference_type OutCoord;
212
213 // FIXME: crashes on Python3
214
215 HistCoord histShape;
216 std::copy(image.shape().begin(), image.shape().end(), histShape.begin());
217 histShape[DIM] = bins;
218 HistType histA(histShape);
219
220 histA = 0.0;
221
222 // collect values
223 HistCoord histCoord,nextHistCoord;
224 {
225 MultiCoordinateIterator<DIM> iter(image.shape());
226 for(std::ptrdiff_t i=0 ;i<image.size(); ++i, ++iter){
227 const ImgCoord imgCoord(*iter);
228 std::copy(imgCoord.begin(),imgCoord.end(),histCoord.begin() );
229
230 const T value = image[imgCoord];
231 const T fbinIndex = ((value-minVal)/(maxVal-minVal))*bins;
232 const T fFloorBin = std::floor(fbinIndex);
233 const int floorBin = static_cast<int>(fFloorBin);
234 const int ceilBin = static_cast<int>(std::ceil(fbinIndex));
235
236 if(floorBin==ceilBin){
237 histCoord[DIM] = floorBin;
238 histA[histCoord] += 1.0;
239 }
240 else{
241 const T floorBin = std::floor(fbinIndex);
242 const T ceilBin = std::ceil(fbinIndex);
243 const double ceilW = (fbinIndex - fFloorBin);
244 const double floorW = 1.0 - ceilW;
245 histCoord[DIM] = floorBin;
246 histA[histCoord] += floorW;
247 histCoord[DIM] = ceilBin;
248 histA[histCoord] += ceilW;
249 }
250
251 }
252 }
253 //
254 ConvolutionOptions<DIM+1> opts;
255 opts.stdDev(sigmas);
256
257 // convolve spatial dimensions
258 gaussianSmoothMultiArray(histA, histA, opts);
259
260 OutCoord outCoord;
261
262
263 std::vector<float> histBuffer(bins);
264 //std::cout<<"normalize and compute ranks\n";
265 {
266 MultiCoordinateIterator<DIM> iter(image.shape());
267 for(std::ptrdiff_t i=0 ;i<image.size(); ++i, ++iter){
268
269 // normalize
270 const ImgCoord imgCoord(*iter);
271 //std::cout<<"at pixel "<<imgCoord<<"\n";
272
273 std::copy(imgCoord.begin(),imgCoord.end(),histCoord.begin() );
274 nextHistCoord = histCoord;
275 std::copy(imgCoord.begin(),imgCoord.end(),outCoord.begin() );
276 double sum = 0;
277 for(size_t bi=0; bi<bins; ++bi){
278 histCoord[DIM] = bi;
279 sum += histA[histCoord];
280 }
281 for(size_t bi=0; bi<bins; ++bi){
282 histCoord[DIM] = bi;
283 histA[histCoord] /= sum;
284 }
285 histCoord[DIM] = 0;
286 histBuffer[0] = histA[histCoord];
287 for(size_t bi=1; bi<bins; ++bi){
288
289 double prevVal = histA[histCoord];
290 histCoord[DIM] = bi;
291 histA[histCoord] +=prevVal;
292 histBuffer[bi] = histA[histCoord];
293 }
294
295
296
297 size_t bi=0;
298 for(std::ptrdiff_t r=0; r<ranks.size(); ++r){
299 outCoord[DIM] = r;
300 const V rank = ranks[r];
301 histCoord[DIM] = bi;
302 nextHistCoord[DIM] = bi +1;
303 //std::cout<<" bi "<<bi<<" rank "<<rank<<" "<<histA[histCoord]<<"\n";
304 // corner cases
305 if(rank < histA[histCoord] ||
306 std::abs(rank-histA[histCoord])< 0.0000001 ||
307 bi==bins-1
308 ){
309 out[outCoord] = static_cast<U>((maxVal-minVal)*bi*bins + minVal);
310 break;
311 }
312 else{
313 // with binary search
314 const size_t upperBinIndex =
315 std::distance(histBuffer.begin(),std::lower_bound(histBuffer.begin()+bi, histBuffer.end(),float(rank)));
316 bi = upperBinIndex - 1;
317 histCoord[DIM] = bi;
318 nextHistCoord[DIM] = upperBinIndex;
319 const double rankVal0 = static_cast<U>((maxVal-minVal)*bi*bins + minVal);
320 const double rankVal1 = static_cast<U>((maxVal-minVal)*(bi+1)*bins + minVal);
321 const double dd = histA[nextHistCoord] - histA[histCoord];
322 const double relD0 = (rank - histA[histCoord])/dd;
323 out[outCoord] = rankVal1 * relD0 + (1.0 - relD0)*rankVal0;
324 break;
325 }
326 }
327 }
328 }
329 }
330 }
331 //end namespace vigra
332
333 #endif //VIGRA_MULTI_HISTOGRAMM_HXX
vigra::GridGraph
Define a grid graph in arbitrary dimensions.
Definition: multi_fwd.hxx:217
vigra::MultiArrayView::difference_type
MultiArrayShape< actual_dimension >::type difference_type
Definition: multi_array.hxx:687
vigra::gaussianSmoothMultiArray
void gaussianSmoothMultiArray(...)
Isotropic Gaussian smoothing of a multi-dimensional arrays.
vigra::convolveMultiArrayOneDimension
void convolveMultiArrayOneDimension(...)
Convolution along a single dimension of a multi-dimensional arrays.
vigra
Definition: accessor.hxx:43
vigra::sum
NumericTraits< V >::Promote sum(TinyVectorBase< V, SIZE, D1, D2 > const &l)
sum of the vector&#39;s elements
Definition: tinyvector.hxx:2073
vigra::abs
FFTWComplex< R >::NormType abs(const FFTWComplex< R > &a)
absolute value (= magnitude)
Definition: fftw3.hxx:1002
vigra::ceil
int ceil(FixedPoint< IntBits, FracBits > v)
rounding up.
Definition: fixedpoint.hxx:675
vigra::floor
int floor(FixedPoint< IntBits, FracBits > v)
rounding down.
Definition: fixedpoint.hxx:667

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