METHOD AND DEVICE FOR VIDEO TRANSCODING USING QUAD-TREE BASED MODE SELECTION

• US 20110170608A1
• Filed: 01/08/2010
• Published: 07/14/2011
• Est. Priority Date: 01/08/2010
• Status: Abandoned Application

• Current Assignee: Research In Motion Limited (Blackberry Limited)
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: Yu, Xiang, He, Dake, Shi, Xun
• Application Number:
  US12/684,247
• Publication Number:
  US 20110170608A1
• Time in Patent Office: Days
• US Class Current: 375/240.24
• CPC Class Codes: H04N 19/109 among a plurality of temporal predictive coding modes
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

An encoder for encoding a downsampled video in which macroblock partitioning is based upon downsampled partitioning of full-resolution macroblocks. The refinement of the downsampled partitioning involves storing the downsampled partitioning in a quad-tree data structure and recursively identifying and evaluating possible mergers of leaf nodes having a common parent node. Using rate-distortion analysis possible mergers are evaluated and advantageous mergers are performed, thereby creating larger partitions and new leaf nodes. The traversing of the quad-tree to identify possible leaf node mergers is stopped when no further possible mergers may be identified that would result in a rate-distortion advantage.

Claims

1. A method of encoding a downsampled video, wherein the downsampled video is a spatially downsampled version of a full-resolution video, the downsampled video including a frame having a macroblock that corresponds to at least two full-resolution macroblocks in a corresponding frame of the full-resolution video, each of the at least two full-resolution macroblocks having an associated full-resolution coding mode that defines partitioning of that full-resolution macroblock, the method comprising:

determining an initial partitioning of the macroblock based on downsampling of the at least two full-resolution macroblocks subject to a minimum partition size, wherein the initial partitioning divides the macroblock into a plurality of partitions;

storing the initial partitioning in a quad-tree data structure, wherein each of the plurality of partitions is a leaf node, each leaf node has a parent node, and the quad-tree data structure represents spatial relationships amongst said plurality of partitions;

recursively,

identifying candidate mergers, wherein each candidate merger comprises the combination of two or more leaf nodes to create a larger partition, and wherein the two or more leaf nodes in each combination have a common parent node, and determining whether the larger partition has a rate-distortion cost smaller than a cumulative rate-distortion cost of the two or more leaf nodes and, if so, merging the two or more leaf nodes to generate an updated partitioning with the larger partition as a new leaf node; and

encoding the downsampled video to generate an encoded downsampled video, including encoding the macroblock using the updated partitioning, after determining that no further candidate mergers are identifiable.

2. The method claimed in claim 1, wherein said identifying includes traversing the quad-tree data structure and, at each leaf node, identifying other leaf nodes sharing the common parent node and excluding from each candidate merger any non-leaf nodes and any leaf nodes not having the common parent node.

3. The method claimed in claim 1, wherein the common parent node for the two or more leaf nodes comprises a partition one level up in the quad-tree data structure.

4. The method claimed in claim 1, wherein each candidate merger identified includes the two or more leaf nodes having the common parent node subject to a set of legitimate partitioning constraints.

5. The method claimed in claim 4, wherein the set of legitimate partitioning constraints are prescribed by a coding scheme in an applicable coding standard.

6. The method claimed in claim 5, wherein the applicable coding standard comprises H.264/AVC.

7. The method claimed in claim 1, wherein said recursively identifying, determining and merging includes using a greedy algorithm to identify and assess the candidate mergers.

8. The method claimed in claim 1, wherein said determining that no further candidate mergers are identifiable includes traversing the quad-tree data structure, including each new leaf node, and determining that each candidate merger in the update partitioning does not result in a rate-distortion cost savings.

9. The method claimed in claim 1, wherein said identifying candidate mergers includes excluding parent nodes from candidate mergers unless leaf nodes within a given parent node are merged such that the given parent node itself becomes a leaf node.

10. The method claimed in claim 1, further including:

decoding a full-resolution encoded video to produce the full-resolution video, including decoding the at least two full-resolution macroblocks and their associated full-resolution coding modes defining their partitioning; and

spatially downsampling the full-resolution video in the pixel domain to produce the downsampled video.

21. A computer-readable medium having stored thereon computer-executable instructions which, when executed by a processor, configure the processor to execute the method claimed in claim 1.

11. An encoder for encoding a downsampled video, wherein the downsampled video is a spatially downsampled version of a full-resolution video, the downsampled video including a frame having a macroblock that corresponds to at least two full-resolution macroblocks in a corresponding frame of the full-resolution video, each of the at least two full-resolution macroblocks having an associated full-resolution coding mode that defines partitioning of that full-resolution macroblock, the encoder comprising:

a processor;

a memory;

a communications system for outputting an encoded downsampled video; and

an encoding application stored in memory and containing instructions for configuring the processor to encode the downsampled video by

determining an initial partitioning of the macroblock based on downsampling of the at least two full-resolution macroblocks subject to a minimum partition size, wherein the initial partitioning divides the macroblock into a plurality of partitions;

storing the initial partitioning in a quad-tree data structure in the memory wherein each of the plurality of partitions is a leaf node, each leaf node having a parent node, and the quad-tree data structure represents spatial relationships amongst said plurality of partitions;

recursively,

identifying candidate mergers, wherein each candidate merger comprises the combination of two or more leaf nodes to create a larger partition, and wherein the two or more leaf nodes in each combination have a common parent node, and determining whether the larger partition has a rate-distortion cost smaller than a cumulative rate-distortion cost of the two or more leaf nodes and, if so, merging the two or more leaf nodes to generate an updated partitioning with the larger partition as a new leaf node; and

encoding the downsampled video to generate an encoded downsampled video, including encoding the macroblock using the updated partitioning, after determining that no further candidate mergers are identifiable.

12. The encoder claimed in claim 11, wherein the encoding application configures the processor to identify candidate mergers by traversing the quad-tree data structure and, at each leaf node, identifying other leaf nodes sharing the common parent node and excluding from each candidate merger any non-leaf nodes and any leaf nodes not having the common parent node.

13. The encoder claimed in claim 11, wherein the common parent node for the two or more leaf nodes comprises a partition one level up in the quad-tree data structure.

14. The encoder claimed in claim 11, wherein each candidate merger identified includes the two or more leaf nodes having the common parent node subject to a set of legitimate partitioning constraints.

15. The encoder claimed in claim 14, wherein the set of legitimate partitioning constraints are prescribed by a coding scheme in an applicable coding standard.

16. The encoder claimed in claim 15, wherein the applicable coding standard comprises H.264/AVC.

17. The encoder claimed in claim 11, wherein the encoding application configures the processor to recursively identify, determine and merge using a greedy algorithm to identify and assess the candidate mergers.

18. The encoder claimed in claim 11, wherein the encoding application configures the processor to determine that no further candidate mergers are identifiable by traversing the quad-tree data structure, including each new leaf node, and determining that each candidate merger in the update partitioning does not result in a rate-distortion cost savings.

19. The encoder claimed in claim 11, wherein the encoding application configures the processor to identify candidate mergers by excluding parent nodes from candidate mergers unless leaf nodes within a given parent node are merged such that the given parent node itself becomes a leaf node.

20. A transcoder, comprising:

a decoder configured to decode a full-resolution encoded video to produce the full-resolution video, including decoding the at least two full-resolution macroblocks and their associated full-resolution coding modes defining their partitioning;

a spatial downsampler configured to spatially downsample the full-resolution video in the pixel domain to produce the downsampled video; and

the encoder claimed in claim 11.