The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Many modeling tasks in computer vision. e.g. structure from motion, shape/reflectance from shading, filter synthesis have a low-dimensional intrinsic structure even though the dimension of the input data can be relatively large. We propose a simple but surprisingly effective iterative randomized algorithm that drastically reduces the time required for recovering the intrinsic structure. The computational cost depends only on the intrinsic dimension of the structure of the task. It is based on the recently proposed Cascade Basis Reduction (CBR) algorithm that was developed in the context of steerable filters. A key feature of our algorithm compared with CBR is that an arbitrary apriori basis for the task is not required. This allows us to extend the applicability of the algorithm to tasks beyond steerable filters. We prove the convergence for the new algorithm and show that in practice the new algorithm is much faster than CBR for the same modeling error. We demonstrate this speed-up for the construction of a steerable basis for Gabor filters. We also demonstrate the generality of the new algorithm by applying it to to an example from structure from motion without missing data.

Keywords

Cascade Basis Reduction, SVD, filter synthesis

Notes

Text Reference

Shyjan Mahamud and Martial Hebert, "Efficient Recovery of Low-dimensional Structure from High-dimensional Data," IEEE International Conference on Computer Vision (ICCV), September, 1999.

BibTeX Reference

@inproceedings{Mahamud_1999_2606,
   author = "Shyjan Mahamud and Martial Hebert",
   title = "Efficient Recovery of Low-dimensional Structure from High-dimensional Data",
   booktitle = "IEEE International Conference on Computer Vision (ICCV)",
   publisher = "IEEE",
   month = "September",
   year = "1999",
}

The Robotics Institute

Menu