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

integral_image.hxx
1/************************************************************************/
2/* */
3/* Copyright 2012-2013 by Ullrich Koethe and Anna Kreshuk */
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_INTEGRALIMAGE_HXX
37#define VIGRA_INTEGRALIMAGE_HXX
38
39#include <vigra/multi_array.hxx>
40#include <vigra/multi_pointoperators.hxx>
41#include <vigra/utilities.hxx>
42#include <vigra/functorexpression.hxx>
43
44namespace vigra {
45
46template <unsigned int N, class T1, class S1, class T2, class S2, class FUNCTOR>
47void
48cumulativeSum(MultiArrayView<N, T1, S1> const & image,
50 int axis,
51 FUNCTOR const & functor)
52{
53 typedef typename MultiArrayShape<N>::type ShapeN;
54 ShapeN offset = ShapeN::unitVector(axis);
55
56 MultiCoordinateIterator<N> i(image.shape()),
57 end(i.getEndIterator());
58 for(; i != end; ++i)
59 {
60 if((*i)[axis] == 0)
61 {
62 out[*i] = functor(image[*i]);
63 }
64 else
65 {
66 out[*i] = functor(image[*i]) + out[*i - offset];
67 }
68 }
69}
70
71template <unsigned int N, class T1, class S1, class T2, class S2, class FUNCTOR>
72void
73integralMultiArrayImpl(MultiArrayView<N, T1, S1> const & array,
75 FUNCTOR const & f)
76{
77 vigra_precondition(array.shape() == intarray.shape(),
78 "integralMultiArray(): shape mismatch between input and output.");
79
80 cumulativeSum(array, intarray, 0, f);
81
82 for(unsigned axis=1; axis < N; ++axis)
83 cumulativeSum(intarray, intarray, axis, functor::Identity());
84}
85
86template <class T1, class S1, class T2, class S2, class FUNCTOR>
87void
88integralMultiArrayImpl(MultiArrayView<2, T1, S1> const & image,
90 FUNCTOR const & functor)
91{
92 vigra_precondition(image.shape() == intimage.shape(),
93 "integralMultiArray(): shape mismatch between input and output.");
94
95 int width = image.shape(0);
96 int height = image.shape(1);
97
98 T2 s = T2();
99 for (int x=0; x<width; ++x)
100 {
101 s += functor(image(x, 0));
102 intimage(x, 0) = s;
103 }
104 for (int y=1; y<height; ++y)
105 {
106 s = T2();
107 for (int x=0; x<width; ++x)
108 {
109 s += functor(image(x, y));
110 intimage(x, y) = s + intimage(x, y-1);
111 }
112 }
113}
114
115template <class T1, class S1, class T2, class S2, class FUNCTOR>
116void
117integralMultiArrayImpl(MultiArrayView<3, T1, S1> const & volume,
119 FUNCTOR const & functor)
120{
121 vigra_precondition(volume.shape() == intvolume.shape(),
122 "integralMultiArray(): shape mismatch between input and output.");
123
124 int nx = volume.shape(0);
125 int ny = volume.shape(1);
126 int nz = volume.shape(2);
127
128 //this vector will store s2(x, y-1) for all values of x
129 MultiArray<1, T2> s2_temp(nx);
130
131 T2 s1 = T2();
132 T2 s2 = T2();
133
134 for (int iy=0; iy<ny; ++iy)
135 {
136 s1 = T2();
137 for (int ix=0; ix<nx; ++ix)
138 {
139 s1 += functor(volume(ix, iy, 0));
140 s2 = s2_temp(ix) + s1;
141 s2_temp(ix) = s2;
142 intvolume(ix, iy, 0) = s2;
143 }
144 }
145
146 for (int iz=1; iz<nz; ++iz)
147 {
148 s2_temp = T2();
149
150 for (int iy=0; iy<ny; ++iy)
151 {
152 s1 = T2();
153 for (int ix=0; ix<nx; ++ix)
154 {
155 s1 += functor(volume(ix, iy, iz));
156 s2 = s2_temp(ix) + s1;
157 s2_temp(ix) = s2;
158 intvolume(ix, iy, iz) = s2 + intvolume(ix, iy, iz-1);
159 }
160 }
161 }
162}
163
164template <unsigned int N, class T1, class S1, class T2, class S2, class FUNCTOR>
165inline void
166integralMultiArray(MultiArrayView<N, T1, S1> const & array,
168 FUNCTOR const & f)
169{
170 integralMultiArrayImpl(array, intarray, f);
171}
172
173template <unsigned int N, class T1, class S1, class T2, class S2, class FUNCTOR>
174inline void
175integralMultiArray(MultiArrayView<N, Multiband<T1>, S1> const & array,
176 MultiArrayView<N, Multiband<T2>, S2> intarray,
177 FUNCTOR const & f)
178{
179 for(int channel=0; channel < array.shape(N-1); ++channel)
180 integralMultiArrayImpl(array.bindOuter(channel), intarray.bindOuter(channel), f);
181}
182
183template <unsigned int N, class T1, class S1, class T2, class S2>
184inline void
185integralMultiArray(MultiArrayView<N, T1, S1> const & array,
187{
188 integralMultiArray(array, intarray, functor::Identity());
189}
190
191template <unsigned int N, class T1, class S1, class T2, class S2>
192inline void
193integralMultiArray(MultiArrayView<N, Multiband<T1>, S1> const & array,
194 MultiArrayView<N, Multiband<T2>, S2> intarray)
195{
196 integralMultiArray(array, intarray, functor::Identity());
197}
198
199template <unsigned int N, class T1, class S1, class T2, class S2>
200inline void
201integralMultiArraySquared(MultiArrayView<N, T1, S1> const & array,
203{
204 using namespace functor;
205 integralMultiArray(array, intarray, sq(Arg1()));
206}
207
208template <unsigned int N, class T1, class S1, class T2, class S2>
209inline void
210integralMultiArraySquared(MultiArrayView<N, Multiband<T1>, S1> const & array,
211 MultiArrayView<N, Multiband<T2>, S2> intarray)
212{
213 using namespace functor;
214 integralMultiArray(array, intarray, sq(Arg1()));
215}
216
217} // namespace vigra
218
219#endif // VIGRA_INTEGRALIMAGE_HXX
TinyVector< MultiArrayIndex, N > type
Definition multi_shape.hxx:272
Base class for, and view to, MultiArray.
Definition multi_array.hxx:705
Main MultiArray class containing the memory management.
Definition multi_array.hxx:2479
Iterate over a virtual array where each element contains its coordinate.
Definition multi_iterator.hxx:89
NumericTraits< T >::Promote sq(T t)
The square function.
Definition mathutil.hxx:382

© 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.12.1 (Thu Feb 27 2025)