Patent
Method and device for compressing vertex data in three-dimensional image data
| العنوان: | Method and device for compressing vertex data in three-dimensional image data |
|---|---|
| Patent Number: | 9,509,973 |
| تاريخ النشر: | November 29, 2016 |
| Appl. No: | 14/372901 |
| Application Filed: | April 12, 2012 |
| مستخلص: | A device for compressing vertex data in three-dimensional (3D) image data includes a codebook design module and a codeword search module. The codebook design module is configured for: grouping residual vectors of vertices in 3D image data for codebook design; generating, for each group of residual vectors, a sub-codebook formed by a specified number of codewords; and sending the generated sub-codebook corresponding to a group of residual vectors to the codeword search module. The codeword search module is configured for: receiving a sub-codebook sent by the codebook design module; searching for a codeword of optimal match of a to-be-compressed residual vector of a vertex in 3D image data to be compressed; and taking an index of the codeword of optimal match and an index of a sub-codebook where the codeword of optimal match is located as compressed data of the vertex. A method for compressing vertex data in 3D image data is further disclosed. With the disclosure, it is possible to save codeword storage space, enhance encoding quality, improve a compression ratio of vertex data, and increase a compression efficiency. |
| Inventors: | He, Feifei (Shenzhen, CN); Hui, Jian (Shenzhen, CN); Sun, Gengmao (Shenzhen, CN); Gao, Feng (Shenzhen, CN); Pan, Zhibin (Shenzhen, CN); Li, Da (Shenzhen, CN); Li, Jingyuan (Shenzhen, CN) |
| Assignees: | ZTE Corporation (Shenzhen, Guangdong, CN) |
| Claim: | 1. A device for compressing vertex data in three-dimensional (3D) image data, comprising a codebook design module and a codeword search module, wherein the codebook design module is configured for: grouping residual vectors of vertices in 3D image data for codebook design; generating, for each group of residual vectors, a sub-codebook formed by a specified number of codewords; and sending the generated sub-codebook corresponding to a group of residual vectors to the codeword search module; and the codeword search module is configured for: receiving a sub-codebook sent by the codebook design module; searching for a codeword of optimal match of a to-be-compressed residual vector of a vertex in 3D image data to be compressed; and taking an index of the codeword of optimal match and an index of a sub-codebook where the codeword of optimal match is located as compressed data of the vertex. |
| Claim: | 2. The device according to claim 1 , further comprising a residual vector calculating module configured for calculating residual vectors of vertices in the 3D image data for codebook design, and sending the calculated residual vectors to the codebook design module, wherein the codebook design module is configured for: receiving the residual vectors of the vertices in the 3D image data for codebook design sent by the residual vector calculating module; sorting the received residual vectors in an ascending order of moduli of the received residual vectors; consecutively extracting a number of residual vectors from the sorted residual vectors to form a group of residual vectors according to a group number and grouping proportions; recording a moduli range of the formed group of residual vectors; obtaining a number (which is equal to the group number) of groups of residual vectors by repeating the extraction step; and numbering each of the obtained groups of residual vectors in an order in which the groups of residual vectors are obtained. |
| Claim: | 3. The device according to claim 2 , wherein the codebook design module is configured for: extracting the groups of residual vectors group by group; generating a specified number of codewords by training an extracted group of residual vectors using an LBG algorithm; and forming, by the specified number of codewords generated, a sub-codebook corresponding to the extracted group of residual vectors. |
| Claim: | 4. The device according to claim 3 , wherein the residual vector calculating module is further configured for calculating a to-be-compressed residual vector of a vertex in the 3D image data to be compressed, and sending the calculated to-be-compressed residual vector to the codeword search module; and the codeword search module is configured for: receiving a to-be-compressed residual vector of a vertex in the 3D image data to be compressed sent by the residual vector calculating module; determining a group of residual vectors of which a modulus of the received to-be-compressed residual vector falls into the moduli range; and searching a sub-codebook corresponding to the determined group of residual vectors for a codeword of optimal match of the received to-be-compressed residual vector. |
| Claim: | 5. The device according to claim 1 , further comprising a control module configured for selecting a codeword search method of a Full Search (FS) method or a quick search method, and sending the codeword search module a notification of a selected codeword search method, wherein the codeword search module is further configured for receiving the notification of the selected codeword search method sent by the control module. |
| Claim: | 6. The device according to claim 5 , wherein the codeword search module is configured for: when the quick search method is selected, calculating an orthogonal transformation matrix of a sub-codebook using a Principal Component Analysis (PCA) algorithm; performing an orthogonal transformation on each codeword in the sub-codebook using the orthogonal transformation matrix of the sub-codebook; and storing the codeword subject to the orthogonal transformation as a new codeword in the sub-codebook; and in codeword search, determining a group of residual vectors of which a modulus of a to-be-compressed residual vector falls into a moduli range, and determining a sub-codebook corresponding to the determined group of residual vectors and the to-be-compressed residual vector; performing orthogonal transformation on the to-be-compressed residual vector using an orthogonal transformation matrix of the determined sub-codebook; and searching codewords subject to orthogonal transformation in the determined sub-codebook for a codeword of optimal match of the transformed to-be-compressed residual vector. |
| Claim: | 7. A method for compressing vertex data in three-dimensional (3D) image data, comprising steps of: grouping residual vectors of vertices in 3D image data for codebook design; and generating, for each group of residual vectors, a sub-codebook formed by a specified number of codewords; and searching for a codeword of optimal match of a to-be-compressed residual vector of a vertex in 3D image data to be compressed; and taking an index of the codeword of optimal match and an index of a sub-codebook where the codeword of optimal match is located as compressed data of the vertex. |
| Claim: | 8. The method according to claim 7 , wherein the step of grouping residual vectors of vertices in 3D image data for codebook design comprises: calculating residual vectors of vertices in the 3D image data for codebook design; and sorting the calculated residual vectors of the vertices in the 3D image data for codebook design in an ascending order of moduli; consecutively extracting a number of residual vectors from the sorted residual vectors to form a group of residual vectors according to a group number and grouping proportions; recording a moduli range of the formed group of residual vectors; obtaining a number (which is equal to the group number) of groups of residual vectors by repeating the extraction step; and numbering each of the obtained groups of residual vectors in an order in which the groups of residual vectors are obtained. |
| Claim: | 9. The method according to claim 7 , wherein the step of generating, for each group of residual vectors, a sub-codebook formed by a specified number of codewords comprises: extracting groups of residual vectors group by group; generating a specified number of codewords by training an extracted group of residual vectors using an LBG algorithm; and forming, by the specified number of codewords generated, a sub-codebook corresponding to the extracted group of residual vectors. |
| Claim: | 10. The method according to claim 7 , wherein the step of searching for a codeword of optimal match of a to-be-compressed residual vector of a vertex in 3D image data to be compressed comprises: calculating the to-be-compressed residual vector of the vertex in the 3D image data to be compressed; and determining a group of residual vectors of which a modulus of the to-be-compressed residual vector falls into a moduli range; and searching a sub-codebook corresponding to the determined group of residual vectors for a codeword of optimal match of the to-be-compressed residual vector. |
| Claim: | 11. The method according to claim 10 , wherein the sub-codebook corresponding to the determined group of residual vectors is searched for the codeword of optimal match using a Full Search (FS) method or a quick search method. |
| Claim: | 12. The method according to claim 11 , wherein when the quick search method is used, the step of searching a sub-codebook corresponding to the determined group of residual vectors for a codeword of optimal match comprises: calculating an orthogonal transformation matrix of a sub-codebook using a Principal Component Analysis (PCA) algorithm; performing an orthogonal transformation on each codeword in the sub-codebook using the orthogonal transformation matrix of the sub-codebook; and storing the codeword subject to the orthogonal transformation as a new codeword in the sub-codebook; and in codeword search, determining the group of residual vectors of which the modulus of the to-be-compressed residual vector falls into the moduli range, and determining the sub-codebook corresponding to the determined group of residual vectors and the to-be-compressed residual vector; performing orthogonal transformation on the to-be-compressed residual vector using an orthogonal transformation matrix of the determined sub-codebook; and searching codewords subject to orthogonal transformation in the determined sub-codebook for a codeword of optimal match of the transformed to-be-compressed residual vector. |
| Patent References Cited: | 6256041 July 2001 Deering 2010/0284392 November 2010 Sato 2011/0046923 February 2011 Lee 2012/0075302 March 2012 Cai 2012/0189220 July 2012 Ahn 1946180 April 2007 101944358 January 2011 2261859 December 2010 2002049933 February 2002 1999002045 January 1999 20030054606 July 2003 100598134 July 2006 2009128617 October 2009 |
| Other References: | Nguyen H et al: “Concentric-Shell Partition Vector Quantization with Application to Image Coding”, IEEE Transactions on Communications, IEEE Service Center, Piscataway, NJ. USA, vol. 42, No. 2/03/04, Feb. 1, 1994 (Feb. 1, 1994), pp. 1911-1918, XP0004474O4,ISSN: 0090-6778, DOI: 10.1109/TC0MM.1994.582901,mailed on Feb. 1, 1994. cited by applicant McNames J: “Rotated partial distance search for faster vector quantization encoding”,IEEE Signal Processing Letters, IEEE Service Center, Piscataway, NJ, US, vol. 7, No. 9, Sep. 1, 2000 (Sep. 1, 2000), pp. 244-246, XP011428310,ISSN: 1070-9908, DOI: 10.1109/97.863145,mailed on Sep. 1, 2000. cited by applicant In: Gersho A et al: “Vector Quantization and Signal Compression”,1991, Kluwer, XP0Q2065452, pp. 423-424,mailed on 1991. cited by applicant Z. Li et al: “Fast codevector search scheme for 3D mesh model vector quantisation”,Electronics Letters, vol. 44, No. 2, Jan. 1, 2008 (Jan. 1, 2008), pp. 104-105, XP055272845,GB ISSN: 0013-5194, DOI: 10.1049/el:20O82270,mailed on Jan. 1, 2008. cited by applicant Supplementary European Search Report in European application No. 12869069.0, mailed on May 31, 2016. cited by applicant International Search Report in international application No. PCT/CN2012/073932, mailed on Nov. 29, 2012. cited by applicant English Translation of the Written Opinion of the International Search Authority in international application No. PCT/CN2012/073932, mailed on Nov. 29, 2012. cited by applicant Vertex Data Compression for Triangular Meshes, Oct. 5, 2000. cited by applicant A Coding Algorithm Using PCA-Based Correlation Vector Quantization, Aug. 2005. cited by applicant Vector quantization technology and applications and parallel algorithm design, Sep. 2003. cited by applicant Fast Planar-Oriented Ripple Search Algorithm for Hyperspace VQ Codebook, Jun. 2007. cited by applicant |
| Primary Examiner: | Wong, Allen |
| Attorney, Agent or Firm: | Oppedahl Patent Law Firm LLC |
| رقم الانضمام: | edspgr.09509973 |
| قاعدة البيانات: | USPTO Patent Grants |
| الوصف غير متاح. |