Abstract:
Disclosed herein are an apparatus and a method of video pre-processing for motion estimation, the apparatus comprising a similarity description module, a storage module, a verdict module, and a motion estimation module. The similarity description module receives a first image in a video, the first image consisting of first blocks, and calculates the similarity descriptors of every first block and a second block of a second image in the video. The second block corresponds to a reference block among the first blocks. The similarity descriptor of each block, which corresponds to a pixel matrix, indicates whether the pixel values of at least one pair of adjacent pixels in the pixel matrix are identical. The verdict module determines whether the similarity descriptors of the second and reference blocks are identical and reaches a verdict, whereby motion estimation is selectively performed on the second block.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This non-provisional application claims priority under 35 U.S.C. §119(a) on Patent Application No. 102143259 filed in Taiwan, R.O.C. on Nov. 27, 2013, the entire contents of which are hereby incorporated by reference. 
       TECHNICAL FIELD  
       [0002]    The present disclosure relates to video processing, particularly to the usage by motion estimation of computing resources. 
       BACKGROUND  
       [0003]    Motion estimation is an important step in video compression. To describe the frame-by-frame changes in terms of motion vectors, the function block of motion estimation in a video codec receives from the source a frame to be processed and recovers the previous frame from the frame buffer, the previous frame having left the source. The majority of the frame buffer&#39;s limited outbound bandwidth is thus often preoccupied, impairing the performance of the codec. Furthermore, video codecs are put on more stringent requirements by the three-dimensional (3D) video extensions to standards such as AVC (Advanced Video Coding) and its successor HEVC (High Efficiency Video Coding), where it is required that depth maps, which describe the distance of each image block in a video to the camera, be compressed parallel to ordinary captured images. 
       SUMMARY 
       [0004]    In light of the above, the present disclosure provides a method and an apparatus of video pre-processing for motion estimation, whose selective execution depends on descriptions of the similarity between pixels in images. 
         [0005]    The video pre-processing method provided by this disclosure starts with a first image in a video being received. The first image consists of first blocks, each of which corresponding to a first pixel matrix. A similarity descriptor is calculated for each of the first blocks to indicate whether pixel values of at least one pair of adjacent pixels in the first pixel matrix are identical. A similarity descriptor of a second block of a second image in the video is also calculated. The second block corresponds to a reference block among the first blocks and to a second pixel matrix. The similarity descriptor of the second block is configured to indicate whether pixel values of at least one pair of adjacent pixels in the second pixel matrix are identical. Depending on whether the similarity descriptors of the second and reference blocks are identical, motion estimation is selectively performed on the second block. 
         [0006]    The video pre-processing apparatus provided by this disclosure comprises a similarity description module, a storage module, a verdict module, and a motion estimation module. The similarity description module receives a first image in a video, the first image consisting of first blocks, calculates a similarity descriptor of each of the first blocks, and calculates a similarity descriptor of a second block of a second image in the video, the second block corresponding to a reference block among the first blocks. The storage module, coupled with the similarity description module, stores the similarity descriptors of the first blocks. The verdict module, coupled with the storage module, determines whether the similarity descriptor of the second block and the similarity descriptor of the reference block are identical. The motion estimation module, subject to the output of the verdict module, is adapted for performing motion estimation on the second block. Each of the first blocks corresponds to a first pixel matrix, the similarity descriptor of each of the first blocks configured to indicate whether pixel values of at least one pair of adjacent pixels in the first pixel matrix are identical. The second block corresponds to a second pixel matrix, and the similarity descriptor thereof is configured to indicate whether pixel values of at least one pair of adjacent pixels in the second pixel matrix are identical. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
         [0007]    The present disclosure will become more fully understood from the detailed description given herein below and the accompanying drawings which are given by way of illustration only and thus are not limitative of the present disclosure and wherein: 
           [0008]      FIG. 1  is a high-level block diagram of a video pre-processing apparatus for motion estimation, in accordance with one embodiment of the present disclosure. 
           [0009]      FIG. 2  is a flowchart of a video pre-processing method for motion estimation, in accordance with one embodiment of the present disclosure. 
           [0010]      FIG. 3  is a diagram of a pixel matrix. 
           [0011]      FIG. 4  is a flowchart illustrating the calculation of a similarity descriptor, in accordance with one embodiment of the present disclosure. 
           [0012]      FIG. 5  is a flowchart illustrating the reconstruction of a first block, in accordance with one embodiment of the present disclosure. 
       
    
    
     DETAILED DESCRIPTION 
       [0013]    In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed embodiments. It will be apparent, however, that one or more embodiments may be practiced without these specific details. In other instances, well-known structures and devices are schematically shown in order to simplify the drawings. 
         [0014]    Please refer to  FIG. 1 . As shown in the block diagram, a video pre-processing apparatus  1  for motion estimation is coupled with a (video) source  2  and a frame buffer  3  and comprises a similarity description module  10 , a storage module  12 , a verdict module  14 , a reconstruction module  16 , and a motion estimation module  18 . The storage module  12  may be a buffer adapted for storing the calculation results of the similarity description module  10 . The similarity description module  10 , the motion estimation module  18 , and the frame buffer  3  are all capable of receiving a frame to be presently processed from the source  2 . Previous images, having left the source  2 , are temporarily harbored in the frame buffer  3 , whence the reconstruction module  16  may load some of the bits of these previous images out of necessity. In one embodiment, the modules mentioned above are substantiated by integrated circuits. In another embodiment, the video pre-processing apparatus  1  further includes a processor that obtains at least a piece of readable program code from one or more memory modules to function as the said modules. 
         [0015]    Please refer to  FIG. 2  with regard to  FIG. 1 . As shown in the flowchart, in step S 20  the similarity description module  10  receives a first image in a video from the source  2 . (Meanwhile, the first image leaves the source  2  and enters the frame buffer  3 .) The first image is divided into first blocks, each of which corresponding to a first pixel matrix. In step S 21 , the similarity description module  10  calculates and saves in the storage module  12  a similarity descriptor of each first block. The similarity description module  10  then receives a second image in the same video from the source  2  in order to calculate in step S 23  a similarity descriptor of a second block of the second image. (Meanwhile, the second image leaves the source  2  and is received by the motion estimation module  18 .) Generally speaking, the first and second images are consecutive frames in the video, and to perform motion estimation on a block of the second image refers to a relative motion vector in the procession of the video being obtained for that block and a corresponding reference block of the first image, the two blocks displaying, for instance, identical or similar objects. In the current embodiment, the block having the same relative position in the first image as the second block in the second image is chosen as the reference block. In other embodiments, a prediction vector in the coordinate system of the first or second image dictates a relative position of the reference block in the first image and another of the second block in the second image. In step S 25 , the verdict module  14  obtains the similarity descriptors of the second and reference blocks from the storage module  12 . In another embodiment, the verdict module  14 , connected to the similarity description module  10 , obtains directly thence the similarity descriptor of the second block. The verdict module  14  directs the motion estimation module  18  to skip the second block if it determines that the similarity descriptors of the second and reference blocks are identical. In the embodiment where the relative positions of the second and reference blocks are the same, a motion vector associated with the second block is therefore assigned null (zero) by the motion estimation module  18  in step S 27 ; in other embodiments, the motion vector associated with the second block is the prediction vector. 
         [0016]    The reconstruction module  16  obtains the similarity descriptors of all the first blocks from the storage module  12  and thereby reconstructs the first image in step S 29  if the verdict module  14  does not consider the similarity descriptors of the second and reference blocks identical. The reconstruction module  16  loads from the frame buffer  3  parts of the first image where the similarity descriptors come up short describing. The reconstructed first image is then fed into the motion estimation module  18 . Please note that what is shown in  FIG. 1  is merely one of the many examples of the connections between the verdict module  14 , the reconstruction module  16 , and the motion estimation module  18 . In this embodiment, the motion estimation module  18  may, upon instruction from the verdict module  14 , request the first image from the reconstruction module  16 , which in turn retrieves similarity descriptors from the storage module  12 , or it may be that the reconstruction module  16  reconstructs the first image anyhow based on the similarity descriptors of all the first blocks, and the motion estimation module  18  either fetches or ignores that depending on the verdict module  14 . In another embodiment, the verdict module  14  is concurrently connected to the reconstruction module  16  and the motion estimation module  18 , so the former need not wait for a request from the motion estimation module  18  to commence the reconstruction. 
         [0017]    The motion estimation module  18  performs motion estimation on the second block with the reconstructed first image. In particular, the motion estimation module  18  may implement block matching, pixel recursion, phase correlation, or optical flow algorithms in general, as seen fit by a person skilled in the art. 
         [0018]    The similarity descriptor of one of the first blocks or the second block is calculated from the block&#39;s corresponding pixel matrix. As exemplified in  FIG. 3 , a pixel matrix has m lines along a first direction and n lines along a second, m being a positive integer not less than 1, n being a positive integer greater than 1. Specifically, the first direction is horizontal in  FIG. 3 , the m lines therefore also known as columns with m=5, while there are n=4 lines or rows along the vertical second direction. Please note that in other embodiments the first and second directions may be vertical and horizontal, respectively, or even non-orthogonal bases. The rows and columns are also numbered in  FIG. 3  as marked on the circumference of the pixel matrix. The numbers along one direction are interchangeable. 
         [0019]    Please refer to  FIG. 4  with regard to  FIG. 3  for an illustration of the calculation of a similarity descriptor. As shown in the flowchart, in step S 41  the similarity description module  10  determines whether the five pixels on the first row have the same pixel values. If they do, a first truth or Boolean value is set to true or 1; if not (any of the five is different from the others), then the first truth value is false or 0. Here a pixel value refers to some data associated with a pixel, for instance hue, tone, saturation, and/or lightness in a true-color image, or grayscale intensity in a depth map. The first truth value associated with this pixel matrix (and its corresponding image block) is 1 due to all the values on the first row being 32. In practice, a plurality of truth values (m−1=4 of them for the pixel matrix in  FIG. 3 ) may be obtained by determining whether the pixel values of every pair of adjacent pixels on the first row are identical and compared with each other by logical conjunction or other operators to yield the first truth value. 
         [0020]    The similarity description module  10  then determines whether the i-th and (i−1)-th rows are the same, i being a positive integer greater than 1 yet not greater than n. Assume that i=3 for a detailed example. In step S 43 , the similarity description module  10  compares the first pixel on the third row (65) with a corresponding pixel on the second row. In one embodiment, such correspondence refers to the pixels being on the same column; in other words, the corresponding pixel is the leftmost 48 on the second row. 65 is not equal to 48, hence the third truth value associated with the first pixel on the third row is 0. As a matter of fact, the third truth values of all the pixels on the third row are 0, but those of the pixels on the fourth row are 1, for the third and fourth rows are exactly identical. In step S 45 , the similarity description module  10  compares the third truth values on the same row by logical conjunction or other operators to obtain the second truth value associated with that row. The second truth value associated with the third row is 0 for one of the row&#39;s third truth value is 0. The third and fourth rows are exactly identical, rendering the second truth value associated with the fourth row 1. Finally, the similarity description module  10  stores the said first truth value, second truth values (of all the rows), and the pixel value of an anchor pixel as the similarity descriptor of the image block corresponding to this matrix into the storage module  12  in step S 47 . The anchor pixel is an arbitrary one on the first row, e.g. the pixel on the first column and the first row (32). For the pixel matrix at hand, the similarity descriptor may be expressed as the tuple (32, h=1, v 2 =0, v 3 =0, v 4 =1), wherein h is the first truth value, and v i  the second truth value associated with the i-th row. 
         [0021]    With the similarity descriptors of all the first blocks, the reconstruction module  16  is able to reconstruct a complete first image block-by-block. Please refer to  FIG. 5  with regard to  FIG. 3  for an illustration of the reconstruction of a first block. As shown in the flowchart, after obtaining from the storage module  12  the similarity descriptor of a first block, the reconstruction module  16  determines in step S 500  whether the first truth value is 1. If it is not, not all the pixels are the same on the first row of the matrix representing this first block, and the reconstruction module  16  reads the bits of the first row from the frame buffer  3  in step S 506 . If the first truth value is 1, the reconstruction module  16  recovers the first row by copying the pixel value of the anchor pixel from the similarity descriptor in step S 503 , for all the pixels on that row, including the anchor, are identical. In step S 510 , the reconstruction module  16  sequentially determines whether each of the second truth values is 1. Continuing with the example of the previous paragraph, v 2 =0, meaning the second and first rows are at least partly different, prompting the reconstruction module  16  to read the bits of the second row from the frame buffer  3  in step S 516 . It is much the same for the third row, but since v 4 =1, the reconstruction module  16  may recover the fourth row simply by copying the third in step S 513 . 
         [0022]    In one embodiment of the present disclosure, the similarity descriptor of a block further records a second truth value associated with the first row, v 1 . v 1  may be the result of the similarity description module  10  comparing the first row of the current block and the last row of another one previously processed. In the block reconstruction exemplified in  FIG. 5 , the reconstruction module  16  may determine whether v 1  is 1 before step S 500 . If it is, the first row is recovered based on the previous block and step S 510  is executed; if not, the reconstruction module  16  performs step S 500 . 
         [0023]    It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.