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

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.

A method for encoding digital images and/or video streams, said method comprising:

• an acquisition phase, wherein at least a portion of an image (f) is acquired from a source,
• a graph learning phase, wherein a weights vector (w*) of a graph related to said at least a portion of the image (f) is determined, through use of a central processing unit, by minimizing a cost function that takes into account the cost of transformed coefficients (Rc) of said graph and the cost of the description (RG) of said graph, and wherein said description cost (RG) depends on a graph Fourier transform of the 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,
• a weights vector transformation phase, wherein a transformed weights vector (ŵ*) is generated, through the central processing unit, by computing a graph Fourier transform of the weights vector (w*) laying on said dual-graph,
• a weights vector quantization phase, wherein the transformed weights vector (ŵ*) are quantized according to each element (Δi) of said set of quantization parameters ({Δi}) using the central processing unit, in order to generate a set of quantized transformed weights vector ({ŵi*}),
• a transformation phase, wherein transformed coefficients ({dot over ({circumflex over (f)})}, {circumflex over (f)}i) are computed, by the central processing unit, for each quantized transformed weights (ŵi*) of said set of quantized transformed weights vector ({ŵi*}) through a graph Fourier transform of a graph related to said at least a portion of the image (f) and having said quantized transformed weights (ŵi*) as weights, in order to generate a set of transformed coefficients ({{dot over ({circumflex over (f)})}},{{circumflex over (f)}i}),
• a de-quantization phase, wherein each element (ŵi*) of the set of quantized transformed weights vector ({ŵi*}) is de-quantized, by the central processing unit, 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*}),
• an inverse transformation phase, wherein an inverse graph Fourier transform is computed for each element ({dot over (w)}i*) of said de-quantized transformed weights vector ({{dot over (w)}i*}), through the central processing unit, on the 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}),
• a distortion computation phase, wherein a distortion cost is computed for each reconstructed image sample ({dot over (f)}i) of the set of reconstructed image samples ({{dot over (f)}i}), through the central processing unit, on the basis of said reconstructed image sample ({dot over (f)}i) and said at least a portion of the image (f),
• a selection phase, wherein it is selected, through the central processing unit, transformed coefficients ({circumflex over (f)}, {circumflex over (f)}q), quantized transformed weights (ŵ*), and at least 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
• a transmission phase, wherein the selected elements ({circumflex over (f)}, {circumflex over (f)}q, ŵ*, Δ) are transmitted and/or stored.

A method for decoding digital images and/or video streams, said method comprising:

• a reception phase, wherein transformed coefficients ({circumflex over (f)}, {circumflex over (f)}q), quantized transformed weights (ŵ*), and a quantization parameter (Δ) are received,
• a de-quantization phase, wherein the quantized transformed weights (ŵ*) are de-quantized using a central processing unit, according to the quantization parameter (Δ), in order to generate de-quantized transformed weights ({dot over (ŵ)}*),
• a weights reconstruction phase, wherein de-quantized reconstructed weights ({dot over (w)}*) are determined, through the central processing unit, 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,
• an inverse transformation phase, wherein at least a portion of a reconstructed image is generated, through the central processing unit, by computing an inverse graph Fourier transform on the basis of the de-quantized reconstructed weights ({dot over (w)}*) and the transformed coefficients ({circumflex over (f)}, {circumflex over (f)}q),
• an output phase, wherein said at least a portion of said reconstructed image is outputted.