Fractal representation of data

• US 6,111,988 A
• Filed: 04/24/1997
• Issued: 08/29/2000
• Est. Priority Date: 07/01/1994
• Status: Expired due to Fees

• Current Assignee: Intellectual Ventures Fund 32 LLC (Intellectual Ventures LLC)
• Original Assignee: Commonwealth Scientific & Industrial Research Organisation (Commonwealth Of Australia As Represented By Department Of Industry, Innovation, Climate Change, Science, Research And Tertiary Education)
• Inventors: Bone, Donald J., Veldkamp, Jan P., Horowitz, Franklin G.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US08/765,676
• Time in Patent Office: 1,223 Days
• Field of Search: 382/232, 382/240, 382/249, 358/426, 358/403, 358/262.1, 358/432, 358/433, 348/403
• US Class Current: 382/249
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method is provided for the fractal representation of data in which a representative continuous n-dimensional surface is defined as a first approximation to the original data. Residual data is formed from the date and the n-dimensional surface, and is then divided into a first number of regions. For each of the first number of regions, the following steps are performed: A number of domain regions are determined from the data; for a current one of each of the domain regions, a second representative n-dimensional surface is formed from the current domain; a (domain residual is formed from the current domain region; and the second representative n-dimensional surface, and a closest distance or error measure is determined. After processing each of the regions, the representation of data is stored.

Claims

1. A method of coding original data comprising the steps of:

(a) defining a representative continuous n-dimensional surface as a first approximation to said original data,

(b) forming residual data from said original data and said representative continuous n-dimensional surface,

(c) dividing said residual data into a first number of range regions,

(d) for each of said first number of range regions, performing the following steps (e) to (h);

(e) determining a number of domain regions from said original data, said domain regions comprising transformed portions of said original data,

(f) for a current one of each of said domain regions, forming a second representative n-dimensional surface from said current domain region,

(g) forming a domain residual from said current domain region and said second representative n-dimensional surface,

(h) scaling said domain residual to approximate residual in a current range region, wherein said scaling exactly matches one of a plurality of terms in a basis expansion of said current range region, and wherein said scaling forms a scaled domain region having location and transformation data associated with said scaled domain region; and

(i) repeating steps (f) to (h) and choosing a scaled domain region which best matches said residual in said range region;

(j) adding said best matching scaled domain region to said first representative n-dimensional surface for said first number of range partitions to form a new representative n-dimensional surface;

(k) forming new residual from said original data and said new representative n-dimensional surface;

(l) repeating steps (d) to (h) until a second approximation is determined; and

(m) repeating steps (d) to (k) for all of said first number of range partitions.

2. The method according to claim 1 wherein said new representative continuous n-dimensional surface includes data values at predetermined locations of said new representative continuous n-dimensional surface.

3. The method according to claim 2 wherein at least one data value is located within each corresponding region of said first number of range regions.

4. The method according to claim 3 wherein said new representative continuous n-dimensional surface is defined from an interpolation of said data values.

5. The method according to claim 1 wherein each of said domain regions is derived from an area overlapping said current one of each of said first number of range regions.

6. The method according to claim 5 wherein said transformed portions of said original data include subsampling said original data.

7. The method according to claim 5 wherein said transformation optionally include one of scaling, rotation, horizontal reflection, vertical reflection or diagonal reflection of said portion of said residual data.

8. The method according to claim 1 wherein said domain regions include a domain region derived from a block of data having a center corresponding to the location of a data value within said current one of each of said first number of regions and a separate domain region being defined for each of said locations of data values within said regions.

9. The method according to claim 1 wherein the number of dimensions is three.

10. A method of decoding data which has been coded in accordance with any one of claims 1, said method of decoding comprising the steps of:

(a) defining said representative continuous n-dimensional surface from said surface information,

(b) dividing said surface into said first number of regions,

(c) for each of said first number of regions, applying the steps of;

(d) determining a corresponding domain from said location and translation data for said region,

(e) transforming said corresponding domain in accordance with said transformation data of said corresponding domain,

(f) defining a second n-dimensional surface from said transformed corresponding domain,

(g) calculating a second residue portion from said second n-dimensional surface and said transformed corresponding domain,

(h) adding said second residue portion to the representative continuous n-dimensional surface of a said current one of said first number of regions and updating current approximation of data, and

(i) repeating steps (b)-(h) until said surface converges to an approximation to said decoded data.

11. The method according to claim 10 wherein said convergence comprises one of repeating steps (b)-(h) a predetermined number of times or said surface undergoing less then a predetermined amount of alteration between successive repetitions of steps (b)-(h).

12. A method of encoding data comprising the steps of:

(a) deriving surface information, which defines an n-dimensional surface, as a first approximation to said data,

(b) forming residual data from said data and said n-dimensional surface,

(c) dividing said residual data into a first number of regions,

(d) for a first one of said first number of regions, determining a corresponding series of domain regions in accordance with the following steps (e) to (j);

(e) forming a domain region series indicator list, initially comprising an empty list,

(f) determining a number of prospective domain regions from said residual data,

(g) for each of said prospective domain regions, determining a residual prospective domain region from said prospective domain region and an approximation to said prospective domain region, and determining a candidate measure value being a measure of the difference between said residual prospective domain region and the first one of said first number of regions,

(h) determining a best matching prospective domain region, being a domain region which is not a member of said domain region series indicator list and having the smallest of said candidate measure values,

(i) appending an indicator corresponding to said best matching prospective domain region to a said domain region series list, and

(j) subtracting the residual prospective domain region of said best matching prospective domain region from said residual data,

(k) repeating steps (e) to (j) until said residual data is less than a predetermined amount,

(l) repeating steps (d) to (k) for each region of said residual data;

(m) defining said coded data to comprise said surface information and a domain region series indicator list for each of said first number of regions; and

wherein step (g) further comprises non-linearly normalising said residual prospective domain region before determining said candidate measure value.

13. A method of encoding data comprising the steps of:

(a) deriving surface information, which defines an n-dimensional surface, as a first approximation to said data,

(b) forming residual data from said data and said n-dimensional surface,

(c) dividing said residual data into a first number of regions,

(d) for a first one of said first number of regions, determining a corresponding series of domain regions in accordance with the following steps (e) to (j);

(e) forming a domain region series indicator list, initially comprising an empty list,

(f) determining a number of prospective domain regions from said residual data,

(g) for each of said prospective domain regions, determining a residual prospective domain region from said prospective domain region and an approximation to said prospective domain region, and determining a candidate measure value being a measure of the difference between said residual prospective domain region and the first one of said first number of regions,

(h) determining a best matching prospective domain region, being a domain region which is not a member of said domain region series indicator list and having the smallest of said candidate measure values,

(i) appending an indicator corresponding to said best matching prospective domain region to a said domain region series list, and

(j) subtracting the residual prospective domain region of said best matching prospective domain region from said residual data,

(k) repeating steps (e) to (j) until said residual data is less than a predetermined amount,

(l) repeating steps (d) to (k) for each region of said residual data;

(m) defining said coded data to comprise said surface information and a domain region series indictor list for each of said first number of regions; and

wherein said step (g) comprises scaling said residual prospective domain region such that a predetermined portion of said residual prospective domain region is equal to a corresponding portion of said residual data and said step (m) includes defining said coded data to include a scale factor for each of said domain regions in said domain region indicator list.

14. The method according to claim 13 wherein said prospective domain regions include a subsampling of said data.

15. The method according to claim 13 wherein said prospective domain regions overlap corresponding ones of said first number of regions.

16. A method of decoding data which has been encoded in accordance with claim 13, said method comprising the steps of:

(a) deriving a current estimate of said data comprising an n-dimensional surface derived from said surface information,

(b) dividing said current estimate into said first number of regions,

(c) for a first one of said first number of regions, applying the steps (d) to (g);

(d) for a first one of said indicators in said domain region series indicator list, applying the steps (e) to (f);

(e) determining, from said current estimate of said data, a domain region corresponding to said indicator,

(f) update current estimate of current one of said first number of regions with new estimate of current domain region,

(g) repeating steps (d) to (f) for each of said indicators in said domain region series indicator list,

(h) repeating steps (c) to (g) for each of said first number of regions, and

(i) repeating steps (c) to (h) until said data converges.

17. The method according to claim 16 wherein said determining step includes deriving a residue comprising the difference between said current estimate of said data and a surface approximation to said current estimate of said data.

18. The method according to claim 16 wherein said determining step (e) includes sub sampling said current estimate of said data.

19. The method according to claim 16 wherein step (e) further comprises normalising said domain region and scaling by the corresponding scaling factor stored in the encoded data.

20. The method according to claim 16 wherein step (f) comprises subtracting the previous estimate of the current domain region from said current one of said first number of regions and adding in said domain region derived in step (e).