Method for content driven image compression

• US 20050131660A1
• Filed: 09/05/2003
• Published: 06/16/2005
• Est. Priority Date: 09/06/2002
• Status: Abandoned Application

• Current Assignee: Jacob Yadegar, Joseph Yadegar
• Original Assignee: Jacob Yadegar, Joseph Yadegar
• Inventors: Yadegar, Jacob, Yadegar, Joseph
• Application Number:
  US10/656,067
• Publication Number:
  US 20050131660A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06T 9/002 using neural networks
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

A method with related structures and computational components and modules for modeling data, particularly audio and video signals. The modeling method can be applied to different solutions such as 2-dimensional image/video compression, 3-dimensional image/video compression, 2-dimensional image/video understanding, knowledge discovery and mining, 3-dimensional image/video understanding, knowledge discovery and mining, pattern recognition, object meshing/tessellation, audio compression, audio understanding, etc. Data representing audio or video signals is subject to filtration and modeling by a first filter that tessellates data having a lower dynamic range. A second filter then further tessellates, if needed, and analyzes and models the remaining parts of data, not analyzable by first filter, having a higher dynamic range. A third filter collects in a generally lossless manner the overhead or residual data not modeled by the first and second filters. A variety of techniques including computational geometry, artificial intelligence, machine learning and data mining may be used to better achieve modeling in the first and second filters.

Claims

1. A method for modeling data using adaptive pattern-driven filters, comprising:

applying an algorithm to data to be modeled based on an approach selected from the group consisting of;

computational geometry;

artificial intelligence;

machine learning; and

data mining;

whereby

the data is modeled to enable better manipulation of the data.

2. A method for modeling data using adaptive pattern-driven filters as set forth in claim 1, further comprising:

the data to be modeled selected from the group consisting of;

2-dimensional still images;

2-dimensional still objects;

2-dimensional time-based objects;

2-dimensional video;

2-dimensional image recognition;

2-dimensional video recognition;

2-dimensional image understanding;

2-dimensional video understanding;

2-dimensional image mining;

2-dimensional video mining;

3-dimensional still images;

3-dimensional still objects;

3-dimensional video;

3-dimensional time-based objects;

3-dimensional object recognition;

3-dimensional image recognition;

3-dimensional video recognition;

3-dimensional object understanding;

3-dimensional object mining;

3-dimensional video mining;

N-dimensional objects where N is greater than 3;

N-dimensional time-based objects;

Sound patterns; and

Voice patterns.

3. A method for modeling data using adaptive pattern-driven filters as set forth in claim 1, further comprising:

the data to be modeled selected from the group consisting of;

generic data of generic nature wherein no specific characteristics of the generic data are know to exist within different parts of the data; and

class-based data of class-based nature wherein specific characteristics are known to exist within different parts of the class-based data, the specific characteristics enabling advantage to be taken in modeling the class-based data.

4. A method for modeling data using adaptive pattern-driven filters as set forth in claim 3, further comprising:

an overarching modeling meta-program generating an object-program for the data.

5. A method for modeling data using adaptive pattern-driven filters as set forth in claim 4, further comprising:

the object-program generated by the meta-program selected from the group consisting of;

a codec, a modeler, and a combination of both.

6. A method for modeling data using adaptive pattern-driven filters as set forth in claim 1, further comprising:

the data is modeled to enable the data being compressed for purposes of reducing overall size of the data.

7. A method for modeling data using adaptive pattern-driven filters as set forth in claim 1, wherein the algorithm applied to the data further comprises:

providing a linear adaptive filter adapted to receive data and model the data that have a low to medium range of intensity dynamics;

providing a non-linear adaptive filter adapted to receive the data and model the data that have medium to high range of intensity dynamics; and

providing a lossless filter adapted to receive the data and model the data not modeled by the linear adaptive filter and the non-linear adaptive filter, including residual data from the linear and non-linear adaptive filters.

8. A method for modeling data as set forth in claim 7, wherein the linear adaptive filter further comprises:

tessellation of the data.

9. A method for modeling data as set forth in claim 8, wherein the tessellation of the data further comprises:

tessellation of the data as viewed from computational geometry.

10. A method for modeling data as set forth in claim 8, wherein the tessellation of the data is selected from the group consisting of planar tessellation and spatial (volumetric) tessellation.

11. A method for modeling data as set forth in claim 8, wherein the tessellation of the data is achieved by a methodology selected from the group consisting of:

a combination of regression techniques;

a combination of optimization methods including linear programming;

a combination of optimization methods including non-linear programming; and

a combination of interpolation methods.

12. A method for modeling data as set forth in claim 10, wherein the planar tessellation of the data comprises triangular tessellation.

13. A method for modeling data as set forth in claim 10, wherein the spatial tessellation of the data comprises tessellation selected from the group consisting of tetrahedral tessellation and tessellation of a 3-dimensional geometrical shape.

14. A method for modeling data as set forth in claim 8, wherein the tessellation of the data is executed by an approach selected from the group consisting of breadth-first, depth-first, best-first, any combination of these, and any method of tessellation that approximates the data subject to an error tolerance.

15. A method for modeling data as set forth in claim 12, wherein the tessellation of the data is selected from the group consisting of Peano-Cezaro decomposition, Sierpiski decomposition, Ternary triangular decomposition, Hex-nary triangular decomposition, any other triangular decomposition, and any other geometrical shape decomposition.

16. A method for modeling data as set forth in claim 7, wherein the non-linear adaptive filter further comprises:

a filter modeling non-planar parts of the data using primitive data patterns.

17. A method for modeling data as set forth in claim 16, further comprising:

the modeling of the non-planar parts of the data performed using a methodology selected from the group consisting of;

artificial intelligence;

machine learning;

knowledge discovery;

mining;

and pattern recognition.

18. A method for modeling data as set forth in claim 16, further comprising:

training the non-linear adaptive filter at a time selected from the group consisting of;

prior to run-time application of the non-linear adaptive filter; and

at run-time application of the non-linear adaptive filter, the non-linear adaptive filter becoming evolutionary and self-improving.

19. A method for modeling data as set forth in claim 16, wherein the non-linear adaptive filter further comprises:

a hash-function data-structure based on prioritization of tessellations, the prioritization based on available information within and surrounding a tessellation with the prioritization of the tessellation for processing being higher according to higher availability of the available information.

20. A method for modeling data as set forth in claim 16, wherein the non-linear adaptive filter further comprises:

a hierarchy of learning units based on primitive data patterns; and

the learning units integrating clusters selected from the group consisting of;

neural networks;

mixtures of Gaussians;

support vector machines;

Kernel functions;

genetic programs;

decision trees;

hidden Markov models;

independent component analysis;

principle component analysis; and

other learning regimes.

21. A method for modeling data as set forth in claim 20, wherein the hierarchy of learning units provide machine intelligence.

22. A method for modeling data as set forth in claim 20, wherein the primitive data patterns include a specific class of data.

23. A method for modeling data as set forth in claim 22, wherein the specific class of data is selected from the group consisting of:

2-dimensional data;

3-dimensional data; and

N-dimensional data where N is greater than 3.

24. A method for modeling data as set forth in claim 16, further comprising:

providing a set of tiles approximating the data;

providing a queue of the set of tiles for input to the non-linear adaptive filter;

the non-linear adaptive filter processing each tile in the queue;

for each tile selected, the non-linear adaptive filter determining if the selected tile is within a tolerance of error;

for each selected tile within the tolerance of error, the tile is returned as a terminal tile;

for each selected tile outside the tolerance of error, the selected tile is decomposed into smaller subtiles which are returned to the queue for further processing.

25. A method for compressing data, comprising:

providing a linear adaptive filter adapted to receive data and compress the data that have low to medium energy dynamic range;

providing a non-linear adaptive filter adapted to receive the data and compress the data that have medium to high energy dynamic range; and

providing a lossless filter adapted to receive the data and compress the data not compressed by the linear adaptive filter and the non-linear adaptive filter;

whereby

data is being compressed for purposes of reducing its overall size.

26. A method for compressing data as set forth in claim 25, wherein the linear adaptive filter further comprises:

tessellation of the data.

27. A method for compressing data as set forth in claim 26, wherein the tessellation of the data is selected from the group consisting of planar tessellation and spatial tessellation.

28. A method for compressing data as set forth in claim 27, wherein the planar tessellation of the data comprises triangular tessellation.

29. A method for compressing data as set forth in claim 27, wherein the spatial tessellation of the data comprises tetrahedral tessellation.

30. A method for compressing data as set forth in claim 26, wherein the tessellation of the data is selected from the group consisting of breadth-first, depth-first, best-first, any combination of these, and any method of tessellation that approximates the data filtered by the linear adaptive filter within selectably acceptable limits of error.

31. A method for compressing data as set forth in claim 28, wherein the tessellation of the data is selected from the group consisting of Peano-Cezaro decomposition, Sierpiski decomposition, Ternary triangular decomposition, Hex-nary triangular decomposition, any other triangular decomposition, and any other geometrical shape decomposition.

32. A method for compressing data as set forth in claim 25, wherein the non-linear adaptive filter further comprises:

a filter modeling non-planar parts of the data using primitive image patterns.

33. A method for compressing data as set forth in claim 32, wherein the non-linear adaptive filter further comprises:

a hash-function data-structure based on prioritization of tessellations, the prioritization based on available information within and surrounding a tessellation with the prioritization of the tessellation for processing being higher according to higher availability of the available information.

34. A method for compressing data as set forth in claim 32, wherein the non-linear adaptive filter further comprises:

a hierarchy of learning units based on primitive data patterns; and

the learning units integrating clusters selected from the group consisting of;

neural networks;

mixtures of Gaussians;

support vector machines;

Kernel functions;

genetic programs;

decision trees;

hidden Markov models;

independent component analysis;

principle component analysis; and

other learning regimes.

35. A method for compressing data as set forth in claim 34, wherein the primitive data patterns include a specific class of images.

36. A method for compressing data as set forth in claim 32, further comprising:

providing a set of tiles approximating the data;

providing a queue of the set of tiles for input to the non-linear adaptive filter;

the non-linear adaptive filter processing each tile in the queue;

for each tile selected, the non-linear adaptive filter determining if the selected tile is within a tolerance of error;

for each selected tile within the tolerance of error, the tile is returned as a terminal tile;

for each selected tile outside the tolerance of error, the selected tile is decomposed into smaller subtiles which are returned to the queue for further processing.

37. A method for modeling an image for compression, comprising:

obtaining an image;

performing computational geometry to the image; and

applying machine learning to decompose the image;

whereby

the image is represented in a data form having a reduced size.

38. A method for modeling an image for compression as set forth in claim 37, further comprising:

recomposing the image from the data form representation by machine learning.

39. A method for modeling an image for compression as set forth in claim 38, further comprising:

the image selected from the group consisting of;

a video image; and

a series of video images.

40. A method for modeling an image for compression, comprising:

formulating a data structure by using a methodology selected from the group consisting of;

computational geometry;

artificial intelligence;

machine learning;

data mining; and

pattern recognition techniques; and

creating a decomposition tree based on the data structure.

41. A method for modeling an image for compression as set forth in claim 40, wherein creating the decomposition tree is achieved by application of an approach selected from the group consisting of:

Peano-Cezaro decomposition;

Sierpiski decomposition;

Ternary triangular decomposition;

Hex-nary triangular decomposition;

any other triangular decomposition approach; and

any other geometrical shape decomposition method.

42. A method for modeling an image for compression as set forth in claim 41, wherein an image to be modeled is selected from the group consisting of:

a video image; and

a series of video images.

43. A method for modeling data using adaptive pattern-driven filters, comprising:

applying an algorithm to data to be modeled based on an approach selected from the group consisting of;

computational geometry;

artificial intelligence;

machine learning; and

data mining;

the data to be modeled selected from the group consisting of;

2-dimensional still images;

2-dimensional still objects;

2-dimensional time-based objects;

2-dimensional video;

2-dimensional image recognition;

2-dimensional video recognition;

2-dimensional image understanding;

2-dimensional video understanding;

2-dimensional image mining;

2-dimensional video mining;

3-dimensional still images;

3-dimensional still objects;

3-dimensional video;

3-dimensional time-based objects;

3-dimensional object recognition;

3-dimensional image recognition;

3-dimensional video recognition;

3-dimensional object understanding;

3-dimensional object mining;

3-dimensional video mining;

N-dimensional objects where N is greater than 3;

N-dimensional time-based objects;

sound patterns;

voice patterns;

generic data of generic nature wherein no specific characteristics of the generic data are know to exist within different parts of the data; and

class-based data of class-based nature wherein specific characteristics are known to exist within different parts of the class-based data, the specific characteristics enabling advantage to be taken in modeling the class-based data;

an overarching modeling meta-program generating an object-program for the data;

the object-program generated by the meta-program selected from the group consisting of;

a codec, a modeler, and a combination of both;

the data is modeled to enable the data being compressed for purposes of reducing overall size of the data;

the algorithm applied to the data including providing a linear adaptive filter adapted to receive data and model the data that have a low to medium range of intensity dynamics, providing a non-linear adaptive filter adapted to receive the data and model the data that have medium to high range of intensity dynamics, and providing a lossless filter adapted to receive the data and model the data not modeled by the linear adaptive filter and the non-linear adaptive filter, including residual data from the linear and non-linear adaptive filters;

linear adaptive filter including tessellation of the data including tessellation of the data as viewed from computational geometry, the tessellation of the data selected from the group consisting of planar tessellation and spatial (volumetric) tessellation;

the planar tessellation including triangular tessellation;

the spatial tessellation of the data comprises tessellation selected from the group consisting of tetrahedral tessellation and tessellation of a 3-dimensional geometrical shape;

the tessellation of the data achieved by a methodology selected from the group consisting of;

a combination of regression techniques;

a combination of optimization methods including linear programming;

a combination of optimization methods including non-linear programming;

a combination of interpolation methods;

the tessellation of the data executed by an approach selected from the group consisting of breadth-first, depth-first, best-first, any combination of these, and any method of tessellation that approximates the data subject to an error tolerance;

the tessellation of the data is selected from the group consisting of Peano-Cezaro decomposition, Sierpiski decomposition, Ternary triangular decomposition, Hex-nary triangular decomposition, any other triangular decomposition, and any other geometrical shape decomposition;

the non-linear adaptive filter including a filter modeling non-planar parts of the data using primitive data patterns including a specific class of data selected from the group consisting of;

2-dimensional data;

3-dimensional data;

N-dimensional data where N is greater than 3;

the non-linear adaptive filter including a hash-function data-structure based on prioritization of tessellations, the prioritization based on available information within and surrounding a tessellation with the prioritization of the tessellation for processing being higher according to higher availability of the available information, and including a hierarchy of learning units based on primitive data patterns, the hierarchy of learning units providing machine intelligence, the learning units integrating clusters selected from the group consisting of;

neural networks;

mixtures of Gaussians;

support vector machines;

Kernel functions;

genetic programs;

decision trees;

hidden Markov models;

independent component analysis;

principle component analysis;

other learning regimes;

the modeling of the non-planar parts of the data performed using a methodology selected from the group consisting of;

artificial intelligence;

machine learning;

knowledge discovery;

mining; and

pattern recognition;

training the non-linear adaptive filter at a time selected from the group consisting of;

prior to run-time application of the non-linear adaptive filter;

at run-time application of the non-linear adaptive filter, the non-linear adaptive filter becoming evolutionary and self-improving;

providing a set of tiles approximating the data;

providing a queue of the set of tiles for input to the non-linear adaptive filter;

the non-linear adaptive filter processing each tile in the queue;

for each tile selected, the non-linear adaptive filter determining if the selected tile is within a tolerance of error;

for each selected tile within the tolerance of error, the tile is returned as a terminal tile; and

for each selected tile outside the tolerance of error, the selected tile is decomposed into smaller subtiles which are returned to the queue for further processing;

whereby

the data is modeled to enable better manipulation of the data.

44. A method for compressing data, comprising:

providing a linear adaptive filter adapted to receive data and compress the data that have low to medium energy dynamic range, the linear adaptive filter including tessellation of the data;

the tessellation of the data selected from the group consisting of planar tessellation and spatial tessellation, wherein the planar tessellation of the data comprises triangular tessellation and wherein the spatial tessellation of the data comprises tetrahedral tessellation;

the tessellation of the data selected from the group consisting of breadth-first, depth-first, best-first, any combination of these, and any method of tessellation that approximates the data filtered by the linear adaptive filter within selectably acceptable limits of error;

the tessellation of the data selected from the group consisting of Peano-Cezaro decomposition, Sierpiski decomposition, Ternary triangular decomposition, Hex-nary triangular decomposition, any other triangular decomposition, and any other geometrical shape decomposition;

providing a non-linear adaptive filter adapted to receive the data and compress the data that have medium to high energy dynamic range;

the non-linear adaptive filter including a filter modeling non-planar parts of the data using primitive image patterns, the primitive image patterns including a specific class of images;

the non-linear adaptive filter including a hash-function data-structure based on prioritization of tessellations, the prioritization based on available information within and surrounding a tessellation with the prioritization of the tessellation for processing being higher according to higher availability of the available information;

the non-linear adaptive filter including a hierarchy of learning units based on primitive data patterns, the learning units integrating clusters selected from the group consisting of;

neural networks;

mixtures of Gaussians;

support vector machines;

Kernel functions;

genetic programs;

decision trees;

hidden Markov models;

independent component analysis;

principle component analysis;

other learning regimes;

providing a lossless filter adapted to receive the data and compress the data not compressed by the linear adaptive filter and the non-linear adaptive filter;

providing a set of tiles approximating the data;

providing a queue of the set of tiles for input to the non-linear adaptive filter;

the non-linear adaptive filter processing each tile in the queue;

for each tile selected, the non-linear adaptive filter determining if the selected tile is within a tolerance of error;

for each selected tile within the tolerance of error, the tile is returned as a terminal tile;

for each selected tile outside the tolerance of error, the selected tile is decomposed into smaller subtiles which are returned to the queue for further processing;

whereby

such that data is being compressed for purposes of reducing its overall size.

45. A method for modeling an image for compression, comprising:

obtaining an image;

performing computational geometry to the image;

applying machine learning to decompose the image such that the image is represented in a data form having a reduced size; and

recomposing the image from the data form representation by machine learning;

wherein

the image selected from the group consisting of;

a video image and a series of video images.

46. A method for modeling an image for compression, comprising:

formulating a data structure by using a methodology selected from the group consisting of;

computational geometry, artificial intelligence, machine learning, data mining, pattern recognition techniques; and

creating a decomposition tree based on the data structure, the decomposition tree is achieved by application of an approach selected from the group consisting of;

Peano-Cezaro decomposition, Sierpiski decomposition, Ternary triangular decomposition, Hex-nary triangular decomposition, any other triangular decomposition approach, any other geometrical shape decomposition method;

wherein

an image to be modeled is selected from the group consisting of a video image and a series of video images.

47. A data structure for use in conjunction with file compression, comprising:

binary tree bits;

an energy row;

a heuristic row; and

a residual energy entry.