Name
Abstract | ||
|---|---|---|
This paper shows that structure from motion is NP-hard for most sensible cost functions when missing data is al- lowed. The result provides a fundamental limitation of what is possible to achieve with any structure from motion algo- rithm. Even though there are recent, promising attempts to compute globally optimal solutions, there is no hope of ob- taining a polynomial time algorithm unless P=NP. The proof proceeds by encoding an arbitrary Boolean formula as a structure from motion problem of polynomial size, such that the structure from motion problem has a zero cost solution if and only if the Boolean formula is satisfi- able. Hence, if there was a guaranteed way to minimize the error of the relevant family of structure from motion prob- lems in polynomial time, the NP-complete problem 3SAT could be solved in polynomial time, which would imply that P=NP. The proof relies heavily on results from both struc- ture from motion and complexity theory. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/ICCV.2007.4409095 | ICCV |
Keywords | Field | DocType |
computational complexity,image coding,image motion analysis,polynomials,Boolean formula,NP-complete problem,NP-hard,arbitrary Boolean formula,encoding,missing data,motion algorithm,polynomial time algorithm | Structure from motion,Cook–Levin theorem,Karp–Lipton theorem,Discrete mathematics,Polynomial,Computer science,Boolean satisfiability problem,co-NP-complete,Time complexity,Computational complexity theory | Conference |
Volume | Issue | ISSN |
2007 | 1 | 1550-5499 |
Citations | PageRank | References |
5 | 0.50 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Nistér | 1 | 2265 | 118.02 |
| Fredrik Kahl | 2 | 1415 | 92.61 |
| Henrik Stewenius | 3 | 2777 | 165.83 |