Distinguished Dissertations – serie

Accurate Visual Metrology from Single and Multiple Uncalibrated Images presents novel techniques for constructing three-dimensional models from bi-dimensional images using virtual reality tools. Antonio Criminisi develops the mathematical theory of computing world measurements from single images, and builds up a hierarchy of novel, flexible techniques to make measurements and reconstruct three-dimensional scenes from uncalibrated images, paying particular attention to the accuracy of the reconstruction.This book includes examples of interesting viable applications (eg. Forensic Science, History of Art, Virtual Reality, Architectural and indoor measurements), presented in a simple way, accompanied by pictures, diagrams and plenty of worked examples to help the reader understand and implement the algorithms.

Sir Isaac Newton's philosophi Naturalis Principia Mathematica'(the Principia) contains a prose-style mixture of geometric and limit reasoning that has often been viewed as logically vague.In A Combination of Geometry Theorem Proving and Nonstandard Analysis, Jacques Fleuriot presents a formalization of Lemmas and Propositions from the Principia using a combination of methods from geometry and nonstandard analysis. The mechanization of the procedures, which respects much of Newton's original reasoning, is developed within the theorem prover Isabelle. The application of this framework to the mechanization of elementary real analysis using nonstandard techniques is also discussed.

First, I would like to thank my principal supervisor Dr Qiang Shen for all his help, advice and friendship throughout. Many thanks also to my second supervisor Dr Peter Jarvis for his enthusiasm, help and friendship. I would also like to thank the other members of the Approximate and Qualitative Reasoning group at Edinburgh who have also helped and inspired me. This project has been funded by an EPSRC studentship, award num­ ber 97305803. I would like, therefore, to extend my gratitude to EPSRC for supporting this work. Many thanks to the staff at Edinburgh University for all their help and support and for promptly fixing any technical problems that I have had . My whole family have been both encouraging and supportive throughout the completion of this book, for which I am forever indebted. York, April 2003 Ian Miguel Contents List of Figures XV 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 Solving Classical CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 2 Applicat ions of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. 3 Limitations of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 3. 1 Flexible CSP 6 1. 3. 2 Dynamic CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 4 Dynamic Flexible CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 5 Flexible Planning: a DFCSP Application . . . . . . . . . . . . . . . . . . 8 1. 6 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 7 Contributions and their Significance 11 2 The Constraint Satisfaction Problem 13 2. 1 Constraints and Constraint Graphs . . . . . . . . .. . . . . . . . . . . . . . 13 2. 2 Tree Search Solution Techniques for Classical CSP . . . . . . . . . . 16 2. 2. 1 Backtrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. 2. 2 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 2. 3 Conflict-Directed Backjumping . . . . . . . . . . . . . . . . . . . . . 19 2. 2. 4 Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

This book investigates sets of images consisting of many overlapping viewsofa scene, and how the information contained within them may be combined to produce single images of superior quality. The generic name for such techniques is frame fusion. Using frame fusion, it is possible to extend the fieldof view beyond that ofany single image, to reduce noise, to restore high-frequency content, and even to increase spatial resolution and dynamic range. The aim in this book is to develop efficient, robust and automated frame fusion algorithms which may be applied to real image sequences. An essential step required to enable frame fusion is image registration: computing the point-to-point mapping between images in their overlapping region. This sub­ problem is considered in detail, and a robust and efficient solution is proposed and its accuracy evaluated. Two forms of frame fusion are then considered: image mosaic­ ing and super-resolution. Image mosaicing is the alignment of multiple images into a large composition which represents part of a 3D scene. Super-resolution is a more sophisticated technique which aims to restore poor-quality video sequences by mod­ elling and removing the degradations inherent in the imaging process, such as noise, blur and spatial-sampling. A key element in this book is the assumption of a completely uncalibrated cam­ era. No prior knowledge of the camera parameters, its motion, optics or photometric characteristics is assumed. The power of the methods is illustrated with many real image sequence examples.

Classifier systems are an intriguing approach to a broad range of machine learning problems, based on automated generation and evaluation of condi­ tion/action rules.

The topic of the research reported here is direct user participation in the task-based development of interactive software systems. Building usable software demands understanding and supporting users and their tasks. Users are a primary source of usability requirements and knowledge, since users can be expected to have intimate and extensive knowledge of themselves, their tasks and their working environment. Task analysis approaches to software development encourage a focus on supporting users and their tasks while participatory design approaches encourage users' direct, active contributions to software development work. However, participatory design approaches often concentrate their efforts on design activities rather than on wider system development activities, while task analysis approaches generally lack active user participation beyond initial data gathering. This research attempts an integration of the strengths of task analysis and user participation within an overall software development process. This work also presents detailed empirical and theoretical analyses of what it is for users and developers to cooperate, of the nature of user-developer interaction in participatory settings. Furthermore, it makes operational and assesses the effectiveness of user participation in development and the impact of user-developer cooperation on the resulting software product. The research addressed these issues through the development and application of an approach to task based participatory development in two real world development projects. In this integrated approach, the respective strengths of task analysis and participatory design methods complemented each other's weaker aspects.

Object-oriented inheritance has been in widespread use for a decade, and it is now realised that although inheritance is a powerful modelling tool with many associated advantages, its benefits are not automatically conferred on systems that simply use it.This book introduces a model of inheritance based around five fundamental inheritance relationships. Each relationship has a clear conceptual basis, representing a fundamental, specialised use of inheritance. The resulting model replaces a confused notion of inheritance with five distinct conceptual relationships supporting more precise modelling of systems and capturing the semantic intent of each use of inheritance within a system.

Asynchronous System-on-Chip Interconnect describes the use of an entirely asynchronous system-bus for the modular construction of integrated circuits. Industry is just awakening to the benefits of asynchronous design in avoiding the problems of clock-skew and multiple clock-domains, an din parallel with this is coming to grips with Intellectual Property (IP) based design flows which emphasise the need for a flexible interconnect strategy. In this book, John Bainbridge investigates the design of an asynchronous on-chip interconnect, looking at all the stages of the design from the choice of wiring layout, through asynchronous signalling protocols to the higher level problems involved in supporting split transactions. The MARBLE bus (the first asynchronous SoC bus) used in a commercial demonstrator chip containing a mixture of asynchronous and synchronous macrocells is used as a concrete example throughout the book.

In recent years, Artificial Intelligence researchers have largely focused their efforts on solving specific problems, with less emphasis on 'the big picture' - automating large scale tasks which require human-level intelligence to undertake. The subject of this book, automated theory formation in mathematics, is such a large scale task. Automated theory formation requires the invention of new concepts, the calculating of examples, the making of conjectures and the proving of theorems. This book, representing four years of PhD work by Dr. Simon Colton demonstrates how theory formation can be automated. Building on over 20 years of research into constructing an automated mathematician carried out in Professor Alan Bundy's mathematical reasoning group in Edinburgh, Dr. Colton has implemented the HR system as a solution to the problem of forming theories by computer. HR uses various pieces of mathematical software, including automated theorem provers, model generators and databases, to build a theory from the bare minimum of information - the axioms of a domain. The main application of this work has been mathematical discovery, and HR has had many successes. In particular, it has invented 20 new types of number of sufficient interest to be accepted into the Encyclopaedia of Integer Sequences, a repository of over 60,000 sequences contributed by many (human) mathematicians.

This book is a minor revision of the thesis submitted in August 1996; no major changes have been made. However, I would like to take this opportunity to mention that since the thesis was written, discoveries have been made which would allow a substantial simplification and strengthening of the results in Chapters 3 and 6. In particular, it is now possible to model sums correctly in the category I as well as in £, which means that the definability results of Chapter 6 can be stated and proved at the intensional level, making them simpler and much closer in spirit to the original proofs of Abramsky, Jagadeesan, Malacaria, Hyland, Ong and Nickau [10,61,79]. This also leads quite straightforwardly to an understanding of call-by-value languages. Details of these improvements can be found in [14,73]. It is also worth mentioning that progress has been made on some of the topics suggested for future research in Chapter 7. In particular, fully abstract models have been found for various kinds of languages with local variables [8,13-16], and a fully complete games model of the polymorphic language System F has been constructed by Hughes [59]. Guy McCusker February 1998 Acknowledgements First of all, I must thank my supervisor, Samson Abramsky. It was he who first introduced me to game semantics and suggested avenues of research in the area; this book would certainly not exist were it not for him.

A central problem in computer vision is to track objects as they move and deform in a video sequence. Stochastic algorithms -- in particular, particle filters and the Condensation algorithm -- have dramatically enhanced the state of the art for such visual tracking problems in recent years. This book presents a unified framework for visual tracking using particle filters, including the new technique of partitioned sampling which can alleviate the "curse of dimensionality" suffered by standard particle filters. The book also introduces the notion of contour likelihood: a collection of models for assessing object shape, colour and motion, which are derived from the statistical properties of image features. Because of their statistical nature, contour likelihoods are ideal for use in stochastic algorithms. A unifying theme of the book is the use of statistics and probability, which enable the final output of the algorithms presented to be interpreted as the computer's "belief" about the state of the world. The book will be of use and interest to students, researchers and practitioners in computer vision, and assumes only an elementary knowledge of probability theory.

Randomized Algorithms discusses two problems of fine pedigree: counting and generation, both of which are of fundamental importance to discrete mathematics and probability. When asking questions like "How many are there?" and "What does it look like on average?" of families of combinatorial structures, answers are often difficult to find -- we can be blocked by seemingly intractable algorithms. Randomized Algorithms shows how to get around the problem of intractability with the Markov chain Monte Carlo method, as well as highlighting the method's natural limits. It uses the technique of coupling before introducing "path coupling" a new technique which radically simplifies and improves upon previous methods in the area.

Architecture-independent programming and automatic parallelisation have long been regarded as two different means of alleviating the prohibitive costs of parallel software development. Building on recent advances in both areas, Architecture-Independent Loop Parallelisation proposes a unified approach to the parallelisation of scientific computing code. This novel approach is based on the bulk-synchronous parallel model of computation, and succeeds in automatically generating parallel code that is architecture-independent, scalable, and of analytically predictable performance.

Models of Sharing Graphs presents a sound mathematical basis for reasoning about models of computation involving shared resources, including graph rewriting systems, denotational semantics and concurrency theory. An algebraic approach, based on the language of category theory, is taken throughout this work, which enables the author to describe several aspects of the notion of sharing in a systematic way. In particular, a novel account of recursive computation created from cyclic sharing is developed using this framework.

Collaborative virtual environments are multi-user virtual realities which actively support communication and co-operation. This book addresses the theory, design, realisation and evaluation of such systems, with a particular emphasis on support for large numbers of distributed users. A broad approach is taken, which ranges from the sociology of interpersonal communication to the management of communication in distributed systems. The emphasis on multi-user environments distinguishes this book from the many general books on virtual reality which only deal with single-user systems. This book presents: models of multi-party awareness and interaction in space-based systems; detailed designs of two prototypes (MASSIVE-1 and MASSIVE-2); experiences with collaborative virtual environments created using these; and analyses of the corresponding network requirements. Many of these results and ideas are applicable to other systems and approaches.

Extensional Constructs in Intensional Type Theory presents a novel approach to the treatment of equality in Martin-Loef type theory (a basis for important work in mechanised mathematics and program verification). Martin Hofmann attempts to reconcile the two different ways that type theories deal with identity types. The book will be of interest particularly to researchers with mainly theoretical interests and implementors of type theory based proof assistants, and also fourth year undergraduates who will find it useful as part of an advanced course on type theory.

This book discusses the use of the real numbers in theorem proving. Typ­ ically, theorem provers only support a few 'discrete' datatypes such as the natural numbers. However the availability of the real numbers opens up many interesting and important application areas, such as the verification of float­ ing point hardware and hybrid systems. It also allows the formalization of many more branches of classical mathematics, which is particularly relevant for attempts to inject more rigour into computer algebra systems. Our work is conducted in a version of the HOL theorem prover. We de­ scribe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis. We also describe an advanced derived decision procedure for the 'Tarski subset' of real algebra as well as some more modest but practically useful tools for automating explicit calculations and routine linear arithmetic reasoning. Finally, we consider in more detail two interesting application areas. We discuss the desirability of combining the rigour of theorem provers with the power and convenience of computer algebra systems, and explain a method we have used in practice to achieve this. We then move on to the verification of floating point hardware. After a careful discussion of possible correctness specifications, we report on two case studies, one involving a transcendental function.

This book updates the thesis I produced for my PhD at the Department of Artificial Intelligence of the University of Edinburgh, correcting errors, and improving some of the formatting and readability. Since the original work was completed (early 1996), research has progressed. Most notably, the public profile of AI and game-playing has reached new heights with the feats of the chess computer DEEPER BLUE (which surely uses AI, no matter what IBM would have us believe). Although less heralded, the ability of computers to play Bridge (the main example domain in this book) has also increased. In July of 1997 a world championship for computer Bridge programs was hosted by the American Contract Bridge League in Albuquerque, New Mex­ ico. This contest was won by a program called Bridge Baron, produced by Great Game Products. Bridge Baron incorporates knowledge-based planning techniques developed by Stephen Smith and Dana Nau [1, 2]. Progress has also been made on the contrasting, more brute-force, approach of sampling the possible card distributions. In particular, Matt Ginsberg has developed a fast double-dummy solver based on partition search [3]. Ginsberg's program fared poorly in the 1997 Bridge championships, but Ginsberg himself reports very promising results [4] on a hard set of complete Bridge deals taken from the Bridge tutoring program Bridge Master.

Evolution through natural selection has been going on for a very long time. Evolution through artificial selection has been practiced by humans for a large part of our history, in the breeding of plants and livestock. Artificial evolution, where we evolve an artifact through artificial selection, has been around since electronic computers became common: about 30 years. Right from the beginning, people have suggested using artificial evolution to design electronics automatically.l Only recently, though, have suitable re­ configurable silicon chips become available that make it easy for artificial evolution to work with a real, physical, electronic medium: before them, ex­ periments had to be done entirely in software simulations. Early research concentrated on the potential applications opened-up by the raw speed ad­ vantage of dedicated digital hardware over software simulation on a general­ purpose computer. This book is an attempt to show that there is more to it than that. In fact, a radically new viewpoint is possible, with fascinating consequences. This book was written as a doctoral thesis, submitted in September 1996. As such, it was a rather daring exercise in ruthless brevity. Believing that the contribution I had to make was essentially a simple one, I resisted being drawn into peripheral discussions. In the places where I deliberately drop a subject, this implies neither that it's not interesting, nor that it's not relevant: just that it's not a crucial part of the tale I want to tell here.

The topic of the research reported here is direct user participation in the task-based development of interactive software systems. Building usable software demands understanding and supporting users and their tasks. Users are a primary source of usability requirements and knowledge, since users can be expected to have intimate and extensive knowledge of themselves, their tasks and their working environment. Task analysis approaches to software development encourage a focus on supporting users and their tasks while participatory design approaches encourage users' direct, active contributions to software development work. However, participatory design approaches often concentrate their efforts on design activities rather than on wider system development activities, while task analysis approaches generally lack active user participation beyond initial data gathering. This research attempts an integration of the strengths of task analysis and user participation within an overall software development process. This work also presents detailed empirical and theoretical analyses of what it is for users and developers to cooperate, of the nature of user-developer interaction in participatory settings. Furthermore, it makes operational and assesses the effectiveness of user participation in development and the impact of user-developer cooperation on the resulting software product. The research addressed these issues through the development and application of an approach to task based participatory development in two real world development projects. In this integrated approach, the respective strengths of task analysis and participatory design methods complemented each other's weaker aspects.

Sir Isaac Newton's philosophi Naturalis Principia Mathematica'(the Principia) contains a prose-style mixture of geometric and limit reasoning that has often been viewed as logically vague.In A Combination of Geometry Theorem Proving and Nonstandard Analysis, Jacques Fleuriot presents a formalization of Lemmas and Propositions from the Principia using a combination of methods from geometry and nonstandard analysis. The mechanization of the procedures, which respects much of Newton's original reasoning, is developed within the theorem prover Isabelle. The application of this framework to the mechanization of elementary real analysis using nonstandard techniques is also discussed.

Object-oriented inheritance has been in widespread use for a decade, and it is now realised that although inheritance is a powerful modelling tool with many associated advantages, its benefits are not automatically conferred on systems that simply use it. This book introduces a model of inheritance based around five fundamental inheritance relationships. Each relationship has a clear conceptual basis, representing a fundamental, specialised use of inheritance. The resulting model replaces a confused notion of inheritance with five distinct conceptual relationships supporting more precise modelling of systems and capturing the semantic intent of each use of inheritance within a system.

Accurate Visual Metrology from Single and Multiple Uncalibrated Images presents novel techniques for constructing three-dimensional models from bi-dimensional images using virtual reality tools. Antonio Criminisi develops the mathematical theory of computing world measurements from single images, and builds up a hierarchy of novel, flexible techniques to make measurements and reconstruct three-dimensional scenes from uncalibrated images, paying particular attention to the accuracy of the reconstruction.This book includes examples of interesting viable applications (eg. Forensic Science, History of Art, Virtual Reality, Architectural and indoor measurements), presented in a simple way, accompanied by pictures, diagrams and plenty of worked examples to help the reader understand and implement the algorithms.

In recent years, Artificial Intelligence researchers have largely focused their efforts on solving specific problems, with less emphasis on 'the big picture' - automating large scale tasks which require human-level intelligence to undertake. The subject of this book, automated theory formation in mathematics, is such a large scale task. Automated theory formation requires the invention of new concepts, the calculating of examples, the making of conjectures and the proving of theorems. This book, representing four years of PhD work by Dr. Simon Colton demonstrates how theory formation can be automated. Building on over 20 years of research into constructing an automated mathematician carried out in Professor Alan Bundy's mathematical reasoning group in Edinburgh, Dr. Colton has implemented the HR system as a solution to the problem of forming theories by computer. HR uses various pieces of mathematical software, including automated theorem provers, model generators and databases, to build a theory from the bare minimum of information - the axioms of a domain. The main application of this work has been mathematical discovery, and HR has had many successes. In particular, it has invented 20 new types of number of sufficient interest to be accepted into the Encyclopaedia of Integer Sequences, a repository of over 60,000 sequences contributed by many (human) mathematicians.

The Distinguished Dissertation Series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. In this way computer scientists with significantly different interests are able to grasp the essentials - or even find a means of entry - to an unfamiliar research topic. Constraint satisfaction is a fundamental technique for knowledge representation and inference in Artificial Intelligence. This success is founded on simplicity and generality: a constraint simply expresses a set of admissible value combinations among a number of variables. However, the classical formulation of a static constraint satisfaction problem (CSP) with inflexible constraints, all of which a solution must satisfy, is insufficient to model many real problems.Recent work has addressed these shortcomings via two separate extensions, known as dynamic CSP and flexible CSP. Representing three years of PhD work by Dr. Ian Miguel, this book demonstrates how a range of instances of these two powerful extensions can be combined in order to solve more complex problems. As an application of this work, Artificial Intelligence Planning is extended to support compromise. Preferences are attached to plan goals and to the set of actions available to achieve these goals, allowing a systematic comparison of candidate plans. Although a plan may not completely satisfy all goals, nor perform the actions it uses in the most preferred situations, it may be significantly shorter than a compromise-free plan. Dr. Miguel has implemented Flexible Graphplan, a planning system based on dynamic flexible CSP, which generates a range of plans from an input problem, trading plan length against the number and severity of compromises made.

The Distinguished Dissertations series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. In this way computer scientists with significantly different interests are able to grasp the essentials - or even find a means of entry - to an unfamiliar research topic. Machine learning promises both to create machine intelligence and to shed light on natural intelligence. A fundamental issue for either endevour is that of credit assignment, which we can pose as follows: how can we credit individual components of a complex adaptive system for their often subtle effects on the world? For example, in a game of chess, how did each move (and the reasoning behind it) contribute to the outcome?This text studies aspects of credit assignment in learning classifier systems, which combine evolutionary algorithms with reinforcement learning methods to address a range of tasks from pattern classification to stochastic control to simulation of learning in animals. Credit assignment in classifier systems is complicated by two features: 1) their components are frequently modified by evolutionary search, and 2) components tend to interact. Classifier systems are re-examined from first principles and the result is, primarily, a formalization of learning in these systems, and a body of theory relating types of classifier systems, learning tasks, and credit assignment pathologies. Most significantly, it is shown that both of the main approaches have difficulties with certain tasks, which the other type does not.

The Distinguished Dissertation Series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. In this way computer scientists with significantly different interests are able to grasp the essentials - or even find a means of entry - to an unfamiliar research topic. This book investigates how information contained in multiple, overlapping images of a scene may be combined to produce images of superior quality. This offers possibilities such as noise reduction, extended field of view, blur removal, increased spatial resolution and improved dynamic range. Potential applications cover fields as diverse as forensic video restoration, remote sensing, video compression and digital video editing.The book covers two aspects that have attracted particular attention in recent years: image mosaicing, whereby multiple images are aligned to produce a large composite; and super-resolution, which permits restoration at an increased resolution of poor quality video sequences by modelling and removing imaging degradations including noise, blur and spacial-sampling. It contains a comprehensive coverage and analysis of existing techniques, and describes in detail novel, powerful and automatic algorithms (based on a robust, statistical framework) for applying mosaicing and super-resolution. The algorithms may be implemented directly from the descriptions given here. A particular feature of the techniques is that it is not necessary to know the camera parameters (such as position and focal length) in order to apply them. Throughout the book, examples are given on real image sequences, covering a variety of applications including: the separation of latent marks in forensic images; the automatic creation of 360 panoramic mosaics; and super-resolution restoration of various scenes, text, and faces in lw-quality video.