Method for data compression by associating complex numbers with files of data values

• US 5,717,787 A
• Filed: 04/16/1996
• Issued: 02/10/1998
• Est. Priority Date: 04/16/1996
• Status: Expired due to Fees

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Kraay, Thomas Arthur, Hanks, David Carlton, Feo, John Thomas
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/633,386
• Time in Patent Office: 665 Days
• Field of Search: 382/232, 382/233, 382/241, 382/247, 382/248, 382/249, 382/253, 382/243, 395/13, 395/612, 364/715.02
• US Class Current: 382/232
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method for compressing data for storage or transmission. Given a complex polynomial and a value assigned to each root, a root generated data file (RGDF) is created, one entry at a time. Each entry is mapped to a point in a complex plane. An iterative root finding technique is used to map the coordinates of the point to the coordinates of one of the roots of the polynomial. The value associated with that root is assigned to the entry. An equational data compression (EDC) method reverses this procedure. Given a target data file, the EDC method uses a search algorithm to calculate a set of m complex numbers and a value map that will generate the target data file. The error between a simple target data file and generated data file is typically less than 10%. Data files can be transmitted or stored without loss by transmitting the m complex numbers, their associated values, and an error file whose size is at most one-tenth of the size of the input data file.

Claims

1. A method for compressing and uncompressing data for storage or transmission, wherein a data file is stored as a file of size N, and letting T be a function that maps integers to points in the complex plane, P be an m degree polynomial, and A be a function of the first derivative of P, and B be a function of the second derivative of P, and further letting C(i) be a map to a unique value for each root of P, where 1≦

i≦

m, then A and B are then iteratively solved for each z=T(i), 1≦

i≦

N, and a solution ultimately converges within some epsilon of one of the roots of P, for when z converges to root j, C(j) is assigned to z, and P, A and B can be defined for any m numbers in the complex plane and color function C to generate a data file of pixel values encoded by m complex numbers.

2. The method of claim 1, wherein given a data file of size N, the m complex numbers and value function C are found that encode said data file using an optimization method, wherein for a given target data file to compress, a main process is repeated until a solution sufficiently close to the target is found or some arbitrary maximum number of generations is exceeded, wherein said main process comprises producing a data file for each member of the generation, then evaluating each member'"'"'s fitness against the target, then scaling the fitness values, then creating N/2 couples of polynomials, where each couple is comprised of two polynomials randomly selected from the current generation, and where the probability of a member being assigned to a couple is in direct proportion to its scaled fitness value, and then, mating each couple to generate two children, allowing for characteristics of each parent to contribute to each child or crossover and allowing for mutation.

3. A method for compressing data for transmission, wherein given a complex polynomial and a value assigned to each root, a root generated data file (RGDF) is created, one entry at a time, and each entry is mapped to a point in a complex plane, then an iterative root finding technique is used to map the coordinates of the point to the coordinates of one of the roots of the polynomial, then the value associated with that root is assigned to the entry, whereafter an equational data compression (EDC) method is used to reverse such steps, wherein given a target data file, the EDC method uses a search algorithm to calculate a set of m complex numbers and a value map that will generate the target data file, wherein data files are transmitted by transmitting the m complex numbers, their associated values, and an error file.