Coding using a redundant dictionary, such as video coding using a self-adaptive redundant dictionary including spatial and/or temporal prediction candidte atoms

A video decoding method for decoding a block (F) of a current video frame, the method comprising:

• a) decoding the bits for this block to yield (1) a quantized block mean value {circumflex over (η)}, (2) a number of chosen atoms (K), (3) chosen atom indices (n(k)) and (4) quantized coefficient indices ({tilde over (t)}(k));
• b) saving at least one of (i) at least one block of a previously decoded video frame and (ii) at least one previously decoded block of the current video frame;
• c) obtaining prediction image blocks from the previously decoded video frame or the previously decoded areas of the current video frame, based on the received chosen atom indices (n(k));
• d) performing mean subtraction and normalization on each of the prediction image blocks to generate the chosen atoms, each having zero mean and norm one;
• e) orthonormalizing the K chosen atoms to generate K orthonormal atoms C(K);
• f) dequantizing the quantized coefficient indices ({tilde over (t)}(k)) to obtain quantized coefficient values ({circumflex over (t)}(k));
• and
• g) reconstructing the block using the K orthonormal atoms (C(k)), the quantized coefficient values ({circumflex over (t)}(k)), and the mean block value, according to
• {circumflex over (F)}=Σk=1K{circumflex over (t)}(k)C(k)+{circumflex over (η)}.

A coding method for coding a block of sample values, the method comprising:

• a) receiving as input, a redundant dictionary including candidate atoms;
• b) responsive to a determination that the candidate atoms do not have zero mean and norm 1, performing mean subtraction and normalization on each of the candidate atoms before continuing processing, and otherwise, responsive to a determination that the candidate atoms have zero mean and norm 1, continuing processing;
• c) coding a mean value (η) of the block either directly, or using predictive coding method;
• d) generating a mean-subtracted block using the current block and the mean value of the current block (F′=F−η);
• e) determining
• (1) a number (K) of orthonormalized atoms,
• (2) a subset of K candidate atoms of the redundant dictionary specified by indices n(k), k=1, 2, . . . , K,
• (3) the K orthonormal atoms (C(k)) determined from the subset of atoms (A(n(k))), and
• 4) quantized coefficients ({circumflex over (t)}(k)), quantized coefficient indices ({tilde over (t)}(k)) associated with the K orthonormal atoms (C(k))
• such that a measure of sparsity of non-zero coefficients (t(k)) of the K orthonormal atoms is minimized and the mean-subtracted block F′ can be approximated well by a linear combination of C(k) with the quantized coefficients ({circumflex over (t)}(k));
• and
• f) applying entropy coding on the indices of the subset of atoms (n(k)), and the quantized coefficient indices ({tilde over (t)}(k)).

An encoder for coding a block of sample values, the encoder comprising:

• a) an input interface for receiving a redundant dictionary including candidate atoms;
• b) at least one processor configured to perform a method including
• 1) responsive to a determination that the candidate atoms do not have zero mean and norm 1, performing mean subtraction and normalization on each of the candidate atoms before continuing processing, and otherwise, responsive to a determination that the candidate atoms have zero mean and norm 1, continuing processing,
• 2) coding a mean value (η) of the block either directly, or using predictive coding method,
• 3) generating a mean-subtracted block using the current block and the mean value of the current block (F′=F−η),
• 4) quantized coefficients ({circumflex over (t)}(k)), quantized coefficient indices ({tilde over (t)}(k)) associated with the K orthonormal atoms (C(k))
• such that a measure of sparsity of non-zero coefficients (t(k)) of the K orthonormal atoms is minimized and the mean-subtracted block F′ can be approximated well by a linear combination of C(k) with the quantized coefficients ({circumflex over (t)}(k)), and
• 5) applying entropy coding on the indices of the subset of atoms (n(k)), and the quantized coefficient indices ({tilde over (t)}(k)).