System and method for coding data

• US 7,123,774 B2
• Filed: 11/27/2002
• Issued: 10/17/2006
• Est. Priority Date: 11/27/2002
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Dhavala, Somasekhar, Wheeler, Frederick Wilson
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US10/306,441
• Publication Number:
  US 20040101203A1
• Time in Patent Office: 1,420 Days
• Field of Search: 382/232, 382/240, 382/248, 707/1, 707/4, 707/201, 707/202, 707/100, 711/108, 348/398.1, 348/406.1
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A universal position coding method and system are provided for coding uncompressed data. Data symbols are assigned to a bin portion and a raw portion, and a data tree structure is utilized. A top down approach involves initializing a data tree based on the bit depth of the data; splitting a bin to form two separate bins based on a predetermined splitting condition; and repeating the splitting step until a terminating condition is achieved. A bottom up approach involves forming a data tree; merging two existing bins to form a new bin based on a merging condition; and repeating the merging step until a terminating condition is achieved.

Claims

1. A method for coding data, said method comprising:

receiving data;

initializing a top tree bin structure based on a bit depth of said data, said top tree bin structure comprising a plurality of top tree bins, each of said top tree bins comprising a plurality of top tree symbols;

splitting any one of said top tree bins into two split top tree bins based on a splitting condition;

wherein said splitting condition is determined based on pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins, said splitting step comprising;

adding bin information or loss of each one of said plurality of child top tree bins,

splitting one of said top tree bins comprising said plurality of child top tree bins that correspond to a minimum increase in bin information or a maximum reduction in loss;

repeating said splitting step until a terminating condition is reached; and

generating said desired bin structure using said plurality of top tree bins and said plurality of said split top tree bins;

coding the date using the desired bin structure.

2. The method of claim 1, wherein a top tree bin having raw equal to zero is not split.

3. The method of claim 1, wherein each one of said plurality of top tree symbols represents said data.

4. The method of claim 1, wherein said splitting condition is determined based on maximum loss.

5. The method of claim 1, wherein said splitting condition is determined based on maximum bit budget.

6. The method of claim 1, wherein said splitting step comprises:

pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins, splitting one of said top tree bins comprising one of said plurality of child top tree bins that correspond to minimum increase in bit budget.

7. The method of claim 1, wherein a mathematical operation is a wavelet transform operation and an inverse mathematical operation is an inverse wavelet transform operation.

8. A method for coding uncompressed data, said data having a predetermined bit depth, the steps of said method, comprising:

receiving said uncompressed data;

initializing a bottom tree bin structure, said bottom tree bin structure comprising a plurality of bottom tree bins, each of said bottom tree bins comprising a plurality of bottom tree symbols;

merging at least two of said plurality of bottom tree bins based on a merging condition to generate a plurality of merged bottom tree bins;

repeating said merging step until a terminating condition is reached; and

generating said desired bin structure using said plurality of bottom tree bins and said plurality of said merged bottom tree bins; and

coding the data using the desired bin structure.

9. The method of claim 8, wherein said merging condition is determined based on merging two of said plurality of bins that corresponds to minimum loss.

10. The method of claim 8, wherein said merging condition is determined based on merging two of said plurality of bins that corresponds to minimum bit budget.

11. The method of claim 8, wherein each one of said plurality of bottom tree symbols represents said uncompressed data.

12. The method of claim 8, further comprising:

performing a mathematical operation said uncompressed data; and

performing an inverse mathematical operation on said decompressed data.

13. The method of claim 8, wherein a mathematical operation is a wavelet transform operation and said inverse mathematical operation is an inverse wavelet transform operation.

14. The method of claim 8, wherein said uncompressed data represents an image.

15. A data coding system for coding uncompressed data using a desired bin structure, the data coding system comprising:

a universal position coding system for generating a desired bin structure, said a universal position coding block comprising;

an initializing block, said initializing block configured for initializing a top tree bin structure; and

a processing block coupled to said initializing block and configured to split any one of said plurality of top tree bins based on a splitting condition to generate a plurality of split top tree bins; and

said processing block is further configured to split said plurality of top tree bins till a terminating condition is reached to generate said desired bin structure using said plurality of top tree bins and said plurality of said split top tree bins;

wherein said splitting condition is determined based on;

pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins,

adding the bin-information or loss of each one of said plurality of child top tree bins,

splitting one of said top tree bins comprising said plurality of child top tree bins that correspond to a minimum increase in bin-information or a maximum reduction in loss.

16. The data coding system of claim 15, wherein said splitting condition is determined based on pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins,

splitting one of said top tree bins comprising one of said plurality of child top tree bins that correspond to minimum increase in bit budget.

17. The data coding system of claim 15, wherein each of said plurality of top tree symbols represents said uncompressed data.

18. The data coding system of claim 15, further comprising:

a mathematical operation block coupled to an entropy encoder block, said mathematical operation block configured for performing a mathematical operation on said uncompressed data; and

an inverse mathematical operation black coupled to an entropy decoder block, said inverse mathematical operation block configured for performing an inverse mathematical operation on said decompressed data.

19. The data coding system of claim 18, wherein said mathematical operation is a wavelet transform operation and said inverse mathematical operation is an inverse wavelet transform operation.

20. A data coding system comprising for coding uncompressed data using a desired bin structure, the data coding system comprising:

a universal position coding system for generating a desired bin structure, said a universal position coding block comprising;

an initializing block, initializes a bottom tree bin structure, said bottom tree bin structure comprising a plurality of bottom tree bins;

wherein each of said bottom tree bins comprises a plurality of bottom tree symbols;

a processing block coupled to said initializing block;

said processing block merges at least two of said plurality of bottom tree bins based on a merging condition to generate a plurality of merged bottom tree bins; and

said processing block further merges said plurality of bottom tree bins till a terminating condition is reached; and

said processing block generates said desired bin structure using said plurality of bottom tree bins and said plurality of said merged bottom tree bins.

21. The data coding system of claim 20, wherein the merging condition is determined based on merging at least two of said plurality of bottom tree bins that corresponds to maximum reduction in bin information.

22. The data coding system of claim 20, wherein the merging condition is determined based on merging at least two of said plurality of bottom tree bins that corresponds to minimum increase in loss.

23. The data coding system of claim 20, wherein the merging condition is determined based on merging at least two of said plurality of bottom tree bins that corresponds to minimum increase in bit budget.

24. The data coding system of claim 20, wherein each one of said plurality of bottom tree symbols represents said uncompressed data.

25. A computer-readable medium storing computer instructions for instructing a computer system to code uncompressed data, the computer instructions including:

initializing a top tree bin structure, said top tree bin structure comprising a plurality of top tree bins;

wherein each of said top tree bins comprises a plurality of top tree symbols;

splitting said any one of said plurality of top tree bins based on a splitting condition to generate a plurality of split top tree bins;

further splitting said plurality of top tree bins till a terminating condition is reached; and

initializing a bottom tree bin structure, said bottom tree bin structure comprising a plurality of bottom tree bins;

wherein each of said bottom tree bins comprises a plurality of bottom tree symbols;

merging at least two of said plurality of bottom tree bins based on a merging condition to generate a plurality of merged bottom tree bins;

further merging said plurality of bottom tree bins till a terminating condition is reached; and

generating a desired bin structure using said plurality of top tree bins, said plurality of split top tree bins, said plurality of bottom tree bins and said plurality of merged bottom tree bins.

26. The computer-readable medium of claim 25, wherein each of said plurality of top tree symbols represents said uncompressed data.

27. The computer-readable medium of claim 25, wherein each one of said plurality of bottom tree symbols represents said uncompressed data.

28. The computer-readable medium of claim 25, further comprising:

performing a mathematical operation said uncompressed data; and

performing an inverse mathematical operation on said decompressed data.

29. The computer-readable medium of claim 28, wherein said mathematical operation is a wavelet transform operation and said inverse mathematical operation is an inverse wavelet transform operation.

30. The computer-readable medium of claim 25, wherein said uncompressed data represents an image.

31. A method for generating a desired bin structure to code an uncompressed date, said method comprising:

initializing a top tree bin structure, said top tree bin structure comprising a plurality of top tree bins;

wherein each of said top tree bins comprises a plurality of top tree symbols;

splitting said any one of said plurality of top tree bins based on a splitting condition to generate a plurality of split top tree bins;

further splitting said plurality of top tree bins till a terminating condition is reached; and

initializing a bottom tree bin structure, said bottom tree bin structure comprising a plurality of bottom tree bins;

wherein each of said bottom tree bins comprises a plurality of bottom tree symbols;

merging at least two of said plurality of bottom tree bins based on a merging condition to generate a plurality of merged bottom tree bins;

further merging said plurality of bottom tree bins till a terminating condition is reached;

generating a desired bin structure using said plurality of top tree bins, said plurality of split top tree bins, said plurality of bottom tree bins and said plurality of merged bottom tree bins; and

coding the uncompressed data using the desired bin structure.

32. The method of claim 31 further comprising:

initializing a top tree bin structure based on the bit depth of said data, said top tree bin structure comprising a plurality of top tree bins, each of said top tree bins comprising a plurality of top tree symbols;

splitting any one of said top tree bins into two split top tree bins based on a splitting condition;

repeating said splitting step until a terminating condition is reached; and

generating said desired bin structure using said plurality of top tree bins and said plurality of said split top tree bins.

33. The method of claim 32, wherein a top tree bin having raw equal to zero is not split.

34. The method of claim 32, wherein each one of said plurality of top tree symbols represents said uncompressed data.

35. The method of claim 32, wherein said splitting condition is determined based on pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins, said splitting step comprising:

adding the bin information of each one of said plurality of child top tree bins,

splitting one of said top tree bins comprising said plurality of child top tree bins that correspond to a minimum increase in bin information.

36. The method of claim 32, wherein said splitting condition is determined based on maximum loss.

37. The method of claim 32, wherein said splitting condition is determined based on pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins, said splitting step comprising:

adding the loss of each one of said plurality of child top tree bins,

splitting one of said top tree bins comprising said plurality of child top tree bins that correspond to a maximum reduction in loss.

38. The method of claim 32, wherein said splitting condition is determined based on maximum bit budget.

39. The method of claim 32, wherein said splitting step comprises:

pseudo-splitting each of said plurality of top tree bins into a plurality of child top tree bins,

splitting one of said top tree bins comprising one of said plurality of child top tree bins that correspond to minimum increase in bit budget.

40. The method of claim 32, wherein a mathematical operation is a wavelet transform operation and an inverse mathematical operation is an inverse wavelet transform operation.

41. The method of claim 31, wherein said merging condition is determined based on merging two of said plurality of bins that corresponds to minimum loss.

42. The method of claim 31, wherein said merging condition is determined based on merging two of said plurality of bins that corresponds to minimum bit budget.

43. The method of claim 31, wherein each one of said plurality of bottom tree symbols represents said uncompressed data.

44. The method of claim 31, further comprising:

performing a mathematical operation said uncompressed data; and

performing an inverse mathematical operation on said decompressed data.

45. The method of claim 31, wherein a mathematical operation is a wavelet transform operation and said inverse mathematical operation is an inverse wavelet transform operation.

46. The method of claim 31, wherein said uncompressed data represents an image.

47. A system for coding uncompressed data, said system comprising:

means for initializing a top tree bin structure, said top tree bin structure comprising a plurality of top tree bins;

wherein each of said top tree bins comprises a plurality at top tree symbols; and

means for splitting said any one of said plurality of top tree bins based on a splitting condition to generate a plurality of split top tree bins;

means for further splitting said plurality of top tree bins till a terminating condition is reached; and

means for initializing a bottom tree bin structure, said bottom tree bin structure comprising a plurality of bottom tree bins;

wherein each of said bottom tree bins comprises a plurality of bottom tree symbols;

means for merging at least two of said plurality of bottom tree bins based on a merging condition to generate a plurality of merged bottom tree bins;

means for further merging said plurality of bottom tree bins till a terminating condition is reached; and

means for generating a desired bin structure using said plurality of top tree bins, said plurality of split top tree bins, said plurality of bottom tree bins and said plurality of merged bottom tree bins.

48. The system of claim 47, wherein each of said plurality of top tree symbols represents said uncompressed data.

49. The system of claim 47, wherein each one of said plurality of bottom tree symbols represents said uncompressed data.

50. The system of claim 47, further comprising:

means for performing a mathematical operation said uncompressed data; and

means for performing an inverse mathematical operation on said decompressed data.

51. The system of claim 50, wherein said mathematical operation is a wavelet transform operation and said inverse mathematical operation is an inverse wavelet transform operation.

52. The system of claim 47, wherein said uncompressed data represents an image.