Sang-hyo Park

Motion Estimation Skipping Strategies for Low-complexity HEVC Encoding

In video coding, motion estimation (ME) that predicts a block among temporally correlated frames has had a crucial impact on not only the compression efficiency, but also the computational complexity. Particularly, fast ME algorithms has been a pivot in much research that attempts to reduce the complexity of video encoder while preserving the compression efficiency as much as possible. However, the overall complexity of ME including time and memory complexity was increased much further in the high efficiency video coding (HEVC) codec to meet twice better coding efficiency than AVC/H.264 codec due to the diversified changes: more various motion partitions, more various motion directions, and more elaborated motion accuracy. Since encoder has to encode huge pixels due to the increased video resolution such as 4K ultra-high-definition (UHD) and 8K UHD, the complexity of ME should be overcome for low-complexity HEVC encoding.
To relieve the complexity of HEVC, two ME skipping strategies are proposed in this dissertation by considering those various changes of HEVC. One is a bidirectional motion estimation (BME) skipping strategy that avoids most compression-inefficient search points for bidirectional motion that has high computational complexity due to additional interpolation process in contrast with unidirectional motion estimation (UME). The proposed method exploits the stochastic correlation of the context of prediction units (PUs)—one of the special characteristic of HEVC—to determine whether BME is critical or not. The other is a skipping strategy of sub-pixel motion estimation (SME) that avoids inefficient search points of half-pixel and of quarter-pixel motions and skips associated interpolation process. Utilizing the correlation of the context of PUs, the second proposed method determines whether SME is critical or not during the encoding of UME and BME. The proposed method additionally checks SME for far reference frames from the current frames to decrease the complexity of SME further. When utilizing two proposed strategies, low-complexity HEVC encoding could be achieved, sustaining reasonable compression performance.
To demonstrate the performance of motion estimation skipping strategies, the following complexity measurement methods were carefully chosen: the number of related function calls, running time, and memory access count. Through experimental results, the proposed BME skipping strategy showed that the time complexity of bi-prediction can be reduced to 36% on average while losing a 0.5% increase of BD-rate, outperforming existing methods in view of encoding time, number of function calls, and memory access. In addition, the proposed SME skipping strategy showed that the time complexity of ME can be reduced to 51% (random access case) and 52% (low-delay case) on average, outperforming existing method. Therefore, the proposed two ME skipping strategies should be considered in low-complexity HEVC encoder for real-time broadcasting systems, surveillance applications, and mobile video encoding devices of battery-constraint.