Region-based karhunen-loeve transformation Number:7,187,798 from the United States Patent and Trademark Office (PTO) owispatent

Title: Region-based karhunen-loeve transformation

Abstract: A region-based Karhunen-Loeve transformational method for compressing a color image. The method includes the steps of converting color image information for the color image into partitioned intrinsic color information, transforming the partitioned intrinsic color information into transformed information, and quantizing the transformed information into quantized information. The method further includes the steps of encoding the quantized information into encoded information, and storing the encoded information.

Patent Number: 7,187,798 Issued on 03/06/2007 to Payton

---

Inventors:	Payton; Paul M. (Burlingame, CA)
Assignee:	Lockheed Martin Corporation (Bethesda, MD)
Appl. No.:	10/985,999
Filed:	November 12, 2004

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	10870422	Jun., 2004
	09625859	Jun., 2004	6754383

---

Current U.S. Class:	382/166
Current International Class:	G06K 9/00 (20060101); G06K 9/36 (20060101)
Field of Search:	382/162,166,232,233,240,244,248,250,251 358/523,525 348/224.1,333.03 345/600-604,619 375/240.03,240.11,240.18,240.19,240.2

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5014198		May 1991		Umemura
	5196946		March 1993		Balkanski et al.
	5253078		October 1993		Balkanski et al.
	5422736		June 1995		Katayama
	5465164		November 1995		Sugiura et al.
	5680129		October 1997		Weinberger et al.
	5798753		August 1998		Zhou et al.
	5982432		November 1999		Uenoyama et al.
	6049775		April 2000		Gertner et al.
	6125201		September 2000		Zador
	6157734		December 2000		Iida
	6195466		February 2001		Schwartz et al.
	6236749		May 2001		Satonaka et al.
	6259741		July 2001		Chen et al.
	6266440		July 2001		Oneda
	6308193		October 2001		Jang et al.
	6320981		November 2001		Yada
	6404928		June 2002		Shaw et al.
	6427029		July 2002		Kono et al.
	6453072		September 2002		Hatakenaka
	6453073		September 2002		Johnson
	6584232		June 2003		Kobayashi
	6597815		July 2003		Satoh et al.
	6665446		December 2003		Kato
	6754383		June 2004		Payton
	6832006		December 2004		Savakis et al.
	6868190		March 2005		Morton
	6891975		May 2005		Okada
	6917384		July 2005		Fukushima
	2003/0016233		January 2003		Charpentier
	2003/0174896		September 2003		Ridge
	2004/0212692		October 2004		Nakami et al.
	2004/0258301		December 2004		Payton

Other References

"ERDAS Field Guide, Fifth Edition, Revised and Expanded", 1999, pp. 238-466, ERDAS, Inc., Atlanta, Georgia. cited by other . European Search Report dated Mar. 18, 2005, in EP 01850124.7. cited by oth- er . "Three-Dimensional Transform Coding Of Multispectral Data", by John A. Saghri, et al., 1993 IEEE, pp. 1342-1346. cited by other . "Terrain-Adaptive Transform Coding Of Multispectral Data", by John A. Saghri, et al., 1994 IEEE, pp. 313-316. cited by other . "Coding Of Spectrally Homogenous Regions In Multispectral Image Compression", by Gabriel Fernandez, et al., 1996 IEEE, pp. 923-926. cited by other . "An Efficient Adaptive KLT For Multispectral Image Compression", by Lena Chang, et al., 2000 IEEE, pp. 252-255. cited by other.

Primary Examiner: Alavi; Amir
Attorney, Agent or Firm: McDermott Will & Emery LLP.

---

Parent Case Text

---

CROSS-REFERENCE

This application is a continuation-in-part application of U.S. patent application Ser. No. 10/870,422, filed Jun. 18, 2004, which is a continuation of U.S. patent application Ser. No. 09/625,859, filed Jul. 26, 2000 (issued as U.S. Pat. No. 6,754,383 on Jun. 22, 2004), both of which are incorporated herein for all purposes.

---

Claims

---

What is claimed is:

1. A computer-readable storage medium in which is stored a program for compressing a color image, the program comprising codes for permitting a computer to perform: a converting step for converting color image information for the color image into partitioned intrinsic color information; a transforming step for transforming the partitioned intrinsic color information into transformed information; a quantizing step for quantizing the transformed information into quantized information; an encoding step for encoding the quantized information into encoded information; and a storing step for storing the encoded information.

2. The computer-readable storage medium according to claim 1, wherein, during the converting step, the program further comprises codes for permitting the computer to perform: a partitioning step for partitioning the color image information into a plurality of regions, including at least first and second adjacent regions; a first computing step for computing a mean vector and a covariance matrix for each of the plurality of regions; a second computing step for computing divergence D.sub.ij, transformed divergence TD.sub.ij, and/or Jeffries-Matusita distance JM.sub.ij for the first and second adjacent regions; and a merging step for merging the first and second adjacent regions, if D.sub.ij, TD.sub.ij, or JM.sub.ij indicate poor separation.

3. The computer-readable storage medium according to claim 2, wherein, during the converting step, the program further comprises codes for permitting the computer to perform: a third computing step for computing a mean vector and a covariance matrix for the merged first and second adjacent region; a fourth computing step for computing D.sub.ij, TD.sub.ij, and/or JM.sub.ij between the merged first and second adjacent region and a third adjacent region adjacent to the merged first and second adjacent region; and a second merging step for merging the merged first and second adjacent region with the third adjacent region, if D.sub.ij, TD.sub.ij, or JM.sub.ij indicate poor separation between the merged first and second adjacent region and the third adjacent region.

4. The computer-readable storage medium according to claim 2, wherein each of the plurality of regions is rectilinear.

5. The computer-readable storage medium according to claim 4, wherein each of the plurality of regions measures K pixels .times.L pixels.

6. The computer-readable storage medium according to claim 5, wherein K equals L.

7. The computer-readable storage medium according to claim 5, wherein K and/or L are 256, initially.

8. The computer-readable storage medium according to claim 5, wherein K and/or L are 512, initially.

9. The computer-readable storage medium according to claim 5, wherein K and/or L grow by multiples of 8.

10. The computer-readable storage medium according to claim 2, wherein D.sub.ij is expressed by: .times..function..times..times..function..times..mu..mu..times..mu..mu. ##EQU00007## wherein C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, tr represents a trace function, and T represents a transposition function.

11. The computer-readable storage medium according to claim 2, wherein TD.sub.ij is expressed by: .times..function..times..times..function..times..mu..mu..times..mu..mu..t- imes..function..function. ##EQU00008## wherein C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, tr represents a trace function, and T represents a transposition function.

12. The computer-readable storage medium according to claim 2, wherein JM.sub.ij is expressed by: .times..mu..mu..times..times..mu..mu..times..function..function..times..t- imes..times. ##EQU00009## wherein C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, |C.sub.i| represents a determinant of C.sub.i, and |C.sub.j| represents a determinant of C.sub.j.

13. The computer-readable storage medium according to claim 2, wherein poor separation is indicated if TD.sub.ij is between 0 and 1700.

14. The computer-readable storage medium according to claim 2, wherein poor separation is indicated if JM.sub.ij is between 0 and 1000.

15. The computer-readable storage medium according to claim 1, wherein the color image comprises greater than or equal to 4,000,000 pixels.

16. The computer-readable storage medium according to claim 1, wherein the transforming step uses a discrete cosine transform.

17. The computer-readable storage medium according to claim 16, wherein the discrete cosine transform is a JPEG discrete cosine transform.

18. The computer-readable storage medium according to claim 1, wherein the transforming step uses a discrete wavelet transform.

19. The computer-readable storage medium according to claim 18, wherein the discrete wavelet transform is a JPEG 2000 discrete wavelet transform.

20. The computer-readable storage medium according to claim 1, wherein, during the converting step, the program further comprises codes for permitting the computer to perform: an establishing step for establishing a principal components space, a generating step for generating intrinsic values, and a determining step for determining scale factors.

21. A method for compressing a color image, comprising the steps of: converting color image information for the color image into partitioned intrinsic color information; transforming the partitioned intrinsic color information into transformed information; quantizing the transformed information into quantized information; encoding the quantized information into encoded information; and storing the encoded information.

22. The method for compressing a color image according to claim 21, wherein the converting step further comprises the steps of: partitioning the color image information into a plurality of regions, including at least first and second adjacent regions; computing a mean vector and a covariance matrix for each of the plurality of regions; computing divergence D.sub.ij, transformed divergence TD.sub.ij, and/or Jeffries-Matusita distance JM.sub.ij for the first and second adjacent regions; and merging the first and second adjacent regions, if D.sub.ij, TD.sub.ij, or JM.sub.ij indicate poor separation.

23. The method for compressing a color image according to claim 22, wherein D.sub.ij is expressed by: .times..function..times..times..function..times..mu..mu..times..mu..mu. ##EQU00010## wherein C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, tr represents a trace function, and T represents a transposition function.

24. The method for compressing a color image according to claim 22, wherein TD.sub.ij is expressed by: .times..function..times..times..function..times..mu..mu..times..mu..mu..t- imes..function..function. ##EQU00011## wherein C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, tr represents a trace function, and T represents a transposition function.

25. The method for compressing a color image according to claim 22, wherein JM.sub.ij is expressed by: .times..mu..mu..times..times..mu..mu..times..function..function..times..t- imes..times. ##EQU00012## wherein C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, |C.sub.i| represents a determinant of C.sub.i, and |C.sub.j| represents a determinant of C.sub.j.

26. The method for compressing a color image according to claim 21, wherein the converting step further comprises the steps of: establishing a principal components space; generating intrinsic values; and determining scale factors.

27. A method for compressing and reconstructing a color image, comprising the steps of: converting color image information for the color image into partitioned intrinsic color information; transforming the partitioned intrinsic color information into transformed information; quantizing the transformed information into quantized information; encoding the quantized information into encoded information; storing the encoded information; and reconstructing the encoded information.

28. The method for compressing a color image according to claim 27, wherein the converting step further comprises the steps of: partitioning the color image information into a plurality of regions, including at least first and second adjacent regions; computing a mean vector and a covariance matrix for each of the plurality of regions; computing divergence D.sub.ij, transformed divergence TD.sub.ij, and/or Jeffries-Matusita distance JM.sub.ij for the first and second adjacent regions; and merging the first and second adjacent regions, if D.sub.ij, TD.sub.ij, or JM.sub.ij, indicate poor separation.

29. A system for compressing a color image, comprising: a memory for storing color image information for the color image; and a computer processor for compressing the stored color image information, by performing the steps of: a) converting color image information for the color image into partitioned intrinsic color information; b) transforming the partitioned intrinsic color information into transformed information; c) quantizing the transformed information into quantized information; d) encoding the quantized information into encoded information; and e) storing the encoded information.

30. The system for compressing a color image according to claim 29, wherein the computer processor performs the converting step by further performing the steps of: i) partitioning the color image information into a plurality of regions, including at least first and second adjacent regions; ii) computing a mean vector and a covariance matrix for each of the plurality of regions; iii) computing divergence D.sub.ij, transformed divergence TD.sub.ij, and/or Jeffries-Matusita distance JM.sub.ij for the first and second adjacent regions; and iv) merging the first and second adjacent regions, if D.sub.ij, TD.sub.ij, or JM.sub.ij indicate poor separation.

---

Description

---

STATEMENT AS TO RIGHTS TO INVENTIONS MADE UNDER FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

Not Applicable.

FIELD OF INVENTION

The present invention relates to true color image compression and reconstruction and, more particularly, relates to lossy compression and reconstruction of large color images by partitioning an image into non-overlapping regions with distinct color histograms, using an iterative region-growing algorithm.

BACKGROUND OF THE INVENTION

Short for "discrete cosine transform," a DCT is a technique for representing waveform data as a weighted sum of cosines, and is commonly used for image compression. Closely related to the discrete Fourier transform ("DFT"), discrete cosine transformations involve manipulation of real numbers only, offering energy compaction improvements over DFT by eliminating artificial discontinuities that appear in DFTs.

Similarly, discrete wavelet transforms ("DWT") are designed to decorrelate an image, decomposing an image block into several subbands, and transforming an image data signal into two or more decimated signals corresponding to different frequency bands. The subbands consist of coefficients that describe the horizontal and vertical spatial frequency characteristics of the original tile component. The DWT generally results in the signal energy being concentrated in a small number of subbands, and the subbands subsequently tend to compress more easily than the original image.

Attributed to these and other appealing qualities, DCTs and DWTs are popularly deployed in a broad class of decoding techniques, known as transform coding or block quantization, which attempt to reduce image signal redundancy by representing signals with a new set of orthogonal bases, reducing the spatial correlations that occur between adjacent pixels. Using DCTs and DWTs, merely a fraction of the transform coefficients are encoded, with tolerable deterioration in image fidelity. JPEG and JPEG 2000 are examples of well known image compression mechanisms which utilize DCT and DWT, respectively.

One problem common to conventional DCT and DWT-based image compression algorithms relates to the wide disparity in color composition found in large images, such as images measuring 2048 pixels .times.2048 pixels or larger. Widely disparate color compositions thwart DCT and DWT algorithms, which are most effective when color statistics of encoded blocks are similar. In order to reduce color composition disparity in large images, the conventional image compression algorithms partition an image into fixed blocks of N.times.N pixels, where N is either arbitrary, or based upon predetermined simulation results of other natural images.

The choice of block sizes is crucial, since the selection of too large of a block can include more than one region with different frequency properties, while the selection of too small of a block results in less efficient image compression. As such, it is a disadvantage of the conventional image compression mechanisms to choose block sizes which are not tailored to the individual images being compressed, and which do not compensate for regions of similar frequency properties. By ignoring these similar regions, conventional image compression mechanisms suffer from increased loss of coefficient magnitudes, decreased overall compression efficiency and increased time required to transmit compressed images.

It is therefore considered highly desirable to provide an enhanced mechanism for compressing images which groups regions or blocks of data with similar frequency properties, in order to increase compression efficiency. In particular, it is desirable to have an iterative region-growing algorithm for partitioned images, which grows regions based on the similarity or difference of color characteristics of non-overlapping regions of the image, resulting in more efficient block coding.

SUMMARY OF THE INVENTION

The present invention relates to true color image compression and reconstruction and, more particularly, relates to lossy compression and reconstruction of color images by partitioning an image into non-overlapping regions with distinct color histograms, using an iterative region-growing algorithm.

Based on the foregoing discussion, it can be appreciated that there presently exists a need in the art for a computer system and corresponding operating method which overcomes the above-described deficiencies of the prior art. The present invention overcomes several key shortcomings, particularly those drawbacks which relate to arbitrarily-determined, fixed block sizes used by the conventional DCT-based or DWT-based image compression mechanisms.

It is a feature and advantage of the present invention to provide an image compression and reconstruction technique that improves the image quality of a reconstructed image, by reducing image quality degradation at high compression ratios. As such, the present invention optimizes utilization of file space, and reduces the transmission time required to transmit compressed images.

It is a further feature and advantage of the invention to compress a color image, utilizing an iterative region-growing algorithm on partitioned images, which grows regions based on the similarity or difference of color characteristics of non-overlapping regions of the image, resulting in more efficient block coding.

The present invention is a system, method, and computer program product for compression and reconstruction of a color image using principal components transformation. The method, which is performed on a computer or other programmable data processing apparatus, is a variant of the conventional JPEG or JPEG 2000 image compression mechanisms.

According to one aspect, the present invention is a computer-readable storage medium in which is stored a program for compressing a color image. The program includes codes for permitting the computer to perform a converting step for converting color image information for the color image into partitioned intrinsic color information, a transforming step for transforming the partitioned intrinsic color information into transformed information, and a quantizing step for quantizing the transformed information into quantized information. The program further includes codes for permitting the computer to perform an encoding step for encoding the quantized information into encoded information, and a storing step for storing the encoded information.

During the converting step, the program further includes codes for permitting the computer to perform a partitioning step for partitioning the color image information into a plurality of regions, including at least first and second adjacent regions, a first computing step for computing a mean vector and a covariance matrix for each of the plurality of regions, and a second computing step for computing divergence D.sub.ij, transformed divergence TD.sub.ij, and/or Jeffries-Matusita distance JM.sub.ij for the first and second adjacent regions. Furthermore, during the converting step, the program also includes codes for permitting the computer to perform a merging step for merging the first and second adjacent regions, if D.sub.ij, TD.sub.ij, or JM.sub.ij indicate poor separation.

During the converting step, the program further includes codes for permitting the computer to perform a third computing step for computing a mean vector and a covariance matrix for the merged first and second adjacent region, and a fourth computing step for computing D.sub.ij, TD.sub.ij, and/or JM.sub.ij between the merged first and second adjacent region and a third adjacent region adjacent to the merged first and second adjacent region. Moreover, during the converting step, the program includes codes for permitting the computer to perform a second merging step for merging the merged first and second adjacent region with the third adjacent region, if D.sub.ij, TD.sub.ij, or JM.sub.ij indicate poor separation between the merged first and second adjacent region and the third adjacent region.

Each of the plurality of regions is rectilinear, where each of the plurality of regions measures K pixels .times.L pixels.

D.sub.ij is expressed by Equation (1), below:

.times..function..times..times..function..times..mu..mu..times..mu..mu. ##EQU00001##

In Equation (1), C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, tr represents a trace function, and T represents a transposition function.

TD.sub.ij is expressed by Equations (1) and (2), below:

.times..function..times..times..function..times..mu..mu..times..mu..mu..ti- mes..function..function. ##EQU00002##

In Equations (1) and (2), C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, tr represents a trace function, and T represents a transposition function. Furthermore, Abs( ) represents the absolute value function.

JM.sub.ij is expressed by Equations (3) and (4), below:

.times..mu..mu..times..times..mu..mu..times..function..function..times..ti- mes..times. ##EQU00003##

In Equations (3) and (4), C.sub.i represents the covariance matrix for the first region, C.sub.j represents the covariance matrix for the second region, .mu..sub.i represents the mean vector for the first region, .mu..sub.j represents the mean vector for the second region, |C.sub.i| represents a determinant of C.sub.i, and |C.sub.j| represents a determinant of C.sub.j. Additionally, Abs ( ) represents the absolute value function.

Poor separation is indicated if TD.sub.ij is between 0 and 1700, or if JM.sub.ij is between 0 and 1000. In alternate arrangements, K equals L, K and/or L are 256, or K and/or L are 512, initially. The color image comprises greater than or equal to 4,000,000 pixels.

The transforming step uses a discrete cosine transform, such as the JPEG discrete cosine transform, or a discrete wavelet transform, such as the JPEG 2000 discrete wavelet transform. During the converting step, the program further includes codes for permitting the computer to perform an establishing step for establishing a principal components space, a generating step for generating intrinsic values, and a determining step for determining scale factors.

According to a second aspect, the present invention is a method for compressing a color image. The method includes the steps of converting color image information for the color image into partitioned intrinsic color information, transforming the partitioned intrinsic color information into transformed information, and quantizing the transformed information into quantized information. The method further includes the steps of encoding the quantized information into encoded information, and storing the encoded information.

According to a third aspect, the present invention is a method for compressing and reconstructing a color image. The method includes the steps of converting color image information for the color image into partitioned intrinsic color information, transforming the partitioned intrinsic color information into transformed information, and quantizing the transformed information into quantized information. Additionally, the method includes the steps of encoding the quantized information into encoded information, storing the encoded information, and reconstructing the encoded information.

According to a fourth aspect, the present invention is a system for compressing a color image, including a memory for storing color image information for the color image, and a computer processor for compressing the stored color image information. The computer processor performs the steps of converting color image information for a color image into partitioned intrinsic color information, transforming the partitioned intrinsic color information into transformed information, and quantizing the transformed information into quantized information. The computer processor further performs the steps of encoding the quantized information into encoded information, and storing the encoded information.

The present invention optimizes channel usage, resulting in less degradation in image quality while allowing greater compression ratios over conventional, fixed transformation techniques. The present invention is particularly relevant to DCT-based or DWT-based compression techniques, since the range of compression ratios is extended, while image quality is maintained at high compression ratios.

In the following description of the preferred embodiment, reference is made to the accompanying drawings that form a part thereof, and in which is shown by way of illustration a specific embodiment in which the invention may be practiced. It is to be understood that other embodiments may be utilized and changes may be made without departing from the scope of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

FIG. 1 is a functional block diagram of a computer in which the invention of the present invention can be carried out;

FIGS. 2A and 2B depict block diagrams of the routines that implement the method of the present invention;

FIG. 3 is a flow diagram of the method performed in the computer of FIG. 1, in accordance with the present invention;

FIG. 4 is a flow diagram of the conversion function implemented by the method of the present invention;

FIG. 5 is a flow diagram of the sampling algorithm performed for generating the mean vector of a color image;

FIG. 6 is an illustration of the covariance matrix generated by the conversion function;

FIG. 7 is a block diagram of the process for reconstructing a color image, depicted as a block diagram;

FIG. 8 is a flow diagram for the method of converting the plurality of intrinsic value sets to numerical value sets;

FIG. 9 is a functional block diagram of a remote computer in which the invention of the present invention can be carried out; and

FIG. 10 is a flow diagram of the transformation function for JPEG DCT or JPEG 2000 DWT encoding according to one embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides an enhanced mechanism for compressing images, by iteratively grouping regions or blocks of data with similar frequency properties, in order to increase compression efficiency. In particular, the present invention provides an iterative region-growing algorithm for a partitioned image, which grows regions based on the similarity or difference of color characteristics of non-overlapping regions of the image, resulting in more efficient block coding.

FIG. 1 is a block diagram of a computer system which implements the methods and computer program product in accordance with one embodiment of the present invention. Computer system 100 includes display interface 102 for visually displaying information to a computer user, central processing unit ("CPU") 104, hard drive 106, main memory 108, network interface 112, input device interface 114, and output buffer 124. As shown, the various components of computer system 100 communicate through system bus 110 or similar architecture. Typically, CPU 104 is a microprocessor, such as an INTEL.RTM. PENTIUM.RTM. processor, but CPU 104 may also be any processor that executes program instructions in order to carry out the functions of the present invention. Input device interface 114 provides the capability to input data to computer system 100. For example, input device interface 114 may include a keyboard (not shown) or a mouse (not shown). Network interface 112 provides for data to be transmitted and received over a network.

Main memory 108 stores data, such as compression program 116, reconstruction program 118, operating system 120, and plurality of data files 122. Data files 122 include, among other data, single image files which can be processed according to the present invention. Compression program 116 and reconstruction program 118 are computer program instructions executed by CPU 104 that are loaded into main memory 108. Compression program 116 and reconstruction program 118 implement the functions, as described in detail hereinafter, performed by the present invention. In addition, compression program 116 and reconstruction program 118 are stored on computer readable media and are used therefrom by computer system 100 to perform the specified functions or steps in accordance with the present invention. Operating system 120 provides overall system functionality. Output buffer 124 stores uncompressed image data for display on display interface 102.

In more detail, computer system 100 includes computer-readable storage medium, such as hard drive 106, in which is stored a program for compressing and/or reconstructing color image data. As shown in FIG. 1, the hardware environment includes computer system 100, display interface 102 for displaying text and images to a user, a keyboard for entering text data and user commands into computer system 100, a mouse for pointing, selecting and manipulating objects displayed on display interface 102, hard drive 106, a removable disk drive, a tape drive, a hardcopy output device, a computer network, network interface 112, and a digital input device.

Display interface 102 displays the graphics, images, and text that comprise the user interface for the software applications used by the present invention, as well as the operating system programs necessary to operate computer system 100. A user of computer system 100 uses a keyboard to enter commands and data to operate and control the computer operating system programs as well as the application programs. The user uses a mouse to select and manipulate graphics and text objects displayed on display interface 102 as part of the interaction with and control of computer system 100 and applications running on computer system 100. The mouse is any type of pointing device, including a joystick, a trackball, or a touch-pad without departing from the scope of the present invention. Furthermore, the digital input device allows computer system 100 to capture digital images, and is a scanner, digital camera or digital video camera.

The enhanced image compression mechanism application programs are stored locally on computer readable memory media, such as hard drive 106. In a further arrangement, hard drive 106 itself comprises a number of physical drive units, such as a redundant array of independent disks ("RAID"). In an additional arrangement, hard drive 106 is a disk drive farm or a disk array that is physically located in a separate computing unit. Such computer readable memory media allow computer system 100 to access color image data, image compression application data, computer-executable process steps, application programs and the like, stored on removable and non-removable memory media.

Network interface 112 is a modem connection, a local-area network ("LAN") connection including the Ethernet, or a broadband wide-area network ("WAN") connection such as a digital subscriber line ("DSL"), cable high-speed internet connection, dial-up connection, T-1 line, T-3 line, fiber optic connection, or satellite connection. The network is a LAN network, however in further arrangements of the present invention the network is a corporate or government WAN network, or the Internet.

The removable disk drive is a removable storage device that is used to off-load data from computer system 100 or upload data onto computer system 100. The removable disk drive is a floppy disk drive, an IOMEGA.RTM. ZIP.RTM. drive, a compact disk-read only memory ("CD-ROM") drive, a CD-Recordable drive ("CD-R"), a CD-Rewritable drive ("CD-RW"), a DVD-ROM drive, flash memory, a Universal Serial Bus ("USB") flash drive, pen drive, key drive, or any one of the various recordable or rewritable digital versatile disk ("DVD") drives such as the DVD-Recordable ("DVD-R" or "DVD+R"), DVD-Rewritable ("DVD-RW" or "DVD+RW"), or DVD-RAM. Operating system programs, applications, and various data files, such as image data files or image compression application programs, are stored on disks. The files are stored on hard drive 106 or on removable media for the removable disk drive without departing from the scope of the present invention.

The tape drive is a tape storage device that is used to off-load data from computer system 100 or upload data onto computer system 100. The tape drive is a quarter-inch cartridge ("QIC"), 4 mm digital audio tape ("DAT"), or 8 mm digital linear tape ("DLT") drive.

The hardcopy output device provides an output function for the operating system programs and applications including the enhanced image compression mechanism. The hardcopy output device is a printer or any output device that produces tangible output objects, including image data or graphical representations of image data. While the hardcopy output device is preferably directly connected to computer system 100, it need not be. For instance, in an alternate arrangement of the invention, the hardcopy output device is connected via a wired or wireless network connection.

Although computer system 100 has been described as a desktop PC, in further arrangements of the present invention computer system 100 is a laptop, a workstation, a midrange computer, a mainframe, or an embedded system.

The internal computing environment of computer system 100 includes CPU 104, where the computer instructions that comprise an operating system or an application, including the enhanced image compression mechanism, are processed; an interface which provides a communication interface and processing functions for rendering graphics, images, and texts on display interface 102; a keyboard interface which provides a communication interface to the keyboard; a pointing device interface which provides a communication interface to the mouse or an equivalent pointing device; a digital input interface which provides a communication interface to input device interface 114; a hardcopy output device interface which provides a communication interface to the hardcopy output device; random access memory ("RAM"), where computer instructions and data are stored in a volatile memory device for processing by CPU 104; read-only memory ("ROM"), where invariant low-level systems code or data for basic system functions such as basic input and output ("I/O"), startup, or reception of keystrokes from the keyboard are stored in a non-volatile memory device; physical media, which can comprise hard drive 106 and the removable disk drive, where the files that comprise operating system 120, application programs (including compression program 116, reconstruction program 118 and other applications) and data files 122 are stored; a modem interface which provides a communication interface to the computer network over a modem; and network interface 112 which provides a communication interface to the computer network over a computer network connection. The constituent devices and CPU 104 communicate with each other over system bus 110.

The RAM interfaces with system bus 110 so as to provide quick memory storage to CPU 104 during the execution of software programs such as the operating system application programs, and device drivers. More specifically, CPU 104 loads computer-executable process steps from hard drive 106 or other memory media into a field of RAM in order to execute software programs. Data, including data relating to the image compression, is stored in RAM, where the data is accessed by CPU 104 during execution.

Main memory 108 stores computer-executable code for windowing operating system 120, application programs such as word processing, spreadsheet, presentation, graphics, image processing, gaming, or other applications. Main memory 108 also stores compression program 116 and reconstruction program 118, which utilize an iterative region-growing algorithm for a partitioned image, growing regions based on the similarity or difference of color characteristics of non-overlapping regions of the image.

Referring ahead briefly to FIG. 2A, compression program 116 includes conversion function 116a, transformation function 116b, quantization function 116c, and encoder function 116d. As shown in FIG. 2B, reconstruction program 118 includes de-conversion function 118a, de-transformation function 118b, de-quantization function 118c, and decoder function 118d. As will be described in detail below, the present invention enables computer system 100, under the direction of compression program 116 and reconstruction program 118, to efficiently compress and reconstruct color images, respectively.

Although the compression and reconstruction of images is preferably implemented as shown, it is also possible to implement the image compression mechanism according to the present invention as a dynamic link library ("DLL"), or as a plug-in to other application programs, such the MICROSOFT.RTM. Internet Explorer web browser.

CPU 104 is one of a number of high-performance computer processors, including an INTEL.RTM. or AMD.RTM. processor, a POWERPC.RTM. processor, a MIPS.RTM. reduced instruction set computer ("RISC") processor, a SPARC.RTM. processor, an HP ALPHASERVER.RTM. processor, or a proprietary computer processor for a mainframe, without departing from the scope of the present invention. In an additional arrangement, CPU 104 in computer system 100 includes more than one processing unit, such as a multiple CPU configuration found in high-performance workstations and servers, or a multiple scalable processing unit found in mainframes.

Operating system 120 is: MICROSOFT.RTM. WINDOWS NT.RTM./WINDOWS.RTM. 2000/WINDOWS.RTM. XP Workstation; WINDOWS NT.RTM./WINDOWS.RTM. 2000/WIDOWS.RTM. XP Server; one of a variety of UNIX.RTM.-flavored operating systems, including AIX.RTM. for IBM.RTM. workstations and servers, SUNOS.RTM. for SUN.RTM. workstations and servers, LINUX.RTM. for INTEL.RTM. CPU-based workstations and servers, HP UX WORKLOAD MANAGER.RTM. for HP.RTM. workstations and servers, IRIX.RTM. for SGI.RTM. workstations and servers, VAX/VMS for Digital Equipment Corporation computers, OPENVMS.RTM. for HP ALPHASERVER.RTM.-based computers, MAC OS.RTM. X for POWERPC.RTM. based workstations and servers, or a proprietary operating system for mainframe computers.

While FIG. 1 illustrates a preferred embodiment of a computing system that executes program code, or program or process steps, configured to compress images using an iterative region-growing algorithm, other types of computing systems may also be used as well. In particular, one having ordinary skill in the art will recognize that the methods and computer program products in accordance with the present invention can be implemented on any system provided with a central processing unit, input/output circuitry, and memory.

FIG. 3 is a flow diagram depicting the process for compressing a color image according to the present invention. Briefly, the method includes the steps of converting color image information for a color image into partitioned intrinsic color information, and transforming the partitioned intrinsic color information into transformed information. The method further includes the steps of quantizing the transformed information into quantized information, encoding the quantized information into encoded information, and storing the encoded information.

In more detail, the compression process begins (Step S300), and color image information or data for a color image is received (Step S310). For example, the received color image is a scanned raster image, a photograph from a digital camera, or a satellite image, such as an image obtained using SPACE IMAGING.RTM.'s IKONOS.RTM., CNES/France's SPOT or the United States' LANDSAT.RTM. satellites. The received color image is obtained and designated in a variety of ways, such as by a user-initiated download, or upon the selection of an image feed, or by an automated periodic image capture.

The color image information includes a plurality of numerical value sets representing the received color image in one of a plurality of normal color space signal formats. A normal color space signal format is a set of numerical values which characterizes an image's colors in a particular color system using spectral weighting functions. Such color systems include but are not limited to a red-green-blue color space ("RGB color space"), a cyan-magenta-yellow color space ("CMY color space"), or a cyan-magenta-yellow-black color space ("CMYK color space").

In the RGB, CMY, or CMYK color space signal formats, a set of three numerical values (if RGB or CMY) or four numerical values (if CMYK) of the plurality of numerical value sets is associated with each pixel in the array of pixels for the received color image. In particular, this set of values in the normal color space signal format is expressed as a color triple or quadruple, such as (0,0,0) in the RGB color space, where each numerical value in the set corresponds to a color component used by the color system, and where the color components are used in combination by the particular color system to represent colors. For example, the set of three numerical values or color triple 0.sub.R,0.sub.G,0.sub.B represents the color black, where the numerical values correspond respectively to the red, green, and blue components for generating the color black in the RGB color space. By varying the numerical values in a set of values in the color triple or quadruple, the representative color of the associated pixel varies. The plurality of numerical value sets enables the display of images for viewing on display interface 102, as well as the compression and reconstruction of an image.

The rationale for using luminance/chrominance color space in the DCT-based or DWT-based image compression mechanisms is that some chrominance information can be lost in an image, since the human eye is less likely to perceive the changes in the chrominance or color component of a reconstructed image. As a result, the chrominance components are sub-sampled or reduced, while the luminance component is left at full resolution. In the YUV luminance/chrominance color space, input color information is represented by three arrays of unsigned bytes, where each unsigned byte has a value between 0 and 255. The input of image information and the conversion of color image information between color spaces are well known in the art.

In Step S320, CPU 104 executes conversion function 116a, and the received image information is converted into partitioned intrinsic color information, using a principal components or Karhunen-Loeve ("KL") transform. The KL transform is a mathematical way of determining that linear transformation of a sample of points in N-dimensional space which exhibits the properties of the sample most clearly along the coordinate axes. Along the new axes the sample variances are extremes (maxima and minima), and uncorrelated. The name "principal component transform" comes from the principal axes of an ellipsoid (e.g. the ellipsoid of inertia), which are just the coordinate axes in question. KL transformation of input color information results in an increased overall compression ratio for the image compression mechanism.

According to the present invention transforms, data which was originally in the RGB, CMY, CMYK or other color space is converted into a principal components color space, using image specific color transformations. Both conventional JPEG and JPEG 2000 image compression mechanisms use a fixed color transformation in the encoding of an image. The present invention, however, produces a covariance matrix for the color image, and uses the covariance matrix to produce an eigenspace transformation that better allocates color information into the color components used in the JPEG or JPEG 2000 compression process. A principal components approach ensures that the luminance channel contains the maximum allowable image entropy. This results in better quality image transmission and reduced file size for a compressed image, as an effect of JPEG or JPEG 2000 compression.

The partitioned intrinsic color information expresses image pixel information such that the most information about an image is presented in the first component of a color triple or quadruple, where the intrinsic color information includes a plurality of value sets for the designated image. The plurality of value sets represents the designated image in a principal components space signal format. The principal components space signal format is based on, and defined by the color image's intrinsic color distribution statistics. The details for converting the received color image information into partitioned intrinsic color information using the KL transform is described in greater detail in the discussion of FIG. 4, below.

In Step S330, a forward DCT or DWT is applied to the partitioned intrinsic color information, generating transformed information (in the form of DCT or DWT coefficient vectors). In particular, CPU 104, under the instruction of transformation function 1116b, performs an approximation of the values in the plurality of intrinsic value sets in response to receiving the partitioned intrinsic color information generated in Step S320. Transformation function 116b applies trigonometric functions to the intrinsic color information, in accordance with the JPEG DCT compression standard, or algebraic functions to the intrinsic color information, in accordance with the JPEG 2000 DWT compression standard, to generate a plurality of approximation values.

The JPEG DCT is a relative of the Fourier transform and likewise gives a frequency map, where the DCT itself is reversible except for round-off error. The motivation for generating a frequency maps is that you can now throw away high-frequency information without impacting low-frequency information. The techniques and methods for implementing the JPEG DCT are well known in the art.

To perform the JPEG 2000 DWT, the present invention uses a one-dimensional sub-band decomposition of a one-dimensional set of samples into low-pass coefficients, representing a downsampled low-resolution version of the original set, and high-pass coefficients, representing a downsampled residual version of the original set, needed to reconstruct the original set from the low-pass set.

Using the JPEG DWT, the partitioned intrinsic color information is decomposed into different decomposition levels using the wavelet transform. These decomposition levels contain a number of sub-bands populated with coefficients that describe the horizontal and vertical spatial frequency characteristics of the original tile-component planes. The coefficients provide frequency information about a local area, rather than across the entire image like the Fourier Transform. Specifically, a small number of coefficients completely describes a single sample. A decomposition level is related to the next decomposition level by spatial powers of two, so each successive decomposition level of the sub-bands has approximately half the horizontal and half the vertical resolution of the previous decomposition level. Images of lower resolution than the original are generated by decoding a selected subset of these sub-bands. The techniques and methods for implementing the JPEG 2000 DWT are also well known in the art.

Although the transformation function is described herein as utilizing the JPEG DCT or JPEG 2000 DWT, it is to be understood that other DCT or DWT algorithms may also be used. As just one example, the present invention contemplates the use of any transformation that iteratively transforms one signal into two or more filtered and decimated signals corresponding to different frequency bands.

FIG. 10 is a flow diagram of the transformation function for JPEG or JPEG 2000 images according to one embodiment of the present invention. Specifically, FIG. 10 further illustrates the process for transforming partitioned intrinsic color information into transformed information using a JPEG DCT or JPEG 2000 DWT algorithm. The process begins (Step S1001), and a JPEG or JPEG 2000 encoder is loaded from a data storage medium such as hard drive 106 into memory 108 (Step S1002). The partitioned intrinsic color data, which was converted from color image information in Step S320 by conversion function 116a, is applied to the JPEG or JPEG 2000 encoder (Step S1004), and the JPEG or JPEG 2000 encoder converts the intrinsic color data to transformed information, and the process ends (Step S1005). Transformation function 116b itself performs no data compression.

Returning to FIG. 3, in Step S340, CPU 104, under the instruction of quantizer function 116c, performs the quantization process in response to receiving the plurality of approximation values in Step S330. The quantization process reduces or truncates the DCT coefficients to a predetermined range of integer values, and thus, reduces the number of bits that are required to represent the approximation values.

Quantization is performed by dividing each approximation value by a predetermined value, where the predetermined value is obtained from an entry in a quantization table. JPEG, for example, defines a standard quantization table for the chrominance channel, and a standard quantization table for the luminance channels. Since the human eye is most sensitive to low frequencies and less sensitive to high frequencies, customized quantization tables can be scaled up or down to adjust the quality factor. Furthermore, one having ordinary skill in the art may vary the entries in the quantization table to optimize image compression of different types of images.

Also in Step S340, following the quantization operation, the quantized information (representing quantized DCT coefficients) is sequenced using a zigzag scan. The zigzag sca