Hierarchical histogram calculation with application to palette table derivation

Patent metadata

Field	Value
Publication number	US-2021099699-A1
Application number	US-201916588772-A
Country	US
Kind code	A1
Filing date	Sep 30, 2019
Priority date	Sep 30, 2019
Publication date	Apr 1, 2021
Grant date	—

Abstract

Systems, apparatuses, and methods for calculating multi-pass histograms for palette table derivation are disclosed. An encoder calculates a first histogram for a first portion of most significant bits (MSBs) of pixel component values of a block of an image or video frame. Then, the encoder selects a given number of the highest pixel count bins from the first histogram. The encoder then increases the granularity of these selected highest pixel count bins by evaluating one or more additional bits from the pixel component values. A second histogram is calculated for the concatenation of the original first portion MSBs from the highest pixel count bins and the one or more additional bits, and the highest pixel count bins are selected from the second histogram. A palette table is derived based on these highest pixel count bins selected from the second histogram, and the block is encoded using the palette table.

First claim

What is claimed is:

1 . A system comprising:
a memory; and an encoder coupled to the memory, wherein the encoder is configured to:
select a first set of bins which have a highest pixel count among a first plurality of bins of a first histogram, wherein the first histogram is calculated based on a first number of bits of a given pixel component of pixels of a block;
select a second set of bins which have a highest pixel count among a second plurality of bins of a second histogram, wherein the second histogram is calculated based on a second number of bits of the given pixel component, and wherein the second number is greater than the first number;
derive a palette table from pixel component values that are assigned to the second set of bins; and
encode the given pixel component of the pixels of the block based on the palette table.

2 . The system as recited in claim 1 , wherein each bin of the first plurality of bins represents a range of potential pixel values.

3 . The system as recited in claim 1 , wherein the encoder is further configured to:
calculate a third histogram for pixels from the second set of bins based on a third number of bits of the given pixel component, wherein the third number is greater than the second portion, and wherein the third histogram includes a third plurality of bins; select a third set of bins which have a highest pixel count among the third plurality of bins; and
derive a palette table for encoding the given pixel component of the pixels of the block from pixel component values that are assigned to the third set of bins.

4 . The system as recited in claim 1 , wherein the first number of bits correspond to a first portion of the given pixel component, wherein the second number of bits correspond to a second portion of the given pixel component, and wherein the second portion contains the first portion.

5 . The system as recited in claim 1 , wherein there are fewer bins in the first set of bins than in the first plurality of bins.

6 . The system as recited in claim 1 , wherein there are fewer bins in the second set of bins than in the second plurality of bins.

7 . The system as recited in claim 1 , wherein the given pixel component is a luminance or chrominance pixel component, and wherein the block is a portion of an image or video frame.

8 . A method comprising:
selecting, by an encoder, a first set of bins which have a highest pixel count among a first plurality of bins of a first histogram, wherein the first histogram is calculated for a given pixel component of pixels of a block based on a first number of bits of the given pixel component; selecting a second set of bins which have a highest pixel count among a second plurality of bins of a second histogram, wherein the second histogram is calculated based on a second number of bits of the given pixel component, and wherein the second number is greater than the first number; deriving a palette table from pixel component values that are assigned to the second set of bins; and encoding the given pixel component of the pixels of the block based on the palette table.

9 . The method as recited in claim 8 , wherein each bin of the first plurality of bins represents a range of potential pixel values.

10 . The method as recited in claim 8 , further comprising:
grouping pixels from the second set of bins into a third plurality of bins based on a third portion of bits of the given pixel component, wherein the third portion is greater than the second portion; selecting a third set of bins which have a highest number of pixels among the third plurality of bins; and deriving a palette table for encoding the given pixel component of the pixels of the block from pixel component values that are assigned to the third set of bins.

11 . The method as recited in claim 8 , wherein the first number of bits correspond to a first portion of the given pixel component, wherein the second number of bits correspond to a second portion of the given pixel component, and wherein the second portion contains the first portion.

12 . The method as recited in claim 8 , wherein there are fewer bins in the first set of bins than in the first plurality of bins.

13 . The method as recited in claim 8 , wherein there are fewer bins in the second set of bins than in the second plurality of bins.

14 . The method as recited in claim 8 , wherein the given pixel component is a luminance or chrominance pixel component, and wherein the block is a portion of an image or video frame.

15 . An apparatus comprising:
a memory; and
control logic coupled to the memory, wherein the control logic is configured to:
select a first set of bins which have a highest pixel count among a first plurality of bins of a first histogram, wherein the first histogram is calculated based on a first number of bits of a given pixel component of pixels of a block;
select a second set of bins which have a highest pixel count among a second plurality of bins of a second histogram, wherein the second histogram is calculated based on a second number of bits of the given pixel component, and wherein the second number is greater than the first number; and
derive a palette table for encoding the given pixel component of the pixels of the block from pixel component values that are assigned to the second set of bins.

16 . The apparatus as recited in claim 15 , wherein each bin of the first plurality of bins represents a range of pixel values.

17 . The apparatus as recited in claim 15 , wherein the control logic is further configured to:
calculate a third histogram for pixels from the second set of bins based on a third number of bits of the given pixel component, wherein the third number is greater than the second number, and wherein the third histogram includes a third plurality of bins; select a third set of bins which have a highest pixel count among the third plurality of bins; and derive a palette table for encoding the given pixel component of the pixels of the block from pixel component values that are assigned to the third set of bins.

18 . The apparatus as recited in claim 15 , wherein the first number of bits correspond to a first portion of the given pixel component, wherein the second number of bits correspond to a second portion of the given pixel component, and wherein the second portion contains the first portion.

19 . The apparatus as recited in claim 15 , wherein there are fewer bins in the first set of bins than in the first plurality of bins.

20 . The apparatus as recited in claim 15 , wherein there are fewer bins in the second set of bins than in the second plurality of bins.

Assignees

• Ati Technologies Ulc

Inventors

• Pan Feng
• Gao Wei
• Liu Yang
• Sau Crystal Yeong-Pian
• Liu Haibo
• Harold Edward A
• Luo Ying
• Amer Ihab
• Sines Gabor

Classifications

• H04N19/15

  by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer · CPC title

• H04N19/186 Primary

  the unit being a colour or a chrominance component · CPC title

• H04N19/105 Primary

  Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction · CPC title

• H04N19/115 Primary

  Selection of the code volume for a coding unit prior to coding · CPC title

• H04N19/136

  Incoming video signal characteristics or properties · CPC title