IP Library › Granted Patent US 11,558,619
Granted Patent B2
US 11,558,619 · App. 17/544,244 · Granted Jan 17, 2023

Adaptation of scan order for entropy coding

Inventor: Dake He (Sunnyvale, CA)
Assignee: GOOGLE LLC
H04N19/129H04N19/172H04N19/176H04N19/18H04N19/182H04N19/61
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,558,619
App. No.
17/544,244
Granted
Jan 17, 2023
Kind
B2
Abstract

Decoding a transform block includes decoding a first group of coefficients of the transform block using a first scan order. The first group includes of first coefficients of a first row along a first edge of the transform block and second coefficients of a first column that is along a second edge of the transform block. The first group is used to determine a second scan order for decoding a second group of coefficients of the transform block. The second group includes remaining coefficients of the transform block and does not include any coefficient of the first group. The second group is decoded using the second scan order.

Claims (38)

1. A method for decoding a transform block, comprising:

decoding a first group of coefficients of the transform block using a first scan order, wherein the first group consists of first coefficients of a first row along a first edge of the transform block and second coefficients of a first column that is along a second edge of the transform block;

determining, using the first group, a second scan order for decoding a second group of coefficients of the transform block, wherein the second group consists of remaining coefficients of the transform block, and wherein the second group does not include any coefficient of the first group; and

decoding the second group using the second scan order.

2. The method of claim 1 , wherein the first scan order is a vertical zig-zag scan order.

3. The method of claim 1 , wherein the first scan order is a horizontal zig-zag scan order.

4. The method of claim 1 , wherein the second scan order is adapted based on the coefficients of the first group.

5. The method of claim 4 , wherein the second scan order is adapted based on a non-zero map of the coefficients of the first group, the non-zero map indicates, for each coefficient of the first group, whether the coefficient is or is not zero.

6. The method of claim 1 , wherein the second scan order is one of a vertical scan order, a horizontal scan order, a second zig-zag scan order, or a diagonal scan order.

7. The method of claim 6 , wherein the second scan order is the horizontal scan order when a first count of non-zero coefficients in a second half of the first row is positive and a second count of non-zero coefficients in a second half of the first column is zero.

8. The method of claim 6 , wherein the second scan order is the vertical scan order when a first count of non-zero coefficients in a second half of the first row is zero and a second count of non-zero coefficients in a second half of the first column is positive.

9. The method of claim 6 , wherein the second scan order is the second zig-zag scan order when a first count of non-zero elements in a second half of the first row is positive and a second count of non-zero elements in the second half of the first column is positive.

10. The method of claim 6 , wherein the second scan order is the diagonal scan order when a first count of non-zero elements in a second half of the first row is positive and a second count of non-zero elements in a second half of the first column is positive.

11. An apparatus for coding a transform block, comprising:

a processor, the processor configured to execute instructions to:

code, as a first group of coefficients, coefficients of a first row and a first column of the transform block using a first scan order,

wherein the transform block comprises the first group of coefficients and remaining coefficients, and

wherein the remaining coefficients comprise a remaining first row of coefficients, a remaining first column of coefficients, and other coefficients; and

code at least a subset of the remaining coefficients of the transform block using a second scan order by instructions to:

code the remaining first row and the remaining first column using the second scan order; and

code the other coefficients using a third scan order.

12. The apparatus of claim 11 , wherein the first scan order is an alternating scan order.

13. The apparatus of claim 12 ,

wherein the first group comprises, a first coefficient of the first row, a second coefficient of the first column, a third coefficient of the first row, and a fourth coefficient of the first column, and

wherein to code, as the first group, the coefficients of the first row and the first column of the transform block using the first scan order comprises to:

code, consecutively, the first coefficient, the second coefficient, the third coefficient, and the fourth coefficient.

14. The apparatus of claim 11 , wherein to code, as the first group, the coefficients of the first row and the first column of the transform block using the first scan order comprises to:

decode, from a compressed bitstream, the coefficients of the first row and the first column of the transform block using the first scan order.

15. The apparatus of claim 11 , wherein to code, as the first group, the coefficients of the first row and the first column of the transform block using the first scan order comprises to:

encode, in a compressed bitstream, the coefficients of the first row and the first column of the transform block using the first scan order.

16. The apparatus of claim 11 , wherein the second scan order is one of a vertical scan order, a horizontal scan order, a second zig-zag scan order, or a diagonal scan order.

17. The apparatus of claim 16 , wherein the second scan order is selected based on a first number of non-zero coefficients in at least a part of the first row and a second number of non-zero coefficients in at least a part of the first column.

18. A non-transitory computer-readable storage medium, comprising executable instructions that, when executed by a processor, facilitate performance of operations comprising:

coding, as a first group, coefficients of a first row and a first column of a transform block using a first scan order, wherein the transform block comprises the coefficients of the first row, coefficients of the first column, and remaining coefficients, and wherein the remaining coefficients comprise a remaining first row, a remaining first column, and other coefficients;

coding the remaining first row and the remaining first column using a second scan order, wherein the second scan order is determined using at least a subset of the coefficients of the first row and at least a subset of the coefficients of the first column; and

coding the other coefficients using a third scan order.

19. The non-transitory computer-readable storage medium of claim 18 , wherein the first scan order is one of a zig-zag scan order or an alternating scan order.

20. The non-transitory computer-readable storage medium of claim 18 , wherein the second scan order is one of a vertical scan order, a horizontal scan order, a second zig-zag scan order, or a diagonal scan order.

Continuity (4)
Continuation 16930903 · Jul 16, 2020
Continuation 16435672 · Jun 10, 2019
Continuation 15608008 · May 30, 2017
Related Publication 20220094938A1 · Mar 24, 2022