Predictive Hybrid Fast Motion Estimation Algorithm For High Efficient QFHD Video Coding

Predictive Hybrid Fast Motion Estimation Algorithm For High Efficient QFHD Video Coding

Harini. R.

PG Student,

1. pplied Electronics, ECE Department Meenakshi College of Engineering Chennai, India

   R.Vani

   Associate Professor, ECE Department

   Meenakshi College of Engineering Chennai, India

   Abstract–Motion estimation in H.264 standard a video compression scheme is used to outperform various other coding standard. Since high quality video requirements is becoming demanded now a days. Motion estimation algorithm makes use of motion vectors in proposing efficient video estimation with advantages of increase in speed and signal to noise ratio. In this paper, Enhanced Predictive Zonal Search Motion Early Termination (EPZS MET) method is being used that can save a greater percent of estimated time by searching macroblocks that is being terminated early by employing threshold based predictors. The proposed approach is simulated using MATLAB whereby overcoming the expensive search delay in existing approaches without affecting the accuracy.

   Keywords-Motion Estimation (ME), Motion Early Termination (MET), Enhanced Predictive Zonal Search (EPZS).

   1. INTRODUCTION

      High quality video requirements are gaining a greater importance because of its higher resolution than the normal standard definition. The resolution being defined is determined by the display which stands as a result of vertical and horizontal lines or visible lines. The design of video coding standard aims at having the highest coding efficiency. Coding efficiency is the technique or the ability to encode the video at lowest possible rate. Motion estimation can also be given as video compression technique that is defined by adjacent frames which enables to determine the motion vectors which results in the transformation of one image to another. These motion vectors may relate to the whole image or specific blocks in an image. A frame in an image is selected as a reference and subsequent frames are being predicted using motion estimation, which analyzes previous or future frames to identify blocks that havent changed and motion vectors are being stored in place of blocks.

      MATLAB, a numerical computing environment and forth generation programming language is being used to carry out the process of estimating the motion vectors and resulting transformation or compression. .Quality High Definition is a resolution standard for monitors or any other electronic devices designed. It is a much greater standard of high definition .This QHD resolution is suitable for bigger screen

      or large sized devices. HEVC was designed to improve the coding efficiency which is the main aim of many video coding standard. This is best featured since it targets with scheduling and scanning process resulting in much better picture quality.

      The paper is organized as follows: Section II explains about the existing overview of the algorithms. Section III explains the proposed EPZS MET algorithm

      .Section IV discusses about results and comparison. Finally, Section V provides the conclusion.

   2. EXISTING OVERVIEW

      The existing algorithm makes use of motion vectors but with a difference of comparing it to the current position and search stopped if the value ought to be larger than the threshold whereby in the end reduces overall quality. Full search algorithm imbibes no technique rather searches every pixel to match between frames which consumes greater time. Diamond search algorithm works on pixels in a diamond mannerism between frames so as to estimate motion vectors and consumes less time than that of full search.

      The cross diamond search algorithm proposed by C.H.Cheung & PO.L.M[2] which employed half way stop techniques with fewer search points. This pattern design was evaluated using directional descriptors. Fractional Motion Estimation technique put forth by Dikbas.S,Arici.T, & Altunbasak.Y[4] searches the sub-pixels in the blocks of various sizes which showed a better compression efficiency but of high computational complexity.H264 was a video coding standard proposed by Lin.Y.K.,Lin.C.C, Kuo.T.Y.And Chang.T.S[6] to increase the coding efficiency with significant increase in computational complexity.Jie & Lei proposed a large coding unit in HEVC. Further a fast coding unit decision algorithm was used to accelerate the encoding procedure. This performed in average encoding time with negligible drop of rate distortion performance.

      The Quad tree based inter-prediction technique put forth by Shiau-Yu Jou ; Chiao-Tung Univ., Hsinchu, Taiwan

      ; Tian-Sheuan Chang[7] gives good efficiency and this also poses a fast pixel unit selection method which helps instead of exhaustive search. High Efficient video coding standard

      was put as newest coding standard for video by MPEG group which enabled significant compression performance and achieved 50%bit rate reduced with same video quality.

   3. PROPOSED ALGORITHM

      The proposed EPZS MET involves considerable Sum of Absolute Differences(SAD) computations along with the HEVC. Each SAD computation for the size that stays larger is computed by downsampling where this speeds up the process because downsampling is performed in both dimensions. Moreover, EPZS is considerably less complex than full search motion estimation but involves a large no of motion vectors. The proposal is to enhance predictive

      STEP 5:

      Examine the results.

      The distortion between original block and prediction block obtained by means of such MV is computed. In conventional HEVC, this happens by means of the Sum of Absolute Differences (SAD) metric. Formally denote as X[h;w] and P[h;w] the samples in the original block X and prediction block P respectively, where h = 0; :::;H – 1, w = 0;

      :::; W – 1 and where H and W are the blocks height and width respectively.

      Then the SAD is computed as shown in (1):

      algorithm in examining more MV predictors and finally selecting the best as final predictor to be used for evaluation.

      = |[, ][, ]|

      (1)

      In particular, as of slow motion sequences or static areas, the motion search starting point is already capable of sufficient accuracy prediction but only after examining all motion vectors ,reaches an optimal solution. Initially let us consider a set of possible MV starting points as MV0, MV1,…. The first MV starting point is derived as the (component-wise) median of the MVs that are used during the MV prediction process. The second MV starting point is the zero-valued MV (i.e. a MV whose components are both 0). Finally, up to 3 other c MV starting points are considered. The available MVs are included in the list of possible candidate starting point and a minimum of 2 and maximum of 5 MVs may be considered. Since the best starting point is used for the further process of EPZS algorithm it is expected to yield better accuracy result.

      The algorithm for EPZS block prediction has the following steps:

      STEP 1:

      Each thread loads a part of the block (8 pixels) in the current frame to private memory.

      STEP 2:

      Load each vector predictor and check whether its (Sum of Absolute Differences) SAD is better than current, following these steps:

      1. Load in shared memory the block in the reference frame pointed by the motion vector.

      2. Compute the SAD for the region inside the block.

      3. Compute the SAD reduction.

      4. The first thread in the group of 32 checks whether the SAD + vector cost is lower than the previous best one and, in case it is, set the current candidate as the current best solution.

      STEP 3:

      Perform small diamond search in the region pointed by the best predictor until convergence. Each candidate vector in the diamond pattern uses the steps (a) – (d) described above.

      STEP 4:

      Perform sub-pixel search.

      The distortion is then adjusted with an estimate of the rate

      necessary to encode the corresponding MV to obtain an estimated RD cost C.

      This is typically computed as given in (2):

      C=SAD+ (2)

      where is a predefined Lagrangian multiplier, and RMV is defined as in (3):

      = + (3)

      where bX and bY are the number of bits necessary to encode the x and y for MV component respectively.

   4. RESULTS AND COMPARISON

      A successful design of multiple early termination Enhanced Predictive Zonal Search algorithm is developed and implemented in MATLAB Graphical User Interface(GUI) tool. EPZS MET has the unique advantage of balancing the bandwidth and high speed digital demands of a HQ video broadcasting. Existing approaches of full and diamond searches are following a technique of expensive motion vector search delay for achieving high quality video estimation. But the proposed approach has the capability to terminate the searching points before its arbitrary iteration, when the threshold based predicative descriptors are used to bypass the arbitrary detour for processing the entire motion vector patterns.

      The default initialization method for a video motion estimation is frame subtraction of the current and next image frames which will used for eliminating the non-movable objects in the video frames. A motion detection algorithm begins with the segmentation part where foreground or moving objects are segmented from the background. The simplest way to implement this is to take an image as background and take the frames obtained at the time t, denoted by I(t) to compare with the background image denoted by B.

      Fig.1. FRAME n

      the sequence were small, or motion was not zero biased, the algorithm could potentially have problems and in the end reduce the overall quality. Instead, in the EPZS algorithm an entirely different approach was used. Even though a fixed threshold was also used after examining the primary, median predictor, this was significantly smaller, thus reducing potentially harmful early terminations. Furthermore, additional early stopping criteria were introduced after all predictors were examined.

      The sethough were adaptively selected and calculated by considering correlations that existed between blocks and frames. In particular, if the current minimum SAD value is below a threshold selected as the minimum of the SAD values of the three adjacent blocks, the search stops. The search also stops if the current best motion vector is the same with the motion vector, and has a smaller SAD value than that, of the collocated block in the previous frame. These thresholding values were though restricted with fixed limits in order to avoid and reduce possible errors resulting from the early termination.

      The Experimental Setup is explained as follows: A car racing input video as shown in Figure 3 which consists of a 95 image frames are taken as test video input for Full search algorithm, every video frames are encoded as motion vectors and reconstructed in the receiver end, The Peak signal to Noise ratio between the original image frame and the reconstructed image frame is calculated using the formula(4) and mean square error using(5).

      = () (4)

      =

      ×

      =

      =

      [(, ) (, )](5)

      Fig 2. FRAME n+1

      Here using simple arithmetic calculations, segmenting out the objects simply by using image subtraction technique as of frame n and frame n+1 as shown in Figure 1 and Figure 2 of computer vision meaning for each pixels in I(t), take the pixel value denoted by P[I(t)] and subtract it with the corresponding pixels at the same position on the background image denoted as P[B].

      The background is assumed to be the frame at time t. This difference image would only show some intensity for the pixel locations which have changed in the two frames. Though we have seemingly removed the background, this approach will only work for cases where all foreground pixels are moving and all background pixels are static A threshold "Threshold" is put on this difference image to improve the subtraction .

      In the existing algorithm after examining the (0,0) motion vector, a single fixed thresholding value was compared to the current position SAD, and if it was larger the search immediately stopped. Even though such a technique enhanced speed up considerably, considering also that the threshold used was not minor, for cases where variations in

      Fig 3. INPUT VIDEO

      A full search of all potential blocks however is a computationally expensive task. Typical inputs are a macroblock of size 16 pixels and a search area of p = 7 pixels.Diamond Search (DS) algorithm uses a diamond search point pattern and the algorithm runs exactly the same as 4SS. However, there is no limit on the number of steps that the algorithm can take Diamond Search algorithm has a peak

      signal-to-noise ratio close to that of Exhaustive Search with significantly less computational expense.

   5. CONCLUSION

A successful design of multiple early termination enhanced predictive zonal search algorithm is developed and implemented in MATLAB GUI tool. EPZS MET has the unique advantage of balancing the bandwidth and high speed digital demands of a HQ video broadcasting. Existing approaches of full and diamond searches are following a technique of expensive motion vector search delay for achieving high quality video estimation. But the proposed approach has the capability to terminate the searching points before its arbitrary iteration, when the threshold based predictive descriptors are used to bypass the arbitrary detour for processing the entire motion vector pattern.

REFERENCES

1. Chen.T.C., et al., Analysis and architecture design of an HDTV720p 30 frames/s H.264/AVC encoder, IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 6, pp. 673688, Jun. 2006.

2. Cheung.C.H., and Po.L.M., A novel cross-diamond search algorithm for fast block motion estimation, IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 12, pp. 11681177, Dec. 2002.

3. Chih-Chuan Yang ; Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan ; Kheng-Joo Tan ; Yao-Chang Yang ; Jiun-In Guo,Low complexity fractional motion estimation with adaptive mode selection for h.264/avc 2010 IEEE International Conference on July 2010

4. Dikbas.S,Arici.T, and Altunbasak.Y, Fast motion estimation with interpolation-free sub-sample accuracy, IEEE Trans. Circuits Syst.Video Technol., vol. 20, no. 7, pp. 10471051, Jul. 2010.

5. 5.Jing-Fu Chang, Jin-Jang Leou,A quadratic prediction based fractional-pixel motion estimation algorithm for h.264 Journal of Visual Communication and Image Representation,Volume 17, Issue 5, October 2006.

6. Lin.Y.K.,Lin.C.C,,Kuo.T.Y.and Chang.T.S. A hardware efficient H.264/AVC motion estimation design for high definition video,IEEE Transaction circuits syst.,Reg papers,vol. 55,no. 6, pp.1526- 1535,jun.2008.

7. 7.Shiau-Yu Jou ; Graduated Inst. of Electron. Eng., Nat. Chiao-Tung Univ., Hsinchu, Taiwan ; Tian-Sheuan Chang,Fast prediction unit selection for hevc fractional pel motion estimation designSignal Processing Systems (SiPS), 2013 IEEE Workshop on16-18 OCT 2013.

8. 8.Sinangil.M.E., Sze.V.,Minhua.Z., and Chandrakasan.A.P, Cost and coding efficient motion estimation design considerations for High Efficiency Video Coding (HEVC) standard, IEEE J. Sel. Topics Signal Process., vol. 7, no. 6, pp. 10171028, Dec. 2013.

9. 9.Sullivan,G.J., Ohm.J.R, Han.W.J. and Wiegnd.T, Overview of the High Efficiency Video Coding (HEVC) standard, IEEE Trans. Circuit Syst. Video Technol., vol. 22, no. 12, pp. 16491668, Dec. 2012

10. 10.Zhao.Z and Liang.P., A statistical analysis of H.264/AVC FME mode reduction, IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 1,pp. 5361, Jan. 2011.