# US 11,122,298 B2 · Techniques for encoding and decoding digital data using graph-based transformations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,122,298 B2
- Document ID: US11122298B2
- Status: Granted
- Kind: B2
- Application number: 16/465,926
- Filed: 2017-11-29
- Published: 2020-07-16
- Granted: 2021-09-14
- Earliest claimed: 2016-12-02
- Assignees: Sisvel Technology S.R.L.; Ecole Polytechnique Federale De Lausanne (Epfl)
- Applicants: Sisvel Technology S.R.L.; Ecole Polytechnique Federale De Lausanne (Epfl)
- Inventors: Giulia Fracastoro; Dorina Thanou; Pascal Frossard
- Web page: https://patentgrep.com/patent/US11122298B2

## CPC

- H04N 19/60: using transform coding
- G06V 10/426: Graphical representations
- G06V 10/431: {Frequency domain transformation; Autocorrelation}
- G06V 30/1916: {Validation; Performance evaluation}
- G06V 30/1988: {Graph matching (graphical image representation G06V30/18181)}
- H04N 19/122: Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
- H04N 19/17: the unit being an image region, e.g. an object
- H04N 19/625: using discrete cosine transform [DCT]
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## 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.

## Claims

### Claim 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 (Rc) of said graph and a cost of a description (RG) of said graph, wherein said description cost (RG) 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, ŵ*, Δ).

### Claim 2 (depends on 1)

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)}iq}),
de-quantize each element ({circumflex over (f)}iq) of the set of quantized transform coefficients ({{circumflex over (f)}iq}) 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)})}}).

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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*).

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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, ŵ*, Δ).

### Claim 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.

### Claim 9 (depends on 8)

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 (ŵ)}*) and the de-quantized transformed coefficients ({dot over ({circumflex over (f)})}).

### Claim 10 (depends on 8)

The decoding apparatus according to claim 8, wherein the central processing unit is further configured to:
receive a size value representing the original size of the quantized transformed weights (ŵ*),
increase the size of the quantized transformed weights (ŵ*) by adding null values, before determining the de-quantized reconstructed weights (ŵ*).

### Claim 11 (depends on 8)

The decoding apparatus according to claim 8, wherein said at least the portion of said reconstructed image is a component of an RGB image, and wherein the central processing unit is further configured for to:
generate at least another component of said RGB image on a basis of said at least the portion of said reconstructed image.

### Claim 12 (depends on 8)

The decoding apparatus according to claim 8, wherein said at least the portion of the reconstructed image is a luminance component or a difference between the luminance component and a chroma component of a YUV coded colour image.

### Claim 13 (depends on 8)

The decoding apparatus according to claim 8, wherein the central processing unit is further configured to:
decompress the received transformed coefficients ({circumflex over (f)}, {circumflex over (f)}q), the received quantized transformed weights (ŵ*), and the received quantization parameter (Δ) using an entropy encoding algorithm, before de-quantizing them ({circumflex over (f)}, {circumflex over (f)}q, ŵ*, Δ).

### Claim 14

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.

### Claim 15 (depends on 14)

The encoding method according to claim 14, further comprising:
a coefficient quantization phase, wherein each element ({circumflex over (f)}i) of the set of transformed coefficients ({{circumflex over (f)}i}) is quantized, through the central processing unit, according to a second quantization parameter (q), in order to generate a set of quantized transformed coefficients ({{circumflex over (f)}iq}), and
a coefficient de-quantization phase, wherein each element ({circumflex over (f)}iq) of the set of quantized transform coefficients ({{circumflex over (f)}iq}) are de-quantized, through the central processing unit, 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 during the inverse transformation phase, the selection phase, and the transmission phase are contained in the set of de-quantized transform coefficients ({{dot over ({circumflex over (f)})}i}).

### Claim 16

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.

### Claim 17 (depends on 16)

The decoding method according to claim 16, wherein the transformed coefficients ({circumflex over (f)}q) received during the reception phase are quantized according to a second quantization parameter (q), wherein said method also comprises:
a coefficient de-quantization phase, wherein the transformed coefficients ({circumflex over (f)}q) are de-quantized, through the central processing unit, according to the second quantization parameter (q), in order to generate de-quantized transformed coefficients ({dot over ({circumflex over (f)})}), and
wherein during the inverse transformation phase said at least a portion of said reconstructed image is generated, through the central processing unit, by computing an inverse graph Fourier transform on the basis of the de-quantized transformed weights ({dot over (ŵ)}*) and the de-quantized transformed coefficients ({dot over ({circumflex over (f)})}).

### Claim 18 (depends on 14)

A hardware storage device comprising instructions that are executable to perform the method according to claim 14.