Verifying Global Minima for L 2 Minimization Problems in Multiple View Geometry

We consider the least-squares (L2) minimization problems in multiple view geometry for triangulation, homography, camera resectioning and structure-and-motion with known rotation, or known plane. Although optimal algorithms have been given for these problems under an L-infinity cost function, finding optimal least-squares solutions to these problems is difficult, since the cost functions are not convex, and in the worst case may have multiple minima. Iterative methods can be used to find a good solution, but this may be a local minimum. This paper provides a method for verifying whether a local-minimum solution is globally optimal, by providing a simple and rapid test involving the Hessian of the cost function. The basic idea is that by showing that the cost function is convex in a restricted but large enough neighbourhood, a sufficient condition for global optimality is obtained. The method is tested on numerous problem instances of real data sets. In the vast majority of cases we are able to verify that the solutions are optimal, in particular, for small to medium-scale problems.     

Only connect

It is supposedly easier to connect with other human beings in the era of ubiquitous technology. Connecting requires action and an element of risk taking in a context of dynamic uncertainty and incomplete information. The article explores what is involved in developing sustainable connections. We reflect on the context of “Socially Useful Artificial Intelligence”, the focus of the first article in issue 1.1.1987 of AI & Society, and explore subsequent research in a changing world. The arguments are illustrated through an account of the development of the Penny University, from a London coffee house to a potential international virtual institution.     

The Capabilities of Some Species of Artificial Organisms

Abstract

A species of artificial organism in which individuals consist of freely interacting elementary components enclosed in an expandible envelope is described. Some organisms of this species are shown to be universal instruction-obeying mechanisms. Several procedures by which such artificial organisms might reproduce are presented and discussed.     

Look-Ahead and One-Person Games

Abstract

A preliminary investigation of the role of look-ahead in one-person games is presented. The use of look-ahead in comparing the effectiveness of different heuristic functions is discussed. There is a survey of recent work in tree-searching including that of Doran and Michie [4], Hart, Nilsson, and Raphael [7] and Pohl [17]–[19]. Based on some of Pohl's results, two theorems are proven in Section 2. These suggest a possible use for look-ahead. Some experimental results are presented in Section 3 which satisfy to a limited degree the aforementioned theorems, and some additional observations are made. In conclusion, an attempt is presented to relate look-ahead to the notion of “informedness” introduced by Hart, Nilsson, and Raphael. Finally, some further directions for research are suggested.