Optimized template matching approach to intra-coding in video/image compression

Patent metadata

Field	Value
Publication number	US-9544596-B1
Application number	US-201314141778-A
Country	US
Kind code	B1
Filing date	Dec 27, 2013
Priority date	Dec 27, 2013
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

A system includes an encoder and a decoder. The encoder selects a first matched template for un-encoded pixels of a video frame using an algorithm for measuring a similarity between image blocks of the video frame, the algorithm being based on a weighted scheme of reconstructed adjacent pixels, generates at least one residual for the un-encoded pixels of the video frame based on the matched template, and encodes residuals as compressed bits using an asymmetric discrete sine transform (ADST). The decoder decodes the compressed video bits as residuals using the ADST, selects a second matched template using an algorithm for measuring a similarity between image blocks of a video frame associated with the compressed video bits, the algorithm being based on a weighted scheme of reconstructed adjacent pixels, and generates reconstructed pixels of the video frame based on the matched template and the decoded compressed video bits.

First claim

What is claimed is:

1. A method for encoding video data, the method comprising:
generating a plurality of candidate templates using a weighted scheme of reconstructed adjacent pixels, the reconstructed adjacent pixels being in one of:
an above row of pixels next to a boundary of an un-encoded image block of a video frame to be encoded, and
a left column of pixels next to the boundary of the un-encoded image block of the video frame to be encoded;

measuring a similarity between the un-encoded image block and each of the plurality of candidate templates;
the weighted scheme including assigning a higher weight to pixels closer to the boundary than pixels further away from the boundary for measuring the similarity;
selecting a matched template for the un-encoded image block based on the measuring of the similarity between the un-encoded image block and each of the plurality of candidate templates;
generating at least one residual for the un-encoded pixel of the video frame based on the selected matched template; and
encoding the at least one residual using an asymmetric discrete sine transform (ADST).

2. The method of claim 1 , wherein:
the measuring of the similarity between image blocks includes using a sum of absolute difference (SAD) algorithm, and
a comparatively smaller SAD value indicates a closer similarity.

3. The method of claim 1 , wherein the selecting of the matched template includes:
selecting a first adjacent above row of pixels;
selecting a second adjacent above row of pixels, the second adjacent above row of pixels being an outer row and the first adjacent above row of pixels being an inner row as compared to the un-encoded pixels of the video frame;
associating a weight ratio with the first adjacent above row of pixels and the second adjacent above row of pixels such that first adjacent above row of pixels is given a higher weight than the second adjacent above row of pixels; and
selecting the matched template based on a sum of absolute difference of the first adjacent above row of pixels and second adjacent above row of pixels.

4. The method of claim 1 , wherein the selecting of the matched template includes:
selecting a first adjacent left column of pixels;
selecting a second adjacent left column of pixels, the second adjacent left column of pixels being an outer column and the first adjacent left column of pixels being an inner column as compared to the un-encoded pixels of a video frame;
associating a weight ratio with the first adjacent left column of pixels and the second adjacent left column of pixels such that first adjacent left column of pixels is given a higher weight than the second adjacent left column of pixels; and
selecting the matched template based on a sum of absolute difference of the first adjacent left column of pixels and second adjacent left column of pixels.

5. The method of claim 1 , wherein the selecting of the matched template includes:
searching a reconstructed area of the video frame for a candidate template;
selecting the matched template as the candidate template having a lowest value calculated using a lowest value of an algorithm for measuring the similarity between image blocks; and
selecting a prediction block based on the matched template.

6. The method of claim 1 , wherein the selecting of the matched template includes:
searching a portion of a reconstructed area of the video frame for a candidate template;
selecting the matched template as the candidate template having a lowest value calculated using a lowest value of an algorithm for measuring the similarity between image blocks; and
using a block associated with the matched template in the reconstructed area as a prediction block.

7. The method of claim 1 , wherein:
the generating of the at least one residual includes subtracting a prediction block from the un-encoded pixels; and
the encoding of the at least one residual includes applying the ADST to transform a residual block including the at least one residual, the method further comprising:
quantizing transform coefficients associated with the encoded at least one residual;
entropy encoding the quantized transform coefficients as a compressed video bit stream; and
transmitting the compressed video bit stream including a header indicating an intra-frame coding mode, the intra-frame coding mode indicating template matched prediction and ADST.

8. The method of claim 1 , wherein:
the selecting of the matched template includes selecting at least two reconstructed pixels adjacent to the un-encoded pixels as a target template;
the encoding of the at least one residual is based on an asymmetric property of the at least two reconstructed pixels; and
the asymmetric property is based on a similarity of the at least two reconstructed pixels to the un-encoded pixel.

9. A method for decoding video data, the method comprising:
decoding compressed video bits as at least one residual using an asymmetric discrete sine transform (ADST);
generating a plurality of candidate templates using a weighted scheme of reconstructed adjacent pixels, the reconstructed adjacent pixels being in one of:
an above row of pixels next to a boundary of an un-encoded image block of a video frame to be encoded, and
a left column of pixels next to the boundary of the un-encoded image block of the video frame to be encoded;

measuring a similarity between image blocks of a video frame and each of the plurality of candidate templates;
the weighted scheme includes assigning a higher weight to pixels closer to the boundary than the pixels further away from the boundary for measuring the similarity;
selecting a matched template for the un-encoded pixel of the video frame based on the measuring of the similarity between the image blocks and each of the plurality of candidate templates; and
generating at least one reconstructed pixel of the video frame based on the matched template and the decoded compressed video bits.

10. The method of claim 9 , wherein:
the measuring of the similarity between image blocks includes using a sum of absolute difference (SAD) algorithm; and
a comparatively smaller SAD value indicates a closer similarity.

11. The method of claim 9 , wherein the selecting of the matched template includes:
selecting a first adjacent above row of pixels;
selecting a second adjacent above row of pixels, the second adjacent above row of pixels being an outer row and the first adjacent above row of pixels being an inner row as compared to an un-reconstructed pixel of the video frame;
associating a weight ratio with the first adjacent above row of pixels and the second adjacent above row of pixels such that first adjacent above row of pixels is given a higher weight than the second adjacent above row of pixels; and
selecting the matched template based on a weighted sum of absolute difference of the first adjacent above row of pixels and second adjacent above row of pixels.

12. The method of claim 9 , wherein the selecting of the matched template includes:
selecting a first adjacent left column of pixels;
selecting a second adjacent left column of pixels, the second adjacent left column of pixels being an outer column and the first adjacent left column of pixels being an inner column as compared to the un-reconstructed pixels of the video frame;
associating a weight ratio with the first adjacent left column of pixels and the second adjacent left column of pixels such that first adjacent left column of pixels is given a higher weight than the second adjacent left column of pixels; and
selecting the matched template based on a weighted sum of absolute difference of the first adjacent lef

Assignees

• Google Inc

Inventors

• Han Jingning
• Su Hui
• Xu Yaowu

Classifications

• H04N19/00775 Primary

  Electricity · mapped topic

• H04N19/105 Primary

  Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction · CPC title

• H04N19/82

  involving filtering within a prediction loop · CPC title

• H04N19/182

  the unit being a pixel · CPC title

• H04N19/154

  Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion (use of rate-distortion criteria H04N19/147) · CPC title