FIELD OF INVENTION

[001] The present invention relates to video coding and more particularly relates to a method and apparatus for determining the partitioning layout of the coding unit for encoding the video. The present application is based on, and claims priority from, an Indian Application Number, 3651/CHE/2012 filed on 4th September, 2012, the disclosure of which is hereby incorporated by reference herein.

BACKGROUND OF INVENTION

[002] Digital video coding technology enables the efficient storage and transmission of the vast amounts of visual data that compose a digital video sequence. With the development of international digital video coding standards, digital video is playing an important role in a host of applications, ranging from video conferencing and digital video discs (DVDs) to digital TV, mobile video, and Internet video streaming and sharing. Digital video coding standards provide the interoperability and flexibility needed to fuel the growth of digital video applications worldwide.

[003] There are two international organizations currently responsible for developing and implementing digital video coding standards: the Video Coding Experts Group (“VCEG”) under the authority of the International Telecommunication Union Telecommunication Standardization Sector (“ITU-T”) and the Moving Pictures Experts Group (“MPEG”) under the authority of the International Organization for Standardization (“ISO”) and the International Electro technical Commission (“IEC”). The ITU-T has developed the H.26x (e.g., H.261, H.263, and H.264) family of video coding standards and the ISO/IEC has developed the MPEG-x (e.g., MPEG-1, MPEG-4) family of video coding standards.

[004] The H.264 video coding standard provides high video quality at substantially lower bit rates (up to 50%) than previous video coding standards. The H.264 standard provides enough flexibility to be applied to a wide variety of applications, including low and high bit rate applications as well as low and high resolution applications, such as video telephony, video gaming, and video surveillance and so on.

[005] The H.264 video coding standard has a number of advantages that distinguishes from other existing video coding standards, while sharing common features with those standards. The basic video coding structure of H.264 is as described herein. H.264 video coder divides each video frame of a digital video sequence into 16×16 blocks of pixels (referred to as “macro blocks”) so that processing of a frame may be performed at a block level. Each macro block may be coded as an intra-coded macro block by using information from its current video frame or as an inter-coded macro block by using information from its previous frames. Intra-coded macro blocks are coded to exploit the spatial redundancies that exist within a given video frame through transform, quantization, and entropy (or variable-length) coding. Inter-coded macro blocks are coded to exploit the temporal redundancies that exist between macro blocks in successive frames, so that only changes between successive frames need to be coded. This is accomplished through motion estimation and compensation.

[006] Because of its high coding efficiency, the H.264 video coding standard is able to compress multimedia contents at low bit rates while achieving good visual quality.

[007] Further, the video encoders have always been one of the resource consuming processes in the modern consumer electronic devices. The demand for more compression for sustaining a number of streaming solutions has led to an increase in complexity of the encoders. Though there are lots of advancements in the processor technologies, some directly resulting in more power consumption, it is not sufficient enough to get real time performance with latest encoders. All the modern encoders have a number of tools to attain the desired compression. One among them is the selection of mode based on spatial and temporal characteristics, such as texture and motion vectors respectively, that gives best compression. The selection is usually done using brute search by encoding and calculating the cost of all different possible modes and selecting the best among them. The brute force search performs encoding for all the possible block sizes and selects the partition size that gives the best compression. However, this is a tedious process, time consuming task and may not be efficient in real time scenarios.

[008] In the light of above discussion, there is a need for a method and apparatus that provides a mechanism for partitioning of the coding unit to different blocks based on spatial and temporal characteristics of the coding unit.

OBJECT OF INVENTION

[009] The principal object of the embodiments herein is to provide a method and apparatus that reduces the complexity of partition search performed for determining the partition layout of a coding unit in a quad tree based video codec.

[0010] Another object of the invention is to provide a method and apparatus that uses a gradient and collocated motion compensated Sum of Absolute Differences (SAD) characteristics of a coding unit for determining the best partition layout.

SUMMARY

[0011] Accordingly the invention provides a method for video processing, wherein the method comprises obtaining a gradient for at least one coding unit in at least one video frame and determining a mode of partition layout for encoding the at least one video frame based on obtained gradient, wherein the mode of partition layout is determined when a standard deviation calculated from the obtained gradients of the frame reaches a threshold. Further, the method comprises optimizing the determined mode of partition layout by reducing number of partitions of the at least one video frame and encoding the at least one coding unit with the optimized mode of partition layout.

[0012] Accordingly the invention provides an apparatus for video processing wherein the apparatus is configured to obtain a gradient for at least one coding unit in at least one video frame and the apparatus is configured to determine a mode of partition layout for encoding the at least one video frame based on the obtained gradient, wherein the partition layout is determined when a standard deviation calculated from the obtained gradient of the frame reaches a threshold. Further, the apparatus is configured to optimize the determined mode of partition layout by reducing number of partitions of the at least one video frame and the apparatus is further configured to encode the at least one coding unit with the optimized mode of partition layout.

[0013] These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings. It should be understood, however, that the following descriptions, while indicating preferred embodiments and numerous specific details thereof, are given by way of illustration and not of limitation. Many changes and modifications may be made within the scope of the embodiments herein without departing from the spirit thereof, and the embodiments herein include all such modifications.

BRIEF DESCRIPTION OF FIGURES

[0014] This invention is illustrated in the accompanying drawings, throughout which like reference letters indicate corresponding parts in the various figures. The embodiments herein will be better understood from the following description with reference to the drawings, in which:

[0015] FIG. 1 illustrates the block diagram of an apparatus for video processing that includes various modules, according to embodiments as disclosed herein;

[0016] FIG. 2 illustrates a flow diagram explaining the various steps involved in determining the best partition layout of coding unit, according to the embodiments disclosed herein;

[0017] FIG. 3 illustrates an exemplary motion vector prediction method for calculating the inter mode SAD, according to the embodiments as disclosed herein;

[0018] FIG. 4 illustrates a method for performing two mode search for optimizing the determined partition layout, according to the embodiments as disclosed herein; and

[0019] FIG. 5 illustrates a computing environment implementing the method and apparatus for determining the partition layout of the coding unit, according to the embodiments as disclosed herein.

DETAILED DESCRIPTION OF INVENTION

[0020] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein can be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.

[0021] The embodiments herein achieve a method and apparatus for determining the partition layout of coding unit using the internal characteristics of the coding unit, which is obtained by the gradient analysis and sum of absolute difference (SAD) analysis. The method disclosed herein provides separate approach for inter frame and intra frame in a video sequence. For determining the partition layout for an intra-frame, the gradient analysis is performed on the coding unit and in case of an inter frame, the gradient analysis and motion compensated SAD calculation is performed for determining the partition layout. Once the partition layout is determined, the determined partition layout is fine-tuned by performing a two mode search. The two mode search involves the mode search for the blocks of the layout which are obtained by combining the encompassed smaller blocks to obtain a bigger block up to one step more than the mode of the determined partition layout. Then Rate Distortion Optimization (RDO) is performed for determining the best partition layout.

[0022] In an embodiment, the apparatus can be an integrated circuit, a stand-alone chip or the like.

[0023] Further, the costs obtained in both the searches are compared to obtain the best partition layout.

[0024] Referring now to the drawings and more particularly to FIGS. 1 through 5 where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments.

[0025] FIG. 1 illustrates the block diagram of an apparatus for video processing that includes various modules, according to embodiments as disclosed herein. As depicted in the figure, the video processing apparatus 100 comprises a memory module 101, intra frame prediction module 102, inter frame prediction module 103, block partition module 104 and a motion search module 105. The memory module 101 is used for storing the video which is provided as an input to the apparatus 100.

[0026] The intra-frame prediction module 102 performs the intra-frame prediction in the block unit and the inter-frame prediction module 103 performs an inter-frame prediction in the block unit.

[0027] The block partition module 104 performs partitioning of each of the inputted original images into small regions. The motion search module 105 detects a motion in the block unit. The motion search module 105 detects whether a particular block has moved in the consecutive frames of a video sequence.

[0028] FIG. 2 illustrates a flow diagram explaining the various steps involved in determining the best partition layout of coding unit, according to the embodiments disclosed herein. Initially the method receives (201) a plurality of video frames for encoding. In an embodiment, the method obtains the plurality of video frames from the memory module 101.

[0029] Once the video frames are obtained from the memory module 201, the method determines the type of the video frames. In an embodiment, the method checks (202) whether the frame obtained is an intra-frame or an inter frame.

[0030] If the received frame is an intra-frame, then the method obtains (203) the gradient of the coding unit. For intra frame, the block prediction within the frame is possible. The spatial characteristics of the coding unit are used for determining the partition layout of the coding unit.

[0031] The gradient of the coding unit is obtained by Sobel filtering on the coding units. The Sobel filter is a derivative operator that provides gradient information in either of the directions based on the coefficients.

[0032] Once the gradient is obtained for the coding unit (say for example 64X64), the uniformity of the block is decided based on the standard deviation of the constituent blocks.

[0033] In an example, for deciding a particular area (say for example 16X16) in a coding unit as uniform, the Standard Deviation (SD) of the constituent 8X8 blocks are calculated and if the SD is less than a threshold, then the blocks are marked as 16X16. For obtaining the gradient, the same method is applied for all the block sizes starting from 4X4 to 64X64 iteratively.

[0034] In an embodiment, the threshold for determining the partition layout based on the obtained gradient may differ depending on different block sizes.

[0035] Further, the method determines (204) the partition layout when the gradient of the coding unit reaches a threshold.

[0036] The above described method for obtaining the partition layout cannot be applicable for an inter frame. Hence the method for obtaining the partition layout for an inter frame is as detailed herein.

[0037] Initially, the method obtains the inter frame from the memory module 101. For obtaining the inter mode partition layout, the method obtains (205) the gradient along with motion vector prediction and SAD estimation.

[0038] In general, the motion vectors of a coding unit are closely related to its surrounding units. Hence for obtaining the mode of partition layout for inter frame, the method calculates (206) the motion vector prediction of the surrounding coding units. In an example, the method for obtaining the predicted motion vectors is as described in FIG. 3.

[0039] In an embodiment, the predicted motion vectors thus generated are added to the collocated coding unit in the reference frame.

[0040] The prediction unit generated is subtracted from the current coding unit and the SAD is generated. Further, the standard deviations of the blocks are calculated using the SAD of the constituent blocks in a quad tree fashion. The uniformity of the block is decided based on the SD of the constituent blocks. The method determines (207) the mode of partition layout of the inter frame by comparing the SD against a pre-defined threshold.

[0041] In an embodiment, the threshold for inter mode blocks is calculated by extensive tests on different streams by taking into account, the quantization parameter used that is directly related to the quality of the reference frame that is constructed.

[0042] In an embodiment, the method may perform a check on the gradient of the coding unit using the same method as used for intra frames, when the coding units in the inter frame are coded with intra modes.

[0043] Once the block partition layout is determined, the method optimizes (208) the determined mode of partition layout by performing a two mode search. The two mode search offers the flexibility of controlling the complexity with respect to the performance (compression). The method for performing the two mode search is as described in FIG. 4.

[0044] The Two mode search involves performing Rate Distortion Optimization (RDO) on the depth (mode of the determined partition layout) given by the layout as well as one step above the determined depth (for example if the determined layout is 32X32, then the search is performed for one step ahead of the 32X32 layout which is 64X64). Further, the method performs the comparison of costs obtained for determined partition layout with the cost obtained after performing the two mode search.

[0045] In an embodiment, the cost represents the total number of bits used for compressing the block using the partition layout. Thus, the costs (number of bits consumed) are compared for both the layouts (for the determined layout as well as one step ahead to the determined layout) and best partition layout is chosen.

[0046] In an embodiment, the depth that gives the minimum cost is used for final encoding.

[0047] The method encodes (209) the coding unit according to the optimized mode of the partition layout. Finally the method provides (210) the encoded video as output. The various actions in flow diagram 200 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 2 may be omitted.

[0048] FIG. 3 illustrates an exemplary motion vector prediction method for calculating the inter mode SAD, according to the embodiments as disclosed herein. In general, the Intra-frame prediction is based on close correlation between gray levels of adjacent pixels in a single frame and the Inter-frame prediction is based on similarities between successive frames in a video sequence. If no abrupt change appears in a moving picture screen, most areas of the moving picture do not change between successive frames. In particular, motion vector prediction is a video coding technique used in inter-frame prediction. Motion vector prediction is used to process images by differentially encoding motion vectors calculated by motion prediction. In general, a motion vector of a certain block has a close relationship with motion vectors of partitions adjacent to the block. Accordingly, by predicting a current block using its adjacent partitions and encoding only a difference vector between the current block and the adjacent partitions, it is possible to reduce the amount of bits that are to be encoded.

[0049] As depicted in the figure, the collocated SAD for the block ‘r’ (as shown in nth frame) is calculated by obtaining the motion vector prediction from the surrounding blocks (shown as dotted lines in nth frame, that are surrounded by block ‘r’) and adding it to the coordinates of the collocated block in the previous frame (N-1) which is denoted as ‘s’.

[0050] FIG. 4 illustrates a method for performing two mode search for optimizing the determined partition layout, according to the embodiments as disclosed herein. Once the partition layout is determined for a coding unit, the two mode search is performed for optimizing the determined partition layout. The method of two mode search for fine tuning the determined partition layout is as detailed herein. As depicted in the figure, the 64X64 coding unit is divided into 4 (32X32) blocks and the three blocks are taken from the 64X64 partition unit and named as X, Y and Z as shown in figure. Further, the 2nd 32X32 block is divided into 4 (16X16) blocks and named as p, r and s respectively as shown in the figure. Similarly, the 1st 16X16 block is divided into 4 8X8 blocks and named as a, b, c and d respectively as shown in the figure.

[0051] Once the partition layout of the coding unit is determined for intra frame as in step 204 and for an inter frame as in step 207, the two mode search is performed on the block size according to the layout. The first block is marked as 32X32 (X as shown in the figure) and the search is performed for the best intra mode if it is an intra frame. Further, for an inter frame, among intra or inter block search is performed.

[0052] In an embodiment, the search is performed by doing one complete encoder-decoder cycle on the block and by obtaining the least cost. In an embodiment, the cost described here denotes the number of bits consumed when a particular block layout is used.

[0053] Further, the search is now performed on the second block that has a combination of 8x8 (a, b, c and d) and 16x16 blocks (p, r and s). The first sub block of the second block has a depth of 3* that corresponds to 8x8. So the brute force search is performed on this block for all prediction types, modes and the best mode is selected. The same process is performed on all 8x8 blocks of the 16x16 block.

[0054] Finally, these blocks are combined to form a 16x16 block and the cost is calculated. This cost is compared to the sum of the costs of the best modes of the 8x8 blocks. This comparison is done up to two levels, i.e. the best depth given by the analyze module and a depth plus one i.e. block size just greater than the one that is obtained using the partition mode detection described above. This significantly decreases the time consumption because the number of brute force searches is reduced. Now the search is performed on the 2nd sub block of the second block. As this block depth is 2 corresponding to 16x16(p in figure), the search is performed at this level and best is chosen. The same process takes places for 3rd (r in figure) and 4th (s in figure) blocks that are 16x16 blocks. Now all these 16x16 blocks are combined to form a 32x32 block and search is performed at that level. These costs are compared and best block size is chosen.

[0055] Finally search is performed at 64x64 level (as 3 blocks of the 64x64 Coding Unit are marked as 32x32 blocks) and mode with least cost is chosen. This is compared to the sum of the costs of best modes of the individual blocks. “Two pass” search significantly reduces the number of brute force searches performed, because initial information about the partition size is obtained by intra inter partition size search described above. For example the types of searches performed for the Coding Unit with layout as shown in the figure are,
32x32 for block x, y and z

• 64x64 search for the complete Coding Unit and compare the cost with the sum of the least costs of the constituent sub blocks.
4 8x8 searches for sub blocks a, b, c and d

• 16x16 search that includes the 4 8x8 blocks. The least cost of 16x16 block is compared with sum of least costs of the constituent 8x8 blocks.
3 16x16 searches for p, q and r

• 32x32 search that includes 3 16x16 sub- blocks p, q and r and 4 8x8 sub-blocks a, b, c and d. The least cost of 32x32 is compared with sum of least costs of 4 8x8 sub blocks and 3 16x16 sub blocks

[0056] A total of 13 brute force searches are performed when compared to 340 searches that need to be performed for a full search. The best possible scenario for this algorithm is when the partition search module gives the correct layout map .i.e. in which blocks with modes 32x32 are marked with either depth 1 (32x32) or 2(16x16) by the partition search module. As, in both these cases search is performed for 32x32 block. The worst case is when a 32x32 block is marked as 4x4 or 8x8 by the partition search module that results in less compression. The performance degradation is more in the case, when a 4x4 block is marked as 32x32 than a case where a 32x32 block is flagged as 8x8 or lower sizes.

[0057] From the above analysis, it is observed that a higher block size with uniform texture is most likely correctly marked in the partition search module that results in better compression.

[0058] FIG. 5 illustrates a computing environment implementing the method and apparatus for determining the partition layout of the coding unit, according to the embodiments as disclosed herein. As depicted the computing environment 501 comprises at least one processing unit 504 that is equipped with a control unit 502 and an Arithmetic Logic Unit (ALU) 503, a memory 505, a storage unit 506, plurality of networking devices 508 and a plurality Input output (I/O) devices 507. The processing unit 504 is responsible for processing the instructions of the algorithm. The processing unit 504 receives commands from the control unit in order to perform its processing. Further, any logical and arithmetic operations involved in the execution of the instructions are computed with the help of the ALU 503.

[001] The overall computing environment 501 can be composed of multiple homogeneous and/or heterogeneous cores, multiple CPUs of different kinds, special media and other accelerators. The processing unit 504 is responsible for processing the instructions of the algorithm. Further, the plurality of processing units 504 may be located on a single chip or over multiple chips.

[002] The algorithm comprising of instructions and codes required for the implementation are stored in either the memory unit 505 or the storage 506 or both. At the time of execution, the instructions may be fetched from the corresponding memory 505 and/or storage 506, and executed by the processing unit 504.

[003] In case of any hardware implementations various networking devices 508 or external I/O devices 507 may be connected to the computing environment to support the implementation through the networking unit and the I/O device unit.

[004] The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the elements. The elements shown in Figs. 1 and 5 include blocks which can be at least one of a hardware device, or a combination of hardware device and software module.

[005] The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore, while the embodiments herein have been described in terms of preferred embodiments, those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the embodiments as described herein.
CLAIMS:

STATEMENT OF CLAIMS

We claim:

1. A method for video processing, wherein said method comprises:

obtaining a gradient for at least one coding unit in at least one video frame;

determining a mode of partition layout for encoding said at least one video frame based on said obtained gradient, wherein said mode of partition layout is determined when a standard deviation calculated from said obtained gradient of said frame reaches a threshold;

optimizing said determined mode of partition layout by reducing number of partitions of said at least one video frame; and

encoding said at least one coding unit with said optimized mode of partition layout.

2. The method as in claim 1, wherein said video processing is performed on at least one of: an intra frame and an inter frame.

3. The method as in claim 2, wherein said method further comprises calculating sum of absolute difference (SAD) of said inter frame before determining said mode of partition layout for encoding said at least one video frame.

4. The method as in claim 3, wherein said method further comprises determining said mode of partition layout said at least one coding unit based on said standard deviations calculated from at least one of: said obtained gradient and said SAD.

5. The method as in claim 1, wherein said method further comprises optimizing said determined mode of partition layout by performing a mode search, wherein said mode search comprises searching for said at least one coding unit of said determined mode of partition layout by combining said at least one coding unit to obtain at least one bigger coding unit up to one step more than said determined mode of partition layout.

6. A system for video processing, wherein said system comprises at least one memory module, at least one intra frame prediction module, at least one inter frame prediction module, at least one block prediction module and a motion search module, wherein said system is configure to perform at least one step as claimed in claims 1 to 5.

7. An apparatus for video processing wherein said apparatus is configured to:

obtain a gradient for at least one coding unit in at least one video frame;

determine a mode of partition layout for encoding said at least one video frame based on said obtained gradient, wherein said partition layout is determined when a standard deviation calculated from said obtained gradient of said frame reaches a threshold;

optimize said determined mode of partition layout by reducing number of partitions of said at least one video frame; and

encode said at least one coding unit with said optimized mode of partition layout.

8. The apparatus as in claim 6, wherein said video processing is performed on at least one of: an intra frame and an inter frame.

9. The apparatus as in claim 7, wherein said apparatus is further configured to calculate sum of absolute difference (SAD) of said inter frame before determining said mode of partition layout for encoding said at least one video frame.

10. The apparatus as in claim 8, wherein said apparatus is further configured to determine said mode of partition layout of said at least one coding unit based on said standard deviation calculated from at least one of: said obtained gradient and said SAD.

11. The apparatus as in claim 6, wherein said apparatus is further configured to optimize said determined mode of partition layout by performing a mode search, wherein said mode search comprises searching for said at least one coding unit of said determined mode of partition layout by combining said at least one coding unit to obtain at least one bigger coding unit up to one step more than said determined mode of partition layout.