aMRG - the augmented Multiresolution Reeb Graph Last update: August 2011
Previous update: May 2011
 Keywords
Reeb graph, Morse theory, 3D shape descriptor, topology matching, shape retrieval, 3D model indexing.
Read me
This page contains binaries to compute augmented Multiresolution Reeb Graphs (aMRG) as they were described in my Ph.D. thesis and in the related papers (see below).
The aMRG is a high level 3D shape descriptor. It allows the user to represent 3D surface models by graphs having homotopy property and at several levels of resolution (0 to 5).
The graphs are constructed based on the Morse theory and preserve surface topology. Furthermore, they can be encoded as feature vectors for shape similarity estimation.
The provided binary is a versatile executable file. It allows the user to:
1) compute an aMRG as a feature vector (*.mrg) from a 3D mesh model:
.\computeAMRG toto.off --> toto.mrg : aMRG feature vector
_toto.off : subdivided mesh in COFF format (colorcode w.r.t. Morse function values)
_toto.tri : subdivided mesh in TRI format (see below for details)
2) compute aMRG graphs for representation at different levels of resolution (0 to 5):
.\computeAMRG toto.mrg --> 0_toto.skel 1_toto.skel 2_toto.skel 3_toto.skel 4_toto.skel 5_toto.skel
0_toto.gph 1_toto.gph 2_toto.gph 3_toto.gph 4_toto.gph 5_toto.gph
3) compare two aMRG feature vectors and return a similarity score:
.\computeAMRG toto.mrg tata.mrg --> float in [0,1] (0 is identity)
NB about file formats: COFF is an ASCII file format for color meshes. SKEL is an ASCII file format to represent skeletons (and aMRG). TRI is a binary file format for triangular meshes. GPH is a binary file format to represent aMRG. COFF and SKEL files can be visualized using an OFF viewer like geomview. More here. TRI and GPH files can be visualized using the viewer developed by Dr. Carlos Hernández Esteban: here. Tips for visualization with TexMesh3D: (1) add both mesh (.tri) and graph (.gph) files, and put the graph on top of the mesh in the Object list. (2) select the mesh, select Data visualization mode, and choose color representation with <, >, Pg Up, Pg Dn. (3) adjust the mesh Surface property Opacity to see the graph trough the surface mesh as shown in the figure above. Details
In the executable all parameters are hard coded. See the library to set your own parameters.
Levels of resolution for graph computation are from 0 to 5. Level of resolution for aMRG matching is r=3.
We use the integral of geodesic distances as Morse function f as described in [Hilaga et al., SIGGRAPH'01].
Our normalization is: fN=(f-fmin)/(fmax-fmin).
Each node of the aMRG embeds the following weighted attributes: surface area (*0.2) + Morse function value (*0.3) + cord length histo (*0.1) + cord angle1 histo (*0.1) + cord angle2 histo (*0.1) + curvature index histo (*0.1) + 3D Hough transform (*0.1) + ratio (*0.0). These parameters were chosen heuristically to favor topology over geometry. The description of the parameters can be found in [Tung et al., Int'l Jour. Shape Modeling 2005]
Limitation
3D mesh models should be manifold surfaces, otherwise you will see some warning/error messages. Only the biggest surface connected component is taken into account. => So, you may need to fix or re-mesh your objects first; MeshLab can be helpful.
Accepted input file formats are: OFF, COFF, NOFF, STL, (most of) VRML, TRI (from ENST Archive).
References Please refer to the following publication for citations: T.Tung and F.Schmitt. Other related publications (PAMI'12, CVPR'09, CVPR'07, SMI'07, SMI'04, etc.) can be found here.The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes, International Journal of Shape Modeling (IJSM), Vol.11, No.1, pp. 91-120, June 2005. [pdf][EE] Linux (x86 - Debian Squeeze): computeAMRG.gz
Four 3D models to play with (in COFF format):
Linux: (HR) tony1.off.gz tony2.off.gz (LR) tony3.off.gz tony4.off.gz
(./computeAMRG tony1.mrg tony2.mrg -> 0.263)
Some very nice 3D models are here: ENST Archive. Various 3D shape descriptors implemented (by myself) in the open source library FVS: [sourceforge]
NB1: Computation time of high resolution 3D models is pretty decent with good machines.
However, if you want to run the software on a notebook, it is better to simplify the meshes first.
NB2: Feel free to inform me by e-mail if you plan to use the Binaries for publication. I'd be happy follow and cite your work in the future.
<NEW!> Library: To test yourself the aMRG with different parameters (e.g., weight attributes), use the library libamrg.a with all the header files given in the matchMesh project here: [GitHub]. Below is a simple example in C/C++ of how you can use it. #include "3dfiles.h" #include "object.h" #include "mrgraph.h" #include "byteOrder.h" #include "point3.h" #include "pointsi.h" #include "similarity.h" /**/ int res=5; Object *obj=NULL; read3D(obj, "file.off", NULL, 0, true); obj->computeMuValues(); obj->subdivide(res); int nbPoints=obj->getNbPoints(); int nbFaces=obj->getNbFaces(); int nbEdges=obj->getNbEdges(); point_3* point=obj->pointNb(i); //arbitrary i MRG* mrg=obj->computeMRG(res); int nbNodes=mrg->nbNodes[res]; MRGNode* oneNode=mrg->nodes[res][i]; //arbitrary i int ResMax=3; int cumul= 1; int dist = 6; // 6:histo intersection float factor[NbAttributes]; //defined in mrgraph.h float l_ratio0; factor[0]=0.2f; //l_area factor[1]=0.3f; //l_mu factor[2]=0.0f; //l_vol factor[3]=0.1f; //l_cordsL factor[4]=0.1f; //l_cords1 factor[5]=0.1f; //l_cords2 factor[6]=0.1f; //l_curvI factor[7]=0.1f; //l_hough3D factor[8]=0.0f; factor[9]=0.0f; l_ratio0=0.0f; //ratio PairList MPair; float *Value=computeSimilarity(mrg1, mrg2, MPair, factor, ResMax, cumul, dist); float val=1-(Value[9+ResMax*NbAttributes]+l_ratio0*(1-fabs(mrg1->getNode(0,0)->getAttribute()->ratio-mrg2->getNode(0,0)->getAttribute()->ratio))); LICENSE Copyright Tony TUNG (c) 2005,2014 <tonytung.org> Please refrain from distributing this beta version (especially if you modify it), and use it for research purpose only. License details will be provided soon. Should you have a request, feel free to contact me: tony2ng _at_ gmail.com |