Page 192 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience
P. 192

Section 7.7.  Fast Full-Search Techniques                     169


            The  )rst  summation  in  this  inequality  is  the  sum  norm  of  block  B  in  the
            current  frame,  and  this  sum  is  denoted  SN t .  The  second  summation,  on  the
            other  hand,  is  the  sum  norm  of  a  candidate  block  in  the  reference  frame
            shifted by (i; j), and this sum is denoted SN t−Mt (i; j). The third summation is
            obviously the SAD(i; j). Thus, for simplicity, Inequality (7.2) can be rewritten
            as

                             |SN t  − SN t−Mt (i; j)|≤ SAD(i; j):        (7.3)
            Now assume that during a full-search, the minimum SAD calculated so far is
            SAD(i m ;j m )  at  search  location  (i m ;j m ).  A  subsequent  search  location  (i; j)is
            said  to  achieve  better  match  only  if  SAD(i; j) ≤ SAD(i m ;j m ).  Put  in  another
            way, and based on Inequality (7.3), a subsequent search location (i; j) is said to
            achieve better match only if |SN t  −SN t−Mt (i; j)|≤ SAD(i m ;j m ). In other words,
            a subsequent location (i; j)  can be immediately skipped from the search if
                            |SN t  − SN t−Mt (i; j)|≥ SAD(i m ;j m ):    (7.4)

            Note that calculating the sum norms in this inequality has a reduced-complexity
            compared to calculating the SAD(i; j) itself. For example, assume that B(x; y)
            is  an  N × N  block  with  its  top-left  cornet  at  (x; y)  and  that  the  next  block
            B(x +1;y)  is  the  block  obtained  by  moving  one  pel  to  the  right.  The  two
            blocks  are  overlapping  and  they  share  N − 1  columns.  Once  the  sum  norm,
            SN(B(x; y)), of the )rst block is calculated, the sum norm, SN(B(x +1;y)),
            of the next block in the line is obtained simply by substracting the sum norm
            of  the  )rst  column  of  block  B(x; y)  and  adding  the  sum  norm  of  the  last
            column in block B(x +1;y). A similar procedure can be used for calculating
            the  sum  norm  of  the  next  block  in  the  column  (i.e.,  when  moving  one  pel
            down). Based on these ideas, a very fast method of calculating the sum norms
            is  presented in Ref. 162.
               A similar algorithm to the SEA has also been proposed in Ref. 164. Assume
                                                                    �
            that  B  is  partitioned  into  subsets  B n  such  that  B =     n  B n  and   n  B n  = ∅.
            Then the triangular inequality becomes
                          �
                             |SN t;n  − SN t−Mt;n (i; j)|≤ SAD(i; j);    (7.5)
                           n
            where  SN t−Mt;n (i; j)  is  the  sum  norm  over  subset  B n  of  the  candidate  block
            in the reference frame shifted by (i; j).  It  can be shown  that
                     �
                         |SN t;n  − SN t−Mt;n (i; j)|≥|SN t  − SN t−Mt (i; j)|:   (7.6)
                       n
            Thus,  a  tighter  bound  is  achieved  when  the  partitioned  case  is  used  in  In-
            equality  (7.4)  instead  of  the  partitioned  case.  This  tighter  bound  will  result
   187   188   189   190   191   192   193   194   195   196   197