Dr Simon J. D. Prince - Computer Vision. Models, Learning, and Inference

CAMBRIDGE UNIVERSITY PRESS

Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, So Paulo, Delhi, Mexico City

Cambridge University Press

32 Avenue of the Americas, New York, NY 10013-2473, USA

www.cambridge.org

Information on this title: www.cambridge.org/9781107011793

Simon J. D. Prince 2012

This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published 2012

Printed in the United States of America

A catalog record for this publication is available from the British Library.

Library of Congress Cataloging in Publication data

Prince, Simon J. D. (Simon Jeremy Damion), 1972

Computer vision : models, learning, and inference / Simon J. D. Prince.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-107-01179-3 (hardback)

1. Computer vision. I. Title.

TA1634.P75 2012

006.37dc23 2012008187

ISBN 978-1-107-01179-3 Hardback

Additional resources for this publication at www.computervisionmodels.com

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Computer Vision

Models, Learning, and Inference

This modern treatment of computer vision focuses on learning and inference in probabilistic models as a unifying theme. It shows how to use training data to learn the relationships between the observed image data and the aspects of the world that we wish to estimate, such as the 3D structure or the object class, and how to exploit these relationships to make inferences about the world from new image data.

With minimal prerequisites, the book starts from the basics of probability and model fitting and works up to real examples that the reader can implement and modify to build useful vision systems. Primarily meant for advanced undergraduate and graduate students, the detailed methodological presentation will also be useful for practitioners of computer vision.

Covers cutting-edge techniques, including graph cuts, machine learning, and multiple view geometry.

A unified approach shows the common basis for solutions of important computer vision problems, such as camera calibration, face recognition, and object tracking.

More than 70 algorithms are described in sufficient detail to implement.

More than 350 full-color illustrations amplify the text.

The treatment is self-contained, including all of the background mathematics.

Additional resources at www.computervisionmodels.com.

Dr. Simon J. D. Prince is a faculty member in the Department of Computer Science at University College London. He has taught courses on machine vision, image processing, and advanced mathematical methods. He has a diverse background in biological and computing sciences and has published papers across the fields of computer vision, biometrics, psychology, physiology, medical imaging, computer graphics, and HCI.

This book is dedicated to Richard Eagle, without whom it would never have been started, and to Lynfa Stroud, without whom it would never have been finished.

Contents

Acknowledgments

I am incredibly grateful to the following people who read parts of this book and gave me feedback: Yun Fu, David Fleet, Alan Jepson, MarcAurelio Ranzato, Gabriel Brostow, Oisin Mac Aodha, Xiwen Chen, Po-Hsiu Lin, Jose Tejero Alonso, Amir Sani, Oswald Aldrian, Sara Vicente, Jozef Dobo, Andrew Fitzgibbon, Michael Firman, Gemma Morgan, Daniyar Turmukhambetov, Daniel Alexander, Mihaela Lapusneanu, John Winn, Petri Hiltunen, Jania Aghajanian, Alireza Bossaghzadeh, Mikhail Sizintsev, Roger De Souza-Eremita, Jacques Cali, Roderick de Nijs, James Tompkin, Jonathan OKeefe, Benedict Kuester, Tom Hart, Marc Kerstein, Alex Bors, Marius Cobzarenco, Luke Dodd, Ankur Agarwal, Ahmad Humayun, Andrew Glennerster, Steven Leigh, Matteo Munaro, Peter van Beek, Hu Feng, Martin Parsley, Jordi Salvador Marcos, Josephine Sullivan, Steve Thompson, Laura Panagiotaki, Damien Teney, Malcolm Reynolds, Francisco Estrada, Peter Hall, James Elder, Paria Mehrani, Vida Movahedi, Eduardo Corral Soto, Ron Tal, Bob Hou, Simon Arridge, Norberto Goussies, Steve Walker, Tracy Petrie, Kostantinos Derpanis, Bernard Buxton, Matthew Pediaditis, Fernando Flores-Mangas, Jan Kautz, Alastair Moore, Yotam Doron, Tahir Majeed, David Barber, Pedro Quelhas, Wenchao Zhang, Alan Angold, Andrew Davison, Alex Yakubovich, Fatemeh Jamali, David Lowe, Ricardo David, Jamie Shotton, Andrew Zisserman, Sanchit Singh, Vincent Lepetit, David Liu, Marc Pollefeys, Christos Panagiotou, Ying Li, Shoaib Ehsan, Olga Veksler, Modesto Castrilln Santana, Axel Pinz, Matteo Zanotto, Gwynfor Jones, Brian Jensen, Mischa Schirris, Jacek Zienkiewicz, Etienne Beauchesne, Erik Sudderth, Giovanni Saponaro, Moos Hueting, Phi Hung Nguyen, Tran Duc Hieu, Simon Julier, Oscar Plag, Thomas Hoyoux, and Abhinav Singh. This book is much better because of your selfless efforts!

I am also especially grateful to Sven Dickinson, who hosted me at the University of Toronto for nine months during the writing of this book; Stephen Boyd, who let me use his beautiful LATEX template; and Mikhail Sizintsev, for his help in summarizing the bewildering literature on dense stereo vision. I am extremely indebted to Gabriel Brostow, who read the entire draft and spent hours of his valuable time discussing it with me. Finally, I am grateful to Bernard Buxton, who taught me most of this material in the first place and has supported my career in computer vision and every stage.

Foreword

I was very pleased to be asked to write this foreword, having seen snapshots of the development of this book since its inception. I write this having just returned from BMVC 2011, where I found that others had seen draft copies, and where I heard comments like What amazing figures!, Its so comprehensive!, and Hes so Bayesian!.

But I dont want you to read this book just because it has amazing figures and provides new insights into vision algorithms of every kind, or even because its Bayesian (although more on that later). I want you to read it because it makes clear the most important distinction in computer vision research: the difference between model and algorithm. This is akin to the distinction that Marr made with his three-level computational theory, but Princes two-level distinction is made beautifully clear by his use of the language of probability.

Why is this distinction so important? Well, let us look at one of the oldest and apparently easiest problems in vision: separating an image into figure and ground. It is still common to hear students new to vision address this problem just as the early vision researchers did, by reciting an algorithm: first Ill use PCA to find the dominant color axis, then Ill generate a grayscale image, then Ill threshold that at some value, then Ill clean up the holes using morphological operators. Trying their recipe on some test images, the novice discovers that real images are rather more complicated, so new steps are added: Ill need some sort of adaptive threshold, I can get that by blurring the edge map and locally computing maxima.

However, as most readers will already know, such recipes are extremely brittle, meaning that the various magic numbers controlling each step all interact, making it impossible to find a set of parameters that works for all images (or even a useful subset). The root of this problem is that the objective of the algorithm has never been defined. What do we