Title of Invention

A METHOD FOR PERFORMING INTRA PREDICTION ON A VIDEO SEQUENCE

Abstract The present invention relates to the field of video data processing. More specifically, the invention describes a method for adaptive switching of constrained intra prediction tool for enhanced coding gain of H.264 encoder. H.264 provides option to transmit encoded data as intra-coded macroblock or inter-coded macroblock. The invention describes a method for dynamic selection between intra-coded macroblock and inter-coded macroblock based on error determination for both the coding methods. The method provides enhanced compression of video data with reduced error in transmission.
Full Text FIELD OF INVENTION
The present invention relates to the field of video data processing. Particularly the invention describes a method for efficient video coding using H.264/AVC video encoder. More particularly the present invention relates to a method for efficient video coding using H.264/AVC video encoder.
DESCRIPTION OF RELATED ART
H.264/AVC is newest video coding standard of the ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG). The main goals of the H.264/AVC standardization effort have been enhanced compression performance and provision of a "network-friendly" video representation addressing applications like video telephony, storage, broadcast, streaming, etc.
Relative to prior video coding standards H.264 provides additional tools and greater flexibility for achieving higher coding gains. One such tool is intra prediction. The coding efficiency of intra macroblocks is greatly improved by directional spatial prediction. Unlike some other previous standards (H.263+, MPEG 4 Visual) where intra prediction has been conducted in the transform domain intra prediction in H.264/AVC is always conducted in the spatial domain, by referring to neighboring samples of previously coded blocks which are to the left and/or above the block to be predicted. Intra prediction means that the samples of a macroblock (MB) are predicted by using only information of already transmitted macroblocks of the same image.

There are two types of intra prediction in H.264 namely Intra 4x4 and Intra 16x16. In intra 4x4, each 4x4 block will be predicted from already coded neighboring blocks and in intra 16x16; each MB is predicted from already coded neighboring macroblocks. When neighboring macroblocks of an intra MB are inter-coded, this may incur error propagation in environments with transmission errors that propagate due to motion compensation into inter-coded macroblocks. To avoid this error, H.264/AVC provides constrained intra prediction tool. When Constrained Intra prediction is enabled, prediction can be performed only from intra-coded neighboring macroblocks. This tool can be operated in two modes:
Enabled Mode: Intra prediction can be performed only from neighboring intra-coded macroblocks.
Disabled Mode: No constraints on Intra prediction, prediction can be performed from neighboring inter-coded macroblocks as well.
If we forget about the transmission error and focus on compression then enabling or disabling constrained intra prediction will drastically affect the coding efficiency of inter slices (P or B slices). The decision as to enable or disable constrained intra prediction will play a significant role in deciding the compression efficiency of the encoder. From our experiments, we observed that for certain kind of sequences disabling constrained intra prediction (CIP) gave better compression then enabling CIP and for some kind of sequences we just observed the opposite.

The performance of each mode depends on the characteristics of video sequence. If we configure the encoder to a particular mode based on the characteristics of video sequence we get better compression. Currently there exists no algorithm which intelligently enables or disables constrained intra prediction tool based on characteristics of video sequence. Human intervention is needed at the start of encoding for enabling or disabling CIP tool. There is no mechanism as such which automatically selects the mode based on certain characteristics of video. Therefore there is a loss in coding gain.
The patent US6907071B2 relates to the field of video coding using H.26L standard. The patent describes a method for a selection between full prediction and limited prediction for intra-coding of a macroblock. According to the method, the choice between full prediction and limited prediction can be signalled explicitly using a code word for each macroblock. However, the signalling is not based on a flag (constrainedjntra__pred_flag) as being used in H.264 standard. Moreover, the concept of signalling based on error computations and without involving user intervention has also not been explicitly mentioned in the patent.
SUMMARY OF THE INVENTION
H.264/AVC is the latest standard for video compression. It provides various tools for video coding, covering wide range of multimedia applications like storage, broadcast, streaming applications. Each tool can be operated in different mode. The choice of the configuration of these tools for coding video will decide the compression efficiency of the encoder. One such tool is constrained intra prediction. In general, user configures the tool and the mode remains static for the

complete duration of the sequence. This results in poor compression because the characteristic of the frames does not remain same for the complete duration of the sequence. In this patent an algorithm is proposed, which automatically enables or disables constrained intra prediction for each inter slice based on characteristics of video sequence. The proposed method will help in designing intelligent and high coding gain H.264/AVC encoders.
Accordingly this invention explains a method for efficient video coding using
H.264/AVC video encoder comprising the steps of:
providing a Constrained Intra Prediction (CIP) tool where the CIP tool in enable mode allowing intra-coding using only intra-coded neighbouring macroblocks; and
allowing intra-coding using both intra-coded as well as inter-coded neighbouring macroblocks by the CIP tool in the disabled mode;
where dynamic selection between CIP enable and disable mode is done based on error determination for both the coding modes.
In H.264/AVC standard, constrained intra prediction is signaled through a flag "constrainedjntra_pred_flag" in picture parameter set (PPS) where two PPS are encoded, in one PPS signal flag disabled and in other signal flag enabled. When adaptively switching the flags for each slice, corresponding PPS is mapped to the respective slices which ensure correct decoding of each slice. For a given P or B slice, determination is made first whether to enable or disable constrained intra

-prediction by using constrained intra prediction switching .After finding out the mode of the CIP tool, the slice is encoded accordingly and if mode is disabled for the slice, then for all intra coded macroblocks constrained intra prediction is performed and if enabled perform normal intra prediction. While switching the constrained intra prediction tool ,for each slice, processing begins from second MB and at the start of each slice, the variables D16, E16, D4 and E4 are initialized to zero where these variables keep count of the macroblocks and 4x4 boundary blocks meeting certain conditions. For each MB, 16x16 intra predictions is performed where for the intra prediction original neighboring macroblocks are used. Of all the possible 16x16 predictions, the best prediction based on SATD (SUM of Absolute Hadamard Transform Difference) criteria is found out where the prediction mode resulting in least SATD value is considered the best mode which is SATD16. For the current MB calculate prediction error by predicting from a flat 16x16 DC block with value 128 at each pixel location the computed SATD for this prediction error is taken as SATDm. If SATD16 E16 then constrained intra prediction tool for the current slice is disabled otherwise 4x4 boundary blocks is processed. When processing at 4x4 levels, we consider only boundary blocks of a MB where for intra prediction of 4x4 boundary blocks prediction is done from samples of the neighboring macroblocks but for non-boundary blocks, only boundary blocks are considered. While processing of 4x4 boundary blocks for each boundary block of a current MB, 4x4 Intra predictions are performed using samples of original neighboring macroblocks. Of all the possible 4x4 predictions, the best prediction based on SATD criteria id found where the prediction mode

resulting in least SATD value is considered best mode which is SATD4. For the current boundary block prediction error is calculated by predicting from a flat 4x4 DC block with value 128 at each pixel location where SATD is computed for this prediction error having value SATDb. If SATD4 E4 then constrained intra prediction tool is disabled for the current slice and enable the constrained intra prediction. The slice are finally encoded with appropriate mode of the constrained intra prediction tool. The said method is repeated for all the inter slices (P or B) till the sequence is completely encoded. These and other objects, features and advantages of the present invention will become more apparent from the ensuing detailed description of the invention taken in conjunction with the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 shows the block Diagram of the proposed invention.
Figure 2 shows the block Diagram of 16x16 Intra Prediction and DC Block Predictions.
Figure 3 shows the macroblock with 4x4 boundary blocks.
Figure 4 shows the block diagram of 4x4 Intra Prediction and DC Block Predictions.
Figure 5 shows the flowchart for proposed invention scheme.

Figure 6 shows the flowchart for 4x4 boundary block processing.
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 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.
For certain slices enabling constrained intra prediction will result in better coding efficiency than disabling it and for some slices we just observe the opposite. So the objective of the invention is to adaptively enable or disable constrained intra prediction for each inter slice in order to achieve higher coding gains. In H.264/AVC standard, constrained intra prediction is signaled through a flag "constrained_intra_pred_flag" in picture parameter set (PPS). We need to encode two PPS, in one PPS we signal flag disabled and in other we signal flag enabled. So when we adaptively switch the flags for each slice, corresponding PPS can be mapped to the respective slices which will ensure correct decoding of each slice.

The block diagram of the proposed invention scheme is shown in Figure 1. For a given P or B slice, we will first determine whether to enable or disable constrained intra prediction by using constrained intra prediction switching algorithm. After finding out the mode of the CIP tool, we encode the slice accordingly. If mode is disabled for the slice, then for all intra coded macroblocks constrained intra prediction is performed. If the mode is enabled we will perform normal intra prediction.
The algorithm for switching the constrained intra prediction tool is as follows:
• For each slice, processing will begin from second MB and no processing
will be done for the first MB of a slice. At the start of each slice, the
variables D16, E16, D4 and E4 are initialized to zero. These variables keep
count of the macroblocks and 4x4 boundary blocks meeting certain
conditions.
• For each MB, we will perform 16x16 Intra predictions. Here for intra
prediction since reconstructed prediction samples are not available,
samples of original neighboring macroblocks will be used.

• Of all the possible 16x16 predictions, we will find out the best prediction
based on SATD (SUM of Absolute Hadamard Transform Difference)
criteria. Refer to the block diagram shown in Figure 2. The prediction
mode resulting in least SATD value is considered best mode. SATD16 is
value of the SATD for the best mode.
• For the current MB calculate prediction error by predicting from a flat 16x16

DC block with value 128 at each pixel location. Compute SATD for this prediction error and let this value be SATDm. The process is shown in Figure 2.
• If SATD16 • Repeat the above steps for all the macroblocks in a slice.
• At the end of slice, if D16 > E16 than disable constrained intra prediction
tool for the current slice otherwise process 4x4 boundary blocks. The
flowchart for the switching algorithm is shown in Figure 5 and Figure 6.
• When processing at 4x4 levels, we consider only boundary blocks of a MB.
The boundary blocks are shown in Figure 3. For intra prediction of 4x4
boundary blocks prediction is done from samples of the neighboring
macroblocks but for non-boundary blocks, the neighboring blocks are
within the current MB. Hence only boundary blocks are considered.
The steps involved in processing of 4x4 boundary blocks are as follows:
• The block diagram for processing at 4x4 levels is shown in figure 4.
• For each boundary block of a current MB, we will perform 4x4 Intra
predictions. Here for intra prediction since reconstructed prediction
samples are not available, samples of original neighboring macroblocks will
be used.
• Of all the possible 4x4 predictions, we will find out the best prediction
based on SATD criteria. The prediction mode resulting in least SATD
value is considered best mode. SATD4 is value of the SATD for the best
mode.
• For the current boundary block calculate prediction error by predicting from

a flat 4x4 DC block with value 128 at each pixel location. Compute SATD for this prediction error and let this value be SATDb. The process is shown in Figure 4.
• If SATD4 • Repeat the above steps for all the boundary blocks of all the macroblocks
in a slice.
• At the end of slice, if D4 > E4 than disable constrained intra prediction tool
for the current slice otherwise enable the constrained intra prediction. The
flowchart for the 4x4 block processing is shown in Figure 6.
• Finally encode the slice with appropriate mode of the constrained intra
prediction tool.
• The above process will be repeated for all the inter slices (P or B) till the
sequence is completely encoded.
With the proposed invention we are intelligently and automatically configuring the constrained intra prediction for each P or B slice, thereby achieving compression gain. We achieve better compression if the prediction error is less. Prediction error depends upon how good the intra prediction and which in turn depends upon the prediction samples of neighboring macroblocks. The nature of prediction samples is governed by the modes of the constrained intra prediction tool. Hence we measure prediction error under different modes. The mode resulting in least prediction error will ultimately influence the switching algorithm in deciding the mode. Hence we will achieve better compression gain than static configuration of only enabling or disabling constrained intra prediction for the entire sequence.

With this invention, we can drastically improve the coding efficiency of H.264 encoders. No user interaction is needed for deciding the constrained intra prediction mode. Invention automatically configures the mode for each slice making the encoder completely intelligent.
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 microchip, microprocessor, handheld communication device, computer, rendering device 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.

GLOSSARY OF TERMS, DEFINITIONS AND REFERENCES THEREOF
Inter-coded: Coding of a block, macroblock, slice, or picture that uses prediction
derived from decoded samples of reference pictures other than the current
decoded picture.
Intra coded: Coding of a block, macroblock, slice, or picture that uses prediction
derived from the decoded samples of the same decoded slice.
SATD: Sum of absolute Hadamard transformed difference.
Boundary Blocks: Blocks whose prediction samples belong to the neighboring
macroblocks.
Non Boundary Blocks: Blocks whose prediction samples belong to the
neighboring blocks of the current macroblock.

WE CLAIM
1. A method for efficient video coding using H.264/AVC video encoder comprising
the steps of:
(a) providing a Constrained Intra Prediction (CIP) tool where the CIP
tool in enable mode allowing intra-coding using only intra-coded
neighbouring macroblocks; and
(b) allowing intra-coding using both intra-coded as well as inter-coded
neighbouring macroblocks by the CIP tool in the disabled mode;
where dynamic selection between CIP enable and disable mode is done based on error determination for both the coding modes.
2. A method as claimed in claim 1 wherein in H.264/AVC standard, constrained
intra prediction is signaled through a flag "constrainedjntra_pred_flag" in
picture parameter set (PPS) where two PPS are encoded, in one PPS signal
flag disabled and in other signal flag enabled.
3. A method as claimed in claim 1 wherein when adaptively switching the flags
for each slice, corresponding PPS is mapped to the respective slices which
ensure correct decoding of each slice.

4. A method as claimed in claim 1 wherein for a given P or B slice, determination
is made first whether to enable or disable constrained intra prediction by using
constrained intra prediction switching .
5. A method as claimed in claim 1 wherein after finding out the mode of the CIP
tool, the slice is encoded accordingly and if mode is disabled for the slice, then
for all intra coded macroblocks constrained intra prediction is performed and if
enabled perform normal intra prediction.
6. A method as claimed in claim 1 wherein while switching the constrained intra
prediction tool ,for each slice, processing begins from second MB and at the
start of each slice, the variables D16, E16, D4 and E4 are initialized to zero
where these variables keep count of the macroblocks and 4x4 boundary
blocks meeting certain conditions.
7. A method as claimed in claim 1 wherein for each MB, 16x16 intra predictions is
performed where for the intra prediction original neighboring macroblocks are
used.
8. A method as claimed in claim 1 wherein of all the possible 16x16 predictions,
the best prediction based on SATD (SUM of Absolute Hadamard Transform
Difference) criteria is found out where the prediction mode resulting in least
SATD value is considered the best mode which is SATD16.

9. A method as claimed in claim 1 wherein for the current MB prediction error is
calculated by predicting from a flat 16x16 DC block with value 128 at each
pixel location the computed SATD for this prediction error is taken as
SATDm.
10. A method as claimed in claim 1 wherein if SATD16 incremented otherwise E16 is incremented .
11. A method as claimed in claim 1 wherein at the end of slice, if D16 > E16 then
constrained intra prediction tool for the current slice is disabled otherwise 4x4
boundary blocks is processed.
12. A method as claimed in claim 1 wherein when processing at 4x4 levels, only
boundary blocks of a MB is considered where for intra prediction of 4x4
boundary blocks prediction is done from samples of the neighboring
macroblocks but for non-boundary blocks, only boundary blocks are
considered.
13. A method as claimed in claim 1 wherein while processing of 4x4 boundary
blocks for each boundary block of a current MB, 4x4 Intra predictions are
performed using samples of original neighboring macroblocks.

14. A method as claimed in claim 1 wherein of all the possible 4x4 predictions, the
best prediction based on SATD criteria is found where the prediction mode
resulting in least SATD value is considered best mode which is SATD4.
15. A method as claimed in claim 1 wherein for the current boundary block
prediction error is calculated by predicting from a flat 4x4 DC block with value
128 at each pixel location where SATD is computed for this prediction error
having value SATDb.
16. A method as claimed in claim 1 wherein if SATD4 otherwise E4 is incremented.
17. A method as claimed in claim 1 wherein the said method is repeated for all the
boundary blocks of all the macroblocks in a slice.
18. A method as claimed in claim 1 wherein at the end of slice, if D4 > E4 then
constrained intra prediction tool is disabled for the current slice.
19. A method as claimed in claim 1 wherein the slice are finally encoded with
appropriate mode of the constrained intra prediction tool.
20. A method as claimed in claim 1 wherein the said method is repeated for all the
inter slices (P or B) till the sequence is completely encoded.

21. A method for efficient video coding using H.264/AVC video encoder substantially described particularly with reference to the accompanying drawings.
Dated this 29th day of December 2006

Documents:

2494-CHE-2006 AMENDED CLAIMS 16-05-2013.pdf

2494-CHE-2006 AMENDED PAGES OF SPECIFICATION 16-05-2013.pdf

2494-CHE-2006 CORRESPONDENCE OTHERS 16-05-2013.pdf

2494-CHE-2006 EXAMINATION REPORT REPLY RECEIVED 01-03-2013.pdf

2494-CHE-2006 FORM-13 01-03-2013.pdf

2494-CHE-2006 OTHER PATENT DOCUMENT 01-03-2013.pdf

2494-CHE-2006 POWER OF ATTORNEY 16-05-2013.pdf

2494-CHE-2006 AMENDED CLAIMS 01-03-2013.pdf

2494-CHE-2006 AMENDED PAGES OF SPECIFICATION 01-03-2013.pdf

2494-CHE-2006 FORM-1 01-03-2013.pdf

2494-CHE-2006 FORM-5 01-03-2013.pdf

2494-CHE-2006 POWER OF ATTORNEY 01-03-2013.pdf

2494-CHE-2006 FORM 1.pdf

2494-CHE-2006 FORM 18.pdf

2494-che-2006-abstract.pdf

2494-che-2006-claims.pdf

2494-che-2006-correspondnece-others.pdf

2494-che-2006-description(complete).pdf

2494-che-2006-drawings.pdf

2494-che-2006-form 1.pdf


Patent Number 256690
Indian Patent Application Number 2494/CHE/2006
PG Journal Number 29/2013
Publication Date 19-Jul-2013
Grant Date 16-Jul-2013
Date of Filing 29-Dec-2006
Name of Patentee SAMSUNG INDIA SOFTWARE OPERATIONS PRIVATE LIMITED
Applicant Address BAGMANE LAKEVIEW, BLOCK B' NO.66/1, BAGMANE TECH PARK, C V RAMAN NAGAR, BYRASANDRA, BANGALORE-560093, KARNATAKA, INDIA
Inventors:
# Inventor's Name Inventor's Address
1 KIRAN VARAGANTI EMPLOYED AT SAMSUNG INDIA SOFTWARE OPERATIONS PVT LTD., HAVING ITS OFFICE AT, BAGMANE LAKEVIEW, BLOCK B' NO.66/1, BAGMANE TECH PARK, C V RAMAN NAGAR, BYRASANDRA, BANGALORE-560093, KARNATAKA, INDIA
PCT International Classification Number H04B 1/66
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 NA