Compressed image production storage transmission and processing

• US 5,410,643 A
• Filed: 08/18/1993
• Issued: 04/25/1995
• Est. Priority Date: 06/13/1990
• Status: Expired due to Fees

• Current Assignee: Efraim Paz, Yoram Elihai, Yossef Yomdin
• Original Assignee: Efraim Paz, Yoram Elihai, Yossef Yomdin
• Inventors: Elihai, Yoram, Paz, Efraim, Yomdin, Yossef
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): HUYNH, BA
• Application Number:
  US08/108,784
• Time in Patent Office: 615 Days
• Field of Search: 395/118-120, 395/127, 395/123, 395/136, 395/141, 395/142, 395/143, 395/165, 395/122
• US Class Current: 345/420
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A process for producing a compressed image of a color picture. The color picture is optically scanned to obtain an array of optical parameters representing the basic colors at each coordinate point of the picture which are then converted into digital values. From such digital values, a selection is made of sets of data values representing a series of elements of the picture having discontinuities therein. A model is formulated for each of the elements having a first component containing all of the discontinuities and a second component representing the differentiable content of the elements. The second component is represented by a Taylor polynomial having a selected polynomial degree of at least 2. A maximum allowable error is then selected. The coefficients of the polynomials of the second component are calculated at selected points of a grid with a grid pitch defined by a specified formula. A compressed color picture is derived from the data values constituting the compressed image.

Claims

1. Process for the production of a compressed image of a static or dynamic color picture, comprising the steps of:

(a) optical scanning said picture to form color corresponding to its basic colors including at least one color selected from the group consisting of magenta, cyan and yellow at all of the coordinate points of said picture;

(b) transforming said color values into an array of digital values;

(c) selecting from said array of digital values, sets of values representing a series of elements of said picture having discontinuities therein;

(d) storing said sets of values within a computer or other electronic storage device;

(e) for each of said elements of said picture, formulating a model, with said model having a first component incorporating the discontinuities of said element and a second component representing the differentiable content of said element, with said second component defined by Taylor polynomials having multiple coefficients;

(f) selecting a maximum allowable error for the model to establish a given precision for the image to be produced;

(g) defining a grid for said picture divided into different regions having multiple grid points and a grid pitch h determined by CMh^k+1 ≦

ε

, wherein C=1/(k+1)! and M is the maximum at each grid point of the absolute value of the derivatives of the grid k+1 of the differential component or components of the model;

(h) selecting the degree of Taylor polynomials equal to at least two;

(i) using a computer to derive from said models of said elements of said picture, an array of data values constituting a compressed image of said original picture based upon the selection of the degree of said polynomials and the maximum allowable error for said models with the coefficients of said Taylor polynomials computed along grid points for approximating the differentiable component of said models;

(j) storing in said computer, the values and parameters defining the first component of said models and the computed coefficients for the Taylor polynomials as the array of data values constituting a compressed image of the original picture;

(k) deriving from said array of optical data values corresponding for each of the identifiable coordinate points; and

(l) generating from said optical values, a color picture which is the compressed image of said original picture.

2. Process according to claim 1, wherein the grid is a square grid having a pitch of 6 pixels.

3. Process according to claim 1, wherein said picture has the form:

space="preserve" listing-type="equation">Φ

(x)=Hx.sub.0,a,b,c,d(x)÷

φ

(x)

wherein H is defined by H(x)=a(x-x₀)+b, if x≧

x₀ or H(x)=c(x-x₀)+d, if x is less than x₀.

4. Process according to claim 1, wherein said picture is a differentiable function of another function which embodies the non-differentiable characteristics of the object.

5. Process according to claim 1, further comprising constructing an adjusted image by applying to each differentiable component a Whitney subroutine, and minimizing the quantity W thus computed, under such constraints that the results of the minimization do not deviate from the initial data by more than the allowed error.

6. Process according to claim 1, further comprising rounding off the coefficients of said Taylor polynomial to a maximum allowable error greater than said maximum allowable error Σ

.

7. Process according to claim 1, further comprising the steps of constructing another grid which is sparser than said grid with a pitch determined by the resolution required by the lowest fineness of said components, deriving a second array of data values constituting a temporary compressed image of said picture;

subtracting the data values of said temporary image from the data values of said original image to obtain a residual image, and repeating the same steps for successively finer components, correspondingly obtaining successive residual images at increasingly higher resolutions.

8. Process according to claim 1, further comprising applying an encoding method to the coefficients of said Taylor polynomials.

9. Process according to claim 1, further comprising constructing a final compressed image by a procedure comprising the steps of dividing the domain in which the possibly image has been defined, into possibly overlapping regions by means of a grid with each region being a portion of the grid around a grid node, and constructing curves representing the Taylor polynomials of degree k from a coefficients defining the temporary image at each grid node.

10. Process according to claim 1, further comprising processing the data values defining the image of said picture for an intermediate image by applying an operator thereto.

11. A process as claimed in claim 1, wherein said maximum allowable error equals 5, said degree k of said polynomial equals 2 and said pitch h of said grid equals 6.

12. Process as claimed in claim 1, wherein said second component of said model is defined by minimizing a quantity representing the deviation from said array of digital values consisting of said first and second components.