Ordered data compression system and methods
First Claim
1. A method for compressing a subject datum of a given data type under a covariant invariance learning framework mi an image processing system or an image, video, and audio processing system, wherein the learning framework comprising the steps of:
- (i) establishing a data model by performing the substeps of;
assembling a set of sample data of the given data type;
associating a transformation operator variable with each datum in the set of sample data, wherein the transformation operator variable operates on the daturn to invariantly transform tie datum to a transformed datum value;
using the transformation operator variables to define an invariant manifold for each datum in the set of sample data, wherein the invariant manifold comprises the invariantly transformed datum values;
defining a convex cost function over a space of transformation operator variables associated with the data in the set of sample data;
defining a convex hull of constraints on the transformation operator variables associated with the data in the set of sample data;
minimizing the cost function over the constrained space of transformation operator variables to identify a linear subspace of the invariant manifolds of the data in the set of sample data; and
using the invariantly transformed data values in the linear subspace as a set of training data to train a data model, wherein tie data model describes the invariantly transformed data values with a limited number of parameters;
(ii) invariantly transforming the subject datum in to the linear subspace as an invariantly transformed subject datum value; and
(iii) using the data model with the limited number of parameters to encode the invariantly transformed subject datum value, whereby a set of coefficients represents the compressed subject datum.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods and systems are provided for encoding, transmission and decoding of vectorized input data, for example, video or audio data. A convex invariance learning framework is established for processing input data or a given data type. Each input vector is associated with a variable transformation matrix that acts on the vector to invariantly permute the vector elements. Joint invariance and model learning is performed on a training set of invariantly transformed vectors over a constrained space of transformation matrices using maximum likelihood analysis. The maximum likelihood analysis reduces the data volume to a linear subspace volume in which the training data can be modeled by a reduced number of variables. Principal component analysis is used to identify a set of N eigen vectors that span the linear subspace. The set of N eigenvectors is used a basis set to encode input data and to decode compressed data.
-
Citations
53 Claims
-
1. A method for compressing a subject datum of a given data type under a covariant invariance learning framework mi an image processing system or an image, video, and audio processing system, wherein the learning framework comprising the steps of:
-
(i) establishing a data model by performing the substeps of;
assembling a set of sample data of the given data type;
associating a transformation operator variable with each datum in the set of sample data, wherein the transformation operator variable operates on the daturn to invariantly transform tie datum to a transformed datum value;
using the transformation operator variables to define an invariant manifold for each datum in the set of sample data, wherein the invariant manifold comprises the invariantly transformed datum values;
defining a convex cost function over a space of transformation operator variables associated with the data in the set of sample data;
defining a convex hull of constraints on the transformation operator variables associated with the data in the set of sample data;
minimizing the cost function over the constrained space of transformation operator variables to identify a linear subspace of the invariant manifolds of the data in the set of sample data; and
using the invariantly transformed data values in the linear subspace as a set of training data to train a data model, wherein tie data model describes the invariantly transformed data values with a limited number of parameters;
(ii) invariantly transforming the subject datum in to the linear subspace as an invariantly transformed subject datum value; and
(iii) using the data model with the limited number of parameters to encode the invariantly transformed subject datum value, whereby a set of coefficients represents the compressed subject datum. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A method for compressing data that is represented by vectors x, wherein each vector is an ordered set of pixels, and wherein each pixel comprises an n-tuple, the method comprising:
-
permuting the ordering of pixels in a set of data S=(x1, . . . xt), over a range of permutations to obtain a bag of unordered pixels representing the data, wherein the range of allowed permutations is linearly constrained, associating a convex cost function with the permutations, wherein the cost function is derived by modeling data as a Gaussian distribution and identified as the determinant of a regularized covariance of the data minimizing the convex cost function over the constrained range of permutations to identify a linear subspace of the bag of pixels, wherein the linear subspace corresponds to the most likely invariant ordering of pixels in the set of data S;
performing PCA to identify a set of N of eigenvectors that span the linear subspace; and
encoding a datum designated for compression using the set of N eigenvectors to represent the datum as a set of corresponding N coefficients in the eigenspace. - View Dependent Claims (18, 19, 20, 21, 22)
-
-
23. A system for compressing data that is represented by vectors x, wherein each vector is an ordered set of pixels, and wherein each pixel comprises an n-tuple, the system comprising
a set of sample data S=(x1, . . . xt), wherein each vector xi is associated with a variable permutation operator that permutes the ordering of the pixels in the vector, wherein the data in set S is a associated with a convex cost function which estimates the cost of permuting the ordering of pixels in S to obtain a bag of unordered pixels representing the data, wherein the range of allowed permutations is linearly constrained, and wherein the cost function is statistically defined as a detest of a covariance of the data; -
a processor for minimizing the convex cost fiction over the constrained range of allowed permutations to identify a linear subspace of the bag of pixels, wherein tee linear subspace corresponds to the most likely invariant ordering of pixels in the set of data S;
a principal components analyzer for identifying a set of N of eigenvectors that span the linear subspace; and
an encoder that compresses data by using the set of N eigenvectors as a basis set to encode tee data, - View Dependent Claims (24, 25, 26, 27, 28, 29)
-
-
30. A method for compressing a subject datum of a given data type for image and audio processing in a way that is invariant to natural transformations and permutations the datum can exhibit, wherein the data type is a vector, image, audio clip or sequence, the method comprising the steps of:
-
(i) assembling a set of sample training data of the given type;
(ii) selecting a classical statistical model such as a Gaussian, principal components analysis, multinomial, or support vector machine for modeling the sample training data, (iii) estimating the parameters of the statistical model with maximum likelihood or standard estimators to fit the sample data;
(iv) improving the estimated model'"'"'s fit or its likelihood by associating a transformation operator variable with each datum in the set of sample data and adjusting the transformation operator to further improve the likelihood for each datum in the sample data;
(v) repeating steps (iii) and (iv) until the model fit or likelihood ceases to improve and finally locking the model parameters. (vi) associating with the subject datum a transformation operator variable and adjusting to improve its likelihood under the final locked model parameters;
(vii) using the final statistical model to encode the invariantly transformed subject datum, whereby a set of coefficients compactly represents the compressed subject datum while being invariant to the transformations and permutations it can undergo. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47)
-
-
48. A method for compressing data for image processing and transmission, wherein the data is represented by vectors x, wherein each vector is a set of arbitrarily ordered pixels, and wherein each pixel comprises au n-tuple containing coordinate and color information, the method comprising:
-
permuting the ordering of pixels in a set of data S=(x1, . . . xt), over a range of permutations to obtain a bag of ordered pixels representing the data;
associating a convex cost function with the permutations, wherein the cost function is derived by modeling data as a Gaussian distribution and identified as the determinant of a regularized covariance of tile data. minimizing the convex cost function over the constrained range of permutations to identify a linear subspace of the bag of pixels, wherein the linear subspace corresponds to the most likely invariant ordering of pixels in the set of data S;
performing PCA to identify a set of N of eigenvectors that span the linear subspace of the training data; and
encoding a datum designated for compression using the set of N eigenvectors to represent the datum as a set of corresponding N coefficients in the eigenspace. - View Dependent Claims (49, 50, 51, 52, 53)
-
Specification