Compression of occupancy or indicator grids

Patent metadata

Field	Value
Publication number	US-10681388-B2
Application number	US-201815883639-A
Country	US
Kind code	B2
Filing date	Jan 30, 2018
Priority date	Jan 30, 2018
Publication date	Jun 9, 2020
Grant date	Jun 9, 2020

Abstract

Encoding and decoding occupancy information is disclosed. A method includes determining row sums for the region, determining column sums for the region, encoding, in a compressed bitstream, at least one of the row sums and the column sums, and encoding, in the compressed bitstream and based on a coding order, at least one of the rows and the columns of the region. The coding order is based on the encoded at least one of the row sums and the column sums. The row sums include, for each row of the region, a respective count of a number of locations in the row having a specified value. The column sums include, for each column of the region, a respective count of a number of locations in the column having the specified value. A location having the specified value is indicative of the occupancy information at the location.

First claim

What is claimed is:

1. A method of encoding occupancy information in a region of an image, the region having rows and columns, the method comprising:
determining row sums for the region,
wherein the row sums comprise, for each row of the region, a respective count of a number of locations in the row having a specified value, a location having the specified value being indicative of the occupancy information at the location;

determining column sums for the region,
wherein the column sums comprise, for each column of the region, a respective count of a number of locations in the column having the specified value;

encoding, in a compressed bitstream, at least one of the row sums and the column sums; and
encoding, in the compressed bitstream and based on a coding order, at least one of the rows and the columns of the region,
wherein the coding order is based on the encoded at least one of the row sums and the column sums.

2. The method of claim 1 , wherein encoding at least one of the row sums and the column sums comprises:
determining, based on a cost of encoding the region, whether to encode the row sums, the column sums, or both the row sums and the column sums.

3. The method of claim 1 , wherein encoding at least one of the rows and the columns of the region comprises:
selecting a next row or column to encode, the next row or column to encode corresponding to a most extreme probability; and
encoding the next row or column.

4. The method of claim 3 , wherein encoding the next row or column comprises:
encoding the next row or column using progressive arithmetic coding.

5. The method of claim 3 , wherein encoding the next row or column comprises:
in a case of encoding a row, using the column sums to encode the row; and
in a case of encoding a column, using the row sums to encode the column.

6. The method of claim 3 , wherein selecting the next row or column to encode comprises:
in a case where a first row or column and a second row or column are equivalent, selecting to encode the one of the first row or column and the second row or column resulting in the remaining probability being more extreme.

7. The method of claim 6 , wherein selecting the next row or column to encode further comprises:
in a case where the first row or column and the second row or column result in a tied most extreme remaining probability, selecting to encode the one of the first row or column that leaves other extremes least changed.

8. The method of claim 1 , further comprising:
splitting the image into sub-tiles, the region being a sub-tile of the sub-tiles; and encoding, in the compressed bitstream, an indication of the sub-tiles.

9. The method of claim 8 , wherein splitting the image into sub-tiles comprises: determining whether to split a sub-tile into further sub-tiles based on a hypothetical encoding of the sub-tiles.

10. The method of claim 9 , wherein the hypothetical encoding is a progressive arithmetic coding.

11. An apparatus for decoding occupancy information in a region of an image, the region comprising rows and columns, the apparatus comprising:
a memory; and
a processor, the processor configured to execute instructions stored in the memory to:
determine a base probability, the base probability being a probability of a location having a value in the region, the location having the value being indicative of the occupancy information at the location;
receive, in a compressed bitstream, at least one of row sums and column sums,
wherein the row sums comprise, for each row of at least some of the rows of the region, a respective count of a number of locations having the value in the row, and
wherein the column sums comprise, for each column of at least some of the columns of the region, a respective count of a number of locations having the value in the column; and

decode, from the compressed bitstream and based on a decoding order, at least one of the rows and the columns of the region,
wherein the decoding order is based on the received at least one of the row sums and the column sums.

12. The apparatus of claim 11 , wherein to decode, from the compressed bitstream based on the decoding order, the at least one of the rows and the columns of the region comprises to:
select a next row or column to decode, the next row or column to decode corresponding to a most extreme probability; and
decode the next row or column.

13. The apparatus of claim 12 , wherein to decode the next row or column comprises to:
decode the next row or column using progressive arithmetic coding.

14. The apparatus of claim 12 , wherein to decode the next row or column comprises to:
in a case of decoding a row, use the column sums to decode the row; and
in a case of decoding a column, use the row sums to decode the column.

15. The apparatus of claim 12 , wherein to select the next row or column to decode comprises to:
in a case where a first row or column and a second row or column are equivalent, select to decode the one of the first row or column and the second row or column resulting in the remaining probability being more extreme.

16. The apparatus of claim 15 , wherein to select the next row or column to decode further comprises to:
in a case where the first row or column and the second row or column result in a tied most extreme remaining probability, select to decode the one of the first row or column that leaves other extremes least changed.

17. The apparatus of claim 11 , the instructions further comprise instructions to:
receive an indication of a segmentation of the image into sub-tiles, the region being a sub-tile of the sub-tiles.

18. An apparatus for encoding a region of an image, the region having rows and columns, comprising:
a memory; and
a processor, the processor configured to execute instructions stored in the memory to:
determine row sums for the region,
the row sums comprise, for each row of at least some rows of the region, a respective count of a number of locations having a specified value;

determine column sums for the region,
the column sums comprise, for each column of at least some columns of the region, a respective count of a number of locations having the specified value;

encode, in a compressed bitstream, at least one of the row sums and the column sums; and
encode, in the compressed bitstream and based on a coding order, at least some one of the rows and the columns of the region,
wherein the coding order is based on the encoded at least one of the row sums and the column sums.

19. The apparatus of claim 18 , wherein the instructions further includes instructions to:
encode, in the compressed bitstream, a count of locations of the region having the specified value.

20. The apparatus of claim 18 , wherein the instructions further include instructions to:
encode an indication of a segmentation of the image into sub-tiles, the region being a coextensive sub-tile of the sub-tiles.

Assignees

• Google Llc

Inventors

• Covell Michele
• Marwood David
• Baluja Shumeet
• Sukthankar Rahul

Classifications

• H04N19/13

  Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC] · CPC title

• H04N19/463

  by compressing encoding parameters before transmission · CPC title

• H04N19/91 Primary

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• H04N19/44

  Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder · CPC title

• H04N19/176

  the region being a block, e.g. a macroblock · CPC title