Intra: Difference between revisions
m (→L^2-norm: now subtracting the correct mean) |
mNo edit summary |
||
| Line 1: | Line 1: | ||
In | In Daala, intra-frame predictors are coefficients that are used to predict the contents of a block based on its three neighboring blocks. Consider a 4x4 block structure: | ||
<math> | <math> | ||
| Line 22: | Line 22: | ||
These predictors often follow certain geometry in the time-domain image space. Imagine a vertical edge that runs through <math>y</math>. A natural predictor might be to simply copy the values <math>\begin{array}{cccc}x_{29}&x_{30}&x_{31}&x_{32}\end{array}</math> down into each row of the 4x4 block <math>y</math>. In order to account for the different possible geometries, each block is assigned a <i>mode</i> which indicates what set of prediction coefficients to use (the <math>\beta</math>). When encoding a block <math>y</math>, the encoder chooses a mode, computes <math>\hat e</math> and writes both the block mode and the residual <math>\hat e</math>. | These predictors often follow certain geometry in the time-domain image space. Imagine a vertical edge that runs through <math>y</math>. A natural predictor might be to simply copy the values <math>\begin{array}{cccc}x_{29}&x_{30}&x_{31}&x_{32}\end{array}</math> down into each row of the 4x4 block <math>y</math>. In order to account for the different possible geometries, each block is assigned a <i>mode</i> which indicates what set of prediction coefficients to use (the <math>\beta</math>). When encoding a block <math>y</math>, the encoder chooses a mode, computes <math>\hat e</math> and writes both the block mode and the residual <math>\hat e</math>. | ||
Because the decoder must know the coefficients for each of the block modes, there is a tradeoff between how well we can predict the values in <math>y</math> (number of block modes) with decoder complexity. Our hypothesis is that the optimal number of block modes will correspond to how closely we can fit different geometries inside the block. For 4x4 blocks, this might correspond to a mode for each of the 8 cardinal directions (ask Jason to clarify) with larger blocks potentially supporting a larger number of directions. In addition, we would like to support the DC and True Motion modes from | Because the decoder must know the coefficients for each of the block modes, there is a tradeoff between how well we can predict the values in <math>y</math> (number of block modes) with decoder complexity. Our hypothesis is that the optimal number of block modes will correspond to how closely we can fit different geometries inside the block. For 4x4 blocks, this might correspond to a mode for each of the 8 cardinal directions (ask Jason to clarify) with larger blocks potentially supporting a larger number of directions. In addition, we would like to support the DC and True Motion modes from WebM/VP8 as they are often the best fit. For common video sequences, anywhere from 20% to 45% of the intra frames use the True Motion mode [1]. | ||
This is slightly complicated by the fact that our coefficients are not in the time-domain, but are the result of a lapped transform, see [[TDLT]]. In practice all of these modes have an equivalent in the frequency domain | This is slightly complicated by the fact that our coefficients are not in the time-domain, but are the result of a lapped transform, see [[TDLT]]. In practice all of these modes have an equivalent in the frequency domain. As a starting point, we are using the 10 modes from Theora to classify the blocks from a set of sample images. Each category of blocks will be used to construct a set of predictors <math>\beta</math> which is then used to reclassify the blocks based on Sum of Absolute Transform Differences (SATD). <i>Tim suggested weighting each blocks contribution based on SATD_bestfit-SATD_nearest</i>. | ||
== <math>L^2</math>-norm == | == <math>L^2</math>-norm == | ||
| Line 49: | Line 49: | ||
In the case of 4x4 blocks, <math>m=48</math> and <math>l=16</math>. Let <math>C=X^T X</math> and <math>D=X^T Y</math>. Then <math>\beta=C^{-1} D</math>. | In the case of 4x4 blocks, <math>m=48</math> and <math>l=16</math>. Let <math>C=X^T X</math> and <math>D=X^T Y</math>. Then <math>\beta=C^{-1} D</math>. | ||
[1] http://blog.webmproject.org/2010/07/inside-webm-technology-vp8-intra-and.html | |||
Revision as of 09:35, 27 June 2012
In Daala, intra-frame predictors are coefficients that are used to predict the contents of a block based on its three neighboring blocks. Consider a 4x4 block structure:
Assuming a linear predictor, we would like to find the 768 coefficients that best predict from the neighboring . That is, for a given block with coefficients and , we would like a 48x16 matrix such that the residual is minimized (for some -norm). Because it is this residual that is quantized and coded in the bitstream, we would prefer that most of its coefficients are zero. This will be discussed further when comparing the different -norms.
Block Modes
These predictors often follow certain geometry in the time-domain image space. Imagine a vertical edge that runs through . A natural predictor might be to simply copy the values down into each row of the 4x4 block . In order to account for the different possible geometries, each block is assigned a mode which indicates what set of prediction coefficients to use (the ). When encoding a block , the encoder chooses a mode, computes and writes both the block mode and the residual .
Because the decoder must know the coefficients for each of the block modes, there is a tradeoff between how well we can predict the values in (number of block modes) with decoder complexity. Our hypothesis is that the optimal number of block modes will correspond to how closely we can fit different geometries inside the block. For 4x4 blocks, this might correspond to a mode for each of the 8 cardinal directions (ask Jason to clarify) with larger blocks potentially supporting a larger number of directions. In addition, we would like to support the DC and True Motion modes from WebM/VP8 as they are often the best fit. For common video sequences, anywhere from 20% to 45% of the intra frames use the True Motion mode [1].
This is slightly complicated by the fact that our coefficients are not in the time-domain, but are the result of a lapped transform, see TDLT. In practice all of these modes have an equivalent in the frequency domain. As a starting point, we are using the 10 modes from Theora to classify the blocks from a set of sample images. Each category of blocks will be used to construct a set of predictors which is then used to reclassify the blocks based on Sum of Absolute Transform Differences (SATD). Tim suggested weighting each blocks contribution based on SATD_bestfit-SATD_nearest.
-norm
Suppose for some mode we have blocks. We can then construct the matrices and where the ith row of each contains the zero-mean values from the ith block.
In the case of 4x4 blocks, and . Let and . Then .
[1] http://blog.webmproject.org/2010/07/inside-webm-technology-vp8-intra-and.html