Hierarchical histogram calculation with application to palette table derivation
Systems, apparatuses, and methods for calculating multi-pass histograms for palette table derivation include an encoder that 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.
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, wherein the first number of bits is less than a total number of bits used to define the pixel component;
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 less than the total number of bits used to define the pixel component;
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, wherein the first number of bits is less than a total number of bits used to define the 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 and less than the total number of bits used to define the pixel component;
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, wherein the first number of bits is less than a total number of bits used to define the pixel component;
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 less than the total number of bits used to define the pixel component; 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.