Palette Mode Search
Encoder Algorithm » Intra Mode Search

## Functions

static void | av1_calc_indices (const int16_t *data, const int16_t *centroids, uint8_t *indices, int n, int k, int dim)
| Calculates the cluster to which each data point belong.
static void | av1_k_means (const int16_t *data, int16_t *centroids, uint8_t *indices, int n, int k, int dim, int max_itr)
| Performs k-means cluster on the data.
int | av1_index_color_cache (const uint16_t *color_cache, int n_cache, const uint16_t *colors, int n_colors, uint8_t *cache_color_found, int *out_cache_colors)
| Checks what colors are in the color cache.
int | av1_get_palette_delta_bits_v (const PALETTE_MODE_INFO *const pmi, int bit_depth, int *zero_count, int *min_bits)
| Gets the rate cost for each delta-encoding v palette.
int | av1_palette_color_cost_y (const PALETTE_MODE_INFO *const pmi, const uint16_t *color_cache, int n_cache, int bit_depth)
| Gets the rate cost for transmitting luma palette color values.
int | av1_palette_color_cost_uv (const PALETTE_MODE_INFO *const pmi, const uint16_t *color_cache, int n_cache, int bit_depth)
| Gets the rate cost for transmitting luma palette chroma values.
void | av1_rd_pick_palette_intra_sby (const struct AV1_COMP *cpi, struct macroblock *x, BLOCK_SIZE bsize, int dc_mode_cost, MB_MODE_INFO *best_mbmi, uint8_t *best_palette_color_map, int64_t *best_rd, int *rate, int *rate_tokenonly, int64_t *distortion, uint8_t *skippable, int *beat_best_rd, struct PICK_MODE_CONTEXT *ctx, uint8_t *tx_type_map)
| Search for the best palette in the luma plane.
void | av1_rd_pick_palette_intra_sbuv (const struct AV1_COMP *cpi, struct macroblock *x, int dc_mode_cost, uint8_t *best_palette_color_map, MB_MODE_INFO *const best_mbmi, int64_t *best_rd, int *rate, int *rate_tokenonly, int64_t *distortion, uint8_t *skippable)
| Search for the best palette in the chroma plane.
static int | remove_duplicates (int16_t *centroids, int num_centroids)
| Removes duplicated centroid indices.

static void

palette_rd_y (const AV1_COMP *const cpi, MACROBLOCK *x, MB_MODE_INFO *mbmi, BLOCK_SIZE bsize, int dc_mode_cost, const int16_t *data, int16_t *centroids, int n, uint16_t *color_cache, int n_cache, bool do_header_rd_based_gating, MB_MODE_INFO *best_mbmi, uint8_t *best_palette_color_map, int64_t *best_rd, int *rate, int *rate_tokenonly, int64_t *distortion, uint8_t *skippable, int *beat_best_rd, PICK_MODE_CONTEXT *ctx, uint8_t *tx_type_map, int *beat_best_palette_rd, bool *do_header_rd_based_breakout, int discount_color_cost)

| Calculate the luma palette cost from a given color palette.

## Detailed Description

This module describes palette mode search algorithm in AV1. More details will be added.

## Function Documentation

## av1_calc_indices()

void av1_calc_indices | ( | const int16_t * | data,
|  | const int16_t * | centroids,
|  | uint8_t * | indices,
|  | int | n,
|  | int | k,
|  | int | dim )

inline static

Calculates the cluster to which each data point belong.

Parameters

  [in] | data | The data points whose cluster indices are to be computed. The data layout is NUM_DATA_POINTS X DATA_DIM.
  [in] | centroids | Pointer to the centroids. The data layout is NUM_CENTROIDS X DATA_DIM.
  [in] | indices | Pointer to store the computed indices.
  [in] | n | Number of data points.
  [in] | k | Number of clusters.
  [in] | dim | Data dimension.

Remarks
  Returns nothing, but saves each data's cluster index in indices.

Referenced by palette_rd_y().

## av1_k_means()

void av1_k_means | ( | const int16_t * | data,
|  | int16_t * | centroids,
|  | uint8_t * | indices,
|  | int | n,
|  | int | k,
|  | int | dim,
|  | int | max_itr )

inline static

Performs k-means cluster on the data.

Parameters

  [in] | data | The data points to be clustered. The data layout is NUM_DATA_POINTS X DATA_DIM.
  [in] | centroids | Pointer to store the computed centroids. The data layout is NUM_CENTROIDS X DATA_DIM.
  [in] | indices | Pointer to store the computed indices. For each training data.
  [in] | n | Number of data points.
  [in] | k | Number of clusters.
  [in] | dim | Data dimension.
  [in] | max_itr | Maximum number of iterations to run.

Remarks
  Returns nothing, but saves each cluster's centroid in centroids and each data's cluster index in indices.

Attention
  The output centroids are rounded off to nearest integers.

References av1_k_means().

Referenced by av1_k_means().

## av1_index_color_cache()

int av1_index_color_cache | ( | const uint16_t * | color_cache,
|  | int | n_cache,
|  | const uint16_t * | colors,
|  | int | n_colors,
|  | uint8_t * | cache_color_found,
|  | int * | out_cache_colors )

Checks what colors are in the color cache.

Parameters

  [in] | color_cache | A cache of colors.
  [in] | n_cache | Number of colors in the cache.
  [in] | colors | New base colors.
  [in] | n_colors | Number of new colors.
  [in] | cache_color_found | Stores what cached colors are presented in colors.
  [in] | out_cache_colors | Stores what colors are not in the cache.

Returns
  Returns the number of colors that are not in cache. In addition, records whether each cache color is presented in colors in cache_color_found, and stores and stores the out of cache colors in out_cache_colors.

Referenced by av1_palette_color_cost_uv(), and av1_palette_color_cost_y().

## av1_get_palette_delta_bits_v()

int av1_get_palette_delta_bits_v | ( | const PALETTE_MODE_INFO *const | pmi,
|  | int | bit_depth,
|  | int * | zero_count,
|  | int * | min_bits )

Gets the rate cost for each delta-encoding v palette.

Parameters

  [in] | pmi | Struct that stores the palette mode info.
  [in] | bit_depth | Pixel bitdepth of the sequence.
  [in] | zero_count | Stores the number of zero deltas.
  [in] | min_bits | Minimum bits for the deltas. Sets to bit_depth - 4.

Returns
  Returns the number of bits used to transmit each v palette color delta and assigns zero_count with the number of deltas being 0.

Referenced by av1_palette_color_cost_uv().

## av1_palette_color_cost_y()

int av1_palette_color_cost_y | ( | const PALETTE_MODE_INFO *const | pmi,
|  | const uint16_t * | color_cache,
|  | int | n_cache,
|  | int | bit_depth )

Gets the rate cost for transmitting luma palette color values.

Parameters

  [in] | pmi | Struct that stores the palette mode info.
  [in] | color_cache | Color cache presented at the decoder.
  [in] | n_cache | Number of colors in the cache.
  [in] | bit_depth | Pixel bitdepth of the sequence.

Returns
  Returns the rate needed to transmit the palette. Note that this does not include the cost of transmitted the color map.

References av1_index_color_cache().

Referenced by intra_mode_info_cost_y().

## av1_palette_color_cost_uv()

int av1_palette_color_cost_uv | ( | const PALETTE_MODE_INFO *const | pmi,
|  | const uint16_t * | color_cache,
|  | int | n_cache,
|  | int | bit_depth )

Gets the rate cost for transmitting luma palette chroma values.

Parameters

  [in] | pmi | Struct that stores the palette mode info.
  [in] | color_cache | Color cache presented at the decoder.
  [in] | n_cache | Number of colors in the cache.
  [in] | bit_depth | Pixel bitdepth of the sequence.

Returns
  Returns the rate needed to transmit the palette. Note that this does not include the cost of transmitted the color map.

References av1_get_palette_delta_bits_v(), and av1_index_color_cache().

Referenced by intra_mode_info_cost_uv().

## av1_rd_pick_palette_intra_sby()

void av1_rd_pick_palette_intra_sby | ( | const struct AV1_COMP * | cpi,
|  | struct macroblock * | x,
|  | BLOCK_SIZE | bsize,
|  | int | dc_mode_cost,
|  | MB_MODE_INFO * | best_mbmi,
|  | uint8_t * | best_palette_color_map,
|  | int64_t * | best_rd,
|  | int * | rate,
|  | int * | rate_tokenonly,
|  | int64_t * | distortion,
|  | uint8_t * | skippable,
|  | int * | beat_best_rd,
|  | struct PICK_MODE_CONTEXT * | ctx,
|  | uint8_t * | tx_type_map )

Search for the best palette in the luma plane.

This function is used in both inter and intra frame coding.

Referenced by av1_rd_pick_intra_sby_mode(), av1_search_palette_mode(), and av1_search_palette_mode_luma().

## av1_rd_pick_palette_intra_sbuv()

void av1_rd_pick_palette_intra_sbuv | ( | const struct AV1_COMP * | cpi,
|  | struct macroblock * | x,
|  | int | dc_mode_cost,
|  | uint8_t * | best_palette_color_map,
|  | MB_MODE_INFO *const | best_mbmi,
|  | int64_t * | best_rd,
|  | int * | rate,
|  | int * | rate_tokenonly,
|  | int64_t * | distortion,
|  | uint8_t * | skippable )

Search for the best palette in the chroma plane.

This function is used in both inter and intra frame coding.

Referenced by av1_rd_pick_intra_sbuv_mode().

## remove_duplicates()

int remove_duplicates | ( | int16_t * | centroids,
|  | int | num_centroids )

static

Removes duplicated centroid indices.

Parameters

  [in] | centroids | A list of centroids index.
  [in] | num_centroids | Number of centroids.

Returns
  Returns the number of unique centroids and saves the unique centroids in beginning of the centroids array.

Attention
  The centroids should be rounded to integers before calling this method.

Referenced by palette_rd_y().

## palette_rd_y()

void palette_rd_y | ( | const AV1_COMP *const | cpi,
|  | MACROBLOCK * | x,
|  | MB_MODE_INFO * | mbmi,
|  | BLOCK_SIZE | bsize,
|  | int | dc_mode_cost,
|  | const int16_t * | data,
|  | int16_t * | centroids,
|  | int | n,
|  | uint16_t * | color_cache,
|  | int | n_cache,
|  | bool | do_header_rd_based_gating,
|  | MB_MODE_INFO * | best_mbmi,
|  | uint8_t * | best_palette_color_map,
|  | int64_t * | best_rd,
|  | int * | rate,
|  | int * | rate_tokenonly,
|  | int64_t * | distortion,
|  | uint8_t * | skippable,
|  | int * | beat_best_rd,
|  | PICK_MODE_CONTEXT * | ctx,
|  | uint8_t * | tx_type_map,
|  | int * | beat_best_palette_rd,
|  | bool * | do_header_rd_based_breakout,
|  | int | discount_color_cost )

inline static

Calculate the luma palette cost from a given color palette.

Given the base colors as specified in centroids[], calculate the RD cost of palette mode.

References av1_calc_indices(), av1_pick_uniform_tx_size_type_yrd(), MB_MODE_INFO::bsize, AV1_COMP::common, macroblock::e_mbd, intra_mode_info_cost_y(), SPEED_FEATURES::intra_sf, macroblockd::lossless, MB_MODE_INFO::palette_mode_info, macroblockd::plane, macroblock::rdmult, remove_duplicates(), MB_MODE_INFO::segment_id, AV1Common::seq_params, AV1_COMP::sf, MB_MODE_INFO::tx_size, macroblockd::tx_type_map, and SPEED_FEATURES::winner_mode_sf.