Data compression method and apparatus, data restoration method and apparatus, and program therefor

• US 8,248,403 B2
• Filed: 12/22/2006
• Issued: 08/21/2012
• Est. Priority Date: 12/27/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Ishiyama, Rui
• Primary Examiner(s): Nguyen, Phu K
• Application Number:
  US12/087,102
• Publication Number:
  US 20090040216A1
• Time in Patent Office: 2,069 Days
• Field of Search: 345/419, 345/427, 345/555, 382/232, 382/254, 382/276
• 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, by making vertexes of the received three-dimensional data correspond to vertexes of three-dimensional reference data serving as a reference, by calculating a minimum one of the vertexes of the received three-dimensional data from those of the three-dimensional reference data; and

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

the corresponding point determination means and the coefficient computation means realized by hardware or a computer with a non-transitory computer readable storage medium storing a program.

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 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.

4. 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.

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 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.

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

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

8. 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.

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

10. 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.

11. The data transmission apparatus according to claim 10, 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.

12. A data compression method performed by a computer system realized by hardware or a computer with a non-transitory computer readable storage medium storing a program, the method comprising:

a step (a) in which corresponding point determination means receives three-dimensional data and generates three-dimensional data to be synthesized, by associating vertexes of the received three-dimensional data with vertexes of three-dimensional reference data serving as a reference, by calculating a minimum one of the vertexes of the received three-dimensional data from those of the three-dimensional reference data; and

a step (b) in which coefficient computation means computes a coupling coefficient which is necessary for synthesizing the three-dimensional data to be synthesized, by coupling a three-dimensional base data group which is used for synthesis of three-dimensional data and which is subjected to point determination processing, and outputs the computed coupling coefficient as compressed data of the received three-dimensional data.

13. The data compression method according to claim 12, 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.

14. The data compression method according to claim 13, 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.

15. The data compression method according to claim 12, 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.

16. The data compression method according to claim 12, wherein:

the compressed data is stored in a detachable memory device.

17. A data transmission method wherein:

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

18. The data transmission method according to claim 17, 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.

19. A data compression method performed by a computer system realized by hardware or a computer with a non-transitory computer readable storage medium storing a program, the method comprising:

a step (a) in which corresponding point determination means receives three-dimensional data, and generates three-dimensional data to be synthesized, by associating vertexes of the received three-dimensional data with vertexes of three-dimensional reference data serving as a reference, by calculating a minimum one of the vertexes of the received three-dimensional data from those of the three-dimensional reference data;

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.

20. The data compression method according to claim 19 wherein:

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

21. A data compression method performed by a computer system realized by hardware or a computer with a non-transitory computer readable storage medium storing a program, the 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.

22. The data compression method according to claim 21, 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.

23. A non-transitory computer storage medium for storing a data compression program, wherein the data compression program is 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, by making vertexes of the received three-dimensional data correspond to vertexes of the three-dimensional reference data by calculating a minimum one of the vertexes of the received three-dimensional data from those of the three-dimensional reference date; and

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

24. The non-transitory computer storage medium for storing a data compression program according to claim 23, the data compression program 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.

25. The non-transitory computer storage medium for storing a data compression program according to claim 24, 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.

26. The non-transitory computer storage medium for storing a data compression program according to claim 23, the data compression program 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.

27. The non-transitory computer storage medium for storing a data compression program according to claim 23, the data compression program 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.

28. The non-transitory computer storage medium for storing a data compression program according to claim 27, wherein:

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

29. The non-transitory computer storage medium for storing a data compression program according to claim 23, 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.

30. The non-transitory computer storage medium for storing a data compression program according to claim 29, 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.

31. The non-transitory computer storage medium for storing a data compression program according to claim 23, wherein:

the compressed data is stored in a detachable memory device.

32. A non-transitory computer storage medium for storing a data transmission program comprising the data compression program according to claim 23 and a program causing a computer to function as data transfer means for transmitting compressed data generated by the data compression program.

33. The non-transitory computer storage medium for storing a data transmission program according to claim 32, 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.