3D Point Cloud Reduction
using Mixed-integer Quadratic Programming

*Hyun Soo Park1, *Yu Wang1, Eriko Nurvitadhi2, James C. Hoe1, Yaser Sheikh1, and Mei Chen2

1Carnegie Mellon University
2Intel Science and Technology Center

* Both authors contributed equally to this work.

Our method signi´Čücantly reduces the number of points. Grey points are original 3D points, blue points are the reduced subset, and red points are reconstructed image locations.


Large scale 3D image localization requires computationally expensive matching between 2D feature points in the query image and a 3D point cloud. In this paper, we present a method to accelerate the matching process and to reduce the memory footprint by analyzing the view-statistics of points in a training corpus. Given a training image set that is representative of common views of a scene, our approach identifies a compact subset of the 3D point cloud for efficient localization, while achieving comparable localization performance to using the full 3D point cloud. We demonstrate that the problem can be precisely formulated as a mixed-integer quadratic program and present a pointwise descriptor calibration process to improve matching. We show that our algorithm outperforms the state-of-theart greedy algorithm on standard datasets, on measures of both point-cloud compression and localization accuracy.


*Hyun Soo Park, *Yu Wang, Eriko Nurvitadhi, James C. Hoe, Yaser Sheikh, Mei Chen,"3D Point Cloud Reduction using Mixed-integer Quadratic Programming", Second International Workshop on Visual Analysis and Geo-Localization of Large-Scale Imagery in conjunction with IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013 [pdf, video, bib]


PPTX (147Mb)