IP Library › Granted Patent US 9,445,093

Granted Patent B2

US 9,445,093 · App. 13/536,762 · Granted Sep 13, 2016

Multiple zone scanning order for video coding

Inventors: Yunfei Zheng (Cupertino, CA); Xianglin Wang (San Diego, CA); Marta Karczewicz (San Diego, CA)

Assignee: QUALCOMM Incorporated

H04N19/00775 H04N19/129 H04N19/17 H04N19/176 H04N19/60

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 9,445,093
App. No.: 13/536,762
Granted: Sep 13, 2016
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A method for encoding transform coefficients in a video encoding process includes dividing a block of transform coefficients into a plurality of zones, determining a scan order for each of the plurality of zones, and performing a scan on each of the transform coefficients in each of the plurality of zones according to their respective determined scan order. In another example, a method for decoding transform coefficients in a video encoding process includes receiving a one-dimensional array of transform coefficients, determining a scan order for each of a plurality of sections of the one-dimensional array, wherein each section of the one-dimensional array corresponds to one of a plurality of zones defining a block of transform coefficients, and performing a scan on each of the transform coefficients in each of the section of the one dimensional array of zones according to their respective determined scan order.

Claims (173)

1. A method for encoding transform coefficients in a video encoding process, the method comprising:

determining a scan order for each of a first zone of a block of transform coefficients, a second zone of the block of transform coefficients, and a third zone of the block of transform coefficients;

in case the determined scan order for the first zone is a horizontal scan order:

dividing the block of transform coefficients into the first zone having a first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

dividing the block of transform coefficients into the second zone having a second boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (W/2+4) or W, the first boundary line and the second boundary line forming a 30° angle relative to the top line of the block of transform coefficients, and

in case the determined scan order for the first zone is a vertical scan order:

dividing the block of transform coefficients into the first zone having a third boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of transform coefficients, and

dividing the block of transform coefficients into the second zone having a fourth boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (H/2+4) or H, the first boundary line and the second boundary line forming a 60° angle relative to the top line of the block of transform coefficients; and

performing a scan on each of the transform coefficients in each of the first zone, the second zone, and the third zone according to their respective determined scan order to produce a one-dimensional array of transform coefficients.

2. The method of claim 1 , wherein determining the scan order comprises determining the scan order for one zone of the first zone, the second zone, or the third zone that is different than the determined scan order for the other zones of the first zone, the second zone, or the third zone.

3. The method of claim 1 , wherein determining the scan order comprises determining the scan order that is the same for each of the first zone, the second zone, and the third zone.

4. The method of claim 1 , wherein performing the scan comprises performing a significance map scan in a context adaptive binary arithmetic coding (CABAC) process.

5. The method of claim 1 , wherein dividing the block of transform coefficients into the first zone, the second zone, and the third zone comprises dividing the block of transform coefficients into the first zone, the second zone, and the third zone based on at least one of a block size, a prediction mode, or motion information.

6. The method of claim 1 , wherein the scan order is one of a forward horizontal scan, a forward vertical scan, a forward diagonal scan, an inverse horizontal scan, an inverse vertical scan, or an inverse diagonal scan.

7. The method of claim 1 ,

wherein determining the scan order comprises determining the scan order with a video encoder,

wherein dividing the block of transform coefficients comprises dividing the block of transform coefficients with the video encoder, and

wherein performing the scan comprises performing the scan with the video encoder.

8. The method of claim 1 ,

wherein determining the scan order comprises determining the scan order with a means for determining the scan order,

wherein dividing the block of transform coefficients comprises dividing the block of transform coefficients with a means for dividing the block of transform coefficients, and

wherein performing the scan comprises performing the scan with a means for performing the scan.

9. The method of claim 1 ,

wherein determining the scan order comprises executing, by one or more processors of a device for encoding video data, instructions stored on a non-transitory computer-readable storage medium that cause the one or more processors to determine the scan order,

wherein dividing the block of transform coefficients comprises executing, by the one or more processors of the device for encoding video data, instructions stored on the non-transitory computer-readable storage medium that cause the one or more processors to divide the block of transform coefficients, and

wherein performing the scan comprises executing, by the one or more processors of the device for encoding video data, instructions stored on the non-transitory computer-readable storage medium that cause the one or more processors to perform the scan.

10. A method for decoding transform coefficients in a video decoding process, the method comprising:

receiving a one-dimensional array of transform coefficients;

determining a scan order for each of a first section, a second section, and a third section of the one-dimensional array, wherein each section of the one-dimensional array corresponds to one of a plurality of zones defining a block of transform coefficients;

in case the determined scan order for the first section is a horizontal scan order:

dividing the block of transform coefficients into a first zone having a first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

dividing the block of transform coefficients into a second zone having a second boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (W/2+4) or W, the first boundary line and the second boundary line forming a 30° angle relative to the top line of the block of transform coefficients, and

in case the determined scan order for the first section is a vertical scan order:

performing a scan on each of the transform coefficients in each section of the one dimensional array according to their respective determined scan order to produce the block of transform coefficients.

11. The method of claim 10 , wherein determining the scan order comprises determining the scan order for one section of the first section, the second section, or the third section that is different than the determined scan order for the other sections of the first section, the second section, or the third section.

12. The method of claim 10 , wherein determining the scan order comprises determining the scan order that is the same for each of the first section, the second section, and the third section.

13. The method of claim 10 , wherein performing the scan comprises performing a significance map scan in a context adaptive binary arithmetic coding (CABAC) process.

14. The method of claim 10 , wherein the plurality of zones of the block of transform coefficients are based on a block size, a prediction mode, or motion information.

15. The method of claim 10 , wherein the scan order is one of a forward horizontal scan, a forward vertical scan, a forward diagonal scan, an inverse horizontal scan, an inverse vertical scan, or an inverse diagonal scan.

16. The method of claim 10 ,

wherein receiving the one-dimensional array comprises receiving the one-dimensional array with a video decoder,

wherein determining the scan order comprises determining the scan order with the video decoder,

wherein dividing the block of transform coefficients comprises dividing the block of transform coefficients with the video decoder, and

wherein performing the scan comprises performing the scan with the video decoder.

17. The method of claim 10 ,

wherein receiving the one-dimensional array comprises receiving the one-dimensional array with a means for receiving the one-dimensional array,

wherein determining the scan order comprises determining the scan order with a means for determining the scan order,

wherein dividing the block of transform coefficients comprises dividing the block of transform coefficients with a means for dividing the block of transform coefficients, and

wherein performing the scan comprises performing the scan with a means for performing the scan.

18. The method of claim 10 ,

wherein receiving the one-dimensional array comprises executing, by one or more processors of a device for decoding video data, instructions stored on a non-transitory computer-readable storage medium that cause the one or more processors to receive the one-dimensional array,

wherein determining the scan order comprises executing, by the one or more processors of the device for decoding video data, instructions stored on the non-transitory computer-readable storage medium that cause the one or more processors to determine the scan order,

wherein dividing the block of transform coefficients comprises executing, by the one or more processors of the device for decoding video data, instructions stored on the non-transitory computer-readable storage medium that cause the one or more processors to divide the block of transform coefficients, and

wherein performing the scan comprises executing, by the one or more processors of the device for decoding video data, instructions stored on the non-transitory computer-readable storage medium that cause the one or more processors to perform the scan.

19. An apparatus configured to encode transform coefficients in a video encoding process, the apparatus comprising:

a memory configured to store a block of transform coefficients; and

a video encoder in communication with the memory, the video encoder configured to:

determine a scan order for each of a first zone of a block of transform coefficients, a second zone of the block of transform coefficients, and a third zone of the block of transform coefficients;

divide the block of transform coefficients into the first zone, the second zone, and the third zone,

wherein in case the determined scan order for the first zone is a horizontal scan order, the video encoder is configured to:

divide the block of transform coefficients into the first zone having a first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

divide the block of transform coefficients into the second zone having a second boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (W/2+4) or W, wherein the first boundary line and the second boundary line form a 30° angle relative to the top line of the block of transform coefficients, and

wherein in case the determined scan order for the first zone is a vertical scan order, the video encoder is configured to:

divide the block of transform coefficients into the first zone having a third boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of transform coefficients, and

divide the block of transform coefficients into the second zone having a fourth boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (H/2+4) or H, wherein the first boundary line and the second boundary line form a 60° angle relative to the top line of the block of transform coefficients; and

perform a scan on each of the transform coefficients in each of the first zone, the second zone, and the third zone according to their respective determined scan order to produce a one-dimensional array of transform coefficients.

20. The apparatus of claim 19 , wherein the video encoder is configured to determine the scan order for one zone of the first zone, the second zone, or the third zone that is different than the determined scan order for the other zones of the first zone, the second zone, or the third zone.

21. The apparatus of claim 19 , wherein the video encoder is configured to determine the scan order that is the same for each of the first zone, the second zone, and the third zone.

22. The apparatus of claim 19 , wherein the video encoder is configured to perform a significance map scan in a context adaptive binary arithmetic coding (CABAC) process.

23. The apparatus of claim 19 , wherein the video encoder is further configured to divide the block of transform coefficients into the first zone, the second zone, and the third zone based on a block size, a prediction mode, or motion information.

24. The apparatus of claim 19 , wherein the scan order is one of a forward horizontal scan, a forward vertical scan, a forward diagonal scan, an inverse horizontal scan, an inverse vertical scan, or an inverse diagonal scan.

25. The apparatus of claim 19 , wherein the video encoder is part of a mobile device and comprises one or more processors.

26. An apparatus configured to decode transform coefficients in a video decoding process, the apparatus comprising:

a memory configured to store a one-dimensional array of transform coefficients; and

a video decoder in communication with the memory, the video decoder configured to:

receive the one-dimensional array of transform coefficients;

determine a scan order for each of a first section, a second section, and a third section of the one-dimensional array, wherein each section of the one-dimensional array corresponds to one of a plurality of zones defining a block of transform coefficients;

divide the block of transform coefficients into a first zone, a second zone, and a third zone,

wherein in case the determined scan order for the first section is a horizontal scan order, the video decoder is configured to:

divide the block of transform coefficients comprises dividing the block of transform coefficients into the first zone having a first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

wherein in case the determined scan order for the first section is a vertical scan order, the video decoder is configured to:

divide the block of transform coefficients comprises dividing the block of transform coefficients into the first zone having a third boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of transform coefficients, and

perform a scan on each of the transform coefficients in each section of the one dimensional array according to their respective determined scan order to produce the block of transform coefficients.

27. The apparatus of claim 26 , wherein the video decoder is configured to determine the scan order for one section of the first section, the second section, or the third section that is different than the determined scan order for the other sections of the first section, the second section, or the third section.

28. The apparatus of claim 26 , wherein the video decoder is configured to determine the scan order that is the same for each of the first section, the second section, and the third section.

29. The apparatus of claim 26 , wherein the video decoder is configured to perform a significance map scan in a context adaptive binary arithmetic coding (CABAC) process.

30. The apparatus of claim 26 , wherein the plurality of zones of the block of transform coefficients are based on a block size, a prediction mode, or motion information.

31. The apparatus of claim 26 , wherein the scan order is one of a forward horizontal scan, a forward vertical scan, a forward diagonal scan, an inverse horizontal scan, an inverse vertical scan, or an inverse diagonal scan.

32. The apparatus of claim 26 , wherein the video decoder is part of a mobile device and comprises one or more processors.

33. An apparatus configured to encode transform coefficients in a video encoding process, the apparatus comprising:

means for determining a scan order for each of a first zone of a block of transform coefficients, a second zone of the block of transform coefficients, and a third zone of the block of transform coefficients;

means for dividing, in case the determined scan order for the first zone is a horizontal scan order, the block of transform coefficients into the first zone having a first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

means for dividing, in case the determined scan order for the first zone is the horizontal scan order, the block of transform coefficients into the second zone having a second boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (W/2+4) or W, the first boundary line and the second boundary line forming a 30° angle relative to the top line of the block of transform coefficients, and

means for dividing, in case the determined scan order for the first zone is a vertical scan order, the block of transform coefficients into the first zone having a third boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of transform coefficients, and

means for dividing, in case the determined scan order for the first zone is the vertical scan order, the block of transform coefficients into the second zone having a fourth boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (H/2+4) or H, the first boundary line and the second boundary line forming a 60° angle relative to the top line of the block of transform coefficients; and

means for performing a scan on each of the transform coefficients in each of the first zone, the second zone, and the third zone according to their respective determined scan order to produce a one-dimensional array of transform coefficients.

34. An apparatus configured to decode transform coefficients in a video decoding process, the apparatus comprising:

means for receiving a one-dimensional array of transform coefficients;

means for determining a scan order for each of a first section, a second section, and a third section of the one-dimensional array, wherein each section of the one-dimensional array corresponds to one of a plurality of zones defining a block of transform coefficients;

means for dividing, in case the determined scan order for the first section is a horizontal scan order, the block of transform coefficients into a first zone having a first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

means for dividing, in case the determined scan order for the first section is the horizontal scan order, the block of transform coefficients into a second zone having a second boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (W/2+4) or W, the first boundary line and the second boundary line forming a 30° angle relative to the top line of the block of transform coefficients, and

means for dividing, in case the determined scan order for the first section is a vertical scan order, the block of transform coefficients into the first zone having a third boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of transform coefficients, and

means for dividing, in case the determined scan order for the first section is the vertical scan order, the block of transform coefficients into the second zone having a fourth boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (H/2+4) or H, the first boundary line and the second boundary line forming a 60° angle relative to the top line of the block of transform coefficients; and

means for performing a scan on each of the transform coefficients in each section of the one dimensional array according to their respective determined scan order to produce the block of transform coefficients.

35. A non-transitory computer-readable storage medium comprising instructions that, when executed, cause one or more processors of a device for video encoding to:

determine a scan order for each of a first zone of a block of transform coefficients, a second zone of the block of transform coefficients, and a third zone of the block of transform coefficients;

divide the block of transform coefficients into the first zone, the second zone, and the third zone,

wherein in case the determined scan order for the first zone is a horizontal scan order, the instructions further cause the one or more processors to:

wherein in case the determined scan order for the first zone is a vertical scan order, the instructions further cause the one or more processors to:

36. A non-transitory computer-readable storage medium comprising instructions that, when executed, cause one or more processors of a device for video decoding to:

receive a one-dimensional array of transform coefficients;

divide the block of transform coefficients into a first zone, a second zone, and a third zone,

wherein in case the determined scan order for the first section is a horizontal scan order, the instructions further cause the one or more processors to:

wherein in case the determined scan order for the first section is a vertical scan order, the instructions further cause the one or more processors to:

perform a scan on each of the transform coefficients in each section of the one dimensional array according to their respective determined scan order to produce the block of transform coefficients.

37. A system for encoding and decoding video data, the system comprising:

a memory configured to store a block of transform coefficients; and

a video encoder in communication with the memory, the video encoder configured to:

determine a scan order for each of a first zone of a block of transform coefficients, a second zone of the block of transform coefficients, and a third zone of the block of transform coefficients;

divide the block of transform coefficients into the first zone, the second zone, and the third zone,

wherein in case the determined scan order for the first zone is a horizontal scan order, the video encoder is configured to:

wherein in case the determined scan order for the first zone is a vertical scan order, the video encoder is configured to:

a video decoder in communication with the memory, the video decoder configured to:

receive a one-dimensional array of transform coefficients;

determine a scan order for each of a first section, a second section, and a third section of the one-dimensional array, wherein each section of the one-dimensional array corresponds to one of the plurality of zones defining the block of transform coefficients;

divide the block of transform coefficients into the first zone, the second zone, and the third zone,

wherein in case the determined scan order for the first section is the horizontal scan order, the video decoder is configured to:

divide the block of transform coefficients comprises dividing the block of transform coefficients into the first zone having the first boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of transform coefficients, and

divide the block of transform coefficients into the second zone having the second boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (W/2+4) or W, wherein the first boundary line and the second boundary line form a 30° angle relative to the top line of the block of transform coefficients, and

wherein in case the determined scan order for the first section is the vertical scan order, the video decoder is configured to:

divide the block of transform coefficients comprises dividing the block of transform coefficients into the first zone having the third boundary line having an intersection to the top line of the block of transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of transform coefficients, and

divide the block of transform coefficients into the second zone having the fourth boundary line having an intersection to the top line of the block of transform coefficients defined by a minimum of (H/2+4) or H, wherein the first boundary line and the second boundary line form a 60° angle relative to the top line of the block of transform coefficients; and

perform a scan on each of the transform coefficients in each section of the one dimensional array according to their respective determined scan order to produce the block of transform coefficients.

38. A method, comprising:

encoding, comprising:

determining a scan order for each of a first zone of a block of transform coefficients, a second zone of the block of transform coefficients, and a third zone of the block of transform coefficients;

in case the determined scan order for the first zone is a horizontal scan order:

in case the determined scan order for the first zone is a vertical scan order:

decoding, comprising:

receiving the one-dimensional array of transform coefficients;

determining a scan order for each of a first section, a second section, and a third section of the received one-dimensional array, wherein each section of the received one-dimensional array corresponds to one of a plurality of zones defining a block of transform coefficients;

in case the determined scan order for the first section of the received one-dimensional array is a horizontal scan order:

dividing the block of received transform coefficients into a first zone having a first boundary line having an intersection to the top line of the block of received transform coefficients defined by a maximum of 6 or (W/4+2) where W is the width of the block of received transform coefficients, and

dividing the block of received transform coefficients into a second zone having a second boundary line having an intersection to the top line of the block of received transform coefficients defined by a minimum of (W/2+4) or W, the first boundary line and the second boundary line forming a 30° angle relative to the top line of the block of received transform coefficients, and

in case the determined scan order for the first section of the received one-dimensional array is a vertical scan order:

dividing the block of received transform coefficients into the first zone having a third boundary line having an intersection to the top line of the block of received transform coefficients defined by a maximum of 6 or (H/4+2) where H is the height of the block of received transform coefficients, and

dividing the block of received transform coefficients into the second zone having a fourth boundary line having an intersection to the top line of the block of received transform coefficients defined by a minimum of (H/2+4) or H, the first boundary line and the second boundary line forming a 60° angle relative to the top line of the block of received transform coefficients; and

performing a scan on each of the received transform coefficients in each section of the one dimensional array of received transform coefficients according to their respective

determined scan order to produce the block of transform coefficients.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 17, 2012

From: ZHENG, YUNFEI; WANG, XIANGLIN; KARCZEWICZ, MARTA

To: QUALCOMM INCORPORATED

Reel/Frame 028569/0635 →

Continuity (3)

Provisional Application 61502753 · Jun 29, 2011

Provisional Application 61554380 · Nov 1, 2011

Related Publication 20130083857A1 · Apr 4, 2013