Lizardtech, Inc.

Celartem, Inc.

Randall L Dougherty

Vance Faber

A method of generating a sequence of matrix factors for a transformation matrix having a plurality of rows and columns using a computer, wherein the transformation matrix stores data values representing a wavelet transform. In a first aspect, at least one plurality of row reduction operations are applied to the transformation matrix. The sequence of matrix factors is generated from the reduced transformation matrix and the row reduction operations. A scaling factor may be removed from the transformation matrix before applying the row reduction operations, wherein the scaled transformation matrix has a determinant with a coefficient equal to 1 or &#x2212;1. In yet another aspect, the transformation matrix may have a nonzero monomial determinant and the sequence of matrix factors further includes a scaling matrix. The method may include further alternative features described herein.

Method of generating a sequence of matrix factors for a transformation matrix

A method of generating matrix factors for a finite-dimensional linear transform using a computer. The linear transform is represented by data values stored in a linear transformation matrix having a nonzero determinant. In one aspect, a first LU-decomposition is applied to the linear transformation matrix. Four matrices are generated from the LU-decomposition, including a first permutation matrix, a second permutation matrix, a lower triangular matrix having a unit diagonal, and a first upper triangular matrix. Additional elements include a third matrix &#xc2;, a signed permutation matrix &#x3a0; such that A=&#x3a0;&#xc2;, a permuted linear transformation matrix A', a second upper triangular matrix U, wherein the second upper triangular matrix satisfies the relationship &#xc2;=UA&#x2032;. The permuted linear transformation matrix is factored into a product including a lower triangular matrix L and an upper triangular matrix U. The linear transformation matrix is expressed as a product of the matrix factors.

Method of generating matrix factors for a finite-dimensional linear transform

A method for generating a first plurality of output data values and the matrix factors used to generate an approximation to an image processing transform is disclosed. The first plurality of output data values are generated by transforming a plurality of input data values using a computer and applying a modified transform stored in a modified transformation matrix to the plurality of input data values. The plurality of input data values are stored in a generated matrix, and at least one data value in this matrix is rearranged using a permutation operation and modified by applying a linear combination of the unmodified values to the at least one data value. The modified transform is an approximation to a known transform stored in a transformation matrix that is used to generate a second plurality of output data values, the first plurality of output values approximating the second plurality of output data values. The modified transformation matrix is generated from a plurality of matrix factors that are generated by factoring the transformation matrix. The known transform and the modified transform approximating the known transform map the same integer data in the plurality of input data values to the same plurality of integer output data values.

Growing community of inventors

Seattle, WA, United States of America

Randall L Dougherty