# US 12,216,733 B2 · Inverse transformation using pruning for video coding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,216,733 B2
- Document ID: US12216733B2
- Status: Granted
- Kind: B2
- Application number: 18/131,747
- Filed: 2023-04-06
- Published: 2023-08-03
- Granted: 2025-02-04
- Earliest claimed: 2011-05-13
- Assignees: Texas Instruments Incorporated
- Applicants: Texas Instruments Incorporated
- Inventors: Madhukar Budagavi; Vivienne Sze
- Web page: https://patentgrep.com/patent/US12216733B2

## CPC

- G06F 17/147: {Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform (G06F17/145 takes precedence)}
- H04N 19/122: Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
- H04N 19/134: characterised by the element, parameter or criterion affecting or controlling the adaptive coding
- H04N 19/14: Coding unit complexity, e.g. amount of activity or edge presence estimation (H04N19/146 takes precedence)
- H04N 19/176: the region being a block, e.g. a macroblock
- H04N 19/18: the unit being a set of transform coefficients
- H04N 19/42: characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation (H04N19/635 takes precedence)
- H04N 19/46: Embedding additional information in the video signal during the compression process (H04N19/517, H04N19/68, H04N19/70 take precedence)
- H04N 19/48: using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data (motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513)
- H04N 19/61: in combination with predictive coding
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method for decoding an encoded video bit stream in a video decoder is provided that includes determining a scan pattern type for a transform block to be decoded, decoding a column position X and a row position Y of a last non-zero coefficient in the transform block from the encoded video bit stream, selecting a column-row inverse transform order when the scan pattern type is a first type, selecting a row-column inverse transform order when the scan pattern type is a second type, and performing one dimensional (1D) inverse discrete cosine transformation (IDCT) computations according to the selected transform order to inversely transform the transform block to generate a residual block.

## Claims

### Claim 1

A method for decoding an encoded video bit stream in a video decoder, the method comprising:
setting a prune flag to indicate pruning when a value of a transform coefficient is zero;
setting the prune flag to indicate no pruning when the value of the transform coefficient is non-zero;
disabling latching of the transform coefficient for multiplication with an inverse discrete cosine transformation (IDCT) coefficient during a clock cycle and outputting a zero when the prune flag is set to indicate pruning; and
enabling latching of the transform coefficient for multiplication with the IDCT coefficient during a clock cycle and outputting a product of the transform coefficient and the IDCT coefficient when the pruning flag is set to indicate no pruning.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining a scan pattern type for a transform block;
decoding a position of a last non-zero coefficient in the transform block;
selecting a transform order based on the scan pattern type;
generating an interim results block based on performing one dimensional (1D) IDCT computations on a subset of the transform block according to the selected transform order; and
generating a residual block using the interim results block.

### Claim 3 (depends on 2)

The method of claim 2, wherein selecting the transform order comprises:
selecting a column-row inverse transform order when the scan pattern type is a first type; and
selecting a row-column inverse transform order when the scan pattern type is a second type.

### Claim 4 (depends on 3)

The method of claim 3, wherein the first type is a vertical scan pattern, and wherein performing the 1D IDCT computations further includes:
performing 1D IDCT computations on only a subset of columns of the transform block to generate the interim results block, wherein a number of columns in the subset is derived from a column position of the last non-zero coefficient; and
performing 1D IDCT computations on all rows of the interim results block to generate the residual block.

### Claim 5 (depends on 3)

The method of claim 3, wherein the second type is a horizontal scan pattern; and wherein performing the 1D IDCT computations further includes:
performing 1D IDCT computations on only a subset of rows of the transform block to generate the interim results block, wherein a number of rows in the subset is derived from a row position of the last non-zero coefficient; and
performing 1D IDCT computations on all columns of the interim results block to generate the residual block.

### Claim 6 (depends on 3)

The method of claim 3, wherein the first type is an up-right scan pattern, and wherein performing the 1D IDCT computations further includes:
performing 1D IDCT computations on only a subset of columns of the transform block to generate the interim results block, wherein a number of columns in the subset is derived from a column position and a row position of the last non-zero coefficient; and
performing 1D IDCT computations on all rows of the interim results block to generate the residual block.

### Claim 7 (depends on 3)

The method of claim 3, wherein the second type is a down-left scan pattern, and wherein performing the 1D IDCT computations further includes:
performing 1D IDCT computations on only a subset of rows of the transform block to generate the interim results block, wherein a number of rows in the subset is derived from a row position and a column position of the last non-zero coefficient; and
performing 1D IDCT computations on all columns of the interim results block to generate the residual block.

### Claim 8 (depends on 3)

The method of claim 3, wherein the first type is a zigzag scan pattern, and wherein performing the 1D IDCT computations further includes:
performing 1D IDCT computations on only a subset of columns of the transform block to generate the interim results block, wherein a number of columns in the subset is derived from a column position and a row position of the last non-zero coefficient; and
performing 1D IDCT computations on all rows of the interim results block to generate the residual block.

### Claim 9 (depends on 3)

The method of claim 3, wherein the second type is a zigzag scan pattern, and wherein performing the 1D IDCT computations further includes:
performing 1D IDCT computations on only a subset of rows of the transform block to generate the interim results block, wherein a number of rows in the subset is derived from a row position and a column position of the last non-zero coefficient; and
performing 1D IDCT computations on all columns of the interim results block to generate the residual block.

### Claim 10 (depends on 3)

The method of claim 3, wherein selecting the column-row inverse transform order comprises selecting the column-row inverse transform order when:
the scan pattern type is a zigzag scan pattern; and
a scan direction of a diagonal of the transform block in which the last non-zero coefficient is located is up-right.

### Claim 11 (depends on 3)

The method of claim 3, wherein selecting the row-column inverse transform order comprises selecting the row-column inverse transform order when:
the scan pattern type is a zigzag scan pattern; and
a scan direction of a diagonal of the transform block in which the last non-zero coefficient is located is down-left.

### Claim 12

A non-transitory computer-readable medium having executable instructions stored thereon, configured to be executable by processing circuitry for causing the processing circuitry to:
set a prune flag to indicate pruning when a value of a transform coefficient is zero;
set the prune flag to indicate no pruning when the value of the transform coefficient is non-zero;
disable latching of the transform coefficient for multiplication with an inverse discrete cosine transformation (IDCT) coefficient during a clock cycle and outputting a zero when the prune flag is set to indicate pruning; and
enable latching of the transform coefficient for multiplication with the IDCT coefficient during a clock cycle and outputting a product of the transform coefficient and the IDCT coefficient when the pruning flag is set to indicate no pruning.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein the instructions are executable by the processing circuitry for further causing the processing circuitry to:
determine a scan pattern type for a transform block;
decode a position of a last non-zero coefficient in the transform block;
select a transform order based on the scan pattern type;
generate an interim results block based on performing one dimensional (1D) IDCT computations on a subset of the transform block according to the selected transform order; and
generate a residual block using the interim results block.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the instructions to select the transform order comprise instructions to:
select a column-row inverse transform order when the scan pattern type is a first type; and
select a row-column inverse transform order when the scan pattern type is a second type.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the first type is an up-right scan pattern, and wherein the instructions to perform the 1D IDCT computations comprise instructions to:
perform 1D IDCT computations on only a subset of columns of the transform block to generate the interim results block, wherein a number of columns in the subset is derived from a column position and a row position of the last non-zero coefficient; and
perform 1D IDCT computations on all rows of the interim results block to generate the residual block.

### Claim 16 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the second type is a down-left scan pattern, and wherein the instructions to perform the 1D IDCT computations comprise instructions to:
perform 1D IDCT computations on only a subset of rows of the transform block to generate the interim results block, wherein a number of rows in the subset is derived from a row position and a column position of the last non-zero coefficient; and
perform 1D IDCT computations on all columns of the interim results block to generate the residual block.

### Claim 17

A method for decoding an encoded video bit stream in a video decoder, the method comprising:
decoding a pruned transform flag in the encoded video bit stream, wherein the pruned transform flag indicates that a subset region of a transform block contains all non-zero coefficients of the transform block, wherein the subset region consists of M rows and N columns of the transform block; and
inverse scanning only quantized transform coefficients of the subset region decoded from the encoded video bit stream to generate the transform block.

### Claim 18 (depends on 17)

The method of claim 17, wherein M=N=4.

### Claim 19 (depends on 17)

The method of claim 17, further comprising:
performing one dimensional (1D) inverse discrete cosine transformation (IDCT) computations on the transform block to generate a residual block, wherein one of a value of M or N is used to determine pruning of the 1D IDCT computations.

### Claim 20 (depends on 19)

The method of claim 19, wherein performing 1D IDCT computations comprises:
using a column-row inverse transform order when N>M, wherein 1D IDCT computations are performed on only N columns of the transform block to generate an interim results block; and
using a row-column inverse transform order when M>N, wherein 1D IDCT computations are performed on only M rows of the transform block to generate the interim results block.