I have the following problem: Given point sets $A$ and $B$, I want a labelling of the points in $A$ with points in $B$, i.e. $L:A\rightarrow B$.

The points $a\in A$ and $b\in B$ have associated (vector) descriptors, $h(a)$ and $h(b)$, so that a "distance" can be defined between the points in the set as $$ d_h(a,b) = ||h(a)-h(b)||_2 $$ Average error could then be: $$ d_H(L) = \frac{1}{|A|} \sum_{a\in A} d_h(a,L(a)) $$ But this is not good enough, because I need $L$ to preserve closeness. I.e. neighbourhoods in $A$ should also be roughly neighbourhoods after mapping. E.g. I could say I also want to minimize: $$ d_N(L) = \frac{1}{|A|} \sum_{a\in A} \sum_{s_i\in L_a} \sum_{s_j\in L_a} || s_i - s_j ||_2 $$ where $N(a)\subset A$ is a set of nearby points of $a$ and $L_a = L(N(a))=\{L(a_i)|a_i\in N(a)\}$.

This can be viewed as a kind of weighted approximate undirected graph matching. In other words the nodes of $A$ need to be mapped to nodes of $B$. Each graph has weights between each node in the graph, and weights between each of the nodes in $A$ and $B$. I need $L$ to be such that if $a_i$ is close to $a_j$, then $L(a_i)$ should be close to $L(a_j)$.

I can't really see an elegant way to solve this, except maybe by an optimization program minimizing some combination of $d_H(L)$ and $d_N(L)$ (which are not on the same scale).

But it seems like I should be able to apply expectation-maximization to it somehow. I.e. I could choose a starting labelling with $d_H$, estimate the error and a probability distribution per $a\in A$, compute a better labelling, and so on. Does someone know how that could work?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.