News Column

Patent Issued for Three Dimensional Data Compression

July 15, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- From Alexandria, Virginia, VerticalNews journalists report that a patent by the inventors Lee, Ken (Fairfax, VA); Hou, Xin (Falls Church, VA), filed on January 20, 2012, was published online on July 1, 2014.

The patent's assignee for patent number 8766979 is VanGogh Imaging, Inc. (McLean, VA).

News editors obtained the following quote from the background information supplied by the inventors: "Three dimensional (3D) imaging is a technique of creating the illusion of depth in an image so that the depth is perceived by a viewer. As 3D applications become more widespread, accurate 3D data compression is becoming more and more important. For example, considerations for 3D applications include not only the speed of rendering, but also the speed of 3D data processing (e.g., such as registration and merging), and the size of memories to save the 3D files.

"Triangle mesh compression is a type of data compression that often involves reducing the number of triangles in the mesh while attempting to preserve the overall shape, volume, and boundaries of the mesh. There are a number of different approaches to triangle mesh compression. A first example, often referred to as coplanar facets merging, searches the facets (or triangle planes in the mesh) to identify facets that are coplanar or nearly coplanar. The identified facets are merged into large polygons to simplify the overall mesh.

"A second example, often referred to as controlled vertex/edge/facet decimation, iteratively eliminates components (e.g., such as vertices, edges and facets) in the mesh. Components are often selected for elimination based on local optimization criteria (e.g., criteria that only preserves the shape (such as high curvature parts) of 3D data without considering other things, such as the distance and angle relative to the viewer or 3D camera) that will preserve the overall shape of mesh.

"A third example, often referred to as vertex clustering, groups vertices of the triangle mesh into clusters, and computes a new representative vertex for each cluster. A fourth example, often referred to as a wavelet-based approach, usually includes a three phases process of re-meshing, re-sampling and wavelet parameterization, to build a multi-resolution representation of the surface. However most triangle mesh compression algorithms just consider the overall shape preservation of the meshes (e.g., regardless of the depth of the mesh)."

As a supplement to the background information on this patent, VerticalNews correspondents also obtained the inventors' summary information for this patent: "Compression that incorporates the depth of the mesh can generate compressed 3D data with little, if any, impact on a user's experience. For example, human eyes are not extremely sensitive to the objects in a 3D scene that are far away from the viewer, or at the edge of vision of the viewer. Therefore, the meshes that are further away from the viewer or at the edge of the viewer's vision can be compressed more than other meshes in the scene with little, if any, notice to the viewer (e.g., such that the compressed meshes with texture, from the viewer's perspective, are nearly the same as the original meshes with texture).

"In one aspect, there is a computerized method. The computerized method is for compressing three dimensional data of a scene. The computerized method includes receiving, by a computing device, data including (i) three dimensional data of a scene, and (ii) depth data associated with the three dimensional data. The computerized method includes generating, by the computing device, a triangle mesh based on the three dimensional data, the triangle mesh including a plurality of triangles, each triangle including three vertices and three edges connecting the three vertices. The computerized method includes calculating, by the computing device, for each edge in the triangle mesh, a metric for the edge based on data from the depth data associated with the edge, a length of the edge, and a curvature of the edge. The computerized method includes collapsing, by the computing device, a set of edges based on a metric associated with each edge in the set of edges to generate a compressed triangle mesh.

"In another aspect, there is a computer program product. The computer program product is tangibly embodied in a non-transitory computer readable medium. The computer program product includes instructions being operable to cause a data processing apparatus to receive data including (i) three dimensional data of a scene, and (ii) depth data associated with the three dimensional data. The computer program product includes instructions being operable to cause a data processing apparatus to generate a triangle mesh based on the three dimensional data, the triangle mesh including a plurality of triangles, each triangle including three vertices and three edges connecting the three vertices. The computer program product includes instructions being operable to cause a data processing apparatus to calculate for each edge in the triangle mesh, a metric for the edge based on data from the depth data associated with the edge, a length of the edge, and a curvature of the edge. The computer program product includes instructions being operable to cause a data processing apparatus to collapse a set of edges based on a metric associated with each edge in the set of edges to generate a compressed triangle mesh.

"In another aspect, there is a computing device. The computing device is for compressing three dimensional data of a scene. The computing device includes a receiving module configured to receive data including (i) three dimensional data of a scene, and (ii) depth data associated with the three dimensional data. The computing device includes a processing module in communication with the receiving module configured to generate a triangle mesh based on the three dimensional data, the triangle mesh including a plurality of triangles, each triangle including three vertices and three edges connecting the three vertices. The computing module is configured to calculate for each edge in the triangle mesh, a metric for the edge based on data from the depth data associated with the edge, a length of the edge, and a curvature of the edge. The computing module is configured to collapse a set of edges based on a metric associated with each edge in the set of edges to generate a compressed triangle mesh.

"In another aspect, there is an apparatus. The apparatus is for compressing three dimensional data of a scene. The apparatus includes a means for receiving data including (i) three dimensional data of a scene, and (ii) depth data associated with the three dimensional data. The apparatus includes a means for (i) generating a triangle mesh based on the three dimensional data, the triangle mesh including a plurality of triangles, each triangle including three vertices and three edges connecting the three vertices, (ii) calculating for each edge in the triangle mesh, a metric for the edge based on data from the depth data associated with the edge, a length of the edge, and a curvature of the edge, and (iii) collapsing a set of edges based on a metric associated with each edge in the set of edges to generate a compressed triangle mesh.

"In other examples, any of the aspects above can include one or more of the following features. In some examples, the received data includes (iii) texture data associated with the three dimensional data, the method further including generating compressed three dimensional data including the compressed triangle mesh and the texture data, wherein the texture data is not modified. Generating the triangle mesh can include generating the triangle mesh based on the depth data associated with the three dimensional data.

"In other examples, collapsing an edge from the set of edges, the edge including a first vertex and a second vertex, includes moving the first vertex to a same location as a location of the second vertex, such that the edge is removed from the triangle mesh. A first set of edges can include the first vertex as an vertex, and collapsing can include adjusting the first set of edges to include the second vertex instead of the first vertex. Generating the triangle mesh can include generating the triangle mesh based on the three dimensional data such that objects in the three dimensional data are not distinguished among using separate triangle meshes.

"In some examples, calculating a metric for an edge includes calculating a metric for a vertex based on: (i) a curvature metric calculated based on neighboring edges that include the vertex, (ii) a distance metric calculated based on a depth from the depth data associated with the vertex, and (iii) an angle metric calculated based on an angle between a normal of the vertex and a direction of a data capturing device that captured the data, wherein the normal is calculated by averaging a normal for each facet in a set of facets in the triangle mesh that contain the vertex.

"In other examples, calculating, for each edge in the triangle mesh, a metric for the edge comprises calculating a metric for each vertex in the triangle mesh based on (i) data from the depth data associated with the vertex, (ii) a length of one or more edges that include the vertex as an end point, and (iii) a curvature of one or more edges of a line that include the vertex as an end point. The set of edges to collapse can be calculated based on: (i) a desired compression ratio, and (ii) a metric associated with each edge in the set of edges. The computing device can include a cell phone, a smart phone, a personal data assistant, a field-programmable gate array, or any combination thereof.

"The techniques, which include both methods and apparatuses, described herein can provide one or more of the following advantages. The 3D data can be accurately compressed with little, if any, impact on the user's perception of the 3D scene. A cost of portions of a 3D model (e.g., a triangle mesh) can be calculated and used to compress certain portions of the 3D model. For example, the metric can be higher for closer objects in the 3D model (e.g., and therefore more likely to cause noticeable distortion to a viewer if collapsed) and lower for objects that are further away (e.g., and therefore less likely to cause noticeable distortion to a viewer if collapsed). Thus, portions with a lower metric can be compressed more than portions with a higher metric without drastically impacting a user's perception of the 3D scene.

"The 3D model can be compressed to achieve a desired compression ratio. Additionally, new components (e.g., vertices, edges) are not added to the 3D model, so the relationship between the 3D data and other information (e.g., the texture data) is maintained. The compression can drastically reduce the size of 3D data files, and therefore the compressed 3D data can therefore be saved easier and/or transmitted easier, and devices can process the compressed 3D data easier than uncompressed 3D data (or data compressed using different computerized methods).

"Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating the principles of the invention by way of example only."

For additional information on this patent, see: Lee, Ken; Hou, Xin. Three Dimensional Data Compression. U.S. Patent Number 8766979, filed January 20, 2012, and published online on July 1, 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=8766979.PN.&OS=PN/8766979RS=PN/8766979

Keywords for this news article include: VanGogh Imaging Inc, Information Technology, Information and Data Processing, Information and Data Compression.

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


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






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