Faster transforms using early aborts and precision refinements
View Patent ↗Fast transforms that use early aborts and precision refinements are disclosed. When to perform a corrective action is detected based upon testing the incremental calculations of transform coefficients. Corrective action is then performed. The corrective action includes refining the incremental calculations to obtain additional precision and/or aborting the incremental calculations when the resulting numbers are sufficient.
1. A data compression system, the data compression system comprising a transformer for applying a linear analysis transform to decorrelate data into transform coefficients using transform equations, the transformer reducing errors of the transform by testing at least one number resulting from an incremental calculation of transform coefficients during a transform, determining whether to perform a corrective action based upon the testing and performing the corrective action when a corrective action is determined to be needed.
2. The data compression system of claim 1 further comprising a quantizer for quantizing the transformed data into quantized data to reduce a number of bits needed to represent the transform coefficients.
3. The data compression system of claim 1 wherein the transformer determines whether to perform a corrective action by detecting whether the incremental calculation of the transform coefficients will result in transform coefficients with unacceptable precision and performs corrective action by refining the at least one number.
4. The data compression system of claim 3 wherein the transform comprises a transform matrix and wherein the transformer refines the at least one number by applying a refinement matrix for increasing precision of the incremental calculation of the transform constants.
5. The data compression system of claim 4 wherein the refinement matrix comprises I+ d D m+1 D m −1 .
6. The data compression system of claim 4 wherein the refinement matrix is based on approximately calculated transform constants.
7. The data compression system of claim 6 wherein the refinement matrix is generated offline or at initialization.
8. The data compression system of claim 5 wherein the refinement matrix is generated by recognizing that an approximate transform is invertible, generating the refinement matrix given by I+ d D m+1 D m −1 , and structuring the transform for efficient computation.
9. The data compression system of claim 5 wherein the refinement matrix is generated by recognizing that recovery of the nth column of a transform matrix for generating the transform is impossible, calculating a pseudo inverse for a portion of the transform matrix and generating an approximation for the refinement matrix using the pseudo inverse for the transform matrix.
10. The data compression system of claim 9 wherein the approximation of the refinement matrix comprises I+ d D 1d {tilde over (D)} 0 .
11. The data compression system of claim 1 wherein the transformer determines whether to perform a corrective action by determining whether an error resulting from terminating the incremental calculation is acceptable and performs corrective action by aborting the incremental calculation of a transform coefficient.
12. The data compression system of claim 11 wherein the transformer terminates the incremental calculation when a determination is made that the incremental calculation will result in a number that is projected to be within a predetermined range.
13. The data compression system of claim 12 wherein the number that is projected to be within a predetermined range comprises a transform coefficient that does satisfy a precision requirement.
14. The data compression system of claim 12 wherein the transformer terminates the incremental calculation when a refinement to the transform coefficient is determined not to change the result.
15. The data compression system of claim 14 wherein the transformer determines that a refinement to the transform coefficient will not change the result when, after checking the relative magnitudes of the results of the incremental calculations, an intermediate calculation of at least one transform coefficient is small compared to the intermediate calculation of another transform coefficient.
16. The data compression system of claim 14 wherein the transformer determines that a refinement to the transform coefficient will not change the result when, after checking the magnitude of the results of at least one incremental calculation, at least one intermediate calculation of the transform coefficient is less than a predetermined threshold.
17. The data compression system of claim 1 wherein the transformer determines that a corrective action is to be determined by determining that a transform coefficient is going to be within a predetermined range of zero and performs corrective action by aborting the incremental calculation of the transform coefficient.