Patent ID: 7454084

Claim:
A method of transforming a digital image signal using a factored linear transformation matrix, wherein the method includes generating matrix factors for a finite-dimensional linear transform using a computer, each matrix factor represented by a symbol, the finite-dimensional linear transform represented by data values stored in a linear transformation matrix A having a nonzero determinant, the method comprising: applying a first LU-decomposition to the linear transformation matrix A ; generating four matrices from the LU-decomposition of the linear transformation matrix A , the four matrices represented by the symbols {tilde over (Π)}, {tilde over (Π)} 2 , {tilde over (L)}, and {tilde over (D)}Ũ and satisfying the relationship {tilde over (Π)}A {tilde over (Π)} 2 ={tilde over (L)}{tilde over (D)}Ũ, the symbol {tilde over (Π)} representing a first permutation matrix, the symbol {tilde over (Π)} 2 representing a second permutation matrix, the symbol {tilde over (L)} representing a lower triangular matrix having a unit diagonal, and the symbol {tilde over (D)}Ũ representing a first upper triangular matrix; generating a third matrix represented by the symbol Â from the linear transformation matrix A, the third matrix having a plurality of rows and a determinant of 1; computing a signed permutation matrix Π from the linear transformation matrix A and the third matrix Â such that A=ΠÂ; generating a permuted linear transformation matrix represented by the symbol A′ from the linear transformation matrix, the permuted linear transformation A′ having a determinant of 1; computing a second upper triangular matrix represented by the symbol U 1 from the permuted linear transformation matrix A′ and the third matrix Â , the second upper triangular matrix U 1 having a plurality of rows, all diagonal entries equal to 1, and all entries below a first row equal to 0, the second upper triangular matrix U 1 satisfying the relationship Â^=U 1 A′; factoring the permuted linear transformation A′ matrix into a product including a lower triangular matrix and an upper triangular matrix, the lower triangular matrix and the upper triangular matrix each having a unit diagonal, the lower triangular matrix represented by the symbol L and the upper triangular matrix represented by the symbol U; generating the matrix factors for the linear transformation matrix A, the matrix factors including at least the lower triangular matrix L, the upper triangular matrix U, the second upper triangular matrix U 1, and the signed permutation matrix Π, the linear transformation matrix A expressed as a product of the matrix factors; and transforming the digital image signal by applying the linear transform to the digital signal using the matrix factors generated by the computer.