News Column

Patent Issued for Apparatus and Method for Coding a Three Dimensional Mesh

August 27, 2014



By a News Reporter-Staff News Editor at Electronics Newsweekly -- According to news reporting originating from Alexandria, Virginia, by VerticalNews journalists, a patent by the inventors Ahn, Min Su (Seoul, KR); Han, Jeong Hwan (Suwon-si, KR); Ahn, Jae Kyun (Seoul, KR); Lee, Dae Youn (Seoul, KR); Kim, Chang Su (Seoul, KR), filed on October 15, 2010, was published online on August 12, 2014.

The assignee for this patent, patent number 8805097, is Samsung Electronics Co., Ltd. (Suwon-Si, KR).

Reporters obtained the following quote from the background information supplied by the inventors: "Example embodiments relate to a three-dimensional (3D) mesh compression apparatus and method, and more particularly, to a technology that constructs a covariance matrix based on a topological distance between vertices, and encodes geometric information associated with an eliminated vertex based on the covariance matrix.

"A three-dimensional (3D) mesh may generally use a large amount of storage space, a large amount of calculations, a broad transmission bandwidth, and the like. Particularly, when a complexity of the mesh increases, a greater storage space and a higher bandwidth of a network used for transmission are used, and thus, there is a difficulty in utilizing the mesh. Therefore, there is a desire for a compression of a 3D object for effective transmission, storage, and rendering of mesh data.

"A 3D mesh model may be constituted of connectivity information, geometric information, and feature information. The connectivity information may indicate a relationship between adjacent vertexes, the geometric information may indicate a 3D location coordinate of each vertex, and the feature information may indicate a color of the mesh, a direction of a perpendicular line of the mesh, a reflection rate of the mesh, and the like.

"Here, the geometric information may be coded based on a residual vector between geometric information at a predicted point, and geometric information at an actual point. However, the residual vector of the geometric information may not be constant based on a predicted triangle, and, when two triangles are not in a form of a parallelogram, the residual vector may increase, thereby decreasing a compression performance.

"Thus, there is a desire for a 3D mesh compression apparatus and method that increases a compression rate of the geometric information, thereby providing an excellent compression rate."

In addition to obtaining background information on this patent, VerticalNews editors also obtained the inventors' summary information for this patent: "According to an aspect, there is provided an a three-dimensional (3D) mesh compression apparatus including a mesh simplifying unit to generate a base mesh by simplifying an inputted 3D mesh, a base mesh coding unit to code the base mesh, and a vertex coding unit to code, based on a covariance matrix, at least one vertex eliminated by the simplification.

"The 3D mesh compression apparatus may further include an entropy coding unit to transform the coded base mesh and the coded at least one vertex into a bit stream by performing entropy-coding.

"According to an embodiment, the entropy coding unit may record a Most Significant Bit (MSB) or a Least Significant Bit (LSB) first among geometric information associated with the coded base mesh and geometric information associated with the at least one coded vertex to transform the recorded MSB and/or the recorded LSB into a bit stream.

"The vertex coding unit may include a geometric information estimating unit to estimate geometric information associated with the at least one eliminated vertex, a segmentation unit to segment the base mesh into at least one area, a matrix generating unit to generate the covariance matrix based on connectivity information between the at least one eliminated vertex, a domain-transforming unit to perform a domain-transform based on the estimated geometric information and the covariance matrix, and a quantization unit to quantize a coefficient calculated by the domain-transform.

"The geometric estimating unit may perform estimating geometric information based on each local coordinate of a plurality of triangles, and a tangent vector of a first local coordinate of a first triangle among the plurality of triangles may be determined by projecting, onto a plane including the first triangle, a tangent vector of a second local coordinate of a second triangle adjacent to the first triangle.

"The matrix generating unit may perform calculating a topological distance between the at least one eliminated vertex, and generating the covariance matrix including a covariance determined based on the topological distance, as an element.

"According to an embodiment, the domain-transforming unit may include an eigenvector calculating unit to calculate at least one eigenvector by performing eigenvector decomposition of the covariance matrix, and a coefficient calculating unit to calculate a coefficient of each of the at least one eigenvectors by calculating an inner product between the at least one eigenvector and at least one residual vector that is calculated through the estimation of the geometric information.

"According to another embodiment, the coefficient calculating unit may calculate a coefficient of each of the at least one eigenvectors by calculating an inner product between the at least one eigenvector and at least one element of at least one residual vector that is calculated through the estimation of the geometric information.

"The quantization unit may differently set a number of bits allocated to the quantization based on an importance of a coefficient extracted through the domain-transform.

"According to another aspect, there is provided an a 3D mesh decoding apparatus including an entropy decoding unit to extract restoration information to restore the 3D mesh by entropy-decoding of an inputted bit stream, a base mesh decoding unit to decode a base mesh based on the restoration information, a vertex decoding unit to restore an eliminated vertex based on a covariance matrix, and a mesh restoring unit to restore the 3D mesh based on the restored vertex data and the base mesh.

"According to still another aspect, there is provided a 3D mesh compression method including generating a base mesh by simplifying an inputted 3D mesh, coding the base mesh, and coding at least one vertex eliminated by the simplification, based on a covariance matrix.

"The 3D mesh compression method may further include transforming the coded base mesh and the coded at least one vertex into a bit stream by performing entropy-coding.

"According to an embodiment, the transforming may include recording an MSB first among the coded base mesh and geometric information associated with the at least one coded vertex to transform the recorded MSB into a bit stream.

"According to another embodiment, the transforming may include recording an LSB first among the coded base mesh and geometric information associated with the at least one coded vertex to transform the recorded LSB into a bit stream.

"The coding based on the covariance matrix may include estimating geometric information associated with the at least one eliminated vertex, segmenting the base mesh into at least one area, generating the covariance matrix based on connectivity information between the at least one eliminated vertex, performing a domain-transform based on the estimated geometric information and the covariance matrix, and quantizing a coefficient calculated through the domain-transform.

"The generating may perform calculating a topological distance between the at least one eliminated vertex, and generating the covariance matrix including a covariance determined based on the topological distance, as an element.

"According to an embodiment, the performing of the domain-transform may include calculating at least one eigenvector by performing eigenvector decomposition of the covariance matrix, and calculating a coefficient of each of the at least one eigenvector by calculating an inner product between the at least one eigenvector and at least one residual vector that is calculated through the estimation of the geometric information.

"According to another embodiment, the performing of domain-transforming may include calculating at least one eigenvector by performing eigenvector decomposition of the covariance matrix, and calculating a coefficient of each of the at least one eigenvectors by calculating an inner product between the at least one eigenvector and at least one element of at least one residual vector that is calculated through the estimation of the geometric information.

"According to another aspect, there is provided a geometric information estimation method that estimates geometric information of a vertex eliminated through mesh-simplification, and the geometric information estimation method may include determining a first predictive point of a first triangle of a base mesh and a second predictive point of a second triangle adjacent to the first triangle, determining a local coordinate of the first predictive point based on a normal vector and a tangent vector at the first predictive point, and an outer product vector between the normal vector and the tangent vector, determining a local coordinate of the second predictive point by projecting, onto a plane including the second triangle, the tangent vector of the first predictive point, and estimating the geometric information of the eliminated vertex based on the local coordinates of the triangles.

"The determining of the local coordinate of the second predictive point may include calculating an inner product of the normal vector of the first predictive point with a normal vector of the second predictive point, determining a tangent vector of the second predictive point by projecting the tangent vector of the first predictive point onto a plane including the second triangle, when the inner product is a positive number, determining, as the tangent vector of the second predictive point, an inverse vector of a vector obtained by projecting the tangent vector of the first predictive point onto the plane including the second triangle, when the inner product is a negative number, determining, as the tangent vector of the second predictive point, one of the normal vector of the first predictive point and an inverse vector of the normal vector of the first predictive point, when the inner product is zero, and determining the local coordinate of the second predictive point based on the tangent vector of the second predictive point, the normal vector of the second predictive point, an outer product vector between the tangent vector of the second predictive point and the normal vector of the second predictive vector.

"The determining, as the tangent vector of the second predictive point, of the one of the normal vector of the first predictive point and the inverse vector of the normal vector of the first predictive point may perform determining the inverse vector of the normal vector of the first predictive point as the tangent vector of the second predictive point, when the tangent vector of the first predictive point is identical to the normal vector of the second predictive point, and determining the normal vector of the first predictive point as the tangent vector of the second predictive point, when the tangent vector of the first predictive point is identical to an inverse vector of the normal vector of the second predictive point.

"Additional aspects, features, and/or advantages of embodiments will be set forth in part in the description which follows and, in part, will be apparent from the description, or may be learned by practice of the disclosure."

For more information, see this patent: Ahn, Min Su; Han, Jeong Hwan; Ahn, Jae Kyun; Lee, Dae Youn; Kim, Chang Su. Apparatus and Method for Coding a Three Dimensional Mesh. U.S. Patent Number 8805097, filed October 15, 2010, and published online on August 12, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8805097.PN.&OS=PN/8805097RS=PN/8805097

Keywords for this news article include: Samsung Electronics Co. Ltd.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering arts and entertainment, please see HispanicBusiness' Arts & Entertainment Channel



Source: Electronics Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters