June 1999

The goal of this project is the development of a technology for the recovery of 3D free-form object and selected scene structure from one or more images and video. It is based on the development of 3D shape representation and a semi-interactive, mixed-initiative system, along with machine decision-directed Bayesian surface-estimation. The main focus of this effort will be the development of tools useful in archaeological site and artifact reconstruction and architecture. This will impact low level shape models and how they are assembled to form either more complex objects or complete ones. The latter condition often occurs at archaeological excavation sites where objects are found in pieces, or have been damaged from erosion.

Despite the recent substantial progress in automated scene recovery in computer vision, the challenges presented by such free-form shape extraction and assembly are still great. We propose an interactive approach to the problem in which a user can guide the recovery process or can be available when requested for assistance by the machine, e.g., in the complex task of assembling many fragments to re-create a large or complicated object. The intent is to develop the fundamentals of a user-controlled technology for the benefit of the naive user. It would then be usable in home, office, industry, entertainment, defense, science, and other domains. The ultimate aim is to significantly enhance productivity in interacting with large amounts of complex visual data by modeling the underlying 3D structure.

Specifically, the objective is to develop both an intuitive, but formal, language for describing arbitrary complex free-form 3D shapes in terms of skeletal graphs, ridges and algebraic surfaces, and an associated gesture-based human-machine interface for generating and interacting with such 3D shapes in relation to multiple views of a scene. This capability is then used in conjunction with user-determined, coarse camera geometry to generate an estimate of the scene geometry from multiple views. Finally, the coarse initial estimates of camera and scene geometry are used in a Bayesian machine decision-directed framework relying on this free-form language of shape to recover the detailed structure of the scene. The premise is that the use of qualitative free-form models reduces the description length and consequently the dimensionality of the search space, while the use of initial user-determined estimates of scene geometry reduces the search range, thus avoiding the pitfalls of a global search. The use of models also greatly increases reconstruction accuracy as it circumvents point matching in multiple images. Machine decision-directed estimation relieves the user from inputting extensive detail, except where called upon for help by the machine. An aim is to evolve a system having decreasing dependence on human-computer interactions (HCI).

In addition, an existing platform for HCI (``Sketch'') allows us to focus, develop and evolve all new work around a continually functional system, thus taking full advantage of challenges and constraints posed by it. The development of this system will be done synergistically by applying reconstruction, shape modeling and object documentation to an archaeological site in Petra, Jordan. Here, major structures (walls, columns, column capitals, statuary and smaller artifacts) must be reconstructed from scattered fragments. This will influence low-level shape modeling and estimation, and methodologies for assembling these estimated models into semi-global and global structures.

This work will have impact by providing new practical tools. It will also provide an effective testbed for 3D shape reconstruction and recognition, more descriptive local and global models for working with 3D shapes, a better understanding of human/decision-making-machine interaction for free-form geometric modeling and for extracting 3D geometry from one or more images and video, and associated computational complexity issues. As applied to the field of archaeology, this technology will provide improved surveying methods, an advanced archaeological record and a means to conduct high-level analysis not heretofore available. It will further permit the transfer of reconstruction capabilities from the artist directly to the archaeologists. Since the problems resolved in the archaeological context are rather generic, and thus transferable to the medical fields, industry, defense, entertainment, etc., the impact will be broad.