Title of Invention

METHOD AND APPARATUS FOR DEBLOCKING EDGES IN A MACROBLOCK OF A VIDEO FRAME

Abstract

This invention is applicable to the area of removing blocking artifacts in block- based video compression. The invention explains a method of reducing computations by using macroblock shape information, in an In-loop and adaptive deblocking filter comprise the steps of, finding the number of partitions in macroblock; evaluating strength of partition; and deblocking all edges in macroblock which have non-zero strength. The said method can be applied to in- loop adaptive deblocking filters used in video coding technologies with standards like H.264 and MPEG.

Full Text

FIELD OF TECHNOLOGY This invention is applicable to the area of removing blocking artifacts in block-based video compression. Further, this invention relates to using shape of information of coded blocks to determine adaptive In-loop De-blocking filter strength. More particularly, this invention proposes a method of reducing computations by using macroblock shape information, in an in-loop and adaptive deblocking filter. DESCRIPTION OF RELATED ART Block'based video compression Block-based video compression may break up each video frame into macroblocks (MBs) of size 16x16 pixels (but not restricted to). A macroblock might be further sub-divided into blocks of rectangular blocks of smaller sizes. Two main types of coding techniques can be applied to encode information about the macroblock • Intra coding (no prediction from neighboring frames) • Inter coding (prediction from neighboring frames) Intra coding is typically used when the prediction from neighboring frame/s is very erroneous (like in the case of a new object entering the picture). Inter coding is useful when there is smooth motion in the video sequence. In Inter coding case, motion for a macroblock is estimated from neighboring frames (in time) and is transmitted as motion vectors (MVs) to the decoder. If the prediction is not perfect, the prediction error is also transmitted as residual information for the macroblock. This residual information is coded using transform-based coding to reduce bit-rate. The presence of residual data for a given macroblock is typically signaled using a parameter known as cbp (coded block pattern) in the transmitted bitstream. At the receiving end, the decoder uses the MVs and decoded neighboring frame information to reconstruct the motion-compensated macroblock. If cbp flag is set, then the decoder also decodes residual information and adds it to the motion-compensated macroblock to reconstruct the final decoded macroblock. In manner, the whole frame is decoded. Deblocking process Due to the block based nature of the process, blocking artifacts appear in the decoded image around the edges of the blocks. These artifacts can become quite pronounced when the quantization value used in the two blocks across an edge is different, thereby severely degrading output picture quality. As video compression standards have developed, increasing emphasis is being given on methods to reduce these blocking artifacts. Typically, the methods involve a "Deblocking filter" as a post-processing step on the output frame. This filter is applied across block edges to smoothen the transition of pixel values across the edge. The filter can be fixed or adaptive (based on the motion and/or residual information across the edge). Until recently, the deblocking filter was put forward as a post-processing step in the decoding process (H.263, Mpeg-1/2 and Mpeg-4 Part 2). Recently, the H.264 video coding standard (also known as Mpeg4 part 10) has introduced an in-loop, adaptive deblocking filter as a normative part of the coding/decoding process. An in-loop operation means that the deblocked frames are being used for prediction in future frames, while in a post-processing scenario the deblocked frames are simply presented at the output (without being used for prediction). The advantage of the filter being in-loop being that it guarantees output quality level, and also helps in compression (by increasing the quality of decoded reference images) [Reference]. Typically the adaptive nature of the filter is implemented by using a set of filters (of varying lengths) and deciding on a given filter after analysis of the state of pixels across the edge. For example, consider the H.264 standard, which defines an in-loop adaptive deblocking filter as a normative part of the standard [Figure 1]. Here, the smallest possible block size is 4x4 pixels. The deblocking filter therefore operates across each 4x4 edge (there are 32 such edges in a 16x16 macroblock [Reference]). By convention, while deblocking a macroblock, only the left and top boundary edges are deblocked in the context of the current macroblock. The bottom and rightmost boundary edges are deblocked in the context of the right (or bottom) macroblock. The filter is adaptive in nature and has four possible modes of operation. The modes differ in the length of the filter being applied across the edge. Each mode is assigned a strength value ranging from 0-3. Thus, deblocking each 4x4 edge involves two steps - strength determination and filtering. The relation of filter strength to the type of filtering is described below The strength determination process is shown in Figure 3. The three-step process evaluates the context across the 4x4 edge in terms of type of coding (intra or inter), reference frames used, presence of residual information and difference in motion vectors of the 4x4 blocks on each side of the edge [Reference]. The key weaknesses with the existing system are the following 1. Evaluation of strength of each edge 2. Strength evaluation is a costly process - it involves the loading and analysis of cbp, motion-vectors and reference frame information for each edge This means that for cases where the strength eventually comes out to be zero (skip MBs, no cbp and no motion cases, etc.), one still ends up performing all the steps of the flowchart in Figure 3. A study of the deblocking filter applied to various kinds of natural video sequences reveals that out of the four possible strength values, zero occurs most often (more than 50% of the time) [Reference]. In such cases, the related art performs significant amount of unnecessary computations. SUMMARY OF THE INVENTION The primary object of this invention is to invent a method of reducing computations by using macroblock shape information, in an in-loop and adaptive deblocking filter. This invention describes a method to use the shape of the block, in case of an in-loop and adaptive deblocking filter, to decide a subset among all the edges in a MB, which need to be evaluated for deblocking. This subset is composed of all edges which are internal to the shape of the block being analyzed. Accordingly, the present invention comprises a method of reducing computations by using macroblock shape information, in an In-loop and adaptive deblocking filter comprising the steps of: (a) finding the number of partitions in macroblock; (b) evaluating strength of partition; and (c) deblocking all edges in macroblock which have non-zero strength. Other advantages and features of the invention will become more clearly apparent from the following description of the embodiments of the invention given as non-restrictive examples only and represented in the accompanying drawings. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS Figure 1 depicts an example of an in-loop deblocking filter (in H.264 video encoder). Figure 2 describes the partitioning of a 16x16 macroblock into 16 4x4 blocks. Figure 3 depicts the steps involved in strength evaluation of each edge during the in-loop, adaptive deblocking process, as described in the H.264 standard Figure 4 describes the partitioning of a 16x16 macroblock into 4 8x8 blocks, as is done in the MPEG-4. Figure 5 depicts the various macroblock partitioning modes used in H.264 video coding standard. Figure 6 depicts the proposed generalized flow-chart for deblocking macroblock edges. Figure 7 depicts an example implementation of the generalized flow-chart for the case of H.264 standard. DETAILED DESCRIPTION OF THE INVENTION The preferred embodiments of the present invention will now be explained with reference to the accompanying drawings. It should be understood however that the disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms. The following description and drawings are not to be construed as limiting the invention and numerous specific details are described to provide a thorough understanding of the present invention, as the basis for the claims and as a basis for teaching one skilled in the art on how to make and/or use the invention. However in certain instances, well-known or conventional details are not described in order not to unnecessarily obscure the present invention in detail. Before going into the description of the invention, it is necessary to understand the illustrations of the prior art and that of the present invention as given exemplified in the accompanying drawings. Figure 1 depicts an example of an in-loop deblocking filter (in H.264 video encoder). The deblocking operation is applied on the reconstructed frame to remove blocking artifacts. This reconstructed frame is obtained by adding motion- compensated and residual data for each partition. The deblocked frame is used as a reference frame for encoding other frames. Figure 2 describes the partitioning of a 16x16 macroblock into 16 4x4 blocks. It enumerates the maximum number of edges (horizontal and vertical) across which deblocking can be done. The horizontal edges are labeled Hij and vertical edges are labeled Vy, where i and j denote row and column indices Figure 3 depicts the steps involved in strength evaluation of each edge during the in-loop, adaptive deblocking process, as described in the H.264 standard, j and k are two neighboring blocks which share the edge. Rj and RR are the reference frame indices used for blocks j and k respectively. MVj,x and MVj.y are motion-vectors components in x- and y-directions for block j. MVR.X and MVk,y are motion-vectors components in x- and y-directions for block k. Figure 4 describes the partitioning of a 16x16 macroblock into 4 8x8 blocks, as is done in the MPEG'-4 Part-2 Video coding standard. In this case, there are a maximum of four horizontal and four vertical edges that can be deblocked. Figure 5 depicts the various macroblock partitioning modes used in H.264 video coding standard. These modes progressively divide the macroblock into smaller partitions. The key observation to be made here is that the macroblock partitioning mode dictates the number of internal edges that might need deblocking. Therefore, a larger partition can result in fewer edges that need deblocking This invention proposes an adaptive de-blocking algorithm that utilizes a parameter that is readily available in all schemes of block-based video coding, which is shape of the predicted block. The shape of the predicted block can be used to reduce the number of edges over which the evaluation of the context change needs to be done. Typically, all block-based video coding algorithms place constraints on the context change permissible within a coded block of the video frame. We look at two examples below: MPEG'4 Video In MPEG-4 the possible block sizes for coding one macroblock (16x16 pixels) are as one 16x16 block or as four 8x8 blocks. Consequently, a macroblock in MPEG-4 can have a single motion vector or 4 motion vectors (one for each 8x8 block). Also, the transform used in MPEG-4 is an 8x8 transform, which means that the residual error signal in a predicted block can have up to four components, one from each 8x8 block. In MPEG-4 video, the edges that need to be de-blocked in one macroblock are shown in Figure 3. The context is constrained to change only across these edges (if it changes). H.264 Video In H.264, a single 16x16 macroblock can be predicted in one of the following ways, resulting in partitioning of the 16x16 macroblock: 1. As a single 16x16 block (1 partition) 2. As two 16x8 or 8x16 blocks (2 partitions) 3. As four 8x8 blocks (4 partitions) Further, each 8x8 block can be predicted as: 1. A single 8x8 block 2. Two 8x4 or 4x8 blocks 3. Four 4x4 blocks Additionally, the transform used in the H.264 video coding algorithm is a 4x4 transform, and hence the number of edges across which the context can change is greatly increased. All the edges that need de-blocking are shown in Figure 2. The context is constrained to change only across these edges (if it changes). Figure 7 depicts an example implementation of the generalized flow-chart for the case of H.264 standard. Using shape of the coded block in edge selection The shape of the coded block can give us information about whether a particular edge needs to be included in the set of candidate edges for de-blocking within a macroblock. This is because the shape of the block also sets constraints on the quantum of context change allowed within the block (as seen from the two examples above). We will see how we can apply the shape information to reduce the set of candidate edges that need to be evaluated for the in-loop de-blocking filter in H.264 video. Based on the shape of the coded block, certain edges can be eliminated from the candidate set and the evaluation of filter strength need not be performed on these edges. This is illustrated in Table, which shows the candidate edges for the first four macroblock coding modes. As an example, we explain how the set of candidate edges is ascertained for a few cases in Table 1. Candidate for 16x16 prediction with no residual - Rows 1 and 2 In this case, the coded macroblock satisfies the following conditions: 1. Coding mode is 16x16 2. There is no residual error between the predicted and original block. 3. There is at most one motion vector for the macroblock. In these modes the 16x16 area in the current frame is obtained by merely picking up the 16x16 area from the reference frame pointed to by the motion vector (or from the same position if MV = 0), and pasting it in the current location. Since the de-blocking filter is in-loop, we know for sure that the area that is being picked up from the reference frame has already been de-blocked. Also, since there is no residual error signal (cbp = 0), and we are predicting a complete 16x16 area, there will be no context change within the 16x16 area. Thus, referring to Figure 1, we need to evaluate filter strengths only for the edges mentioned in column 3 of rows 1 and 2 of Table 1, since we are sure that for all other edges, the strength will always evaluate to 0 (i.e. no filtering). By applying the knowledge of shape of the coded block, we have now reduced the candidate edges by 75 %. This means that the algorithm to evaluate the filter strength given in Figure 2 now need to be applied for 75 % less edges, thus reducing the total computation in the de-blocking of a macroblock of this type. Figure 6 depicts the proposed generalized flow-chart for deblocking macroblock edges. Here we present the exact steps involved in the optimized strength evaluation algorithm: 1 Find N = number of partitions in macroblock 2. if N is equal to One, and cbp is Zero, then only evaluate strength for macroblock boundary edges. Set strength values for all internal edges to zero. Goto Step 10. 3. If N is greater than One, let K be partition index, K e {0, N-1} 4. SetK=1 5. If residual information in partition K is equal to zero, skip all internal edges for that partition. Otherwise, evaluate strength for internal edges of partition. 6. Evaluate strength for top and left boundary edges of partition. 7. SetK=K+1. 8. If K is less than N, then go to Step 5. 9. If K is equal to N, evaluate strength for top and left boundary edges for macroblock. 10. Deblock all edges in macroblock which have non-zero strength. A graphical demonstration of the above algorithm is depicted in Figure 6. The proposed invention has the following advantages: 1. The invention can be applied to all in-loop adaptive deblocking filters used in video coding technologies. 2. Since shape information is available at the time of deblocking, no additional computation is needed for generating this information. 3. The invention can be directly applied to existing standards like H.264 and MPEG. 4. In-loop adaptive deblocking filters are known in the industry to be computationally complex to implement - this invention provides a method to significantly decrease computations. 5. The computational savings imparted by this invention are dependant on the video sequence. Our invention gives us best savings in case of low-to-medium motion video sequences. At the same-time, for very high-motion or high- texture video sequences, the increase in computation is minimal. It will also be obvious to those skilled in the art that other control methods and apparatuses can be derived from the combinations of the various methods and apparatuses of the present invention as taught by the description and the accompanying drawings and these shall also be considered within the scope of the present invention. Further, description of such combinations and variations is therefore omitted above. It should also be noted that the host for storing the applications include but not limited to a computer, mobile communication device, mobile server or a multi function device. Although the present invention has been fully described in connection with the preferred embodiments thereof with reference to the accompanying drawings, it is to be noted that various changes and modifications are possible and are apparent to those skilled in the art. Such changes and modifications are to be understood as included within the scope of the present invention as defined by the appended claims unless they depart there from. WE CLAIM 1. A method of reducing computations by using macroblock shape information, in an In-loop and adaptive deblocking filter comprising the steps of: (a) finding the number of partitions in macroblock; (b) evaluating strength of partition; and (c) deblocking all edges in macroblock which have non-zero strength. 2. A method as claimed in claim 1 wherein the presence of residual data for a given macroblock is typically signaled using a cbp (coded block pattern) in the transmitted bitstream. 3. A method as claimed in claim 1 wherein if number of partitions in macroblock is equal to One, and cbp is Zero, then only evaluate strength for macroblock boundary edges. 4. A method as claimed in claim 1 wherein if number of partitions in macroblock is equal to One, and cbp is Zero, then strength values for all internal edges is set to zero and a deblocking is performed in all edges in macroblock which have non-zero strength. 5. A method as claimed in claim 1 wherein if number of partitions in macroblock is greater than one then partition index is set to one. 6. A method as claimed in claim 1 wherein if residual information in partition index is equal to zero, skip all internal edges for that partition. 7. A method as claimed in claim 1 wherein if residual information in partition index is not equal to zero strength for internal edges of partition is evaluated. A method as claimed in claim 1 wherein evaluating the strength of partition involve evaluating strength for top and left boundary edges of partition. A method as claimed in claim 1 wherein after evaluation the partition index is incremented. .A method as claimed in claim 1 wherein the strength evaluation is done until partition index is less than number of partitions in macroblock. .A method as claimed in claim 1 wherein if partition index is equal to number of partitions in macroblock. strength for top and left boundary edges for macroblockis evaluated. .A method as claimed in claim 1 wherein deblocking all edges in macroblock which have non-zero strength is performed. I. A method as claimed in claim 1 wherein adaptive de-blocking utilizes a parameter which is shape of the predicted block. .A method as claimed in claim 1 wherein shape of the predicted block can be used to reduce the number of edges over which the evaluation of the context change needs to be done. .A method as claimed in claim 1 wherein the shape of the coded block gives information about whether a particular edge needs to be included in the set of candidate edges for de-blocking within a macroblock. I. A method as claimed in claim 1 wherein the said method can be applied to in-loop adaptive deblocking filters used in video coding technologies with standards like H.264 and MPEG. .A method of reducing computations by using macroblock shape information, in an In-loop and adaptive deblocking filter such as substantially herein described particularly with reference to the accompanying drawings.

Documents:

1468-CHE-2004 CORRESPONDENCE OTHERS 30-05-2012.pdf

1468-CHE-2004 AMENDED CLAIMS 25-05-2012.pdf

1468-CHE-2004 AMENDED CLAIMS 26-06-2012.pdf

1468-CHE-2004 AMENDED PAGES OF SPECIFICATION 25-05-2012.pdf

1468-CHE-2004 AMENDED PAGES OF SPECIFICATION 26-06-2012.pdf

1468-CHE-2004 CORRESPONDENCE OTHERS 25-05-2012.pdf

1468-CHE-2004 EXAMINATION REPORT REPLY RECEIVED 26-06-2012.pdf

1468-CHE-2004 FORM-1 25-05-2012.pdf

1468-CHE-2004 FORM-13 19-06-2006.pdf

1468-CHE-2004 FORM-13 26-06-2012.pdf

1468-CHE-2004 OTHER PATENT DOCUMENT 25-05-2012.pdf

1468-CHE-2004 POWER OF ATTORNEY 25-05-2012.pdf

1468-che-2004-abstract.pdf

1468-che-2004-claims.pdf

1468-che-2004-correspondnece-others.pdf

1468-che-2004-description(complete).pdf

1468-che-2004-description(provisional).pdf

1468-che-2004-drawings.pdf

1468-che-2004-form 1.pdf

1468-che-2004-form 26.pdf

1468-che-2004-form 5.pdf