Fractal image compression using reinforcement learning

• US 6,775,415 B1
• Filed: 05/25/2000
• Issued: 08/10/2004
• Est. Priority Date: 05/25/1999
• Status: Expired due to Term

• Current Assignee: George Mason Intellectual Properties, Inc.
• Original Assignee: George Mason University
• Inventors: Wechsler, Harry, Clausen, Clifford
• Primary Examiner(s): Chen, Wenpeng
• Application Number:
  US09/577,949
• Time in Patent Office: 1,538 Days
• Field of Search: 382/249, 382/233, 382/232, 382/248, 382/235, 382/166, 382/240, 382/239
• US Class Current: 382/249
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

A method for fractal image compression using reinforced learning is disclosed. The reinforced learning algorithm improves the performance of fractal image compression algorithms by improving image partitioning and transform family selection while considering the impact of domain to range matching. The present invention differs from other fractal image compression algorithms in that it makes decisions about transform family and image partitioning by generalizing from experience compressing small portions of an image to compressing an image as a whole.

Claims

1. A method for coding an image comprising the steps of:

(a) pre-smoothing said image;

(b) constructing a lean domain pool;

(c) classifying domain blocks in the lean domain pool;

(d) learning a Q-function;

(e) compressing said image; and

(f) storing said image.

2. The method according to claim 1, wherein said step of pre-smoothing said image consists of using a low pass filter to remove high frequency content.

3. The method according to claim 1, wherein said step of constructing a lean domain pool further includes the steps of:

(a) determining the variance of each domain block in a domain pool; and

(b) eliminating low variance domain blocks from the domain pool;

thereby reducing the size of said domain pool.

4. The method according to claim 1, wherein said step of classifying domain blocks in the lean domain pool includes assigning classifications to said domain blocks determined by sub block averages and variances.

5. The method according to claim 1, wherein said step of classifying domain blocks in the lean domain pool includes classifying said domain blocks in the lean domain pool according to difference ordinals of block quadrant averages.

6. The method according to claim 1, wherein said step of learning a Q-function further includes the steps of:

(a) determining how to partition said image into range blocks; and

(b) determining a fractal transform to use to code a range block based upon local characteristics of the range block.

7. The method according to claim 1, wherein said step of learning a Q-function further includes the steps of:

(a) learning no-split decisions; and

(b) learning split decisions.

8. The method according to claim 7, wherein said step of learning no-split decisions further includes the steps of:

(a) calculating range block attribute vectors;

(b) calculating quality and compression cost of coding the range block with Bath and affine transform types; and

(c) updating Q function quality and compression cost estimates for Bath and affine transform types based upon a range block attribute vector calculation.

9. The method according to claim 7, wherein said step of learning split decisions further includes the steps:

(a) calculating range block attribute vectors and calculating attribute vectors for each quadrant block; and

(b) updating Q-function quality and compression cost estimates for Bath and affine transform actions based upon range block attribute vector and quadrant attribute vector calculations.

10. The method according to claim 1, wherein said step of compressing said image includes using fractal image compression to compress said image.

11. The method according to claim 1, wherein said step of compressing said image further comprises the steps of:

(a) using the Q-function to determine an expected quality cost of a Bath no-split decision, an affine no-split decision, a Bath split decision and an affine split decision;

(b) using the Q-function in the case of split decisions to determine when to stop block splitting;

(c) using the Q-function compression cost estimate to decide among multiple acceptable decisions made based upon quality cost estimate; and

(d) matching range blocks to a domain block by classifying the range block and assaying candidates from the lean domain pool that are of the same class.

12. The method according to claim 11, wherein said step of matching range blocks to a domain block further consists of the step of in the case of a Bath transform, classifying the residual of the range block and a functional approximation of the range block instead of classifying the range block.

13. The method according to claim 1, wherein said step of compressing said image includes the steps of:

(a) calculating expected RMS values from block splitting for a multitude of transforms;

(b) selecting a transform from said multitude of transforms with the lowest RMS value, if all said multitude of transforms failed to achieve a desired RMS value; and

(c) selecting a transform from said multitude of transforms that has the minimum bit rate, if all said multitude of transforms achieved a desired RMS value.

14. The method according to claim 1, wherein said step of compressing said image further includes the steps of:

(a) determining if a block is of smallest size;

(b) calculating the variance of said block;

(c) estimating the image quality cost of coding said block directly; and

(d) if said block is not of a smallest size and if said calculated cost is less than a predetermined cost threshold, splitting said block.

15. The method according to claim 1, wherein said step of storing an image further includes the steps of:

(a) storing image header information including a minimum range block size, a maximum range block size, an image size, and lean domain pool index to location information; and

(b) storing transform information including transform family information and adaptive Huffman coded transform parameter information.

18. The method according to claim 8, wherein said step of updating Q function quality and compression cost estimates for Bath and affine transform types based upon a range block attribute vector calculation includes updating Q function quality and compression cost estimates for Bath and affine transform types based upon a range block attribute vector calculation and candidate block splitting actions.

16. A method for decoding an image that was coded by a method comprising the steps of:

pre-smoothing an image;

constructing a lean domain pool;

classifying domain blocks in the lean domain pool;

learning a Q-function;

compressing said image; and

storing said image, wherein said method for decoding said image comprises the steps of;

(a) iterating transforms used in the step of compressing said image using a pyramidal scheme to produce a decoded image; and

(b) post smoothing said image to reduce perceptible line artifacts.

17. The method according to claim 16, wherein said step of post smoothing the image further includes the steps of:

(a) determining a region to filter as one fourth the dimension of a block being filtered in the direction being filtered; and

(b) calculating filtered values as weighted averages of proximate pixels along a line perpendicular to a block boundary being filtered where weights are calculated from a gaussian distribution.