IP Library › Granted Patent US 11,758,133
Granted Patent B2
US 11,758,133 · App. 16/834,611 · Granted Sep 12, 2023

Flexible block partitioning structures for image/video compression and processing

Inventors: Alexandros Tourapis (Milpitas, CA); David W. Singer (San Francisco, CA); Dominik Mehlem (Cupertino, CA); Krishnakanth Rapaka (San Jose, CA)
Assignee: APPLE INC
H04N19/119H04N19/139H04N19/159H04N19/176H04N19/543H04N19/573
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,758,133
App. No.
16/834,611
Granted
Sep 12, 2023
Kind
B2
Abstract

Techniques for coding and decoding video may include predicting picture regions defined by a time-varying tessellation and/or by a tessellation that varies spatially within a picture. These techniques improve decoded video quality, for example, by reducing block-based visual artifacts. Tessellation patterns may be irregular spatially to prevent alignment of some prediction region boundaries within a picture. Tessellation patterns may vary over time based on a spatial offset value, and the spatial offset value may be determined via a modulo function. Tessellation patterns may include overlapped shapes, for example when used in conjunction with overlapped block motion compensation.

Claims (78)

1. A method of coding video comprising:

determining a predetermined plurality of spatial partitioning schemes based on spatial offsets derived from temporal locations of corresponding input frames;

for each of a plurality of input frames of a video to be coded, selecting a spatial partitioning scheme from the predetermined plurality of spatial partitioning schemes, wherein partitions of the spatial partitioning schemes are spatially offset from partitions of others of the spatial partitioning schemes and the selecting is based on respective temporal locations of the input frames within the video,

for a first input frame:

partitioning the first input frame into partitioning units according to the spatial partitioning scheme selected for the first input frame;

coding the partitioning units of the first input frame according to a prediction algorithm;

for a second input frame temporally offset from the first input frame:

partitioning the second input frame into partitioning units according to the spatial partitioning scheme selected for the second input frame, and

coding the partitioning units of the second input frame according to a prediction algorithm; and

transmitting a coded video sequence including the first predictively-coded input frame, the second predictively-coded input frame, and indications of the spatial partitioning schemes selected for them including an indication of the corresponding spatial offsets.

2. The method of claim 1 , wherein

the spatial partitioning scheme selected for the first input frame is spatial offset from an initial spatial partitioning scheme based on a temporal location of the first input frame, and

the spatial partitioning scheme selected for the second input frame is spatial offset from the initial spatial partitioning scheme based on a temporal location of the second input frame.

3. The method of claim 1 , wherein the spatial offsets are predetermined based on a selected offset function of time.

4. The method of claim 1 , wherein the indication of the spatial offsets includes an indication of a selected offset function of time.

5. The method of claim 1 , wherein the method further comprises:

prior to coding the first or second input frames, determining the predetermined plurality of spatial partitioning schemes by deriving the spatial offsets from the function 2 *modulo(t,N), where t is a respective temporal locations of an input frame, and N is a predetermined constant.

6. The method of claim 1 , wherein the spatial offsets include a horizontal offset magnitude specified by a first selected function based on a first constant and a vertical offset magnitude specified by a second function based on a second constant.

7. The method of claim 1 , wherein the plurality of spatial partitioning schemes includes irregular partitioning having partitions of varying shapes within a partitioning scheme for an input frame.

8. A non-transitory computer readable medium containing instructions for coding video that, when executed by a processor, cause:

determining a predetermined plurality of spatial partitioning schemes based on spatial offsets derived from temporal locations of corresponding input frames;

for each of a plurality of input frames of a video to be coded, selecting a spatial partitioning scheme from the predetermined plurality of spatial partitioning schemes, wherein partitions of the spatial partitioning schemes are spatially offset from partitions of others of the spatial partitioning schemes and the selecting is based on respective temporal locations of the input frames within the video,

for a first input frame:

partitioning the first input frame into partitioning units according to the spatial partitioning scheme selected for the first input frame;

coding the partitioning units of the first input frame according to a prediction algorithm;

for a second input frame temporally offset from the first input frame:

partitioning the second input frame into partitioning units according to the spatial partitioning scheme selected for the second input frame, and

coding the partitioning units of the second input frame according to a prediction algorithm; and

transmitting a coded video sequence including the first predictively-coded input frame, the second predictively-coded input frame, and indications of the spatial partitioning schemes selected for them including an indication of the corresponding spatial offsets.

9. A video coder, comprising:

a decoded picture buffer (DPB),

a predictor for predicting from reference pictures in the DPB, and

a controller for executing instructions that cause:

determining a predetermined plurality of spatial partitioning schemes based on spatial offsets derived from temporal locations of corresponding input frames;

for each of a plurality of input frames of a video to be coded, selecting a spatial partitioning scheme from the predetermined plurality of spatial partitioning schemes, wherein partitions of the spatial partitioning schemes are spatially offset from partitions of others of the spatial partitioning schemes and the selecting is based on respective temporal locations of the input frames within the video,

for a first input frame:

partitioning the first input frame into partitioning units according to the spatial partitioning scheme selected for the first input frame;

coding the partitioning units of the first input frame according to a prediction algorithm including predicting the partitioning units of the first input frame by the predictor from reference picture(s) in the DPB;

for a second input frame temporally offset from the first input frame:

partitioning the second input frame into partitioning units according to the spatial partitioning scheme selected for the second input frame, and

coding the partitioning units of the second input frame according to a prediction algorithm including predicting the partitioning units of the second input frame by the predictor from reference picture(s) in the DPB; and

transmitting a coded video sequence including the first predictively-coded input frame, the second predictively-coded input frame, and indications of the spatial partitioning schemes selected for them including an indication of the corresponding spatial offsets.

10. A video decoding method, comprising:

extracting, from an encoded video sequence, an indication of spatial partitioning schemes for corresponding plurality of encoded frames, wherein partitions of the spatial partitioning schemes are spatially offset from partitions of others of the spatial partitioning schemes, and the indication of the spatial partitioning schemes includes an indication of spatial offsets derived from temporal locations of corresponding encoded frames,

for a first encoded frame:

partitioning the first encoded frame into partitioning units according to the spatial partitioning scheme indicated for the first encoded frame;

decoding the partitioning units of the first encoded frame according to a prediction algorithm; and

for a second encoded frame temporally offset from the first encoded frame:

partitioning the second encoded frame into partitioning units according to the spatial partitioning scheme indicated for the second encoded frame, and

decoding the partitioning units of the second encoded frame according to the prediction algorithm.

11. The method of claim 10 , wherein

the spatial partitioning scheme indicated for the first encoded frame is spatial offset from an initial spatial partitioning scheme based on a temporal location of the first encoded frame, and

the spatial partitioning scheme indicated for the second encoded frame is spatial offset from the initial spatial partitioning scheme based on a temporal location of the second encoded frame.

12. The method of claim 10 , wherein the spatial offsets are predetermined based on a selected offset function of time.

13. The method of claim 10 , wherein the indication of the spatial offsets includes an indication of a selected offset function of time.

14. The method of claim 10 , wherein the method further comprises:

prior to decoding the first or second encoded frames, determining the spatial partitioning schemes by deriving the spatial offsets from the function 2 *modulo(t,N), where t is a respective temporal locations of an encoded frame, and N is a predetermined constant.

15. The method of claim 10 , wherein the spatial offsets include a horizontal offset magnitude specified by a first selected function based on a first constant and a vertical offset magnitude specified by a second function based on a second constant.

16. The method of claim 10 , wherein the plurality of spatial partitioning schemes includes irregular partitioning having partitions of varying shapes within a partitioning scheme for an encoded frame.

17. A non-transitory computer readable medium containing instructions for decoding video that, when executed by a processor, cause:

extracting, from an encoded video sequence, an indication of spatial partitioning schemes for corresponding plurality of encoded frames, wherein partitions of the spatial partitioning schemes are spatially offset from partitions of others of the spatial partitioning schemes, and the indication of the spatial partitioning schemes includes an indication of spatial offsets derived from temporal locations of corresponding encoded frames,

for a first encoded frame:

partitioning the first encoded frame into partitioning units according to the spatial partitioning scheme indicated for the first encoded frame;

decoding the partitioning units of the first encoded frame according to a prediction algorithm; and

for a second encoded frame temporally offset from the first encoded frame:

partitioning the second encoded frame into partitioning units according to the spatial partitioning scheme indicated for the second encoded frame, and

decoding the partitioning units of the second encoded frame according to the prediction algorithm.

18. A video decoder, comprising:

a decoded picture buffer (DPB),

a predictor for predicting from reference pictures in the DPB, and

a controller for executing instructions that cause:

extracting, from an encoded video sequence, an indication of spatial partitioning schemes for corresponding plurality of encoded frames, wherein partitions of the spatial partitioning schemes are spatially offset from partitions of others of the spatial partitioning schemes, and the indication of the spatial partitioning schemes includes an indication of spatial offsets derived from temporal locations of corresponding encoded frames,

for a first encoded frame:

partitioning the first encoded frame into partitioning units according to the spatial partitioning scheme indicated for the first encoded frame;

decoding the partitioning units of the first encoded frame according to a prediction algorithm; and

for a second encoded frame temporally offset from the first encoded frame:

partitioning the second encoded frame into partitioning units according to the spatial partitioning scheme indicated for the second encoded frame, and

decoding the partitioning units of the second encoded frame according to the prediction algorithm.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 9, 2020
From: TOURAPIS, ALEXANDROS; SINGER, DAVID W.; MEHLEM, DOMINIK; RAPAKA, KRISHNAKANTH
To: APPLE INC.
Reel/Frame 052356/0818 →
Continuity (2)
Provisional Application 62929045 · Oct 31, 2019
Related Publication 20210136370A1 · May 6, 2021