Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1999-06-24
2003-12-23
Do, Anh Hong (Department: 2721)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C382S241000, C716S030000, C716S030000
Reexamination Certificate
active
06668091
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a progressive coding/decoding method of three-dimensional (3D) mesh data used in the fields of motion picture experts group-4 synthetic and natural hybrid coding (MPEG-4 SNHC), virtual reality modelling language (VRML) and the like.
2. Description of the Related Art
In transmitting 3D objects composed of 3D mesh data, it is very important to progressively restore transmitted data as well as to effectively code the 3D mesh data. In the event that a data error is generated due to a transmission path error, a progressive restoration would allow transmitted data to be partially restored and minimize the amount of mesh data to be retransmitted. The progressive restoration method which is robust against such communication path errors can be effectively used in wireless communications or low transmission rate communications. The purposes of the present invention are to construct connectivity, geometry and photometry necessary for progressively coding 3D mesh data and providing resilience against data errors, and to propose a coding/decoding method of the same.
The definitions of terms used in the art related to the invention will be first described as follows.
Polygonal mesh: A polygonal mesh is defined by coordinates (geometry) on a 3D space of vertices, the relationship (connectivity) between the respective faces and the vertices forming the same, and photometry such as color, normal or texture information, which do not affect the geometry of a mesh but affect the appearance of the mesh.
Face: A face is a set of vertex indices and a corner is a pair of (face, vertex) sets. A simple face is a set of vertex indices in which different indices form a face. In this invention, only a polygonal mesh consisting of simple faces will be dealt with.
Edge: A edge is a pair of vertex indices. If an edge appears on only one face in a polygonal mesh, the edge is defined as a “boundary” edge. If one and the same edge appears on several faces, the edge is defined as a “singular” edge. If an edge appears on only two neighboring faces, the edge is defined as an “internal” edge. The boundary edge and the internal edge are defined to be “regular”.
Mesh graph and dual graph: One point is defined within each face of a mesh and then points defined above and passing through the internal edge between neighboring faces are connected to be defined as a dual graph.
FIG. 5A
is a mesh graph and
FIG. 5B
is a dual graph.
Connected component: A path in a polygonal mesh is a series of non-recurrent vertices such as consecutive vertex pairs connected by one edge. The first and last vertices on a path are referred to as being connected by the path. If all pairs of the vertices of a triangular mesh are connected by one path, the triangular mesh is referred to as being connected. If a triangular mesh is not connected, the triangular mesh can be split into at least two connected components. Each connected component is a connected triangular mesh consisting of a subset of vertices, edges and triangles of the original triangular mesh. If two vertices of the triangular mesh are connected by one path, they belong to the same connected component.
Virtual reality modeling language (VRML): The VRML is a graphic standard format prepared for describing and transmitting a virtual space in the Internet.
Moving Picture Experts Group (MPEG): The MPEG is a group for carrying out international standardization activities for standardizing a compression format for transmitting a variety of media such as video.
Mesh: A mesh is a representation of an object constructed of several polygons.
Node: A node is a vertex in a vertex spanning graph or a minimum description unit used in VRML.
Topological surgery: A topological surgery is a mesh coding method proposed by I.B.M. Corp. in which a mesh is cut along a given path in order to make the mesh into the form of strips.
Vertex spanning graph: A vertex spanning graph is a path for cutting a mesh in the topological surgery.
Triangle spanning tree: The triangle spanning tree is a binary tree as a triangle strip produced by cutting a mesh along the vertex spanning graph
vrun: A vrun is a set of connected vertices and ends with a branch or vleaf.
vlast: A vlast indicates whether the current run is the last branch or not. If the current run is the last branch, the value of vlast is 1, and 0 otherwise.
vleaf: A vleaf indicates whether the current vertex run ends with a leaf or a branch. If the current vertex run ends with a leaf, the value of vleaf is 1, and 0 otherwise.
vlength is the length of a vertex run.
loopstart: The leaf of a vertex run may meet another vertex run to form a loop. In such a case, the start of the loop is indicated by the loopstart.
loopend: In the case when the leaf of a vertex run forms a loop, the end of the loop is indicated by the loopend.
loopmap: A loopmap indicates connectivity between the loopstart and the loopend and is a set of indices connecting edges from the loopend to the loopstart.
trun: A trun is a set of consecutive triangles and the end thereof is a leaf triangle or a branching triangle.
tleaf: A tleaf indicates whether the run of a triangle ends with a leaf triangle or a branching triangle. If the run of a triangle ends with a leaf triangle, the value of tleaf is 1, and 0 otherwise.
tmarching: A tmarching describes the marching aspect of triangles. If a strip has an edge at its right boundary, the value of tmarching is 1. If a strip has an edge at its left boundary, the value of tmarching is 0.
polygonedge: A polygonedge indicates whether a current edge is given from the original mesh model or inserted for representing the polygon as a set of triangles. If a current edge is given from the original mesh model, the value of polygonedge is 1, and 0, otherwise.
Torientation: A Torientation indicates whether the left or right side of the branching triangle is visited first. If the left side is visited first, 1 is given to the Torientation. If the right side is visited first, 0 is given.
In the conventional coding method of 3D mesh data, since the mesh data is wholly coded, it is almost impossible to partially restore data before an entire bitstream is received. Also, due to transmission path errors generated during transmission, even if only a part of the data is damaged, the entire bitstream of data must be received again. For example, ISO/IEC JTC1/SC29/WG11 MPEG-98/W2301, “MPEG-4 SNHC Verification Model 9.0” proposed by I.B.M. Corp. is currently being adopted as an MPEG-4 SNHC 3D mesh coding technology.
In MPEG-4 SNHC, mesh coding is designed based on VRML. In the VRML, a mesh is described in a node form referred to as an lndexedFaceSet. One of the main technologies for coding mesh data is a topological surgery proposed by I.B.M. Corp. According to this technology, it is assumed that a given mesh is the same as a sphere topologically. Then, the mesh is cut along a given cutting-edge to generate a triangle spanning graph having a binary tree structure. Here, the cutting-edge defined for cutting the mesh is configured such that it connects vertices, that is, it is given as a tree structure having a loop. The cutting-edge is referred to as a vertex spanning graph. Thus, two tree structures, that is, the triangle spanning graph and the vertex spanning graph, are coded/decoded, thereby restoring the original mesh without loss.
According to MPEG-4 SNHC, although there may be multiple IndexedFaceSets in a VRML file, compression is basically performed on the unit of one IndexedFaceSet. However, it is allowed to form a single IndexedFaceSet by several connected components.
In general, for fast graphics processing, modeling must be performed in units of triangles. These triangles are not formed randomly but are preferably connected to each other in the form of strips or fans. Also, the more symbols that are repeatedly represented, the better the compressibility is. To this end, a mesh formed by a single long triangular strip is proposed by I.B.M. Corp. in view of fast graphics proc
Han Mahn-jin
Jang Euee-seon
Jung Seok-yoon
Kim Sung-jin
Seo Yang-seock
Burns Doane , Swecker, Mathis LLP
Do Anh Hong
Samsung Electronics Co,. Ltd.
LandOfFree
3D mesh coding/decoding method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with 3D mesh coding/decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3D mesh coding/decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130122