aMRG

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:

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.

COFF is an ASCII file format for color meshes. SKEL is an ASCII file format to represent skeletons (and aMRG).

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.

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]

Other related publications (PAMI'12, CVPR'09, CVPR'07, SMI'07, SMI'04, etc.) can be found here.

Downloads

Binaries:

Win7 (x86 - VC++2008): computeAMRG.exe (zip)

Linux (x86 - Debian Squeeze): computeAMRG.gz

Four 3D models to play with (in COFF format):

Win7: (HR) tony1.zip tony2.zip (LR) tony3.zip tony4.zip

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

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

Google Sites

Report abuse