Fast Block Based Motion Estimation Algorithms for Hevc

FAST BLOCK BASED MOTION ESTIMATION ALGORITHMS FOR HEVC

PROJECT INTERIM REPORTUNDERTHEGUIDANCEOF

DR.K.R.RAOCOURSE:EE5359-MULTIMEDIAPROCESSING,SPRING2015SUBMISSIONDATE:14thAPRIL 2015

SUBMITTED BY

VASIREDDY SRIKANTH

UT ARLINGTON ID:1001101538

EMAILID:

DEPARTMENTOFELECTRICALENGINEERING

UNIVERSITYOFTEXAS,ARLINGTON

Block based motion estimation [27] is a key component in video encoding leading to high compression although at high computational complexity. Motion estimation process has become a bottleneck problem in many video applications. Typical applications include HDTV, multimedia communications, video conferencing, etc. Motion estimation [1] is a useful in estimating the motion of any object. Motion estimation is used to identify moving image content in order to better exploit temporal redundancy.

This project aims at understand the various block matching motion estimation algorithms [27][29] for HEVC and analyze how fast the best match is selected. The simulation will be conducted using HM Software 16.0[17], with different video sequences [31], search range, block sizes. PSNR (dB), rate distortionplots and BD (Bjontegaard Delta) [9] results will be calculated for various algorithms. Also to find a trade-off between computational complexity, prediction quality, result quality and other various applications.

2.FundamentalsinVideo Coding

2.1Video and its Attributes

A video is nothing but a sequence of images. Figure 1 represents the attributes of video i.e. Height, Width, Frame rate and Pixel values .

Figure 1: Attributes of a Video [1][25]

2.2ColorSpaces

Thecommon colorspacesfordigital imageandvideorepresentationare:

RGB color space – Each pixel is represented by three numbers indicating the relativeproportionsof red, greenand bluecolors
YCrCbcolorspace–Yistheluminancecomponent,amonochromeversionofcolorimage.Yis a weighted averageofR,G andB:

YkrRkgGkbB,wherekaretheweightingfactors.

Thecolorinformationisrepresentedascolordifferencesorchrominancecomponents,whereeach chrominancecomponent is differencebetweenR, Gor Band theluminanceY.

Asthehumanvisualsystemislesssensitivetocolorthantheluminancecomponent,YCrCbhasadvantagesoverRGBspace.Theamountofdatarequiredtorepresentthechrominancecomponentreduceswithoutimpairingthe visualquality[1].The sampling patterns are shown in Figure 2.

Thepopular patternsofsampling [1] are:

4:4:4–ThethreecomponentsY:Cr:Cbhavethesameresolution,whichisforevery4luminancesamplesthereare 4Cr and4 Cbsamples.
4:2:2–Forevery4luminancesamplesinthehorizontaldirection,thereare2Crand2Cbsamples.Thisrepresentation is used forhigh quality videocolorreproduction.
4:2:0–TheCrandCbeachhavehalfthehorizontalandverticalresolutionofY.Figure 3 represents the 4:2:0 sampling pattern. Thisispopularlyused inapplicationssuch asvideo conferencing,digital television andDVDstorage.

Figure 2:4:2:0, 4:2:2 and 4:4:4 sampling patterns[1]

Figure 3:4:2:0 sub-sampling pattern[25]

2.3Need for Video Compression

Higher bit rates are required for uncompressed video. For example uncompressed 1080p HD video at 24fps has a bit rate of 1.2 Gbits/sec.Compression is achieved by removing the redundant information from video sequeunce by maintaining an ‘acceptable level’ of video quality.

3.HighEfficiencyVideoCoding

3.1Introduction

HighEfficiencyVideoCoding(HEVC)[12]isaninternationalstandardforvideocompressiondevelopedbyaworkinggroupofISO/IECMPEG(MovingPictureExpertsGroup)andITU-TVCEG(VideoCodingExperts Group).Themaingoalof HEVC standardisto significantly improvecompressionperformancecomparedtoexistingstandards(suchasH.264/AdvancedVideoCoding)intherangeof50%bitrate reductionat similarvisualquality.HEVC [25] isdesignedtoaddressexistingapplicationsofH.264/MPEG-4AVCandtofocusontwokeyissues:increasedvideoresolutionandincreaseduseofparallelprocessingarchitectures.Itprimarilytargetsconsumerapplicationsaspixelformatsarelimitedto4:2:08-bitand4:2:010-bit.Also HEVC is used in different kinds of applications like scalable video coding, multiview coding, and screen content coding. [25]

3.2EncoderandDecoderinHEVC

Sourcevideo,consistingofasequenceofvideo frames, isencodedorcompressedbyavideoencodertocreateacompressedvideobitstream.Thecompressedbitstreamisstoredortransmitted.Avideodecoderdecompressesthebitstream tocreatea sequenceof decodedframes[11].Figs.4-6 represents the steps followed by encoder and decoder.

Thevideo encoderperformsthefollowingsteps:

Partitioning eachpictureinto multipleunits
Predictingeachunitusinginterorintraprediction,andsubtractingthepredictionfromtheunit
Transformingandquantizingtheresidual(thedifferencebetweentheoriginalpictureunitandthe prediction)
Entropyencoding transform output,predictioninformation,modeinformationandheaders

Thevideo decoderperformsthefollowingsteps:

•Entropydecoding andextracting theelementsofthecoded sequence

•Rescaling andinverting the transform stage

•Predictingeach unit andadding theprediction tothe output ofthe inversetransform

•Reconstructing a decodedvideo image

Figure 4:BlockDiagramofHEVCCODEC[11]

Figure 5:BlockDiagramofHEVCEncoder[32]

Figure 6:BlockDiagramofHEVCDecoder[21]

3.3FeaturesofHEVC

3.3.1Partitioning

HEVCsupportshighlyflexiblepartitioning of avideosequence. Eachframe ofthesequence issplitupintorectangular or squareregions(units or blocks),each ofwhichis predictedfrompreviouslycodeddata.Afterprediction,anyresidualinformation istransformed andentropyencoded.

Eachcodedvideoframe,orpicture,ispartitionedintotilesand/orslices,whicharefurtherpartitionedintocodingtreeunits(CTUs) which are shown in Figs.7-8.TheCTUisthebasicunitofcoding,analogoustothemacro-blockinearlierstandards, andcan beup to 64x64pixels in size.

Acodingtreeunitcanbesubdividedintosquareregionsknownascodingunits(CUs)usingaquad-treestructure.EachCUispredictedusinginterorintrapredictionandtransformedusingoneormoretransformunits.

Figure7:Picture,Slice,CodingTreeUnit(CTU),CodingUnit(CU)[25]

Figure 8:CTU partitioning and corresponding coding tree structure [18]

3.3.2Prediction

Framesofvideoarecoded using intraor interprediction:

Intraprediction:EachPUispredictedfromneighbouringimagedatainthesamepicture,usingDCprediction(anaveragevalueforthePU),planarprediction(fittingaplanesurfacetothePU)ordirectionalprediction (extrapolating fromneighbouring data).

Interprediction:EachPUispredictedfromimagedatainoneortworeferencepictures(beforeorafterthecurrentpictureindisplayorder),usingmotion compensatedprediction.

Figure 9:Modesand angular intraprediction directions in HEVC [4]

3.3.3Motion Estimation and Motion Compensation[1]

Motion estimation (ME) refers to the process of determining motion vectors and representing the transition of objects in successive video frames. Motion estimation finds its applications in two main areas: reduction of temporal redundancy in video coders and representation of true motion of objects in real-time video applications. Motion estimation process in HEVC consumes more than 50% coding complexity or time to encode with equal perceptual quality.

Motion estimation creates a model of the current frame based on available data in one ormore previously encoded frames (‘reference frames’). These reference frames may be ‘past’frames or ‘future’ frames .The design goals for a motion estimation algorithm are to model the currentframe as accurately as possible (since this gives better compression performance) whilst maintaining acceptable computational complexity. Figure 10 represents the concept of Motion estimation.

Figure10:Motion Estimation and Motion Compensation Block Diagram[1]

3.3.4Block Matching Algorithms [27]

Blockbasedmotion estimation (BBME) is themost widely usedmotion estimation methodforvideocoding.Theunderlying supposition behind motion estimation is that the patterns corresponding to objects andbackground in a frame of videosequence move within the frame to frame The ideabehindblock matching is to divide the currentframe into a matrix of “macro blocks” that are then compared with corresponding block and its adjacent neighbors’ in the previousframe to create a vector thatstipulates the movement of a macro block from one location to another in the previousframe. This movement calculated for all the macro blocks comprising a frame, constitutes the motionestimated in thecurrent frame. Thesearch area for a goodmacro block match is constrained up to “p”pixels on all fours sides of the corresponding macro block in previous frame. This “p” is called as the search parameter. Figure 11 represents the block based motion estimation process. Larger motions require a larger p and the larger thesearch parameter the more computationally expensive the process of motion estimation process. Usually the macro block is taken as a square of side 16 pixels, and the search parameter p is 7 pixels.

Figure11: Block based Motion Estimation process [27]

Figure 12: Illustration of Motion Estimation process [27]

Blockmatchingalgorithm is themostpopularmotionestimation algorithm. Theblock-matching algorithms eliminatethetemporal redundancy, which is foundpredominantly in anyvideosequence. The idea behind blockmatching is to dividesframesintoequal sized non-overlappingblocks and calculatesthedisplacement of thebest-matchedblockfromtheprevious frame as themotionvectoroftheblock in the current frame withinthesearch window. Duringblockmatching,each target block of thecurrent frame is compared with a previous frame in order to find the best matchingblock.Block-matchingalgorithmscalculatethe best matchusing Mean Absolute Difference(MAD).

There are different block matching algorithms as shown in Figure 13 likeFullSearchMotionEstimation,ThreeStepSearchAlgorithm,NewThree-StepSearchAlgorithm,Four-StepSearchAlgorithm,DiamondSearchAlgorithm,HexagonalSearch, multi-directional gradient descent search and the fast directional gradient descent search.[27][29]

Figure 13: Different Motion Estimation Algorithms[29]

3.3.4.1 Analysis of HEVC Fast Search in HM 16.0

The TZS algorithm is a mixture of diamond search and raster search patterns. The flowchart of the complete algorithm is shown in figure 11. The algorithm is broadly classified into four steps:

Motion Vector Prediction (MVP): TZS algorithm employs median predictor, left predictor, up predictor, upper right predictor. The minimum of these predictors is selected as a starting location for further search steps.

Figure 14: Flowchart of Fast Search Algorithm [29][36]

2. Initial Grid Search: In this step, the algorithm searches the search window in using diamond or square patterns with different stride lengths ranging from1 through 64, in multiples of 2. The patterns used are either 8-point diamond search or 8-point square search. A sample grid with stride length 8 for diamond is shown in figure 13.The motion vector with minimum SAD is taken as the center search point for further steps. The stride length for this minimum distortion point is stored in variable ‘uiBestDistance’. The maximum number of search points for this step, n1, is given by,

Where S is the size of search window, P is the number of search points per each grid (8 for diamond, 6 for hexagon etc.) and floor represents floor function.

3.Raster Search: The raster search is a simple full-search on a down-sampled version of the search window. A predefined value ‘iRaster’ for raster scan is set before compilation of the code [20]. This value is used as a sampling factor for the search window. The search window (for 16x16 search window) for raster scan with iRaster value ‘3’ is shown in Figure 13. The condition for performing the above raster search is that uiBestDistance obtained from previous step must be greater than iRaster. If this condition is not satisfied, the algorithm will skip the step. If the step is processed, then uiBestDistance is changed to iRaster value. As seen from Figure 10(c), the number of search points in each row or column would be ceil(S/R), where ceil represents ceiling function and R represents iRaster value. So the maximum number of search points in this step, n2, is given by,

4. Raster/Star Refinement: The Raster refinement is a fine refinement of the motion vectors obtained from the step 3. As shown in flowchart in Figure 11, either raster refinement or the square/diamond (star refinement) pattern refinement can be enabled. In general, only one of the refinement methods is enabled for fast computation. In both of these refinements, either 8-point square pattern or 8-point diamond pattern is used. The two refinement methods differ in their search operation. The raster-refinement will search by down-scaling the uiBestDistance value (obtained from raster search) by 2 in every step of the loop, till uiBestDistance equals to zero. The whole refinement process will only start if uiBestDistance is greater than zero. After every loop, the new stride length is stored in variable uiBestDistance. The search stops when uiBestDistance equals to zero. The total number of search points for this step (n3) depends on the video sequence and it is not constant for each iteration.

3.3.5 Transform and Quantization

AnyresidualdataremainingafterpredictionistransformedusingablocktransformbasedontheDiscreteCosineTransform(DCT)or4x4 intra Y DiscreteSineTransform(DST).Oneormoreblocktransformsofsize32x32,16x16,8x8and4x4areappliedtoresidualdataineachCU.Thenthetransformeddataisquantized [25].

3.3.6 Entropycoding

A coded HEVCbitstreamconsistsof quantizedtransformcoefficients,prediction information such aspredictionmodesandmotionvectors,partitioninginformationandotherheaderdata.Alloftheseelementsareencodedusing ContextAdaptiveBinaryArithmeticCoding (CABAC)[25].

4.Comparison Metrics

4.1PeakSignaltoNoiseRatio

Peaksignal-to-noiseratio(PSNR)isanexpressionfortheratiobetweenthemaximumpossiblevalue(power)ofasignalandthepowerofdistortingnoisethataffectsthequalityofitsrepresentation.Becausemanysignalshaveaverywidedynamicrange(ratiobetweenthelargestandsmallestpossiblevaluesofachangeablequantity),thePSNRisusuallyexpressedintermsofthelogarithmicdecibelscale.

PSNRismostcommonlyusedtomeasurethequalityofreconstructionoflossycompressioncodecs.Thesignalinthiscaseistheoriginaldata,andthenoiseistheerrorintroducedbycompression.Whencomparingcompressioncodecs,PSNRisanapproximationtohumanperceptionofreconstructionquality.AlthoughahigherPSNRgenerallyindicatesthatthereconstructionisofhigherquality,insomecasesitmaynot.Onehastobeextremelycarefulwiththerangeofvalidityofthismetric;itisonlyconclusivelyvalidwhenitisusedtocompareresultsfromthesamecodec(orcodectype)andsamecontent.

PSNRisdefinedviathemeansquarederror(MSE).Givenanoise-freemxnmonochromeimageIandits noisyapproximation K,MSEis definedas:

ThePSNRisdefinedas:

Here,MAXIisthemaximumpossiblepixelvalueoftheimage. For test sequences in 4:2:0 color format, PSNR is computed as a weighted average of luminance ( PSNRY ) and chrominance ( PSNRU , PSNRV) components [9] as given below:

4.2BjontegaardDeltaBitrate(BD-BR)andBjontegaardDeltaPSNR(BD-PSNR)

To objectivelyevaluatethecoding efﬁciencyof video codecs,BjontegaardDeltaPSNR(BD-PSNR)wasproposed.Basedontherate-distortion(R-D)curveﬁtting,BD-PSNRprovidesagoodevaluationoftheR-Dperformance [8][9].BDmetricsallowscomputingtheaveragegaininPSNRortheaveragepercentsavinginbitratebetweentworate-distortioncurves.However,BD-PSNRhasacriticaldrawback:Itdoesnottakethecoding complexityintoaccount[9].

4.3ImplementationComplexity

Thecomputationaltimeof different motion estimation algorithms ofHEVCwill becompared andthisserves as an indicationof implementation complexity.

5.Profile to be used

TheHM16.0mainprofile[17]with random access configuration will beusedforthisproject.This profile allows for a bit depth of 8-bits per sample with 4:2:0 chroma sampling, which is the most common type of video used with consumer devices.

6.Test Sequences

The following test sequences [31] of various resolutions are used for study of motion estimation algorithms for HEVC.

Test Sequence / Resolution / Frame rate (fps)
RaceHorses_416x240_30.yuv / 416 x 240 / 30
BQMall_832x480_60.yuv / 832 x 480 / 60
KristenAndSara_1280x720_60.yuv / 1280 x 720 / 60
ParkScene_1920x1080_24.yuv / 1920 x 1080 / 24

RaceHorses_416x240_30.yuv

BQMall_832x480_60.yuv

KristenAndSara_1280x720_60.yuv

ParkScene_1920x1080_24.yuv

Figure 15: Test Sequences [31]

7.Configuration Settings in HM 16.0

Test sequences in .yuv format are encoded using HM 16.0 [17].Different resolutions of test sequences are used. The main profile in HM 16.0 is used for running the test sequences. The following sections give brief description of configuration settings used in the encoding tools.

7.1Configuration of HM16.0

Main Random Access mode settings:

IntraPeriod : 64 # Period of I-Frame (-1 = only first)

GOPSize : 8 # GOP Size (number of B slice = GOPSize-1)

QP : 22 # Quantization parameter (0-51) (22, 27, 32 or 37 is used at a time)

FastSearch : 1 # 0: Full search 1: TZ search

SearchRange : 64 # (0: Search range is a Full frame)

Command line parameters for using HM 16.0 encoder:

TAppEncoder [-h] [-c config.cfg] [--parameter=value]

Options:

-h Prints parameter usage

-c Defines configuration file to use. Multiple configuration files may be used with repeated –c options.

--parameter=value Assigns value to a given parameter.

Sample command line parameters for HM 16.0 encoder:

E:\ HEVC\bin\vc10\Win32\Release\TAppEncoder.exe -c encoder_intra_main.cfg -wdt 416 -hgt 240 -fr 30 -f 20 -i RaceHorses_416x240_30.yuv

E:\ HEVC\bin\vc10\Win32\Release\TAppEncoder.exe -c encoder_intra_main.cfg -wdt 416 -hgt 240 -fr 30 -f 20 -i RaceHorses_416x240_30.yuv > E:\HEVC\results\RaceHorses_416x240_30 _logfile.txt (PRESS ENTER)

Figure 16: Snapshot of encoder_randomaccess_main.cfg[17][20]

7.2Testing Platform:

Processor / Intel Core(TM) i5 CPU 4210U 2.40 GHz
Number of cores / 2
Memory / 8GB
Operating System / 64 bit (x64-based processor),Windows 8.1

8.Simulation Results

Simulation results of all-intra configuration for the test sequences are tabulated in Tables 1-3:

RaceHorses_416x240_30.yuv, Number of frames encoded = 20
Random Access profile (FAST SEARCH) / Random Access profile (FULL SEARCH)
QP / PSNR in dB / Bit rate in kbps / Encoding time in seconds / PSNR in dB / Bit rate in kbps / Encoding time in seconds
22 / 39.5858 / 1504.992 / 120.810 / 39.5969 / 1494.096 / 1399.795
27 / 35.9841 / 769.740 / 101.093 / 35.9926 / 762.0240 / 1508.792
32 / 32.7600 / 391.116 / 88.600 / 32.7769 / 389.296 / 1306.499
37 / 30.1072 / 202.572 / 71.437 / 30.1423 / 202.3080 / 1231.534

Table 1: Results for RaceHorses_416x240_30.yuv sequence in Random Access Configuration

BQMall_832x480_60.yuv , Number of frames encoded = 20
Random Access profile (FAST SEARCH) / Random Access profile (FULL SEARCH)
QP / PSNR in dB / Bit rate kbps / Encoding time in seconds / PSNR in dB / Bit rate in kbps / Encoding time in seconds
22 / 40.6653 / 4538.160 / 308.840 / 40.7583 / 4528.440 / 4875.343
27 / 38.2347 / 2257.968 / 259.764 / 38.2446 / 2252.592 / 5214.150
32 / 35.4849 / 1200.864 / 244.682 / 35.4965 / 1196.352 / 4837.578
37 / 32.7343 / 656.088 / 224.326 / 32.7370 / 655.2240 / 5248.942

Table 2: Results for BQMall_832x480_60.yuv sequence in Random Access Configuration

KristenAndSara_1280x720_60.yuv

Number of fames encoded =20

/ ParkScene_1920x1080_24.yuv

Number of fames encoded =20

Random Access profile (FAST SEARCH) / Random Access profile (FAST SEARCH)
QP / PSNR in dB / Bit rate in kbps / Encoding time in seconds / PSNR in dB / Bit rate in kbps / Encoding time in seconds
22 / 44.3166 / 2676.456 / 533.038 / 40.7117 / 8421.072 / 1808.863
27 / 42.5646 / 1232.856 / 570.403 / 38.3703 / 3673.3632 / 1356.223
32 / 40.4650 / 667.344 / 481.128 / 36.0006 / 1697.606 / 1211.177
37 / 38.0715 / 381.720 / 444.487 / 33.7621 / 791.712 / 1107.963

Table 3: Results for KirstenAndSara_1280x720_60.yuv & ParkScene_1920x1080_24.yuv sequences in Random Access Configuration

Fig 17: Bit rate vs QP for all test sequences

Fig 18: PSNR vs QP for all test sequences

Fig 19: R-D plot for RaceHorses_416x240_30.yuv sequence

Fig 20: R-D plot for BQMall_832x480_60.yuv sequence

Fig 21: R-D plot for KirstenAndSara_1280x720_60.yuv sequence

Fig 22: R-D plot for ParkScene_1920x1080_24.yuv sequence

Fig 23: Encoding time comparison for RaceHorses_416x240_30.yuv sequence

Fig 24: Encoding time comparison for RaceHorses_416x240_30.yuv sequence

Fig 25: Fast Search Encoding time comparison for all test sequences

Fig 26: Full Search Encoding time comparison for RaceHorses & BQMall

9. References

[1]I.E.G.Richardson,“VideoCodecDesign:DevelopingImageandVideoCompressionSystems”,Wiley,2002.

[2]K.R.Rao,D.N.KimandJ.J.Hwang,“VideoCodingStandards:AVSChina,H.264/MPEG-4Part10,HEVC,VP6,DIRAC andVC-1”,Springer,2014.

[3]G.J.Sullivanetal,“OverviewoftheHighEfficiencyVideoCoding(HEVC)Standard”,IEEETrans.onCircuitsandSystemsforVideoTechnology,Vol.22,No.12,pp.1649-1668,Dec.2012.

[4]F.Bossenetal,“HEVCComplexityandImplementationAnalysis”,IEEETrans.onCircuitsandSystemsforVideo Technology,Vol.22,No.12,pp.1685-1696, Dec.2012.

[5]J.R.Ohmetal,“ComparisonoftheCodingEfficiencyofVideoCodingStandards—IncludingHighEfficiencyVideoCoding(HEVC)”,IEEETrans.onCircuitsandSystemsforVideoTechnology,Vol.22, No.12,pp.1669-1684,Dec.2012.

[6]X.Lietal,“Rate-complexity-distortionevaluationforhybridvideocoding”,IEEEInternationalConferenceonMultimediaand Expo(ICME),pp.685-690,July 2010.

[7]B.Brossetal,“HighEfficiencyVideoCoding(HEVC)TextSpecificationDraft10”,DocumentJCTVC-L1003,ITU-T/ISO/IECJointCollaborativeTeamonVideoCoding(JCT-VC),Mar.2013availableon

[8]J.Vanneetal,“ComparativeRate-Distortion-ComplexityAnalysisofHEVCandAVCVideoCodecs”,IEEETrans. onCircuitsandSystemsforVideoTechnology,Vol.22,No.12,pp.1885-1898,Dec.2012.

[9]G.Bjontegaard,“CalculationofAveragePSNRDifferencesbetweenRD Curves”,documentVCEG-M33,ITU-TSG16/Q6,Austin,TX,Apr.2001.

[10]D. Groiset al,“PerformanceComparisonof H.265/MPEG-HEVC,VP9, andH.264/ MPEG-AVCEncoders”,availableon:

[11] HEVCtutorialbyI.E.G.Richardson:

[12] H.264tutorialbyI.E.G.Richardson:

[13]HEVCwhitepaper-IttiamSystems:

[14] HEVCwhitepaper-Ateme:

[15]HEVCwhitepaper-ElementalTechnologies: h265-demystified-white-paper

[16] TestSequences:ftp://ftp.kw.bbc.co.uk/hevc/hm-11.0-anchors/bitstreams/

[17] AccesstoHM 16.0ReferenceSoftware:

[18] Detailed Overview of HEVC/H.265 by Shevach Riabtsev

[19]Accessthewebsite

[20] AccesstoHM 16.0Software Manual:

[21]C.Fogg,“SuggestedfiguresfortheHEVCspecification”,ITU-T/ISO-IECDocument:JCTVCJ0292r1,July2012.

[22]Z.Wangetal,“ImageQualityAssessment:FromErrorVisibilitytoStructuralSimilarity”,IEEETrans.on ImageProcessing,Vol. 13,No. 4,pp.600-612,Apr. 2004.

[23]G. Correa et al, “Performance and computational complexity assessment of high efficiency video encoders”, IEEE Trans. on Circuits and Systems for Video Technology, Vol.22, pp.1899-1909, Dec.2012.

[24] L.-K.Liu and E.Feig, “A block based gradient descent search algorithm for block motion estimation in video coding,” IEEE Trans. on Circuits and Systems for Video Technology ,Vol. 6, No. 4, pp. 419-422, Aug. 1996.

[25] V. Sze and M. Budagavi, “Design and Implementation of Next Generation Video Coding Systems (H.265/HEVC Tutorial)”, IEEE International Symposium on Circuits and Systems (ISCAS), Melbourne, Australia, June 2014, available on

[26]F. Bossen, B. Bross, K. Suhring, and D. Flynn, "HEVC Complexity and Implementation Analysis," IEEE Trans. Circuits and Systems for Video Technology, Vol. 22, No. 12, pp.1685-1696 ,Dec. 2012.

[27] M.J.Jakubowski and G.Pastuszak, “Block-based motion estimation algorithms – a survey,” Opto-Electronic Review, Vol. 21, pp 86-102, March2013.

[28] W. Hong, “Coherent Block-Based Motion Estimation for Motion-Compensated Frame Rate Up-Conversion", IEEE International Conference on Consumer Electronics, pp. 165-166, Jan.2010.

[29] L.N.A. Alves and A. Navarro, " Fast Motion Estimation Algorithm for HEVC ", Proc. IEEE International Conf. on Consumer Electronics -ICCE Berlin , Germany , vol.11 , pp. 11 - 14 , Sep. , 2012.

[30] A. Abdelazim,W. Masri and B. Noaman "Motion estimation optimization tools for the emerging high efficiency video coding (HEVC)", SPIE vol. 9029, Visual Information Processing and Communication V, 902905, Feb. 17, 2014.

[31] Video test sequences - or or ftp://ftp.kw.bbc.co.uk/hevc/hm-11.0-anchors/bitstreams/

[32] G. J. Sullivan et al “Standardized Extensions of High Efficiency Video Coding (HEVC)”,IEEE Journal of selected topics in Signal Processing, vol. 7, pp.1001-1016, Dec. 2013.

[33] M. Wien, “High efficiency video coding: Tools and specification”, Springer, 2015.

[34] I.E. Richardson, “Coding video: A practical guide to HEVC and beyond”, Wiley, 11 May 2015.

[35]V.Sze, M.Budagaviand G.J.Sullivan “High Efficiency Video Coding (HEVC) –Algorithms and Architectures”, Springer, 2014.

[36] N.Purnachand, L.N. Alves, A. Navarro “Improvements to TZ search motion estimation algorithm for multiview video coding” 19th International Conference on Systems, Signals and Image Processing IWSSIP, pp. 388 -391, 2012.