]> git.sesse.net Git - movit/blob - fft_pass_effect_test.cpp
Make Phase take other Phases as inputs, not Nodes.
[movit] / fft_pass_effect_test.cpp
1 // Unit tests for FFTPassEffect.
2
3 #include <math.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 #include "effect_chain.h"
8 #include "fft_pass_effect.h"
9 #include "glew.h"
10 #include "gtest/gtest.h"
11 #include "image_format.h"
12 #include "multiply_effect.h"
13 #include "test_util.h"
14
15 namespace movit {
16
17 namespace {
18
19 // Generate a random number uniformly distributed between [-1.0, 1.0].
20 float uniform_random()
21 {
22         return 2.0 * ((float)rand() / RAND_MAX - 0.5);
23 }
24
25 void setup_fft(EffectChain *chain, int fft_size, bool inverse,
26                bool add_normalizer = false,
27                FFTPassEffect::Direction direction = FFTPassEffect::HORIZONTAL)
28 {
29         assert((fft_size & (fft_size - 1)) == 0);  // Must be power of two.
30         for (int i = 1, subsize = 2; subsize <= fft_size; ++i, subsize *= 2) {
31                 Effect *fft_effect = chain->add_effect(new FFTPassEffect());
32                 bool ok = fft_effect->set_int("fft_size", fft_size);
33                 ok |= fft_effect->set_int("pass_number", i);
34                 ok |= fft_effect->set_int("inverse", inverse);
35                 ok |= fft_effect->set_int("direction", direction);
36                 assert(ok);
37         }
38
39         if (add_normalizer) {
40                 float factor[4] = { 1.0f / fft_size, 1.0f / fft_size, 1.0f / fft_size, 1.0f / fft_size };
41                 Effect *multiply_effect = chain->add_effect(new MultiplyEffect());
42                 bool ok = multiply_effect->set_vec4("factor", factor);
43                 assert(ok);
44         }
45 }
46
47 void run_fft(const float *in, float *out, int fft_size, bool inverse,
48              bool add_normalizer = false,
49              FFTPassEffect::Direction direction = FFTPassEffect::HORIZONTAL)
50 {
51         int width, height;
52         if (direction == FFTPassEffect::HORIZONTAL) {
53                 width = fft_size;
54                 height = 1;
55         } else {
56                 width = 1;
57                 height = fft_size;
58         }
59         EffectChainTester tester(in, width, height, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
60         setup_fft(tester.get_chain(), fft_size, inverse, add_normalizer, direction);
61         tester.run(out, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
62 }
63
64 }  // namespace
65
66 TEST(FFTPassEffectTest, ZeroStaysZero) {
67         const int fft_size = 64;
68         float data[fft_size * 4] = { 0 };
69         float out_data[fft_size * 4];
70
71         run_fft(data, out_data, fft_size, false);
72         expect_equal(data, out_data, 4, fft_size);
73
74         run_fft(data, out_data, fft_size, true);
75         expect_equal(data, out_data, 4, fft_size);
76 }
77
78 TEST(FFTPassEffectTest, Impulse) {
79         const int fft_size = 64;
80         float data[fft_size * 4] = { 0 };
81         float expected_data[fft_size * 4], out_data[fft_size * 4];
82         data[0] = 1.0;
83         data[1] = 1.2;
84         data[2] = 1.4;
85         data[3] = 3.0;
86
87         for (int i = 0; i < fft_size; ++i) {
88                 expected_data[i * 4 + 0] = data[0];
89                 expected_data[i * 4 + 1] = data[1];
90                 expected_data[i * 4 + 2] = data[2];
91                 expected_data[i * 4 + 3] = data[3];
92         }
93
94         run_fft(data, out_data, fft_size, false);
95         expect_equal(expected_data, out_data, 4, fft_size);
96
97         run_fft(data, out_data, fft_size, true);
98         expect_equal(expected_data, out_data, 4, fft_size);
99 }
100
101 TEST(FFTPassEffectTest, SingleFrequency) {
102         const int fft_size = 16;
103         float data[fft_size * 4] = { 0 };
104         float expected_data[fft_size * 4], out_data[fft_size * 4];
105         for (int i = 0; i < fft_size; ++i) {
106                 data[i * 4 + 0] = sin(2.0 * M_PI * (4.0 * i) / fft_size);
107                 data[i * 4 + 1] = 0.0;
108                 data[i * 4 + 2] = 0.0;
109                 data[i * 4 + 3] = 0.0;
110         }
111         for (int i = 0; i < fft_size; ++i) {
112                 expected_data[i * 4 + 0] = 0.0;
113                 expected_data[i * 4 + 1] = 0.0;
114                 expected_data[i * 4 + 2] = 0.0;
115                 expected_data[i * 4 + 3] = 0.0;
116         }
117         expected_data[4 * 4 + 1] = -8.0;
118         expected_data[12 * 4 + 1] = 8.0;
119
120         run_fft(data, out_data, fft_size, false, false, FFTPassEffect::HORIZONTAL);
121         expect_equal(expected_data, out_data, 4, fft_size);
122
123         run_fft(data, out_data, fft_size, false, false, FFTPassEffect::VERTICAL);
124         expect_equal(expected_data, out_data, 4, fft_size);
125 }
126
127 TEST(FFTPassEffectTest, Repeat) {
128         srand(12345);
129         for (int fft_size = 2; fft_size < 512; fft_size *= 2) {
130                 const int num_repeats = 31;  // Prime, to make things more challenging.
131                 float data[num_repeats * fft_size * 4];
132                 float expected_data[num_repeats * fft_size * 4], out_data[num_repeats * fft_size * 4];
133
134                 for (int i = 0; i < num_repeats * fft_size * 4; ++i) {
135                         data[i] = uniform_random();
136                 }
137
138                 for (int i = 0; i < num_repeats; ++i) {
139                         run_fft(data + i * fft_size * 4, expected_data + i * fft_size * 4, fft_size, false);
140                 }
141
142                 {
143                         // Horizontal.
144                         EffectChainTester tester(data, num_repeats * fft_size, 1, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
145                         setup_fft(tester.get_chain(), fft_size, false);
146                         tester.run(out_data, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
147
148                         expect_equal(expected_data, out_data, 4, num_repeats * fft_size);
149                 }
150                 {
151                         // Vertical.
152                         EffectChainTester tester(data, 1, num_repeats * fft_size, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
153                         setup_fft(tester.get_chain(), fft_size, false, false, FFTPassEffect::VERTICAL);
154                         tester.run(out_data, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
155
156                         expect_equal(expected_data, out_data, 4, num_repeats * fft_size);
157                 }
158         }
159 }
160
161 TEST(FFTPassEffectTest, TwoDimensional) {  // Implicitly tests vertical.
162         srand(1234);
163         const int fft_size = 16;
164         float in[fft_size * fft_size * 4], out[fft_size * fft_size * 4], expected_out[fft_size * fft_size * 4];
165         for (int y = 0; y < fft_size; ++y) {
166                 for (int x = 0; x < fft_size; ++x) {
167                         in[(y * fft_size + x) * 4 + 0] =
168                                 sin(2.0 * M_PI * (2 * x + 3 * y) / fft_size);
169                         in[(y * fft_size + x) * 4 + 1] = 0.0;
170                         in[(y * fft_size + x) * 4 + 2] = 0.0;
171                         in[(y * fft_size + x) * 4 + 3] = 0.0;
172                 }
173         }
174         memset(expected_out, 0, sizeof(expected_out));
175
176         // This result has been verified using the fft2() function in Octave,
177         // which uses FFTW.
178         expected_out[(3 * fft_size + 2) * 4 + 1] = -128.0;
179         expected_out[(13 * fft_size + 14) * 4 + 1] = 128.0;
180
181         EffectChainTester tester(in, fft_size, fft_size, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
182         setup_fft(tester.get_chain(), fft_size, false, false, FFTPassEffect::HORIZONTAL);
183         setup_fft(tester.get_chain(), fft_size, false, false, FFTPassEffect::VERTICAL);
184         tester.run(out, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
185
186         expect_equal(expected_out, out, 4 * fft_size, fft_size, 0.25, 0.0005);
187 }
188
189 // The classic paper for FFT correctness testing is Funda Ergün:
190 // “Testing Multivariate Linear Functions: Overcoming the Generator Bottleneck”
191 // (http://www.cs.sfu.ca/~funda/PUBLICATIONS/stoc95.ps), which proves that
192 // testing three basic properties of FFTs guarantees that the function is
193 // correct (at least under the assumption that errors are random).
194 //
195 // We don't follow the paper directly, though, for a few reasons: First,
196 // Ergün's paper really considers _self-correcting_ systems, which may
197 // be stochastically faulty, and thus uses various relatively complicated
198 // bounds and tests we don't really need. Second, the FFTs it considers
199 // are all about polynomials over finite fields, which means that results
200 // are exact and thus easy to test; we work with floats (half-floats!),
201 // and thus need some error tolerance.
202 //
203 // So instead, we follow the implementation of FFTW, which is really the
204 // gold standard when it comes to FFTs these days. They hard-code 20
205 // testing rounds as opposed to the more complicated bounds in the paper,
206 // and have a simpler version of the third test.
207 //
208 // The error bounds are set somewhat empirically, but remember that these
209 // inputs will give frequency values as large as ~16, where 0.025 is
210 // within the 9th bit (of 11 total mantissa bits in fp16).
211 const int ergun_rounds = 20;
212
213 // Test 1: Test that FFT(a + b) = FFT(a) + FFT(b).
214 TEST(FFTPassEffectTest, ErgunLinearityTest) {
215         srand(1234);
216         const int max_fft_size = 64;
217         float a[max_fft_size * 4], b[max_fft_size * 4], sum[max_fft_size * 4];
218         float a_out[max_fft_size * 4], b_out[max_fft_size * 4], sum_out[max_fft_size * 4], expected_sum_out[max_fft_size * 4];
219         for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
220                 for (int inverse = 0; inverse <= 1; ++inverse) {
221                         for (int i = 0; i < ergun_rounds; ++i) {
222                                 for (int j = 0; j < fft_size * 4; ++j) {
223                                         a[j] = uniform_random();
224                                         b[j] = uniform_random();
225                                 }
226                                 run_fft(a, a_out, fft_size, inverse);
227                                 run_fft(b, b_out, fft_size, inverse);
228
229                                 for (int j = 0; j < fft_size * 4; ++j) {
230                                         sum[j] = a[j] + b[j];
231                                         expected_sum_out[j] = a_out[j] + b_out[j];
232                                 }
233
234                                 run_fft(sum, sum_out, fft_size, inverse);
235                                 expect_equal(expected_sum_out, sum_out, 4, fft_size, 0.03, 0.0005);
236                         }
237                 }
238         }
239 }
240
241 // Test 2: Test that FFT(delta(i)) = 1  (where delta(i) = [1 0 0 0 ...]),
242 // or more specifically, test that FFT(a + delta(i)) - FFT(a) = 1.
243 TEST(FFTPassEffectTest, ErgunImpulseTransform) {
244         srand(1235);
245         const int max_fft_size = 64;
246         float a[max_fft_size * 4], b[max_fft_size * 4];
247         float a_out[max_fft_size * 4], b_out[max_fft_size * 4], sum_out[max_fft_size * 4], expected_sum_out[max_fft_size * 4];
248         for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
249                 for (int inverse = 0; inverse <= 1; ++inverse) {
250                         for (int i = 0; i < ergun_rounds; ++i) {
251                                 for (int j = 0; j < fft_size * 4; ++j) {
252                                         a[j] = uniform_random();
253
254                                         // Compute delta(j) - a.
255                                         if (j < 4) {
256                                                 b[j] = 1.0 - a[j];
257                                         } else {
258                                                 b[j] = -a[j];
259                                         }
260                                 }
261                                 run_fft(a, a_out, fft_size, inverse);
262                                 run_fft(b, b_out, fft_size, inverse);
263
264                                 for (int j = 0; j < fft_size * 4; ++j) {
265                                         sum_out[j] = a_out[j] + b_out[j];
266                                         expected_sum_out[j] = 1.0;
267                                 }
268                                 expect_equal(expected_sum_out, sum_out, 4, fft_size, 0.025, 0.0005);
269                         }
270                 }
271         }
272 }
273
274 // Test 3: Test the time-shift property of the FFT, in that a circular left-shift
275 // multiplies the result by e^(j 2pi k/N) (linear phase adjustment).
276 // As fftw_test.c says, “The paper performs more tests, but this code should be
277 // fine too”.
278 TEST(FFTPassEffectTest, ErgunShiftProperty) {
279         srand(1236);
280         const int max_fft_size = 64;
281         float a[max_fft_size * 4], b[max_fft_size * 4];
282         float a_out[max_fft_size * 4], b_out[max_fft_size * 4], expected_a_out[max_fft_size * 4];
283         for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
284                 for (int inverse = 0; inverse <= 1; ++inverse) {
285                         for (int direction = 0; direction <= 1; ++direction) {
286                                 for (int i = 0; i < ergun_rounds; ++i) {
287                                         for (int j = 0; j < fft_size * 4; ++j) {
288                                                 a[j] = uniform_random();
289                                         }
290
291                                         // Circular shift left by one step.
292                                         for (int j = 0; j < fft_size * 4; ++j) {
293                                                 b[j] = a[(j + 4) % (fft_size * 4)];
294                                         }
295                                         run_fft(a, a_out, fft_size, inverse, false, FFTPassEffect::Direction(direction));
296                                         run_fft(b, b_out, fft_size, inverse, false, FFTPassEffect::Direction(direction));
297
298                                         for (int j = 0; j < fft_size; ++j) {
299                                                 double s = -sin(j * 2.0 * M_PI / fft_size);
300                                                 double c = cos(j * 2.0 * M_PI / fft_size);
301                                                 if (inverse) {
302                                                         s = -s;
303                                                 }
304
305                                                 expected_a_out[j * 4 + 0] = b_out[j * 4 + 0] * c - b_out[j * 4 + 1] * s;
306                                                 expected_a_out[j * 4 + 1] = b_out[j * 4 + 0] * s + b_out[j * 4 + 1] * c;
307
308                                                 expected_a_out[j * 4 + 2] = b_out[j * 4 + 2] * c - b_out[j * 4 + 3] * s;
309                                                 expected_a_out[j * 4 + 3] = b_out[j * 4 + 2] * s + b_out[j * 4 + 3] * c;
310                                         }
311                                         expect_equal(expected_a_out, a_out, 4, fft_size, 0.025, 0.0005);
312                                 }
313                         }
314                 }
315         }
316 }
317
318 TEST(FFTPassEffectTest, BigFFTAccuracy) {
319         srand(1234);
320         const int max_fft_size = 2048;
321         float in[max_fft_size * 4], out[max_fft_size * 4], out2[max_fft_size * 4];
322         for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
323                 for (int j = 0; j < fft_size * 4; ++j) {
324                         in[j] = uniform_random();
325                 }
326                 run_fft(in, out, fft_size, false, true);  // Forward, with normalization.
327                 run_fft(out, out2, fft_size, true);       // Reverse.
328
329                 // These error bounds come from
330                 // http://en.wikipedia.org/wiki/Fast_Fourier_transform#Accuracy_and_approximations,
331                 // with empirically estimated epsilons. Note that the calculated
332                 // rms in expect_equal() is divided by sqrt(N), so we compensate
333                 // similarly here.
334                 double max_error = 0.0009 * log2(fft_size);
335                 double rms_limit = 0.0007 * sqrt(log2(fft_size)) / sqrt(fft_size);
336                 expect_equal(in, out2, 4, fft_size, max_error, rms_limit);
337         }
338 }
339
340 }  // namespace movit