# US 2022/0044446 A1 · Parent-child cluster compression

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

- Number: US 2022/0044446 A1
- Document ID: US20220044446A1
- Status: Published application
- Kind: A1
- Application number: 17/139,407
- Filed: 2020-12-31
- Published: 2022-02-10
- Earliest claimed: 2020-08-07
- Assignees: Texas Instruments Incorporated
- Applicants: Texas Instruments Incorporated
- Inventors: Jeffrey Matthew KEMPF; Jonathan Andrew LUCAS
- Web page: https://patentgrep.com/patent/US20220044446A1

## CPC

- G06T 9/00: Image coding (bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00)
- H04N 19/98: Adaptive-dynamic-range coding [ADRC]
- G06T 3/4007: based on interpolation, e.g. bilinear interpolation (image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403)
- G06T 3/4015: Image demosaicing, e.g. colour filter arrays [CFA] or Bayer patterns
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method to compress an image includes assigning each pixel of the image to a cluster based on a red-green-blue (RGB) location of the pixel. The method also includes updating a centroid of the cluster after each pixel is assigned, based at least in part on the RGB location of the pixel, where the centroid is an RGB location. The method includes replacing each pixel in the image with an RGB value of the centroid of the cluster to which the pixel is assigned. The method also includes instructing a display to display a compressed image where, in the compressed image, each pixel in the image is replaced with the RGB value of the centroid of the cluster to which the pixel is assigned.

## Claims

### Claim 1

A method, comprising:
obtaining an image with a processor;
assigning a pixel of the image to a parent cluster of pixels based on a red-green-blue (RGB) location of the pixel;
updating a centroid of the parent cluster based at least in part on the RGB location of the pixel;
splitting the parent cluster into at least a first child cluster and a second child cluster;
assigning the pixel to the first child cluster;
updating a centroid of the first child cluster based at least in part on the RGB location of the pixel;
replacing the pixel in the image with the centroid of the first child cluster; and
instructing, by the processor, a display to display a compressed image, where the pixel in the image is replaced with the centroid of the first child cluster in the compressed image.

### Claim 2 (depends on 1)

The method of claim 1, wherein a location of the centroid of the parent cluster is a location of a brightest pixel in the image.

### Claim 3 (depends on 1)

The method of claim 1, wherein a location of the centroid of the parent cluster is a location of a dimmest pixel in the image.

### Claim 4 (depends on 1)

The method of claim 1, wherein a location of the centroid of the parent cluster is a location of a centroid of the pixels of the image.

### Claim 5 (depends on 1)

The method of claim 1, wherein the parent cluster is a first parent cluster, and an RGB space includes a second parent cluster and a third parent cluster.

### Claim 6 (depends on 5)

The method of claim 5, further comprising splitting each of the second parent cluster and the third parent cluster into two child clusters.

### Claim 7 (depends on 6)

The method of claim 6, further comprising splitting one or more child clusters into additional child clusters until a predetermined number of clusters is reached.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
assigning each pixel in the image to one of the predetermined number of clusters; and
replacing each pixel in the image with a centroid of a respective cluster to which each pixel is assigned.

### Claim 9 (depends on 1)

The method of claim 1, wherein assigning the pixel to the parent cluster based on the location of the pixel in RGB space further comprises assigning the pixel based on a distance between the pixel and the centroid of the parent cluster.

### Claim 10 (depends on 1)

The method of claim 1, wherein splitting the parent cluster further comprises splitting the parent cluster based at least in part on compactness of the parent cluster of pixels.

### Claim 11 (depends on 1)

The method of claim 1, further comprising assigning the pixel to the first child cluster based on a distance in RGB space between the pixel and the centroid of the first child cluster.

### Claim 12 (depends on 1)

The method of claim 1, further comprising storing a key for the pixel, where the key indicates the centroid of the first child cluster.

### Claim 13 (depends on 1)

The method of claim 1, wherein the pixel is a first pixel, and the method further comprises:
assigning a second pixel of the image to the second child cluster;
updating a centroid of the second child cluster based at least in part on a location of the second pixel in RGB space; and
replacing the second pixel in the image with the centroid of the second child cluster.

### Claim 14

A system, comprising:
a processor configured to:
assign each pixel in an image to a child cluster of child clusters, wherein each of the child clusters comprises a centroid, and wherein each centroid comprises a palette of a first set of palettes;
interpolate between palettes of the first set of palettes to produce a second set of palettes;
assign each pixel in the image to an assigned palette in the first set of palettes or the second set of palettes; and
replace each pixel in the image with the assigned palette; and
a memory coupled to the processor, the memory configured to:
store a key for each pixel in the image, wherein the key denotes the assigned palette for each pixel in the image.

### Claim 15 (depends on 14)

The system of claim 14, wherein the processor is further configured to:
compress keys stored for each pixel in the image, wherein the keys are compressed using low entropy encoding.

### Claim 16 (depends on 14)

The system of claim 14, wherein the processor is further configured to:
store a control bit for a sub-block of pixels, where the control bit indicates a type of encoding for the sub-block of pixels.

### Claim 17 (depends on 14)

The system of claim 14, wherein the processor is further configured to assign each pixel in the image to a respective child cluster based at least in part on a location of each pixel in red-green-blue (RGB) space.

### Claim 18 (depends on 14)

The system of claim 14, wherein the processor is further configured to weight each pixel in the image based on a location of the pixel in the image.

### Claim 19 (depends on 14)

The system of claim 14, wherein the processor is further configured to:
determine a strength of a bond between one or more palettes; and
sort the one or more palettes based at least in part on the strength of the bond.

### Claim 20

A system, comprising:
a processor configured to compress an image, wherein compressing the image comprises:
assigning each pixel of the image to a cluster based on a red-green-blue (RGB) location of the pixel;
updating a centroid of the cluster after each pixel is assigned, based at least in part on the RGB location of the pixel, wherein the centroid is an RGB location;
replacing each pixel in the image with an RGB value of the centroid of the cluster to which the pixel is assigned; and
instructing a display to display a compressed image, wherein in the compressed image each pixel in the image is replaced with the RGB value of the centroid of the cluster to which the pixel is assigned.
