# US 2012/0251013 A1 · Method for Compressing Textured Images

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

- Number: US 2012/0251013 A1
- Document ID: US20120251013A1
- Status: Published application
- Kind: A1
- Application number: 13/076,522
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Mitsubishi Electric Research Laboratories, Inc.
- Inventors: Fatih Porikli
- Web page: https://patentgrep.com/patent/US20120251013A1

## CPC

- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H04N 19/85: using pre-processing or post-processing specially adapted for video compression
- H04N 19/97: Matching pursuit coding
- 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)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method compresses an image partitioned into blocks of pixels, for each block the method converts the block to a 2D matrix. The matrix is decomposing into a column matrix and a row matrix, wherein a width of the column matrix is substantially smaller than a height of the column matrix and the height of the row matrix is substantially smaller than the width of the row matrix. The column matrix and the row matrix are compressed, and the compressed matrices are then combined to form a compressed image.

## Claims

### Claim 1

A method for compressing an image partitioned into blocks of pixels, for each block comprising the steps of:
converting the block to a 2D matrix;
decomposing the matrix into a column matrix and a row matrix, wherein a width of the column matrix is substantially smaller than a height of the column matrix and the height of the row matrix is substantially smaller than the width of the row matrix;
compressing the column matrix and the row matrix to produce corresponding compressed columns matrix and compressed row matrix; and,
combining the compressed column matrix and the compressed row matrix to form a compressed image, wherein the steps are performed in a processor.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
partitioning the 2D matrix into a low-rank term and a sparse error term by applying principal component analysis.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
removing variability among similar regions in the matrix.

### Claim 4 (depends on 1)

The method of claim 1, wherein the decomposing is a singular value decomposition (SVD).

### Claim 5 (depends on 1)

The method of claim 1, wherein the decomposing is a k-means singular value decomposition (K-SVD).

### Claim 6 (depends on 4)

The method of claim 4, wherein the image is Y, the column matrix is D, and the row matrix is X, and wherein the decomposing minimizes a residual error ∥Y−DA∥2F where F is a Frobenius norm.

### Claim 7 (depends on 5)

The method of claim 5, wherein the image is Y, the column matrix is D, and the row matrix is X, and wherein the decomposing minimizes a residual error min∥Y−DX∥2F, such that |xi∥≦S for all i, where xi indicates an ith column of X, and S is a sparsity constraint, such that S≦K, and where F is a Frobenius norm.

### Claim 8 (depends on 7)

The method of claim 7, wherein the K-SVD uses a matching pursuit process.

### Claim 9 (depends on 7)

The method of claim 7, wherein the K-SVD alternates between sparse encoding and codebook update until convergence or a termination condition is reached.

### Claim 10 (depends on 9)

The method of claim 9, wherein the sparse encoding stage determines vectors xi for each pixel y, by minimizing the residual min ∥yi−Dxi∥2xi, subject to ∥xi∥≦S.

### Claim 11 (depends on 10)

The method of claim 10, wherein the codebook update each column k in D by defining a group of pixels that use an element wk, and further comprising:
determining an overall representation error matrix Ek by
E
k
=
Y
-
∑
j
≠
k


d
j

x
j
;
and
restricting Ek by only selecting the columns corresponding to wk and obtain ERk, and applying the SVD decomposition ERk=UΣV* to select the updated column matrix column to be a first column of U, and coefficient vector XkR to be the first column of V multiplied by Σ1,1.

### Claim 12 (depends on 2)

The method of claim 2, further comprising:
separating the low-rank term and the sparse error terms using a Lagrangian multiplier.

### Claim 13 (depends on 1)

The method of claim 1, wherein the image is of a façade of a building with multiple floor, and further comprising:
reducing the column matrix to a single-floor column matrix by identifying a periodicity of floors in the building.

### Claim 14 (depends on 1)

The method of claim 1, further comprising:
decompressing the compressed image by decoding the compressed column matrix and the compressed row matrix, and multiplying the decoded column matrix by the decoded row matrix.

### Claim 15 (depends on 1)

The method of claim 1, wherein the block of pixels corresponds to the entire image.

### Claim 16 (depends on 1)

The method of claim 1, further comprising:
clustering the rows of the column matrix using a target bit-rate and a target quality parameter.

### Claim 17 (depends on 1)

The method of claim 1, further comprising:
finding the smallest dominant frequency for the column matrix by Fourier transform;
selecting a submatrix of the column matrix according to the smallest dominant frequency for compressing the column matrix; and
repeating the submatrix to reconstruct the column matrix in the decompression.

### Claim 18 (depends on 1)

The method of claim 1, further comprising:
partitioning the 2D matrix into 1D vectors;
applying a 1D transform to 1D vectors to obtain transform coefficients and ordering the transform coefficients with respect to their values; and,
selecting the highest values transform coefficients for further compression.

### Claim 19 (depends on 18)

The method of claim 18, wherein the 1D transform is a wavelet transform.

### Claim 20 (depends on 18)

The method of claim 18, wherein the 1D transform is a discrete cosine transform.

### Claim 21 (depends on 1)

The method of claim 1, further comprising:
compressing the column matrix and row matrix by entropy coding.

### Claim 22 (depends on 1)

The method of claim 1, further comprising:
applying a spatial transform to the input image in a preprocessing stage to obtain an image with vertical and horizontal patterns.

### Claim 23 (depends on 22)

The method of claim 22, wherein the spatial transform maps pixels in polar coordinates to Cartesian coordinates for input image with circular patterns.

### Claim 24 (depends on 1)

The method of claim 1, wherein the image is a multi-spectral image and the 2D matrix conversion maps each channel into a separate 2D matrix.

### Claim 25 (depends on 1)

The method of claim 1, wherein the image is a multi-spectral image and the 2D matrix conversion maps all channels into a single 2D matrix.

### Claim 26 (depends on 1)

The method of claim 1, further comprising:
determining a diffusion matrix between the column matrix and row matrix wherein a width of the column matrix is smaller than a width of the column matrix without a diffusion matrix and a height of the row matrix is smaller than the height of the row matrix without a diffusion matrix; and
compressing the diffusion matrix.

### Claim 27 (depends on 1)

The method of claim 1, wherein the decomposing is a rank factorization.

### Claim 28 (depends on 1)

The method of claim 1, wherein the decomposing is a non-negative matrix factorization.
