Recent advancements in the processing capabilities of handsets, tablets and computers have resulted in a considerable increase of the demand for improved visual quality and higher resolution video content. To meet these demands, modern video compression standards, like H.264/advanced video coding (AVC) and H.265/high efficiency video coding (HEVC), have considerably increased the solution space of motion estimation (ME). Modern motion estimation algorithms only consider a very small part of the solution space, which results in suboptimal solutions that not only reduce visual quality but also increase the bit rate.
Approaches like the successive elimination algorithm (SEA) and its derivatives show great potential in reducing the solution space of ME without reducing visual quality or increasing the bit rate. However, SEA is rarely used in modern encoders, because it has not been adapted to modern coding tools and, since, historically, it was intended for exhaustive searches, not suboptimal ones. In this thesis, we propose multiple algorithms to improve the efficiency of SEA and we also tailor SEA to suboptimal search algorithms.
Our first proposition is a cost-based search ordering pattern for SEA, which is based on new insight that conventional search orderings can weaken the filtering criterion of SEA in a rateconstrained context. On average, for the H.264 reference software encoder, the number of sum of the absolute differences (SAD) operations is reduced by 2.86%. For smaller block sizes, this can exceed 10%.
Our second contribution is the sorted subset approach, a dynamic search ordering for SEA that avoids performing unnecessary cost function evaluations. On average, it reduces SAD operations by 3.66% for the HEVC reference software encoder. For smaller block sizes, the average rises to 8.06%.
Our third contribution to SEA is a fast cost-based search ordering algorithm. It decreases the number of SAD operations by approximately 3%. It allows for a new early-termination criterion which only requires performing 36% and 46% of block-matching loop iterations for Random Access and Low Delay respectively. This new solution is more than five times faster than the HEVC HM encoder in full search mode, without impact on visual quality or rate.
Our fourth contribution applies more generally to motion estimation and allows for an enhanced rate constraint. This rate constraint reuses information from the partitioning ME algorithms. When combined with the rate-constrained successive elimination algorithm (RCSEA) in the HEVC HM encoder reference software, the number of SAD operations drops by an average of 94.9%, resulting in an average speedup of 6.13x in full search mode.
Finally, our fifth contribution, is the multi-level rate-constrained successive elimination algorithm (ML-RCSEA) a derivative of the SEA designed to be used with the suboptimal ME algorithm implemented in the HEVC reference software encoder, the TZ-Search. It reduces the motion estimation time by approximately 45% contributing to an average encoding time reduction of about 7% without impact on visual quality or rate.
Trudeau, L. (Author),
Coulombe (Supervisor) &
Desrosiers (Co-supervisor),
11 Aug 2017Student thesis: Doctoral thesis › Doctorate in Engineering: Engineering