Sunday, January 10, 2010

Measuring the difference between two meshes

Computing the geometric difference between two 3D models is a quite common task in mesh processing. In our lab, many years ago (11 !), we developed and freely distributed the standard tool for such task, Metro, whose paper has been cited more than 500 times . While Metro is still a small open source standalone command line program available at our web site, its functionality have been integrated into MeshLab in the filter Sampling->Hausdorff Distance, and they can be used in a variety of ways.
So here is a short basic tutorial.

Start with a mesh (in the following the well known Stanford Happy Buddha (1087716 triangles). Aggressively simplify it in a significant way to just 50k tris (e.g. 1/20 of the original size). Reload the original mesh as a new layer. At this point you should have two approximation of the same shape well aligned in the same space. Toggling the visibility on and off of each mesh you should easily see the difference between the two meshes (tip: ctrl+click over the eye icon in the layers window turn off all the other layers).

Now you are ready to start the Hausdorff distance filter.  First of all remember that the Hausdorff Distance between two meshes is a the maximum between the two so-called one-sided Hausdorff distances (technically not they are not a distance):
These two measures are not symmetric (e.g. the results depends on what mesh you set as X or Y).
In the Hausdorff filters MeshLab computes only the one-sided version
leaving the task of getting the maximum of the two to the user.

Now on the practical side. MeshLab uses a sampling approach to compute the above formula taking a bunch of points over a mesh X and searching for each x the closest point y on a mesh Y. That means that the result is strongly affected on how many points do you take over X and there are a lot of option on for that. A common very simple approach is just to use the vertexes of the highest density mesh as sampling points (e.g. the original Buddha vertexes): to do this simply leave checked only the "vertex sampling" option in the filter dialog and be sure that the number of samples is greater or equal than the vertex number. After a few secs the filter ends writing down in the layers log windows the collected info. Something like:

: Hausdorff Distance computed
: Sample 543652
: min : 0.000000 max 0.001862
: mean : 0.000029 RMS : 0.000083
: Values w.r.t. BBox Diag (0.229031)
: min : 0.000000 max 0.008128
: mean : 0.000126 RMS : 0.000361

For sake of human readability the filter reports the values in the mesh units (whatever they are) and with respect to the diagonal of the bounding box of the mesh that is something you are always able to understand without knowing anything about the model units. For example in this case you can see that the maximum error between the two mesh is approximately 1% of the bbox diag, but on the average the two meshes are almost in the 1/10000 range.


The filter save in the all-purpose quality field of the vertexes of the sampled mesh the computed distance values. To better visualize the error you can simply convert these values (for the high resolution mesh) into colors using the Color->Colorize by quality filter that maps them in to a rather red-green-blue colormap. Usually given the non uniform distribution of the values you have to play a bit with the filter parameters clamping the mapping range to something meaningful (only a few points have the maximum so with a linear mapping of the values over the whole range will result into a almost uniform red mesh. Note that it is a red-green-blu map, so red is min and blue is max, so in our case red means zero error (good) and blue high error (bad).
The next image sequence report just a small detail of the one of the points with higher error. During the simplification we removed some topological noise, (the thin tubes connecting the two side of the hole)  from a Hausdorff point of view it is a rather large error: the points in the middle of the thin tubes has nothing in the simplified mesh that is close to them; so they bring up the maximum error significantly. Luckily enough they represent only a small portion of the whole mesh so the average error remains low.


Note that if you measure the other one-sided Hausdorff distance, that specific mesh portion will not denote any particular error, because in that case you sample the simplified mesh and for each point of the simplified mesh there are points of the original mesh that are quite close to them. In other words, in this case the simplified mesh is close to the original one, but the original one is not close to the simplified one.

Next post will discuss some remaining issues including the sampling of the surface, looking at all the taken samples and the found closest points and how to colorize the low resolution mesh...
Second part of the tutorial here.

48 comments:

天天月月年年 said...

hi, this is useful. But I still do not know to to get a color map for the Hausdorf distances between two meshes. Can you give a list of operations like 1) File->open 2) File->open as a new layer 3)...

Thank you very much !!!

ALoopingIcon said...

In summary the operations are:

1) Load two meshes as layers
2) Sampling->Hausdorff Distance: checking only the "sample vertexes" option. You get the result in the log window
3) Color->Colorize by Quality, Adjust the range to get the interesting values well mapped in the red-green-blue colormap

Let me know for what part of the above you need more info.

Cheers
P.

Olivier said...

Hey there, great stuff this MeshLab! I just found out about it, it seems pretty nice. Any idea when the next post will be? Because I'd be quite interested to know how to colorise the low resolution mesh as well. Color->Colorize by Quality does not work in that case.

Esfahlan said...

Hi
Which one represent Hausdorff distance? max, min, RMS or mean?

ALoopingIcon said...

@Esfahlan

By definition, the Hausdorff distance is the one-sided max of the min distance. However in practice the mean or RMS measures are quite useful (much less sensible to outliers).

Cheers
P.

Stuart Dunning said...

Hi, very useful, but for me it is also the direction of difference, I have negative and positive distances (before and after image) - in some parts Mesh 1 protrudes beyond Mesh 2, and in others it is behind. Is there a way to get at that rather than pure 'distance'? I guess this might mean defining a direction?

Ke Jiang said...
This comment has been removed by the author.
Ke Jiang said...

Hi, I have two meshes that are not very similar to compare. They are reconstructed from the point cloud of a wooden boat. I try to see the difference of the boat over time, since wood is sensitive and would transform due to the environment... Anyway, I aligned and used the Hausdorff distance filter with my meshes, but the result seems not right. The filter report says no point is sampled from the mesh.

What should I do with this condition? Or is it because these two meshes are too different (seems not)?

Aurore said...

Hi!

How can I display a scale showing the differences between the distances?

Thanks in advance!

vaggos said...

Dear Aurore,
if you mean how to show up the color-map scale, you may go Edit -> Quality Mapper. There you can find a range of choices.

markus dreck said...

Since this description is a little outdated, i took the time to do a in detail procedure for computing the Housdorff Dist. in Meshlab V1.3.3

Since i am not an expert in MeshLab you are welcome to suggest better ways. It seems rather complicated to me!

1)load or generate the two meshes. (Let's say A and B, where B is the mesh you want colored).
2)right click on B in the Layer Dialog (Ctrl-L if invisible) and select "Define new Per Vertex Attribute"
choose a name (e.g "Quality") and choose "q" as the Function.
3)Make sure that B is selected in the Layer Dialog
3)Compute the Hausdorff Distance (Filters: Sampling->Hausdorff Distance) With Sampled Mesh = B and Target Mesh = A
4)repeat 3) and Click the colored Rabit (or Edit:QualityMapperDialog) and Click Apply
5)Make A invisible (click the eye in the Layer Dialog)

Cheerz M

MedZag said...

Hi,

Is there a way I can know the positive and negative mesh surface differencse rather than absolute differences?

Thank you in advance.
Dalia

Swapnil Mali said...

Can anyone provide command to compare two mashes ?

Thanks

Angad Bajwa said...

I saw that error percentage was calculated. Can anyone elaborate as to what parameters were used to do that?

Were the rms , mean , min and max values used for it?
Could you give the formula for this?

Karthika Shree said...

I am expecting more interesting topics from you. And this was nice content and definitely it will be useful for many people.

Matlab Training in Chennai

Karthika Shree said...

I am expecting more interesting topics from you. And this was nice content and definitely it will be useful for many people.

Matlab Training in Chennai

Brenda Smith said...

You have already made my day. By submitting this post you do me a fever. There are some post I have seen but not like this. You have submit the article with some good image. I have a blog with full of post in this category. You all can visit my blog. paper comparison checker.

traverse jamaica said...

Thank you for taking the time and sharing this information with us. It was indeed very helpful and insightful while being straight forward and to the point.
mcdonaldsgutscheine.net/ | startlr.com/ | saludlimpia.com/

suresh H said...

This information is impressive..I am inspired with your post writing style & how continuously you describe this topic. After reading your post,thanks for taking the time to discuss this, I feel happy about it and I love learning more about this topic Excellent article.
AngularJS Training Institute in Chennai
AngularJS Cetification Training in Chennai
AWS Training in Chennai
AWS Devops Training in Chennai
DevOps Certification in Chennai
DevOPs Certification Training Institute in Chennai
Best AngularJS Training in Chennai
AngularJS Training in Chennai

anushka sharma said...

Thank you for sharing the useful information.MATLAB training in chennai

Coepd BA Trainings said...

We at Coepd declared Data Science Internship Programs (Self sponsored) for professionals who want to have hands on experience. We are providing this program in alliance with IT Companies in COEPD Hyderabad premises. This program is dedicated to our unwavering participants predominantly acknowledging and appreciating the fact that they are on the path of making a career in Data Science discipline. This internship is designed to ensure that in addition to gaining the requisite theoretical knowledge, the readers gain sufficient hands-on practice and practical know-how to master the nitty-gritty of the Data Science profession. More than a training institute, COEPD today stands differentiated as a mission to help you "Build your dream career" - COEPD way.

http://www.coepd.com/AnalyticsInternship.html

pooja saravanan said...

This is very good content you share on this blog. it's very informative and provide me future related information.

Hadoop Training in Chennai

Hadoop Training in Bangalore

Big data training in tambaram

Big data training in Sholinganallur

Big data training in annanagar

aruna raj said...

I enjoy what you guys are usually up too. This sort of clever work and coverage! Keep up the wonderful works guys I’ve added you guys to my blog roll.


MEAN stack training in Chennai

MEAN stack training in bangalore

MEAN stack training in tambaram

MEAN stack training in annanagar

MEAN stack training in Velachery

shalinipriya said...

Its really an Excellent post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog. Thanks for sharing....
Data Science Training in Chennai
Data science training in bangalore
Data science online training
Data science training in pune
Data science training in kalyan nagar

Ram priya said...

Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging.

Devops training in Chennai
Devops training in Bangalore
Devops Online training
Devops training in Pune

Sanaa Ibraham said...

Hello Sir,
How can I benefit from the measurements in the comparison and what does RMS means?

gowsalya said...

Great post! I am actually getting ready to across this information, It’s very helpful for this blog.Also great with all of the valuable information you have Keep up the good work you are doing well.
Devops Training in Chennai

Devops Training in Bangalore

gkr ragini said...

The knowledge of technology you have been sharing thorough this post is very much helpful to develop new idea. here by i also want to share this.

Devops Training in pune

Devops training in tambaram
Devops training in velachery
Devops training in annanagar
DevOps online Training

amilu B said...

Nice tutorial. Thanks for sharing the valuable information. it’s really helpful. Who want to learn this blog most helpful. Keep sharing on updated tutorials…
java training in chennai | java training in bangalore

java training in tambaram | java training in velachery

java training in omr | oracle training in chennai

kevingeorge said...


Great post! I am actually getting ready to across this information, It’s very helpful for this blog.Also great with all of the valuable information you have Keep up the good work you are doing well.

rpa training in Chennai

rpa training in anna nagar | rpa training in marathahalli

rpa training in btm | rpa training in kalyan nagar

rpa training in electronic city | rpa training in chennai

rpa online training | selenium training in training

kevingeorge said...


Great post! I am actually getting ready to across this information, It’s very helpful for this blog.Also great with all of the valuable information you have Keep up the good work you are doing well.

rpa training in Chennai

rpa training in anna nagar | rpa training in marathahalli

rpa training in btm | rpa training in kalyan nagar

rpa training in electronic city | rpa training in chennai

rpa online training | selenium training in training

Mouni yoga said...

Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care and we take your comments to heart.As always, we appreciate your confidence and trust in us
Python training in marathahalli
Python training in pune
AWS Training in chennai

Mouni yoga said...

I always enjoy reading quality articles by an individual who is obviously knowledgeable on their chosen subject. Ill be watching this post with much interest. Keep up the great work, I will be back
python training in rajajinagar
Python training in btm
Python training in usa

simbu said...

I prefer to study this kind of material. Nicely written information in this post, the quality of content is fine and the conclusion is lovely. Things are very open and intensely clear explanation of issues
java training in chennai | java training in USA

selenium training in chennai

Sugi Bala said...

It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...

java training in chennai | java training in bangalore

java online training | java training in pune

Deepika Analy said...

Great work. Quite a useful post, I learned some new points here.I wish you luck as you continue to follow that passion.

Cloud Training
Cloud Training in Chennai

pavithra dass said...

Whatever we gathered information from the blogs, we should implement that in practically then only we can understand that exact thing clearly, but it’s no need to do it, because you have explained the concepts very well. It was crystal clear, keep sharing..

Amazon Web Services Training in Chennai
Best AWS Training in Bangalore
AWS Training in Nolambur
AWS Training in Guindy

kanchi sandeep said...


Nice blog..! I really loved reading through this article. Thanks for sharing such a amazing post with us and keep blogging...

ABiNitio online training in Hyderabad

ABiNitio training in Hyderabad

online ABiNitio training in Hyderabad

SUN TRAININGS said...


It's Amazing! Am exceptionally Glad to peruse your blog. Numerous Will Get Good Knowledge After Reading Your Blog With The Good Stuff. Continue Sharing This Type Of Blogs For Further Uses.
data science online training in Hyderabad
best data science online training in Hyderabad
data science training in Hyderabad

kanchi sandeep said...

Nice blog..! I really loved reading through this article. Thanks for sharing such a amazing post with us and keep blogging...

ABiNitio online training in Hyderabad

ABiNitio training in Hyderabad

online ABiNitio training in Hyderabad

kanchi sandeep said...

Nice blog..! I really loved reading through this article. Thanks for sharing such a amazing post with us and keep blogging...

ABiNitio online training in Hyderabad

ABiNitio training in Hyderabad

online ABiNitio training in Hyderabad

Nila shri said...

I likeable the posts and offbeat format you've got here! I’d wish many thanks for sharing your expertise and also the time it took to post!!

Data Science training in rajaji nagar | Data Science with Python training in chenni
Data Science training in electronic city | Data Science training in USA
Data science training in pune | Data science training in kalyan nagar

SUN TRAININGS said...

I really Enjoyed your blog and we loved it To maintain reagularly!

Tableau online training in Hyderabad

Best Tableau online training in usa

Tableau training in uk

pavithra dass said...

Superb. I really enjoyed very much with this article here. Really it is an amazing article I had ever read. I hope it will help a lot for all. Thank you so much for this amazing posts and please keep update like this excellent article. thank you for sharing such a great blog with us. expecting for yours.
Angularjs Training in Chennai
Angularjs Training
Angularjs course in Chennai
Angularjs Training institute in Chennai
Angular 2 Training in Chennai
Angular 4 Training in Chennai

Mouni yoga said...

Your good knowledge and kindness in playing with all the pieces were very useful. I don’t know what I would have done if I had not encountered such a step like this.
python training in pune
python training institute in chennai
python training in Bangalore

gowsalya said...

Thank you for allowing me to read it, welcome to the next in a recent article. And thanks for sharing the nice article, keep posting or updating news article.
Online DevOps Certification Course - Gangboard
Best Devops Training institute in Chennai

akhilapriya404 said...

I really enjoy the blog.Much thanks again. Really Great core Java online course

sathya shri said...

Needed to compose you a very little word to thank you yet again regarding the nice suggestions you’ve contributed here.

angularjs Training in bangalore

angularjs Training in bangalore

angularjs Training in btm

angularjs Training in electronic-city

angularjs online Training