# A Physicist's View on Partial 3D Shape Matching
## 2 A Physics Approach to Shape Comparison
### The Optimal Balanced Transport Problem  
A full description of this formalism is provided in [47; 54]. We outline the method here as it is key to the framework proposed in this paper. The sets of vertices of the two meshes are relabeled as \(S_{1}\) of size \(N_{1}\) and \(S_{2}\) of size \(N_{2}\). Each point \(k\) in \(S_{1}\) (resp \(S_{2}\)) is allocated a \"mass\" \(m_{1}(k)\) (respectively, \(m_{2}(k)\)). We ensure that \(\sum_{k}m_{1}(k)=\sum_{l}m_{2}(l)\), namely, that we have balance. For convenience, we set those two sums to be \(1\). We encode the cost of transport between \(S_{1}\) and \(S_{2}\) as a positive matrix \(C(k,l)\) with \(k\in\{1\ldots,N_{1}\}\) and \(l\in\{1\ldots,N_{2}\}\). \(C(k,l)\) is set to the L1 or L2-norm of the difference of the signatures of the points \(k\) and \(l\) on \(\mathcal{M}_{1}\) and \(\mathcal{M}_{2}\), respectively (see Implementations for the choice of the norm). The OT problem can then be stated as finding a transportation matrix \(G\) between \(S_{1}\) and \(S_{2}\) that minimizes the transport cost \(U\) defined as  
\[U(G)=\sum_{k,l}G(k,l)C(k,l), \tag{6}\]  
where the summations extend over all \(k\in\{1\ldots,N_{1}\}\) and \(l\in\{1\ldots,N_{2}\}\). The minimum of \(U\) is to be found for the values of \(G(k,l)\) that satisfy the following constraints:  
\[\forall(k,l),\quad G(k,l)\geq 0, \tag{7}\] \[\forall k,\quad\sum_{l}G(k,l)=m_{1}(k),\] \[\forall l,\quad\sum_{k}G(k,l)=m_{2}(l).\]  
The solution to the OT problem provides an optimal transport plan \(G_{opt}\) and the corresponding minimum transport cost \(U_{min}=U(G_{opt})\). We adopt a reasoning common in statistical physics. A system in thermal equilibrium at a fixed temperature will sample a large number of states. The likelihood that this system will exist in any certain condition is represented by the associated Gibbs distribution. The state with the least energy is the one that is most likely. Therefore, the problem of minimizing an energy function can be recast as the problem of locating the most likely state of the system it characterizes. This system corresponds to the polytope \(\mathcal{G}(S_{1},S_{2})\) of all transportation plans that are in compliance with the constraints defined in Equation (7). To find the most probable state, we consider the partition function \(Z_{\beta}(S_{1},S_{2})\) computed over all states in this polytope, given by  
\[Z_{\beta}(S_{1},S_{2})=e^{-\beta\mathcal{F}_{\beta}(S_{1},S_{2})}=\int_{G\in \mathcal{G}(S_{1},S_{2})}e^{-\beta U(G)}d\mu_{12}. \tag{8}\]  
Note that \(\beta=1/k_{B}T\), with \(k_{B}\) the Boltzmann constant and \(T\) the temperature. \(d\mu_{12}\) is an integration variable that can be assimilated to the Lebesgue measure for the space of transportation plans. \(\mathcal{F}_{\beta}(S_{1},S_{2})\) is the free energy of the system. Unfortunately, it is not possible to explicitly calculate this free energy. Instead, we suggest a method that estimates the extremum of this free energy using the concept of saddle point approximation. Considering the constraints defined in Equation (7) and the fact that \(0\leq G(k,l)\leq 1\), \(Z_{\beta}(S_{1},S_{2})\) can be expressed as  
\[Z=\int_{0}^{1}\prod_{kl}dG(k,l)e^{-\beta\sum\limits_{kl}C(k,l)G( k,l)}\] \[\prod_{k}\delta\left(\sum_{l}G(k,l)-m_{1}(k)\right)\prod_{l} \delta\left(\sum_{k}G(k,l)-m_{2}(l)\right). \tag{9}\]  
We can represent the delta functions using the Fourier transform, adding new auxiliary variables \(\lambda(k)\) and \(\mu(l)\). Ignoring some multiplicative constants, the partition function can then be expressed as  
\[Z=\int_{-i\infty}^{+i\infty}\prod_{k}d\lambda(k)\int_{-i\infty}^ {+i\infty}\prod_{l}d\mu(l)\int_{0}^{1}\prod_{k,l}dG(k,l)\] \[e^{-\beta\sum\limits_{kl}G(k,l)(C(k,l)+\lambda(k)+\mu(l)+\beta \left(\sum\limits_{k}\lambda(k)m_{1}(k)+\sum\limits_{l}\mu(l)m_{2}(l)\right)}. \tag{10}\]  
Note that the \(\lambda(k)\) and \(\mu(l)\) are imaginary complex numbers.