Transform Coefficient Coding and Optimization
Encoder Algorithm

## Functions

void | av1_alloc_txb_buf (AV1_COMP *cpi)
| Allocate the memory resources for all the macro blocks in the current coding frame.
void | av1_free_txb_buf (AV1_COMP *cpi)
| Free the memory resources for all the macro blocks in the current coding frame.
void | av1_write_coeffs_txb (const AV1_COMMON *const cm, MACROBLOCK *const x, aom_writer *w, int blk_row, int blk_col, int plane, int block, TX_SIZE tx_size)
| Write quantized coefficients in a transform block into bitstream using entropy coding.
void | av1_write_intra_coeffs_mb (const AV1_COMMON *const cm, MACROBLOCK *x, aom_writer *w, BLOCK_SIZE bsize)
| Write quantized coefficients of all transform blocks in an intra macroblock into the bitstream using entropy coding.
uint8_t | av1_get_txb_entropy_context (const tran_low_t *qcoeff, const SCAN_ORDER *scan_order, int eob)
| Pack the context info of the current transform block into an uint8_t.
void | av1_update_intra_mb_txb_context (const AV1_COMP *cpi, ThreadData *td, RUN_TYPE dry_run, BLOCK_SIZE bsize, uint8_t allow_update_cdf)
| Update the probability model (cdf) and the entropy context related to coefficient coding for all transform blocks in the intra macroblock.
void | av1_update_and_record_txb_context (int plane, int block, int blk_row, int blk_col, BLOCK_SIZE plane_bsize, TX_SIZE tx_size, void *arg)
| Update the probability model (cdf) and the entropy context related to coefficient coding for a transform block.
void | av1_record_txb_context (int plane, int block, int blk_row, int blk_col, BLOCK_SIZE plane_bsize, TX_SIZE tx_size, void *arg)
| Update the entropy context related to coefficient coding for a transform block.
CB_COEFF_BUFFER * | av1_get_cb_coeff_buffer (const struct AV1_COMP *cpi, int mi_row, int mi_col)
| Get the corresponding CB_COEFF_BUFFER of the current macro block.
static int | av1_cost_skip_txb (const CoeffCosts *coeff_costs, const TXB_CTX *const txb_ctx, int plane, TX_SIZE tx_size)
| Returns the entropy cost associated with skipping the current transform block.
int | av1_optimize_txb (const struct AV1_COMP *cpi, MACROBLOCK *x, int plane, int block, TX_SIZE tx_size, TX_TYPE tx_type, const TXB_CTX *const txb_ctx, int *rate_cost, int sharpness)
| Adjust the magnitude of quantized coefficients to achieve better rate-distortion (RD) trade-off.
int | av1_cost_coeffs_txb (const MACROBLOCK *x, const int plane, const int block, const TX_SIZE tx_size, const TX_TYPE tx_type, const TXB_CTX *const txb_ctx, int reduced_tx_set_used)
| Compute the entropy cost of coding coefficients in a transform block.
int | av1_cost_coeffs_txb_laplacian (const MACROBLOCK *x, const int plane, const int block, const TX_SIZE tx_size, const TX_TYPE tx_type, const TXB_CTX *const txb_ctx, const int reduced_tx_set_used, const int adjust_eob)
| Estimate the entropy cost of coding a transform block using Laplacian distribution.

## Detailed Description

This module describes the algorithms of transform coefficient coding and optimization in AV1. More details will be added.

## Function Documentation

## av1_alloc_txb_buf()

void av1_alloc_txb_buf | ( | AV1_COMP * | cpi | ) |

Allocate the memory resources for all the macro blocks in the current coding frame.

Each macro block will need a CB_COEFF_BUFFER to store information for rate-distortion optimization and entropy coding of transform coefficients.

Parameters

  [in] | cpi | Top-level encoder structure

## av1_free_txb_buf()

void av1_free_txb_buf | ( | AV1_COMP * | cpi | ) |

Free the memory resources for all the macro blocks in the current coding frame.

See av1_alloc_txb_buf and CB_COEFF_BUFFER for more details.

Parameters

  [in] | cpi | Top-level encoder structure

## av1_write_coeffs_txb()

void av1_write_coeffs_txb | ( | const AV1_COMMON *const | cm,
|  | MACROBLOCK *const | x,
|  | aom_writer * | w,
|  | int | blk_row,
|  | int | blk_col,
|  | int | plane,
|  | int | block,
|  | TX_SIZE | tx_size )

Write quantized coefficients in a transform block into bitstream using entropy coding.

This function will write the quantized coefficients in a transform block into the bitstream using entropy coding.

The coding steps are as follows.

1) Code the end of block position "eob", which is the scan index of the last non-zero coefficient plus one.

2) Code the lower magnitude level (<= COEFF_BASE_RANGE + NUM_BASE_LEVELS) for each coefficient in reversed scan order.

3) Code the sign and higher magnitude level (> COEFF_BASE_RANGE + NUM_BASE_LEVELS) in forward scan order.

Parameters

  [in] | cm | Top-level structure shared by encoder and decoder
  [in] | x | Pointer to structure holding the data for the current encoding macroblock
  [in] | w | Entropy coding write pointer
  [in] | blk_row | The row index of the current transform block in the macroblock. Each unit has 4 pixels in y plane
  [in] | blk_col | The col index of the current transform block in the macroblock. Each unit has 4 pixels in y plane
  [in] | plane | The index of the current plane
  [in] | block | The index of the current transform block in the macroblock. It's defined by number of 4x4 units that have been coded before the currernt transform block
  [in] | tx_size | The given transform size

## av1_write_intra_coeffs_mb()

void av1_write_intra_coeffs_mb | ( | const AV1_COMMON *const | cm,
|  | MACROBLOCK * | x,
|  | aom_writer * | w,
|  | BLOCK_SIZE | bsize )

Write quantized coefficients of all transform blocks in an intra macroblock into the bitstream using entropy coding.

All transform blocks in the intra macroblock share the same transform size.

This function use av1_write_coeffs_txb() to code each transform block in raster order.

Parameters

  [in] | cm | Top-level structure shared by encoder and decoder
  [in] | x | Pointer to structure holding the data for the current encoding macroblock
  [in] | w | Entropy coding write pointer
  [in] | bsize | Block size of the current macroblock

## av1_get_txb_entropy_context()

uint8_t av1_get_txb_entropy_context | ( | const tran_low_t * | qcoeff,
|  | const SCAN_ORDER * | scan_order,
|  | int | eob )

Pack the context info of the current transform block into an uint8_t.

This context info will be collected and consolidated by its neighbor transform blocks for coding transform block skip flag (tx_skip) and the sign of DC coefficient (dc_sign).

Parameters

  [in] | qcoeff | Buffer of quantized coefficients
  [in] | scan_order | Coding order of coefficients in the transform block
  [in] | eob | The scan index of last non-zero coefficient plus one

## av1_update_intra_mb_txb_context()

void av1_update_intra_mb_txb_context | ( | const AV1_COMP * | cpi,
|  | ThreadData * | td,
|  | RUN_TYPE | dry_run,
|  | BLOCK_SIZE | bsize,
|  | uint8_t | allow_update_cdf )

Update the probability model (cdf) and the entropy context related to coefficient coding for all transform blocks in the intra macroblock.

This function will go through each transform block in the intra macorblock and call av1_update_and_record_txb_context to update the probability model and entropy context properly.

Parameters

  [in] | cpi | Top-level encoder structure
  [in] | td | Top-level multithreading structure
  [in] | dry_run | Whether this is a dry run.
  [in] | bsize | Block size of the current macroblock
  [in] | allow_update_cdf | Allowed to update probability model (cdf) or not.

## av1_update_and_record_txb_context()

void av1_update_and_record_txb_context | ( | int | plane,
|  | int | block,
|  | int | blk_row,
|  | int | blk_col,
|  | BLOCK_SIZE | plane_bsize,
|  | TX_SIZE | tx_size,
|  | void * | arg )

Update the probability model (cdf) and the entropy context related to coefficient coding for a transform block.

There are regular mode and dry run for this funtion.

Regular mode:

The probability model (cdf) for each coding symbol in the transform block will be updated.

The entropy context of this transform block will be updated.

Dry run:

The probability model update will be skipped.

The entropy context of this transform block will be updated.

Parameters

  [in] | plane | The index of the current plane.
  [in] | block | The index of the current transform block in the macroblock. It's defined by number of 4x4 units that have been coded before the currernt transform block.
  [in] | blk_row | The row index of the current transform block in the macroblock. Each unit has 4 pixels in y plane.
  [in] | blk_col | The col index of the current transform block in the macroblock. Each unit has 4 pixels in y plane.
  [in] | plane_bsize | Block size for this plane. When the video source uses chroma subsampling, the block size of UV planes will be smaller than the block size of Y plane.
  [in] | tx_size | The given transform size.
  [in] | arg | This parameter will be translated into tokenize_b_args, in which RUN_TYPE indicates using regular mode or dry run.

## av1_record_txb_context()

void av1_record_txb_context | ( | int | plane,
|  | int | block,
|  | int | blk_row,
|  | int | blk_col,
|  | BLOCK_SIZE | plane_bsize,
|  | TX_SIZE | tx_size,
|  | void * | arg )

Update the entropy context related to coefficient coding for a transform block.

There are regular mode and dry run for this function.

Regular mode:

The entropy context of this transform block will be updated.

Dry run:

The probability model update will be skipped.

The entropy context of this transform block will be updated.

Parameters

  [in] | plane | The index of the current plane.
  [in] | block | The index of the current transform block in the macroblock. It's defined by number of 4x4 units that have been coded before the currernt transform block.
  [in] | blk_row | The row index of the current transform block in the macroblock. Each unit has 4 pixels in y plane.
  [in] | blk_col | The col index of the current transform block in the macroblock. Each unit has 4 pixels in y plane.
  [in] | plane_bsize | Block size for this plane. When the video source uses chroma subsampling, the block size of UV planes will be smaller than the block size of Y plane.
  [in] | tx_size | The given transform size.
  [in] | arg | This parameter will be translated into tokenize_b_args, in which RUN_TYPE indicates using regular mode or dry run.

## av1_get_cb_coeff_buffer()

CB_COEFF_BUFFER * av1_get_cb_coeff_buffer | ( | const struct AV1_COMP * | cpi,
|  | int | mi_row,
|  | int | mi_col )

Get the corresponding CB_COEFF_BUFFER of the current macro block.

The macroblock's location is described by mi_row and mi_col, row and column mi indexes in the coding frame.

Each mi unit is a 4x4 pixel block.

Parameters

  [in] | cpi | Top-level encoder structure.
  [in] | mi_row | Row mi index of the current transform block in the frame.
  [in] | mi_col | Column mi index of the current transform block in the frame.

Returns
  CB_COEFF_BUFFER* Pointer of CB_COEFF_BUFFER associated to this macroblock.

Referenced by encode_sb_row().

## av1_cost_skip_txb()

int av1_cost_skip_txb | ( | const CoeffCosts * | coeff_costs,
|  | const TXB_CTX *const | txb_ctx,
|  | int | plane,
|  | TX_SIZE | tx_size )

inline static

Returns the entropy cost associated with skipping the current transform block.

Parameters

  [in] | coeff_costs | Table of entropy cost for coefficient coding.
  [in] | txb_ctx | Context info for entropy coding transform block skip flag (tx_skip) and the sign of DC coefficient (dc_sign).
  [in] | plane | The index of the current plane
  [in] | tx_size | The transform size

References CoeffCosts::coeff_costs, and LV_MAP_COEFF_COST::txb_skip_cost.

## av1_optimize_txb()

int av1_optimize_txb | ( | const struct AV1_COMP * | cpi,
|  | MACROBLOCK * | x,
|  | int | plane,
|  | int | block,
|  | TX_SIZE | tx_size,
|  | TX_TYPE | tx_type,
|  | const TXB_CTX *const | txb_ctx,
|  | int * | rate_cost,
|  | int | sharpness )

Adjust the magnitude of quantized coefficients to achieve better rate-distortion (RD) trade-off.

This function goes through each coefficient and greedily choose to lower the coefficient magnitude by 1 or not based on the RD score.

The coefficients are processing in reversed scan order.

Note that, the end of block position (eob) may change if the original last coefficient is lowered to zero.

Parameters

  [in] | cpi | Top-level encoder structure
  [in] | x | Pointer to structure holding the data for the current encoding macroblock
  [in] | plane | The index of the current plane
  [in] | block | The index of the current transform block in the
  [in] | tx_size | The transform size
  [in] | tx_type | The transform type
  [in] | txb_ctx | Context info for entropy coding transform block skip flag (tx_skip) and the sign of DC coefficient (dc_sign).
  [out] | rate_cost | The entropy cost of coding the transform block after adjustment of coefficients.
  [in] | sharpness | When sharpness > 0, the function will be less aggressive towards lowering the magnitude of coefficients. In this way, the transform block will contain more high-frequency coefficients and therefore will preserve the sharpness of the reconstructed block.

## av1_cost_coeffs_txb()

int av1_cost_coeffs_txb | ( | const MACROBLOCK * | x,
|  | const int | plane,
|  | const int | block,
|  | const TX_SIZE | tx_size,
|  | const TX_TYPE | tx_type,
|  | const TXB_CTX *const | txb_ctx,
|  | int | reduced_tx_set_used )

Compute the entropy cost of coding coefficients in a transform block.

Parameters

  [in] | x | Pointer to structure holding the data for the current encoding macroblock.
  [in] | plane | The index of the current plane.
  [in] | block | The index of the current transform block in the macroblock. It's defined by number of 4x4 units that have been coded before the currernt transform block.
  [in] | tx_size | The transform size.
  [in] | tx_type | The transform type.
  [in] | txb_ctx | Context info for entropy coding transform block skip flag (tx_skip) and the sign of DC coefficient (dc_sign).
  [in] | reduced_tx_set_used | Whether the transform type is chosen from a reduced set.

## av1_cost_coeffs_txb_laplacian()

int av1_cost_coeffs_txb_laplacian | ( | const MACROBLOCK * | x,
|  | const int | plane,
|  | const int | block,
|  | const TX_SIZE | tx_size,
|  | const TX_TYPE | tx_type,
|  | const TXB_CTX *const | txb_ctx,
|  | const int | reduced_tx_set_used,
|  | const int | adjust_eob )

Estimate the entropy cost of coding a transform block using Laplacian distribution.

This function compute the entropy costs of the end of block position (eob) and the transform type (tx_type) precisely.

Then using av1_cost_coeffs_txb_estimate() (see av1/encoder/txb_rdopt.c) to estimate the entropy costs of coefficients in the transform block.

In the end, the function returns the sum of entropy costs of end of block position (eob), transform type (tx_type) and coefficients.

Compared to av1_cost_coeffs_txb, this function is much faster but less accurate.

Parameters

  [in] | x | Pointer to structure holding the data for the current encoding macroblock
  [in] | plane | The index of the current plane
  [in] | block | The index of the current transform block in the macroblock. It's defined by number of 4x4 units that have been coded before the currernt transform block
  [in] | tx_size | The transform size
  [in] | tx_type | The transform type
  [in] | txb_ctx | Context info for entropy coding transform block skip flag (tx_skip) and the sign of DC coefficient (dc_sign).
  [in] | reduced_tx_set_used | Whether the transform type is chosen from a reduced set.
  [in] | adjust_eob | Whether to adjust the end of block position (eob) or not.

Returns
  int Estimated entropy cost of coding the transform block.