Data Compression Method and Apparatus, Data Restoration Method and Apparatus, and Program Therefor

• US 20090040216A1
• Filed: 12/22/2006
• Published: 02/12/2009
• Est. Priority Date: 12/27/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Ishiyama, Rui
• Granted Patent: US 8,248,403 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/27 involving both synthetic and natural picture components, e.g. synthetic natural hybrid coding [SNHC]

Abstract

Three-dimensional data (120) is compressed at a high compression ratio without deteriorating resolution and accuracy, by computing a coupling coefficient from input three-dimensional data and a three-dimensional base data group obtained from a plurality of objects and outputting the coupling coefficient as compressed data (130). Specifically, the three-dimensional data (120) is input to corresponding point determination means (101). The corresponding point determination means (101) generates three-dimensional data to be synthesized (103) in which vertexes of the three-dimensional data (120) are made to correspond to vertexes of three-dimensional reference data (111) serving as a reference to determine association relationship between vertexes. Coefficient computation means (102) computes a coupling coefficient for coupling a three-dimensional base data group (112) used for synthesis of three-dimensional data to synthesize three-dimensional data to be synthesized (103), and outputs the computed coupling coefficient as the compressed data (130) of the three-dimensional data (120).

Claims

1. A data compression apparatus comprising:

corresponding point determination means which receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are made to correspond to vertexes of three-dimensional reference data serving as a reference to determine the correspondence relationship between the vertexes; and

coefficient computation means which computes coupling coefficients for synthesizing the three-dimensional data to be synthesized by coupling a three-dimensional base data group used for synthesis of three-dimensional data, and outputs the computed coupling coefficients as compressed data of the received three-dimensional data.

2. The data compression apparatus according to claim 1, further comprising compression determination means which restores three-dimensional data from the coupling coefficient computed by the coefficient computation means and the three-dimensional base data group, compares the restored three-dimensional data with the three-dimensional data to be synthesized, and if the restoration accuracy does not satisfy a predetermined accuracy, adds new three-dimensional base data to the three-dimensional base data group used for synthesis of three-dimensional data.

3. The data compression apparatus according to claim 1, comprising base data selection means which selects a plurality of three-dimensional base data sets suitable for synthesis of the three-dimensional data to be synthesized from the three-dimensional base data group used for synthesis of three-dimensional data.

4. The data compression apparatus according to claim 2, wherein:

the compressed data contains, in addition to the coupling coefficient, selection information for identifying the three-dimensional base data that has been used for coupling.

5. The data compression apparatus according to claim 1, comprising region dividing means for dividing the three-dimensional data to be synthesized into a plurality of subregions, and

wherein the coefficient computation means computes, for each subregion, coupling coefficients for coupling the three-dimensional base data group divided into a same subregion to synthesize the three-dimensional data to be synthesized, and outputs the coupling coefficient computed for each subregion as compressed data of the received three-dimensional data.

6. The data compression apparatus according to claim 1, comprising:

region dividing means for dividing the three-dimensional data to be synthesized into a plurality of subregions; and

compression determination means which restores three-dimensional data from the coupling coefficient computed by the coefficient computation means and the three-dimensional base data group, compares the restored three-dimensional data with the three-dimensional data to be synthesized, divides the three-dimensional data to be synthesized into a plurality of subregions by means of the region dividing means if the restoration accuracy does not satisfy a predetermined accuracy, computes, for each subregion, a coupling coefficient for coupling the three-dimensional base data group divided into a same subregion to synthesize the three-dimensional data to be synthesized by means of coefficient computation means, and outputs the coupling coefficient computed for each subregion as compressed data of the received three-dimensional data.

7. The data compression apparatus according to claim 5 wherein:

if the restoration accuracy as a whole does not satisfy the predetermined accuracy even after the division into subregions, the compression determination means further divides the three-dimensional data to be synthesized into smaller subregions and performs control to find a coupling coefficient for each subregion.

8. The data compression apparatus according to claim 5, wherein:

the compressed data contains subregion determination data for identifying the subregions.

9. The data compression apparatus according to claim 1, comprising a detachable memory device for storing the compressed data.

15. A data transmission apparatus comprising:

a data compression apparatus according to claim 1;

a memory device for storing three-dimensional reference data and a three-dimensional base data group used by the data compression apparatus; and

data transmission means for transmitting compressed data generated by the data compression apparatus.

16. The data transmission apparatus according to claim 15, wherein the data transfer means transfers three-dimensional base data added to the three-dimensional base data group by the data compression apparatus, to a transmission destination of compressed data.

10. A data restoration apparatus comprising:

three-dimensional data restoration means which receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets used for synthesis, using the coupling coefficient contained in the compressed data.

13. The data restoration apparatus according to claim 10, comprising a detachable memory device for storing the compressed data.

17. A data reception apparatus comprising:

a data restoration apparatus according to claim 10;

a memory device for storing a three-dimensional base data group used by the data restoration apparatus; and

data transfer means for receiving compressed data and outputting the same to the data restoration apparatus.

18. The data reception apparatus according to claim 17, wherein:

when receiving additional three-dimensional base data, the data transfer means adds the same to the three-dimensional base data group.

11. A data restoration apparatus comprising:

base data retrieval means which receives compressed data containing coupling coefficients and selection information of a three-dimensional base data group which has been used for synthesis, and extracts, from a predetermined three-dimensional base data group, the three-dimensional base data group which has been used for synthesis of three-dimensional data to be compressed based on the selection information; and

three-dimensional data restoration means which restores three-dimensional data by coupling the extracted three-dimensional base data group, using the coupling coefficient contained in the compressed data.

12. A data restoration apparatus comprising:

base data retrieval means which receives compressed data containing a coupling coefficient for each subregion and subregion determination data identifying a subregion of three-dimensional base data group which has been used for synthesis, and extracts, from a predetermined three-dimensional base data group, a subregion of the three-dimensional base data group used for synthesis of three-dimensional data to be compressed, based on the subregion determination data; and

three-dimensional data restoration means which restores three-dimensional data by coupling the extracted three-dimensional base data group of each same subregion, using the coupling coefficient for each subregion contained in the compressed data.

14. A compression/restoration system comprising:

a compression/restoration apparatus having a data compression apparatus, and a data restoration apparatus; and

a memory device for storing compressed data generated by the compression/restoration apparatus,

the data compression apparatus comprising;

corresponding point determination means which receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are made to correspond to vertexes of three-dimensional reference data serving as a reference to determine the correspondence relationship between the vertexes; and

coefficient computation means which computes coupling coefficients for synthesizing the three-dimensional data to be synthesized by coupling a three-dimensional base data group used for synthesis of three-dimensional data, and outputs the computed coupling coefficients as compressed data of the received three-dimensional data,

the data restoration apparatus comprising;

three-dimensional data restoration means which receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets used for synthesis, using the coupling coefficient contained in the compressed data.

19. A data transfer system wherein:

a data transmission apparatus;

a data reception apparatus connected to the data transmission apparatus through a communication path,

the data transmission apparatus comprising;

a data compression apparatus comprising;

corresponding point determination means which receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are made to correspond to vertexes of three-dimensional reference data serving as a reference to determine the correspondence relationship between the vertexes; and

coefficient computation means which computes coupling coefficients for synthesizing the three-dimensional data to be synthesized by coupling a three-dimensional base data group used for synthesis of three-dimensional data, and outputs the computed coupling coefficients as compressed data of the received three-dimensional data;

a memory device for storing three-dimensional reference data and a three-dimensional base data group used by the data compression apparatus; and

data transmission means for transmitting compressed data generated by the data compression apparatus,

the data reception apparatus comprising;

three-dimensional data restoration means which receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets used for synthesis, using the coupling coefficient contained in the compressed data;

a memory device for storing a three-dimensional base data group used by the data restoration apparatus; and

data transfer means for receiving compressed data and outputting the same to the data restoration apparatus.

20. A data compression method comprising:

a step (a) in which corresponding point determination means receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are associated with vertexes of three-dimensional reference data serving as a reference for determining association relationship between the vertexes; and

a step (b) in which coefficient computation means computes a coupling coefficient for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data.

21. The data compression method according to claim 20, comprising a step (c) in which compression determination means restores three-dimensional data from the coupling coefficient computed in the step (b) and the three-dimensional base data group, compares the restored three-dimensional data with the three-dimensional data to be synthesized, and adds new three-dimensional base data to a three-dimensional base data group used for synthesis of three-dimensional data if the restoration accuracy does not satisfy a predetermined accuracy.

22. The data compression method according to claim 20, comprising a step (d) in which base data selection means selects a plurality of three-dimensional base data sets suitable for synthesis of the three-dimensional data to be synthesized from a three-dimensional base data group used for synthesis of three-dimensional data.

23. The data compression method according to claim 21, wherein:

the compressed data contains selection information for identifying three-dimensional base data which has been used for synthesis, in addition to the coupling coefficient.

28. The data compression method according to claim 20, wherein:

the compressed data is stored in a detachable memory device.

34. A data transmission method wherein:

compressed data generated by the data compression method according to claim 20 is transferred by means of data transfer means.

35. The data transmission method according to claim 34, wherein:

the data transfer means transfers three-dimensional base data added to the three-dimensional base data group in the data compression method, to a transmission destination of compressed data.

24. A data compression method comprising:

a step (a) in which corresponding point determination means receives three-dimensional data, and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are associated with vertexes of three-dimensional reference data serving as a reference for determining association relationship between vertexes;

a step (b) in which region dividing means divides the three-dimensional data to be synthesized into a plurality of subregions; and

a step (c) in which coefficient computation means computes, for each subregion, a coupling coefficient for coupling a three-dimensional base data group used for synthesis of three-dimensional data and divided into a same subregion to synthesize the three-dimensional data to be synthesized, and outputs the coupling coefficient computed for each subregion as compressed data of the received three-dimensional data.

27. The data compression method according to claim 24 wherein:

the compressed data contains subregion determination data for identifying the subregions.

25. A data compression method comprising:

a step (a) in which corresponding point determination means receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are associated with vertexes of three-dimensional reference data serving as a reference for determining association relationship between vertexes;

a step (b) in which coefficient computation means computes a coupling coefficient for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data; and

a step (c) in which compression determination means restores three-dimensional data from the coupling coefficient computed in the step (b) and the three-dimensional base data group, compares the restored three-dimensional data with the three-dimensional data to be synthesized, and divides the three-dimensional data to be synthesized into a plurality of subregions by means of the region dividing means if the restoration accuracy does not satisfies a predetermined accuracy, computes, for each subregion, a coupling coefficient for coupling a three-dimensional base data group divided into a same subregion to synthesize the three-dimensional data to be synthesized by means of the coefficient computation means, and outputs the coupling coefficient computed for each subregion as compressed data of the received three-dimensional data.

26. The data compression method according to claim 25, wherein:

when the restoration accuracy as a whole does not satisfies the predetermined accuracy even after the division into subregions, the three-dimensional data to be synthesized is further divided into smaller subregions and a coupling coefficient is found for each subregion.

29. A data restoration method wherein:

three-dimensional data restoration means receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets which have been used for synthesis, using the coupling coefficient contained in the compressed data.

32. The data restoration method according to claim 29 wherein:

the compressed data is input from a detachable memory device.

36. A data reception method wherein:

compressed data received by data transfer means is restored to three-dimensional data by the data restoration method according to claim 29.

37. The data reception method according to claim 36, wherein:

when receiving additional three-dimensional base data, the data transfer means adds the same to a three-dimensional base data group used in the data restoration method.

30. A data restoration method comprising:

a step (a) in which base data retrieval means receives compressed data containing a coupling coefficient and selection information of a three-dimensional base data group that has been used for synthesis, and extracts the three-dimensional base data group that has been used for synthesis of three-dimensional data to be compressed from a predetermined three-dimensional base data group, based on the selection information; and

a step in which three-dimensional data restoration means restores three-dimensional data by coupling the extracted three-dimensional base data group, using the coupling coefficient contained in the compressed data.

31. A data restoration method comprising:

a step (a) in which base data retrieval means receives compressed data containing a coupling coefficient for each subregion and subregion determination data for identifying a subregion of a three-dimensional base data group that has been used for synthesis, and extracts, from a predetermined three-dimensional base data group, a subregion of the three-dimensional base data group that has been used for synthesis of three-dimensional data to be compressed based on the subregion determination data; and

a step (b) in which three-dimensional data restoration means restores three-dimensional data by coupling the extracted three-dimensional base data group of each same subregion, using the coupling coefficient for each subregion contained in the compressed data.

33. A compression/restoration method wherein:

compressed data generated by a data compression method is stored in a memory device, and compressed data retrieved from the memory device is restored to three-dimensional data by a data restoration method,

the data compression method comprising;

a step (a) in which corresponding point determination means receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are associated with vertexes of three-dimensional reference data serving as a reference for determining association relationship between the vertexes; and

a step (b) in which coefficient computation means computes a coupling coefficient for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data,

the data restoration method wherein

three-dimensional data restoration means receives compressed data containing a coupling coefficient and restores three-dimensional data by coupling a plurality of three-dimensional base data sets which have been used for synthesis, using the coupling coefficient contained in the compressed data.

38. A data transfer method wherein:

a data transmission method is combined with a data reception method,

the data transmission method wherein;

compressed data generated by a data compression method is transferred by means of data transfer means, the data compression method comprising;

a step (a) in which corresponding point determination means receives three-dimensional data and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are associated with vertexes of three-dimensional reference data serving as a reference for determining association relationship between the vertexes; and

a step (b) in which coefficient computation means computes a coupling coefficient for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data,

the data reception method wherein;

compressed data received by data transfer means is restored to three-dimensional data by a data restoration method wherein;

three-dimensional data restoration means receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets which have been used for synthesis, using the coupling coefficient contained in the compressed data.

39. A data compression program for operating a computer which has a memory device for storing three-dimensional reference data serving as a reference for determining correspondence relationship between vertexes and a three-dimensional base data group used for synthesis of three-dimensional data so as to function as:

corresponding point determination means which receives three-dimensional data, and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are made to correspond to vertexes of the three-dimensional reference data; and

coefficient computation means which computes coupling coefficients for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data.

40. The data compression program according to claim 39, causing the computer to function further as compression determination means which restores three-dimensional data from the coupling coefficient computed by the coefficient computation means and the three-dimensional base data group, compares the restored three-dimensional data and the three-dimensional data to be synthesized, and adds new three-dimensional base data to a three-dimensional base data group used for synthesis of three-dimensional data if the restoration accuracy does not satisfy a predetermined accuracy.

41. The data compression program according to claim 39, causing the computer to function further as base data selection means which selects a plurality of three-dimensional base data sets suitable for synthesis of the three-dimensional data to be synthesized, from the three-dimensional base data group used for synthesis of three-dimensional data.

42. The data compression program according to claim 40, wherein the compressed data contains selection information for identifying three-dimensional base data that has been used for coupling, in addition to the coupling coefficient.

43. The data compression program according to claim 39, causing the computer to function further as region dividing means for dividing the three-dimensional data to be synthesized into a plurality of subregions and characterized in that the coefficient computation means computes, for each subregion, a coupling coefficient for coupling a three-dimensional base data group divided into a same subregion for synthesizing the three-dimensional data to be synthesized, and outputs the coupling coefficient computed for each subregion as compressed data of the received three-dimensional data.

44. The data compression program according to claim 39, causing the computer to function further as:

region dividing means which divides the three-dimensional data to be synthesized into a plurality of subregions; and

compression determination means which restores three-dimensional data from the coupling coefficient computed by the coefficient computation means and the three-dimensional base data group, compares the restored three-dimensional data with the three-dimensional data to be synthesized, divides the three-dimensional data to be synthesized into a plurality of subregions by means of the region dividing means if the restoration accuracy does not satisfy a predetermined accuracy, computes a coupling coefficient for each subregion for coupling the three-dimensional base data group divided into a same subregion to synthesize three-dimensional data to be synthesized by means of the coefficient computation means, and outputs the coupling coefficient computed for each subregion as compressed data of the received three-dimensional data.

45. The data compression program according to claim 44, wherein:

when the restoration accuracy as a whole does not satisfy the predetermined accuracy even if the data is compressed after being divided into subregions, the compression determination means further divides the three-dimensional data to be synthesized into smaller subregions, and performs control to find a coupling coefficient for each subregion.

46. The data compression program according to claim 43, wherein:

the compressed data contains subregion determination data for identifying the subregions.

47. The data compression program according to claim 39, wherein:

the compressed data is stored in a detachable memory device.

53. A data transmission program comprising the data compression program according to claim 39 and a program causing a computer to function as data transfer means for transmitting compressed data generated by the data compression program.

54. The data transmission program according to claim 53, wherein:

the data transfer means transfers three-dimensional base data added to the three-dimensional base data group by the data compression program to a transmission destination of compressed data.

48. A data restoration program causing a computer having a memory device for storing a three-dimensional base data group used for synthesis of three-dimensional data to function as:

three-dimensional data restoration means which receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets which have been used for synthesis, using the coupling coefficient contained in the compressed data.

51. The data restoration program according to claim 48 characterized in that the compressed data is input from a detachable memory device.

55. A data reception program comprising the data restoration program according to claim 48, and a program causing a computer to function as data transfer means for receiving compressed data and outputting the same to the data restoration program.

56. The data reception program according to claim 55 wherein:

when receiving additional three-dimensional base data, the data transfer means adds the same to a three-dimensional base data group stored in a memory device.

49. A data restoration program for causing a computer having a memory device for storing a three-dimensional base data group used for synethesis of three-dimensional data to function as:

base data retrieval means which receives compressed data containing a coupling coefficient and selection information of a three-dimensional base data group that has been used for synthesis, and retrieves from the memory device a three-dimensional base data group that has been used for synthesis of three-dimensional data to be compressed, based on the selection information; and

three-dimensional data restoration means which restores three-dimensional data by coupling the retrieved three-dimensional base data group, using the coupling coefficient contained in the compressed data.

50. A data restoration program for causing a computer having a memory device for storing a three-dimensional base data group used for synthesis of three-dimensional data to function as:

base data retrieval means which receives compressed data containing a coupling coefficient for each subregion and subregion determination data for identifying a subregion of a three-dimensional base data group that has been used for synthesis, and extracts from a predetermined three-dimensional base data group a subregion of the three-dimensional base data group that has been used for synthesis of three-dimensional data to be compressed, based on the subregion determination data; and

,

three-dimensional data restoration means which restores three-dimensional data by coupling the extracted three-dimensional base data group of each same subregion by using the coupling coefficient for each subregion contained in the compressed data.

52. A compression/restoration program comprising a data compression program;

and

a data restoration program,

the data compression program for operating a computer which has a memory device for storing three-dimensional reference data serving as a reference for determining correspondence relationship between vertexes and a three-dimensional base data group used for synthesis of three-dimensional data so as to function as;

corresponding point determination means which receives three-dimensional data, and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are made to correspond to vertexes of the three-dimensional reference data; and

coefficient computation means which computes coupling coefficients for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized and outputs the computed coupling coefficient as compressed data of the received three-dimensional data,

the data restoration program causing a computer having a memory device for storing a three-dimensional base data group used for synthesis of three-dimensional data to function as;

three-dimensional data restoration means which receives compressed data containing a coupling coefficient, and restores three-dimensional data by coupling a plurality of three-dimensional base data sets which have been used for synthesis, using the coupling coefficient contained in the compressed data.

57. A data transfer program comprising a data transmission program and the and a data reception program,

the data transmission program comprising a data compression program and a program causing a computer to function as data transfer means for transmitting compressed data generated by the data compression program,

the data compression program for operating a computer which has a memory device for storing three-dimensional reference data serving as a reference for determining correspondence relationship between vertexes and a three-dimensional base data group used for synthesis of three-dimensional data so as to function as:

corresponding point determination means which receives three-dimensional data, and generates three-dimensional data to be synthesized in which vertexes of the received three-dimensional data are made to correspond to vertexes of the three-dimensional reference data; and

coefficient computation means which computes coupling coefficients for coupling a three-dimensional base data group used for synthesis of three-dimensional data to synthesize the three-dimensional data to be synthesized, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data,

the data reception program comprising a data restoration program, and a program causing a computer to function as data transfer means for receiving compressed data and outputting the same to the data restoration program,

the data restoration program for causing a computer having a memory device for storing a three-dimensional base data group used for synethesis of three-dimensional data to function as;

base data retrieval means which receives compressed data containing a coupling coefficient and selection information of a three-dimensional base data group that has been used for synthesis and retrieves from the memory device a three-dimensional base data group that has been used for synthesis of three-dimensional data to be compressed, based on the selection information; and

three-dimensional data restoration means which restores three-dimensional data by coupling the retrieved three-dimensional base data group, using the coupling coefficient contained in the compressed data.