Adaptive segmentation

• US 9,094,681 B1
• Filed: 02/28/2012
• Issued: 07/28/2015
• Est. Priority Date: 02/28/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wilkins, Paul Gordon, Gu, Qunshan
• Primary Examiner(s): Kelley, Christopher S
• Assistant Examiner(s): Findley, Christopher
• Application Number:
  US13/407,073
• Time in Patent Office: 1,246 Days
• US Class Current: 1/1
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/167 Position within a video image, e.g. region of interest [ROI]
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers

Abstract

Disclosed herein are systems, methods, and apparatuses for selecting different coding parameters for different portions of a video frame or image to be transmitted or stored for later decoding. The coding parameters for a particular portion of a video frame or image are selected according to their distance from a selected point of interest, where the parameters can be selected to alter the tradeoff between transmission bandwidth and perceived image quality to preserve image quality in areas designated as high interest while saving transmission bandwidth for areas designated as having less interest. Also disclosed are associated systems, methods, and apparatuses for decoding such encoded video frames or images.

Claims

1. A computer-implemented method for encoding a video including a plurality of frames capturing a scene having one or more objects positioned therein, the method comprising:

receiving, at one or more computing devices, a first one of the plurality of frames;

identifying, in the first frame, a first location associated with a first object in the scene;

identifying, in the first frame, a plurality of regions extending out from the first location by a predetermined step size until a limit is reached, including;

identifying a first region including the first location by selecting a first plurality of blocks that are at least partly located within a first distance range relative to the first location, an outer perimeter of the first region based on the predetermined step size;

assigning a first value for a coding parameter to the first region;

identifying at least one additional region extending out from the first region wherein each additional region contains a second plurality of blocks each at least partly located within a distance range defined by outer perimeter of a previous region and the outer perimeter of the previous region incremented by the predetermined step size; and

assigning a value for the coding parameter to each additional region after the first region by incrementing the value assigned to the previous region by a predetermined gradient value;

wherein the limit comprises at least one of a maximum distance from the first location, a maximum allowed change to the value for the coding parameter from the first value, or a maximum number of regions;

encoding the first plurality of blocks using the first coding parameter value;

encoding the second plurality of blocks of each additional region using the value assigned to the region; and

storing, into a bitstream of encoded blocks, the first location, the predetermined gradient value, and the predetermined step size.

2. The method of claim 1, wherein the first object is associated with a high level of user interest relative to the other objects in the scene.

3. The method of claim 1 wherein the coding parameter is a quantization level.

4. The method of claim 1 wherein the coding parameter is at least one of a loop filter type, a loop filter strength or a motion prediction parameter.

5. The method of claim 1, further comprising:

receiving, at the one or more computing devices, a second one of the plurality of frames in which the first object in the scene has moved to a different position relative to position of the first object in the first frame;

identifying, in the second frame, a second location associated with the different position of the first object;

identifying, in the second frame, a plurality of regions extending out from the second location by the predetermined step size until the limit is reached, including;

identifying a third region including the second location by selecting a third plurality of blocks that are at least partly located within the first distance range relative to the second location, an outer perimeter of the third region based on the predetermined step size; and

identifying at least one additional region extending out from the third region, wherein each additional region contains a fourth plurality of blocks each at least partly located within the second distance range defined by the outer perimeter of a previous region and the outer perimeter of the previous region incremented by the predetermined step size;

encoding the third plurality of blocks using the first coding parameter value;

encoding the fourth plurality of blocks of each additional region using the value assigned to the region; and

storing, into the bitstream of encoded blocks, the second location.

6. The method of claim 1, further comprising:

identifying, in the first frame, a second location associated with a second object in the scene; and

identifying, in the first frame, a second region including the second location by selecting a third plurality of blocks each located at least partially within a third distance range relative to the second location, and wherein the second region overlaps at least a portion of an outermost region of the plurality of regions.

7. The method of claim 6 further comprising:

determining a second value for the coding parameter based on an average of (i) the value for the coding parameter assigned to the outermost region, and (ii) another value for the coding parameter that is assigned to the second region; and

using the second value to encode at least one block of the third plurality of blocks.

8. The method of claim 7, wherein the determining the second value further comprises:

determining a first weighting value based on the distance between the first location and the at least one block of the third plurality of blocks, and a second weighting value based on the distance between the second location and the at least one block of the third plurality of blocks; and

wherein the average is a weighted average that is determined using the first weighting value as applied to the value for the coding parameter assigned to the outermost region and the second weighing value as applied to the value that is assigned to the second region.

9. The method of claim 1, wherein each additional region is annular and defined by an inner circular periphery and an outer circular periphery, wherein the distance between the first location and the inner circular periphery, and the distance between the inner circular periphery and the outer circular periphery, are both equal to the predetermined step size.

10. The method of claim 1, wherein the first region and each additional region are oval-shaped about the outer perimeter.

11. The method of claim 1, wherein the first region and each additional region are rectilinear and the predetermined step size comprises a first value in an x-direction and a second value in a y-direction, the second value different from the first value.

12. A computer-implemented method for encoding a video stream including at least one frame, comprising:

receiving, at one or more computing devices, a frame from the video stream;

identifying, in the frame, a first location of an object of interest;

identifying, in the frame, a plurality of regions spaced relative to the first location at intervals defined by a fixed step distance;

identifying a first coding parameter and a fixed step size by which the first coding parameter varies between adjacent ones of the plurality of regions;

identifying, for at least one of the plurality of regions, a region-specific coding parameter based on the first coding parameter and the fixed step size;

encoding at least one block in the at least one region using the region-specific coding parameter; and

storing, into a bitstream, the first location, the fixed step distance and the fixed step size, wherein the plurality of regions comprises a number of regions within at least one of a maximum distance from the first location that is based on the fixed step distance, a maximum allowed change in the first coding parameter that is based on the fixed step size or a predetermined maximum number of regions.

13. The method of claim 12 where at least some of the plurality of regions have a shape that is one of circular, elliptical or rectilinear.

14. The method of claim 13, wherein identifying the region-specific coding parameter further comprises:

determining a multiplier based on the rank of the at least one region; and

identifying the region-specific coding parameter based on the first coding parameter and the fixed step size multiplied by the multiplier.

15. The method of claim 13, wherein the first coding parameter is at least one of a quantizer, loop filter type, loop filter strength or motion prediction parameters.

16. A computer-implemented method for decoding encoded video data including at least one encoded frame having a plurality of blocks, comprising:

receiving, at one or more computing devices, encoded video data;

identifying, in the encoded video data, a frame, a first location within the frame, a first base value for a coding parameter, a fixed first step distance defining a first plurality of regions in the frame, and a fixed first step size defining a change in the value of the coding parameter;

identifying, in the frame, a first encoded block in one of the first plurality of regions;

identifying a region-specific value of the coding parameter for the one of the first plurality of regions based on the first base value for the coding parameter, a number of steps by which the one of the first plurality of regions is spaced from the first location, and the fixed first step size; and

decoding the first encoded block using the region-specific value of the coding parameter for the one of the first plurality of regions.

17. The computer-implemented method of claim 16, further comprising:

identifying, in the encoded video data, a second location within the frame, a second base value for a coding parameter, a fixed second step distance defining a second plurality of regions in the frame, and a fixed second step size defining a change in the value of the coding parameter;

identifying, in the frame, a second encoded block in one of the second plurality of regions, the second encoded block also located in a second one of the first plurality of regions;

identifying a region-specific value of the coding parameter for the second one of the first plurality of regions based on the first base value for the coding parameter, a number of steps by which the second one of the first plurality of regions is spaced from the first location, and the fixed first step size;

identifying a region-specific value of the coding parameter for the one of the second plurality of regions based on the second base value for the coding parameter, a number of steps by which the one of the second plurality of regions is spaced from the second location, and the fixed second step size;

calculating a block-specific value of the coding parameter for the second encoded block by averaging the region-specific values for the second one of the first plurality of regions and the one of the second plurality of regions; and

decoding the second encoded block using the block-specific value of the coding parameter.

18. The computer-implemented method of claim 17, wherein averaging the region-specific value comprises generating a weighted average by weighting the region-specific value for the second one of the first plurality of regions by on a distance in the frame between the second encoded block and the first location and weighting the region-specific value for the one of the second plurality of regions by a distance in the frame between the second encoded block and the second location.

19. The computer-implemented method of claim 16, further comprising:

identifying, in the encoded video data, a second location within the at least one encoded frame, the fixed first step distance defining a second plurality of regions in the frame;

identifying, in the frame, a second encoded block in one of the second plurality of regions, the second encoded block also located in a second one of the first plurality of regions;

identifying a region-specific value of the coding parameter for the second one of the first plurality of regions based on the first base value for the coding parameter, a number of steps by which the second one of the first plurality of regions is spaced from the first location, and the fixed first step size;

identifying a region-specific value of the coding parameter for the one of the second plurality of regions based on the first base value for the coding parameter, a number of steps by which the one of the second plurality of regions is spaced from the second location, and the fixed first step size;

calculating a block-specific value of the coding parameter for the second encoded block by averaging the region-specific values for the second one of the first plurality of regions and the one of the second plurality of regions; and

decoding the second encoded block using the block-specific value of the coding parameter.

20. The computer-implemented method of claim 19, wherein averaging the region-specific value comprises generating a weighted average by weighting the region-specific value for the second one of the first plurality of regions by on a distance in the frame between the second encoded block and the first location and weighting the region-specific value for the one of the second plurality of regions by a distance in the frame between the second encoded block and the second location.