# US 12,112,510 B2 · Convolutional approach to fast and compact packing of 3D mesh into 2D maps > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,112,510 B2 - Document ID: US12112510B2 - Status: Granted - Kind: B2 - Application number: 18/050,372 - Filed: 2022-10-27 - Published: 2023-09-28 - Granted: 2024-10-08 - Earliest claimed: 2022-03-25 - Assignees: Tencent America LLC - Applicants: Tencent America LLC - Inventors: Jun Tian; Chao Huang; Xiaozhong Xu; Xiang Zhang; Shan Liu - Web page: https://patentgrep.com/patent/US12112510B2 ## CPC - G06T 9/001: {Model-based coding, e.g. wire frame} - H04N 19/597: specially adapted for multi-view video sequence encoding - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract This disclosure relates generally to coding and decoding of 3-dimensional (3D) mesh and specifically to fast and efficient packing of parts of a 3D mesh into a map in a 2-dimensional (2D) space. In one example, a 3D mesh frame is decomposed into charts. The charts are iteratively projected and packed into a 2D map to achieve improved compactness by using an image filtering technology. The image filtering technology may involve perform efficient convolution and correlation processing using fast Fourier transform. ## Claims ### Claim 1 A method for projecting a first portion of a three-dimensional (3D) mesh frame to a two-dimensional (2D) occupancy map, the method comprising: obtaining an initial 2D occupancy map, the initial 2D occupancy map comprising: zero or more pixels with a first predefined value indicating that the zero or more pixels have been mapped to at least one other portion of the 3D mesh frame, the at least one other portion being non-overlapping with the first portion of the 3D mesh frame; and remaining pixels with a second predefined value indicating that the remaining pixels have not been mapped to the 3D mesh frame; generating a 2D occupancy matrix for the first portion of the 3D mesh frame, wherein the first predefined value corresponds to an occupied pixel and the second predefined value corresponds to an unoccupied pixel; computing a correlation matrix between the initial 2D occupancy map and the 2D occupancy matrix; identifying a zero-valued target element in the correlation matrix; and generating an updated 2D occupancy map by replacing pixels having the second predefined value in a patch in the initial 2D occupancy map having a same size as the 2D occupancy matrix with corresponding elements in the 2D occupancy matrix, the patch being located in the initial 2D occupancy map at a packing location according to a position of the zero-valued target element in the correlation matrix. ### Claim 2 (depends on 1) The method of claim 1, wherein the correlation matrix is computed as a convolution between the 2D occupancy matrix as a convolutional kernel and the initial 2D occupancy map. ### Claim 3 (depends on 2) The method of claim 2, wherein the convolution is calculated using fast Fourier transform. ### Claim 4 (depends on 1) The method of claim 1, wherein identifying the zero-valued target element in the correlation matrix comprise: identifying a plurality of zero-valued elements in the correlation matrix; and selecting one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element. ### Claim 5 (depends on 4) The method of claim 4, wherein selecting one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element comprises selecting a zero-valued element of the plurality of zero-valued elements in the correlation matrix having a smallest index in a width dimension. ### Claim 6 (depends on 4) The method of claim 4, wherein selecting one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element comprises selecting a zero-valued element of the plurality of zero-valued elements in the correlation matrix having a smallest index in a height dimension. ### Claim 7 (depends on 4) The method of claim 4, wherein selecting one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element comprises selecting a zero-valued element of the plurality of zero-valued elements in the correlation matrix having a smallest sum of a width index and a height index. ### Claim 8 (depends on 4) The method of claim 4, wherein selecting one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element comprises selecting a zero-valued element of the plurality of zero-valued elements based on an optimization function of a height index and a width index. ### Claim 9 (depends on 8) The method of claim 8, wherein the optimization function comprises alp norm function. ### Claim 10 (depends on 4) The method of claim 4, wherein selecting one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element comprises: determining a preferred packing location of the 2D occupancy matrix into the initial 2D occupancy map; and selecting the zero-valued target element from the plurality of zero-valued elements in the plurality of zero-valued elements in the correlation matrix according to the preferred packing location. ### Claim 11 (depends on 10) The method of claim 10, wherein selecting the zero-valued target element from the plurality of zero-valued elements in the plurality of zero-valued elements in the correlation matrix according to the preferred packing location comprises: selecting from the plurality of zero-valued elements that matches the preferred packing location as the zero-valued target element when possible; otherwise selecting from the plurality of zero-valued elements in a neighborhood of the preferred packing location based on an optimization function of the preferred packing location and locations of zero-valued elements in the neighborhood of the preferred packing location. ### Claim 12 (depends on 11) The method of claim 11, wherein the optimization function comprises a lp norm function of location differences between the preferred packing location and the locations of zero-valued elements among the plurality of zero-valued elements. ### Claim 13 (depends on 1) The method of claim 1, wherein identifying the zero-valued target element in the correlation matrix comprises determining a first identified zero-valued element of the correlation matrix as the zero-valued target element, and the method further comprises terminating calculating the correlation matrix once the first identified zero-valued element of the correlation matrix is found. ### Claim 14 (depends on 1) The method of claim 1, wherein the steps of claim 1 is iterated until all portions of the 3D mesh frame are mapped to the updated 2D occupancy map. ### Claim 15 (depends on 14) The method of claim 14, further comprising compressing into a bitstream the updated 2D occupancy map using a video encoder and compressing information of sizes and packing locations of 2D occupancy matrices of all portions of the 3D mesh frame. ### Claim 16 (depends on 1) The method of claim 1, wherein initial 2D occupancy map and the 2D occupancy matrix comprises binary values comprising the first predefined value and the second predefined value. ### Claim 17 A device comprising a memory for storing computer instructions and a processor, the processor, when executing the computer instructions to project a first portion of a three-dimensional (3D) mesh frame to a two-dimensional (2D) occupancy map, is configured to: obtain an initial 2D occupancy map, the initial 2D occupancy map comprising: zero or more pixels with a first predefined value indicating that the zero or more pixels have been mapped to at least one other portion of the 3D mesh frame, the at least one other portion being non-overlapping with the first portion of the 3D mesh frame; and remaining pixels with a second predefined value indicating that the remaining pixels have not been mapped to the 3D mesh frame; generate a 2D occupancy matrix for the first portion of the 3D mesh frame, wherein the first predefined value corresponds to an occupied pixel and the second predefined value corresponds to an unoccupied pixel; compute a correlation matrix between the initial 2D occupancy map and the 2D occupancy matrix; identify a zero-valued target element in the correlation matrix; and generate an updated 2D occupancy map by replacing pixels having the second predefined value in a patch in the initial 2D occupancy map having a same size as the 2D occupancy matrix with corresponding elements in the 2D occupancy matrix, the patch being located in the initial 2D occupancy map at a packing location according to a position of the zero-valued target element in the correlation matrix. ### Claim 18 (depends on 17) The device of claim 17, wherein: the correlation matrix is computed as a convolution between the 2D occupancy matrix as a convolutional kernel and the initial 2D occupancy map; and the convolution is calculated using fast Fourier transform. ### Claim 19 (depends on 17) The device of claim 17, wherein to identify the zero-valued target element in the correlation matrix comprise to: identify a plurality of zero-valued elements in the correlation matrix; and select one of the plurality of zero-valued elements in the correlation matrix as the zero-valued target element. ### Claim 20 A non-transitory computer readable medium for storing computer instructions, the computer instructions when executed by a processor of an electronic device to project a first portion of a three-dimensional (3D) mesh frame to a two-dimensional (2D) occupancy map, is configured to cause the electronic device to: obtain an initial 2D occupancy map, the initial 2D occupancy map comprising: zero or more pixels with a first predefined value indicating that the zero or more pixels have been mapped to at least one other portion of the 3D mesh frame, the at least one other portion being non-overlapping with the first portion of the 3D mesh frame; and remaining pixels with a second predefined value indicating that the remaining pixels have not been mapped to the 3D mesh frame; generate a 2D occupancy matrix for the first portion of the 3D mesh frame, wherein the first predefined value corresponds to an occupied pixel and the second predefined value corresponds to an unoccupied pixel; compute a correlation matrix between the initial 2D occupancy map and the 2D occupancy matrix; identify a zero-valued target element in the correlation matrix; and generate an updated 2D occupancy map by replacing pixels having the second predefined value in a patch in the initial 2D occupancy map having a same size as the 2D occupancy matrix with corresponding elements in the 2D occupancy matrix, the patch being located in the initial 2D occupancy map at a packing location according to a position of the zero-valued target element in the correlation matrix.