Enhanced image compression with clustering and lookup procedures

Patent metadata

Field	Value
Publication number	US-2021195193-A1
Application number	US-202117248795-A
Country	US
Kind code	A1
Filing date	Feb 8, 2021
Priority date	May 21, 2018
Publication date	Jun 24, 2021
Grant date	—

Abstract

An image encoder includes a processor and a memory. The memory includes instructions configured to cause the processor to perform operations. In one example implementation, the operations may include determining whether a dictionary item is available for replacing a block of an image being encoded, the determining based on a hierarchical lookup mechanism, and encoding the image along with reference information of the dictionary item in response to determining that the dictionary item is available. In one more example implementation, the operations may include performing principal component analysis (PCA) on a block to generate a corresponding projected block, the block being associated with a group of images, comparing the projected block with a corresponding threshold, descending the block recursively based on the threshold until a condition is satisfied, and identifying a left over block as a cluster upon satisfying of the condition.

First claim

What is claimed is:

1 . A method, comprising:
determining, at an encoder, whether a dictionary item is available for replacing transform coefficients corresponding to a block of an image being encoded, the determining based on a hierarchical lookup mechanism, the transform coefficients being obtained by converting values of the pixels of the block from the spatial domain to a frequency domain; and encoding, at the encoder, the image along with reference information of the dictionary item in response to determining that the dictionary item is available.

2 . The method of claim 1 , wherein the hierarchical lookup mechanism comprises:
generating a projected block based on a corresponding projection matrix; and comparing the projected block with a corresponding threshold for determining whether the block matches the dictionary item.

3 . The method of claim 1 , further comprising:
receiving, by the encoder, a dictionary that includes the dictionary item.

4 . The method of claim 1 , wherein the dictionary item is associated with a feature of the image.

5 . The method of claim 1 , wherein a size of the block is an 8×8 matrix.

6 . The method of claim 1 , further comprising:
determining the dictionary item, wherein determining the dictionary item comprises: performing principal component analysis, PCA, on a block to generate a corresponding projected block, the block being associated with a group of images, values of the pixels of the block being converted from the spatial domain to a frequency domain before performing the PCA; comparing the projected block with a corresponding threshold; descending the block recursively based on the threshold until a condition is satisfied; and identifying a left over block as a cluster upon satisfying of the condition.

7 . A method, comprising:
performing principal component analysis (PCA) on a block to generate a corresponding projected block, the block being associated with a group of images, values of the pixels of the block being converted from the spatial domain to a frequency domain before performing the PCA; comparing the projected block with a corresponding threshold; descending the projected blocks recursively based on the threshold until a condition is satisfied; and identifying a left over block as a cluster upon satisfying of the condition.

8 . The method of claim 7 , wherein the threshold is generated using Otsu's method.

9 . An apparatus, comprising:
a decoder configured to decode an encoded image produced by: determining whether a dictionary item is available for replacing transform coefficients corresponding to a block of an image being encoded, the determining based on a hierarchical lookup mechanism, the transform coefficients being obtained by converting values of the pixels of the block from the spatial domain to a frequency domain, the encoded image including reference information of the dictionary item in response to determining that the dictionary item is available.

10 . The apparatus of claim 9 , wherein the processor is further configured to:
generate a projected block based on a corresponding projection matrix; and compare the projected block with a corresponding threshold for determining whether the block matches the dictionary item.

11 . The apparatus of claim 9 , wherein the processor is further configured to:
receive a dictionary that includes the dictionary item.

12 . The apparatus of claim 9 , wherein the dictionary item is associated with a feature of the image.

13 . The apparatus of claim 9 , wherein a size of the block is an 8×8 matrix.

14 . An encoder, comprising:
a processor; and a memory, the memory including instructions configured to cause the processor to:
perform principal component analysis (PCA) on a block to generate a corresponding projected block, values of the pixels of the block being converted from the spatial domain to a frequency domain before performing the PCA, the block being associated with a group of images;
compare the projected block with a corresponding threshold;
descend the block recursively based on the threshold until a condition is satisfied; and
identify a left over block as a cluster upon satisfying of the condition.

15 . The encoder of claim 14 , wherein the threshold is generated using Otsu's method.

16 . A non-transitory computer-readable storage medium having stored thereon computer executable program code which, when executed on a computer system, causes the computer system to perform a method, comprising:
determining, at an encoder, whether a dictionary item is available for replacing a block of an image being encoded, the determining based on a hierarchical lookup mechanism; and encoding, at the encoder, the image along with reference information of the dictionary item in response to determining that the dictionary item is available.

17 . The computer-readable storage medium of claim 16 , wherein the hierarchical lookup mechanism further comprises code for:
generating a projected block based on a corresponding projection matrix; and comparing the projection matrix with a corresponding threshold for determining whether the block matches the dictionary item.

18 . The computer-readable storage medium of claim 16 , further comprising code for:
receiving, by the encoder, a dictionary that includes the dictionary item.

19 . The computer-readable storage medium of claim 16 , wherein a size of the block is an 8×8 matrix.

Assignees

• Google Llc

Inventors

• Potempa Krzysztof
• Alakuijala Jyrki
• Obryk Robert

Classifications

• H04N19/122 Primary

  Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type · CPC title

• G06V10/7625

  Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms · CPC title

• H04N19/85 Primary

  using pre-processing or post-processing specially adapted for video compression · CPC title

• G06V10/772

  Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries · CPC title

• G06V10/7715

  Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods · CPC title