Apparatus and method for picture representation by data compression

• US 5,510,838 A
• Filed: 11/22/1994
• Issued: 04/23/1996
• Est. Priority Date: 03/22/1992
• Status: Expired due to Fees

• Current Assignee: IGP Research and Development Limited
• Original Assignee: IGP Research and Development Limited
• Inventors: Briskin, Miriam, Elihai, Yoram, Yomdin, Yosef
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): Le, Vu
• Application Number:
  US08/343,210
• Time in Patent Office: 518 Days
• Field of Search: 348/384, 348/390, 348/429, 348/671
• US Class Current: 348/384.1
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

Processes for pictorial representation by data compression including dividing a picture into regions of designated brightness values, fixing a characteristic scale for each region representing a number of pixels, dividing each region into cells, identifying each cell representing the basic structure of each cell by way of models, and storing and/or transmitting the data for each such model in the form of primary compression of the picture.

Claims

1. A process of picture representation by data compression which comprises the steps of:

subdividing the picture into regions;

registering for each region a set of brightness values;

fixing for each region a characteristic scale in terms of a number of pixels;

dividing each region into cells, each of said cells comprising a number of pixels defined by two coordinates, said cells having a linear dimension in the order of said characteristic scale;

identifying in each cell basic structures chosen from among smooth areas, positive and negative hills, and curvilinear structures chosen from among edges and ridges;

constructing for said curvilinear structures geometric models comprising lines approximating the center lines of said structures and parameters defining the profiles of said structures;

associating to each of said smooth areas, positive and negative hills and geometric models of curvilinear structures a mathematical model;

condensing said mathematical models to define a global mathematical model for the cell;

quantizing and encoding the data defining said global mathematical model; and

storing and/or transmitting said data as representing the primary compression for the picture.

2. Process according to claim 1, further comprising the step of decompressing said data to reconstruct the picture.

3. Process according to claim 1, wherein said geometric and mathematical models, approximate said structures, and the degree of approximation is predetermined.

4. Process according to claim 1, wherein the basic structures are mathematically defined through the derivatives of a brightness function.

5. Process according to claim 4, wherein the brightness function is approximated by an approximating function p(x,y), where x and y are the coordinate system of said region, and where p(x,y) is a polynomial of the second degree having the form p(x,y)=a₀₀ +a₁₀ x+a₀₁ y+a₂₀ x² +a₁₁ xy+a₀₂ y².

6. Process according to claim 1, comprising defining a number of said models and associating to each of said models a code identifying each of said models, said each model being defined by said code and by its parameters.

7. Processing according to claim 1, comprising eliminating information having a limited psycho-visual significance by dropping some models and eliminating some excessive parameters of the models that are retained.

8. Process according to claim 4, comprising assigning each grid point to one of three domains A₁, A₂ and A₃, wherein:

domain A₁ contains all the points where all the derivatives of the approximating function p of orders 1 and 2 do not exceed a threshold T₁,

domain A₂ includes the grid points where the gradient of the approximating function p is large; and

domain A₃ includes the grid points in which the second order derivatives are bigger than a threshold T₃, while |grad(p(x,y))| does not exceed another threshold T₂ ; and

identifying in the domains the basic structures.

9. Process according to claim 8, wherein the domain A₁ is the set of the points of the grid for which

10. Process according to claim 1, which comprises the steps of:

1) registering the values of the brightness function z=f(x,y);

2) determining a window and a grid related thereto;

3) for each grid point, approximating the brightness function z(x,y) by an approximating function;

4) fixing a number of thresholds;

5) assigning each grid point to one of three domains A₁, A₂ and A₃ ;

6) identifying in the domains the basic structures;

7) approximating the curvilinear basic structures by lines related to their center lines and parameters related to their profiles;

9) representing the basic structures by mathematical models;

10) interrelating the models thus constructed to construct a global model;

12) quantizing the data thus obtained; and

13) encoding the same.

11. Process according to claim 1 wherein the characteristic scale is comprised between 6 and 48 pixels.

12. Process according to claim 10, wherein the window has a linear dimension comprised between 2 and 6 pixels.

13. Process according to claim 12, wherein the window has a linear dimension chosen from among 3 and 4 pixels.

14. Process according to claim 1 or 10, wherein the data quantization consists in substituting the values of the compressed data by the closest of a predetermined set of values.

15. Process according to claim 1, comprising encoding the compression data by representing the corresponding quantized data in the form of a binary file.

16. Process according to claim 1, comprising repeating the steps of said process for a set of brightness functions chosen from those representing the basic colors or those representing a monochrome signal and color data information carrying signals.

17. Process according to claim 1 comprising carrying out its operations for one of a set brightness functions chosen from those representing the basic colors or those representing a monochrome signal and color data information carrying signals, retaining the geometric parameters found for the models of said one brightness function and repeating said operations for the other brightness functions of the same set and using the same models with the said geometric parameters and the appropriate brightness parameters for each of the other brightness functions of the same set.

18. Process according to claim 10, wherein the window is a square having a side of a few pixels and the grid is constituted by the pixels themselves, if the side is an uneven number of pixels, and is constituted by the central points between the pixels, if the side is an even number of pixels.

19. Process according to claim 1, wherein the processing comprises one or more operations chosen from among further compression, picture comparison, feature stressing, picture enhancement, creation of visual effects, color operations, geometric transformations, 3D-geometric transformations and texture creation.

20. Process according to claim 1, wherein the information defining the brightness distribution of the various colors is a function of time.

21. Process according to claim 1, wherein the characteristic scale is between 6 and 48 pixels.

22. Process according to claim 1, wherein said picture comprises a plurality of video sequences, wherein only a subsequence of frames is compressed, and the intermediate frames are represented by the same models as the control frames, with the parameters obtained by interpolation from the control frames.

23. Process according to claim 1 wherein the steps 5 and 6 are performed by choosing among the prefixed list of models, those which (after minimization with respect to the parameters) provide the best approximation of the picture.

26. A process according to claim 1, wherein the basic structures are chosen from among smooth areas, positive and negative hills, edges and ridges, and saddles.

27. A process according to claim 1, wherein geometric and mathematical models are constructed for only part of the basic structures.

28. A process according to claim 1, wherein the condensing of the models to define a global model comprises eliminating at least one of the mathematical models.

24. A process of representing a picture by data, comprising the steps of:

subdividing the picture into regions;

registering for each region a set of brightness values, said set of brightness values collectively defining a brightness function;

dividing each region into cells, each of said cells comprising a number of pixels having a location defined by two coordinates;

identifying in each said cell basic structures chosen among;

(a) background areas wherein the values of said brightness function change slowly;

(b) curvilinear edges having a center line wherein on one side of said edge the values of said brightness function undergo a sharp change;

(c) curvilinear ridges having a center line, wherein the cross-sectional profile perpendicular to said center line is a bell-shaped curve; and

(d) hills wherein the brightness function value is a maximum or minimum and decreases or increases, respectively, in all directions from said hills;

constructing geometric models for those basic structures which are curvilinear, said geometric models comprising lines approximating the center lines of said structures and parameters defining the profiles of said structures;

associating a mathematical model with each of said background areas, hills and geometric models;

condensing said mathematical models to define a global mathematical model for the cell;

quantizing and encoding the data defining said global mathematical model; and

storing and/or transmitting said data.

25. A process according to claim 24, wherein the basic structures are chosen from among said background areas, said edges, said ridges and said hills, and chosen from among saddles comprising a central smooth region bounded by two edges, wherein the values of said brightness function increase at one edge and decrease at the other edge.