Accelerating Merge with Motion Vector Difference via Filter Difference Analysis for VVenC

Technical Summary: Accelerating Merge with Motion Vector Difference via Filter Difference Analysis for VVenC

Problem Statement
Merge with Motion Vector Difference (MMVD) is a critical tool in Versatile Video Coding (VVC) designed to enhance motion prediction accuracy by refining base motion vectors with a directional offset and distance. However, the standard implementation relies on an exhaustive search over all direction–distance combinations (four directions and eight distance steps), which imposes a substantial computational burden. In the VVenC encoder, enabling MMVD increases encoding time by approximately 36.39% under the "faster" preset and 21.20% under the "fast" preset. This overhead hinders the adoption of MMVD in low-latency scenarios. Existing fast-search strategies in VVenC reduce this burden but still require evaluating a significant portion of candidates, particularly quarter-pixel MVD candidates which account for 60%–80% of total trials.

Methodology
The authors propose a novel fast MMVD algorithm that utilizes fractional motion vector filter difference analysis to estimate the potential coding gain of MMVD candidates, allowing for the early termination of non-promising search paths. The core approach involves the following steps:

1. Filter Approximation: The method approximates the standard 8-tap interpolation filters used in VVC with lightweight 2-tap filters. This simplification allows the difference between the regular merge prediction and the MMVD prediction to be modeled using spatial gradients.
2. Residual-Gradient Criterion:
   • Aligned-Support Case: When the MMVD offset does not shift the integer-positioned reference samples, the difference in prediction is approximated as a function of the spatial gradient of the reference block ($g_{ref}$) and the residual of the regular merge candidate ($e_i$). A candidate is skipped if the inner product term $-\alpha_{i,j}\langle e_i, g_{ref} \rangle \geq 0$, indicating that the MMVD candidate is unlikely to yield lower distortion than the regular merge.
   • Shifted-Support Case: When the offset crosses an integer-sample boundary, the support shifts. The authors generalize the criterion to handle this by factorizing the filter difference and applying a simple 2-tap filter to the gradient, avoiding direct 3-tap filtering on the reference block.
   • 2D Separable Filtering: The 1D analysis is extended to VVC's 2D separable interpolation. Since MMVD only searches cardinal directions, the cross-terms vanish, allowing the residual-gradient criterion to be applied independently to horizontal and vertical offsets.
3. Implementation Optimizations: To minimize the overhead of the proposed method itself, two optimizations are introduced:
   • Symmetric Offset Inference: For symmetric offsets (e.g., $+\Delta$ and $-\Delta$), the response of a shifted-support case is inferred by sign inversion of the aligned-support case response, reducing redundant computations.
   • Cross-Shaped Downsampled Dot-Product: Instead of computing the dot product over the entire block, the calculation is restricted to a central cross-shaped region (middle row for horizontal offsets, middle column for vertical offsets).

Key Contributions

• Novel Criterion: Derivation of a lightweight criterion based on spatial gradients and prediction residuals to estimate MMVD gain without exhaustive search.
• Generalization: Extension of the criterion to accommodate both shifted integer reference samples and 2D separable filtering, covering practical VVC scenarios.
• Engineering Optimizations: Introduction of symmetric offset inference and efficient dot-product computation to ensure the acceleration method itself adds minimal complexity.
• Integration: Seamless integration of the proposed algorithm into the existing VVenC fast-search framework (combining with Fast1, Fast2, and Fast3 strategies).

Experimental Results
Experiments were conducted using the VVenC-1.14.0 encoder across four presets (faster, fast, medium, slow) and standard test sequences (JVET CTC Classes A1, A2, B, C, D).

• Search Reduction: The proposed method reduces the average MMVD search ratio from 21.07% (with existing fast strategies) to 11.05%.
• Complexity vs. Performance: Under the "fast" preset, the encoding-time overhead is reduced from 4.52% (existing fast strategies) to 2.23%.
• Efficiency Metric ($\eta$): The efficiency-complexity metric $\eta$ (encoding time overhead per unit BD-rate gain) improves significantly. For the "fast" preset, $\eta$ decreases from 11.79 (existing fast strategies) to 7.10. Similar improvements are observed across other presets.
• Coding Gain: The method preserves the majority of the coding gain provided by MMVD, with BD-rate losses being negligible compared to the full search baseline when combined with the proposed pruning.

Significance and Claims
The paper claims that the proposed algorithm achieves a superior trade-off between encoding complexity and Rate-Distortion (RD) performance compared to existing MMVD acceleration schemes in VVenC. By effectively pruning less promising candidates through filter difference analysis, the method significantly reduces the computational load of MMVD without sacrificing coding efficiency. The authors note that the current implementation supports only the standard four cardinal directions and plan to extend the method to support MMVD modes with flexible diagonal angles in future work.