TELKOM NIKA , Vol. 11, No. 10, Octobe r 2013, pp. 5 703 ~ 5 710   ISSN: 2302-4 046           5703      Re cei v ed Ma rch 2 9 , 2013;  Re vised June  30, 2013; Accepte d  Jul y  1 4 , 2013   Fast Intra Prediction Mode Decision Algorithm for  HEVC       Mengmeng Zhang* 1 , Jia n feng Q u 1 , Huihui Bai 2   1 Colle ge of Info rmation En gin e e rin g , North Ch ina U n ivers i t y   of  T e chnol og y,  Beiji ng, Chi n a   2 Institute of Informatio n  Scien c e, Be iji ng Jia o t ong Un iversit y , Beijin g, Chin a   *Corres p o ndi n g  author, e-ma i l : muchmen g @ 126.com       A b st r a ct   T h is p aper  pr o poses  a  nov el  fast intra- pred iction  al gorith m  th at ex plo i ts the S o b e op erator  t o   repl ace th e H a da mar d  transf o rm use d  i n  th e Ro ug h Mo de  Decis i o n  (RM D ) proc ess of  i n tra pr edicti on  i n   High  Efficie n cy  Vid e o  Co di ng  (HEVC). F i rst,  the So be oper at or is  us ed  to  calcul ate t he v e ctor d i rectio o f   each  pixe l. A judg ment is the n  made  on w h i c h pred ic tio n   mo de th e vect or bel on gs to, and  a histo g ra m i s   app lie d in th e sche m e to g e n e rate the statis tics of  predicti on  mod e s for each pr ed ictio n  unit. F i na lly, t h e   pred iction   mo d e  ca ndi dates  a r e p l ace d   in th e ca ndi dat e  lis t for the r a te-d istortion  opti m i z a t i o n  proc ess .   Experi m ental  r e sults s how  th at our  pro pos e d  al gor ith m   for  RMD si gnific a n t ly red u ce s the com p lexity  of the  enco der w i th a n  accepta b l e  d egra datio n of  q uality a nd BD-r ate co mpar ed  w i th HM7.0.    Ke y w ords : Hi gh Efficiency V i de o Cod i n g , Intra, Prediction  Modes,   Sobel          Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  High Efficie n c y Video  Co ding (HEVC) [1] provide s  signifi cantly better video  codi ng  efficien cy tha n  the  last  ge neratio n vide o codin g , tha t  is, Advan c e  Video  Codin g  (AV C ).  Un de the conditio n  of maintai n i ng the  same  video  qualit y, the goal  o f  HEVC i s  to  red u ce bit - rate   deman d by 5 0 % com p a r e d  with AV at the exp e n s e of i n crea sed comp utational  com p lex i ty,  whi c h is in a n  accepted ran ge.  Although  HE VC still b e lo ngs to  the b l ock-b a sed h y brid video   codi ng frame w ork, it  provide s  a h i ghly flexible hiera r chy o f  unit  representation [2], which in clu des th ree bl ock  con c e p ts, na mely, codin g   unit (CU), predictio n uni t (PU), an d tran sform  unit (T U). CU i s  a u n it   simila r to the  macroblo c k. CU  can  be  split and is  al ways  squ a re. The dime nsi on of CU ra n ges  from 8x8 up t o  the larg est  codi ng unit (LCU). The  d e fi nition of CU allo ws itsel f  to split into four   equal -si z e d  PU is a ba sic u n it used for  carryin g inform ation relate d to the predi cti on pro c e s s. PU  can o n ly be u s ed in  CU. P U  ha s two  sizes that  are su pporte d in intra pre d iction,  namely, 2N×2N  and  N×N. In   addition  to  CU a nd P U , T U  i s  a  u n it rel a ted to t r an sf ormatio n  a n d  qua ntizatio and  its size cann ot exceed tha t  of  CU. Base d on the re cu rsive  stru ct ure, the encod er mu st exha ust   all combi nati ons of CU, PU, and T U  to determin e   a n  optimal sol u tion. Ho wev e r, this proce ss i s   time-con sumi ng.  To imp r ove  the effici en cy and  a c cura cy of vid eo  codi ng,  HEVC p r ovide s  u p  to  34   predi ction  mo des   for i n tra  predi ction  [3], whi c h fa r ex cee d s th e ni n e  predi ction  mode s of AV C.  HEVC use s  rate-di s tortio n   optimization (RDO te chni que to  de cid e  the  codi ng  mode fo r a  CU.  Figure sh ows the RDO p r o c e ss. As  can  be see n   fro m  Figure, to cho o se the b e st co ding m ode  for an  CU,  HEVC en cod e r cal c ulate s  th e rate -di s torti on  cost (RD co st)  of eve r y possible m ode  (34 o r  17 m ode s), after that HEVC choo se the mode which has the mini mum value. Thi s   pro c e ss i s   re peatedly  carried out for  al l the po ssi bl e mode s fo  CU.  Ho wev e r, the en co der   can not affo rd  the total  co mputation if   a ll the  34  predictio n mo d e pa ss thro ugh th RDO   pro c e ss. Th e r efore, relea s e the  comp utational bu rde n  of RDO in  HEVC is far  more d e man d ing   than any existing video co ding alg o rith m. The Ha d a m ard transf o rm is used in  HM7.0, and t h ree  or eight can d i dates  a r e sel e cted   throug a Ro ugh  M ode  De ci sion  (RMD)  pro c e s s to  red u ce t he  comp utation  of the en co d e r. All p r edi ction mo d e i n   the RM D pro c e s a r e tested usi ng the   minimum a b solute su m of Hada mard Tran sfo r med  coeffici ents o f  resid ual si g nal [4]. RDO  is  then a pplie d t o  eve r y candi date m ode  se lected  by  the   RMD p r o c e s s. Ho wever,  th e computatio n   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : 570 3 –  5710   5704 of the encod er process is still  very huge despite the applicatio n o f  the Hadam ard tra n sfo r m  in  the RM pro c e ss.  Thu s , redu cing  the  n u mbe r  of  ca n d idate s  for RDO i s   ne ce ssary to mi nimi ze  the com putat ional bu rd en  of the enco der. Fo r ex a m ple, for thi s  re ason, a  fast algo rith m is   prop osed i n   this  study to  re pla c e th Had a ma rd t r ansfo rm i n   HM 7.0.  HM  7 . 0 mad e  ma ny  optimizatio ns on the foundation of  other HEVC Te st Model s. Some of these  optimization s  o n   intra predi ction will be di scussed in  section 2.  The remain d e r of this  pa per i s  o r gani zed  as  follo ws: Section  briefly de scri bes i n tra  predi ction  in  HEVC. S e ction 3 i n trod uce s  th e al g o rithm  and  the p r in ciple   of the fa st i n tra  predi ction  proce s s. Secti on 4 p r e s en ts the expe rimental resul t s. Finally, the la st se cti o n   pre s ent s the con c lu sio n     2. Intra Prediction in HEV C   Figure 1 sh o w s that the in tra codi ng to ol of  HEVC p r ovide s  up to  34 predi ction  modes,  as  well a s  the  plana r mo de  for the lum a   comp one nt  of different PU  sizes. In  HM7 . 0, PU si ze of  4×4, 8 × 8, 16 ×16, 3 2 ×32, and 64 ×6 4, correspon d to 18, 35, 35,  3 5 , and 35  predictio n mod e s.     H o w e ve r ,  in  p r e v io us  vis i on s ,  th er e  ar e   ju s t   4 p r e d icti on mod e s for 64×64. Thi s   optimizatio n i s   very important for the video  whi c h hav e large blo cks, at thi s  case LCU  will be chosen as  the  best CU [5]. So this optimi z ation  can off e r us  b e tter p r edi ction mo d e s, and lo we r the BD-rate.          Figure 1. 35 predi ction m o des      Based on the 4×4 predi ction unit illustrated in  Figure  2, we can  m a ke  a rough judgment   from its luma  texture. The  predi ction ve ctor i s  the sa me as the  arrow. The  RM D process sh ould   find a  way  to sele ct can d idate s  from  the 3 4   pre d i ction  mode s and  try its  best to  ma ke  the  optimal mod e  is one of the s e candi date s         Figure 2. Illustration of a 4x4 PU  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Fast Intra Pre d iction Mo de  De cisi on Algo rithm  for HEVC (Me ngm en g Zhang 5705 The followi n g  intra pre d i c tion process must  be p e rform ed to sele ct the best intra  predi ction m o de for the lu ma co mpon e n t of each  P U . The first step is an  RM D process, which   will ma ke  a rough  de cisi o n  on th choi ce  of t he b e st predi ction   mode.  HM7.0  then a pplie s the  Had a ma rd transfo rm. Afte rwa r d, th e p r edictio co st  Jpred,SATD i s   cal c ulate d  f o r all  po ssible   predi ction m ode s, and se veral pre d icti on mode s wi th lower  co sts are  cho s e n  as ca ndid a t mode s. The  different pred iction unit si zes [6] of  4×4,  8×8, 16 ×16,  32×32, and 6 4 ×6 4 have 8,  8,  3, 3, and 3 candid a te mod e s, as liste d in Table  1. After that, a proce s s of MPM is adopted . In   previou s   editi ons, th e MP M process h a s  two  candi d a tes, h o weve r the r e a r e  th ree  ca ndid a te s in   HM7.0.  What 's mo re, the  MPM pro c e ss  ha chan ged tre m en d ously. In HM7.0, the M P pro c e s s d o e s  not j u st  sim p ly pu sh  the  intra  dire ction s  of  ab ove a nd left P U  i n to the  candid a te   list.  Th e MP M process of  HM 7.0 m a ke the  mo st u s of the  ab ove an d left  predi ction  mo de throug h a we ighted co efficient  when   ab ove  an l e ft  predi ction   m ode s are eq ual. Finally, the   sele cted mo des a r e pl aced in the ca ndidate li st, whi c h is u s e d  for the RDO pro c e s s. The   flowchart of RDO is  sho w in Figure 3.      Table 1 Num ber of predi ction m ode s after the process of RM D   PU size   Number of  predic t ion modes  4x4   8x8   16x16   32x32   64x64       Since the HM7.0 has t h ree MPM [ 7 ] whic h is more than  other editi ons, the  comp utationa l burden  is m o re  than  othe r e d itions.  Re lease the  bu rden  of the  en cod e r i s  the  key  point of this p r opo se d algo rithm.           Figure 3. The  process of RDO       3. Fast Intr a Prediction Algorithm  Our pro p o s e d   algo rithm  i n trodu ce s a new method  for  the RM D pro c e ss, whi c intend s   to redu ce the  number of candid a tes an d the comput ation load. Th e flowch art of the algorithm  is  s h ow n  in  F i gu r e  4 .   The core  of  t h is algorithm ut ilize the tex t ure  of a CU t o   make out  which predi ction mode  is mo st p r ob a b ly be the  be st mod e . We   found t hat th e pixels (b oth  luma a nd  ch roma ) al ong t h e   dire ction of l o cal e dge  ne arly have the  similar  val u es. The r efo r e  by predi ct the pixels  usi ng  those  neig h b o ring  pixels i n  the same d i rectio n of the  edge, a  pre d i ction mo de  can be  got. After  that an  edg e  map  whi c h   rep r e s ent s th e vecto r  of l o cal  ed ge i s  created,  an d a l o cal e d g e   dire ction hi stogra m  is then  establi s he d for ea ch CU.   Since texture  is the  core o f  edge d e tect ion,  the prop ose d  alg o rith m will u s e th e Sobel  operator a s  the co re alg o ri thm for its excelle nt perfo rmance wh en  use d  in edg e detectio n  [8].    Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : 570 3 –  5710   5706     Figure 4. Algorithm flowch art       The form ula of Sobel ope rator is given  by (1), and m a trix A is a 3×3 pixel unit.    1, 1 1 , 1 , 1 ,1 , , 1 1, 1 1 , 1 , 1 10 1 1 2 1 2 0 2 *    , 000 * ,   10 1 1 2 1 ij ij ij x y ij ij i j ij ij i j pp p GA G A A p p p pp p             (1)     Two  co nvolut ion  kernel s e x ist for the  S obel  ope rator, and  ea ch  kernel  is rel a ted to th degree  of dif f eren ce  between th e h o ri zontal  an d v e rtical  di re ctions [9]. The  co rrespon di ng  dire ction vect or  {dx i,j ,dy i,j } for a luma pix e l in a picture  is defined a s   , 1 ,1 ,1 1 , 1 1 , 1 , 1 1 , 1 2 ij i j ij i j i j ij i j dx p p p p p p    (2)     , 1 , 1 1, 1, 1 1 , 1 1 , 1, 1 2 i j ij ij ij i j i j i j dy p p p p p p    (3)     The d e g r ee  of differen c e   on the  ho rizo ntal an d verti c al  dire ction s  are  corre s po ndingly  rep r e s ente d  by dx i,j  and dy i,j . The magnitude of th e vector i s  a c curately p r e s ente d  by (4 ). In  addition, (5 ) i s  ado pted wh en the com p u t ation load is  con s id ere d   22 ,, , () ( ) ( ) ij ij ij Am p D dx dy   (4)     ,, , () ' ij ij i j A mp D d x d y   (5)     The angl e of vector   is p r e s ente d  by (6).   In fact, (7) can be u s ed to  pre s ent the  angle of  the vecto r  b e ca use it is a sim p ler t h re shol d techniqu e for b u ilding  up th e edg e direction   histog ram.     , , 180 ( ) arct a n ( ) o ij ij dy Ang D dx   (6)     , , () ' ij ij dy Ang D dx  (7)     After obtainin g  the vecto r   in a coo r dina te system, Fi gure  5  sho w s ho w to m a ke the   deci s io n on whi c h predi ction mode th e vector  bel ong s to. The region b oun dary of the two   adja c ent p r ed iction mo de v e ctors i s  the  bise ctrix of th e two ve ctors. So if a vector is i n  the a r ea   betwe en  one  pre d ictio n  m ode  and  a  bi se ctrix, it will  be j udg ed t o  bel ong s to  the p r edi ctio mode. Ta king  Figure 5 a s   an example,  the vector   we  got is in the area b e twe e n  the predi ctio n   mode 3 a nd t he Boun dary  line of the jud g ment, So the vector  belo ngs to m ode  3, and (5 ) is t he  corre s p ondin g  magnitud e Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Fast Intra Pre d iction Mo de  De cisi on Algo rithm  for HEVC (Me ngm en g Zhang 5707 31 8 1 0 26 14 B o und ar y li ne of   t h J u d g men t The v e ctor w e  go t Predi c t i on Mo de Vect o r s     Figure 5. Illustration of the boun dar y line  for predi ction  mode judg m ent      The first ste p  is calculate t he vecto r  of  ev ery pixel in  a LCU  whi c h  will be  ope ra ted, and  put the data o f   these vecto r  into two arra y(one a rray st ore s  mag n itu des, an other  store s  an gle s ).  After that  th e  process  goe s into  a  re cu r s iv st ru ct ur e ,  in t h i s   st ru ct ure,  P U   wit h  t he  siz e   of 64×64, 32×32, 16×16,  8×8, 4×4 will  get the vector  of every pixel in each  PU from the arrays  whi c h we got  in the first ste p , and ma ke the j udgm ent  whi c h p r edi ction mod e  the vector b e long to.  The next  ste p  is  creating  a histo g ra m. Figur e 6  sho w s th at a hi stogram  wa use d  to  cou n t the  su m of the  ma gnitude  of e a ch  p r edi ctio n mo de i n  a  PU. T he X - axis  contai ns the   predi ction m ode s, whe r e a s the Y-axis contain s  the  sum of the magnitud e  of each p r edi ct ion  mode in  a P U . The  highe st and th e se con d  hig h e s t predi ction  mo des i n  the hi stogram  are th en  cho s e n  (Ta k i ng b o th BD-rate an codi ng time i n to  con s id eratio n ,  two  can d id ates  are  a  b e tter   choi ce  than  one  or three  can d idat es) a s   the   can d idate s  f o RDO. Th ough  it is  not  mathemati c al ly corre s po n d ing to  plan e predi cti on  to any di re ctional e dge,  we  can  for  sure   asso ciate the  predi ction to  its re sp ectiv e  edg es. T h e r efore, it is fairly re asona ble for u s  to  try  plane  predi ction if it i s  n o t obvio u s ly a   DC predi ctio n. In Fig u re   5, as an  exa m ple, p r edi cti o n   mode s 6 a n d  9 are  cho s e n  as the  ca n d idate mo de s. Finally, the two mod e a r e pla c e d  in the   can d idate li st.      0 200 400 600 800 1000 1200 012 3456 789 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2     Figure 6. Edge dire ction hi stogram       4. Experimental Re sults   In this expe ri ment, 300 fra m es of e a ch  seq uen ce a r e  cod ed to test the perfo rm ance of  prop osed  alg o rithm, an d e v ery frame i s   intra  cod ed.  A comp uter  whi c h h a s 2. 8GHz  co re i s   use d   to do this  experiment.  The exp e rim ental results [ 10] of thi s  st udy  are p r e s ented i n  Ta bl es  2, whi c h  show that  the pro p o s ed  algorith m  sa ves 16.5% o n  avera ge  coding time  a nd the B D -ra t e increa se by  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : 570 3 –  5710   5708 approximatel y 1.122% in high efficie n cy (HE) te st con d ition s , resp ectivel y . The resul t s in   Cla s ses A a nd B  are  be tter than  tho s e i n  oth e r test  seq uen ces. T herefore, the p r o p o s ed   algorith m  perf o rm s better u nder a hi gh g r aphi cs co ndi tion.  To calculate  the time saving of the  fast  intra - p r edi ction al g o rithm, the f o llowin g   cal c ulatio n is defined to  e v aluate the ti me differe nces.  We ta ke  T HEVC  prese n t the coding  time   use d  by HM 7.0 encode r,  corre s po ndi ngly T pro  be the time take n by the faster intra p rediction  algorith m , an d is define d  a s   % 100 T T T Time HEVC Pro HEVC  (8)       Table 2. Result in HE test condition    All-Intra HE   BD-rat e   BD-rat e   BD-rat e   Ti m e   Class A   0.73%   0.0  0.3%   -15.7%   Class B   0.4%   0.0%   -0.15%   -16.9%   Class C   1.245%   0.45%   0.775%   -16.7%   Class  2.025%   1.125%  0.575%  -16.8%   Class  E   1.21%   1.1%  0.8%  -16.1%   All 1.122%   0.535%   0.46%   -16.44 %       The Rate -Distortion (RD) curves of ParkSc ene a nd Race Ho rses a r e  shown in Figures  7, 8. The cu rve of the pro posed alg o rit h m is very  cl ose to the  cu rve of HM7.0 .  In addition, the   efficien cy of ParkS c en e is be tter than that of  Race Horses.           Figure 7. RD  Curve s  of ParkSce ne (Cla ss B 1920 ×10 80HE )           Figure 8. RD  Curve s  of Ra ce Horse s _ 8 3 2 ×4 80_ 30 (Cl a ss C 83 2×4 80 HE)  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Fast Intra Pre d iction Mo de  De cisi on Algo rithm  for HEVC (Me ngm en g Zhang 5709 Figure 9  sho w s that the  re con s tru c ted  i m age  quality  differen c bet wee n   HM7.0  and th prop osed alg o rithm is alm o st negli g ible  unde r the HE  test conditio n       (a)  Re con s tru c ted by HM7. 0(HE     (c) Re co nstru c ted by  pro p o s ed al gorith m (HE)    Figure 9. The  difference be tween  HM4.0   and pro p o s e d  algorith m  (Ra c e H orse s)      5. Conclusio n   This pap er propo sed  a fa st intra  pre d ict i on mo de  de cisi on  algo rithm for HEV C , whi c h   wa s achieve d  usin g the Sobel ope rat o r and  by redu cing the  numbe r of p r edi ction mo de  can d idate s   fo RDO. The  experim ental results  i n  Se ction  sho w  that the p r o posed  algo rithm  can  red u ce the co mplexit y  of the enco der a nd t hat  the video qu ality loss i s  a l most ne gligi b le   comp ared  wit h  HM7.0. In   addition, th prop osed  alg o rithm  achiev ed u p  to  19. 8% re du ction  in   codi ng time with negligible  degradatio n o f  quality and BD-rate.       Ackn o w l e dg ements   This  wo rk wa supp orte d i n  pa rt by National  Natu ral  Scien c Fou ndation  of Ch ina (No.  6110 3113,  No. 6127 2051 ), Jiang su Provincial  Na tu ral Sci e n c Found ation (BK20114 55)  and   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : 570 3 –  5710   5710 Beijing Mu ni cipal Ed ucation Commi ssion Scie nce  and T e chn o logy Devel opment P r og ram  (KM201 310 0 0900 4).       Referen ces   [1]    Kemal Ug ur, Kenn eth  A nde rsson.  Hi gh  Perf ormanc e, Lo w  Com p le xi t y   Vi de C odi ng and   the   Emergi ng HEV C  Stand ard.  IEEE Transactio n s on C i rcuits  and Syste m s f o r Vide o Tech nol ogy . 20 10 ;   20(1 2 ): 168 8-1 697.   [2]    W oo-Jin H an.  Improved Vi de o Compr e ssio n  Effi cienc y T h rou gh F l e x ibl e  Unit R epres entatio n an d   Corresp on din g  Extens ion  of Codi ng T ools.  IEEE Transactions on C i rc uits and Syste m s for Vid e o   T e chno log . 2 0 10; 20(1 2 ): 170 9-17 20.   [3]    Lia ng Z hao. F a st Mode Deci sion Al gorithm  for Intra Prediction in HEVC.  Visua l  Co mmu n icati ons an d   Imag e Process i ng (VCIP).  20 11; 1-4.   [4]    F r ank Bosse n,  Virgi n ie  Dru g eon. Vi de o C o din g  Usi ng  Simplifi ed B l oc k Structure a n d  Adva nce d   Codi ng T e chni ques.  IEEE Transactions on  Circuits a nd S ystem s for  Video Technology . 2010; 2( 12) :   166 7-16 75.   [5]    Van W a ll end ae l G. Improved intra mode si gn alin g for HEVC Multime d i a  an d Expo (ICME) . 2011; 1-6.   [6]    Benj amin  Bros s. High  efficie n c y  v i de co di n g  (HEVC)  te xt specific ation  dr aft 7.  JCT - VC 5th  Me eting 201 1; 56-7 1 [7]    Il-Koo K i m. H M 7: Hig h Effici enc y V i de Co din g  (HEV C) T e st Mod e 7 E n cod e r D e scri p tion.  JC T- V C   9th Meetin g . 2 012; 31- 46.   [8]    Anil  K J a in,  A d it ya V a il a y a.  Image r e triev a l  usi n g  col o a nd s h a pe.  P a ttern Reco gn it . 29(8):  12 33- 124 4.   [9]    F eng Pan. F a st Mode Deci sion Al gorithm   for Intrapredi ction in H.2 6 4 / AVC Video C odi ng.  IE EE  T r ansactio n s o n  Circuits a nd  Systems for Vi deo T e ch no log y . 2005; 15( 7): 813- 822.   [10]    F r ank Bosse n. Commo n test  cond itions  an d  soft w a re ref e r ence c onfi gura t ions.  JCT - VC 6th  Meeti n g 201 1; 14-2 2   Evaluation Warning : The document was created with Spire.PDF for Python.