Permutation Diffusion Maps (PDMs)

We study the data (or image) association problem with applications in Computer Vision. We are specifically interested in unordered sets of images in the presence of large duplicate structures. Generally, the image to image associations derived from visual feature similarities alone. For example -- image match matrix for Structure from Motion (SfM). Due to the presence of large duplicate structure, visual feature similarities alone are misinformative; as a result, existing SfM algorithms are prone to making systematic, coherent errors which lead to poor 3D reconstructions. The new algorithm that we propose in this paper, Permutation Diffusion Maps (PDM), provides a mechanism for fully global reasoning based on putative pairwise matches. The key technical construct is the generalization of the concept of vector diffusion to permutations. PDM equips the data with a new similarity metric called permutation diffusion distance, which, we argue, is more meaningful than existing solutions. We show the utility of PDM on two applications, (1) SfM, and (2) Scene summarization.

Paper Poster

Acknowledgments

This work was supported in part by NSF − 1320344, NSF − 1320755 and by funding from the University of Wisconsin Graduate School. The authors would also like to acknowledge Dr. Li Zhang for scene summarization data and useful insight. We would also like to acknowledge Dr. Chuck Dyer for valuable discussions.

Note: Please open this webpage using Safari or Chrome. Videos may not apprear if opened in Firefox or IE.


Structure From Motion

We integrate the proposed data association strategy into an incremental structure from motion pipeline and demonstrate its efficiency on multiple challenging datasets. To see the 3D reconstruction for each dataset, please click the images below.

Cup Dataset Oats Dataset Book Dataset Desk Dataset
Scene Summarization

We considered the task of summarizing car models using few representative images from image dataset. To see the summary for each car model, please click the images below.
Hyundai Dataset Escalade Dataset
Go Back
 
Baseline reconstructionPDM reconstruction