Informatics, TU Vienna

General, nested, and constrained Wiberg minimization

Ultra-wide baseline matching

Wiberg matrix factorization breaks a matrix Y into low-rank factors U and V by solving for V in closed form given U, linearizing V(U) about U, and iteratively minimizing ||Y - UV(U)|| with respect to U only. This approach factors the matrix while effectively removing V from the minimization. We generalize this approach to more general L1 minimization problems that are nonlinear in both U and V, which might normally be attacked with expectation-minimization. We also show how one Wiberg minimization can be nested inside another, effectively eliminating two of three sets of variables from a minimization, and how Wiberg minimization can solve constrained problems. We apply the algorithm to L1 bundle adjustment (general Wiberg), L1 projective bundle adjustment (nested Wiberg), and multiple instance learning (constrained Wiberg).

Ultra-wide baseline matching

Ultra-wide baseline matching attempts to automatically match building facade points in aerial and Street View images, for 3D modeling from both datasets and for “bundling the world.” This problem is difficult because of the extreme difference in the facades’ appearance, viewpoint,
and parallax between the two image sets. But, by exploiting rough prior estimates for the pose and building geometry and using some special sauce we’ve discovered, it’s possible to attack this problem using local descriptors. I’ll describe our special sauce and show many of the (correct and incorrect) matches we’ve produced.


Dennis received a B.S. from the University of Wisconsin in 1994, an M.S. from the University of Illinois in 1996, and a Ph.D. from Carnegie Mellon in 2004, all in computer science. He worked at K2T, Inc. (now Quantapoint, 1996-1998), Honeywell (2005-2006), and Google (2006-present), where he is an engineer in the machine perception group. His research interests are in computer vision and optimization.