System and method for a multiresolution transform of digital image information

• US 5,946,417 A
• Filed: 09/10/1998
• Issued: 08/31/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:
  US09/150,952
• Time in Patent Office: 355 Days
• Field of Search: 382/103, 382/107, 382/232, 382/233, 382/240, 382/248, 382/249, 382/236, 358/433, 348/397, 348/398, 348/403, 348/420, 348/438, 348/402, 348/416, 348/407
• US Class Current: 382/236
• 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

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 which can be efficiently matched to other compressed images in order to identify the image being processed. The encoding technique spatially decimates the images at numerous frequency scales produced by wavelet transformations and forms blocks comprising of groups of pixels at each frequency scales. The average modulus values and average angle values of the data in each of the blocks are compared to the next higher scale. Each frequency 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 fractal encoding and also accelerates the matching process between the scales. A decoding technique which includes a synthetic edge procedure is used to reconstruct the image. Video encoding can also be done using a variation of the encoding technique.

Claims

1. A method for processing compressed digital image data representing an original image in a series of frames, wherein said image data for a first and second frame has been spatially decomposed into a plurality of frequency scales and into a low frequency and high frequency representation at least two of said scales, the method comprising the steps performed by a data processor of:

computing an optical flow between the first compressed frame and the second compressed frame for at least one frequency scale;

computing the average optical flow within range and domain blocks for said at least one frequency scale;

computing new range and domain blocks for said second frame if said average optical flow exceeds a threshold; and

transmitting range and domain blocks which have changed between said first and second frames.

2. The method of claim 1, wherein said range and domain blocks are related by an average modulus value of each said block.

3. The method of claim 1, wherein said range and domain blocks are related by an average angle value of each said block.

4. The method of claim 1, wherein said new range and domain blocks are stored to track at least one object in said image.

5. The method of claim 1, wherein said new range and domain blocks are stored for later decoding.

6. The method of claim 1, wherein said entire second compressed frame is transmitted if the number of changed optical flow blocks exceeds a threshold.

7. The method of claim 1, further including the steps of:

receiving said transmitted new range and domain blocks;

decoding said new range and domain blocks wherein said entire second frame is decoded if said average optical flow of said transmitted blocks exceeds a threshold.

8. A system for processing digital image data representing an original image in a server of frames comprising:

an image recorder for recording a video image;

a digitizer for converting said recorded video images as said image data;

at least one first processor which spatially decomposes said image data for a first and second frame into a plurality of frequency scales and into a low frequency and high frequency representing at least two of said scales, computing an optical flow between the first compressed frame and the second compressed frame for at least one frequency scale, computing the average optical flow within range and domain blocks for said at least one frequency scale, computing new range and domain blocks for said second frame if said average optical flow exceeds a threshold, and transmitting range and domain blocks which have changed between the first and second frames;

a storage medium for storing information describing said matching blocks; and

a monitor to display said image.

9. The system of claim 8, wherein said range and domain blocks are related by an average modulus value of each said block.

10. The system of claim 8, wherein said range and domain blocks are related by an average angle value of each said block.

11. The system of claim 8, wherein said new range and domain blocks are stored to track at least one object in said image.

12. The system of claim 8, wherein said new range and domain blocks are stored for later decoding.

13. The system of claim 8, wherein said at least one processor transmits said entire second compressed frame if the number of changed optical flow blocks exceeds a threshold.

14. The system of claim 8, further including a second processor for receiving said transmitted new range and domain blocks and decoding said new range and domain blocks wherein said entire second frame is decoded if said average optical flow of said transmitted blocks exceeds a threshold.