The fraction of incorrect permutations as a function of noise for symmetric group of order n. Various colors represent varying m, m=10 (red), m=50 (blue) and m=100 (green).
The problem of matching not just two, but m different sets of objects to each other arises in many contexts, including finding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, Permutation Synchronization, which finds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efficient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods.
Paper Supplement material Data
This work was supported in part by NSF − 1320344, NSF − 1320755 and by funding from the University of Wisconsin Graduate School.
We present a generic set up for applications that require synchronization over symmetric group (Sn) for any kind of later analysis. In particular, this demonstrate the potential use of our method in areas outside Computer Vision.
We considered a matching problem which include a set of n objects. We randomly simulated m permutation (σ1,σ2,...,σm) from the uniform distribution over Sn, each representing an independent ordering of to be matched objects. For each pair (σi,σj), we compute pairwise assignments as τ_ji=σjσi^{-1}. Permutation matrix corresponding to τ_ji becomes the (i,j) block of the objective matrix T. In this simulation, one can introduce noise by replacing the correct τ_ji by a random permutation, and corresponding permutation matrix. This corresponds to more realistic (corrupt) T. Permutation synchronization method takes this objective matrix T as input and recover ground truth permutations. These permutations can be used to produce pairwise assignments eventually.
The fraction of incorrect permutations as a function of noise for symmetric group of order n. Various colors represent varying m, m=10 (red), m=50 (blue) and m=100 (green).
Download the simulation code here.
We used CMU House dataset for this experiment. Shape context features are used to obtain pairwise assignments and to construct the objective matrix. The results of proposed permutation synchronization method on this data are summarized below. Our implementation is available here.
Matches found for a representative image pair. (Green circles) landmarks, (green lines) ground truth, (red lines) found matches. (Left) Pairwise linear assignment, (right) Permutation Synchronization.
Note that less visible green is good.
Normalized error as dataset (m) increases on the House dataset. Permutation Synchronization (blue) vs.~the pairwise Kuhn-Munkres baseline (red).
Please report bugs and errors to pachauri@cs.wisc.edu