Abstract:
Presented herein are caching structures and apparatus for use in block based video. In one embodiment, there is described a system receiving lower resolution frames and generating higher resolution frames. The system comprises an upsampling circuit, a first circuit, and a second circuit. The upsampling circuit upsamples a particular lower resolution frame, thereby resulting in an upsampled frame. The first circuit maps frames that are proximate to the particular frame, to the particular frame. The second circuit simultaneously updates the upsampled frame with two or more blocks from at least one of the frames that are proximate to the particular frame.

Description:
RELATED APPLICATIONS 
       [0001]    This application is related to the following applications for U.S. Patent:
   Serial No. Attorney Docket Title
       20739US01   20736US01
 
Each of which are incorporated herein by reference for all purposes.
   
       
 
     
    
     BACKGROUND OF THE INVENTION 
       [0005]    High Definition (HD) displays are becoming increasingly and popular. Many uses are now accustomed to viewing high definition media. However, a lot of media, such as older movies, and shows were captured with in Standard Definition (SD). Since the actual the actual scene was captured by a video camera that only captured the scene in standard definition, even if the display is high definition, there are not enough pixels to take advantage of the display. 
         [0006]    Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art, through comparison of such systems with some aspects of the present invention as set forth in the remainder of the present application with reference to the drawings. 
       BRIEF SUMMARY OF THE INVENTION 
       [0007]    The present invention is directed to parallel processing for providing high resolution frames from low resolution frames, substantially as shown in and/or described in connection with at least one of the figures, as set forth more completely in the claims. 
         [0008]    These and other advantages and novel features of the present invention, as well as illustrated embodiments thereof will be more fully understood from the following description and drawings. 
     
    
     
       BRIEF DESCRIPTION OF SEVERAL VIEWS OF THE DRAWINGS 
         [0009]      FIG. 1  is a block diagram describing an exemplary video frame capturing a scene at a particular time in lower resolution; 
           [0010]      FIG. 2  is a block diagram describing an exemplary video frame capturing the scene at the same time in higher resolution; 
           [0011]      FIG. 3  is a block diagram describing upscaling lower resolution frames to higher resolution in accordance with an embodiment of the present invention; 
           [0012]      FIG. 4  is a block diagram describing motion estimation in accordance with an embodiment of the present invention; 
           [0013]      FIG. 5  is a block diagram describing motion estimation between non-adjacent frames in accordance with an embodiment of the present invention; 
           [0014]      FIG. 6  is a block diagram describing motion compensated back projection in accordance with an embodiment of the present invention; 
           [0015]      FIG. 7  is a block diagram describing motion free back projection in accordance with an embodiment of the present invention; 
           [0016]      FIG. 8  is a block diagram of an integrated circuit and off-chip memory in accordance with an embodiment of the present invention; 
           [0017]      FIG. 9  is a block diagram of a higher resolution frame partition into blocks in accordance with an embodiment of the present invention; 
           [0018]      FIG. 10  is a block diagram of a destination domain in accordance with an embodiment of the present invention; 
           [0019]      FIG. 11  is a block diagram of an exemplary source domain stripe in accordance with an embodiment of the present invention; 
           [0020]      FIG. 12  is a block diagram describing an exemplary order of processing source domain stripes in accordance with an embodiment of the present invention; 
           [0021]      FIG. 13  is a block diagram describing another exemplary order of processing source domain stripes in accordance with an embodiment of the present invention; 
           [0022]      FIG. 14  is a block diagram describing a portion of a high resolution frames mapped to a buffer; 
           [0023]      FIG. 15  is a block diagram describing pixel level parallel processing in accordance with an embodiment of the present invention; and 
           [0024]      FIG. 16  is a block diagram describing another exemplary pixel level parallel processing in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0025]    Referring now to  FIG. 1 , there is illustrated a block diagram describing an exemplary video frame capturing a scene in lower resolution. Video frames  120  are generated by a video camera and represent images captured by the camera at specific time intervals t. A frame  120   0 . . . t  represents each image. The frames  120  comprise two-dimensional grids of pixels  125 (x,y), wherein each pixel in the grid corresponds to a particular spatial location of an image captured by the camera. Each pixel  125  stores a color value describing the spatial location corresponding thereto. 
         [0026]    It is noted that position x,y are discrete variables, that actually correspond to a range xΔx−0.5Δx→xΔx+0.5Δx, yΔy−0.5Δy→yΔy+0.5Δy, in both the scene and the picture, where Δx*Δy are the dimensions of the pixel. An exemplary standard for frame dimensions is the ITU-R Recommendation Bt.656 which provides for 30 frames of 720×480 pixels per second. Additionally, the pixel value of  125 (x, y) is also a discrete value. For example, 24-bit color uses 256 red, 256 blue, and 256 green color values to represent the range of colors that are visible to the human eye. 
         [0027]    While the video frames  120  comprise discrete pixels at discrete locations, a real-life scene that is captured is continuous in color and space. Thus, while the position in a scene corresponding to pixel  125 (x, y), xΔx−0.5Δx→xΔx+0.5Δx, yΔy−0.5Δy→yΔy+0.5Δy is within a range that may include several colors. The colors themselves may not necessarily match exactly with any one of the 24-bit colors. 
         [0028]    However, the actual color that is recorded by the camera can be modeled as some type of statistical averaging of the colors that appear between xΔx−0.5Δx→xΔx+0.5Δx, yΔy−0.5Δy→yΔy+0.5Δy. The averaging can be a simple averaging of the colors or weighted averaging based on the distance of the point and color from the center x, y. A particular one of the 24-bit colors is selected that most closely approximates the actual color. 
         [0029]    The differences between adjacent colors in 24-bit colors are indistinguishable to the human eye. Accordingly, adjacent colors appear continuous. An exemplary standard for display of the video sequence  105  is the ITU-R Recommendation Bt.656 which provides for 30 frames of 720×480 pixels per second. The foregoing picture appears spatially continuous to the viewer. However, although 720×480 pixels appear continuous to the user, information is lost from the original scene, resulting in a loss of detail. For example, fine texture in the scene may be lost. 
         [0030]    Referring now to  FIG. 2 , there is illustrated a block diagram describing an exemplary video frame capturing the scene  100  in higher resolution. The higher resolution is double the resolution in both the x and y directions, e.g., 960V×1440H pixels, in the present example, however it should be understood that other multiples, integer or non-integer, may be used. It should also be understood that the multiples in the x and y directions are not necessarily the same. 
         [0031]    Thus pixels  225 (x,y) are discrete variables, that actually correspond to a range 0.5xΔx−0.25Δx→0.5xΔx+0.25Δx, 0.5yΔy−0.25Δy→0.5yΔy+0.25Δy, in both the scene and the picture, where 0.5Δx*0.5Δy are the dimensions of the pixel. As in the case of lower resolution, the pixel value of  225 (x, y) is also a discrete value. For example, 24-bit color uses 256 red, 256 blue, and 256 green color values to represent the range of colors that are visible to the human eye. 
         [0032]    The position in a scene corresponding to pixel  1125 (x, y), 0.5xΔx−0.25Δx→0.5xΔx+0.25Δx, 0.5yΔy−0.25Δy→0.5yΔy+0.25Δy is also within a range that may include several colors. The colors themselves may not necessarily match exactly with any one of the 24-bit colors. The actual color that is recorded by the camera can be modeled as some type of statistical averaging of the colors that appear between 0.5xΔx−0.25Δx→0.5xΔx+0.25Δx, 0.5yΔy−0.25Δy→0.5yΔy+0.25Δy. The averaging can be a simple averaging of the colors or weighted averaging based on the distance of the point and color from the center x, y. A particular one of the 24-bit colors is selected that most closely approximates the actual color. 
         [0033]    The foregoing higher resolution picture more accurately captures the scene and provides greater detail, including finer texture than the lower resolution picture. However, a lot of media, such as older movies, and shows were captured with in Standard Definition (SD), while high definition displays are becoming increasingly common. 
         [0034]    When a scene is captured in lower resolution, although the continuous detail of the scene is not known, information about the scene as a series of ranges xΔx−0.5Δx→xΔx+0.5Δx, yΔy−0.5Δy→yΔy+0.5Δy is known. The image of  FIG. 2  is the gold standard, higher resolution image. However, the gold standard higher resolution image includes information from the scene at 0.5xΔx−0.25Δx→0.5xΔx+0.25Δx, 0.5yΔy−0.25Δy→0.5yΔy+0.25Δy, which is not available. 
         [0035]    Nevertheless, the foregoing information can be estimated by up-sampling the low resolution frame using any one of a variety of techniques such as spatial interpolation, or filtering. The foregoing results in an estimated higher resolution frame. Exemplary upsampled frames  320  that estimate the higher resolution frame are shown in  FIG. 3 . 
         [0036]    The foregoing can be done with each of the low resolution frames that are captured at other times, e.g., t−3, t−2, t−1, t, t+1, t+2, t+3 . . . , resulting in upsampled frames  320   t−3 ,  320   t−2 ,  320   t−1 ,  320   t ,  320   t+1 ,  320   t+2 ,  320   t+3 . However, it should be noted that with recursion, the processing for higher resolution frames prior to  320   t  was completed prior to processing of frame  320   t . Accordingly, these frames are now designated  320   t−3 ′,  320   t−2 ′,  320   t−1 ′. Frames  320   t+1 ,  320   t+2 ,  320   t+3  are not yet completely processed. 
         [0037]    Information from proximate time periods can be used to improve the quality of frame  320   t . To achieve this, the motion between proximate input frames may be required. The foregoing will now be described with reference to  FIG. 4 .  FIG. 4  is an illustration of an exemplary motion estimation process using stages. The purpose of the proposed method of motion estimation using staged procedures is to achieve a large effective search area by covering small actual search areas in each motion estimation stage. This is especially useful when a large number of low resolution frames are used to generate a high resolution frame, since in that case, the motion between two non-adjacent frames may be relatively substantial. For example, locating a best matching block in a frame that is substantially distant in time, may require the search of a large frame area. 
         [0038]    ME stage  1 : In the first stage, details of which are shown in  410 , motion estimation is performed between pairs of neighboring frames  320   t−3 ′ and  320   t−2 ′,  320   t−2 ′, and  320   t−1 ′,  320   t−1 ′ and  320   t ,  320   t  and  320   t+1 ,  320   t+2 ,  320   t+2  and  320   t+3 . For each pair of neighboring frames, two motion estimations are performed. 
         [0039]    In the first motion estimation, the earlier frame is the reference frame and divided into predetermined sized blocks, e.g.,  320   t−1 ′. The later frame  320   t  is the target frames and is searched for a block that matches  320   t−1 ′. In the second motion estimation, the later frame is the reference frame and divided into predetermined sized blocks, e.g.,  320   t . The earlier frame  320   t−1 ′ is the target frame and is searched for a block that matches  320   t . 
         [0040]    Motion estimation in this stage is based on full-search block matching, with (0, 0) as search center and a rectangular search area with horizontal dimension search_range_H and vertical dimension search_range_V. The reference frame is partitioned into non-overlapping blocks of size block_size_H×block_size_V. Next, for a block R in a reference frame with top-left pixel at (x, y), the corresponding search area is defined as the rectangular area in the target frame delimited by the top-left position (x−0.5*search_range_H, y−0.5*search_range_V) and its bottom-right position (x+0.5*search_range_H 1 / 2 , y+0.5*search_range_V 1 ), where search_range_H and search_range_V are programmable integers. Thereafter, in searching for the best-matching block in the target frame for the block R in the reference frame, R is compared with each of the blocks in the target frame whose top-left pixel is included in the search area. The matching metric used in the comparison is the sum of absolute differences (SAD) between the pixels of block R and the pixels of each candidate block in the target frame. If, among all the candidate blocks in the search area, the block at the position (x′, y′) has the minimal SAD, then the motion vector (MV) for the block R is given by (MVx, MVy) where MVx=x-x′, and MVy=y-y′. 
         [0041]    As noted above, with recursion, the processing of frames  320   t−3 ′,  320   t−2 ′,  320   t−1 ′ is completed. While frames  320   t−3 ′ . . .  320   t+3  are a window for  320   t . During processing of  320   t−1 ′, the upsampling was performed for all of the time periods except t+3, and motion estimation would be performed for all of the foregoing pairs except for  320   t+2  and  320   t+2 . All the other motion estimation results are available from previous processing due to pipelined processing of consecutive images. Thus, only the foregoing motion estimation needs to be computed at this stage, provided the previous motion estimation results are properly buffered and ready to be used in the next two stages of motion estimation. 
         [0042]    After the first stage of motion estimation, the next two stages are preferably performed in the following order at frame level: first, stages  2  and  3  for  320   t−2 ′ and  1320   t+2 , then stage  2  and  3  for  320   t−2 ′ and  320   t+2 . 
         [0043]    ME stage  2 : In this stage, details of which are shown in  420 , the motion vectors between non-adjacent frames are predicted based on the available motion estimation results. The predicted motion vectors will be used as search centers in stage  3 . For example, the predicted motion vectors between  320   t+2  as the reference frame and  320   t  as the target frame, can be represented as C_MV(t+2, t). To determine C_MV(t+2, t), MV(t+2, t+1) and MV(n+1, t) are combined, both being available from the previous stage of motion estimation processing. 
         [0044]    For example, as shown in  FIG. 5 , a block R at location (x, y) in  320   t+2  may have its best-matching block in  320   t+1  as block T, which is determined in the motion estimation between  320   t+2  as the reference frame and  320   t+1  as the target frame. Note that although R is aligned with the block grids, for example, x % block_size_H 1 =0 and y % block_size_V 1 =0, T may not be aligned with the block grid of its frame, and may be located anywhere in the search area. Block T may contain pixels from up to four grid-aligned blocks in  302   t+1  whose top-left pixels are at (x 0 , y 0 ), (x 1 , y 1 ), (x 2 , y 2 ), and (x 3 , y 3 ), respectively. In case of less than four grid-aligned blocks covered by T, some of the four top-left pixels overlap. 
         [0045]    The predicted motion vector for R from  320   t+2  to  320   t  may be set as the summation of the motion vectors for the block R from  320   t+2  to  320   t+1  and the median of the motion vectors for the block T from  320   t+1  to  320   t , as shown in Equation 1: 
         [0000]        C   —   MV ( t+ 2,  t, x, y )= MV ( t+ 2,  t+ 1,  x, y )+median ( MV ( t+ 1,  t, xi, yi ),  i= 0, 1, 2, 3)   (1)
 
         [0000]    where the median of a set of motion vectors may be the motion vector with the lowest sum of distances to the other motion vectors in the set. For example, consider each motion vector in the set as a point in the two dimensional space, and calculate the distance between each pair of motion vectors in the set. The median of the set may then be the motion vector whose summation of the distances to other motion vectors is minimal among the motion vectors in the set. Note that in other embodiments, the distance between two motion vectors may be calculated as the Cartesian distance between the two points corresponding to the two motion vectors, or it may be approximated as the sum of the horizontal distance and the vertical distance between the two motion vectors to reduce computing complexity. 
         [0046]    Similarly, the predicted motion vectors from  320   t+3  as the reference frame to  320   t  as the target frame is obtained by cascading the motion vectors from  320   t+3  to  320   t+2  with the motion vectors from  320   t+2  and  320   t . The predicted motion vectors from  320   t−3 ′ and  320   t  can be obtained in a similar manner. 
         [0047]    In another embodiment of this invention, in predicting the motion vector for R from non-adjacent frames, the median operator in Equation 1 may be replaced with the arithmetic average of the four motion vectors. In another embodiment, in predicting the motion vector for R, the minimal SAD between the block T and each of the four blocks Si (i=1, 2, 3, 4) may be used in Equation 1 to replace the median of the four motion vectors. In yet another embodiment of this invention, in predicting the motion vector, one may calculate the SAD corresponding to each of the following four motion vectors: MV(t+2,t+1,x,y)+MV(t+1,t,xi,yi) (i=0,1,2,3), and choose the one with the minimal SAD. 
         [0048]    ME stage  3 : In the last stage,  430  of  FIG. 4 , of processing in the motion estimation block, the predicted motion vectors are refined to determine to determine motion vectors between  320   t+k ,  320   t  for (k=−3, −2, 2, 3), by searching around the corresponding predicted motion vectors. For example, to determine the motion vectors, a block-based motion estimation is performed with a search center at (x+C_MVx(t+k, t), y+C_MVy(t+k, t)) and a search areas (search_range_H 2 , search_range_V 2 ) and (search_range_H 3 , search_range_V 3 ), where the foregoing are programmable integers representing respectively the horizontal search range and vertical search range. The search range at this stage may be set to be smaller than that in the stage  1  of motion estimation to reduce the computational complexity of motion estimation. 
       Motion-Compensated Back Projection 
       [0049]    Subsequent to motion estimation processing, the image  320   t ′ is subjected to processing for motion-compensated back projection (MCBP). The inputs to this block are the frames and motion estimation results from  320   t+k , (k=−3, −2, −1, 1, 2, 3), and frame  320   t . 
         [0050]    MCBP favors frames that are temporally close to  320   t  over frames further away. Temporally close frames are favored because motion estimation is generally more reliable for a pair of frames with a smaller temporal distance than that with a larger temporal distance. Also, this ordering favors the motion estimation results of prior frames over later frames. Thus, MCBP follows the order t−3, t+3, t−2, t+2, t−1, t+1. 
         [0051]    Referring now to  FIG. 6 , there is illustrated a block diagram describing motion compensated back projection between two frames in accordance with an embodiment of the present invention. 
         [0052]    In a first step, for each block-grid-aligned block R in  320   t+3 , the corresponding motion-compensated block T in  320   t  is found using the motion estimation results. For example, if block R is at the position (x, y) in  320   t+3  and its motion vector is (mvx, mvy), the corresponding motion compensated block T is the block at the position (x-mvx, y-mvy) in  320   t . 
         [0053]    In a second step, for each pixel z in the low resolution frame LR(n+3) within the spatial location of block R, the corresponding pixels are identified in block R of  320   t+3  based on a pre-determined spatial window, for example, a 00  . . . a 55 , and consequently the corresponding pixels in block T of  320   t , for example, a′ 00  . . . a′ 55 . From the identified pixels in  320   t  a simulated pixel z′ corresponding to z is generated. Note that the simulated pixel z′ may not necessarily co-site with an existing pixel of LR(n): the pixel z′ co-sites with an existing pixel of LR(n) if and only if both mvx and mvy are integers in terms of the resolution of LR(t). For example, in the case of using spatial interpolation to up-scale LR(t) by three both horizontally and vertically, the simulated pixel z′ co-sites with an existing pixel of LR(t) if and only mvx % 3=0 and mvy % 3=0. 
         [0054]    In the second step above, to identify the pixels in  320   t  corresponding to the pixel z in LR(t+3) and simulate the pixel z′ from these pixels, ideally, the point spread function (PSF) in the image acquisition process is required. Since PSF is generally not available to high-resolution processing and it often varies among video sources, an assumption may be made with regard to the PSF, considering both the required robustness and computational complexity. 
         [0055]    For example, a poly-phase down-sampling filter may be used as PSF. The filter may consist, for example, of a 6-tap vertical poly-phase filter and a consequent 6-tap horizontal poly-phase filter. As shown in  FIG. 6 , the pixel z in LR(n+3) corresponds to the pixels a 00  to a 55  in  1320   t+3  through the PSF; and the pixels a 00  to a 55  correspond to the pixels a′ 00  to a′ 55  in  1320   t  through the motion vector (mvx, mvy); therefore, the pixels in  1320   t  corresponding to z are a′ 00  to a′ 55  and the simulated pixel z′ is: 
         [0000]    
       
         
           
             
               
                 
                   
                     z 
                     ′ 
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       5 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         5 
                       
                        
                       
                         
                           PSF 
                           ij 
                         
                         * 
                         
                           a 
                           ij 
                           ′ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where PSF ij  is the coefficient in the PSF corresponding to a′ ij . In another embodiment of this invention, a bi-cubic filter may be used as the PSF. 
         [0056]    In a third step, the residue error between the simulated pixel z′ and the observed pixel z is computed, as residue_error=z-z′. 
         [0057]    In a fourth step, the pixels in  320   t  can be updated for example, from pixels a′ 00  . . . a′ 55  in  320   t  to pixels a″ 00  . . . a″ 55 , according to the calculated residue error as shown at the bottom right in  FIG. 6 . 
         [0058]    In the fourth step above, the residue error is scaled by λ*PSF ij  and added back to the pixel a′ ij  in  320   t  to generate the pixel a″ ij . The purpose of PSF ij  is to distribute the residue error to the pixels a′ ij  in  320   t  according to their respective contributions to the pixel z′. As proposed herein, the purpose of the scaling factor λ is to increase the robustness of the algorithm to motion estimation inaccuracy and noise. λ may be determined according to the reliability of the motion estimation results for the block R. The motion estimation results can include (mvx, mvy, sad, nact). Among the eight immediate neighboring blocks of R in  320   t+3 , let sp be the number of blocks whose motion vectors are not different from (mvx, mvy) by 1 pixel (in terms of the high-resolution), both horizontally and vertically. In an embodiment of this invention, λ may be determined according to the following formula: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       if 
                     
                     
                       
                         
                           sp 
                           ≥ 
                           1 
                         
                         &amp;&amp; 
                         
                             
                         
                          
                         
                           sad 
                           &lt; 
                           
                             nact 
                             * 
                             
                               4 
                               / 
                               4 
                             
                           
                         
                       
                     
                     
                       
                         
                           λ 
                           = 
                           1 
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         else 
                          
                         
                             
                         
                          
                         if 
                       
                     
                     
                       
                         
                           sp 
                           ≥ 
                           2 
                         
                         &amp;&amp; 
                         
                             
                         
                          
                         
                           sad 
                           &lt; 
                           
                             nact 
                             * 
                             
                               6 
                               / 
                               4 
                             
                           
                         
                       
                     
                     
                       
                         
                           λ 
                           = 
                           
                             1 
                             / 
                             2 
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         else 
                          
                         
                             
                         
                          
                         if 
                       
                     
                     
                       
                         
                           sp 
                           ≥ 
                           3 
                         
                         &amp;&amp; 
                         
                             
                         
                          
                         
                           sad 
                           &lt; 
                           
                             nact 
                             * 
                             
                               8 
                               / 
                               4 
                             
                           
                         
                       
                     
                     
                       
                         
                           λ 
                           = 
                           
                             1 
                             / 
                             4 
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         else 
                          
                         
                             
                         
                          
                         if 
                       
                     
                     
                       
                         
                           sp 
                           ≥ 
                           4 
                         
                         &amp;&amp; 
                         
                             
                         
                          
                         
                           sad 
                           &lt; 
                           
                             nact 
                             * 
                             
                               10 
                               / 
                               4 
                             
                           
                         
                       
                     
                     
                       
                         
                           λ 
                           = 
                           
                             1 
                             / 
                             8 
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         else 
                          
                         
                             
                         
                       
                     
                     
                       
                         
                           sp 
                           ≥ 
                           5 
                         
                         &amp;&amp; 
                         
                             
                         
                          
                         
                           sad 
                           &lt; 
                           
                             nact 
                             * 
                             
                               12 
                               / 
                               4 
                             
                           
                         
                       
                     
                     
                       
                         
                           λ 
                           = 
                           
                             1 
                             / 
                             16 
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         else 
                          
                         
                             
                         
                       
                     
                     
                       
                           
                       
                     
                     
                       
                         
                           λ 
                           = 
                           0 
                         
                         ; 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    conveying that the contribution from the residue error to updating the pixels in  320   t  should be proportional to the reliability of the motion estimation results. This proportionality is measured in terms of motion field smoothness, represented by the variable sp in the neighborhood of R and how good the match is between R and T, for example, as represented by comparison of sad and nact. 
         [0059]    Note that, in  FIG. 6 , if the simulated pixel z′ co-sites with an existing pixel in LR(n), λ is reduced by half, which implies the updating back-projection strength from the residue error is reduced by half. A reason for this is that, in the case that z′ co-sites with an existing pixel in LR(n), the pixel z′ is a version of the pixel z that is simply shifted an integer number of pixels, and hence it does not provide much additional information in terms of resolution enhancement. However, it may be helpful in reducing noise. 
         [0060]    In another embodiment of this invention, in calculating the scaling factor λ, the reliability of the motion estimation results may be measured using the pixels in  320   t  and  320   t+3  corresponding to the pixel z, i.e., a 00  . . . a 55  in  320   t+3  and a′ 00  . . . a′ 55  in  320   t . For example, sad and nact may be computed from these pixels only instead from all the pixels in R and T. 
         [0061]    For example, if the block size is 4×4 pixels, the sad between R and T may be defined as in Equation 4: 
         [0000]    
       
         
           
             
               
                 
                   sad 
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         
                           - 
                           1 
                         
                       
                       4 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           
                             - 
                             1 
                           
                         
                         4 
                       
                        
                       
                          
                         
                           
                             R 
                             
                               i 
                               , 
                               j 
                             
                           
                           - 
                           
                             T 
                             
                               i 
                               , 
                               j 
                             
                           
                         
                          
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and act of R may be defined as in Equation 5: 
         [0000]    
       
         
           
             
               
                 
                   act 
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           
                             - 
                             1 
                           
                         
                         3 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             
                               - 
                               1 
                             
                           
                           4 
                         
                          
                         
                            
                           
                             
                               R 
                               
                                 i 
                                 , 
                                 j 
                               
                             
                             - 
                             
                               R 
                               
                                 
                                   i 
                                   + 
                                   1 
                                 
                                 , 
                                 j 
                               
                             
                           
                            
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           
                             - 
                             1 
                           
                         
                         4 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             
                               - 
                               1 
                             
                           
                           3 
                         
                          
                         
                            
                           
                             
                               R 
                               
                                 i 
                                 , 
                                 j 
                               
                             
                             - 
                             
                               R 
                               
                                 i 
                                 , 
                                 
                                   j 
                                   + 
                                   1 
                                 
                               
                             
                           
                            
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where R i,j  refers to the i,j pixel of R, and likewise T i,j  refers to the i,j pixel of T. Block R is a rectangular area with a top-left pixel of R 0,0  and a bottom right pixel of R 3,3 , likewise block T is a rectangular area with a top-left pixel of T 0,0  and a bottom right pixel of T 3,3 . Equations (4) and (5) are indicative of the fact that the pixels surrounding R and T may also be used in the computation of sad and act. The activity of a block may be used to evaluate the reliability of corresponding motion estimation results. To accurately reflect reliability, act may have to be normalized against the corresponding SAD in terms of the number of absolute pixel differences, as shown below in Equation 6: 
         [0000]    
       
         
           
             
               
                 
                   nact 
                   = 
                   
                     
                       act 
                       * 
                       num_pixels 
                        
                       _in 
                        
                       _sad 
                     
                     
                       num_pixels 
                        
                       _in 
                        
                       _act 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where num_pixels_in_sad is the number of absolute pixel differences in the calculation of sad, and num_pixels_in_act is that of act, respectively. The term nact is the normalized activity of the block. Note that the surrounding pixels of R and T may be used in calculating sad and act as well. 
         [0062]    The foregoing can be repeated for the frames for each time period t−3, t−2, t−1, t+1, t+2, and t+3, resulting in a motion compensated back predicted higher resolution frame  320   t . 
       Motion Free Back Projection 
       [0063]    Referring now to  FIG. 7 , there is illustrated a block diagram describing motion-free back projection in accordance with an embodiment of the present invention. Subsequent to motion compensated back projection, the image  320   t ′ is subjected to processing for motion-free back projection (MCBP). The inputs to this block are the frame  320   t ′, and motion compensated back predicted higher resolution frame  320   t ″. The output from the MCBP processing block is the high resolution frame. 
         [0064]    Motion-free back projection between frame  320   t ′ and frame  320   t ″ are performed similar to motion-compensated back projection, except that all motion vectors are set to zero and the weighting factor λ is a constant. 
         [0065]      FIG. 8  is an illustration of an exemplary block diagram of a system in accordance with an embodiment of the present invention. The system comprises an integrated circuit  802  comprising high resolution image estimation module  820  that generates an initially estimated high resolution image by processing images. Also included are a motion estimation module  830  for motion estimation, a motion-compensated back projection module  840 , a direct memory access  885 , and a cache  890  for motion-compensated back projection, and a motion-free back projection module  850  for motion-free back projection. 
         [0066]    The modules  820 - 840  can be implemented in software, firmware, hardware (such as processors or ASICs which may be manufactured from or using hardware description language coding that has been synthesized), or using any combination thereof. The embodiment may further include a processor  870 , and an input interface  810  through which the lower resolution images are received and an output interface  860  through which the higher resolved images are transmitted. 
         [0067]    An off-chip memory  880  stores data after interpolation, after motion estimation  830 , and after the motion compensation back projection  840 . On-chip memory  851  stores portions of the higher resolution frames that are being updated. Program memory  852  stores instruction for execution by the processor  870 . 
         [0068]    It is noted that the foregoing image processing involves the transfer and processing of large amounts of data. Storing larger amounts of the data within the integrated circuit  802  increases the cost and consumes more area on the integrated circuit  802 . Storing larger amounts of data in the off-chip memory  880  results in lower access times, and consequently, lower throughput. 
         [0069]    In certain embodiments of the present invention, the pixels in the low-resolution frames are traversed according to a certain temporal and spatial order, and the motion-compensated back-projection processes for all the low-resolution pixels are serialized. The motion-compensation back-projection for a low-resolution pixel runs to its completion before the motion-compensation back-projection for the next low-resolution pixel begins. For each low-resolution pixel, the corresponding high-resolution pixels are read from memory, updated, and then written back to the memory. In a real-time system, the foregoing processes for all the low-resolution pixels may be completed in a fixed frame interval. 
         [0070]    The foregoing may advantageously use very small, shared on-chip storage that is enough to hold the high-resolution pixels to be updated for a low-resolution pixel. Additional bandwidth can be allocated for reading/writing the high-resolution pixels to/from off-chip memory. 
         [0071]    In another embodiments, each low-resolution frame may have its own high-resolution buffer for MCBP to work on. At any point of time, a portion of the pixels in a high-resolution buffer corresponding to a low-resolution frame may be retired from the MCBP if they are no longer impacted by the MCBP process for the remainder pixels in the low-resolution frame. The retired pixels from the high-resolution buffer may be conceptually moved to another high-resolution buffer corresponding to the next low-resolution frame, and the high-resolution pixels that are no longer impacted by any low-resolution pixels are output to HR(t). This approach may use a small amount of bandwidth for reading/writing the high-resolution frame to/from off-chip memory, and a low operating frequency since this approach may allow parallel processing of the multiple MCBP processes for the multiple low-resolution frames. Additionally, on-chip storage can be allocated to hold the multiple high-resolution buffers. 
         [0072]    MCBP may require significant computation resources, such as bandwidth, storage, and computational cycles. This is especially true in a real-time, embedded environment. Therefore, methods of implementing MCBP are needed that are efficient in terms of computation resources and also can offer various trade-offs among these resources. 
         [0073]    In certain embodiments of the invention, a patch of pixels in higher resolution frame  320   t  is processed to completion in the MCBP processes using all the low-resolution frames LR. 
         [0074]    Referring now to  FIG. 9 , there is illustrated a block diagram of the higher resolution frame  320   t  partitioned into non-overlapping blocks  905 , each block  905  having a size of dest_size_x*dest_size_y, which respectively represent the horizontal size and vertical size of the block. Shown on the left of  FIG. 9  is such a partition. For a block 905 at the position (m*dest_size_x, n*dest_size_y) in the partition, define its corresponding back-projection patch as the rectangle delimited by its top-left pixel 
         [0000]    
       
         
           
             
               ( 
               
                 
                   
                     
                       
                         
                           
                             m 
                             * 
                           
                            
                           dest_size 
                            
                           _x 
                         
                         - 
                         
                           
                             
                               patch_size 
                                
                               _x 
                             
                             - 
                             
                               dest_size 
                                
                               _x 
                             
                           
                           2 
                         
                       
                       , 
                     
                   
                 
                 
                   
                     
                       
                         
                           n 
                           * 
                         
                          
                         dest_size 
                          
                         _y 
                       
                       - 
                       
                         
                           
                             patch_size 
                              
                             _y 
                           
                           - 
                           
                             dest_size 
                              
                             _y 
                           
                         
                         2 
                       
                     
                   
                 
               
               ) 
             
               
           
         
       
     
         [0000]    and its bottom-right pixel 
         [0000]    
       
         
           
             
               ( 
               
                 
                   
                     
                       
                         
                           
                             
                               ( 
                               
                                 m 
                                 + 
                                 1 
                               
                               ) 
                             
                             * 
                           
                            
                           dest_size 
                            
                           _x 
                         
                         - 
                         1 
                         + 
                         
                           
                             
                               patch_size 
                                
                               _x 
                             
                             - 
                             
                               dest_size 
                                
                               _x 
                             
                           
                           2 
                         
                       
                       , 
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             ( 
                             
                               n 
                               + 
                               1 
                             
                             ) 
                           
                           * 
                         
                          
                         dest_size 
                          
                         _y 
                       
                       - 
                       1 
                       + 
                       
                         
                           
                             patch_size 
                              
                             _y 
                           
                           - 
                           
                             dest_size 
                              
                             _y 
                           
                         
                         2 
                       
                     
                   
                 
               
               ) 
             
               
           
         
       
     
         [0000]    where patch_size_x and patch_size_y represent respectively the horizontal size and vertical size of the patch. Each block  905  has a corresponding back-projection patch  910 . Note that the two patches of two neighboring blocks in the partition may overlap each other. 
         [0075]    Following a raster-scan order, each patch  910  is motion compensation back projected for the pixels in LR(n−k), . . . , LR(n+k) (or any other temporal order of them). After the MCBP processes are completed for the patch, the center block  905  in the patch and of size dest_size_x by dest_size_y is output. 
         [0076]    It is noted that in the MCBP processes for the patch  910 , all the pixels in the patch may be updated, but only the pixels at the center block  905  are output. The boundary pixels, the pixels that are in the patch  910  but not in the block  905  may have impact on the inner pixels in the patch during the MCBP process. Additionally, the boundary pixels may be further impacted by the MCBP processes of the neighboring patches  910 . 
         [0077]    Referring now to  FIG. 10 , there is illustrated a block diagram of a patch  910  and an the area  1005  in a low-resolution frame LR(n+j) that potentially impacts the patch  910  in MCBP, with the area being defined as the set of the blocks  1010  (each of size block_size_x*block_size_y) in LR(n+j) that, after motion-compensation, may potentially back-project into the patch. 
         [0078]    It is noted that the total number of blocks in the above defined area in LR(n+j) may increase with the motion range between LR(n+j) and LR(n), and this number may potentially become quite large. However, quite often, only a portion of the blocks in the area can actually be back-projected into the patch after considering their corresponding motion vectors, and this portion may become even smaller if some conditions on the motion vectors are imposed for a block to be used in MCBP. Therefore, to reduce the requirements on bandwidth for accessing low-resolution blocks, an upper-limit on the number of blocks that can be used in MCBP is imposed for a patch  910 . An example of such upper-limit is γ*(patch_size_x/block_size_x)*(patch_size_y/block_size_y), where γ is a constant parameter. 
         [0079]    In one embodiment, all the blocks in the area can be scanned in the low-resolution frame corresponding to a patch  910 . Each qualified block is processed in the MCBP  840  until the upper-limit is reached. Note that in scanning the low-resolution area, in certain embodiments, different scan orders may be used instead of the conventional raster-scan; for example, in one embodiment, the center blocks in the area are used first, spiraling to the outer blocks in the area. 
         [0080]    In another embodiment, the blocks can be scanned in the area in the low-resolution frame, and ranked according to a measurement of their corresponding motion quality. The blocks can be chosen from the top rank down until the limit is reached. 
         [0081]    It is noted that the foregoing allows parallel processing of multiple patches in the destination domain, since a patch may be processed independently of other patches. Another advantage is the relatively lower requirement of on-chip storage, since only a number of patches are required for high-resolution storage. 
         [0082]    Although some redundant operations may occur in the MCBP  840  due to the fact that the patch size is larger than the destination block size, this can be reduced by appropriately choosing the patch sizing and using cache, such as described in the U.S. patent application Ser. No. ______, which is incorporated herein by reference for all purposes. 
         [0083]    In other embodiments, instead of using the destination domain, the source domain can be used. A stripe in the low resolution frames can be defined as a row of blocks, each block having a size of block_size_x*block_size_y, and all being aligned with the block grids in the low-resolution frame. Shown in  FIG. 11  are a stripe in a low-resolution frame LR(n+j) and the area in SP(n) that may be potentially impacted by the stripe in MCBP. 
         [0084]    Referring now to  FIG. 11 , there is illustrated a block diagram describing an exemplary stripe  1105  in a lower resolution frame LR and the corresponding area  1110  in the higher resolution frame. The blocks of each stripe are back projected to the higher resolution frame following a certain order. 
         [0085]    Referring now to  FIG. 12 , there is illustrated a block diagram describing an exemplary order for the MCBP  840  in accordance with an embodiment of the present invention. The stripes are processed in the order  1201 ,  1202 ,  1203 , . . . ,  1210 ,  1211 . 
         [0086]    In certain embodiments of the present invention, the blocks in the two co-located stripes in LR(n±j) may be processed in ping-pong fashion; i.e., process a first block in  1201  in the MCBP  840 , then process a first block in  1202  which may be co-located with the first block in  1201 , then a second block in  1201 , then a second block in  1202  which may be co-located with the second block in  1201 , and so on. 
         [0087]    In certain embodiments of the present invention, the MCBP  840  may process in a stripe-based manner, top-to-bottom spatially and far-to-near (relative to LR(n)) temporally, but with some vertical offsets among the stripes at the low-resolution frames. Referring now to  FIG. 13 , there is illustrated an exemplary order for the MCBP  840 . The MCBP  840  proceeds starting with stripe  1301 , and proceeds to  1302  . . .  1311 . 
         [0088]    A high-resolution buffer in MCBP may still be shared among the MCBP processes for the low-resolution frames, since the motion ranges and thus the sizes of the MCBP support normally decrease as the temporal distance from LR(n+j) to LR(n) decreases. 
         [0089]    In certain embodiments of the present invention, the blocks in the two co-located stripes in LR(n±j) may be processed in ping-pong fashion; i.e., process a first block in  1301  in the MCBP  840 , then process a first block in  1302  which may be co-located with the first block in  1301 , then a second block in  1301 , then a second block in  1302  which may be co-located with the second block in  1301 , and so on. 
         [0090]    In certain embodiments of the present invention, the MCBP  840  can process the blocks in the multiple low-resolution frames in the following order. For each block in a low-resolution frame, a block-coordinate (bx, by) is assigned which specifies its block-column position and block-row position. The top-left block in a low-resolution frame has the coordinate of (0, 0). An example process order at any moment in MCBP is shown in the following, using the case of 9 low-resolution frames as an example:
       (bx, by) in  1301     (bx, by) in  1302     (bx-offset 3 _H, by-offset 3 _V) in  1303     (bx-offset 3 _H, by-offset 3 _V in  1304     (bx-offset 2 _H, by-offset 2 _V) in  1305     (bx-offset 2 _H, by-offset 2 _V in  1306     (bx-offset 1 _H, by-offset 1 _V) in  1307     (bx-offset 1 _H, by-offset 1 _V in  1308     (bx-offset 0 _H, by-offset 0 _V) in  1309         
 
         [0100]    In the above, offset 3 _H/V, offset 2 _H/V, offset 1 _H/V, and offset 0 _H/V are offsets in blocks in the horizontal and vertical directions, all relative to the position of the current block in LR(n±4). If the foregoing offsets are properly chosen, the MCBP  840  processes may potentially be performed in parallel within a shared high-resolution buffer. 
         [0101]    Referring now to  FIG. 14 , there is illustrated an exemplary higher resolution frame mapped to a shared buffer in accordance with an embodiment of the present invention. It is noted that the areas impacted  1415  by the current blocks in  1301  . . .  1309  do not overlap with each other. 
         [0102]    Accordingly, a high-resolution buffer may be shared between the MCBP  840  processes for the multiple low-resolution frames. Additionally, the MCBP  840  can perform the foregoing processes in parallel. Additionally, bandwidth efficiency in accessing the blocks of the low-resolution frames is improved, as a result of the stripe based pattern. 
         [0103]    Referring now to  FIG. 15 , there is illustrated a block diagram describing a parallel processing at the pixel level in the MCBP  840 . A block of 8×8 pixels  1505  in a low-resolution frame share the same motion, and that 6×6 pixels  1510  in a higher resolution frame are used in simulating a low-resolution pixel  1515 . For the 8×8 pixels in each low-resolution block, a raster-scan order may be followed in the MCBP  840 . Note that MCBP  840  in this manner is essentially sequential in two senses: 
         [0104]    (i) the high-resolution pixels updated in processing the current low-resolution pixel are subject to further updating in processing the subsequent low-resolution pixels in the block; 
         [0105]    (ii) in simulating a low-resolution pixel, the previously updated high-resolution pixels are used. 
         [0106]    Referring now to  FIG. 16 , in certain embodiments of the present invention, the 8×8 pixels  1505  in a low-resolution block can be partitioned into 4 quadrants  1605 , and each of which contains 4×4 pixels with a top-left pixel  1610 . Shown also are the high-resolution areas  1615  that are impacted by the four pixels top-left pixels  1610 . Note that if 6×6 pixels in the higher resolution are used to simulate a low-resolution pixel and thus are impacted by the low-resolution pixel, the four high-resolution areas  1615  corresponding to these four pixels  1610  do not overlap each other. Therefore, in MCBP, these four low-resolution pixels  1610  may be processed in parallel, assuming sufficient hardware resources exist. After the four pixels  1610  are processed, the four pixels to the right of the four pixels  1610  in the four quadrants may be processed in parallel, and so on until all the pixels in the block are processed. 
         [0107]    It is noted that in certain embodiments of the present invention, within the four quadrants in  1615 , other scan orders may be followed instead of the conventional raster scanning order. Additionally, in certain embodiments, different numbers of low-resolution pixels may be processed in parallel. 
         [0108]    As well, if a measure of motion quality is available at pixel-level, the MCBP  840  behavior may be adapted accordingly. For example, the strength of MCBP  840  may be increased for a low-resolution pixel having a smaller local SAD and decrease the strength of MCBP  840  for a low-resolution pixel having a larger local SAD, where the local SAD of a low-resolution pixel z may be calculated as the sum-of-absolute-difference between a window of pixels in LR(n+j) surrounding z and the corresponding motion-compensated pixels in LR(n). 
         [0109]    Note that this method does not require motion estimation at pixel-level but still offers pixel-level adaptive-ness in MCBP. An upper-limit may be be imposed on the number of pixels in a low-resolution block that are allowed to use in MCBP, for the potential benefit of reducing computation cycles for each low-resolution block. In such case, a fixed scan order of the low-resolution pixels in a block can be followed until the upper-limit is reached, or the pixels in the block can be ranked according to some pixel-level motion quality measurement the top-ranked pixels are chosen until the upper-limit is reached. 
         [0110]    In certain embodiments of the present invention, the foregoing allows a lower operation frequency of the MCBP  840  hardware, due to the parallel processing at pixel level. Another advantage is that it may be superior to the conventional raster scanning order in terms of the resulting picture quality, since it allows the effects of MCBP to diffuse across the resultant high-resolution frame more evenly in all directions, rather than imposing a diffusion from top-left to bottom-right within, across the entire frame. 
         [0111]    In certain embodiments of the present invention, the methods described in the above may be applied to both luma and chroma, or to luma only. In another embodiment, the pixel-level parallel MCBP may be used together with the destination-domain patch-based processing or the source-domain stripe-based processing. 
         [0112]    Example embodiments of the present invention may include such systems as personal computers, personal digital assistants (PDAs), mobile devices (e.g., multimedia handheld or portable devices), digital televisions, set top boxes, video editing and displaying equipment and the like. 
         [0113]    The embodiments described herein may be implemented as a board level product, as a single chip, application specific integrated circuit (ASIC), or with varying levels of the system integrated with other portions of the system as separate components. Alternatively, certain aspects of the present invention are implemented as firmware. The degree of integration may primarily be determined by the speed and cost considerations. 
         [0114]    While the present invention has been described with reference to certain embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the scope of the present invention. 
         [0115]    Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed, but that the present invention will include all embodiments falling within the scope of the appended claims and equivalents thereof.