Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-05-25
2004-08-10
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Transform coding
C382S239000, C382S240000
Reexamination Certificate
active
06775415
ABSTRACT:
FIELD OF THE INVENTION
This invention generally relates to the field of image compression. More specifically, the present invention relates to fractal image compression using a reinforcement learning algorithm.
BACKGROUND OF THE INVENTION
Images can occupy a vast amount of storage space when represented in digital form. However, representing images and other information digitally has many advantages including robustness. Digital representation of information may be stored and recovered, transmitted and received, processed and manipulated, all virtually without error. Communications are converting to digital at an impressive rate. Telephone transmissions, fax transmissions, and multimedia content are mostly communicated in digital form. Digital content integrated with computers, telecommunications networks, and consumer products are now fueling the information revolution.
Because of the potential size of digital content, there has developed a need for digital compression. As a result compression has become an important area of interest. Compression may reduce disk capacity requirements for storage of digital content, and may improve transmission time for digital content in bandwidth limited applications such as web pages.
Communications channels such as the public switched telephone networks, coaxial cable networks, cellular networks, and satellite networks have a limited bitrate available. A technique to increase transmission speed is to reduce the average number of bits being transmitted, that is, to compress the digital data. To become viable, many low bitrate applications such as image retrieval on the World Wide Web require compression.
Many compression algorithms of varying complexity, quality, robustness and efficiency have been developed including fractal image compression. Fractal image compression exploits self-similarity which exists in natural images to achieve compression. Fractal image compression may require that images be partitioned into sub regions, called ranges that may each be represented as transformed copies of other sub regions called domains. Domains are typically overlapping regions and transformations are usually contractive. A domain pool is a set of domains. A search may be performed among the domains in a domain pool and among a set of function families that map image domains to image ranges to find a domain/function pair that closely matches each range within the current partition of the image. This search may be computationally expensive and as a consequence, practical fractal image compression may require that the search be constrained. What is needed is a way of improving the efficiency of fractal compression that addresses the following aspects of the compression process: image partitioning; transform family selection; and domain to range matching.
SUMMARY AND ADVANTAGES OF THE INVENTION
One advantage of the invention is that it improves fractal image compression by reducing compression time.
Another advantage of this invention is that it uses a learning algorithm to make choices between different transform families based upon local block characteristics and to rapidly partition images based upon local image characteristics.
Yet a further advantage of this invention is that it finds good domain to range block matches by combining the concept of lean domain pools, that is domain pools consisting of high variance blocks, with the concept of block classification. Lean domain pools reduce the size of the domain pool and hence may reduce search time. Block classification further reduces a search by classifying range and domain blocks and then only attempting to match domains to ranges that are in the same class as the range.
Yet a further advantage of this invention does not require a model of the environment.
Yet a further advantage of this invention is that it can be achieved with a high degree of parallelism.
To achieve the foregoing and other advantages, in accordance with all of the invention as embodied and broadly described herein, a method for coding an image 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 the image and storing the image.
In yet a further aspect of the invention, a method for coding an image wherein the step of construction a lean domain pool further includes the steps of determining the various of domain blocks in a domain pool, and eliminating low variance domain blocks from the domain pool, thereby reducing the size of said domain pool.
In yet a further aspect of the invention, a method for coding an image wherein the step of learning a Q-function further includes the steps of learning no-split decisions, and learning split decisions.
In yet a further aspect of the invention, 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 the image, and storing the image, wherein the method for decoding the image comprises the steps of iterating the transforms used in the step of compressing the image using a pyramidal scheme to produce a decoded image, and post smoothing the image to reduce perceptible line artifacts.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
REFERENCES:
patent: 5347600 (1994-09-01), Barnsley et al.
patent: 5867603 (1999-02-01), Barnsley et al.
patent: 5923376 (1999-07-01), Pullen et al.
patent: 5982441 (1999-11-01), Hurd et al.
patent: 6002794 (1999-12-01), Bonneau et al.
“Fractal Image Compression Using Quad-Q-Learning,” Ph.D. dissertation, George Mason University, Nov. 13, 1998, pag 122-178.*
“Lean domain pools for fractal image compression,” D. Saupe, Journal of Electronic Imaging, 8(1), Jan., 1999, pp. 99-103.*
“A quadtree classified-based fractal image coding approach,” Wang et al., Fifth Asia-Pacific Conference on Communication an Fourth Optoelectronics and Communications Conference, vol. 2, Oct. 18-22, 1999, pp. 912-915.
Clausen Clifford
Wechsler Harry
Chen Wenpeng
George Mason University
Grossman David G.
Lebovitz Richard
LandOfFree
Fractal image compression using reinforcement learning does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fractal image compression using reinforcement learning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fractal image compression using reinforcement learning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3322036