Techniques for encoding and decoding digital data using graph-based transformations

Patent metadata

Field	Value
Publication number	US-11122298-B2
Application number	US-201716465926-A
Country	US
Kind code	B2
Filing date	Nov 29, 2017
Priority date	Dec 2, 2016
Publication date	Sep 14, 2021
Grant date	Sep 14, 2021

Abstract

A method and an apparatus for encoding and/or decoding digital images, wherein the encoding apparatus includes a processor configured for determining weights of a graph related to an image by minimizing a cost function, transforming the weights through a graph Fourier transform, quantizing the transformed weights, computing transformed coefficients through a graph Fourier transform of a graph having the transformed weights as weights, de-quantizing the quantized transformed weights, computing a reconstructed image through an inverse graph Fourier transform on the basis of the de-quantized transformed weights, computing a distortion cost on the basis of the reconstructed image and the original image, generating a final encoded image on the basis of the distortion cost.

First claim

The invention claimed is:

1. An apparatus for encoding digital images and/or video streams, said apparatus comprising:
a memory;
a central processing unit configured to:
facilitate acquiring at least a portion of an image (f) from a source,
facilitate transmitting at least a portion of an encoded image to a destination, and
read at least a portion of said image (f),

wherein the memory includes at least a set of quantization parameters ({Δ i }), and wherein the central processing unit is further configured to:
determine a weights vector (w*) of a graph related to said at least the portion of the image (f) by minimizing a cost function that takes into account a cost of transformed coefficients (R c ) of said graph and a cost of a description (R G ) of said graph, wherein said description cost (R G ) depends on a graph Fourier transform of weights of said graph as a signal laying on a dual-graph that is an unweighted graph where each node represents an edge of said graph, and two nodes of said dual-graph are connected only if their corresponding edges in the graph share a common endpoint,
generate a transformed weights vector (ŵ*) by computing a graph Fourier transform of the weights vector (w*) laying on said dual-graph,
quantize the transformed weights vector (ŵ*) according to each element (Δ i ) of said set of quantization parameters ({Δ i }), in order to generate a set of quantized transformed weights vector ({ŵ i *}),
compute, for each quantized transformed weights (ŵ i *) of said set of quantized transformed weights vector ({ŵ i *}), transformed coefficients ({circumflex over (f)} i , {circumflex over (f)} i ) through a graph Fourier transform of a graph related to said at least a portion of the image (f), wherein said graph has said quantized transformed weights (ŵ i *) as weights, in order to generate a set of transformed coefficients ({{circumflex over (f)} i }, {{circumflex over (f)} i }),
de-quantize each element (ŵ i *) of the set of quantized transformed weights vector ({ŵ i *})) according to the quantization parameter (Δ i ) used to quantize it, in order to generate a set of de-quantized transformed weights vector ({{dot over (w)} i *}),
compute, for each element ({dot over (w)} i *) of said de-quantized transformed weights vector ({{dot over (w)} i *}), an inverse graph Fourier transform on a basis of said element ({dot over (w)} i *) and the transformed coefficients ({dot over ({circumflex over (f)})} i , {circumflex over (f)} i ) used in the graph Fourier transform, in order to get a set of reconstructed image samples ({{dot over (f)} i }),
compute, for each reconstructed image sample ({dot over (f)} i ) of the set of reconstructed image samples ({{dot over (f)} i }), a distortion cost on a basis of said reconstructed image sample ({dot over (f)} i ) and said at least a portion of the image (f),
select transformed coefficients ({circumflex over (f)}, {circumflex over (f)} q ), quantized transformed weights (ŵ*), and a quantization parameter (Δ) used for quantizing said transformed quantized transformed weights, associated to the reconstructed image sample ({dot over (f)} i ) having the lowest distortion cost, and transmitting and/or storing them ({circumflex over (f)}, {circumflex over (f)} q , ŵ*, Δ).

2. The encoding apparatus according to claim 1 , wherein the central processing unit is further configured to:
quantize each element ({circumflex over (f)} i ) of the set of transformed coefficients ({{circumflex over (f)} i }) according to a second quantization parameter (q), in order to generate a set of quantized transformed coefficients ({{circumflex over (f)} i q }),
de-quantize each element ({circumflex over (f)} i q ) of the set of quantized transform coefficients ({{circumflex over (f)} i q }) according to the second quantization parameter (q), in order to generate a set of de-quantized transform coefficients ({{dot over ({circumflex over (f)})} i }),
wherein the transform coefficients used for computing the inverse graph Fourier transform, selected on the basis of the distortion cost, and transmitted are contained in the set of de-quantized transform coefficients ({{dot over ({circumflex over (f)})}}).

3. The encoding apparatus according to claim 1 , wherein the central processing unit is further configured to:
filter said at least a portion of the image (f), in order to remove at least a frequency component having its frequency higher than a threshold.

4. The encoding apparatus according to claim 1 , wherein the central processing unit is further configured to:
reduce the size of the weights vector (w*) by truncating it at the first {tilde over (M)}<M elements, wherein M is the edge number of the graph related to said at least a portion of the image, and
transmit the original size of said weights vector (w*).

5. The encoding apparatus according to claim 1 , wherein said at least the portion of the image (f) is a component of an RGB image.

6. The encoding apparatus according to claim 1 , wherein said at least the portion of the image (f) is a luminance component or a difference between the luminance component and a chroma component of a YUV coded color image.

7. The encoding apparatus according to claim 1 , wherein the central processing unit is further configured to:
compress the selected transformed coefficients ({circumflex over (f)}, {circumflex over (f)} q ), the selected quantized transformed weights (ŵ*), and the selected quantization parameter (Δ) using an entropy encoding algorithm, before transmitting them ({circumflex over (f)}, {circumflex over (f)} q , ŵ*, Δ).

8. An apparatus for decoding digital images and/or video streams, said apparatus comprising:
a memory;
a central processing unit configured to:
facilitate acquiring at least a compressed portion of an image (f) from a communication channel or a storage media,
facilitate outputting at least a portion of a reconstructed image,
receive transformed coefficients ({circumflex over (f)}, {circumflex over (f)} q ), quantized transformed weights (ŵ*), and at least a quantization parameter (Δ) related to said transformed weights,
de-quantize the quantized transformed weights (ŵ*) according to said at least the quantization parameter (Δ), in order to generate de-quantized transformed weights ({dot over (ŵ)}*),
determine de-quantized reconstructed weights ({dot over (w)}*) by computing an inverse graph Fourier transform of the de-quantized transformed weights ({dot over (ŵ)}*), which are considered laying on a dual-graph that is an unweighted graph where each node represents an edge of a graph related to the image (f), and two nodes of said dual-graph are connected only if their corresponding edges in the graph share a common endpoint,
generate said at least a portion of said reconstructed image by computing an inverse graph Fourier transform on a basis of the de-quantized reconstructed weights ({dot over (w)}*) and the transformed coefficients ({circumflex over (f)}, {circumflex over (f)} q ),
output said at least the portion of said reconstructed image.

9. The decoding apparatus according to claim 8 , wherein the received transformed coefficients ({circumflex over (f)} q ) are quantized according to at least a second quantization parameter (q), and wherein the central processing unit is further configured to:
de-quantize the transformed coefficients ({circumflex over (f)} q ) according to said at least the second quantization parameter (q), in order to generate de-quantized transformed coefficients ({dot over ({circumflex over (f)})}),
generate said at least the portion of said reconstructed image by computing an inverse graph Fourier transform on a basis of the de-quantized transformed weights ({dot over (ŵ)}*) an

Assignees

• Sisvel Tech S R L
• Ecole Polytechnique Fed Lausanne Epfl

Inventors

• Fracastoro Giulia
• Thanou Dorina
• Frossard Pascal

Classifications

• H04N19/625 Primary

  using discrete cosine transform [DCT] · CPC title

• H04N19/60 Primary

  using transform coding · CPC title

• G06V30/1988

  Graph matching (graphical image representation G06V30/18181) · CPC title

• G06V30/1916

  Validation; Performance evaluation · CPC title

• G06V10/426

  Graphical representations · CPC title