Name
Abstract | ||
|---|---|---|
We present a practical algorithm that provably achieves the global optimum for a class of bilinear programs com- monly arising in computer vision applications. Our ap- proach relies on constructing tight convex relaxations of the objective function and minimizing it in a branch and bound framework. A key contribution of the paper is a novel, prov- ably convergent branching strategy that allows us to solve large-scale problems by restricting the branching dimensions to just one set of variables constituting the bilinearity. Experiments with synthetic and real data validate our claims of optimality, speed and convergence. We contrast the optimality of our solutions with those obtained by a tra- ditional singular value decomposition approach. Among sev- eral potential applications, we discuss two: exemplar-based face reconstruction and non-rigid structure from motion. In both cases, we compute the best bilinear fit that represents a shape, observed in a single image from an arbitrary view- point, as a combination of the elements of a basis. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/CVPR.2008.4587846 | CVPR |
Keywords | Field | DocType |
computer vision,convergence,convex programming,face recognition,image motion analysis,image reconstruction,image representation,linear programming,minimisation,relaxation theory,tree searching,branch and bound framework,computer vision,convergent branching strategy,convex relaxations,exemplar-based face reconstruction,nonrigid structure,objective function minimisation,optimal bilinear programming,shape representation | Convergence (routing),Structure from motion,Singular value decomposition,Computer vision,Branch and bound,Mathematical optimization,Computer science,Minimisation (psychology),Artificial intelligence,Linear programming,Convex optimization,Bilinear interpolation | Conference |
Volume | Issue | ISSN |
2008 | 1 | 1063-6919 |
Citations | PageRank | References |
11 | 0.90 | 25 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manmohan Chandraker | 1 | 451 | 25.58 |
| David Kriegman | 2 | 7693 | 451.96 |