# US 2019/0356916 A1 · Enhanced image compression with clustering and lookup procedures

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

- Number: US 2019/0356916 A1
- Document ID: US20190356916A1
- Status: Published application
- Kind: A1
- Application number: 15/985,317
- Filed: 2018-05-21
- Published: 2019-11-21
- Earliest claimed: 2018-05-21
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Krzysztof Potempa; Jyrki Alakuijala; Robert Obryk
- Web page: https://patentgrep.com/patent/US20190356916A1

## CPC

- H04N 19/85: using pre-processing or post-processing specially adapted for video compression
- G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
- G06V 10/7625: {Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms}
- G06V 10/7715: {Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods}
- G06V 10/772: Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries
- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- 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/176: the region being a block, e.g. a macroblock
- H04N 19/625: using discrete cosine transform [DCT]
- H03M 7/3077: {Sorting}
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

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

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the hierarchical lookup mechanism comprises:
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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 1)

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

### Claim 6

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

### Claim 7 (depends on 6)

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

### Claim 8

An encoder, comprising:
a processor; and
a memory, the memory including instructions configured to cause the processor to:
determine whether a dictionary item is available for replacing a block of an image being encoded, the determining based on a hierarchical lookup mechanism; and
encode the image along with reference information of the dictionary item in response to determining that the dictionary item is available.

### Claim 9 (depends on 8)

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

### Claim 10 (depends on 8)

The encoder of claim 8, wherein the processor is further configured to:
receive a dictionary that includes the dictionary item.

### Claim 11 (depends on 8)

The encoder of claim 8, wherein the dictionary item is associated with a feature of the image.

### Claim 12 (depends on 8)

The encoder of claim 8, wherein a size of the block is an 8×8 matrix.

### Claim 13

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

### Claim 14 (depends on 13)

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

### Claim 15

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.

### Claim 16 (depends on 15)

The computer-readable storage medium of claim 15, 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.

### Claim 17 (depends on 15)

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

### Claim 18 (depends on 15)

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

### Claim 19

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

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein the threshold is generated using Otsu's method.
