4 // Code for computing optical flow between two images, and using it to interpolate
5 // in-between frames. The main user interface is the DISComputeFlow and Interpolate
6 // classes (also GrayscaleConversion can be useful).
18 // Predefined operating points from the paper.
19 struct OperatingPoint {
20 unsigned coarsest_level; // TODO: Adjust dynamically based on the resolution?
21 unsigned finest_level;
22 unsigned search_iterations; // Halved from the paper.
23 unsigned patch_size_pixels;
24 float patch_overlap_ratio;
25 bool variational_refinement;
27 // Not part of the original paper; used for interpolation.
28 // NOTE: Values much larger than 1.0 seems to trigger Haswell's “PMA stall”;
29 // the problem is not present on Broadwell and higher (there's a mitigation
30 // in the hardware, but Mesa doesn't enable it at the time of writing).
31 // Since we have hole filling, the holes from 1.0 are not critical,
32 // but larger values seem to do better than hole filling for large
33 // motion, blurs etc. since we have more candidates.
37 // Operating point 1 (600 Hz on CPU, excluding preprocessing).
38 static constexpr OperatingPoint operating_point1 = {
41 8, // Search iterations.
42 8, // Patch size (pixels).
43 0.30f, // Overlap ratio.
44 false, // Variational refinement.
45 1.0f // Splat size (pixels).
48 // Operating point 2 (300 Hz on CPU, excluding preprocessing).
49 static constexpr OperatingPoint operating_point2 = {
52 6, // Search iterations.
53 8, // Patch size (pixels).
54 0.40f, // Overlap ratio.
55 true, // Variational refinement.
56 1.0f // Splat size (pixels).
59 // Operating point 3 (10 Hz on CPU, excluding preprocessing).
60 // This is the only one that has been thorougly tested.
61 static constexpr OperatingPoint operating_point3 = {
64 8, // Search iterations.
65 12, // Patch size (pixels).
66 0.75f, // Overlap ratio.
67 true, // Variational refinement.
68 4.0f // Splat size (pixels).
71 // Operating point 4 (0.5 Hz on CPU, excluding preprocessing).
72 static constexpr OperatingPoint operating_point4 = {
75 128, // Search iterations.
76 12, // Patch size (pixels).
77 0.75f, // Overlap ratio.
78 true, // Variational refinement.
79 8.0f // Splat size (pixels).
82 int find_num_levels(int width, int height);
84 // A class that caches FBOs that render to a given set of textures.
85 // It never frees anything, so it is only suitable for rendering to
86 // the same (small) set of textures over and over again.
87 template<size_t num_elements>
88 class PersistentFBOSet {
90 void render_to(const std::array<GLuint, num_elements> &textures);
92 // Convenience wrappers.
93 void render_to(GLuint texture0)
95 render_to({ { texture0 } });
98 void render_to(GLuint texture0, GLuint texture1)
100 render_to({ { texture0, texture1 } });
103 void render_to(GLuint texture0, GLuint texture1, GLuint texture2)
105 render_to({ { texture0, texture1, texture2 } });
108 void render_to(GLuint texture0, GLuint texture1, GLuint texture2, GLuint texture3)
110 render_to({ { texture0, texture1, texture2, texture3 } });
114 // TODO: Delete these on destruction.
115 std::map<std::array<GLuint, num_elements>, GLuint> fbos;
118 // Same, but with a depth texture.
119 template<size_t num_elements>
120 class PersistentFBOSetWithDepth {
122 void render_to(GLuint depth_rb, const std::array<GLuint, num_elements> &textures);
124 // Convenience wrappers.
125 void render_to(GLuint depth_rb, GLuint texture0)
127 render_to(depth_rb, { { texture0 } });
130 void render_to(GLuint depth_rb, GLuint texture0, GLuint texture1)
132 render_to(depth_rb, { { texture0, texture1 } });
135 void render_to(GLuint depth_rb, GLuint texture0, GLuint texture1, GLuint texture2)
137 render_to(depth_rb, { { texture0, texture1, texture2 } });
140 void render_to(GLuint depth_rb, GLuint texture0, GLuint texture1, GLuint texture2, GLuint texture3)
142 render_to(depth_rb, { { texture0, texture1, texture2, texture3 } });
146 // TODO: Delete these on destruction.
147 std::map<std::pair<GLuint, std::array<GLuint, num_elements>>, GLuint> fbos;
150 // Convert RGB to grayscale, using Rec. 709 coefficients.
151 class GrayscaleConversion {
153 GrayscaleConversion();
154 void exec(GLint tex, GLint gray_tex, int width, int height, int num_layers);
157 PersistentFBOSet<1> fbos;
166 // Compute gradients in every point, used for the motion search.
167 // The DIS paper doesn't actually mention how these are computed,
168 // but seemingly, a 3x3 Sobel operator is used here (at least in
169 // later versions of the code), while a [1 -8 0 8 -1] kernel is
170 // used for all the derivatives in the variational refinement part
171 // (which borrows code from DeepFlow). This is inconsistent,
172 // but I guess we're better off with staying with the original
173 // decisions until we actually know having different ones would be better.
177 void exec(GLint tex_view, GLint grad_tex, int level_width, int level_height, int num_layers);
180 PersistentFBOSet<1> fbos;
183 GLuint sobel_program;
188 // Motion search to find the initial flow. See motion_search.frag for documentation.
191 MotionSearch(const OperatingPoint &op);
192 void exec(GLuint tex_view, GLuint grad_tex, GLuint flow_tex, GLuint flow_out_tex, int level_width, int level_height, int prev_level_width, int prev_level_height, int width_patches, int height_patches, int num_layers);
195 const OperatingPoint op;
196 PersistentFBOSet<1> fbos;
198 GLuint motion_vs_obj;
199 GLuint motion_fs_obj;
200 GLuint motion_search_program;
202 GLuint uniform_inv_image_size, uniform_inv_prev_level_size, uniform_out_flow_size;
203 GLuint uniform_image_tex, uniform_grad_tex, uniform_flow_tex;
204 GLuint uniform_patch_size, uniform_num_iterations;
207 // Do “densification”, ie., upsampling of the flow patches to the flow field
208 // (the same size as the image at this level). We draw one quad per patch
209 // over its entire covered area (using instancing in the vertex shader),
210 // and then weight the contributions in the pixel shader by post-warp difference.
211 // This is equation (3) in the paper.
213 // We accumulate the flow vectors in the R/G channels (for u/v) and the total
214 // weight in the B channel. Dividing R and G by B gives the normalized values.
217 Densify(const OperatingPoint &op);
218 void exec(GLuint tex_view, GLuint flow_tex, GLuint dense_flow_tex, int level_width, int level_height, int width_patches, int height_patches, int num_layers);
222 PersistentFBOSet<1> fbos;
224 GLuint densify_vs_obj;
225 GLuint densify_fs_obj;
226 GLuint densify_program;
228 GLuint uniform_patch_size;
229 GLuint uniform_image_tex, uniform_flow_tex;
232 // Warp I_1 to I_w, and then compute the mean (I) and difference (I_t) of
233 // I_0 and I_w. The prewarping is what enables us to solve the variational
234 // flow for du,dv instead of u,v.
236 // Also calculates the normalized flow, ie. divides by z (this is needed because
237 // Densify works by additive blending) and multiplies by the image size.
239 // See variational_refinement.txt for more information.
243 void exec(GLuint tex_view, GLuint flow_tex, GLuint normalized_flow_tex, GLuint I_tex, GLuint I_t_tex, int level_width, int level_height, int num_layers);
246 PersistentFBOSet<3> fbos;
248 GLuint prewarp_vs_obj;
249 GLuint prewarp_fs_obj;
250 GLuint prewarp_program;
252 GLuint uniform_image_tex, uniform_flow_tex;
255 // From I, calculate the partial derivatives I_x and I_y. We use a four-tap
256 // central difference filter, since apparently, that's tradition (I haven't
257 // measured quality versus a more normal 0.5 (I[x+1] - I[x-1]).)
258 // The coefficients come from
260 // https://en.wikipedia.org/wiki/Finite_difference_coefficient
262 // Also computes β_0, since it depends only on I_x and I_y.
266 void exec(GLuint input_tex, GLuint I_x_y_tex, GLuint beta_0_tex, int level_width, int level_height, int num_layers);
269 PersistentFBOSet<2> fbos;
271 GLuint derivatives_vs_obj;
272 GLuint derivatives_fs_obj;
273 GLuint derivatives_program;
278 // Calculate the diffusivity for each pixels, g(x,y). Smoothness (s) will
279 // be calculated in the shaders on-the-fly by sampling in-between two
280 // neighboring g(x,y) pixels, plus a border tweak to make sure we get
281 // zero smoothness at the border.
283 // See variational_refinement.txt for more information.
284 class ComputeDiffusivity {
286 ComputeDiffusivity();
287 void exec(GLuint flow_tex, GLuint diff_flow_tex, GLuint diffusivity_tex, int level_width, int level_height, bool zero_diff_flow, int num_layers);
290 PersistentFBOSet<1> fbos;
292 GLuint diffusivity_vs_obj;
293 GLuint diffusivity_fs_obj;
294 GLuint diffusivity_program;
296 GLuint uniform_flow_tex, uniform_diff_flow_tex;
297 GLuint uniform_alpha, uniform_zero_diff_flow;
300 // Set up the equations set (two equations in two unknowns, per pixel).
301 // We store five floats; the three non-redundant elements of the 2x2 matrix (A)
302 // as 32-bit floats, and the two elements on the right-hand side (b) as 16-bit
303 // floats. (Actually, we store the inverse of the diagonal elements, because
304 // we only ever need to divide by them.) This fits into four u32 values;
305 // R, G, B for the matrix (the last element is symmetric) and A for the two b values.
306 // All the values of the energy term (E_I, E_G, E_S), except the smoothness
307 // terms that depend on other pixels, are calculated in one pass.
309 // The equation set is split in two; one contains only the pixels needed for
310 // the red pass, and one only for the black pass (see sor.frag). This reduces
311 // the amount of data the SOR shader has to pull in, at the cost of some
312 // complexity when the equation texture ends up with half the size and we need
313 // to adjust texture coordinates. The contraction is done along the horizontal
314 // axis, so that on even rows (0, 2, 4, ...), the “red” texture will contain
315 // pixels 0, 2, 4, 6, etc., and on odd rows 1, 3, 5, etc..
317 // See variational_refinement.txt for more information about the actual
319 class SetupEquations {
322 void exec(GLuint I_x_y_tex, GLuint I_t_tex, GLuint diff_flow_tex, GLuint flow_tex, GLuint beta_0_tex, GLuint diffusivity_tex, GLuint equation_red_tex, GLuint equation_black_tex, int level_width, int level_height, bool zero_diff_flow, int num_layers);
325 PersistentFBOSet<2> fbos;
327 GLuint equations_vs_obj;
328 GLuint equations_fs_obj;
329 GLuint equations_program;
331 GLuint uniform_I_x_y_tex, uniform_I_t_tex;
332 GLuint uniform_diff_flow_tex, uniform_base_flow_tex;
333 GLuint uniform_beta_0_tex;
334 GLuint uniform_diffusivity_tex;
335 GLuint uniform_gamma, uniform_delta, uniform_zero_diff_flow;
338 // Actually solve the equation sets made by SetupEquations, by means of
339 // successive over-relaxation (SOR).
341 // See variational_refinement.txt for more information.
345 void exec(GLuint diff_flow_tex, GLuint equation_red_tex, GLuint equation_black_tex, GLuint diffusivity_tex, int level_width, int level_height, int num_iterations, bool zero_diff_flow, int num_layers, ScopedTimer *sor_timer);
348 PersistentFBOSet<1> fbos;
354 GLuint uniform_diff_flow_tex;
355 GLuint uniform_equation_red_tex, uniform_equation_black_tex;
356 GLuint uniform_diffusivity_tex;
357 GLuint uniform_phase, uniform_num_nonzero_phases;
360 // Simply add the differential flow found by the variational refinement to the base flow.
361 // The output is in base_flow_tex; we don't need to make a new texture.
365 void exec(GLuint base_flow_tex, GLuint diff_flow_tex, int level_width, int level_height, int num_layers);
368 PersistentFBOSet<1> fbos;
370 GLuint add_flow_vs_obj;
371 GLuint add_flow_fs_obj;
372 GLuint add_flow_program;
374 GLuint uniform_diff_flow_tex;
377 // Take a copy of the flow, bilinearly interpolated and scaled up.
381 void exec(GLuint in_tex, GLuint out_tex, int input_width, int input_height, int output_width, int output_height, int num_layers);
384 PersistentFBOSet<1> fbos;
386 GLuint resize_flow_vs_obj;
387 GLuint resize_flow_fs_obj;
388 GLuint resize_flow_program;
390 GLuint uniform_flow_tex;
391 GLuint uniform_scale_factor;
394 // All operations, except construction and destruction, are thread-safe.
397 GLuint get_texture(GLenum format, GLuint width, GLuint height, GLuint num_layers = 0);
398 void release_texture(GLuint tex_num);
399 GLuint get_renderbuffer(GLenum format, GLuint width, GLuint height);
400 void release_renderbuffer(GLuint tex_num);
406 GLuint width, height, num_layers;
408 bool is_renderbuffer = false;
411 std::vector<Texture> textures; // Under mu.
414 class DISComputeFlow {
416 DISComputeFlow(int width, int height, const OperatingPoint &op);
422 enum ResizeStrategy {
424 RESIZE_FLOW_TO_FULL_SIZE
427 // The texture must have two layers (first and second frame).
428 // Returns a texture that must be released with release_texture()
430 GLuint exec(GLuint tex, FlowDirection flow_direction, ResizeStrategy resize_strategy);
432 void release_texture(GLuint tex)
434 pool.release_texture(tex);
439 GLuint initial_flow_tex;
440 GLuint vertex_vbo, vao;
442 const OperatingPoint op;
444 // The various passes.
446 MotionSearch motion_search;
449 Derivatives derivatives;
450 ComputeDiffusivity compute_diffusivity;
451 SetupEquations setup_equations;
453 AddBaseFlow add_base_flow;
454 ResizeFlow resize_flow;
457 // Forward-warp the flow half-way (or rather, by alpha). A non-zero “splatting”
458 // radius fills most of the holes.
461 Splat(const OperatingPoint &op);
463 // alpha is the time of the interpolated frame (0..1).
464 void exec(GLuint gray_tex, GLuint bidirectional_flow_tex, GLuint flow_tex, GLuint depth_rb, int width, int height, float alpha);
467 const OperatingPoint op;
468 PersistentFBOSetWithDepth<1> fbos;
472 GLuint splat_program;
474 GLuint uniform_splat_size, uniform_alpha;
475 GLuint uniform_gray_tex, uniform_flow_tex;
476 GLuint uniform_inv_flow_size;
479 // Doing good and fast hole-filling on a GPU is nontrivial. We choose an option
480 // that's fairly simple (given that most holes are really small) and also hopefully
481 // cheap should the holes not be so small. Conceptually, we look for the first
482 // non-hole to the left of us (ie., shoot a ray until we hit something), then
483 // the first non-hole to the right of us, then up and down, and then average them
484 // all together. It's going to create “stars” if the holes are big, but OK, that's
487 // Our implementation here is efficient assuming that the hierarchical Z-buffer is
488 // on even for shaders that do discard (this typically kills early Z, but hopefully
489 // not hierarchical Z); we set up Z so that only holes are written to, which means
490 // that as soon as a hole is filled, the rasterizer should just skip it. Most of the
491 // fullscreen quads should just be discarded outright, really.
496 // Output will be in flow_tex, temp_tex[0, 1, 2], representing the filling
497 // from the down, left, right and up, respectively. Use HoleBlend to merge
499 void exec(GLuint flow_tex, GLuint depth_rb, GLuint temp_tex[3], int width, int height);
502 PersistentFBOSetWithDepth<1> fbos;
509 GLuint uniform_z, uniform_sample_offset;
512 // Blend the four directions from HoleFill into one pixel, so that single-pixel
513 // holes become the average of their four neighbors.
518 void exec(GLuint flow_tex, GLuint depth_rb, GLuint temp_tex[3], int width, int height);
521 PersistentFBOSetWithDepth<1> fbos;
525 GLuint blend_program;
527 GLuint uniform_left_tex, uniform_right_tex, uniform_up_tex, uniform_down_tex;
528 GLuint uniform_z, uniform_sample_offset;
533 Blend(bool split_ycbcr_output);
535 // output2_tex is only used if split_ycbcr_output was true.
536 void exec(GLuint image_tex, GLuint flow_tex, GLuint output_tex, GLuint output2_tex, int width, int height, float alpha);
539 bool split_ycbcr_output;
540 PersistentFBOSet<1> fbos;
541 PersistentFBOSet<2> fbos_split;
544 GLuint blend_program;
546 GLuint uniform_image_tex, uniform_flow_tex;
547 GLuint uniform_alpha, uniform_flow_consistency_tolerance;
552 Interpolate(const OperatingPoint &op, bool split_ycbcr_output);
554 // Returns a texture (or two, if split_ycbcr_output is true) that must
555 // be released with release_texture() after use. image_tex must be a
556 // two-layer RGBA8 texture with mipmaps (unless flow_level == 0).
557 std::pair<GLuint, GLuint> exec(GLuint image_tex, GLuint gray_tex, GLuint bidirectional_flow_tex, GLuint width, GLuint height, float alpha);
559 void release_texture(GLuint tex)
561 pool.release_texture(tex);
566 GLuint vertex_vbo, vao;
568 const bool split_ycbcr_output;
572 HoleBlend hole_blend;
576 #endif // !defined(_FLOW_H)