Encoding and decoding of color digital image using wavelet and fractal encoding

• US 6,002,794 A
• Filed: 08/26/1997
• Issued: 12/14/1999
• Est. Priority Date: 04/08/1996
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Bonneau, Robert J., Meadows, Henry E.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/918,791
• Time in Patent Office: 840 Days
• Field of Search: 382/232-233, 382/248-249, 382/240, 382/162, 382/166, 358/433, 358/518-521, 348/398, 348/403, 348/420, 348/438, 348/397
• US Class Current: 382/166
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions
• CPC Class Codes: G06V 40/168 Feature extraction; Face representation
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/619 the transform being operated outside the prediction loop
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

Color digital image data is encoded and compressed by a technique which combines the advantages of both wavelet and fractal encoding. The technique produces an encoded image separated by color components which can be efficiently matched to other compressed images in order to identify the image being processed. The encoding technique divides the images at numerous scales produced by wavelet transformations and forms blocks comprising of groups of pixels at each scales. The average modulus values and average angles values of the data in each of the blocks are compared to the next higher scale. Each scale is then encoded for the blocks which have corresponding matching blocks in the adjacent scale. The technique provides the edge retention benefits of wavelet and the compression benefits of fractal encoding and also accelerates the matching process between the scales. A decoding technique which uses a cross scale approximation of wavelet coefficients is used to reconstruct the image.

Claims

1. A method for compressing color digital image data, wherein said color digital image data is separated into a plurality of different color data groups, comprising the steps of:

transforming one of said groups of color data into a different selected color, wherein said different selected color is more indicative of edges in said image than said data group which is transformed;

spatially decomposing each of said groups of image data into high frequency and low frequency images at a plurality of scales of decreasing frequencies;

fractally encoding said high frequency data for each said group responsive to said high frequency data at said scales generated for said group; and

storing separately encoded data for each said group data responsive to said fractal encoding and comprising information representing modulus and angle relationships between portions of said image at said plurality of scales.

2. The method of claim 1, where said spatially decomposing step includes forming point representations at each scale for each said group.

3. The method of claim 2, said fractally encoding step includes the step of dividing said point representations of each said scale into blocks.

4. The method of claim 3, wherein said generated blocks are restricted to be selected from an object representation in said image being encoded.

5. The method of claim 3, said fractally encoding step includes the step of computing the normalized modulus and angle values of each of said blocks.

6. The method of claim 5, wherein said fractally encoding step includes matching said normalized modulus and angle values from said blocks of each of said scales to said blocks of an adjacent scale.

7. The method of claim 1, wherein said plurality of different color data comprises red, blue and green data.

8. The method of claim 1, wherein said different selected color is luminance.

9. The method of claim 8, wherein said transformed group of data comprises data representative of green.

10. The method of claim 1, wherein said stored group data is processed separately for each color.

11. The method of claim 1, where said stored group data comprises luminance data, and said luminance data is transformed to green data prior to being decompressed.

12. The method of claim 1, where said storing data further includes storing data indicating the color of the data.

13. The method of claim 12, further including storing data indicating the position of the object.

14. The method of claim 13, further including storing data indicative of the low frequency information of said object.

15. The method of claim 14, where said data indicative of the low frequency information comprises a Holder exponent.

16. The method for processing compressed color digital image data representing an original color image, wherein said image data has been spatially decomposed into a plurality of scales, wherein information representing modulus and angle value relationships between portions of said image at the plurality of scales and a representation of said image at the lowest scale has been stored, the method comprising the steps of:

a. spatially decoding said stored representation;

b. decoding said spatially decoded representation responsive to said stored relationship information;

c. transforming said decoded representation in step b to a representation in a next scale; and

d. repeating steps b and c until said representation closely approximates the original image.

17. The method of claim 16, wherein said decoding step b fractally decodes said image.

18. The method of claim 17, where said transforming step c uses a wavelet transformation.

19. The method of claim 16, where said decoding step a uses a wavelet transformation.

20. The method of claim 16, further including the step of filtering said representation after each said fractally decoding step b is performed.

21. The method of claim 20, wherein said filtering removes block artifacts from said representation.

22. The method of claim 16, wherein said spatially decoding step upsamples said compressed image data.

23. The method of claim 16, wherein said relationship information includes block information and said decode step b uses an average angle value for said block information for decoding.

24. The method of claim 23, wherein said relationship information further includes data responsive to average intensity values of said blocks.

25. The method of claim 16, wherein said digital image data comprises color information, and said image is stored as a plurality of different color data groups, and method for processing compressed digital image data is performed for each said data group.

26. The method of claim 25, wherein said plurality of data groups are combined to restore said original image.

27. The method of claim 25, where one of said plurality of stored colors is luminance.

28. The method of claim 27, wherein said luminance data is transformed to a different color prior to being combined with said other of said plurality of color data groups.

29. A system for processing compressed color digital image data to reconstruct said color digital image comprising:

a storage medium for storing information indicative of said compressed image which has been spatially decomposed into a plurality of scales, wherein said information comprises information representing modulus and angle value relationships between portions of said image at the plurality of scales;

at least one processor which repeatedly transforms said compressed image by fractally decoding and spatially reconstructing said stored information at a plurality of scales using said relationships, wherein said image information is repeatedly transformed until said compressed image approximates the original image; and

a display for displaying said reconstructed image.

30. The system of claim 29, wherein said processor utilizes average modulus and angle value of block representations of portions of said image during said decoding function.

31. The method of claim 30, wherein said processor further utilizes data responsive to average intensity values of said block representations.

32. The system of claim 29, where said spatially reconstruction function is performed with wavelet transforms.

33. The system of claim 29, where said stored information in said storage medium includes data organized by objects in said image.

34. The system of claim 29, where said stored information in said storage medium includes data organized by color components.