Ordered data compression system and methods

• US 20050265618A1
• Filed: 05/18/2005
• Published: 12/01/2005
• Est. Priority Date: 12/26/2002
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Jebara, Tony
• Granted Patent: US 7,788,191 B2
• Time in Patent Office: Days
• US Class Current: 382/243
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: 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
• CPC Class Codes: G06T 9/002 using neural networks
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/169 Holistic features and representations, i.e. based on the facial image taken as a whole
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

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.

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.

2. The method of claim 1, wherein the given data type comprises dawn represented by ordered n-tuples, and wherein associating a transformation operator variable comprises associating a permutation operator that reorders the ordering of n-tuples in the datum

3. The method of claim 2, further comprises approximating the permutation operator by a doubly-stochastic matrix.

4. The method of claim 1 wherein defining a convex cost function comprises defining the convex cost function as a Gaussian maximum likelihood function.

5. The method of claim 1 wherein the Gaussian maximum likelihood function is a Gaussian mean estimator.

6. The method of claim 1 wherein the Gaussian maximum likelihood function is a Gaussian covariance mean estimator.

7. The method of claim 1 wherein defining a convex cost function comprises associating a penalty function to each transformation operator variable.

8. The method of claim 1 wherein defining a convex cost unction comprises associating a penalty function with the transformation operator variables.

9. The method of claim 1 wherein minimizing the cost function over the constrained space of transformation operator variables comprises using a convex programming technique.

10. The method of claim 9 wherein the convex programming technique is an axis-parallel optimization technique.

11. The method of claim 1 wherein using the invariantly transformed data values in the linear subspace as a set of training data to train a model, comprises performing principal components analysis (PCA) to identify a number N of significant eigenvectors spanning the linear subspace.

12. The method of claim 11 wherein using the data model comprises using the set of N eigenvectors as a basis to encode the invariantly transformed subject datum, and wherein the set of coefficients is a set of eigenvalues.

13. The method of claim 1 wherein invariantly transforming the subject datum in to the linear subspace as an invariantly transformed subject datum value comprises perturbatively reminimizing the cost function with respect to a transformation operator variable associated with the subject datum.

14. The method of claim 1, further comprising transmitting the set of coefficients to a receiver.

15. The method of claim 14, other comprising:

providing the receiver with the data model; and

using the transmitting set of coefficients and the data model to reconstruct the subject datum.

16. The method of claim 1 wherein the subject datum comprises datum of the type selected from video, audio, time sequences, any data represented by ordered n-tuples, and any combination thereof.

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=(x₁, . . . x_t), 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.

18. The method of claim 17 wherein minimizing the convex cost function comprises minimizing the convex cost function iteratively using a variational upper bound on the cost function.

19. The method of claim 18 wherein the variational upper bound on the cost function is selected such that the minimization of the cost function is one of a quadratic cost, quadratic assignment problem or a linear assignment problem.

20. The method of claim 18 wherein minimizing the cost function comprises using one of quadratic programming, axis-parallel optimization, Procrustes approaches, singular value decomposition, Kuhn-Munkres algorithms, and any combination thereof.

21. The method of claim 17 wherein encoding data designated for compression comprises first invariantly transforming the designated data into the linear subspace and then representing the data as a set of N eigenvalues.

22. The method of claim 21, further comprising reconstructing data in a vector representation from the set of N eigenvalues by linear combination of the eigenvectors.

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=(x₁, . . . x_t), wherein each vector x_i 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,

24. The system of claim 23 wherein the processor comprises a convex program for minimizing the cost function over the constrained range of allowed permutations

25. The system of claim 24 wherein the convex program comprises an iterative program and a variational upper bound on the cost function.

26. The system of claim 25 wherein the variational upper bound is such that the minimization of the cost function maps to one of a quadratic cost, a quadratic assignment problem and a linear assignment problem.

27. The system of claim 25 wherein the iterative program comprises one of a quadratic program a Prosecutes approach program, a singular value decomposition program, an axis-parallel optimization program, a Kuhn-Munkres algorithm and any combination thereof

28. A transmitter for transmitting data compressed by the system of claim 23 to a receiver.

29. A receiver comprising a reconstruction unit for decoding data compressed by the system of claim 23, wherein the reconstruction unit uses the set of N eigenvectors as a basis set to decode the compressed data

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.

31. The method of claim 30, wherein the given data type comprises datum represented by ordered n-tuples, and wherein associating a transformation operator variable comprises associating a permutation operator that reorders the ordering of n-tuples in the datum.

32. The method of claim 31, further comprising approximating the transformation operator by a doubly-stochastic matrix.

33. The method of claim 30 wherein the statistical model is a Gaussian resulting in a convex cost function namely a Gaussian maximum likelihood function.

34. The method of claim 33 wherein the Gaussian maximum likelihood function is a Gaussian mean estimator.

35. The method of claim 33 wherein the Gaussian maximum likelihood function is a kernelized Gaussian mean estimator or a Gaussian mean estimator in a higher dimension space of features.

36. The method of claim 33 wherein the Gaussian maximum likelihood function is a Gaussian covariance and a Gaussian mean estimator.

37. The method of claim 33 wherein defining a convex cost function comprises associating a penalty function to each transformation operator variable to discourage certain transformations over others.

38. The method of claim 30 wherein step (iii) involves a singular value decomposition to estimate the parameters of the statistical model.

39. The method of claim 30 where step (iv) involves the Kuhn-Munkres algorithm, linear assignment programs, or quadratic assignment prod to compute a maximum likelihood transformation and permutation operator for each datum.

40. The method of claim 30 wherein step (iii) and step (iv) involve mi g a cost function over the constrained space of transformation operator variables using a convex programming technique.

41. The method of claim 40 wherein the convex programing technique is an axis-parallel optimization technique.

42. The method of claim 30 wherein using the final statistical model involves principal components analysis (PCA) using a singular value decomposition of the transformed data to identify a number N of significant eigenvectors spanning the transformed sample training data

43. The method of claim 42 wherein using the statisctical model comprises using the set of N eigenvectors as a basis to encode the invariantly transformed subject datum, and wherein the set of coefficients represent the scaling of the eigenvectors.

44. The method of claim 30 wherein invariantly transforming the subject datum in to the linear subspace as an invariantly transformed subject datum value comprises perturbatively reminimizing the maximum likelihood cost function with respect to a transformation operator variable associated with the subject data.

45. The method of claim 30, finer comprising transmitting the set of coefficients to a receiver.

46. The method of claim 45, further comprising:

providing the receiver with the data model; and

using the transmitting set of coefficients and the data model to reconstruct the subject datum.

47. The method of claim 30 wherein the subject datum comprises datum of the type selected from video, audio, time sequences, any data represented by ordered n-tuples, and any combination thereof.

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=(x₁, . . . x_t), 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.

49. The method of claim 48 wherein minimizing the convex cost function comprises minimizing the convex cost function iteratively using a variational upper bound on the cost function.

50. The method of claim 49 wherein the variational upper bond on the cost function is selected such that the minimization of the cost function is one of a quadratic cost, quadratic assignment problem or a linear assignment problem.

51. The method of claim 50 wherein minimizing the cost function comprises using one of quadratic programming, axis-parallel optimization, Procrustes approaches, singular value decomposition, Kuhn-Munkres algorithms, and any combination thereof.

52. The method of claim 50 wherein encoding data designated for compression comprises first invariantly transforming the designated data into the linear subspace and then representing the data as a set of N coefficients.

53. The method of claim 50, further comprising reconstructing data in a vector representation from the set of N eigenvalues by linear combination of the eigenvectors.