Methods and apparatus for image compression by iterated function system

A random iteration method for decoding iterated function system compression codes to generate an image, comprising the steps of:

• receiving and storing a plurality of compression codes in a compression code memory;
• determining an initial point in a display memory;
• randomly selecting one of the compression codes in the compression code memory;
• performing an affine transformation on the initial point corresponding to the affine transformation represented by the selected compression code to move the initial point to a second point in the display memory;
• storing a picture element in the display memory at a memory location corresponding to the location of the second point;
• utilizing the second point from the preceding step as an initial point, repeating the steps of randomly selecting one of the compression codes, performing an affine transformation, and storing a picture element, until an output image converges to an attractor in the display memory;
• and
• displaying data corresponding to the stored picture elements in the display memory corresponding to the attractor as a decoded output image.

A deterministic method for decoding iterated function system compression codes to generate an image on a graphics display terminal, comprising the steps of:

• receiving and storing a plurality of n sets of compression codes;
• providing an initial image in a display memory associated with the graphics display terminal;
• performing transformations on the initial image in the memory corresponding to each of the n sets of compression codes;
• combining the results of the transformations so as to obtain a second image in the memory;
• utilizing the second image as the initial image, repeatedly iterating by carrying out the above steps, for a plurality of iterations of the n sets of compression codes, until an attractor stabilizes;
• storing in the memory a plurality of picture elements corresponding to the attractor as a final image;
• and
• displaying on the graphics display terminal data corresponding to the stored picture elements of the final image corresponding to the attractor as a decoded output image.

Apparatus for decoding iterated function system compression codes to generate an image by random iteration, comprising:

• a compression code memory for storing a plurality of compression codes;
• a display memory for storing an image being generated;
• means for determining an initial point in said display memory;
• means for randomly selecting one of said compression codes in said compression code memory;
• means for performing an affine transformation on said initial point corresponding to the affine transformation represented by said selected compression codes to move said initial point to a second point;
• means for storing a picture element in a display memory at a memory location in said display memory corresponding to the location of said second point;
• iteration means for repeatedly utilizing said second point as said initial point for subsequent operations of said compression code selecting means, said affine transformation means, and said picture element storing means, until an output image converges to an attractor in said display memory;
• and
• means for displaying data stored in said display memory corresponding to stored picture elements corresponding to said attractor as a decoded output image.

An apparatus for decoding iterated function system compression codes to generate an image by deterministic decoding, comprising:

• a compression code memory for storing a plurality of n sets of compression codes;
• a initial image display memory for storing an initial image;
• a generated image display memory for storing a generated image;
• means for providing an initial image in said initial image display memory;
• means for performing an affine transformation on said initial image in said initial image display memory corresponding to each of said sets of compression codes;
• means for combining the results of said affine transformations to produce a second image in said generated image display memory;
• means for transferring said second image from generated image display memory to initial image display memory;
• deterministic iteration means for causing said affine transformation means, said combining means, and said transferring means to repeatedly operate for a plurality of iterations of the n set of compression codes, until an attractor stabilizes;
• means for storing a plurality of picture elements corresponding to the attractor in said display memory;
• and
• means for displaying data corresponding to the stored picture elements stored in said display memory corresponding to said attractor as a decoded output image.

An apparatus for decoding a compressed image represented by a plurality of sets of compression codes, each one of said sets of compression codes having a contractivity factor S, where 0.ltoreq.S<1, and each one of said sets of compression codes having a probability code associated therewith, comprising:

• a compression code memory for storing a plurality of sets of input compression codes;
• a probability memory for storing the probability codes associated with each one of said sets of compression codes;
• means for storing said input compression codes in said compression code memory in addressable locations having addresses corresponding to said probability codes;
• a display memory corresponding to a display space for storing an image;
• a random number generator for generating a probability addresses which randomly vary;
• compression code selecting means responsive to said probability addresses for selecting compression codes stored at addresses in said compression code memory at a frequency corresponding to said probability codes, such that a compression code having a higher probability code is more likely to be selected than a compression code having a lower probability code;
• matrix processing means responsive to compression codes provided by said compression code selecting means for performing an approximately contractive affine transformation on an initial point in said display space to determine a second point in said display space;
• means for storing image data in said display memory corresponding to said second point in said display space;
• control means for causing said compression code selecting means and said matrix processing means to iteratively plot a plurality of points in said display space until an attractor of said compression codes stabilizes;
• means for storing data in said display memory corresponding to points plotted in said display space by said control means;
• and
• means for displaying the contents of said display memory after a plurality of iterations.

Apparatus for compressing an image represented by an array of pixels, comprising:

• a target memory means for storing an uncompressed input target image;
• means for generating, aligning, and overlaying a collage comprising a plurality of contractive affinely transformed copies of a portion of said target image with respect to said portion of said target image stored in said target memory means until particular geometric features of said portion of said target image are substantially covered by said collage;
• output means for providing, as a compressed image output, a plurality of compression codes corresponding to the numerical coefficients of said plurality of contractive affinely transformed copies of said portion of said target image;
• decoder means responsive to said compression codes for generating and storing an approximation image in said approximation memory means;
• an approximation image memory means for storing said approximation image;
• comparator means for comparing said target image stored in said target memory means to said approximation image stored in said approximation image memory means and for providing error data;
• affine transformation correction means responsive to said error data for modifying said collage of contractive affinely transformed copies of said portion of said target image to minimize the number of said compression codes.

A method of compressing an image represented by an array of pixels, comprising:

• storing an uncompressed input target image in a target memory;
• generating contractive transformed copies of a portion of the target image;
• aligning the contractive transformed copies with respect to the portions of said target image stored in the target memory until particular geometric features of the portions of the target image are substantially covered by a collage;
• providing, as a compressed image output, a plurality of compression codes corresponding to the numerical coefficients of the plurality of contractive transformed copies of the portion of the target image;
• decoding the compression codes to generate approximation image;
• storing the approximation image in an approximation image memory;
• comparing the target image stored in the target memory to the approximation image stored in the approximation image memory means and providing error data as a function of the error between the two images;
• modifying the collage of contractive transformed copies of the portion of the target image in response to the error data to minimize the number of compression codes.

In an image compression system, a method for encoding rendering information for an image represented by an array of pixels, each pixel having a rendering value, comprising the steps of, in a programmed computer:

• determining the number of different rendering values in an input image to be encoded;
• determining a measure corresponding to the cumulation of the rendering values for all pixels in the image;
• assigning a weighting to each one of the number of different rendering values;
• assigning a rendering mapping of each one of the rendering values to one of the different renderings to be encoded;
• encoding predetermined features of the input image with an iterated function system to as to obtain a plurality of sets of transformation coefficients representing the image without color rendering;
• assigning a probability code to each one of the sets of transformation coefficients in relation to the relative weight assigned to the number of different rendering values;
• and
• providing as an encoded output a set of compression codes comprising a plurality of sets of transformation coefficients and a corresponding probability code for each one of the sets of transformation coefficients.

A method for compressing images, comprising the steps of, in a programmed computer:

• storing an input target image to be compressed in a target memory;
• selecting geometric regions of the input target image having predetermined similar fractal characteristics;
• determining a separate set of iterated function system codes corresponding to and representing each of said selected geometric regions, to thereby obtain a plurality of sets of iterated function system codes;
• determining a residual set of data corresponding to those residual portions of the image not represented by one of said plurality of sets of iterated function system codes;
• encoding the residual set with a conventional data compression scheme to obtain a set of conventional compression codes;
• providing as a compressed output representing the entire image a set of iterated function system codes representing the selected geometric regions and a set of conventional compression codes representing the residual portions of the image.

A deterministic method for decoding iterated function system compression codes to generate an image by parallel processing, comprising the steps of:

• receiving and storing a plurality of n sets of compression codes in a decoder;
• providing an initial image in a display memory;
• concurrently performing in a separate one of a plurality of processing units each of the n transformations corresponding to the stored compression codes on the initial image so as to generate n transformed images,
• forming a second image corresponding to the union of the n transformed images;
• repeatedly iterating by carrying out the above steps of concurrently performing n transformations and forming the second image, wherein, for each iteration, the second image formed in the previous iteration is utilized as the initial image for the following iteration and continuing such iteration until an attractor image stabilizes;
• and
• displaying data corresponding to the attractor as a decoded output image.

A random iteration method for decoding iterated system compression codes to generate an image by parallel processing, comprising the steps of:

• receiving and storing a plurality of compression codes in a decoder;
• determining a plurality n of initial points in a display memory;
• randomly selecting n of the compression codes with replacement;
• concurrently applying the transformation corresponding to each of the selected compression codes in one of a plurality of processing units to a particular initial point selected from the plurality of initial points without replacement to generate a set of n transformed points;
• repeatedly iterating by carrying out the above steps of randomly selecting n compression codes and applying the corresponding transformations, wherein for each iteration, the set of n transformed points generated in the previous iteration is utilized as the plurality of n initial points for the following iteration, and continuing such iteration until an attractor image stabilizes;
• and
• displaying data corresponding to the attractor as decoded output image.

A random iteration method for decoding iterated system compression codes to generate an image by parallel processing, comprising the steps of:

• receiving and storing a plurality of compression codes in a decoder;
• independently and concurrently, with a plurality of n processors, and until an attractor image stabilizes, carrying out the following steps of:
• determining an initial point in a display memory,
• randomly selecting one of the plurality of compression codes,
• applying the transformation corresponding to the selected compression code to the initial point to generate a transformed point, and
• repeatedly iterating by carrying out the above steps of selecting a compression code and applying the corresponding transformation, wherein for each iteration, the transformed point generated in the previous iteration is utilized as the initial point of the following iteration;
• and
• after the attractor image stabilizes, displaying data corresponding to the attractor as a decoded output image.