Paper reference for EMD implementation

ThibaultGROUEIX commented 6 years ago

Hi Fei, Could you give a reference for the EMD approximation you implemented ? Also side question : i've experienced nan errors with EMD, is there a specific version of pytorch it is supposed to work with ? Thanks :) (and see you at CVPR :) )

fxia22 commented 6 years ago

It's from Hao's paper: https://arxiv.org/abs/1612.00603

I was able to run it on pytorch before v0.2, and haven't tested after that.

See you at CVPR :D, congrats on the spotlight!

ThibaultGROUEIX commented 6 years ago

I'm a bit confused. Hao's paper points to http://www.mit.edu/~dimitrib/TheAuctionAP.pdf which is better explained in https://web.eecs.umich.edu/~pettie/matching/Bertsekas-a-new-algorithm-assignment-problem-Mathematical-Programming-1981.pdf An clear open C implementation is available at https://github.com/maxdan94/auction/blob/master/auction.c But I can't relate it to what's done in https://github.com/fxia22/pointGAN/blob/master/emd/src/my_lib.c :/ Variables such as saturatedr, saturatedl, factorl, factorr, ss, ss2 are doesn't appear in the auction algorithm. Am I missing something ?

fxia22 commented 6 years ago

Interesting, I wrote the wrapper but never looked deep into that piece of C/CUDA code. At least that is what I was told, it could very well be that they did some adaptation to the original auction algorithm. Maybe @charlesq34 can point out if we missed something here?(thanks)

fxia22 commented 6 years ago

Let's move this conversation to personal channel btw.

fxia22 commented 6 years ago

BTW the nan gradient issue could be similar to #2.

mrquincle commented 5 years ago

Did you figure out which algorithm for the assignment problem / bipartite matching problem has been used? There is some loop over levels. For each level there are a few subloops. I don't see a subloop where it is iterated over a variable number, which you have for example with the Hungarian algorithm which is part of for example "A Near-Linear Constant-Factor Approximation for Euclidean Bipartite Matching" [pdf] to just mention a paper that has a concept of "level". So, who helps me out? @charlesq34 perhaps?

Colin97 commented 5 years ago

I'm a bit confused. Hao's paper points to http://www.mit.edu/~dimitrib/TheAuctionAP.pdf which is better explained in https://web.eecs.umich.edu/~pettie/matching/Bertsekas-a-new-algorithm-assignment-problem-Mathematical-Programming-1981.pdf An clear open C implementation is available at https://github.com/maxdan94/auction/blob/master/auction.c But I can't relate it to what's done in https://github.com/fxia22/pointGAN/blob/master/emd/src/my_lib.c :/ Variables such as saturatedr, saturatedl, factorl, factorr, ss, ss2 are doesn't appear in the auction algorithm. Am I missing something ?

@ThibaultGROUEIX Have you found out the reference for this implementation [https://github.com/fxia22/pointGAN/blob/master/emd/src/my_lib.c]? It seems to be a greedy algorithm rather than the auction algorithm mentioned above.

ThibaultGROUEIX commented 5 years ago

No i was not able to get to the bottom of this. At least I couldn't link this code to the auction algorithm as explained by Bertsekas. (maybe it would be good to reopen this issue)

Here is the list of other implementations of EMD i compiled for myself, in case that helps:

Deep Geometric Prior for Surface Reconstruction

in this repo

pytorch Approximate Wasserstein distances between point-clouds using the Sinkhorn method.

Pix3D and Dense 3D Point Cloud Reconstruction Using a Deep Pyramid Network.

tensorflow Unclear which version is implemented.

GEOmetrics

tensorflow Slightly different implementation

PointGan + PointSetGen

Pytorch and tensorflow https://github.com/fxia22/pointGAN/tree/dev/emd Unclear which version is implemented.

Geomloss

https://github.com/jeanfeydy/geomloss/tree/master/geomloss Sinkhorn

mrquincle commented 5 years ago

Yeah, I also asked here: https://github.com/optas/latent_3d_points/issues/2#issuecomment-466334808, but not much success. There's some epsilon scaling as described in the reference paper by Bertsekas on the so-called TRANSAUCTION algorithm. I found other algorithms to find "saturated cuts". It might be just a mix and match of different techniques.

gkioxari commented 4 years ago

To re-surface this issue, I heard back fro Charles and the author of the implementation and the verdict is that "... the code was designed by [author] and has no guarantee on its correctness or approximation accuracy. [Author] recommended not to use it in a serious use case."

Colin97 commented 4 years ago

To re-surface this issue, I heard back fro Charles and the author of the implementation and the verdict is that "... the code was designed by [author] and has no guarantee on its correctness or approximation accuracy. [Author] recommended not to use it in a serious use case."

Please take a look at our EMD implementation: https://github.com/Colin97/MSN-Point-Cloud-Completion

mrquincle commented 4 years ago

Ah, sweet! The paper is short on details. I've read the "Similarity Metric" section. Do you have more information? It states "The algorithm terminates in finite iterations and outputs an assignment of points whose the mean distance is within epsilon of being optimal. Here, epsilon is a parameter which balances the error rate and the speed of convergence". Do you have a proof that it terminates and that its result is within epsilon of being optimal?

fxia22 / pointGAN