Alternating asymmetric search range assignment for bidirectional motion estimation in H.265/HEVC and H.264/AVC

• The huge complexity of motion estimation is a critical problem for implementation.
• We propose alternating asymmetric search range assignment (AASRA) to save complexity.
• Temporal AASRA (T-AASRA) and temporal-spatial AASRA (TS-AASRA) are proposed.
• T-AASRA and TS-AASRA can get 43.5% and 65.2% complexity reduction, respectively.
• AASRA has the flexibility to be combined with existing algorithms and architectures.

Bidirectional motion estimation (ME) significantly enhances video coding efficiency, whereas its huge complexity is also a critical problem for implementation. This paper presents alternating asymmetric search range assignment (AASRA) schemes to reduce the complexity by switching the use of a large and a small search ranges (SR.L and SR.S). A temporal AASRA (T-AASRA) scheme performs search range switching between past and future reference directions. A temporal-spatial AASRA (TS-AASRA) scheme performs more aggressive switching on the two dimensions of reference direction and MB/CTB index. T-AASRA and TS-AASRA achieve 43.5% and 65.2% complexity reduction, respectively, with small coding efficiency drop. Even after removing the factor of coding efficiency drop, the two schemes still show 38.4% and 54.7% equivalent complexity reduction. AASRA can also be combined with existing fast algorithms for further complexity saving, which has been demonstrated on hierarchical ME and dynamic search range selection algorithms.