Method and system for representing a data set with a data transforming function and data mask

• US 5,838,832 A
• Filed: 04/03/1995
• Issued: 11/17/1998
• Est. Priority Date: 04/03/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Iterated Systems Inc (Hewlett-Packard Enterprise Company)
• Inventors: Barnsley, Michael F.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US08/415,559
• Time in Patent Office: 1,324 Days
• Field of Search: 382/249, 382/248, 382/283, 382/232, 358/433, 358/467
• US Class Current: 382/249
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

A system and method are disclosed for representing a data set by selecting a data transformation function and a data masking function. Preferably, the data set transformation and data masking functions are used to generate an attractor that more accurately represents the data set than an attractor generated by the data transformation function alone. The data masking function is a set of exclusionary data elements which are used to terminate data transformations for data elements which generate the attractor. Preferably, the data masking function is defined as a polygon for a two dimensional space. When the data masking function is incorporated with the data transformation function, the attractor normally produced by the data set transformation function is constrained to more accurately represent the data set. The data masking function may be used with any data transformation function including those comprised of complex, projective, affine maps, fractal transform, or fractal transform error function transformations. Deterministic and random iterative methods may be used to generate the constrained attractor that represents the data set to be represented.

Claims

1. A method for representing a data set comprising the steps of:

selecting one of a complex, affine, and projective transformation function that generates an attractor that approximates a data set; and

selecting a data mask function for constraining said attractor produced by said data set transformation function whereby said attractor more accurately represents said data set.

2. The method of claim 1 wherein said selecting transformation function step further includes the step of:

selecting a plurality of transformation functions to represent said data set.

3. The method of claim 1 wherein said selecting data masking function step further includes the step of:

selecting a set of exclusionary data elements.

4. The method of claim 3 wherein said selecting data exclusionary set including the step of:

selecting a polygon as said data masking function.

5. The method of claim 2 wherein said selecting transformation functions step further includes the step of:

selecting coefficients for each selected transformation function.

6. The method of claim 1 further comprising the step of:

evaluating said constrained attractor to determine an error between said constrained attractor and said data set to be represented; and

modifying one of said selected transformation function and said selected data masking function in response to said determined error being greater that a predetermined threshold.

7. The method of claim 6 wherein said modifying step further includes the step of:

modifying at least one coefficient of said selected transformation function.

8. The method of claim 6, wherein said modifying step further includes the step of:

modifying data elements of an exclusionary data set comprising said data masking function.

9. The method of claim 7 further comprising the step of:

determining whether said modified transformation function and said selected data masking function generate an attractor that more accurately represents said data set.

11. The method of claim 1 wherein said selecting transformation function step further includes:

selecting a fractal transform method to transform said data set.

12. The method of claim 11 further including the step of:

selecting a data masking function to constrain an attractor generated by transforming a range block.

13. The method of claim 1 further comprising the step of:

generating an error function which defines an accuracy error between said data set and said transformation function and data masking function; and

minimizing said generated error function to reduce a set of coefficients to represent said data set.

10. The method of claim 10 further comprising the step of:

transmitting said coefficients of said modified transformation function and said data masking function so that a receiver may generate said attractor that represents said data set.

14. A method for generating a transformed data set which represents a data set comprising the steps of:

initializing a data buffer with a random image;

applying one of a complex, affine, and projective transformation function to each data element of said random image and storing said transformed data element in a transform buffer unless said data element of said random image is within a data masking function;

measuring an error difference between said data elements of data buffer and said transform buffer;

exchanging said data buffer and said transform buffer; and

repeating said applying, said measuring, and said exchanging steps until said error measurement does nor exceed a predetermined threshold so that said transformation buffer contains an attractor representing said data set.

15. The method of claim 14 wherein said error difference measuring step measures said error difference by computing one of a Hausdorff distance, a root mean square distance, and a Hamming distance.

16. The method of claim 14 further comprising the steps of:

measuring an error difference between said attractor and said data set being represented; and

modifying one of said transformation function and said data masking function whereby said attractor generated by said modified data masking function and transformation function more accurately represent said data set.

17. The method of claim 16 wherein said error difference measuring step measures said error difference by computing one of a Hausdorff distance, a root mean square distance, and a Hamming distance.

19. The method of claim 17 further comprising the steps of:

measuring an error difference between said attractor and said data set being represented; and

modifying one of said transformation function and said data masking function whereby said attractor generated by said modified data masking function and transformation function more accurately represent said data set.

20. The method of claim 19 wherein said error difference measuring step measures said error difference by computing one of a Hausdorff distance, a root mean square distance, and a Hamming distance.

18. A method for generating a transformed data set which represents a data set comprising the steps of:

initializing a data buffer with a random image;

applying one of a complex, affine, and projective transformation function to each data element of said random image and storing said transformed data element in a transform buffer unless said data element of said random image is within a data masking function;

decrementing an iteration count;

exchanging said data buffer and said transform buffer; and

repeating said applying and said decrementing steps until said iteration count is zero so that said last buffer to which data elements were stored contains an attractor representing said data set.

21. A method of generating a transformed data set which represents a data set comprising the steps of

initializing a data element in a data buffer;

applying one of a complex, affine, and projective data transformation function to transform said data element within said data buffer;

determining whether said transformed data element is within a data masking function;

applying said transformation function to one of said transformed element and a last transformed element in response to said determination of said transformed data element being within said data masking function;

decrementing an iteration count; and

continuing said determining and applying steps until said iteration count is zero whereby said transformed data elements in said data buffer form an attractor that represents said data set.

22. The method of claim 21 further comprising the step of:

selecting a transformation from a set of transformations that comprise said data transformation function.

23. The method of claim 22 wherein said transformation is selected in accordance with a probability corresponding to said transformations comprising said transformation function.

24. The method of claim 22 wherein said set of transformations is a plurality of affine maps.

25. The method of claim 21 further comprising the step of:

defining said data masking function as a set of exclusionary data elements.

26. The method of claim 25 wherein said defining step further includes the step of:

selecting vertices which define a polygon.

27. The method of claim 26 wherein said selecting vertices step further includes the step of:

selecting said vertices being done interactively.

28. The method of claim 26 wherein said selecting vertices step further includes the step of:

identifying coordinates for said vertices.

29. The method of claim 26 wherein said selecting vertices step further includes the step of:

selecting a mathematical equation that defines said polygon.

30. The method of claim 21 further comprising the steps of:

measuring an error difference between said attractor and said data set being represented; and

modifying one of said transformation function and said data masking function whereby said attractor generated by said modified data masking function and transformation function more accurately represent said data set.

31. The method of claim 30 further comprising the step of:

modifying coefficients of an affine map in response to a determination that said attractor does not conform to said set of data.

32. The method of claim 30 further comprising the step of:

modifying vertices of a polygon defining said data masking function in response to a determination that said attractor does not conform to said data set.

33. A system for generating an attractor from a data transformation function and a data masking function that represents a data set;

a data mask generator for generating a data masking function;

a data function generator for generating one of a complex, affine, and projective transformation function, said data function generator said said transformation function and said data masking function to generate an attractor; and

a transmitter for transmitting said transformation function and said data masking function to a remote site for regeneration of sad attractor.

34. The system of claim 33 further comprising:

a comparator for comparing said attractor generated by said data function generator to a data set to be represented by said attractor, said comparator measuring an error distance between said data set and said attractor.

35. The system of claim 34 wherein said data function generator further comprises:

a coefficient modifier for modifying coefficients of said transformation function in correspondence with said error distance.

36. The system of claim 34 wherein said data mask generator further comprises:

a masking modifier for modifying said data masking function in correspondence with said error distance.

37. The system of claim 34 wherein said comparator further comprises:

an error function generator for generating an error function and minimizing said error function so that coefficients for said minimized error function may be used to represent said data set.

38. The system of claim 33 wherein said data function generator generates said attractor with a deterministic process.

39. The system of claim 33 wherein said data function generator generates said attractor with a random iteration process.

40. The system of claim 33 wherein said data function generator generates said attractor with a fractal process.

41. The system of claim 33 wherein said data function generator generates said attractor with a error function fractal process.

42. The system of claim 40 further comprising:

means for transforming range blocks with another data transformation and another data masking function whereby said transformed range blocks more accurately conform to domains generated from said data set.

43. The system of claim 40 further comprising:

means for using said data masking function to prevent comparison of a domain to a range block.

45. The system of claim 38 wherein said selecting transformation function means further comprises:

means for selecting a plurality of data transformations to represent said data set.

46. The system of claim 38 wherein said data masking function is a set of exclusionary data elements.

47. The system of claim 41 said data exclusionary set being a polygon.

48. The system of claim 39 further comprising:

means for selecting coefficients for each selected transformation function.

44. A system for representing a data set comprising the steps of:

means for selecting one of a complex, affine, and projective transformation function that generates an attractor that approximates a data set; and

means for selecting a data mask function for constraining said attractor produced by said transformation function whereby said attractor more accurately represents said data set.

49. The system of claim 44 further comprising:

means for evaluating said constrained attractor to determine an error between said constrained attractor and said data set to be represented; and

means for modifying one of said selected transformation function and said selected data masking function in response to said determined error being greater than a predetermined threshold.

50. The system of claim 49 wherein said modifying means further comprises:

means for modifying at least one coefficient of said selected transformation function.

51. The system of claim 49 wherein said modifying means further comprises:

means for modifying data elements of an exclusionary data set comprising said data masking function.

52. The system of claim 50 further comprising:

means for determining whether said modified transformation function and said selected data masking function generate an attractor that more accurately represents said data set.

53. The system of claim 52 further comprising:

means for transmitting said coefficients of said modified transformation function and said data masking function so that a receiver may generate said attractor that represents said data set.

54. The system of claim 44, further comprising:

means for generating an error function which defines an accuracy error between said data set and said data transformation and data masking function; and

means for minimizing said generated error function to reduce a set of coefficients to represent said data set.

55. A system for generating a transformed data set which represents a data set comprising:

means for initializing a data buffer with a random image;

means for applying one of a complex, affine, and transformation function to each data element of said random image and storing said transformed data element in a transform buffer unless said data element of said random image is within a data masking function;

means for measuring an error difference between said data buffer and said transform buffer;

means for applying a data transformation function to each data element of said transform buffer and storing said transformed data element in said data buffer unless said data element of said transform buffer is with a data masking function in response to said error difference exceeding a predetermined threshold;

means for repeating said applying and said measuring steps until said error measurement does not exceed said predetermined threshold.

56. The system of claim 55 wherein said error difference measuring means measures said error difference by computing one of a Hausdorff distance, a root mean square distance, and a Hamming distance.

57. The method of claim 55 further comprising the steps of:

means for measuring an error difference between said attractor and said data set being represented; and

means for modifying one of said data transformation function and said data masking function whereby said attractor generated by said modified data masking function and transformation function more accurately represent said data set.

58. A system for generating a transformed data set which represents a data set comprising:

means for initializing a data buffer with a random image;

means for applying one of a complex, affine, and projective transformation function to each data element of said random image and storing said transformed data element in a transform buffer unless said data element of said random image is within a data masking function;

means for decrementing an iteration count;

means for applying one of a complex, affine, and projective transformation function to each data element of said transform buffer and storing said transformed data element in said data buffer unless said data element of said transform buffer is within a data masking function in response to said decremented iteration count being non-zero; and

means for repeating said applying and said decrementing steps until said iteration count is zero so that said last buffer to which data elements were stored contains an attractor representing said data set.

59. The system of claim 58 further comprising the steps of:

means for measuring an error difference between said attractor and said data set being represented; and

means for modifying one of said transformation function and said data masking function whereby said attractor generated by said modified data masking function and transformation function more accurately represent said data set.

60. A system of generating a transformed data set which represents a data set comprising:

means for initializing a data element in a data buffer;

means for applying one of a complex affine, and projective transformation function to transform said data element within said data buffer;

means for determining whether said transformed data element is within a data masking function;

means for applying said transformation function to one of said transformed element and a last transformed element in response to said determination of said transformed said element being within said data masking function;

means for decrementing an iteration count; and

means for continuing said determining and applying steps until said iteration count is zero whereby said transformed data elements in said data buffer form an attractor that represents said data set.

61. The system of claim 60 further comprising the steps of:

means for measuring an error difference between said attractor and said data set being represented; and

means for modifying one of said transformation function and said data masking function whereby said attractor generated by said modified data masking function and data transformation more accurately represent said data set.

62. The system of claim 61 further comprising:

means for modifying coefficients of said transformation function in response to a determination that said attractor does not conform to said set of data.

63. The system of claim 61 further comprising the step of:

means for modifying said data masking function in response to a determination that said attractor does not conform to said data set.