Method of encoding a digital image using adaptive partitioning in an iterated transformation system

• US 5,862,262 A
• Filed: 03/30/1992
• Issued: 01/19/1999
• Est. Priority Date: 03/30/1992
• Status: Expired due to Fees

• Current Assignee: The Government Of The United States As Represented By The Secretary Of The Navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Fisher, Yuval, Jacobs, Everett W., Boss, Roger D.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): KELLEY, CHRISTOPHER S
• Application Number:
  US07/859,782
• Time in Patent Office: 2,486 Days
• Field of Search: 382/56, 382/14, 358/426, 358/430, 358/433, 358/133, 358/135, 358/136
• US Class Current: 382/249
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A method of encoding a digital image using adaptive partitioning in an iterated transformation image compression system is provided. A set of ranges R is initialized to include at least two uncovered ranges. A set of domains D is initialized to include only one member which is the entire image area.

For each uncovered range in the set R: A transformation is generated for each domain in the set of domains. Each domain is transformed into corresponding transformed images to map onto each uncovered range in the set R. Each domain'"'"'s transformation is optimized and is indicative of a domain'"'"'s corresponding optimized transformation image for an associated uncovered range. Each optimized transformation image is compared with the associated uncovered range to provide error data as a function of the difference therebetween. The associated uncovered range is redefined as a covered range when the error data for the associated uncovered range is within predefined limits. The covered range is then added to the set of domains D. The associated uncovered range is partitioned into a plurality of non-overlapping image areas. Partitioning is based upon the features of the image bounded by the associated uncovered range and takes place when the error data for the associated uncovered range exceeds the predefined limits. Each of the non-overlapping image areas is added to the set R of uncovered ranges and the associated uncovered range is added to the set of domains D.

The steps of generating, transforming, optimizing, comparing, redefining, partitioning and adding are repeated to select a set of covered ranges, domains and corresponding optimized transformations. The set of covered ranges form a non-overlapping tiling of the image and some iterate of the set of selected transformations is contractive. Information that identifies the set of covered ranges, domains and corresponding optimized transformations is stored compactly in an addressable memory.

Claims

1. A method of data compression for compressed data storage or transmission over a data link of compressed data representing an image, said image being comprised of an array of pixels, each pixel having a position in said array, comprising the steps of:

acquiring a digital image that is a digital representation of said image, said digital image being represented by an array of pixel values defining an entire image area, each pixel value being defined by a three-dimensional vector identifying the position of the pixel in the array and an intensity level of the pixel;

defining at least one partition in said digital representation of said image based upon the intensity levels of each of said pixels in said image area so as to create a plurality of ranges which are to be encoded, each range being a section of said entire image area, there being a union of said ranges, wherein said union of said ranges tile said entire image area, thereby deriving a digital representation of each said partition;

using said digital representation of each said partition to identify each partitioned image area as a member of a set of domains;

generating for each range which is to be encoded a transformation for each member of said set of domains, said transformation comprising positional scaling coefficients and an intensity scaling coefficient, and further comprising positional offset coefficients and intensity offset coefficients;

using each said transformation to transform the corresponding member of said set of domains into a corresponding transformed digital image scaled in size and intensity to map onto each range which is to be encoded;

optimizing each said transformation in terms of the intensity scaling and offset coefficients, wherein an optimized transformation is indicative of a corresponding optimized transformed digital image for the associated range;

comparing each said optimized transformed digital image with the associated range to provide error data as a function of the difference therebetween;

redefining each range which is to be encoded as an encoded range when at least one of said error data for the range is within predefined limits and adding said encoded range to said set of domains;

defining for each range which is still to be encoded following said step of redefining at least one additional partition in said digital representation of said range which is still to be encoded based upon the intensity level of each of said pixels in said image area encompassed by said range which is still to be encoded so as to create a plurality of non-overlapping image areas thereby deriving a digital representation of each said additional partition;

adding each range which is still to be encoded following said redefining step to said set of domains;

creating a new set of ranges which are to be encoded comprising said plurality of non-overlapping image areas;

repeating said steps of generating using each said transformation, optimizing, comparing, redefining, defining, adding and creating to select a set of encoded ranges, domains and corresponding optimized transformations, wherein said set of encoded ranges form a non-overlapping tiling of said entire image area such that some iterate of the set of selected set of transformations is contractive so as to create a digital representation of the entire partition comprising each said partition and each said additional partition; and

storing in an addressable memory information that represents said image by said digital representation of said entire partition, said set of encoded ranges, domains and corresponding optimized transformations.

2. A method according to claim 1 wherein said step of defining comprises the steps of:

locating edge features in each associated range which is still to be encoded following said step of redefining wherein an edge feature is indicative of intensity change in each associated range which is still to be encoded following said step of redefining, wherein the greatest level of intensity change is indicative of a prominent edge feature; and

dividing each associated range which is still to be encoded following said step of redefining into two adjacent rectangles having a common lengthwise side, wherein at least one of the rectangles does not contain the prominent edge feature.

3. A method according to claim 2 wherein the prominent edge feature forms at least a portion of the common lengthwise side of the rectangles.

4. A method according to claim 2 wherein one of the rectangles contains the prominent edge feature.

5. A method according to claim 4 wherein the prominent edge feature intersects a corner of the one rectangle containing the prominent edge feature.

6. A method according to claim 1 wherein the transformation for a domain D_i from the set of domains D is defined as w_i (x,y,z) and is of the form ##EQU5## where, for a pixel in D_i, a_i, b_i, c_i and d_i are positional scaling coefficients for transforming the position of the pixel;

s_i is the intensity scaling coefficient for transforming a gray level of the pixel;

e_i and f_i are positional offset coefficients for the pixel; and

o_i is an intensity offset coefficient for the pixel.

7. A method according to claim 6 wherein xy contractivity as determined by the positional scaling coefficients is not restricted to be contractive.

8. A method according to claim 7 wherein the intensity scaling coefficient is restricted to be less than one.

9. The method of claim 1 wherein said transformation comprises a 3×

3 matrix identifying said positional scaling and intensity scaling coefficients, and a 3×

1 vector identifying said positional offset and intensity offset coefficients.