search

optas / latent_3d_points

Auto-encoding & Generating 3D Point-Clouds.
Other
506 stars 109 forks source link

Question about EMD algorithm #2

Closed godspeed1989 closed 6 years ago

godspeed1989 commented 6 years ago

Is there any theoretical reference for the EMD algorithm implemented in tf_approxmatch.cpp?

optas commented 6 years ago

Here it is: D. P. Bertsekas. A distributed asynchronous relaxation algorithm for the assignment problem. In Decision and Control, 1985 24th IEEE Conference on, pages 1703–1704. IEEE, 1985.

mrquincle commented 5 years ago

The code that belongs to this paper can be found on the website of Bertsekas https://web.mit.edu/dimitrib/www/noc.htm in Fortran at https://web.mit.edu/dimitrib/www/lopnet.txt (it is labeled RELAX_QC). Now is the Fortran code not the easiest to read, but it just doesn't look like the same thing. Maybe it's another algorithm by Bertsekas.

optas commented 5 years ago

Hi Anne,

Thank you very much for your overall interest and the applied diligence.

The losses (Chamfer/EMD) are pieces of code we used from an external project (namely, the of https://arxiv.org/abs/1612.00603).

I have not personally look closely at their implementation. Perhaps you want to reach to the developers directly?

We appreciate your feedback and I am more than happy to discuss this further.

Best, Panos

On Feb 21, 2019, at 7:21 AM, Anne van Rossum notifications@github.com<mailto:notifications@github.com> wrote:

The code that belongs to this paper can be found on the website of Bertsekas https://web.mit.edu/dimitrib/www/noc.htm in Fortran at https://web.mit.edu/dimitrib/www/lopnet.txt (it is labeled RELAX_QC). Now is the Fortran code not the easiest to read, but it just doesn't look like the same thing. Maybe it's another algorithm by Bertsekas.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHubhttps://github.com/optas/latent_3d_points/issues/2#issuecomment-466039678, or mute the threadhttps://github.com/notifications/unsubscribe-auth/ADkopDPisWxrouVdN_UKeTDEYe11Kp6nks5vPrmDgaJpZM4RDNCS.

mrquincle commented 5 years ago

Thanks I will do so! I was already reading through Hao Su's (impressive) PhD thesis, https://cseweb.ucsd.edu/~haosu/papers/thesis_finalversion.pdf, page 109 where he describes that he used a (1 + epsilon) approximation scheme from Bertsekas. He references that particular paper as well. However, Bertsekas has also described an auction algorithm for the transportation problem in particular: https://www.researchgate.net/publication/225431349_The_auction_algorithm_for_the_transportation_problem

It's by the way not that I think it's something completely different. I see "epsilon scaling" is used. Describing the TRANSAUCTION code Bertsekas mentions how he starts from a large value and ends with epsilon = 1 / min(M,N) and how in the implementation he just multiplies all costs with min(M,N), so the algorithm's final value for epsilon = 1. However, details are different, and I want to adjust it to a different version of EMD, so I've to know exactly what happens here. :-)

Off topic: sweet talk by Bertsekas https://www.youtube.com/watch?v=T-fSmSqzcqE - describes a little bit his history. It's quite cute. :-)