1Motion Estimation and Intra Frame Prediction in H.264/AVC EncoderRahul VanamUniversity of Washington2Motion EstimationH.264/AVC Encoder [2]3Motion Estimation• H.264 does block based coding.• Each frame is divided into blocks of 16x16 pixels called macroblocks (MB).• Each MB can be encoded using blocks of pixels that are already encoded within the current frame -Intra frame coding.• MBs can be coded using blocks of pixels in previous or future encoded frames -Inter frame coding.• The process of finding a match of pixel blocks in inter frame coding is called Motion Estimation.4Macroblock Partitions16x168x8 8x88x8 8x816x816x88x168x1616x16 16x168x84x44x44x44x48x4 8x48x84x84x88x816x16 blocks can be broken into blocks of sizes 8x8, 16x8, or 8x16.8x8 blocks can be broken into blocks of sizes 4x4, 4x8, or 8x4. 5Sub-pixel Motion Estimation• Compute the block distortion at each pixel position within the searchwindowInteger pixel search6Sub-pixel Motion EstimationInteger pixel searchCenter of best match• Find the position corresponding to the minimum block distortion27Sub-pixel Motion EstimationHalf pixel searchCenter of the best match• Half pixel motion estimation is then done where the best match wasfound in the integer pixel search step.8Sub-pixel Motion EstimationQuarter pixel searchCenter of the best match• Finally, quarter pixel motion estimation is done where the bestmatch was found from the half pixel search step, giving us the final motion vector.9Motion Estimation• Motion estimation is computationally expensive since – search is done at every pixel position– over different reference frames• There are several different fast integer search methods – diamond search, hexagon search, Simplified Uneven Multihexagon search (UMH), etc.10Diamond Search Algorithm• It uses large diamond search pattern of radius 2 and small diamond search pattern of radius 1.S. Zhu and K. K. Ma, IEEE CSVT 2000 Large diamond search patternSmall diamond search pattern11Diamond Search AlgorithmApply large diamond to the center of the search window12Diamond Search AlgorithmCompute the block distortions corresponding to all positions and check if the center position has the minimum distortion.?313Diamond Search AlgorithmMinimum distortionposition14Diamond Search AlgorithmThe minimum point in the previous step is the center position of this step.Apply large diamond to the new center position.Find the new minimum block distortion.If the center is not the minimum, move the center to the minimum point and reapply the large diamond pattern.Past search points Current search pointsPoints that overlap15Diamond Search AlgorithmIf the center is the minimum block distortion position, then apply a small diamond.16Diamond Search AlgorithmThe minimum block distortion position in this step gives the final motion vector. Final motion vector (3,0)Starting point(0,0)17Hexagon Search Algorithm• It consists of large hexagon pattern of radius 2 in horizontal and vertical direction, and small hexagon (or diamond) pattern of radius 1.• The search approach is similar to Diamond search.C. Zhu, X. Lin and L-P. Chau, IEEE CSVT, 2002 Large hexagon pattern Small hexagon pattern 18Hexagon Search AlgorithmApply large hexagon to the center of the search window.Compute the block distortions corresponding to all positions and check if the center position has the minimum distortion.?419Hexagon Search AlgorithmMinimum distortionposition20Hexagon Search AlgorithmThe minimum point in the previous step is the center position of this step.Apply large hexagon to the new center position.Find the new minimum block distortion.If the center is not the minimum, move the center to the minimum point and reapply the large hexagon pattern.Past search pointsCurrent search pointsPoints that overlap21Hexagon Search AlgorithmIf the center is the minimum block distortion position, then apply a small hexagon.22Hexagon Search AlgorithmThe minimum block distortion position in this step gives the final motion vector. Final motion vector (3,0)(0,0)23Hexagon Search Algorithm (HEXS)Comparison with Diamond search (DS)– HEXS uses fewer search points compared to diamond search (DS). In our example, HEXS requires 14 search points while DS requires 18 search points.– HEXS gives higher savings in searches for larger motion vectors.– HEXS results in slightly higher mean distortion compared to DS.24Intra-Frame PredictionH.264/AVC Encoder [2]525Intra-Frame Prediction• Intra modes for Luma samples– 9 modes for 4x4 blocks– 4 modes for 8x8 blocks• Intra modes for Chroma samples– 4 modes for 8x8 blocks26Intra Luma Prediction for 4x4 blocks• Samples a, b, …, p are predicted from samples A,…, M that have been encoded previously.njfbpomLlkiKhgeJdcaIG HFEDCBAMSamples to be intra predictedSamples that arealready encoded27Intra Luma Prediction for 4x4 blocks• The direction of prediction for 8 modes are shown above [2].• In Mode 2, the samples a,..,p are predicted using average of samples A,..,D and I,…,L.28Intra Luma Prediction for 4x4 blocksFive of the 9 intra 4x4 modes [3]29Intra Luma Prediction for 16x16 blocks• There are 4 modes– Mode 0: vertical prediction– Mode 1: horizontal prediction– Mode 2: DC prediction– Mode 4: Plane prediction• Intra chroma prediction has the same modes as above, but prediction is done for 8x8 chroma blocks.30Mode Decision16x16 luma MacroblockIntra Modes(For all frames)Inter Modes (Only for P and B-frames)• Nine 4x4 Modes• Four 16x16 Modes• Macroblock partitions: 16x16,16x8,8x16, 8x8,8x4,4x8,4x4• Use of reference frames• Use of integer, half and quarter pixel motion estimation• Each mode (inter or intra) has an associated Rate-Distortion (RD) cost.• Encoder performs mode decision to select the mode having the least RD cost. This process is computationally intensive.631References1. I.E.Richardson, “H.264 and MPEG-4 video compression,” Wiley, 2003.2. G. J. Sullivan, P. Topiwala, and A. Luthra, “The H.264/AVC Advanced Video Coding Standard:Overview and Introduction to the Fidelity Range Extensions,” SPIE Conference on Applications of Digital Image Processing XXVII, August, 20043. T. Wiegand, G. J. Sullivan, G. Bjøntegaard, and A. Luthra, “Overview of the H.264/AVC Video Coding Standard,” IEEE CSVT, Vol.13, pp. 560-576, July
View Full Document
Unlocking...