Method and apparatus for manipulating colors or patterns using fractal or geometric methods

• US 5,416,848 A
• Filed: 06/08/1992
• Issued: 05/16/1995
• Est. Priority Date: 06/08/1992
• Status: Expired due to Term

• Current Assignee: Chroma Graphics, Inc.
• Original Assignee: Chroma Graphics, Inc.
• Inventors: Young, Fredric S.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US07/895,510
• Time in Patent Office: 1,072 Days
• Field of Search: 382/41, 382/44, 382/17, 382/56, 340/750, 340/778, 340/799, 395/119, 395/141, 395/120, 395/125, 395/133, 395/152, 395/162
• US Class Current: 382/191
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

Colors for a two-dimensional ordered image such as a fractal map are selected by first sampling colors from a real or natural source of colors, such as a tree or a feather and storing values representing the colors in Munsell color space (the three-dimensional space defined by hue, saturation and value) in a source color file, then ordering colors by distance in Munsell color space from a seed reference color (e.g. black), thereafter storing a representation of the color whose distance is closest to the seed reference color as the first color in a storage file known as an ordered color file, using the first color as a new reference color, then sorting the remaining colors according to distance from the new reference color, and storing a representation of the color closest to the new reference color as the second color in the ordered color file. The process is recursively performed until all colors in the source color file have been ordered in the ordered color file. The ordered color file can be mapped into any ordered set, such as a fractal set which is naturally ordered, by assigning the colors of the ordered color file according to the fractal value representing the higher dimension of the fractal set. Colors lost in the color sampling process can be recovered by interpolation between discrete values in the ordered color set. Interpolation is an effective form of data compression of colors.

Claims

1. A method using a computer for preparing ordered sets of colors expressible in a three-dimensional color space from a source of information for use in mapping the information onto an ordered pattern in a lower dimensional image space, such as a two-dimensional physical surface, the method comprising the steps of:

(a) digitizing the source of information for generating a digitized image file;

thereafter

(b) sampling the digitized image file for generating a color sample file;

(c) converting the color sample file to obtain color value, saturation and hue terms as a set of coordinate color points in the color space;

thereafter

(d) storing the set of color points and its terms in a source file of a first memory means;

(d) establishing black as a current reference point;

thereafter

(f) calculating a set of distance values in the color space between each color point of the source file and the current reference point and storing the set of distance values in a list file in a second memory means;

(g) selecting the color point having the minimum distance value,

storing this color point at the current bottom of an ordered color file of a third memory means and establishing this color point as the current reference point;

(h) removing said current reference point from the set of color points in the source file;

thereafter

(i) repeating steps (f) through (h) until the source file is empty, in order to obtain a full range ordered color file in said third memory means;

thereafter

(j) filling a target image with colors representative of the hue, saturation and value of the ordered color file to obtain a colored image comprising a distribution of colors over the target image; and

(k) presenting the colored image through an output device for observation.

2. The method according to claim 1, further including the steps, after step (i), of:

(i1) adding points in color space connecting the first ordered color point and the last ordered color point of said full range ordered color file and rescaling to a preselected number of points relative to a reference color in order to obtain a closed ordered color file; and

(i2) storing said closed ordered color file in a fourth memory means for use in filling the target image.

3. The method according to claim 2, further including the step, after step (i1), of:

(i1a) smoothing across adjacent features of the closed ordered color file.

4. The method according to claim 3, further including the steps, after step (i1a), of:

(i1b) interpolating between ordered color points in the closed ordered color file to obtain interpolated points; and

(i1c) inserting the interpolated points in color order into the closed ordered color file.

5. The method of claim 1 wherein the target image is derivable from a compressed IFS code.

6. The method of claim 1 wherein the target image is a random fractal surface.

7. The method of claim 1 wherein the target image is a dynamical system mapped image sorted according to like colors.

8. The method of claim 1 wherein the target image is a bitmapped image sorted according to like colors.

9. An apparatus, including a central processing unit, for preparing ordered sets of colors expressible in a three-dimensional color space from a source of color information for use in mapping the color information onto an ordered pattern in a lower dimensional image space, such as a two-dimensional physical surface, the apparatus comprising:

(a) a digitizer for converting the source of color information into a digital file;

(b) a first memory means coupled to said digitizer for storing the digital file;

(c) means for sampling the digital file to create a color sample file;

(d) a second memory means coupled to said sampling means for storing the color sample file;

(e) means in said central processing unit coupled to said second memory means for converting said color sample file into a set of color points, each color point having a color value, saturation and hue term;

(f) a third memory means coupled to said central processing unit for storing the set of color points in a color point source file;

(g) means in said central processing unit coupled to said third memory means for establishing a current reference point;

(h) means in said central processing unit for initializing said current reference point to black;

(i) means in said central processing unit coupled to said third memory means for calculating a set of distance values in the color space between each color point of the set of color points and the current reference point;

(j) a fourth memory means for storing the set of distance values;

(k) means in said central processing unit for selecting the color point having the minimum distance value, storing this color point at the current bottom of an ordered color file of a fifth memory means, and establishing this color point as the current reference point;

(l) means in said central processing unit coupled to said third memory means for removing said current reference point from the set of color points in the color point source file;

(m) means in said central processing unit for repeatedly calculating said distance values, storing and removing until the color point source file is empty, in order to obtain a full range ordered color file of ordered color points for storing in said fifth memory means;

(n) means in said central processing unit for filling a target image with colors representative of the hue, saturation and value of the ordered color points to obtain a colored image comprising a distribution of colors over the target image; and

(o) an output device coupled to said central processing unit for presenting the colored image for observation.

10. The apparatus according to claim 9, further including:

(m1) means for adding points in color space connecting the first ordered color point and the last ordered color point of said full range ordered color file and for rescaling to a preselected number of color points relative to a reference color in order to obtain a closed ordered color file; and

(m2) a sixth memory means for storing said closed ordered color file for use in filling the target image.

11. The apparatus according to claim 10, further including:

(m1a) means for smoothing across adjacent features of the closed ordered color file.

12. The apparatus according to claim 11 further including:

(m1b) means for interpolating between ordered points in the closed ordered file to obtain interpolated points; and

(m1c) means for inserting the interpolated points in color order into the closed ordered color file.

21. The apparatus of claim 9 wherein said digitizer is an image scanner.

22. The apparatus of claim 9 wherein said digitizer is a video camera with a frame grabber.

13. A method using a computer for preparing ordered sets of terms expressible in a multidimensional space from a source of information for use in mapping the information onto an ordered pattern in a lower dimensional order of space, the method comprising the steps of:

(a) digitizing the source of information for generating a digitized image file;

thereafter

(b) sampling the digitized image file for generating a color sample file;

(c) converting the color sample file to obtain terms representative of coordinates of a set of color points in the multidimensional space;

thereafter

(d) storing the set of color points and its terms in a source file of a first memory means;

(e) establishing black as a current reference point;

thereafter

(f) calculating a set of distance values between each color point of the source file and the current reference point in the multidimensional space and storing the set of distance values in a list file in a second memory means;

(g) selecting the color point having the minimum distance value,

storing this color point at the current bottom of an ordered color file of a third memory means and establishing this color point as the current reference point;

(h) removing said current reference point from the set of color points in the source file;

thereafter

(i) repeating steps (f) through (h) until the source file is empty, in order to obtain a full range ordered color file in said third memory means;

thereafter

(j) filling a target image with features representative of the terms of the ordered color points in the full range ordered color file to obtain a featured image comprising a distribution of features over the target image; and

(k) presenting the featured image through an output device for observation.

14. The method according to claim 13, further including the steps, after step (j), of:

(j1) adding points in the multidimensional space connecting the first ordered point and the last ordered point of said full range ordered file and rescaling to a preselected number of points relative to a reference point in order to obtain a closed ordered file; and

(j2) storing said closed ordered file in a third memory means for use in filling the target image.

15. The method according to claim 14, further including the step, after step (j1), of:

(j1a) smoothing across adjacent features of the closed ordered file.

16. The method according to claim 15, further including the steps, after step (j1a), of:

(j1b) interpolating between ordered points in the closed ordered file to obtain interpolated points; and

(j1c) inserting the interpolated points in order into the closed ordered file.

17. The method of claim 13 wherein the target image is derivable from a compressed IFS code.

18. The method of claim 13 wherein the target image is a random fractal surface.

19. The method of claim 13 wherein the target image is a dynamical system mapped image sorted according to like colors.

20. The method of claim 13 wherein the target image is a bitmapped image sorted according to like colors.