Progressive Compression of 3D Mesh Geometry Using Sparse Approximations from Redundant Frame Dictionaries

Abstract

The proliferation of sophisticated techniques for 3D model acquisition and graphic design in recent years is resulting in a rapid increase in the number and complexity of 3D models being produced. At the same time, the need for exchanging 3D models is also rising due to new computing paradigms (e.g., cloud computing) and an increase in collaborative applications and online social networks. This has created a need for efficient compression techniques for 3D models, which are progressive, allow high quality or even lossless reconstruction, and minimize the amount of transferred data. Most of the research on 3D model compression to date has focused on the compression of triangular surface meshes, as this is the most common representation for 3D objects. In particular, progressive compression techniques for 3D mesh models have become very popular in recent years, as they allow a mesh to be reconstructed from coarse to fine levels of detail at the decoder while the bitstream of data is still being received. Currently the best-performing progressive compression techniques seem to be those that use transform coding ideas borrowed from traditional signal and image processing. The fundamental assumption behind such techniques is that the input data can be represented as some sparse linear combination of atoms taken from a representative dictionary of atoms that constitute the new representation domain. Traditionally, these dictionaries have been chosen to be orthogonal bases; however, recent research into alternative signal representations has shown that overcomplete dictionaries, or frames, may be able to produce even sparser representations than orthogonal bases can. In the field of 3D mesh compression, the idea of using redundant representations has only just started to surface. The main challenge here is currently the creation of a good overcomplete dictionary, particularly for mesh models with irregular connectivity that needs to be preserved. In light of this, the main objective of the work in this thesis is to develop a new method for constructing a frame, which can be applied to a manifold triangle mesh directly (i.e., with no requirement for a prior remeshing to a more regular domain) and can be used to obtain sparse approximations of the mesh geometry in a progressive compression scenario. This is the main contribution of this thesis. The frames that we propose are constructed from the unit-norm eigenvectors of a combinatorial mesh Laplacian matrix, plus a large number of redundant linear combinations of these eigenvectors. A sparse synthesis of the input mesh geometry is achieved by selecting atoms from the frame using the Matching Pursuit algorithm. The proposed frames can be applied directly to a manifold mesh with arbitrary topology and connectivity type, as long as the mesh can be represented as a connected graph. Our experimental results for a variety of different mesh models indicate that, for a given reconstruction quality, a sparser approximation of the input mesh geometry can be obtained with the proposed frames than by decomposition of the mesh geometry onto the corresponding Laplacian basis. This sparsity can be further improved by increasing the frame redundancy. These gains in sparsity with the proposed frames are also shown to translate to gains in bitrate, even when an unoptimized encoding strategy is used. Our frames are designed to be particularly efficient for representing mesh models with smoothly varying surface features, but they can also capture well the features of CAD-like models that are typically characterized by sharp corners and large, flat areas. We believe that the proposed compression technique could be especially useful for compressing large databases of small mesh models that share the same connectivity, but also in applications where rapid previewing of a model is required, or potentially for rapid database search and retrieval. Our results indicate that the proposed technique, even in its prototype state, generally exhibits a superior rate-distortion performance to other existing progressive compression algorithms that use a transform coding approach, and this is especially evident at low bitrates. Apart from our main contribution, other contributions of this thesis include: the introduction of a new error metric for measuring shape dissimilarities between 3D models; a new investigation of a classic, wavelet-based mesh compression technique by using a combination of perceptual and geometric error metrics; a comparison of the MSDM2 perceptual metric to the distortion scores provided by a group of human observers in a real-use case scenario; an up-to-date literature review of existing 3D mesh compression techniques, using a new classification system for the existing progressive compression algorithms; and an up-to-date literature review of previous work on sparse representations from redundant dictionaries, which is relevant to the work presented in this thesis.