<figure><img src="image_1.png" /></figure>

HAL
open science

# A Coding Efficiency Improvement Algorithm for Future Video Coding

Xiantao Jiang, Xiaofeng Wang, Yadong Yang, Tian Song, Wen Shi, Takafumi Katayama

► To cite this version:

Xiantao Jiang, Xiaofeng Wang, Yadong Yang, Tian Song, Wen Shi, et al. A Coding Efficiency Improvement Algorithm for Future Video Coding. 2nd International Conference on Intelligence Science (ICIS), Oct 2017, Shanghai, China. pp.279-287, 10.1007/978-3-319-68121-4_30. hal-01820927

HAL Id: hal-01820927

https://inria.hal.science/hal-01820927

Submitted on 22 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Coding Efficiency Improvement Algorithm for Future Video Coding

Xiantao Jiang¹*, Xiaofeng Wang¹, Yadong Yang¹, Tian Song², Wen Shi², and Takafumi Katayama²

¹Department of Information Engineering, Shanghai Maritime University, Shanghai, China.

²Department of Electrical and Electronics Engineering, Tokushima University, Tokushima, Japan.

**Abstract.** Motion estimation is critical in motion coding. However, the fixed pattern of search center decision method in HEVC is lack of precision. Taking advantage of the surrounding coding unit information, a universal motion vector prediction framework is presented to improve the coding efficiency in HEVC. The proposed framework is composed of two parts: motion vector prediction (MVP) and search range (SR) selection. Firstly, a novel motion vector prediction (NMVP) method is presented to improve the coding efficiency. Secondly, an adaptive search range selection (ASRS) method is developed to reduce the coding complexity in motion estimation. The simulation results demonstrate that the overall bitrate can be reduced by 5.49% on average, up to 9.18% compared with HEVC reference software.

**Keywords:** High Efficiency Video Coding, Coding Efficiency, Motion Vector Prediction, Search Range.

## 1 Introduction

In HEVC standard, the performance of motion estimation (ME) highly depended on the selection of advanced motion vector prediction (AMVP) technology[1]. The motion vector prediction (MVP) is selected from a motion vector candidate list which consists of one motion vector from neighboring units on the left of the current coding unit, one motion vector from above neighboring units, and the motion vector of the spatially the same position in the previous encoded frame. And the motion vector in the list with minimum cost is selected as the final MVP. AMVP is significantly simplified to provide a good trade-off between coding efficiency and an implementation cost. However, the fixed pattern of the MVP decision process without consideration of the reliability of the surrounding motion vectors makes it has lower estimation accuracy.

<footnote>* Corresponding author</footnote>
Some previous works are proposed to improving the performance of MV coding. The main idea based on the spatial and temporal MVP candidate schemes for video coding have one assumption in common. The motion of neighboring blocks has to be similar [2]-[8]. Lin et al. present a new location of the temporal motion vector predictor, a priority-based derivation algorithm of spatial and temporal MVPs [1, 2]. Jung et al. propose the motion vector competition (MVC) scheme to select one motion vector predictor among the given motion vector candidates [3]. These methods can increase the coding efficiency of motion vector coding in HEVC. Yang et al. define a predictor candidate set, and the motion vector predictor can be generated by the minimum motion vector difference criterion [4]. Chien et al. design an enhanced AMVP mechanism to get an accurate motion vector predictor [5]. However, the spatial and temporal MVP candidates lack precision, and these approaches improve the performance of motion vector coding limitedly.

Motion estimation is a core part of video coding, and it can improve the coding efficiency significantly. Meanwhile, the coding complexity has significantly increased. Some adaptive search range (SR) methods have been presented to reduce the encoding complexity. Determining a suitable SR, they can be classified two categories: MV-based method and SAD-based method.

The MV-based methods [10]-[15] persist in that, when the distribution of the MVD is concentrated in zero with a small variance, the SR can be adjusted to the small. Lou et al. present an adaptive motion search range method to reduce the memory access bandwidth [10]-[12]. In this method, an applicable SR is chosen to contain the optimal MV by using a probability model. In Dai's work [13], an adaptive SR method is proposed by using a Cauchy distribution. These methods can reduce the encoding complexity significantly.

The SAD-based methods [16]-[17] set a threshold on SAD value to decide whether the video content is motion or not. However, the SAD-based methods are unreliable.

In summary, a universal motion vector prediction framework is proposed to improve the coding efficiency in this work. For the fixed pattern of MV coding in HEVC, the main disadvantages of the previous work are that the precision is not sufficient and the robustness is not high. Firstly, a novel motion vector prediction method is used to generate the optimal MV. For the fixed SR adopting in motion search processing, there are a large number of redundant computation. Thus, an adaptive search range selection method is developed to reduce the encoding complexity of ME owing to the benefit of the accurate motion vector prediction. Different from the state-of-the-art, my approach treats the MVP selection and the SR selection jointly.

# 2 Proposed Method

## 2.1 Novel Motion Vector Prediction (NMVP)

Considering the video content with strong spatial correlations, motion vector predictor of the current CU can be generated from the adjacent CUs. The novel
motion vector prediction is based on the previous work [9]. Different from the fixed pattern AMVP technology, the spatial neighborhood cluster G is composed of all spatial neighbor CUs. The cluster G is shown as in Fig.1. Where $CU_L$,

<figure><img src="image_3.png" /><figcaption>Fig. 1: Spatial Correlation Neighborhood Cluster.</figcaption></figure>

$CU_{TR}$ and $CU_{TL}$ denote the left, top right and top left CU of the current CU, separately. The cluster G is defined as

$$G = \{CU_L, \dots, CU_{TL}, \dots, CU_{TR}\} \qquad (1)$$

The MVs and depths information of G can be used to predict the MVP of the current CU. However, the computation complexity is high by the checking all of the information. Thus, the relatively reliable sub-cluster should be developed for the MVP. Therefore, in order to utilize the spatial correlation, the sub-cluster M is defined as

$$M = \{CU_L, CU_{TL}, CU_{TR}\} \qquad (2)$$

The sub-cluster M is contained in the cluster G ($M \subset G$). $MV_L$, $MV_{TR}$ and $MV_{TL}$ indicate the MV candidates in the left, top right and top left of the current CU.

The basic idea of the proposed MVP method is to prejudge the MVP of the current CU according to the MVs of the spatial adjacent CUs. When the sub-cluster M is available, the information of M is used to predict the MVP of the current CU. In contrast, when the sub-cluster M is unavailable, the information of G is used to predict the MVP of the current CU.

When the MVs of sub-cluster M are available, a simple MV can be selected as the optimized MV for the current CU. On the contrary, when the MVs of sub-cluster M are not available, the reliability of the candidate MVs is the lowest and it is hard to get the accurate MVP using the fixed AMVP mechanism. In this case, the MVP position may tend to be near to the left of CU, and it is possible to tend to be near to the top of CU. Thus, all available MVs of the
spatial neighborhood cluster G need to be checked. In order to get the accurate MVP, all surrounding MVs of G can be added to the candidates MVs, and the cost of these MVs are checked to get the optimized MVP.

## 2.2 Adaptive Search Range Selection (ASRS)

An accurate MVP is critical to SR reduction. In this subsection, the importance of the MVP to the SR reduction is studied. As to the SR, the optimized MV is close to the MVP so that a smaller SR can be used in the ME. In the contrast, a larger SR should be used in the ME if the optimized MV is far away the MVP. The difference between the optimized MV and the MVP is named the MV prediction difference (MVPD). Thus, when the distribution of the MVPD is concentrated near the center with a small variance, a smaller SR can be adopted.

Previous works on adaptive search range selection (ASRS) methods are reported in [10] and [12]. The MV variance ($\sigma^2$) of the spatial and temporal neighboring CUs is used to adjust the search range in ME. In these methods, the Cauchy distribution is proposed to model the distribution of the MVPD. The probability density function of MVPD is used to calculate the probability of the optimized MV within the SR in [10], the probability density function of zero mean Cauchy distribution is can be defined as

$$f_{ME}(x, y) = f_{ME,X}(x) \cdot f_{ME,Y}(y) \qquad (3)$$

$$f_{ME,X}(x) = \frac{C_x}{\left|\frac{x}{\zeta_x}\right|^{\frac{5}{3}} + 1} \qquad (4)$$

$$f_{ME,Y}(y) = \frac{C_y}{\left|\frac{y}{\zeta_y}\right|^{\frac{5}{3}} + 1} \qquad (5)$$

where $C_x$, $C_y$ are normalization constants, and $\zeta_x$ and $\zeta_y$ are parameters of the modified zero-mean Cauchy function, which can be computed by the sample variances of MVPDs ($\sigma^2$). Thus, the probability of the optimized MV can be defined as

$$F_{ME}(SR_x, SR_y) = F_{ME,X}(SR_x) \cdot F_{ME,Y}(SR_y) \qquad (6)$$

$$F_{ME,X}(SR_x) = \int_{-SR_x-0.5}^{SR_x+0.5} f_{ME,X}(x)dx \qquad (7)$$

$$F_{ME,Y}(SR_y) = \int_{-SR_y-0.5}^{SR_y+0.5} f_{ME,Y}(y)dy \qquad (8)$$

where $SR_x$ and $SR_y$ are horizontal and vertical component of search range, separately. For the given probability $C_{prob}$ that denotes the search range contains
the optimized MV, the dynamic search range can be determined by the closest SR with a probability no less than $C_{prob}$, and it satisfies

$$F_{ME,X}(SR_x) = F_{ME,Y}(SR_y) = \sqrt{C_{prob}} \qquad (9)$$

where the computational dynamic search range can be represented by $SRx\_dyn$ and $SRy\_dyn$, respectively. In this work, the default SR is represented by $SR\_def$. When the MVP is accurate enough, the minimal search range (represented by $SRx\_min$ and $SRy\_min$) is set to 1/8 of the default SR.

<figure><img src="image_4.png" /><figcaption>Fig. 2: Search range refinement</figcaption></figure>

Recall that the spatial correlation based MVP decision algorithm is studied in above section, and the reliability of the neighboring candidate MVs is used to get the optimized MVP. To treat the MVP selection and the SR reduction jointly, when a high precision MVP is selected to be close to the optimized MV, the SR will be small. An example of the search range refinement method is shown in Fig.2. In this case, the SR of modified search range is set to $SR_x$ and $SR_y$, while the default SR ($SR\_def$) is set to 64 × 64 in the ME of HEVC reference software.

## 2.3 Universal Motion Vector Prediction Framework

Jointing the NMVP and ASRS methods together, the universal motion vector prediction algorithm is shown as algorithm 1. Firstly, the optimized MVP is decided by the MVs of the spatial neighbor CUs. Secondly, the search range is adjusted by the probability of the optimized MV within the SR and the reliability of the MV candidates. It is noted that, when the reliability of the neighboring candidate MVs is the highest, the SR can be reduced significantly and it is set to the ($SRx\_min$, $SRy\_min$). Moreover, when the reliability of the neighboring
candidate MVs is the lowest, the SR is set to the {$\min(SR\_def, SRx\_min + SRx\_dyn), \min(SR\_def, SRy\_min + SRy\_dyn)$} respectively.

<table><caption>**Algorithm 1:** Universal motion vector prediction.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Start inter prediction for CU</td></tr><tr><td>2</td><td>if the sub-cluster M exist then</td></tr><tr><td>3</td><td>if MV<sub>TR</sub> = MV<sub>TL</sub> = MV<sub>L</sub> then</td></tr><tr><td>4</td><td>MV<sub>L</sub> is selected as best MVP;</td></tr><tr><td>5</td><td>SR<sub>x</sub> = SRx_min, SR<sub>y</sub>=SRy_min;</td></tr><tr><td>6</td><td>else if |MV<sub>TR</sub> - MV<sub>TL</sub>|>|MV<sub>TL</sub> - MV<sub>L</sub>| then</td></tr><tr><td>7</td><td>Add MV<sub>TL</sub> and MV<sub>L</sub> to MV candidate list;</td></tr><tr><td>8</td><td>SR<sub>x</sub> = min(SR_def, SRx_min + SRx_dyn);</td></tr><tr><td>9</td><td>SR<sub>y</sub>=min(SR_def, SRy_min + SRy_dyn);</td></tr><tr><td>10</td><td>else</td></tr><tr><td>11</td><td>Add MV<sub>TR</sub> and MV<sub>TL</sub> to MV candidate list;</td></tr><tr><td>12</td><td>SR<sub>x</sub> = min(SR_def, SRx_min + SRx_dyn);</td></tr><tr><td>13</td><td>SR<sub>y</sub>=min(SR_def, SRy_min + SRy_dyn);</td></tr><tr><td>14</td><td>else</td></tr><tr><td>15</td><td>Add all MVs of the cluster G to MV candidate list;</td></tr><tr><td>16</td><td>Reduce the redundant MV candidates;</td></tr><tr><td>17</td><td>SR<sub>x</sub> = min(SR_def, SRx_min + SRx_dyn), SR<sub>y</sub>=min(SR_def, SRy_min + SRy_dyn);</td></tr><tr><td>18</td><td>Process motion search</td></tr></tbody></table>

## 3 Experiment Results

The proposed algorithm is implemented and verified based on HEVC test model HM16.12. The test conditions are set to evaluate the performance of the proposed algorithm at different profiles (RA and LD)[18]. The quantization parameters ($QP_i$) are set to 22, 27, 32 and 37, respectively. In this work, the search strategy is TZsearch, and the SR is adjusted adaptively.

The performance of the proposed algorithm is evaluated Bjontegarrd Delta bitrate (BDBR)[19], and the average time increasing (TI) is defined as

$$TI(\%) = \frac{1}{4} \sum_{i=1}^{i=4} \frac{T_{Pro}(QP_i) - T_{HM}(QP_i)}{T_{HM}(QP_i)} \times 100\% \quad (10)$$

where $T_{HM}(QP_i)$ and $T_{Pro}(QP_i)$ are the encoding time by using the HEVC reference software and the proposed method with different $QP_i$.

Table 1 shows the performance of the universal motion vector prediction algorithm. In RA case, the bitrate can be reduced by 5.49% on average, while
<table><caption>Table 1: Performance of universal motion vector prediction.</caption><thead><tr><th rowspan="2">Class</th><th rowspan="2">Sequence</th><th colspan="2">RA</th><th colspan="2">LD</th></tr><tr><th>BDBR</th><th>TI (%)</th><th>BDBR</th><th>TI (%)</th></tr></thead><tbody><tr><td rowspan="5">1920 × 1080</td><td>Kimono</td><td>-5.92</td><td>51.64</td><td>-4.46</td><td>45.41</td></tr><tr><td>ParkScene</td><td>-4.35</td><td>56.79</td><td>-4.88</td><td>52.13</td></tr><tr><td>Cactus</td><td>-4.76</td><td>54.68</td><td>-4.55</td><td>48.29</td></tr><tr><td>BasketballDrive</td><td>-7.85</td><td>51.14</td><td>-6.04</td><td>51.03</td></tr><tr><td>BQTerrace</td><td>-2.15</td><td>54.67</td><td>-2.77</td><td>50.59</td></tr><tr><td rowspan="3">1280 × 720</td><td>Vidyo1</td><td>-3.61</td><td>63.92</td><td>-5.30</td><td>60.75</td></tr><tr><td>Vidyo3</td><td>-4.66</td><td>59.53</td><td>-4.29</td><td>51.20</td></tr><tr><td>Vidyo4</td><td>-5.17</td><td>59.12</td><td>-5.84</td><td>52.72</td></tr><tr><td>High Resolution</td><td>Average</td><td>-4.81</td><td>56.44</td><td>-4.77</td><td>51.52</td></tr><tr><td rowspan="4">832 × 480</td><td>BasketballDrill</td><td>-7.30</td><td>48.46</td><td>-7.13</td><td>42.56</td></tr><tr><td>BQMall</td><td>-4.69</td><td>53.65</td><td>-5.10</td><td>47.36</td></tr><tr><td>PartyScene</td><td>-4.60</td><td>45.68</td><td>-4.51</td><td>35.83</td></tr><tr><td>RaceHorses</td><td>-8.93</td><td>41.63</td><td>-6.72</td><td>33.40</td></tr><tr><td rowspan="4">416 × 240</td><td>BasketballPass</td><td>-6.18</td><td>56.13</td><td>-6.17</td><td>34.97</td></tr><tr><td>BQSquare</td><td>-2.79</td><td>54.77</td><td>-3.84</td><td>36.29</td></tr><tr><td>BlowingBubbles</td><td>-5.74</td><td>47.41</td><td>-5.92</td><td>36.59</td></tr><tr><td>RaceHorses</td><td>-9.18</td><td>18.89</td><td>-7.95</td><td>40.23</td></tr><tr><td>Low Resolution</td><td>Average</td><td>-6.18</td><td>45.83</td><td>-5.92</td><td>38.40</td></tr><tr><td>Average</td><td></td><td>-5.49</td><td>51.13</td><td>-5.34</td><td>44.96</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Fig. 3: R-D curve of BasketballDrive (RA).</figcaption></figure>
the encoding time increasing is 51.13%. In LD case, the bitrate can be reduced by 5.34% on average, while the encoding time increasing is 44.96%. The proposed algorithm can improve the coding efficiency significantly.

It is noted that, for the motion severe sequence, the proposed algorithm can improve the performance, which is the greatest contribution of this paper. The bitrate can be reduced by 7.85% for BasketballDrive sequence in RA case, and the R-D curve is shown as Fig.3.

It would be specially mentioned that this proposed method causes the encoding complexity increasing with the encoding efficiency raising. However, for the application that does not care about the real-time encoding, and care more about the coding efficiency, and it is an efficient approach for coding efficiency improvement in HEVC.

## 4 Conclusion

In this work, a universal motion vector prediction framework is presented to improve the performance of HEVC. The simulation results demonstrate that the proposed overall algorithm can improve the encoding efficiency by 5.34%-5.49% on average, which the encoding time increasing is about 45%-51%.

## References

1. J.L. Lin, Y.W. Chen, Y.W. Huang, and S.M. Lei, "Motion vector coding in the HEVC standard," IEEE Journal of Selected Topics in Signal Processing, vol. 7, no. 6, pp. 957-968, Dec. 2013.

2. J. L. Lin, Y. W. Chen, Y. P. Tsai, Y. W. Huang and S.M. Lei, "Motion vector coding techniques for HEVC," International Workshop on Multimedia Signal Processing (MMSP), pp. 1-6, 2011.

3. J. Jung, B. Bross, P. Chen, W.-J. Han, "Description of Core Experiment 9 (CE9): MV Coding and Skip/Merge operations," Document of Joint Collaborative Team on Video Coding, JCTVC-D609, Jan. 2011.

4. W. Yang, O. C. Au, J. Dai, F. Zou, C. Pang and Y. Liu, "Motion vector coding algorithm based on adaptive template matching," International Workshop on Multimedia Signal Processing (MMSP), pp. 222-227, 2010.

5. W. D. Chien, K. Y. Liao and J. F. Yang, "Enhanced AMVP mechanism based adaptive motion search range decision algorithm for fast HEVC coding," IEEE International Conference on Image Processing (ICIP), pp.3696-3699, Oct. 2014.

6. M. Tok, A. Glantz, A. Krutz and T. Sikora, "Parametric motion vector prediction for hybrid video coding," Picture Coding Symposium (PCS), pp. 381-384, 2012.

7. M. Tok, V. Eiselein, T. Sikora, "Motion modeling for motion vector coding in HEVC," Picture Coding Symposium (PCS), pp. 154-158, 2015.

8. D. Springer, F. Simmet, D. Niederkorn and A. Kaup, "Robust rotational motion estimation for efficient HEVC compression of 2D and 3D navigation video sequences," IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1379-1383, 2013.
9. Jin Ikegita, Xiantao Jiang, Tian Song, Jenq-Shiou Leu, Takashi Shimamoto. "Efficient Prediction Motion Vector Candidate Selection Algorithm for HEVC," ITC-CSCC:International Technical Conference on Circuits Systems, Computers and Communications, 2015,402-403.

10. C.C. Lou, S.W. Lee, C.C. Jay Kuo, "Motion vector search window prediction in memory-constrained systems," SPIE Optical Engineering Applications. International Society for Optics and Photonics, pp. 74430E-74430E, 2009.

11. C.C. Lou, S.W. Lee, C.C. Jay Kuo, "Adaptive search range selection in motion estimation," IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 918-921, 2010.

12. C.C. Lou, S.W. Lee, C.C. Jay Kuo, "Adaptive motion search range prediction for video encoding," IEEE Transactions on Circuits and Systems for Video Technology, vol.20, no.12, pp.1903-1908, 2010.

13. W. Dai, O. C. Au, S. Li, L. Sun and R. Zou, "Adaptive search range algorithm based on Cauchy distribution," Visual Communications and Image Processing (VCIP), pp. 1-5, 2012.

14. Z. Shi, W. A. C. Fernando, A. Fernando, "Adaptive direction search algorithms based on motion correlation for block motion estimation," IEEE Transactions on Consumer Electronics, vol.57, no.3, pp.1354-1361, 2011.

15. Y. H. Ko, H. S. Kang, S. W. Lee, "Adaptive search range motion estimation using neighboring motion vector differences," IEEE Transactions on Consumer Electronics, vol.57, no.2, pp.726-730, 2011.

16. S.W. Lee, S.M. Park, H.S. Kang, "Fast motion estimation with adaptive search range adjustment," Optical Engineering, vol. 46, no. 4, pp. 040504-040504-3, 2007.

17. S. Saponara, M. Casula, L. Fanucci, F. Rovati and D. Alfonso, "Dynamic control of motion estimation search parameters for low complex H. 264/AVC video coding," IEEE International Conference on Consumer Electronics, pp. 481-482, 2006.

18. F. Bossen, "Common test conditions and software reference configurations," JCTVC-L1100, Jan. 2013.

19. G. Bjontegaard, "Calculation of average PSNR differences between RD-curves," ITU-T SG16 Q.6, VCEG-M33, Apr. 2001.