Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
2352
3
Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Tokyo
Anders Heyden Gunnar Sparr Mads Nielsen Peter Johansen (Eds.)
Computer Vision – ECCV 2002 7th European Conference on Computer Vision Copenhagen, Denmark, May 28-31, 2002 Proceedings, Part III
13
Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Anders Heyden Gunnar Sparr Lund University, Centre for Mathematical Sciences Box 118, 22100 Lund, Sweden E-mail: {Anders.Heyden,Gunnar.Sparr}@math.lth.se Mads Nielsen The IT University of Copenhagen Glentevej 67-69, 2400 Copenhagen NW, Denmark E-mail:
[email protected] Peter Johansen University of Copenhagen Universitetsparken 1, 2100 Copenhagen, Denmark E-mail:
[email protected]
Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Computer vision : proceedings / ECCV 2002, 7th European Conference on Computer Vision, Copenhagen, Denmark, May 28 - 31, 2002. Anders Heyden ... (ed.). - Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer Pt. 3 . - 2002 (Lecture notes in computer science ; Vol. 2352) ISBN 3-540-43746-0 CR Subject Classification (1998): I.4, I.3.5, I.5, I.2.9-10 ISSN 0302-9743 ISBN 3-540-43746-0 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2002 Printed in Germany Typesetting: Camera-ready by author, data conversion by PTP-Berlin, Stefan Sossna e.K. Printed on acid-free paper SPIN: 10870041 06/3142 543210
Preface
Premiering in 1990 in Antibes, France, the European Conference on Computer Vision, ECCV, has been held biennially at venues all around Europe. These conferences have been very successful, making ECCV a major event to the computer vision community. ECCV 2002 was the seventh in the series. The privilege of organizing it was shared by three universities: The IT University of Copenhagen, the University of Copenhagen, and Lund University, with the conference venue in Copenhagen. These universities lie ¨ geographically close in the vivid Oresund region, which lies partly in Denmark and partly in Sweden, with the newly built bridge (opened summer 2000) crossing the sound that formerly divided the countries. We are very happy to report that this year’s conference attracted more papers than ever before, with around 600 submissions. Still, together with the conference board, we decided to keep the tradition of holding ECCV as a single track conference. Each paper was anonymously refereed by three different reviewers. For the final selection, for the first time for ECCV, a system with area chairs was used. These met with the program chairs in Lund for two days in February 2002 to select what became 45 oral presentations and 181 posters. Also at this meeting the selection was made without knowledge of the authors’ identity. The high-quality of the scientific program of ECCV 2002 would not have been possible without the dedicated cooperation of the 15 area chairs, the 53 program committee members, and all the other scientists, who reviewed the papers. A truly impressive effort was made. The spirit of this process reflects the enthusiasm in the research field, and you will find several papers in these proceedings that define the state of the art in the field. Bjarne Ersbøll as Industrial Relations Chair organized the exhibitions at the conference. Magnus Oskarsson, Sven Spanne, and Nicolas Guilbert helped to make the review process and the preparation of the proceedings function smoothly. Ole Fogh Olsen gave us valuable advice on editing the proceedings. Camilla Jørgensen competently headed the scientific secretariat. Erik Dam and Dan Witzner were responsible for the ECCV 2002 homepage. David Vernon, who chaired ECCV 2000 in Dublin, was extremely helpful during all stages of our preparation for the conference. We would like to thank all these people, as well as numerous others who helped in various respects. A special thanks goes to Søren Skovsgaard at the Congress Consultants, for professional help with all practical matters. We would also like to thank Rachid Deriche and Theo Papadopoulo for making their web-based conference administration system available and adjusting it to ECCV. This was indispensable in handling the large number of submissions and the thorough review and selection procedure. Finally, we wish to thank the IT University of Copenhagen and its president Mads Tofte for supporting the conference all the way from planning to realization. March 2002
Anders Heyden Gunnar Sparr Mads Nielsen Peter Johansen
Organization
Conference Chair Peter Johansen
Copenhagen University, Denmark
Conference Board Hans Burkhardt Bernard Buxton Roberto Cipolla Jan-Olof Eklundh Olivier Faugeras Bernd Neumann Giulio Sandini David Vernon
University of Freiburg, Germany University College London, UK University of Cambridge, UK Royal Institute of Technology, Sweden INRIA, Sophia Antipolis, France University of Hamburg, Germany University of Genova, Italy Trinity College, Dublin, Ireland
Program Chairs Anders Heyden Gunnar Sparr
Lund University, Sweden Lund University, Sweden
Area Chairs Ronen Basri Michael Black Andrew Blake Rachid Deriche Jan-Olof Eklundh Lars Kai Hansen Steve Maybank Theodore Papadopoulo Cordelia Schmid Amnon Shashua Stefano Soatto Bill Triggs Luc van Gool Joachim Weichert Andrew Zisserman
Weizmann Institute, Israel Brown University, USA Microsoft Research, UK INRIA, Sophia Antipolis, France Royal Institute of Technology, Sweden Denmark Technical University, Denmark University of Reading, UK INRIA, Sophia Antipolis, France INRIA, Rhône-Alpes, France The Hebrew University of Jerusalem, Israel University of California, Los Angeles, USA INRIA, Rhône-Alpes, France K.U. Leuven, Belgium & ETH, Zürich, Switzerland Saarland University, Germany University of Oxford, UK
Organization
VII
Program Committee Luis Alvarez Padmanabhan Anandan Helder Araujo Serge Belongie Marie-Odile Berger Aaron Bobick Terry Boult Francois Chaumette Laurent Cohen Tim Cootes Kostas Daniilidis Larry Davis Frank Ferrie Andrew Fitzgibbon David J. Fleet David Forsyth Pascal Fua Richard Hartley Vaclav Hlavac Michal Irani Allan Jepson Peter Johansen Fredrik Kahl Sing Bing Kang Ron Kimmel Kyros Kutulakos Tony Lindeberg Jim Little Peter Meer David Murray Nassir Navab Mads Nielsen Patrick Perez Pietro Perona Marc Pollefeys Long Quan Ian Reid Nicolas Rougon José Santos-Victor Guillermo Sapiro Yoichi Sato Bernt Schiele Arnold Smeulders
University of Las Palmas, Spain Microsoft Research, USA University of Coimbra, Portugal University of California, San Diego, USA INRIA, Lorraine, France Georgia Tech, USA Leheigh University, USA INRIA, Rennes, France Université Paris IX Dauphine, France University of Manchester, UK University of Pennsylvania, USA University of Maryland, USA McGill University, USA University of Oxford, UK Xerox Palo Alto Research Center, USA University of California, Berkeley, USA EPFL, Switzerland Australian National University, Australia Czech Technical University, Czech Republic Weizmann Institute, Israel University of Toronto, Canada Copenhagen University, Denmark Lund University, Sweden Microsoft Research, USA Technion, Israel University of Rochester, USA Royal Institute of Technology, Sweden University of Brittish Columbia, Canada Rutgers University, USA University of Oxford, UK Siemens, USA IT-University of Copenhagen, Denmark Microsoft Research, UK California Insititute of Technology, USA K.U. Leuven, Belgium Hong Kong University of Science and Technology, Hong Kong University of Oxford, UK Institut National des Télécommunications, France Instituto Superior Técnico, Lisbon, Portugal University of Minnesota, USA IIS, University of Tokyo, Japan ETH, Zürich, Switzerland University of Amsterdam, The Netherlands
VIII
Organization
Gerald Sommer Peter Sturm Tomas Svoboda Chris Taylor Phil Torr Panos Trahanias Laurent Younes Alan Yuille Josiane Zerubia Kalle Åström
University of Kiel, Germany INRIA, Rhône-Alpes, France Swiss Federal Institute of Technology, Switzerland University of Manchester, UK Microsoft Research, UK University of Crete, Greece CMLA, ENS de Cachan, France Smith-Kettlewell Eye Research Institute, USA INRIA, Sophia Antipolis, France Lund University, Sweden
Additional Referees Henrik Aanaes Manoj Aggarwal Motilal Agrawal Aya Aner Adnan Ansar Mirko Appel Tal Arbel Okan Arikan Akira Asano Shai Avidan Simon Baker David Bargeron Christian Barillot Kobus Barnard Adrien Bartoli Benedicte Bascle Pierre-Louis Bazin Isabelle Begin Stephen Benoit Alex Berg James Bergen Jim Bergen Marcelo Bertamlmio Rikard Berthilsson Christophe Biernacki Armin Biess Alessandro Bissacco Laure Blanc-Feraud Ilya Blayvas Eran Borenstein Patrick Bouthemy Richard Bowden
Jeffrey E. Boyd Edmond Boyer Yuri Boykov Chen Brestel Lars Bretzner Alexander Brook Michael Brown Alfred Bruckstein Thomas Buelow Joachim Buhmann Hans Burkhardt Bernard Buxton Nikos Canterakis Yaron Caspi Alessandro Chiuso Roberto Cipolla Dorin Comaniciu Kurt Cornelis Antonio Criminisi Thomas E. Davis Nando de Freitas Fernando de la Torre Daniel DeMenthon Xavier Descombes Hagio Djambazian Gianfranco Doretto Alessandro Duci Gregory Dudek Ramani Duraiswami Pinar Duygulu Michael Eckmann Alyosha Efros
Michael Elad Ahmed Elgammal Ronan Fablet Ayman Farahat Olivier Faugeras Paulo Favaro Xiaolin Feng Vittorio Ferrari Frank Ferrie Mario Figueireda Margaret Fleck Michel Gangnet Xiang Gao D. Geiger Yakup Genc Bogdan Georgescu J.-M. Geusebroek Christopher Geyer Peter Giblin Gerard Giraudon Roman Goldenberg Shaogang Gong Hayit Greenspan Lewis Griffin Jens Guehring Yanlin Guo Daniela Hall Tal Hassner Horst Haussecker Ralf Hebrich Yacov Hel-Or Lorna Herda
Organization
Shinsaku Hiura Jesse Hoey Stephen Hsu Du Huynh Naoyuki Ichimura Slobodan Ilic Sergey Ioffe Michael Isard Volkan Isler David Jacobs Bernd Jaehne Ian Jermyn Hailin Jin Marie-Pierre Jolly Stiliyan-N. Kalitzin Behrooz Kamgar-Parsi Kenichi Kanatani Danny Keren Erwan Kerrien Charles Kervrann Renato Keshet Ali Khamene Shamim Khan Nahum Kiryati Reinhard Koch Ullrich Koethe Esther B. Koller-Meier John Krumm Hannes Kruppa Murat Kunt Prasun Lala Michael Langer Ivan Laptev Jean-Pierre Le Cadre Bastian Leibe Ricahrd Lengagne Vincent Lepetit Thomas Leung Maxime Lhuillier Weiliang Li David Liebowitz Georg Lindgren David Lowe John MacCormick Henrik Malm
Roberto Manduchi Petros Maragos Eric Marchand Jiri Matas Bogdan Matei Esther B. Meier Jason Meltzer Etienne Mémin Rudolf Mester Ross J. Micheals Anurag Mittal Hiroshi Mo William Moran Greg Mori Yael Moses Jane Mulligan Don Murray Masahide Naemura Kenji Nagao Mirko Navara Shree Nayar Oscar Nestares Bernd Neumann Jeffrey Ng Tat Hieu Nguyen Peter Nillius David Nister Alison Noble Tom O’Donnell Takayuki Okatani Nuria Olivier Ole Fogh Olsen Magnus Oskarsson Nikos Paragios Ioannis Patras Josef Pauli Shmuel Peleg Robert Pless Swaminathan Rahul Deva Ramanan Lionel Reveret Dario Ringach Ruth Rosenholtz Volker Roth Payam Saisan
Garbis Salgian Frank Sauer Peter Savadjiev Silvio Savarese Harpreet Sawhney Frederik Schaffalitzky Yoav Schechner Chrostoph Schnoerr Stephan Scholze Ali Shahrokri Doron Shaked Eitan Sharon Eli Shechtman Jamie Sherrah Akinobu Shimizu Ilan Shimshoni Kaleem Siddiqi Hedvig Sidenbladh Robert Sim Denis Simakov Philippe Simard Eero Simoncelli Nir Sochen Yang Song Andreas Soupliotis Sven Spanne Martin Spengler Alon Spira Thomas Strömberg Richard Szeliski Hai Tao Huseyin Tek Seth Teller Paul Thompson Jan Tops Benjamin J. Tordoff Kentaro Toyama Tinne Tuytelaars Shimon Ullman Richard Unger Raquel Urtasun Sven Utcke Luca Vacchetti Anton van den Hengel Geert Van Meerbergen
IX
X
Organization
Pierre Vandergheynst Zhizhou Wang Baba Vemuri Frank Verbiest Maarten Vergauwen Jaco Vermaak Mike Werman David Vernon Thomas Vetter
Rene Vidal Michel Vidal-Naquet Marta Wilczkowiak Ramesh Visvanathan Dan Witzner Hansen Julia Vogel Lior Wolf Bob Woodham Robert J. Woodham
Chenyang Xu Yaser Yacoob Anthony Yezzi Ramin Zabih Hugo Zaragoza Lihi Zelnik-Manor Ying Zhu Assaf Zomet
Table of Contents, Part III
Shape 3D Statistical Shape Models Using Direct Optimisation of Description Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R.H. Davies, C.J. Twining, T.F. Cootes, J.C. Waterton, C.J. Taylor
3
Approximate Thin Plate Spline Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 G. Donato, S. Belongie DEFORMOTION: Deforming Motion, Shape Average and the Joint Registration and Segmentation of Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 S. Soatto, A.J. Yezzi Region Matching with Missing Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 A. Duci, A.J. Yezzi, S. Mitter, S. Soatto
Stereoscopic Vision I What Energy Functions Can Be Minimized via Graph Cuts? . . . . . . . . . . . . . . . . . 65 V. Kolmogorov, R. Zabih Multi-camera Scene Reconstruction via Graph Cuts . . . . . . . . . . . . . . . . . . . . . . . . 82 V. Kolmogorov, R. Zabih A Markov Chain Monte Carlo Approach to Stereovision . . . . . . . . . . . . . . . . . . . . . 97 J. S´en´egas A Probabilistic Theory of Occupancy and Emptiness . . . . . . . . . . . . . . . . . . . . . . . 112 R. Bhotika, D.J. Fleet, K.N. Kutulakos
Texture Shading and Colour / Grouping and Segmentation / Object Recognition Texture Similarity Measure Using Kullback-Leibler Divergence between Gamma Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 J.R. Mathiassen, A. Skavhaug, K. Bø All the Images of an Outdoor Scene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 S.G. Narasimhan, C. Wang, S.K. Nayar Recovery of Reflectances and Varying Illuminants from Multiple Views . . . . . . . . 163 Q.-T. Luong, P. Fua, Y. Leclerc
XII
Table of Contents, Part III
Composite Texture Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 A. Zalesny, V. Ferrari, G. Caenen, D. Auf der Maur, L. Van Gool Constructing Illumination Image Basis from Object Motion . . . . . . . . . . . . . . . . . . 195 A. Nakashima, A. Maki, K. Fukui Diffuse-Specular Separation and Depth Recovery from Image Sequences . . . . . . . 210 S. Lin, Y. Li, S.B. Kang, X. Tong, H.-Y. Shum Shape from Texture without Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 D.A. Forsyth Statistical Modeling of Texture Sketch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 Y.N. Wu, S.C. Zhu, C.-e. Guo Classifying Images of Materials: Achieving Viewpoint and Illumination Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 M. Varma, A. Zisserman Estimation of Multiple Illuminants from a Single Image of Arbitrary Known Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 Y. Wang, D. Samaras The Effect of Illuminant Rotation on Texture Filters: Lissajous’s Ellipses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 M. Chantler, M. Schmidt, M. Petrou, G. McGunnigle On Affine Invariant Clustering and Automatic Cast Listing in Movies . . . . . . . . . . 304 A. Fitzgibbon, A. Zisserman Factorial Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 J. Kim, R. Zabih Evaluation and Selection of Models for Motion Segmentation . . . . . . . . . . . . . . . . 335 K. Kanatani Surface Extraction from Volumetric Images Using Deformable Meshes: A Comparative Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 J. Tohka DREAM2 S: Deformable Regions Driven by an Eulerian Accurate Minimization Method for Image and Video Segmentation (Application to Face Detection in Color Video Sequences) . . . . . . . . . . . . . . . . . . 365 S. Jehan-Besson, M. Barlaud, G. Aubert Neuro-Fuzzy Shadow Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 B.P.L. Lo, G.-Z. Yang Parsing Images into Region and Curve Processes . . . . . . . . . . . . . . . . . . . . . . . . . . 393 Z. Tu, S.-C. Zhu
Table of Contents, Part III
XIII
Yet Another Survey on Image Segmentation: Region and Boundary Information Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 J. Freixenet, X. Mu˜noz, D. Raba, J. Mart´ı, X. Cuf´ı Perceptual Grouping from Motion Cues Using Tensor Voting in 4-D . . . . . . . . . . . 423 M. Nicolescu, G. Medioni Deformable Model with Non-euclidean Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 438 B. Taton, J.-O. Lachaud Finding Deformable Shapes Using Loopy Belief Propagation . . . . . . . . . . . . . . . . . 453 J.M. Coughlan, S.J. Ferreira Probabilistic and Voting Approaches to Cue Integration for Figure-Ground Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469 E. Hayman, J.-O. Eklundh Bayesian Estimation of Layers from Multiple Images . . . . . . . . . . . . . . . . . . . . . . . 487 Y. Wexler, A. Fitzgibbon, A. Zisserman A Stochastic Algorithm for 3D Scene Segmentation and Reconstruction . . . . . . . . 502 F. Han, Z. Tu, S.-C. Zhu Normalized Gradient Vector Diffusion and Image Segmentation . . . . . . . . . . . . . . 517 Z. Yu, C. Bajaj Spectral Partitioning with Indefinite Kernels Using the Nystr¨om Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531 S. Belongie, C. Fowlkes, F. Chung, J. Malik A Framework for High-Level Feedback to Adaptive, Per-Pixel, Mixture-of-Gaussian Background Models . . . . . . . . . . . . . . . . . . . . . . . . 543 M. Harville Multivariate Saddle Point Detection for Statistical Clustering . . . . . . . . . . . . . . . . . 561 D. Comaniciu, V. Ramesh, A. Del Bue Parametric Distributional Clustering for Image Segmentation . . . . . . . . . . . . . . . . . 577 L. Hermes, T. Z¨oller, J.M. Buhmann Probabalistic Models and Informative Subspaces for Audiovisual Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592 J.W. Fisher, T. Darrell Volterra Filtering of Noisy Images of Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 J. August Image Segmentation by Flexible Models Based on Robust Regularized Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621 M. Rivera, J. Gee
XIV
Table of Contents, Part III
Principal Component Analysis over Continuous Subspaces and Intersection of Half-Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635 A. Levin, A. Shashua On Pencils of Tangent Planes and the Recognition of Smooth 3D Shapes from Silhouettes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651 S. Lazebnik, A. Sethi, C. Schmid, D. Kriegman, J. Ponce, M. Hebert Estimating Human Body Configurations Using Shape Context Matching . . . . . . . 666 G. Mori, J. Malik Probabilistic Human Recognition from Video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681 S. Zhou, R. Chellappa SoftPOSIT: Simultaneous Pose and Correspondence Determination . . . . . . . . . . . . 698 P. David, D. DeMenthon, R. Duraiswami, H. Samet A Pseudo-Metric for Weighted Point Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 P. Giannopoulos, R.C. Veltkamp Shock-Based Indexing into Large Shape Databases . . . . . . . . . . . . . . . . . . . . . . . . . 731 T.B. Sebastian, P.N. Klein, B.B. Kimia EigenSegments: A Spatio-Temporal Decomposition of an Ensemble of Images . . 747 S. Avidan On the Representation and Matching of Qualitative Shape at Multiple Scales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759 A. Shokoufandeh, S. Dickinson, C. J¨onsson, L. Bretzner, T. Lindeberg Combining Simple Discriminators for Object Discrimination . . . . . . . . . . . . . . . . . 776 S. Mahamud, M. Hebert, J. Lafferty Probabilistic Search for Object Segmentation and Recognition . . . . . . . . . . . . . . . . 791 U. Hillenbrand, G. Hirzinger Real-Time Interactive Path Extraction with On-the-Fly Adaptation of the External Forces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807 O. G´erard, T. Deschamps, M. Greff, L.D. Cohen Matching and Embedding through Edit-Union of Trees . . . . . . . . . . . . . . . . . . . . . 822 A. Torsello, E.R. Hancock A Comparison of Search Strategies for Geometric Branch and Bound Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837 T. M. Breuel Face Recognition from Long-Term Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . 851 G. Shakhnarovich, J.W. Fisher, T. Darrell
Table of Contents, Part III
XV
Stereoscopic Vision II Helmholtz Stereopsis: Exploiting Reciprocity for Surface Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 869 T. Zickler, P.N. Belhumeur, D.J. Kriegman Minimal Surfaces for Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885 C. Buehler, S.J. Gortler, M.F. Cohen, L. McMillan Finding the Largest Unambiguous Component of Stereo Matching . . . . . . . . . . . . 900 ˇara R. S´
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915
Table of Contents, Part I
Active and Real-Time Vision Tracking with the EM Contour Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.E.C. Pece, A.D. Worrall
3
M2Tracker: A Multi-view Approach to Segmenting and Tracking People in a Cluttered Scene Using Region-Based Stereo . . . . . . . . . . . . . . . . . . . . . 18 A. Mittal, L.S. Davis
Image Features Analytical Image Models and Their Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 37 A. Srivastava, X. Liu, U. Grenander Time-Recursive Velocity-Adapted Spatio-Temporal Scale-Space Filters . . . . . . . . 52 T. Lindeberg Combining Appearance and Topology for Wide Baseline Matching . . . . . . . . . . . . 68 D. Tell, S. Carlsson Guided Sampling and Consensus for Motion Estimation . . . . . . . . . . . . . . . . . . . . . 82 B. Tordoff, D.W. Murray
Image Features / Visual Motion Fast Anisotropic Gauss Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 J.-M. Geusebroek, A.W.M. Smeulders, J. van de Weijer Adaptive Rest Condition Potentials: Second Order Edge-Preserving Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 M. Rivera, J.L. Marroquin An Affine Invariant Interest Point Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 K. Mikolajczyk, C. Schmid Understanding and Modeling the Evolution of Critical Points under Gaussian Blurring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 A. Kuijper, L. Florack Image Processing Done Right . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 J.J. Koenderink, A.J. van Doorn Multimodal Data Representations with Parameterized Local Structures . . . . . . . . . 173 Y. Zhu, D. Comaniciu, S. Schwartz, V. Ramesh
Table of Contents, Part I
XVII
The Relevance of Non-generic Events in Scale Space Models . . . . . . . . . . . . . . . . 190 A. Kuijper, L. Florack The Localized Consistency Principle for Image Matching under Non-uniform Illumination Variation and Affine Distortion . . . . . . . . . . . . . . . . . . . 205 B. Wang, K.K. Sung, T.K. Ng Resolution Selection Using Generalized Entropies of Multiresolution Histograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 E. Hadjidemetriou, M.D. Grossberg, S.K. Nayar Robust Computer Vision through Kernel Density Estimation . . . . . . . . . . . . . . . . . 236 H. Chen, P. Meer Constrained Flows of Matrix-Valued Functions: Application to Diffusion Tensor Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 C. Chefd’hotel, D. Tschumperl´e, R. Deriche, O. Faugeras A Hierarchical Framework for Spectral Correspondence . . . . . . . . . . . . . . . . . . . . . 266 M. Carcassoni, E.R. Hancock Phase-Based Local Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 G. Carneiro, A.D. Jepson What Is the Role of Independence for Visual Recognition? . . . . . . . . . . . . . . . . . . . 297 N. Vasconcelos, G. Carneiro A Probabilistic Multi-scale Model for Contour Completion Based on Image Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 X. Ren, J. Malik Toward a Full Probability Model of Edges in Natural Images . . . . . . . . . . . . . . . . . 328 K.S. Pedersen, A.B. Lee Fast Difference Schemes for Edge Enhancing Beltrami Flow . . . . . . . . . . . . . . . . . 343 R. Malladi, I. Ravve A Fast Radial Symmetry Transform for Detecting Points of Interest . . . . . . . . . . . . 358 G. Loy, A. Zelinsky Image Features Based on a New Approach to 2D Rotation Invariant Quadrature Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 M. Felsberg, G. Sommer Representing Edge Models via Local Principal Component Analysis . . . . . . . . . . . 384 P.S. Huggins, S.W. Zucker Regularized Shock Filters and Complex Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . 399 G. Gilboa, N.A. Sochen, Y.Y. Zeevi
XVIII
Table of Contents, Part I
Multi-view Matching for Unordered Image Sets, or “How Do I Organize My Holiday Snaps?” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 F. Schaffalitzky, A. Zisserman Parameter Estimates for a Pencil of Lines: Bounds and Estimators . . . . . . . . . . . . . 432 G. Speyer, M. Werman Multilinear Analysis of Image Ensembles: TensorFaces . . . . . . . . . . . . . . . . . . . . . 447 M.A.O. Vasilescu, D. Terzopoulos ‘Dynamism of a Dog on a Leash’ or Behavior Classification by Eigen-Decomposition of Periodic Motions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 R. Goldenberg, R. Kimmel, E. Rivlin, M. Rudzsky Automatic Detection and Tracking of Human Motion with a View-Based Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476 R. Fablet, M.J. Black Using Robust Estimation Algorithms for Tracking Explicit Curves . . . . . . . . . . . . . 492 J.-P. Tarel, S.-S. Ieng, P. Charbonnier On the Motion and Appearance of Specularities in Image Sequences . . . . . . . . . . . 508 R. Swaminathan, S.B. Kang, R. Szeliski, A. Criminisi, S.K. Nayar Multiple Hypothesis Tracking for Automatic Optical Motion Capture . . . . . . . . . . 524 M. Ringer, J. Lasenby Single Axis Geometry by Fitting Conics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 G. Jiang, H.-t. Tsui, L. Quan, A. Zisserman Computing the Physical Parameters of Rigid-Body Motion from Video . . . . . . . . . 551 K.S. Bhat, S.M. Seitz, J. Popovi´c, P.K. Khosla Building Roadmaps of Local Minima of Visual Models . . . . . . . . . . . . . . . . . . . . . 566 C. Sminchisescu, B. Triggs A Generative Method for Textured Motion: Analysis and Synthesis . . . . . . . . . . . . 583 Y. Wang, S.-C. Zhu Is Super-Resolution with Optical Flow Feasible? . . . . . . . . . . . . . . . . . . . . . . . . . . . 599 W.Y. Zhao, H.S. Sawhney New View Generation with a Bi-centric Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . 614 D. Weinshall, M.-S. Lee, T. Brodsky, M. Trajkovic, D. Feldman Recognizing and Tracking Human Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 J. Sullivan, S. Carlsson
Table of Contents, Part I
XIX
Towards Improved Observation Models for Visual Tracking: Selective Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 J. Vermaak, P. P´erez, M. Gangnet, A. Blake Color-Based Probabilistic Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661 P. P´erez, C. Hue, J. Vermaak, M. Gangnet Dense Motion Analysis in Fluid Imagery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676 ´ M´emin, P. P´erez T. Corpetti, E. A Layered Motion Representation with Occlusion and Compact Spatial Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692 A.D. Jepson, D.J. Fleet, M.J. Black Incremental Singular Value Decomposition of Uncertain Data with Missing Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707 M. Brand Symmetrical Dense Optical Flow Estimation with Occlusions Detection . . . . . . . . 721 L. Alvarez, R. Deriche, T. Papadopoulo, J. S´anchez Audio-Video Sensor Fusion with Probabilistic Graphical Models . . . . . . . . . . . . . . 736 M.J. Beal, H. Attias, N. Jojic
Visual Motion Increasing Space-Time Resolution in Video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753 E. Shechtman, Y. Caspi, M. Irani Hyperdynamics Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769 C. Sminchisescu, B. Triggs Implicit Probabilistic Models of Human Motion for Synthesis and Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784 H. Sidenbladh, M.J. Black, L. Sigal Space-Time Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801 L. Torresani, C. Bregler
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813
Table of Contents, Part II
Surface Geometry A Variational Approach to Recovering a Manifold from Sample Points . . . . . . . . . J. Gomes, A. Mojsilovic
3
A Variational Approach to Shape from Defocus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 H. Jin, P. Favaro Shadow Graphs and Surface Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Y. Yu, J.T. Chang Specularities Reduce Ambiguity of Uncalibrated Photometric Stereo . . . . . . . . . . . 46 ˇara O. Drbohlav, R. S´
Grouping and Segmentation Pairwise Clustering with Matrix Factorisation and the EM Algorithm . . . . . . . . . . 63 A. Robles-Kelly, E.R. Hancock Shape Priors for Level Set Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 M. Rousson, N. Paragios Nonlinear Shape Statistics in Mumford–Shah Based Segmentation . . . . . . . . . . . . 93 D. Cremers, T. Kohlberger, C. Schn¨orr Class-Specific, Top-Down Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 E. Borenstein, S. Ullman
Structure from Motion / Stereoscopic Vision / Surface Geometry / Shape Quasi-Dense Reconstruction from Image Sequence . . . . . . . . . . . . . . . . . . . . . . . . . 125 M. Lhuillier, L. Quan Properties of the Catadioptric Fundamental Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 140 C. Geyer, K. Daniilidis Building Architectural Models from Many Views Using Map Constraints . . . . . . . 155 D.P. Robertson, R. Cipolla Motion – Stereo Integration for Depth Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 170 C. Strecha, L. Van Gool
Table of Contents, Part II
XXI
Lens Distortion Recovery for Accurate Sequential Structure and Motion Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 K. Cornelis, M. Pollefeys, L. Van Gool Generalized Rank Conditions in Multiple View Geometry with Applications to Dynamical Scenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 K. Huang, R. Fossum, Y. Ma Dense Structure-from-Motion: An Approach Based on Segment Matching . . . . . . 217 F. Ernst, P. Wilinski, K. van Overveld Maximizing Rigidity: Optimal Matching under Scaled-Orthography . . . . . . . . . . . 232 J. Maciel, J. Costeira Dramatic Improvements to Feature Based Stereo . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 V.N. Smelyansky, R.D. Morris, F.O. Kuehnel, D.A. Maluf, P. Cheeseman Motion Curves for Parametric Shape and Motion Estimation . . . . . . . . . . . . . . . . . 262 P.-L. Bazin, J.-M. V´ezien Bayesian Self-Calibration of a Moving Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 G. Qian, R. Chellappa Balanced Recovery of 3D Structure and Camera Motion from Uncalibrated Image Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 B. Georgescu, P. Meer Linear Multi View Reconstruction with Missing Data . . . . . . . . . . . . . . . . . . . . . . . 309 C. Rother, S. Carlsson Model-Based Silhouette Extraction for Accurate People Tracking . . . . . . . . . . . . . 325 R. Plaenkers, P. Fua On the Non-linear Optimization of Projective Motion Using Minimal Parameters . 340 A. Bartoli Structure from Many Perspective Images with Occlusions . . . . . . . . . . . . . . . . . . . 355 D. Martinec, T. Pajdla Sequence-to-Sequence Self Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 L. Wolf, A. Zomet Structure from Planar Motions with Small Baselines . . . . . . . . . . . . . . . . . . . . . . . . 383 R. Vidal, J. Oliensis Revisiting Single-View Shape Tensors: Theory and Applications . . . . . . . . . . . . . . 399 A. Levin, A. Shashua
XXII
Table of Contents, Part II
Tracking and Rendering Using Dynamic Textures on Geometric Structure from Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 D. Cobzas, M. Jagersand Sensitivity of Calibration to Principal Point Position . . . . . . . . . . . . . . . . . . . . . . . . 433 R.I. Hartley, R. Kaucic Critical Curves and Surfaces for Euclidean Reconstruction . . . . . . . . . . . . . . . . . . . 447 F. Kahl, R. Hartley View Synthesis with Occlusion Reasoning Using Quasi-Sparse Feature Correspondences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 D. Jelinek, C.J. Taylor Eye Gaze Correction with Stereovision for Video-Teleconferencing . . . . . . . . . . . . 479 R. Yang, Z. Zhang Wavelet-Based Correlation for Stereopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 M. Clerc Stereo Matching Using Belief Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510 J. Sun, H.-Y. Shum, N.-N. Zheng Symmetric Sub-pixel Stereo Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 R. Szeliski, D. Scharstein New Techniques for Automated Architectural Reconstruction from Photographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 T. Werner, A. Zisserman Stereo Matching with Segmentation-Based Cooperation . . . . . . . . . . . . . . . . . . . . . 556 Y. Zhang, C. Kambhamettu Coarse Registration of Surface Patches with Local Symmetries . . . . . . . . . . . . . . . 572 J. Vanden Wyngaerd, L. Van Gool Multiview Registration of 3D Scenes by Minimizing Error between Coordinate Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 G.C. Sharp, S.W. Lee, D.K. Wehe Recovering Surfaces from the Restoring Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598 G. Kamberov, G. Kamberova Interpolating Sporadic Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613 L. Noakes, R. Kozera Highlight Removal Using Shape-from-Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626 H. Ragheb, E.R. Hancock
Table of Contents, Part II
XXIII
A Reflective Symmetry Descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642 M. Kazhdan, B. Chazelle, D. Dobkin, A. Finkelstein, T. Funkhouser Gait Sequence Analysis Using Frieze Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657 Y. Liu, R. Collins, Y. Tsin Feature-Preserving Medial Axis Noise Removal . . . . . . . . . . . . . . . . . . . . . . . . . . . 672 R. Tam, W. Heidrich Hierarchical Shape Modeling for Automatic Face Localization . . . . . . . . . . . . . . . . 687 C. Liu, H.-Y. Shum, C. Zhang Using Dirichlet Free Form Deformation to Fit Deformable Models to Noisy 3-D Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704 S. Ilic, P. Fua Transitions of the 3D Medial Axis under a One-Parameter Family of Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718 P. Giblin, B.B. Kimia Learning Shape from Defocus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735 P. Favaro, S. Soatto A Rectilinearity Measurement for Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746 ˇ c, P.L. Rosin J. Zuni´ Local Analysis for 3D Reconstruction of Specular Surfaces – Part II . . . . . . . . . . . 759 S. Savarese, P. Perona Matching Distance Functions: A Shape-to-Area Variational Approach for Global-to-Local Registration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775 N. Paragios, M. Rousson, V. Ramesh Shape from Shading and Viscosity Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 790 E. Prados, O. Faugeras, E. Rouy Model Acquisition by Registration of Multiple Acoustic Range Views . . . . . . . . . . 805 A. Fusiello, U. Castellani, L. Ronchetti, V. Murino
Structure from Motion General Trajectory Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823 J.Y. Kaminski, M. Teicher Surviving Dominant Planes in Uncalibrated Structure and Motion Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837 M. Pollefeys, F. Verbiest, L. Van Gool A Bayesian Estimation of Building Shape Using MCMC . . . . . . . . . . . . . . . . . . . . 852 A.R. Dick, P.H.S. Torr, R. Cipolla
XXIV
Table of Contents, Part II
Structure and Motion for Dynamic Scenes – The Case of Points Moving in Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867 P. Sturm What Does the Scene Look Like from a Scene Point? . . . . . . . . . . . . . . . . . . . . . . . 883 M. Irani, T. Hassner, P. Anandan
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899
3D Statistical Shape Models Using Direct Optimisation of Description Length Rhodri H. Davies1 , Carole J. Twining1 , Tim F. Cootes1 , John C. Waterton2 , and Chris J. Taylor1 1
Division of Imaging Science, Stopford Building, Oxford Road, University of Manchester, Manchester, M13 9PT, UK
[email protected] 2 AstraZeneca, Alderley Park, Macclesfield, Cheshire, SK10 4TG, UK
Abstract. We describe an automatic method for building optimal 3D statistical shape models from sets of training shapes. Although shape models show considerable promise as a basis for segmenting and interpreting images, a major drawback of the approach is the need to establish a dense correspondence across a training set of example shapes. It is important to establish the correct correspondence, otherwise poor models can result. In 2D, this can be achieved using manual ‘landmarks’, but in 3D this becomes impractical. We show it is possible to establish correspondences automatically, by casting the correspondence problem as one of finding the ‘optimal’ parameterisation of each shape in the training set. We describe an explicit representation of surface parameterisation, that ensures the resulting correspondences are legal, and show how this representation can be manipulated to minimise the description length of the training set using the model. This results in compact models with good generalisation properties. Results are reported for two sets of biomedical shapes, showing significant improvement in model properties compared to those obtained using a uniform surface parameterisation.
1
Introduction
Statistical models of shape show considerable promise as a basis for segmenting and interpreting images in 2D [5]. The basic idea is to establish, from a training set, the pattern of ‘legal’ variation in the shapes and spatial relationships of structures for a given class of images. Statistical analysis is used to give an efficient parameterisation of this variability, providing a compact representation of shape and allowing shape constraints to be applied effectively during image interpretation [6]. A key step in building a model involves establishing a dense correspondence between shape boundaries/surfaces over a reasonably large set of training images. It is important to establish the ‘correct’ correspondences, otherwise an inefficient parameterisation of shape can result, leading to difficulty in defining shape constraints effectively. In 2D, correspondence is often established using manually defined ‘landmarks’ but this is a time-consuming, error-prone A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 3–20, 2002. c Springer-Verlag Berlin Heidelberg 2002
4
R.H. Davies et al.
and subjective process. In principle, the method extends to 3D, but in practice, manual landmarking becomes impractical. In this paper we show how an ‘optimal’ model can be built by automatically defining correspondences across a training set of 3D shapes. Several previous attempts have been made to build 3D statistical shape models [3,4,10,12,13,14,21,25]. The problem of establishing dense correspondence over a set of training shapes can be posed as that of defining a parameterisation for each of the training set, assuming correspondence between equivalently parameterised points. Kelemen et. al [14] and Hill et. al [12] use different arbitrary parameterisations of the training shapes. Christiensen et al. [7], Szekely and Lavalle [23] and Rueckert et al. [21] describe methods for warping the space in which the shapes are embedded. Models can then be built from the resulting deformation field [10,13,21]. Brett and Taylor [3,4] and Wang et. al [25] use shape ‘features’ (e.g. regions of high curvature) to establish point correspondences. The correspondences found using the methods described above are not, in any obvious sense, the correct ones. We show in section 2 (fig. 1) that unsatisfactory models can result if correspondences are chosen inappropriately. We start from the position that the correct correspondences are, by definition, those that build the ‘best’ model. We define the ‘best’ model as that with optimal compactness, specificity and generalisation ability. We have shown elsewhere [8] that a model with these properties can be obtained using an objective function based on the minimum description length principle [18]. We have also described a method that uses the objective function to build models in 2D that are better than the best models we could build using manual landmarks [9]. The representation of the parameterisation did not, however, extend to surfaces in 3D. In this paper we describe the derivation of the objective function. We also describe a novel method of representing and manipulating the parameterisation of a surface allowing the construction of shape models in 3D. The method ensures that only valid correspondences can be represented. In the remainder of the paper, we establish notation, and outline the modelbuilding problem. We then provide a summary of the derivation of the minimum description length objective function. We show how a set of surface parameterisations can be represented explicitly and manipulated to build an optimal model. Finally, we present qualitative and quantitative results of applying the method to surfaces obtained from 3D MR images of brain ventricles and rat kidneys.
2
Statistical Shape Models
A 2d (3d) statistical shape model is built from a training set of example outlines (surfaces), aligned to a common coordinate frame. Each shape, Si , (i = 1, . . . ns ), can (without loss of generality) be represented by a set of n points regularly sampled on the shape, as defined by some parameterisation φi . This allows each shape Si to be represented by an np -dimensional shape vector xi , formed by concatenating the coordinates of its sample points. Using Principal Component
3D Statistical Shape Models
5
analysis, each shape vector can be expressed using a linear model of the form: ¯ + Pbi = x ¯+ pm bm (1) xi = x i , m
where x ¯ is the mean shape vector, P = {pm } are the eigenvectors of the covariance matrix (with corresponding eigenvalues {λm }) that describe a set of orthogonal modes of shape variation and b = {bm } are shape parameters that control the modes of variation. Since our training shapes are continuous, we are interested in the limit np → ∞. This leads to an infinitely large covariance matrix, but we note that there can only be, at most, ns − 1 eigenvalues that are not identically zero (although they may be computationally zero). This means that in the summation above, the index m only takes values in the range 1 to ns − 1. To calculate the non-zero eigenvalues, we consider the np × ns data matrix ¯) : i = 1, . . . ns }. The np × np W constructed from the set of vectors {(xi − x covariance matrix is given by D = np1ns WWT with eigenvectors and eigenvalues {pm , λm } thus: Dpm = λm pm . (2) If we define {pm , λm , } to be the eigenvectors and eigenvalues of the ns × ns matrix, D = np1ns WT W then: D pm = λm pm From (2) : Dpm = λm pm 1 ⇒ WWT pm = λm pm , np ns
(3)
pre-multiplying by WT : m
m
⇒ D (WT p ) = λm (WT p ) Similarly: D(Wpm ) = λm (Wpm ).
(4)
Therefore, for all λm = 0, we can assign indices such that: λm = λm and pm = Wpm .
(5)
Thus the ns − 1 eigenvalues of D, which are not identically zero, can be obtained directly from D , and the eigenvectors are a weighted sum of the training shapes. As shown in [15], in the limit np → ∞ the ij th element of D is given by the inner product of shapes i and j: ¯ ¯ Dij = dt (Si (φi (t)) − S(t)) · (Sj (φj (t)) − S(t)) (6) ns where S¯ = n1s i=1 Si is the mean shape and Si (φi ) is a continuous representation of Si parameterised by φi . The integral can be evaluated numerically.
6
R.H. Davies et al.
Fig. 1. The first mode of variation (±3σ) of two shape models built from the training set of hand outlines but parameterised differently. Model A was parameterised using manual ‘landmarks’ and model B was parameterised using arc-length parameterisation. The figure demonstrates that model B can represent invalid shape instances.
New examples of the class of shapes can be generated by choosing values of {bm } within the range found in the training set. The utility of the linear model of shape shown in (1) depends on the appropriateness of the set of parameterisations {φi } that are chosen. An inappropriate choice can result in the need for a large set of modes (and corresponding shape parameters) to approximate the training shapes to a given accuracy and may lead to ‘legal’ values of {bm } generating ‘illegal’ shape instances. For example, figure 1 shows two 2D models generated from a set of 17 hand outlines. Model A uses a set of parameterisations of the outlines that cause ‘natural’ landmarks such as the tips of the fingers to correspond. Model B uses one such correspondence but then uses a simple path length parameterisation to position the other sample points. The variances of the three most significant modes of models A and B are (1.06, 0.58, 0.30) and (2.19, 0.78, 0.54) respectively. This suggests that model A is more compact than model B. All the example shapes generated by model A using values of {bm } within the range found in the training set are ‘legal’ examples of hands, whilst model B generates implausible examples and is thus of limited utility for imposing shape constraints when the model is used for image search, see fig. 1. The set of parameterisations used for model A were obtained by marking ‘natural’ landmarks manually on each training example, then using simple path length parameterisation to sample a fixed number of equally spaced points between them. This manual mark-up is a time-consuming and subjective process. In principle, the modelling approach extends to 3D, but in practice, manual landmarking becomes impractical. We propose to overcome this problem by automatically defining correspondences between a training set of example shapes.
3
An Information Theoretic Objective Function
We wish to define a criterion for selecting the set of parameterisations {φi } that are used to construct a statistical shape model from a set of training boundaries {Si }. Our aim is to choose {φi } so as to obtain the ‘best possible’ model. Ideally, we would like a model with optimal:
3D Statistical Shape Models
7
Generalisation Ability: the model can describe any instance of the object not just those seen in the training set; Specificity: the model can only represent valid instances of the object; Compactness: the variation is explained with few parameters. To achieve this, we follow the principle of Occam’s razor which can be paraphrased: ‘simple descriptions generalise best’. As a quantitative measure of ‘simplicity’, we choose to apply The Minimum Description Length (MDL) Principle [18,19]. The MDL principle is based on the idea of transmitting a data set as an encoded message, where the code is based on some pre-arranged set of parametric statistical models. The full transmission then has to include not only the encoded data values, but also the coded model parameter values. Thus MDL balances the model complexity, expressed in terms of the cost of sending the model parameters, against the quality of fit between the model and the data, expressed in terms of the coding length of the data. Comparison of Description Lengths calculated using models from different classes can be used as a way of solving the Model Selection Problem [11]. However, our emphasis here is not on selecting the class of model, but on using the Description Length for a single class of model as an objective function for optimisation of correspondence between the shapes. We will use the simple two-part coding formulation of MDL. Although this does not give us a coding which is of the absolute minimum length [20], it does however give us a functional form which is computationally simple to evaluate, hence suitable to be used as an objective function for numerical optimisation. 3.1
The Model
Our training set of ns shapes is sampled according to the parameterisations {φi } to give a set of np -dimensional shape vectors {xi }. We choose to model this set of shape vectors using a multivariate Gaussian model. The initial step in constructing such a model is to change to a coordinate system whose axes are aligned with the principal axes of the data set. This corresponds to the orientation of the linear model defined earlier (1): xi = x ¯+
n s −1
pm bm i .
(7)
m=1
The ns − 1 mutually-orthogonal eigenvectors {pm } span the subspace which contains the training set, and, by appropriate scaling, can be transformed into an orthonormal basis set for this subspace. We will also order these vectors in terms of non-decreasing eigenvalue to give us our final orthonormal basis set {˜ pm }. To transmit a shape xi using this model, we first have to transmit the mean shape x ¯, then the deviations from the mean shape, which can be written thus: ˜ m · (xi − x ¯). yim ≡ p
(8)
8
R.H. Davies et al.
¯ is We will assume that the code length for the transmission of the mean shape x a constant for a given training set and number of sample points. Furthermore, the code length for the transmission of the set of ns − 1, np -dimensional basis vectors {˜ pm } is also constant for a given training set and number of sample points and need not be considered further. 3.2
The Description Length
˜ m , we now have to transmit the set of values Y m ≡ {yim : For each direction p i = 1 to ns }. Since we have aligned our coordinate axes with the principal axes of the data, and aligned our origin with the mean shape, each direction can now be modelled using a one-dimensional, centred Gaussian. In the Appendix, we derive an expression for the Description Length of one-dimensional, bounded and quantised data, coded using a centred Gaussian model. To utilise this result, we first have to calculate a strict upper-bound R on the range of our data and also estimate a suitable value for the data quantisation parameter ∆. Suppose that, for our original shape data, we know that the coordinates of our sample points are strictly bounded thus: −
r r ≤ xiα ≤ for all α = 1 to np , i = 1 to ns . 2 2
(9)
Then, the strict bound for the coordinates {yim } is given by: √ R = r np , so that |yim | ≤ R for all i, m.
(10)
The data quantisation parameter ∆ can be determined by quantising the coordinates of our original sample points. Comparison of the original shape and the quantised shape then allows a maximum permissible value of ∆ to be determined. For example, for boundaries obtained from voxelated images, ∆ will typically be of the order of the voxel size. This also determines our lower bound on the modelled variance σmin ≡ 2∆. The parameters R and ∆ are held constant for a given training set, hence we need not consider the Description Length for the transmission of these values. Our original data values Y m are now replaced by their quantised1 values Yˆ m . The variance of the quantized data is then calculated thus: (σ m )2 =
ns 1 (ˆ y m )2 . ns i=1 i
(11)
The Description Length Dm for each direction is then given by (see Appendix): • If σ m ≥ σmin : • If σ m < σmin but the range of Yˆ m ≥ ∆: • Else: 1
Dm = D(1) (σ m , ns , R, ∆) Dm = D(2) (σ m , ns , R, ∆) Dm = 0.
We will use a ˆ to denote the quantised value of a continuum variable a.
3D Statistical Shape Models
3.3
9
The Objective Function
Let us define ng to be the number of directions for which the first of the above criteria holds, and nmin the number which satisfy the second. Then, since the directions are ordered in terms of non-increasing eigenvalue/variance, the total Description Length for our training set, and our Objective function, can be written thus: F=
ng p=1
ng +nmin
D(1) (σ p , ns , R, ∆) +
D(2) (σ q , ns , R, ∆).
(12)
q=ng +1
We now consider the form of this objective function. For the linear model defined earlier (1): ns 1 (y m )2 (13) n p λm = ns i=1 i In the limit ∆ → 0, the quantised values in Yˆ approach their continuum values, so that: (14) σ m → n p λm . If we also consider the limit where ns is sufficiently large, it can be seen that the functions D(1) and D(2) can be written in the form: D(1) (σ m , ns , R, ∆) ≈ f (R, ∆, ns ) + (ns − 2) ln σ m D(2) (σ m , ns , R, ∆) ≈ f (R, ∆, ns ) + (ns − 2) ln σmin +
(ns + 3) 2
m
σ σmin
2
(15) −1
where f is some function which depends only on R, ∆ and ns . So, in this dual m limit, the part of the objective function which depends on the {σ } contains terms similar to the determinant of the covariance matrix (that is ln λm ) used by Kotcheff and Taylor [15]. However, our objective function is well-defined, even in the limit λm → 0, where in fact such a direction makes no contribution to the objective function. Whereas in the form used previously, without the addition of artificial correction terms, it would have an infinitely large contribution.
4
Manipulating the Parameterisation of a Surface
In order to build a statistical shape model, we need to sample a number of corresponding points on each shape. As demonstrated in section 2, the choice of correspondences determines the quality of the model. We have chosen to cast this correspondence problem as that of defining the parameterisation φi , of each shape so as to minimise the value of F in (12). We propose to sove for {φi } using numerical optimisation, which requires that we formulate an explicit (and ideally, compact) representation of the φi that can be manipulated. We would also like the computational complexity to be minimal (i.e. it should only involve the evaluation of elementary functions).
10
R.H. Davies et al.
Each surface in our training set is originally represented as a triangular mesh that is topologically equivalent to a sphere. We obtain an initial parameterisation by mapping each surface mesh to a unit sphere, where the mapping must be such that there is no folding or tearing. Each mapped mesh can then be represented thus: (16) Si = Si (θ, ψ), Si R3 where Si is the set of original positions of the mesh vertices for the ith surface in Euclidean space, and (θ, ψ) are the spherical polar coordinates of each mapped vertex. Various approaches have been described to achieve such mappings [1,2, 24]. Since we intend to optimise the parameterisations, the final result should significantly not depend on this initial mapping. We have used the method described by Brechbulher [2] to produce the results reported below. Changes in parameterisation of a given surface correspond to altering the positions of the mapped vertices on the sphere. That is: Si → Si , θ → θ , ψ → ψ where
Si (θ, ψ) =
Si (θ , ψ )
and
θ =
(17) φθi (θ, ψ),
ψ =
φψ i (θ, ψ).
Note that we have separate parameterisation functions φi = (φθi , φψ i ) for each surface. Valid parameterisation functions φi correspond to exact homeomorphic mappings of the sphere. That is, mappings that are continuous, one-to-one and onto. In the following sections, we present a number of such mappings. 4.1
Symmetric Theta Transformations
Consider an arbitrary point P on the unit sphere. For simplicity, assume that the spherical polar co-ordinates (θ, ψ) on the sphere have been redefined so that P corresponds to the point θ = 0. Let us first consider a rotationally symmetric mapping that reparameterises the θ coordinate: θ → f (θ).
(18)
For the mapping to be homeomorphic and continuous with the identity, f must be a differentiable non-decreasing monotonic function over the range 0 < θ < π, with f (0) = 0, f (π) = π. Any such monotonic function f can be rewritten in terms of the cumulative distribution function of some density function ρ(θ), defined over the range 0 ≤ θ ≤ π. As our normalised density function, we take a constant term plus a wrapped Cauchy distribution. The wrapped Cauchy [16] is a normalisable, uni-modal distribution for circular data, of variable width, which has an analytic indefinite integral:
1 − α2 1 1+A (19) ρ(θ) = N 1 + α2 − 2α cos θ where N = π [1 + A]. Hence: θ f (θ) = π 0
1 (1 + α2 ) cos θ − 2α ds ρ(s) = θ + A arccos 1+A 1 + α2 − 2α cos θ
(20)
3D Statistical Shape Models
11
Fig. 2. Left: Original sphere. Right: Sphere after asymmetric θ transformation.
where α (α ≡ e−a , a ∈ R) is the width, and A (A ≥ 0) is the amplitude of the Cauchy. The constant term is included so that f (θ) = θ when A = 0. i.e. the parameterisation is unchanged when the Cauchy has zero magnitude. 4.2
Asymmetric Theta Transformations
We can also perform non-symmetric transformations: θ → f (θ, ψ).
(21)
Define ψ to be the ψ coordinates redefined so that a point (Q = P ) corresponds to ψ = 0. An asymmetric transformation around the point P , towards a point Q can be achieved using (20) and making the amplitude A a smooth function of the ψ coordinate: A → A(ψ ). (22) One such way to do this is to use the wrapped Cauchy distribution to obtain: A(ψ ) = A0
1 − β2 1 − β2 − 2 1 + β − 2β cos ψ (1 + β)2
(23)
where β (β ≡ e−b ) is the width of the subsidiary Cauchy. We have chosen the formulation such that A(ψ ) has a minimum value of zero. An example of an asymmetric transformation is shown in figure 2.
12
R.H. Davies et al.
4.3
Shear and Twist
We also consider transformations of the ψ coordinate. This is equivalent to shearing and twisting the sphere about the axis defined by the point P . So, for example, we could consider a reparameterisation of the form: ψ → ψ + g(θ) where
g(θ) =
B 2π
1+
γ2
1 − γ2 − 2γ cos (θ − θ0 )
(24)
(25)
where B is the amplitude, γ (γ ≡ e−c , c ∈ R) is the width and θ0 is the position of the centre. This transformation is continuous with the identity at B = 0 (i.e. the transformation has no affect when B = 0). It can also be localised about θ = θ0 in the limit of zero width. An example of such a transformation is shown in Figure 3. Figure 4 shows an example of applying a combination of all the transformations described above.
5
Optimising the Parameterisations
We now wish to manipulate {φi } so as to minimise F in (12). We have found that, for the objects modelled in this paper, the symmetric theta transformations, alone, provide a sufficient group of reparameterisations. To manipulate the parameterisations, we fix the position P and width a of each of the Cauchy kernels and vary its magnitude A. To select the positions P of the kernels, we (approximately) uniformly sample the sphere and centre the kernels at these sample points. It is not strictly possible to position an arbitrary number of equidistant points on the sphere, but a good
Fig. 3. Left: Original sphere. Right: Sphere after shear transformation.
3D Statistical Shape Models
13
Fig. 4. Left: Original sphere. Right: Sphere after combined transformation.
approximation can be obtained by recursive subdivision of a polyhedron (initially an octohedron) and projecting the points onto the sphere surface. At each level of recursion, each triangle is divided into 4 smaller triangles by placing 3 new vertices halfway along each edge - this gives 12 × 4k−2 new kernels on the k th level of recursion. We choose to use a multiresolution approach to the optimisation. The basic idea is to begin with broad Cauchies and to iteratively refine the parameterisation by introducing additional, narrower Cauchies between the existing ones. We have found, by cross validation, that the best value for the width parameter, is ak = 1/2k−2 , i.e. the widths are halved at each level of recursion. A local optimisation algorithm is employed to find the optimum magnitude of each kernel. At each level of recursion, we have 12 × 4k−2 kernels for each shape, creating a 12ns × 4k−2 -dimensional configuration space. This is generally too difficult to optimise robustly and reliably. We have found, however, that optimising the magnitude of a single kernel in turn on each shape gives better results and is substantially quicker. We used the Nelder-Mead simplex algorithm [17] to obtain the results reported in section 6.
6
Results
We present qualitative and quantitative results of applying our method to a training set of 16 rat kidneys and 8 anterior horns of brain ventricles. In each case the shapes were segmented by hand from a set of 3D magnetic resonance images. The algorithm was run for three levels of recursion, giving a total of 66 kernels per shape. We compare the results to models built by uniformly sampling the surface. In figures 5 and 6, we show qualitative results by displaying the variation captured by the first three modes of each model (bm varied by ±2[standard deviatiations seen across the training set]). We show quantitative results in
14
R.H. Davies et al.
Fig. 5. The first three modes of variation ±2λm of the automatically produced model of the brain ventricle
Fig. 6. The first three modes of variation ±2λm of the automatically produced model of the rat kidneys
3D Statistical Shape Models
15
Table 1. A quantitative comparison of each model showing the variance explained by each mode. F is the value of the objective function and VT is the total variance.
Mode 1 2 3 4 5 6 VT F
Kidneys
Automatic 3.06 2.75 1.35 0.94 0.76 0.46 10.51 1396
Uniform 3.23 3.01 1.70 1.08 0.87 0.57 11.98 1417
Mode 1 2 3 4 5 6 VT F
Ventricles
Automatic 11.98 1.41 1.16 0.69 0.36 0.22 15.90 366
Uniform 12.58 1.77 1.49 0.79 0.45 0.24 17.46 371
Fig. 7. A plot showing the cumulative variance described by each mode of the model. This is a measure of the compactness of each model.
table 1, tabulating the variance explained by each mode, the total variance and the value of F . In both cases F is substantially better for the optimised model. Figure 7 shows the cumulative variance plotted against the number of modes used for each model; this measures the compactness of the model. The plots show that, for the entire range of modes, the optimised models are substantially more compact than those obtained by uniformly-sampling the surface. To test the generalisation ability of the models, we performed leaveone-out tests on each model. In figure 8 we show the approximation error for representing an unseen shape as a function of the number of modes used in the reconstruction. The optimised models perform substantially better than the uniformly sampled models whatever the number of modes used, demonstrating superior generalisation ability.
7
Discussion and Conclusions
We have described a method for building 3D statistical shape models by automatically establishing optimal correspondences between sets of shapes. We have shown that the method produces models that are more compact than those
16
R.H. Davies et al.
Fig. 8. Leave one out tests on the models. The plot shows the number of modes used against the mean squared approximation error. This measures the ability of each model to generalise to unseen examples.
based on uniformly-sampled shapes and have substantially better generalisation ability. We have described a novel method of reparameterising closed surfaces. The method guarantees that the resulting reparameterisation is homeomorphic - an essential constraint. With a suitable choice of boundary conditions, the representation can also be applied to reparameterise open surfaces. Although we have only reported results on a relatively small set of example shapes, we believe the method scales easily to deal with sets of 40-50 shapes. The local optimisation algorithm employed will, however, be substantially slower. We are currently looking for more robust and faster methods of finding the minimum. The MDL objective function and optimisation approach provides a unified framework for dealing with all aspects of model building. For example, we plan to investigate including the alignment of the shapes in the optimisation.
Appendix: Description Length for One-Dimensional Centred Gaussian Models In this Appendix, we show how to construct an expression for the description length required to send a one-dimensional, centred data set using a Gaussian model. Our data model is the family of centred Gaussian distributions: 1 y2 (26) ρ(y; σ) = √ exp − 2 . 2σ σ 2π Following the two-part coding scheme [19], the total description length is computed as the sum of two parts; the description length for sending the value and accuracy of the parameter σ, and the description length for coding the data according to this model. To calculate these description lengths, we use the fundamental result that the ideal-coding codeword length for a discrete event A, encoded using a statistical model with associated event probabilities P (A) is given by the Shannon Coding codeword length [22]:
3D Statistical Shape Models
L(A; P ) = − log2 P (A) bits, or: − ln P (A) nats.2
17
(27)
We take our centred data set to be Y = {yi : i = 1 to ns }, where the data is known to lie within a strictly bounded region. To reduce the continuum values {yi } to a set of discrete events, we quantize the data values using a parameter ∆, so that Y → Yˆ = {ˆ yi : i = 1 to ns } 3 , where for any quantized value yˆ from any possible data set: − R < yˆ < R and yˆ = m∆, m ZZ.
(28)
Coding the Parameters We will assume that the parameter σ is described to an accuracy δ. We will also assume that our now quantized parameter σ ˆ is bounded, hence has the allowed values: ˆ ≤ σmax . (29) σ ˆ = nδ, n IN and σmin ≤ σ Given the absence of any prior knowledge, we assume a flat distribution for σ ˆ over this range, which gives us the codeword length: σmax − σmin . (30) Lσˆ = ln δ Note that our receiver cannot decrypt the value of σ ˆ without knowing the value of δ. If we assume that the quantization parameter δ is of the form: δ = 2±k , k IN
(31)
then it can easily be seen that it can be coded directly with a codeword length: Lδ = 1 + | log2 δ| bits ≈ 1 + | ln δ| nats
(32)
where the additional bit/nat codes for the sign in the exponent of δ. The total code length for transmitting the parameters is then given by Lσˆ + Lδ . Coding the Data For our Gaussian data model, the probability P (ˆ y ) associated with a bin centred at yˆ is: yˆ+∆/2 2 ∆ P (ˆ y) = y /2ˆ (33) dk ρ(k; σ ˆ ) ≈ √ exp −ˆ σ2 . σ ˆ 2π yˆ−∆/2
2
3
In what follows, we will restrict ourselves to natural logarithms, and codeword lengths in units of nats. However, expressions can be easily converted to the more familiar binary lengths by noting that 1 bit ≡ ln 2 nats. We will use α ˆ to denote the quantized value of the continuum value α.
18
R.H. Davies et al.
It can be shown numerically that this is a very good approximation (mean fractional error ≤ 1.0% ± 0.8%) for all values σ ˆ ≥ 2∆, hence we will take σmin = 2∆. The code length for the data is then: Ldata = −
ns
ln P (ˆ yi ) = −ns ln ∆ +
i=1
ns ns 1 ln(2πˆ σ2 ) + 2 yˆ2 2 2ˆ σ i=1 i
(34)
The variance of the quantized data is: σ2 =
ns 1 yˆ2 and σmax = R. ns i=1 i
(35)
In general σ differs from the nearest quantized value σ ˆ thus: δ . (36) 2 So, averaging over an ensemble of data sets, and assuming a flat distribution for dσ over this range, we find: δ2 δ2 1 1 δ2 , 2 ≈ 2 1 + 2 , ln σ d2σ = ˆ 2 ≈ ln σ 2 − . (37) 12 σ ˆ σ 4σ 12σ 2 σ ˆ = σ + dσ , |dσ | ≤
By substituting these expressions into (34) and using (35) gives the following expression for the Description Length of the data: ns δ 2 ns ns ln(2πσ 2 ) + + . (38) 2 2 12σ 2 The total Description Length for the parameters and the data is then: ns ns ns δ 2 σmax − σmin . (39) +| ln δ|−ns ln ∆+ ln(2πσ 2 )+ + L(1) = 1+ln δ 2 2 12σ 2 Ldata = −ns ln ∆ +
By differentiating w.r.t. δ and setting the derivative to zero, we find that the optimum parameter accuracy δ is:
12 ∗ δ (σ, ns ) = min 1, σ (40) ns which then allows us to write the above expression as: L(1) = D(1) (σ, ns , R, ∆).
(41)
In the case where σ < σmin , but the quantized data occupies more than one bin, we will model the data using a Gaussian of width σmin and a quantization parameter δ = δ ∗ (σmin , ns ). An analogous derivation to that given above then gives us the Description Length: ns σmax − σmin 2 ) + | ln δ| − ns ln ∆ + ln(2πσmin L(2) = 1 + ln δ 2 ns δ 2 ns σ 2 δ2 − + (42) 1 + ≡ D(2) (σ, ns , R, ∆). 2 2 2 24σmin 2σmin 4σmin
3D Statistical Shape Models
19
The only remaining case is where all the quantized data lies in one bin at the origin. This requires no further information to describe it fully, hence has a description length of zero. Acknowledgements. The authors would like to thank Alan Brett and Johann Kim for their contribution to this work. Rhodri Davies would like to acknowledge the BBSRC and AstraZeneca4 for their financial support.
References 1. Angenent, S., S. Haker, A. Tannenbaum and R. Kikinis: “On the laplace-beltrami operator and brain surface flattening”. IEEE Trans. Medical Imaging, 18: p. 700711. 1999 2. Brechbulher, C., G. Gerig and O. Kubler, “Parameterisation of closed surfaces for 3-D shape description”, in Computer Vision and Image Understanding, 61(2), p154-170, 1995 3. Brett A.D. and C.J. Taylor, “A Method of automated landmark generation for automated 3D PDM construction”, in Image and Vision Computing, 18(9), p. 739-748, 2000 4. Brett A.D. and C.J. Taylor, “Construction of 3D Shape Models of Femoral Articular Cartialge Using Harmonic Maps”, in MICCAI’00, p. 1205-1214, 2000 5. Cootes, T., A. Hill, C. Taylor, and J. Haslam, “The use of Active shape models for locating structures in medical images”. Image and Vision Computing, 12: p. 355-366. 1994. 6. Cootes, T., C. Taylor, D. Cooper and J. Graham, “Active shape models - their training and application”. Computer Vision and Image Understanding, 61: p. 3859. 1995. 7. Christensen, G. E., S. C. Joshi, M.I. Miller, “Volumetric Transformation of Brain Anatomy”, in IEEE Trans. Medical Imaging, 16, p864-877, 1997 8. Davies, Rh. H., C.J. Twining, T.F. Cootes, J.C. Waterton and C.J. Taylor, “A Minimum Description Length Approach to Statistical Shape Modelling”, in IEEE trans. Medical Imaging, To appear 9. Davies, Rh. H., T.F. Cootes, C.J. Twining and C.J. Taylor, “An Information Theoretic Approach to Statistical Shape Modelling”, in British Machine Vision Conference - BMVC’01, p 3-12, 2001 10. Fluete, M., S. Lavalee, “Building a Complete Surface Model from Sparse Data Using Statistical Shape Models: Application to Computer Assisted Knee Surgery”, in MICCAI’98, p878-887, 1998 11. M. H. Hansen and B. Yu, “Model Selection and the Principle of Minimum Description Length”, Technical Memorandum, Bell Labs, Murray Hill, N.J. 1998. 12. Hill,A., A. Thornham and C.J. Taylor, “Model based interpretation of 3D medical images”, in British Machine Vision Conference, BMVC’93, p339-348, 1993 13. Joshi et. al , “Gaussian Random Fields on Sub-Manifolds for Characterizing Brain Surfaces”, in IPMI’97, p381-386, 1997 14. Kelemen, A., G. Szekely, and G. Gerig, “Elastic model-based segmentation of 3-D neuroradiological data sets”. IEEE Transactions On Medical Imaging, 18(10): p. 828-839. 1999. 4
AstraZeneca, Alderley Park, Macclesfield, Cheshire, UK
20
R.H. Davies et al.
15. Kotcheff, A.C.W. and C.J. Taylor, ”Automatic Construction of Eigenshape Models by Direct Optimisation”. Medical Image Analysis, 2: p. 303-314. 1998. 16. Mardia, K. V., Statistics of Directional Data, Academic Press,London,1972 17. Press, W.H., S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, Cambridge University Press; 1993 18. Rissanen, J. R. ”A universal prior for integers and estimation by minimum description length”, Annals of Statistics, vol. 11, no. 2, pp. 416-431, 1983. 19. Rissanen, J. R. Stochastic Complexity in Statistical Inquiry, World Scientific Series in Computer Science, Vol. 15, World Scientific Publishing Co., Singapore, 1989. 20. Rissanen, J. R. “Fisher Information and Stochastic Complexity”, IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 40-47, 1996. 21. Rueckert, D., Frangi, F., Schnabel, J.A., “Automatic construction of 3D statistical deformation models using non-rigid registration”, MICCAI’01 p77-84. 2001. 22. Shannon, C. E., “A mathematical theory of communication,”, Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, 1948. 23. Szeleky, G., S. Lavalee, “Matching 3-D Anatomical Surface with Non-Rigid Deformations using Octree-Splines”, in International Journal of Computer Vision, 18(2), p171-186, 1996 24. D. Tosun and J.L. Prince, “Hemispherical map for the human brain cortex,” Proc. SPIE Medical Imaging 2001, p 290-300. 2001. 25. Wang, Y., B. S. Peterson, and L. H. Staib. “Shape-based 3D surface correspondence using geodesics and local geometry”. CVPR 2000, v. 2: p. 644-51. 2000.
Approximate Thin Plate Spline Mappings Gianluca Donato1 and Serge Belongie2 1
Digital Persona, Inc., Redwood City, CA 94063
[email protected] 2 U.C. San Diego, La Jolla, CA 92093-0114
[email protected]
Abstract. The thin plate spline (TPS) is an effective tool for modeling coordinate transformations that has been applied successfully in several computer vision applications. Unfortunately the solution requires the inversion of a p × p matrix, where p is the number of points in the data set, thus making it impractical for large scale applications. As it turns out, a surprisingly good approximate solution is often possible using only a small subset of corresponding points. We begin by discussing the obvious approach of using the subsampled set to estimate a transformation that is then applied to all the points, and we show the drawbacks of this method. We then proceed to borrow a technique from the machine learning community for function approximation using radial basis functions (RBFs) and adapt it to the task at hand. Using this method, we demonstrate a significant improvement over the naive method. One drawback of this method, however, is that is does not allow for principal warp analysis, a technique for studying shape deformations introduced by Bookstein based on the eigenvectors of the p × p bending energy matrix. To address this, we describe a third approximation method based on a classic matrix completion technique that allows for principal warp analysis as a by-product. By means of experiments on real and synthetic data, we demonstrate the pros and cons of these different approximations so as to allow the reader to make an informed decision suited to his or her application.
1
Introduction
The thin plate spline (TPS) is a commonly used basis function for representing coordinate mappings from R2 to R2 . Bookstein [3] and Davis et al. [5], for example, have studied its application to the problem of modeling changes in biological forms. The thin plate spline is the 2D generalization of the cubic spline. In its regularized form the TPS model includes the affine model as a special case. One drawback of the TPS model is that its solution requires the inversion of a large, dense matrix of size p × p, where p is the number of points in the data set. Our goal in this paper is to present and compare three approximation methods that address this computational problem through the use of a subset of corresponding points. In doing so, we highlight connections to related approaches in the area of Gaussian RBF networks that are relevant to the TPS mapping A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 21–31, 2002. c Springer-Verlag Berlin Heidelberg 2002
22
G. Donato and S. Belongie
problem. Finally, we discuss a novel application of the Nystr¨ om approximation [1] to the TPS mapping problem. Our experimental results suggest that the present work should be particularly useful in applications such as shape matching and correspondence recovery (e.g. [2,7,4]) as well as in graphics applications such as morphing.
2
Review of Thin Plate Splines
Let vi denote the target function values at locations (xi , yi ) in the plane, with i = 1, 2, . . . , p. In particular, we will set vi equal to the target coordinates (xi ,yi ) in turn to obtain one continuous transformation for each coordinate. We assume that the locations (xi , yi ) are all different and are not collinear. The TPS interpolant f (x, y) minimizes the bending energy 2 2 2 (fxx + 2fxy + fyy )dxdy If = R2
and has the form f (x, y) = a1 + ax x + ay y +
p
wi U ((xi , yi ) − (x, y))
i=1
where U (r) = r2 log r. In order for f (x, y) to have square integrable second derivatives, we require that p
wi = 0
i=1
p i=1
w i xi =
p
and wi yi = 0 .
i=1
Together with the interpolation conditions, f (xi , yi ) = vi , this yields a linear system for the TPS coefficients: K P w v = (1) a o PT O where Kij = U ((xi , yi ) − (xj , yj )), the ith row of P is (1, xi , yi ), O is a 3 × 3 matrix of zeros, o is a 3 × 1 column vector of zeros, w and v are column vectors formed from wi and vi , respectively, and a is the column vector with elements a1 , ax , ay . We will denote the (p + 3) × (p + 3) matrix of this system by L; as discussed e.g. in [7], L is nonsingular. If we denote the upper left p × p block of L−1 by L−1 p , then it can be shown that T If ∝ v T L−1 p v = w Kw .
Approximate Thin Plate Spline Mappings
23
When there is noise in the specified values vi , one may wish to relax the exact interpolation requirement by means of regularization. This is accomplished by minimizing H[f ] =
n
(vi − f (xi , yi ))2 + λIf .
i=1
The regularization parameter λ, a positive scalar, controls the amount of smoothing; the limiting case of λ = 0 reduces to exact interpolation. As demonstrated in [9,6], we can solve for the TPS coefficients in the regularized case by replacing the matrix K by K + λI, where I is the p × p identity matrix.
3
Approximation Techniques
Since inverting L is an O(p3 ) operation, solving for the TPS coefficients can be very expensive when p is large. We will now discuss three different approximation methods that reduce this computational burden to O(m3 ), where m can be as small as 0.1p. The corresponding savings factors in memory (5x) and processing time (1000x) thus make TPS methods tractable when p is very large. In the discussion below we use the following partition of the K matrix: A B K= (2) BT C with A ∈ Rm×m , B ∈ Rm×n , and C ∈ Rn×n . Without loss of generality, we will assume the p points are labeled in random order, so that the first m points represent a randomly selected subset. 3.1
Method 1: Simple Subsampling
The simplest approximation technique is to solve for the TPS mapping between a randomly selected subset of the correspondences. This amounts to using A in place of K in Equation (1). We can then use the recovered coefficients to extrapolate the TPS mapping to the remaining points. The result of applying this approximation to some sample shapes is shown in Figure 1. In this case, certain parts were not sampled at all, and as a result the mapping in those areas is poor. 3.2
Method 2: Basis Function Subset
An improved approximation can be obtained by using a subset of the basis functions with all of the target values. Such an approach appears in [10,6] and Section 3.1 of [8] for the case of Gaussian RBFs. In the TPS case, we need to account for the affine terms, which leads to a modified set of linear equations. Starting from the cost function R[w, ˜ a] =
1 λ T ˜w v − K ˜ − P a2 + w ˜ Aw ˜ , 2 2
24
G. Donato and S. Belongie (a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
Fig. 1. Thin plate spline (TPS) mapping example. (a,b) Template and target synthetic fish shapes, each consisting of 98 points. (Correspondences between the two shapes are known.) (c) TPS mapping of (a) onto (b) using the subset of points indicated by circles (Method 1). Corresponding points are indicated by connecting line segments. Notice the quality of the mapping is poor where the samples are sparse. An improved approximation can be obtained by making use of the full set of target values; this is illustrated in (d), where we have used Method 2 (discussed in Section 3.2). A similar mapping is found for the same set of samples using Method 3 (see Section 3.3). In (e-h) we observe the same behavior for a pair of handwritten digits, where the correspondences (89 in all) have been found using the method of [2].
we minimize it by setting ∂R/∂ w ˜ and ∂R/∂a to zero, which leads to the following (m + 3) × (m + 3) linear system, T T ˜ + λA K ˜TP ˜ K ˜ v K w ˜ K (3) = T T ˜ T a P v P K P P ˜ T = [A B T ], w ˜ is an m × 1 vector of TPS coefficients, and the rest where K of the entries are as before. Thus we seek weights for the reduced set of basis functions that take into account the full set of p target values contained in v. If we call P˜ the first m rows of P and I˜ the first m columns of the p × p identity matrix, then under the assumption P˜ T w ˜ = 0, Equation (3) is equivalent to ˜ + λI˜ P w ˜ v K = a o P˜ T O which corresponds to the regularized version of Equation (1) when using the ˜ and P˜ T in place of K and P T . subsampled K The application of this technique to the fish and digit shapes is shown in Figure 1(d,h).
Approximate Thin Plate Spline Mappings
3.3
25
Method 3: Matrix Approximation
The essence of Method 2 was to use a subset of exact basis functions to approximate a full set of target values. We now consider an approach that uses a full set of approximate basis functions to approximate the full set of target values. The approach is based on a technique known as the Nystr¨om method. The Nystr¨om method provides a means of approximating the eigenvectors of K without using C. It was originally developed in the late 1920s for the numerical solution of eigenfunction problems [1] and was recently used in [11] for fast approximate Gaussian process regression and in [8] (implicitly) to speed up several machine learning techniques using Gaussian kernels. Implicit to the Nystr¨ om method is the assumption that C can be approximated by B T A−1 B, i.e. A B ˆ K= (4) B T B T A−1 B If rank(K) = m and the m rows of the submatrix [A B] are linearly indepenˆ = K. In general, the quality of the approximation can be expressed dent, then K as the norm of the difference C − B T A−1 B, the Schur complement of K. Given the m × m diagonalization A = U ΛU T , we can proceed to find the approximate eigenvectors of K: U T ˜ ˆ ˜ ˜ (5) K = U ΛU , with U = B T U Λ−1 ˜ are not orthogonal. To address this, first Note that in general the columns of U ˜ Λ1/2 so that K ˆ = ZZ T . Let QΣQT denote the diagonalization define Z = U of Z T Z. Then the matrix V = ZQΣ −1/2 contains the leading orthonormalized ˆ i.e. K ˆ = V ΣV T , with V T V = I. eigenvectors of K, From the standard formula for the partitioned inverse of L, we have −1 K + K −1 P S −1 P T K −1 −K −1 P S −1 L−1 = , S = −P T K −1 P −S −1 P T K −1 S −1 and thus
(I + K −1 P S −1 P T )K −1 v w −1 v = =L o a −S −1 P T K −1 v
ˆ −1 = V Σ −1 V T and Using the Nystr¨om approximation to K, we have K w ˆ = (I + V Σ −1 V T P Sˆ−1 P T )V Σ −1 V T v , a ˆ = −Sˆ−1 P T V Σ −1 V T v with Sˆ = −P T V Σ −1 V T P , which is 3 × 3. Therefore, by computing matrixvector products in the appropriate order, we can obtain estimates to the TPS
26
G. Donato and S. Belongie (a)
(b)
(c)
Fig. 2. Grids used for experimental testing. (a) Reference point set S1 : 12 × 12 points on the interval [0, 128]×[0, 128]. (b,c) Warped point sets S2 and S3 with bending energy 0.3 and 0.8, respectively. To test the quality of the different approximation methods, we used varying percentages of points to estimate the TPS mapping from S1 to S2 and from S1 to S3 .
coefficients without ever having to invert or store a large p × p matrix. For the regularized case, one can proceed in the same manner, using (V ΣV T + λI)−1 = V (Σ + λI)−1 V T . Finally, the approximate bending energy is given by ˆ = (V T w)T Σ(V T w) wT Kw Note that this bending energy is the average of the energies associated to the x and y components as in [3]. Let us briefly consider what w ˆ represents. The first m components roughly correspond to the entries in w ˜ for Method 2; these in turn correspond to the ˆ (i.e. K) ˜ for which exact information is available. The remaining columns of K ˆ with (implicitly) filled-in values for all but the entries weight columns of K first m entries. In our experiments, we have observed that the latter values of w ˆ are nonzero, which indicates that these approximate basis functions are not being disregarded. Qualitatively, the approximation quality of methods 2 and 3 are very similar, which is not surprising since they make use of the same basic information. The pros and cons of these two methods are investigated in the following section.
4 4.1
Experiments Synthetic Grid Test
In order to compare the above three approximation methods, we ran a set of experiments based on warped versions of the cartesian grid shown in Figure 2(a). The grid consists of 12 × 12 points in a square of dimensions 128 × 128. Call this set of points S1 . Using the technique described in Appendix A, we generated
Approximate Thin Plate Spline Mappings If=0.3
8
6
6
5
5
4
4
3
3
2
2
1
1
0
5
10
15 20 Percentage of samples used
25
Method 1 Method 2 Method 3
7
MSE
MSE
7
If=0.8
8
Method 1 Method 2 Method 3
30
27
0
5
10
15 20 Percentage of samples used
25
30
Fig. 3. Comparison of approximation error. Mean squared error in position between points in the target grid and corresponding points in the approximately warped reference grid is plotted vs. percentage of randomly selected samples used. Performance curves for each of the three methods are shown in (a) for If = 0.3 and (b) for If = 0.8.
point sets S2 and S3 by applying random TPS warps with bending energy 0.3 and 0.8, respectively; see Figure 2(b,c). We then studied the quality of each approximation method by varying the percentage of random samples used to estimate the (unregularized) mapping of S1 onto S2 and S3 , and measuring the mean squared error (MSE) in the estimated coordinates. The results are plotted in Figure 3. The error bars indicate one standard deviation over 20 repeated trials. 4.2
Approximate Principal Warps
In [3] Bookstein develops a multivariate shape analysis framework based on −1 −1 eigenvectors of the bending energy matrix L−1 p KLp = Lp , which he refers to as principal warps. Interestingly, the first 3 principal warps always have eigenvalue zero, since any warping of three points in general position (a triangle) can be represented by an affine transform, for which the bending energy is zero. The shape and associated eigenvalue of the remaining principal warps lend insight into the bending energy “cost” of a given mapping in terms of that mapping’s projection onto the principal warps. Through the Nystr¨ om approximation in ˆ −1 Method 3, one can produce approximate principal warps using L p as follows: ˆ −1 ˆ −1 + K ˆ −1 P S −1 P T K ˆ −1 L p =K = V Σ −1 V T + V Σ −1 V T P S −1 P T V Σ −1 V T = V (Σ −1 + Σ −1 V T P S −1 P T V Σ −1 )V T ∆ ˆ T = V ΛV
28
G. Donato and S. Belongie
Fig. 4. Approximate principal warps for the fish shape. From left to right and top to bottom, the surfaces are ordered by eigenvalue in increasing order. The first three principal warps, which represent the affine component of the transformation and have eigenvalue zero, are not shown.
where ∆ Λˆ = Σ −1 + Σ −1 V T P S −1 P T V Σ −1 = W DW T
to obtain orthogonal eigenvectors we proceed as in section 3.3 to get ˆΣ ˆW ˆT Λˆ = W ∆ ˆ = ˆ 1/2 and QΣQ ˆ T is the diagonalization of D1/2 W T W D1/2 . where W W D1/2 QΣ Thus we can write
ˆ ˆˆT T ˆ −1 L p = V W ΣW V An illustration of approximate principal warps for the fish shape is shown in Figure 4, wherein we have used m = 15 samples. As in [3], the principal warps are visualized as continuous surfaces, where the surface is obtained by ˆ −1 applying a warp to the coordinates in the plane using a given eigenvector of L p as the nonlinear spline coefficients; the affine coordinates are set to zero. The
Approximate Thin Plate Spline Mappings
29
Fig. 5. Exact principal warps for the fish shape.
corresponding exact principal warps are shown in Figure 5. In both cases, warps 4 through 12 are shown, sorted in ascending order by eigenvalue. Given a rank m Nystr¨ om approximation, at most m − 3 principal warps with nonzero eigenvalue are available. These correspond to the principal warps at the “low frequency” end, meaning that very localized warps, e.g. pronounced stretching between adjacent points in the target shape, will not be captured by the approximation. 4.3
Discussion
We now discuss the relative merits of the above three methods. From the synthetic grid tests we see that Method 1, as expected, has the highest MSE. Considering that the spacing between neighboring points in the grid is about 10, it is noteworthy, however, that all three methods achieve an MSE of less than 2 at 30% subsampling. Thus while Method 1 is not optimal in the sense of MSE, its performance is likely to be reasonable for some applications, and it has the advantage of being the least expensive of the three methods. In terms of MSE, Methods 2 and 3 perform roughly the same, with Method 2 holding a slight edge, more so at 5% for the second warped grid. Method 3 has a disadvantage built in relative to Method 2, due to the orthogonalization
30
G. Donato and S. Belongie (a)
(b)
Fig. 6. Comparison of Method 2 (a) and 3 (b) for poorly chosen sample locations. (The performance of Method 1 was terrible and is not shown.) Both methods perform well considering the location of the samples. Note that the error is slightly lower for Method 3, particularly at points far away from the samples.
step; this leads to an additional loss in significant figures and a slight increase in MSE. In this regard Method 2 is the preferred choice. While Method 3 is comparatively expensive and has slightly higher MSE than Method 2, it has the benefit of providing approximate eigenvectors of the bending energy matrix. Thus with Method 3 one has the option of studying shape transformations using principal warp analysis. As a final note, we have observed that when the samples are chosen badly, e.g. crowded into a small area, Method 3 performs better than Method 2. This is illustrated in Figure 6, where all of the samples have been chosen at the back of the tail fin. Larger displacements between corresponding points are evident near the front of the fish for Method 2. We have also observed that the bending energy ˜ exhibits higher variance than that of Method 3; estimate of Method 2 (w ˜ T Aw) e.g. at a 20% sampling rate on the fish shapes warped using If = 0.3 over 100 trials, Method 2 estimates If to be 0.29 with σ = 0.13 whereas Method 3 gives 0.25 and σ = 0.06. We conjecture that this advantage arises from the presence of the approximate basis functions in the Nystr¨ om approximation, though a rigorous explanation is not known to us.
5
Conclusion
We have discussed three approximate methods for recovering TPS mappings between 2D pointsets that greatly reduce the computational burden. An experimental comparison of the approximation error suggests that the two methods that use only a subset of the available correspondences but take into account the full set of target values perform very well. Finally, we observed that the method based on the Nystr¨om approximation allows for principal warp analysis and per-
Approximate Thin Plate Spline Mappings
31
forms better than the basis-subset method when the subset of correspondences is chosen poorly. Acknowledgments. The authors wish to thanks Charless Fowlkes, Jitendra Malik, Andrew Ng, Lorenzo Torresani, Yair Weiss, and Alice Zheng for helpful discussions. We would also like to thank Haili Chui and Anand Rangarajan for useful insights and for providing the fish datasets.
Appendix: Generating Random TPS Transformations To produce a random TPS transformation with bending energy ν, first choose a set of p reference points (e.g. on a grid) and form L−1 p . Now generate a random vector u, set its last three components to zero, and normalize it. Compute the T diagonalization L−1 p = U ΛU , with the eigenvalues sorted in descending order. √ Finally, compute w = νU Λ1/2 u. Since If is unaffected by the affine terms, their values are arbitrary; we set translation to (0, 0) and scaling to (1, 0) and (0, 1).
References 1. C. T. H. Baker. The numerical treatment of integral equations. Oxford: Clarendon Press, 1977. 2. S. Belongie, J. Malik, and J. Puzicha. Matching shapes. In Proc. 8th Int’l. Conf. Computer Vision, volume 1, pages 454–461, July 2001. 3. F. L. Bookstein. Principal warps: thin-plate splines and decomposition of deformations. IEEE Trans. Pattern Analysis and Machine Intelligence, 11(6):567–585, June 1989. 4. H. Chui and A. Rangarajan. A new algorithm for non-rigid point matching. In Proc. IEEE Conf. Comput. Vision and Pattern Recognition, pages 44–51, June 2000. 5. M.H. Davis, A. Khotanzad, D. Flamig, and S. Harms. A physics-based coordinate transformation for 3-d image matching. IEEE Trans. Medical Imaging, 16(3):317– 328, June 1997. 6. F. Girosi, M. Jones, and T. Poggio. Regularization theory and neural networks architectures. Neural Computation, 7(2):219–269, 1995. 7. M. J. D. Powell. A thin plate spline method for mapping curves into curves in two dimensions. In Computational Techniques and Applications (CTAC95), Melbourne, Australia, 1995. 8. A.J. Smola and B. Sch¨ olkopf. Sparse greedy matrix approximation for machine learning. In ICML, 2000. 9. G. Wahba. Spline Models for Observational Data. SIAM, 1990. 10. Y. Weiss. Smoothness in layers: Motion segmentation using nonparametric mixture estimation. In Proc. IEEE Conf. Comput. Vision and Pattern Recognition, pages 520–526, 1997. 11. C. Williams and M. Seeger. Using the Nystr¨ om method to speed up kernel machines. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference, pages 682–688, 2001.
DEFORMOTION Deforming Motion, Shape Average and the Joint Registration and Segmentation of Images Stefano Soatto1 and Anthony J. Yezzi2 1
Department of Computer Science, University of California, Los Angeles, Los Angeles – CA 90095
[email protected] 2 Department of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta – GA 30332
[email protected]
Abstract. What does it mean for a deforming object to be “moving” (see Fig. 1)? How can we separate the overall motion (a finite-dimensional group action) from the more general deformation (a diffeomorphism)? In this paper we propose a definition of motion for a deforming object and introduce a notion of “shape average” as the entity that separates the motion from the deformation. Our definition allows us to derive novel and efficient algorithms to register non-equivalent shapes using region-based methods, and to simultaneously approximate and register structures in grey-scale images. We also extend the notion of shape average to that of a “moving average” in order to track moving and deforming objects through time.
Fig. 1. A jellyfish is “moving while deforming.” What exactly does this mean? How can we separate its “global” motion from its “local” deformation?
1
Introduction
Consider a sheet of paper falling. If it were a rigid object, one could describe its motion by providing the coordinates of one particle and the orientation of an orthonormal reference frame attached to that particle. That is, 6 numbers
This research is supported in part by NSF grant IIS-9876145, ARO grant DAAD1999-1-0139 and Intel grant 8029.
A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 32–47, 2002. c Springer-Verlag Berlin Heidelberg 2002
DEFORMOTION
33
would be sufficient to describe the object at any instant of time. However, being a non-rigid object, in order to describe it at any instant of time one should really specify the trajectory of each individual particle on the sheet. That is, if γ0 represents the initial collection of particles, one could provide a function f that describes how the entire set of particles evolves in time: γt = f (γ0 , t). Indeed, if each particle can move independently, there may be no notion of “overall motion,” and a more appropriate description of f is that of a “deformation” of the sheet. That includes as a special case a rigid motion, described collectively by a rotation matrix1 R(t) ∈ SO(3) and a translation vector T (t) ∈ R3 , so that γt = f (γ0 , t) = R(t)γ0 + T (t) with R(t) and T (t) independent of the particle in γ0 . In practice, however, that is not how one usually describes a sheet of paper falling. Instead, one may say that the sheet is “moving” downwards along the vertical direction while “locally deforming.” The jellyfish in Fig. 1 is just another example to illustrate the same issue. But what does it even mean for a deforming object to be “moving”? From a mathematical standpoint, rigorously defining a notion of motion for deforming objects presents a challenge. In fact, if we describe the deformation f as the composition of a rigid motion (R(t), T (t)) and a “local deformation” function h(·, t), so that γt = h(R(t)γ0 + T (t), t), we can always find infinitely many ˜ t), R(t), ˜ different choices h(·, T˜(t) that give rise to the same overall deformation ˜ Rγ ˜ 0 + T˜(t), t) by simply choosing f : γt = f (γ0 , t) = h(R(t)γ0 + T (t), t) = h( . T ˜ ˜ ˜ ˜ T˜). Therefore, we could h(γ, t) = h(RR (γ − T ) + T, t) for any rigid motion (R, ˜ T˜), which is describe the motion of our sheet with (R, T ) as well as with (R, arbitrary, and in the end we would have failed in defining a notion of “motion” that is unique to the event observed. So, how can we define a notion of motion for a deforming object in a mathematically sound way that reflects our intuition? For instance, in Fig. 6, how do we describe the “motion” of a jellyfish? Or in Fig. 5 the “motion” of a storm? In neuroanatomy, how can we “register” a database of images of a given structure, say the corpus callosum (Fig. 9), by “moving” them to a common reference frame? All these questions ultimately boil down to an attempt to separate the overall motion from the more general deformation. Before proceeding, note that this is not always possible or even meaningful. In order to talk about the “motion” of an object, one must assume that “something” of the object is preserved as it deforms. For instance, it may not make sense to try to capture the “motion” of a swarm of bees, or of a collection of particles that indeed all move independently. What we want to capture mathematically is the notion of overall motion when indeed there is one that corresponds to our intuition! The key to this paper is the observation that the notion of motion and the notion of shape are very tightly coupled. Indeed, we will see that the shape average is exactly what allows separating the motion from the deformation.
1
SO(3) denotes the set of 3 × 3 orthogonal matrices with unit determinant.
34
S. Soatto and A.J. Yezzi
1.1
Prior Related Work
The study of shape spans at least a hundred years of research in different communities from mathematical morphology to statistics, geology, neuroanatomy, paleontology, astronomy etc. In statistics, the study of “Shape Spaces” was championed by Kendall, Mardia and Carne among others [15,20,8,24,9]. Shapes are defined as the equivalence classes of N points in RM under the similarity group2 , RM N /{SE(M ) × R}. Although the framework clearly distinguishes the notion of “motion” (along the fibers) from the “deformation” (across fibers), the analytical tools are essentially tied to the point-wise representation. One of our goals in this paper is to extend the theory to smooth curves, surfaces and other geometric objects that do not have distinct “landmarks.” In computer vision, a wide literature exists for the problem of “matching” or “aligning” objects based on their images, and space limitations do not allow us to do justice to the many valuable contributions. We refer the reader to [32] for a recent survey. A common approach consists of matching collections of points organized in graphs or trees (e.g. [19,11]). Belongie et al. [4] propose comparing planar contours based on their “shape context.” The resulting match is based on “features” rather than on image intensity directly, similar to [10]. “Deformable Templates,” pioneered by Grenander [12], do not rely on “features” or “landmarks;” rather, images are directly deformed by a (possibly infinite-dimensional) group action and compared for the best match in an “image-based” approach [34]. There, the notion of “motion” (or “alignment” or “registration”) coincides with that of deformation, and there is no clear distinction between the two [5]. Another line of work uses variational methods and the solution of partial differential equations (PDEs) to model shape and to compute distances and similarity. In this framework, not only can the notion of alignment or distance be made precise [3,33,25,28], but quite sophisticated theories that encompass perceptually relevant aspects can be formalized in terms of the properties of the evolution of PDEs (e.g. [18,16]). Kimia et al. [16] describes a scale-space that corresponds to various stages of evolution of a diffusing PDE, and a “reacting” PDE that splits “salient parts” of planar contours by generating singularities. The variational framework has also proven very effective in the analysis of medical images [23,30,22]. Although most of these ideas are developed in a deterministic setting, many can be transposed to a probabilistic context [35,7,31]. Scalespace is a very active research area, and some of the key contributions as they relate to the material of this paper can be found in [14,29,17,1,2] and references therein. The “alignment,” or “registration,” of curves has also been used to define a notion of “shape average” by several authors (see [21] and references therein). The shape average, or “prototype,” can then be used for recognition in a nearestneighbor classification framework, or to initialize image-based segmentation by providing a “prior.” Leventon et al. [21] perform principal component analysis 2
SE(M ) indicates the Euclidean group of dimension M .
DEFORMOTION
35
in the aligned frames to regularize the segmentation of regions with low contrast in brain images. Also related to this paper is the recent work of Paragios and Deriche, where active regions are tracked as they “move.” In [27] the notion of motion is not made distinct from the general deformation, and therefore what is being tracked is a general (infinite-dimensional) deformation. Our aim is to define tracking as a trajectory on a finite-dimensional group, despite infinite-dimensional deformations. Substantially different in methods, but related in the intent, is the work on stochastic filters for contour tracking and snakes (see [6] and references therein). Our framework is designed for objects that undergo a distinct overall “global” motion while “locally” deforming. Under these assumptions, our contribution consists of a novel definition of motion for a deforming object and a corresponding definition of shape average (Sect. 2). Our definition allows us to derive novel and efficient algorithms to register non-identical (or non-equivalent) shapes using region-based methods (Sect. 5). We use our algorithms to simultaneously approximate and register structures in images, or to simultaneously segment and calibrate images (Sect. 6). In the context of tracking, we extend our definition to a novel notion of “moving average” of shape, and use it to perform tracking for deforming objects (Sect. 4). Our definitions do not rely on a particular representation of objects (e.g. explicit vs. implicit, parametric vs. non-parametric), nor on the particular choice of group (e.g. affine, Euclidean), nor are they restricted to a particular modeling framework (e.g. deterministic, energy-based vs. probabilistic). For the implementation of our algorithms on deforming contours, we have chosen an implicit non-parametric representation in terms of level sets, and we have implemented numerical algorithms for integrating partial differential equations to converge to the steady-state of an energy-based functional. However, these choices can be easily changed without altering the nature of the contribution of this paper. Naturally, since shape and motion are computed as the solution of a nonlinear optimization problem, the algorithms we propose are only guaranteed to converge to local minima and, in general, no conclusions can be drawn on uniqueness. Indeed, it is quite simple to generate pathological examples where the setup we have proposed fails. In the experimental section we will highlight the limitations of the approach when used beyond the assumptions for which it is designed.
2
Defining Motion and Shape Average
The key idea underlying our framework is that the notion of motion throughout a deformation is very tightly coupled with the notion of shape average. In particular, if a deforming object is recognized as moving, there must be an underlying object (which will turn out to be the shape average) moving with the same motion, from which the original object can be obtained with minimal deformations. Therefore, we will model a general deformation as the composition of a group action g on a particular object, on top of which a local deformation is applied. The shape average is defined as the one that minimizes such deformations.
36
S. Soatto and A.J. Yezzi
ht
γt
gt (µ)
gt
. . .
. . .
h2
g2 µ
T12
γ2
g2 (µ)
h1
γ1
g1
g1 (µ)
Fig. 2. A model (commutative diagram) of a deforming contour.
Let γ1 , γ2 , . . . , γn be n “shapes” (we will soon make the notion precise in Def. 1). Let the map between each pair of shapes be Tij γi = Tij γj , i, j = 1 . . . n.
(1)
It comprises the action of a group g ∈ G (e.g. the Euclidean group on the plane G = SE(2)) and a more general transformation h that belongs to a pre-defined class H (for instance diffeomorphisms). The deformation h is not arbitrary, but depends upon another “shape” µ, defined in such a way that γi = hi ◦ gi (µ), i = 1 . . . n.
(2)
Therefore, in general, following the commutative diagram of Fig. 2, we have that . Tij = hi ◦ gi ◦ gj−1 (µ) ◦ h−1 (3) j so that g = gi gj−1 and h is a transformation that depends on hi , hj and µ. Given two or more “shapes” and a cost functional E : H → R+ defined on the set of diffeomorphisms, the motion gt and the shape average are defined as the n minimizers of t=1 E(ht ) subject to γt = ht ◦ gt (µ). Note that the only factors which determine the cost of ht are the “shapes” before and after the transfor. mation, µi = gi (µ) and γi , so that we can write, with an abuse of notation, . E(h(µi , γi )) = E(µi , γi ). We are therefore ready to define our notion of motion during a deformation. Definition 1 Let γ1 , . . . , γn be smooth boundaries of closed subsets of a differentiable manifold embedded in RN , which we call pre-shapes. Let H be a class of diffeomorphisms acting on γi , and let E : H → R+ be a positive, real-valued functional. Consider now a group G acting on γi via g(γi ). We say that gˆ1 , . . . , gˆn is a motion undergone by γi , i = 1 . . . n if there exists a pre-shape µ ˆ such that gˆ1 , . . . , gˆn , µ ˆ = arg min gt ,µ
n i=1
E(hi ) subject to γi = hi ◦ gi (µ)
i = 1...n
(4)
DEFORMOTION
37
The pre-shape µ ˆ is called the shape average relative to the group G, or Gaverage, and the quantity gˆi−1 (γi ) is called the shape of γi . Remark 1 (Invariance) In the definition above, one will notice that the shape average is actually a pre-shape, and that there is an arbitrary choice of group action g0 that, if applied to γi and µ, leaves the definition unchanged (the functional E is invariant with respect to g0 because T (g ◦ g0 , h ◦ g0 ) = T (g, h) ∀ g0 ). For the case of the Euclidean group SE(N ), a way to see this is to notice that the reference frame where µ is described is arbitrary. Therefore, one may choose, for instance, µ = h−1 1 (γ1 ). Remark 2 (Symmetries) In Def. 1 we have purposefully avoided to use the article “the” for the minimizing value of the group action gˆt . It is in fact possible that the minimum of (4) not be unique. A particular case when this occurs is when the pre-shape γ is (symmetric, or) invariant with respect to a particular element of the group G, or to an entire subgroup. Notice, however, that the notion of shape average is still well-defined even when the notion of motion is not unique. This is because any element in the symmetry group suffices to register the pre-shapes, and therefore compute the shape average (Fig. 3).
3
Shape and Deformation of a Planar Contour
In this section we consider the implementation of the program above for a simple case: two closed planar contours, γ1 and γ2 , where we choose as cost functional for the deformations h1 , h2 either the set-symmetric difference ∆ of their interior (the union minus the intersection), or what we call the signed distance score3 ψ . ψ(µ, γ) = ζ(γ)dx (5) µ ¯
where µ ¯ denotes the interior of the contour µ and ζ is the signed distance function of the contour γ; dx is the area form on the plane. In either case, since we have an arbitrary choice of the global reference frame, we can choose g1 = e, the . group identity. We also call g = g2 , so that µ2 = g(µ). The problem of defining the motion and shape average can then be written as gˆ, µ ˆ = arg min g,µ
3
2
E(hi ) subject to γ1 = h1 (µ); γ2 = h2 ◦ g(µ).
(6)
i=1
The rationale behind this score is that one wants to make the signed distance function as positive as possible outside the contour to be matched, and as negative as possible inside. This score can be interpreted as a weighted Monge-Kantorovic functional where the mass of a curve is weighted by its distance from the boundary.
38
S. Soatto and A.J. Yezzi
. As we have anticipated, we choose either E(hi ) = ∆(gi (µ), γi ) or E(hi ) = ψ(gi (µ), γi ). Therefore, abusing the notation as anticipated before Def. 1, we can write the problem above as an unconstrained minimization gˆ, µ ˆ = arg min φ(γ1 , γ2 ) g,µ
where
. φ(γ1 , γ2 ) = E(µ, γ1 ) + E(g(µ), γ2 )
(7)
and E is either ∆ or ψ. The estimate gˆ defines the motion between γ1 and γ2 , and the estimate µ ˆ defines the average of the two contours. If one thinks of contours and their interior, represented by a characteristic function χ, as a binary image, then the cost functional above is just a particular case of a more general cost functional where each term is obtained by integrating a function inside and a function outside the contours φ=
2 i=1
µ ¯ in
fin (x, γi )dx +
µ ¯ out
fout (x, γi )dx
(8)
where the bar in µ ¯ indicates that the integral is computed on a region inside or outside µ and we have emphasized the fact that the function f depends upon the contour γi . For instance, for the case of the set symmetric difference we have fin = (χγ − 1) and fout = χγ . To solve the problem, therefore, we need to minimize the following functional fin (x, γ1 ) + fin (g(x), γ2 )|Jg |dx + fout (x, γ1 ) + fout (g(x), γ2 )|Jg |dx µ ¯ in
µ ¯ out
(9)
where |Jg | is the determinant of the Jacobian of the group action g. This makes it easy to compute the component of the first variation of φ along the normal direction to the contour µ, so that we can impose ∇µ φ · N = 0
(10)
to derive the first-order necessary condition. If we choose G = SE(2), an isometry, it can be easily shown that ∇µ φ = fin (x, γ1 ) − fout (x, γ1 ) + fin (g(x), γ2 ) − fout (g(x), γ2 ) 3.1
(11)
Representation of Motions and Their Variation
For the specific case of matrix Lie groups (e.g. G = SE(2)), there exist twist coordinates ξ that can be represented as a skew-symmetric matrix ξ so that4
g = eξ 4
and
∂g ∂ ξ = g ∂ξi ∂ξi
(12)
The “widehat” notation, which indicates a lifting to the Lie algebra, should not be confused with the “hat”ˆ, which indicates an estimated quantity.
DEFORMOTION
39
∂ξ where the matrix ∂ξ is composed of zeros and ones and the matrix exponential i can be computed in closed form using Rodrigues’ formula. To compute the variation of the functional φ with respect to the group action g, we notice that the first two terms in φ do not contribute since they are inde. pendent of g. The second two terms are of the generic form A(g) = g(¯µ) f (x)dx. Therefore, we consider the variation of A with respect to the components of ∂A , which we will eventually use to compute the gradient with the twist ξi , ∂ξ i respect to the natural connection ∇G φ = ∂φ g. We first rewrite A(g) us∂ξ ing the change of measure g(¯µ) f (x)dx = µ¯ f ◦ g(x)|Jg |dx which leads to ∂A(g) = µ¯ ∂ξ∂ i (f ◦ g(x))|Jg |dx + µ¯ (f ◦ g(x)) ∂ξ∂ i |Jg |dx and note that the Eu∂ξi clidean group is an isometry and therefore the determinant of the Jacobian is one and the second integral can be re-written, using is zero. The last equation ∂g ∂g −1 , g N ds Green’s theorem, as g(µ) f (x) ∂ξi ◦ g (x), N ds = µ f ◦ g(x) ∂ξ ∗ i where g∗ indicates the push-forward. Notice that g is an isometry and therefore it does not affect the arc length; we then have
∂ ξ ∂A(g) = f (g(x)) g, g∗ N ds (13) ∂ξi ∂ξi µ
After collecting all the partial derivatives into an operator evolution of the group action. 3.2
∂φ ∂ξ ,
we can write the
Evolution
The algorithm for evolving the contour and the group action consists of a twostep process where an initial estimate of the contour µ ˆ = γ1 is provided, along with an initial estimate of the motion gˆ = e. The contour and motion are then updated in an alternating minimization where motion is updated according to ∂φ dˆ g = gˆ dt ∂ξ
(14)
Notice that this is valid not just for SE(2), but for any (finite-dimensional) matrix Lie group, although there may not be a closed-form solution for the exponential map like in the case of SE(3) and its subgroups. In practice, the group evolution (14) can be implemented in local (exponential) coordinates by evolv ∂φ ing ξ defined by g = eξ via dξ dt = ∂ξ . In the level set framework, the derivative of the cost function φ with respect to the coordinates of the group action ξi can be computed as the collection of two terms, one for fin , one for fout where ∂g(x) ∂φ ∂ξi = g(γ1,2 ) ∂ξi , f{in,out} (g(x), γ1,2 )J(g∗ T ) ds. As we have anticipated in Eq. (11), the contour µ ˆ evolves according to dˆ µ = (fin (x, γ1 ) − fout (x, γ1 ) + fin (g(x), γ2 ) − fout (g(x), γ2 ))N dt
(15)
40
S. Soatto and A.J. Yezzi
As we have already pointed out, the derivation can be readily extended to surfaces in space and to multiple objects, as we show in Sect. 6. 3.3
Distance between Shapes
The definition of motion gˆ and shape average µ ˆ as a minimizer of (6) suggests defining the distance5 between two shapes as the “energy” necessary to deform one into the other via the average shape: . ˆ j ). d(γi , γj ) = E(γi , T (ˆ g , h)γ
(16)
For instance, for the case of the set-symmetric difference of two contours, we have . (17) d∆ (γ1 , γ2 ) = χµˆ χγ1 + χgˆ(ˆµ) χγ2 dx and for the signed distance transform we have . dψ (γ1 , γ2 ) = ζ(γ1 )dx + ˆ µ ¯
ˆ ¯) g ˆ(µ
ζ(γ2 )dx.
(18)
In either case, a gradient flow algorithm based on Eq. (14) and (15), when it converges to a global minimum, returns an average shape and a set of group elements gi which minimize the sums of the distances between the contours γi and any other common contour modulo the chosen group.
4
Moving Average and Tracking
The discussion above assumes that an unsorted collection of shapes is available, where the deformation between any two shapes is “small” (modulo G), so that the whole collection can be described by a single average shape. Consider however the situation where an object is evolving in time, for instance Fig. 5. While the deformation between adjacent time instants could be captured by a group action and a small deformation, as time goes by the object may change so drastically that talking about a global time average may not make sense. One way to approach this issue is by defining a notion of “moving average”, similarly to what is done in time series analysis. In classical linear time series, however, the uncertainty is modeled via additive noise. In our case, the uncertainty is an infinite-dimensional deformation h that acts on the measured contour. So the model becomes µ(t + 1) = g(t)µ(t) (19) γ(t) = h(µ(t)) 5
Here we use the term distance informally, since we do not require that it satisfies the triangular inequality. The term pseudo-distance would be more appropriate.
DEFORMOTION
41
where µ(t) represents the moving average of order k = 1. A similar model can be used to define moving averages of higher-order k > 1. The procedure described in Sect. 3, initialized with µ(0) = γ1 , provides an estimate of the moving average of order 1, as well as the tracking of the trajectory g(t) in the group G, which in (19) is represented as the model parameter. Note that the procedure in Sect. 3 simultaneously estimates the state µ(t) and identifies the parameters g(t) of the model (19). It does so, however, without imposing restrictions on the evolution of g(t). If one wants to impose additional constraints on the motion parameters, one can augment the state of the model to include the parameters g, for instance g(t + 1) = eξ(t) g(t). This, however, is beyond the scope of this paper. In Fig. 5 we show the results of tracking a storm with a moving average of order one.
5
Simultaneous Approximation and Registration of Non-equivalent Shapes
So far we have assumed that the given shapes are obtained by moving and deforming a common underlying “template” (the average shape). Even though the given shapes are not equivalent (i.e. there is no group action g that maps one exactly onto the other), g is found as the one that minimizes the cost of the deviation from such an equivalence. In the algorithm proposed in Eq. (14)-(15), however, there is no explicit requirement that the deformation between the given shapes be small. Therefore, the procedure outlined can be seen as an algorithm to register shapes that are not equivalent under the group action. A registration is a group element gˆ that minimizes the cost functional (4). To illustrate this fact, consider the two considerably different shapes shown in Fig. 7, γ1 , γ2 . The simultaneous estimation of their average µ, for instance relative to the affine group, and of the affine motions that best matches the shape average onto the original ones, g1 , g2 , provides a registration that maps γ1 onto γ2 and vice-versa: g = g2 g1−1 . If instead of considering the images in Fig. 7 as binary images that represent the contours, we consider them as gray-scale images, then the procedure outlined, for the case where the score is computed using the set-symmetric difference, provides a way to simultaneously jointly segment the two images and register them. This idea is illustrated in Fig. 9 for true gray-scale (magnetic resonance) images of brain sections.
6
Experiments
Fig. 3 illustrates the difference between the motion and shape average computed under the Euclidean group, and the affine group. The three examples show the two given shapes γi , the mean shape registered to the original shapes, gi (µ) and the mean shape µ. Notice that affine registration allows to simultaneously capture the square and the rectangle, whereas the Euclidean average cannot be registered to either one, and is therefore only an approximation.
42
S. Soatto and A.J. Yezzi
Fig. 3. Euclidean (top) vs. affine (bottom) registration and average. For each pair of objects γ1 , γ2 , the registration g1 (µ), g2 (µ) relative to the Euclidean motion and affine motion is shown, together with the Euclidean average and affine average µ. Note that the affine average can simultaneously “explain” a square and a rectangle, whereas the Euclidean average cannot.
Fig. 4 compares the effect of choosing the signed distance score (left) and the set-symmetric difference (right) in the computation of the motion and average shape. The first choice results in an average that captures the common features of the original shapes, whereas the second captures more of the features in each one. Depending on the application, one may prefer one or the other.
Fig. 4. Signed distance score (left) vs. set-symmetric difference (right). Original contours (γ1 on the top, γ2 on the bottom), registered shape gi (µ) and shape average µ. Note that the original objects are not connected, but are composed by a circle and a square. The choice of pseudo-distance between contours influences the resulting average. The signed distance captures more of the features that are common to the two shapes, whereas the symmetric difference captures the features of both.
DEFORMOTION
43
c Fig. 5. Storm (first row) a collection of images from EUMETSAT 2001, (second row) affine motion of the storm based on two adjacent time instances, superimposed to the original images, (bottom) moving average of order 1.
Fig. 6. Jellyfish. Affine registration (top), moving average and affine motion (bottom) for the jellyfish in Fig. 1. (Bottom right) trajectory of the jellyfish (affine component of the group).
Fig. 5 shows the results of tracking a storm. The affine moving average is computed, and the resulting affine motion is displayed. The same is done for the jellyfish in Fig. 6. Fig. 7 and 8 are meant to challenge the assumptions underlying our method. The pairs of objects chosen, in fact, are not simply local deformations of one another. Therefore, the notion of shape average is not meaningful per se in this context, but serves to compute the change of (affine) pose between the two shapes (Fig. 7). Nevertheless, it is interesting to observe how the shape average allows registering even apparently disparate shapes. Fig. 8 shows a representative example from an extensive set of experiments. In some cases, the shape average contains disconnected components, in some other it includes small parts that are shared by the original dataset, whereas in others it removes parts that are not consistent among the initial shapes (e.g. the tails). Notice that our framework is not meant to capture such a wide range of variations. In particular, it does
44
S. Soatto and A.J. Yezzi
Fig. 7. Registering non-equivalent shapes. Left to right: two binary images representing two different shapes; affine registration; corresponding affine shape; approximation of the original shapes using the registration of the shape average based on the set-symmetric difference. Results for the signed distance score are shown in Fig. 8. This example is shown to highlight the limitations of our method.
Fig. 8. Biological shapes. For the signed distance score, we show the original shape with the affine shape average registered and superimposed. It is interesting to notice that different “parts” are captured in the average only if they are consistent in the two shapes being matched and, in some cases, the average shape is disconnected.
not possess a notion of “parts” and it is neither hierarchical nor compositional. In the context of non-equivalent shapes (shapes for which there is no group action mapping one exactly onto the other), the average shape serves purely as a support to define and compute motion in a collection of images of a given deforming shape. Fig. 9 shows the results of simultaneously segmenting and computing the average motion and registration for 4 images from a database of magnetic resonance images of the corpus callosum.
DEFORMOTION
45
Fig. 9. Corpus Callosum (top row) a collection of (MR) images from different patients (courtesy of J. Dutta), further translated, rotated and distorted to emphasize their misalignment (second row). Aligned contour (second row, dark gray, superimposed to original regions) and shape average (bottom) corresponding to the affine group.
Finally, Fig. 10 shows an application of the same technique to simultaneously register and average two 3D surfaces. In particular, two 3D models in different
Fig. 10. 3D Averaging and registration (left) two images of 3D models in different poses (center) registered average (right) affine average. Note that the original 3D surfaces are not equivalent. The technique presented allows “stitching” and registering different 3D models in a natural way.
46
S. Soatto and A.J. Yezzi
poses are shown. Our algorithm can be used to register the surfaces and average them, thus providing a natural framework to integrate surface and volume data. We wish to thank S. Belongie and B. Kimia for test data and suggestions.
References 1. L. Alvarez and J. M. Morel. Morphological approach to multiscale analysis: From principles to equations. In In Geometric–Driven Diffusion in Computer Vision, 1994. 2. L. Alvarez, J. Weickert, and J. Sanchez. A scale-space approach to nonlocal optical flow calculations. In In ScaleSpace ’99, pages 235–246, 1999. 3. R. Azencott, F. Coldefy, and L. Younes. A distance for elastic matching in object recognition. Proc. 13th Intl. Conf. on Patt. Recog, 1:687–691, 1996. 4. S. Belongie, J. Malik, and J. Puzicha. Matching shapes. In Proc. of the IEEE Intl. Conf. on Computer Vision, 2001. 5. D. Bereziat, I. Herlin, and L. Younes. Motion detection in meteorological images sequences: Two methods and their comparison. In Proc. of the SPIE, 1997. 6. A. Blake and M. Isard. Active contours. Springer Verlag, 1998. 7. C. Bregler and S. Omohundro. Surface Learning with Applications to Lip Reading. In J. D. Cowan, G. Tesauro and J. Alspector (eds), Advances in Neural Information Processing Systems (6), San Francisco, CA: Morgan Kaufmann Publishers, 1994. 8. T. K. Carne. The geometry of shape spaces. Proc. of the London Math. Soc. (3) 61, 3(61):407–432, 1990. 9. T. F. Cootes, C. J. Taylor, D. H. Cooper, and J. Graham. Active Shape Models - Their Training and Application. Computer Vision and Image Understanding, 61(1), 1995, 38-59. 10. H. Chui and A. Rangarajan. A new algorithm for non-rigid point matching. In Proc. of the IEEE Intl. Conf. on Comp. Vis. and Patt. Recog., pages 44–51, 2000. 11. M. Fischler and R. Elschlager. The representation and matching of pictorial structures. IEEE Transactions on Computers, 22(1):67–92, 1973. 12. U. Grenander. General Pattern Theory. Oxford University Press, 1993. 13. U. Grenander and M. I. Miller. Representation of knowledge in complex systems. J. Roy. Statist. Soc. Ser. B, 56:549–603, 1994. 14. P.T. Jackway and R. Deriche. Scale-space properties of the multiscale morphological dilationerosion. IEEE Trans. PAMI, 18(1):38–51, 1996. 15. D. G. Kendall. Shape manifolds, procrustean metrics and complex projective spaces. Bull. London Math. Soc., 16, 1984. 16. B. Kimia, A. Tannenbaum, and S. Zucker. Shapes, shocks, and deformations i: the components of two-dimensional shape and the reaction-diffusion space. IJCV, 15:189–224, 1995. 17. R. Kimmel. Intrinsic scale space for images on surfaces: The geodesic curvature flow. In Lecture Notes In Computer Science: First International Conference on Scale-Space Theory in Computer Vision, 1997. 18. R. Kimmel, N. Kiryati, and A. M. Bruckstein. Multivalued distance maps for motion planning on surfaces with moving obstacles. IEEE TAC, 14(3):427–435, 1998.
DEFORMOTION
47
19. M. Lades, C. Borbruggen, J. Buhmann, J. Lange, C. von der Malsburg, R. Wurtz, and W. Konen. Distortion invariant object recognition in the dynamic link architecture. IEEE Trans. on Computers, 42(3):300–311, 1993. 20. H. Le and D. G. Kendall. The Riemannian structure of Euclidean shape spaces: a novel environment for statistics. The Annals of Statistics, 21(3):1225–1271, 1993. 21. M. Leventon, E. Grimson, and O. Faugeras. Statistical shape influence in geodesic active contours, 2000. 22. R. Malladi, R. Kimmel, D. Adalsteinsson, V. Caselles G. Sapiro, and J. A. Sethian. A geometric approach to segmentation and analysis of 3d medical images. In Proc. Mathematical Methods in Biomedical Image Analysis Workshop, pages 21–22, 1996. 23. R. Malladi, J. A. Sethian, and B. C. Vemuri. Shape modeling with front propagation: A level set approach. IEEE PAMI, 17(2):158–175, 1995. 24. K. V. Mardia and I. L. Dryden. Shape distributions for landmark data. Adv. appl. prob., 21(4):742–755, 1989. 25. M. I. Miller and L. Younes. Group actions, diffeomorphisms and matching: a general framework. In Proc. of SCTV, 1999. 26. S. Osher and J. Sethian. Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi equations. J. of Comp. Physics, 79:12–49, 1988. 27. N. Paragios and R. Deriche. Geodesic active contours and level sets for the detection and tracking of moving objects. IEEE PAMI, 22(3):266–280, 2000. 28. C. Samson, L. Blanc-Feraud, G. Aubert, and J. Zerubia. A level set model for image classification. In in International Conference on Scale-Space Theories in Computer Vision, pages 306–317, 1999. 29. B. ter Haar Romeny, L. Florack, J. Koenderink, and M. Viergever (Eds.). Scalespace theory in computer vision. In LLNCS, Vol 1252. Springer Verlag, 1997. 30. P. Thompson and A. W. Toga. A surface-based technique for warping threedimensional images of the brain. IEEE Trans. Med. Imaging, 15(4):402–417, 1996. 31. K. Toyama and A. Blake. Probabilistic tracking in a Metric Space. In Proc. of the Eur. Conf. on Comp. Vision, 2001. 32. R. C. Veltkamp and M. Hagedoorn. State of the art in shape matching. Technical Report UU-CS-1999-27, University of Utrecht, 1999. 33. L. Younes. Computable elastic distances between shapes. SIAM J. of Appl. Math., 1998. 34. A. Yuille. Deformable templates for face recognition. J. of Cognitive Neurosci., 3(1):59–70, 1991. 35. S. Zhu, T. Lee, and A. Yuille. Region competition: Unifying snakes, region growing, energy /bayes/mdl for multi-band image segmentation. In ICCV, pages 416–423, 1995.
Region Matching with Missing Parts Alessandro Duci1,4 , Anthony J. Yezzi2 , Sanjoy Mitter3 , and Stefano Soatto4 1
Scuola Normale Superiore, Pisa – Italy 56100
[email protected] 2 Georgia Institute of Technology, Atlanta – GA 30332
[email protected] 3 Massachusetts Institute of Technology, Cambridge – MA 02139
[email protected] 4 University of California at Los Angeles, Los Angeles – CA 90095
[email protected]
Abstract. We present a variational approach to the problem of registering planar shapes despite missing parts. Registration is achieved through the evolution of a partial differential equation that simultaneously estimates the shape of the missing region, the underlying “complete shape” and the collection of group elements (Euclidean or affine) corresponding to the registration. Our technique applies both to shapes, for instance represented as characteristic functions (binary images), and to grayscale images, where all intensity levels evolve simultaneously in a partial differential equation. It can therefore be used to perform “region inpainting” and to register collections of images despite occlusions. The novelty of the approach lies on the fact that, rather than estimating the missing region in each image independently, we pose the problem as a joint registration with respect to an underlying “complete shape” from which the complete version of the original data is obtained via a group action. Keywords: shape, variational, registration, missing part, inpainting
1
Introduction
Consider different images of the same scene, taken for instance from a moving camera, where one or more of the images have been corrupted, so that an entire part is missing. This problem arises, for instance, in image registration with missing data, in the presence of occlusions, in shape recognition when one or more parts of an object may be absent in each view, and in “movie inpainting” where one or more frames are damaged and one wants to “transfer” adjacent frames to fill in the damaged part. We consider a simplified version of the problem, where we have a compact region in each image i, bounded by a closed planar contour, γi , and a region of the
This research is sponsored in part by ARO grant DAAD19-99-1-0139 and Intel grant 8029.
A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 48–62, 2002. c Springer-Verlag Berlin Heidelberg 2002
Region Matching with Missing Parts
49
image, with support described by a characteristic function χi , is damaged. We do not know a-priori what the region χi is, and we do not know the transformation mapping one image onto the other. However, we make the assumption that such a transformation can be well approximated by a finite-dimensional group gi , for instance the affine or the projective group. In addition, we do not know the value of the image in the missing region. Therefore, given a sequence of images, one has to simultaneously infer the missing regions χi as well as the transformations gi and the occluded portions of each contour γi . We propose an algorithm that stems from a simple generative model, where an unknown contour µ0 , the “complete shape,” is first transformed by a group action gi , and then occluded by a region χi (Figure 1). Therefore, one only estimates the complete shape and the group actions: gˆ1 , . . . , gˆk , µ ˆ0 , χ ˆ1 , . . . , χ ˆk = arg min
gi ,µ0
k
φ(χi (γi ), χi ◦ gi (µ0 ))
(1)
i=1
for a given discrepancy measure φ. A simpler case is when the occlusion occurs at the same location in all shapes; in this case, there is only one indicator function χ0 that acts on the complete shape µ0 .
Fig. 1. A contour undergoes a global motion and local occlusions.
50
2
A. Duci et al.
Background and Prior Work
The analysis of “Shape Spaces” was pioneered in Statistics by Kendall, Mardia and Carne among others [12,17,6,20]. Shapes are defined as the equivalence classes of points modulo the similarity group, RM N /SE(M ) × R. These tools have proven useful in contexts where N distinct “landmarks” are available, for instance in comparing biological shapes with N distinct “parts.” Various extensions to missing points have been proposed, mostly using expectationmaximization (EM), alternating between computing the sufficient statistics of the missing data and performing shape analysis in the standard framework of shape spaces. However, since this framework is essentially tied to representing shapes as collections of points, they do not extend to the case of continuous curves and surfaces in a straightforward way, and we will therefore not pursue them further here. In computational vision, a wide literature exists for the problem of “matching” or “aligning” discrete representations of collections of points, for instance organized in graphs or trees [16,8]. A survey of shape matching algorithms is presented in [29]. Just to highlight some representative algorithms, Belongie et al. [2] propose comparing planar contours based on the “shape context” of each point along the contour. This work is positioned somewhere in between landmark or feature-based approaches and image-based ones, similarly to [7]. Kang et al. [11] have recently approached the multiple image inpainting problem using a shape context representation. Deformable templates, pioneered by Grenander [9], do not rely on a pointwise representation; rather, images are deformed under the action of a group (possibly infinite-dimensional) and compared for the best match in an imagebased approach [32,3]. Grenander’s work sparked a current that has been particularly successful in the analysis of medical images, for instance [10]. In this work we would like to retain some of the features of deformable templates, but extend them to modeling missing parts. A somewhat different line of work is based on variational methods and the solution of partial differential equations (PDEs) to deform planar contours and quantify their “distance.” Not only can the notion of alignment or distance be made precise [1,31,21,14,26], but quite sophisticated theories of shape, that encompass perceptually relevant aspects, can be formalized in terms of the properties of the evolution of PDEs (e.g. [15,13]). The variational framework has also been proven very effective in the analysis of medical images [19,28,18]. Zhu et al. [33] have also extended some of these ideas to a probabilistic context. Other techniques rely on matching different representations, for instance skeletons [13], that are somewhat robust to missing parts. In [27] a similar approach is derived using a generic representation of 2-D shape in the form of structural descriptions from the shocks of a curve evolution process, acting on bounding contours. The possibility of making multiple registration by finding a mean shape and a rigid transformation was studied by Pennec [24] in the case of 3D landmarks. Leung, Burl and Perona [5] described an algorithm for locating quasi-frontal
Region Matching with Missing Parts
51
views of human faces in cluttered scenes that can handle partial occlusions. The algorithm is based on coupling a set of local feature detectors with a statistical model of the mutual distances between facial features. In this work, we intend to extend these techniques to situations where parts of the image cannot be used for matching (see [30]) and at the same time landmark approaches fail. In the paper of Berger and Gerig [4], a deformable area-based template matching is applied to low contrast medical images. In particular, they use a least squares template matching (LSM) with an automatic quality control of the resulting match. Nastar, Moghaddam and Pentland [22] proposed to use a statistical learning method for image matching and interpolation of missing data. Their approach is based on the idea of modeling the image like a deformable intensity surface represented by a 3D mesh and use principal component analysis to provide a priori knowledge about object-specific deformations. Rangarajan, Chui and Mjolsness [25] defined a novel distance measure for non-rigid image matching where probabilistic generative models are constructed for the nonrigid matching of point-sets. 2.1
Contributions of This Paper
This work presents a framework and an algorithm to match regions despite missing parts. To the best of our knowledge, work in this area, using region-based variational methods, is novel. Our framework relies on the notion of “complete shape” which is inferred simultaneously with the group actions that map the complete shape onto the incomplete ones. The complete shape and the registration parameters are defined as the ones that minimize a cost functional, and are computed using an alternating minimization approach where a partial differential equation is integrated using level set methods [23].
3
Matching with Missing Parts
The formulation of the problem and the derivation of the evolution equations are introduced in this section for the case of a planar shape under isometric transformations (rigid motions). In this case, the dimension of the space is 2 and the determinant of the Jacobian of the group is J(g) = 1 for all the elements g of the group G. The main assumption about the shape is that it must be a regular domain, that is an open and bounded subset of R2 with a finite number of connected components and a piece-wise C ∞ boundary. This regularity is required to avoid singular pathologies and to make the computation possible. The main notation that will be used in this section is listed below. Notation – – – – –
¯ are regular domains in R2 γ¯i , µ γi , µ are the boundaries of γ¯i , µ ¯ χ(γ) is the characteristic function of the set γ¯ A(γ) is the area (volume) of the region γ¯ ·, · is the usual inner product
52
3.1
A. Duci et al.
Formulation of the Problem
Let γ¯1 , . . . , γ¯k be regular domains of R2 , all obtained from the same regular domain µ ¯ ⊂ R2 by composition with characteristic functions χ1 , . . . , χk : R2 → R and actions of Lie group elements g1 , . . . , gk ∈ G. We want to find the best solution in the sense expressed by the functional φ=
k
A(¯ γi \ gi (¯ µ)) + α A(¯ µ)
(2)
i=1
where A denotes the area, α is a design constant, µ ¯, χi and gi are the unknowns and the sets γ¯i and the structure of G are given. The rationale behind the choice of the cost function φ is that one wants to maximize the overlap between the incomplete shapes and the registered complete shape (first term) while keeping the complete shape as small as possible (second term). This is equivalent to minimizing the area of the γ¯i that is not covered by the image of the complete shape after the application of the group action gi . At the same time, one needs to minimize a quantity related to the complete shape (e.g. the area) to constrain the solution to be non-singular. Without the second term, it is always possible to choose a compact complete shape that covers all the incomplete ones (e.g. a big square) and minimizes the first term. 3.2
Minimization with Respect to Shape
The functional φ can be written in integral form φ=
k i=1
γ ¯i
(1 − gi µ ¯)dx + α
dx
(3)
χ(µ)dx
(4)
µ ¯
and using the characteristic function notation φ=
k
χ(γi )(1 − χ(gi µ))dx + α
i=1
=
k
χ(γi )dx −
i=1
k
χ(γi )χ(gi µ))dx + α
χ(µ)dx.
(5)
i=1
Since the first term of φ is independent of µ, g and remembering that gi are isometries, the problem of minimizing φ is equivalent to that of finding the minimum of the energy E(gi , µ) =
µ ¯
α−
k i=1
χ(gi−1 γi ) dx.
(6)
Region Matching with Missing Parts
53
One can show that the first variation of this integral along the normal direction of the contour is simply its integrand, by using the divergence theorem, and therefore conclude that a gradient flow that minimizes the energy E with respect to the shape of the contour µ is given by k ∂µ −1 χ(gi γi ) N (7) = α− ∂t i=1 where N is the normal vector field of the contour µ.
3.3
Minimization with Respect to the Group Action
In order to compute the variation of the functional φ with respect to the group actions gi , we first notice that there is only one term that depends on gi in equation (6). Therefore, we are left with having to compute the variation of (8) − χ(gi−1 γi )dx. µ ¯
In order to simplify the notation, we note that the term above is of the generic form . W (g) = f (g(x))dx (9) µ ¯
with f = χ(γi ). Therefore, we consider the variation of W with respect to the components of the exponential coordinates1 ξi of the group gi = eξi ∂W ∂ = f (g(x))dx (10) ∂ξi ∂ξi µ¯ ∂ ∇f (g(x)) g(x)dx. (11) = ∂ξi µ ¯ Using Green’s theorem it is possible to write the variation as an integral along the contour of µ and one over g(¯ µ) with a divergence integrand
∂W ∂ ∂ ∗ −1 (g) = f (g(x)) g(x), g N d s − f (y)∇y · g(g (y)) d y. ∂ξi ∂ξi ∂ξi µ g(¯ µ) (12) Therefore, the derivative with respect of the group action is ∂ ∂φ = gi (x), gi∗ Ni d s. ∂ξi ∂ξi µ ¯ ∩gi−1 (γi ) 1
(13)
Every finite-dimensional Lie group admits exponential coordinates. For the simple case of the isometries of the plane, the exponential coordinates can be computed in closed-form using Rodrigues’ formula.
54
A. Duci et al.
Where N is the normal vector field to the boundary of gi−1 (γi ) and gi∗ is the push forward induced by the map gi . Detailed calculations are reported in Appendix A. 3.4
Evolution Equations
Within the level set framework, a function ψ is evolved instead of the contour µ. The function ψ is negative inside µ, positive outside and zero on the contour. The evolution of ψ depends on the velocity of µ via the Hamilton-Jacobi equation
k ut + α − i=1 χ(gi−1 γi ) |∇u| = 0, (14) u(0, x) = ψ (t) (x). The evolution equations follow ψ (t+1) (x) = u(1, x |ψ (t) ) µ ¯(t) = {x : ψ(x) < 0} (t+1) (t) = ξi − βξ ξi
(15)
µ ¯ ∩gi−1 (γi )
∂ ∗ gi (x), gi Ni d s ∂ξi
(16) (17)
where βξ is a step parameter and u(·, · |ψ (t) ) is the solution of (14) with initial condition u(0, x) = ψ (t) (x). 3.5
Generalization to Graylevel Images
There are many possible generalizations of the above formulas. Here we present the case of gray level images. The case of color images is very similar so the equations will not be stated. The main idea is to work with a generic level set between the minimum and the maximum intensity levels and write the functional to match all the level sets simultaneously using the partial differential equation in Eq. (25). To derive this equation, let k images of the same object Ii , i = 1, . . . , k be given and γ¯iδ = {x : Ii < δ}
(18)
be the generic δ-underlevel of Ii , where δ is a positive constant. Then let µ : R2 → R
(19)
be a function that represents the complete image intensity (the choice of the name µ is not casual, since this will turn out to be the complete shape for the case of greylevel images) and µ ¯δ = {x : µ < δ} µδ = ∂ µ ¯δ
(20)
Region Matching with Missing Parts
55
respectively its underlevel and the boundary of the underlevel. From the same considerations developed for the case of a contour, we write the functional φ as φ=
n k
A(¯ γiδ \ gi (¯ µj )) + α
i=1 j=1
n
A(µj )
(21)
j=1
where j is a discretization of the level set δ φ=
k n
χ(γiδ )(1
j
− χ(gi µ ))dx + α
i=1 j=1
n
χ(µj )dx
(22)
j=1
and in the same way the derivatives of the functional can be obtained as k ∂ µj −1 δ = α− χ(gi γi ) N j , ∂t i=1 n ∂ ∂φ ∗ δ =− gi (x), gi Ni d s. ∂ξi ∂ξi ¯ j ∩gi−1 (γiδ ) j=1 µ
(23) (24)
After letting j go to the limit, Eq. (23) gives the Hamilton-Jacobi equation for the function µ: k H (Ii (gi (x)) − µ(t, x)) − α |∇µ(t, x)| = 0 (25) µt (t, x) + i=1
where
1 if s > 0, H(s) = 0 if s ≤ 0.
(26)
Therefore, the evolution equation for both the function µ and the parameters gi is given by (t) k (t) (t) µ(t+1) (x) = µ(t) (x) − βµ i=1 H Ii (gi (x)) − µ (x) − α |∇µ (x)| (t) ∂ gi (t+1) (t) (t) (t) = ξi − βξ H Ii (gi ) − µ(t) dx ξi (t) , (∇γi )(gi (x)) ∂ξi
(27) where βµ and βξ are step parameters.
4
Experiments
A numerical implementation of the evolution equations (15),(16),(17) has been written within the level set framework proposed by Osher and Sethian [23] using
56
A. Duci et al.
Fig. 2. Hands. (Top) a collection of images of the same hand in different poses with different missing parts. The support of the missing parts is unknown. (Middle) similarity group, visualized as a “registered” image. (Bottom) estimated template corresponding to the similarity group (“complete shape”).
Fig. 3. Hands Evolution. (Top) evolution of the complete shape for t = 0, . . . , 20. (Bottom) evolution of g2 (µ) for t = 0, . . . , 20.
Region Matching with Missing Parts
57
an ultra narrow band algorithm and an alternating minimization scheme. A set of common shapes (hands, leaves, mice, letters) has been chosen and converted into binary images of 256 × 256 pixels. For each image of this set, a group of binary images with missing parts and with different poses has been generated (Figures 2, 4 curves γ1 , . . . , γ5 ). The following level set evolution equation has been used µt +
α−
k i=1
χ(gi−1 γi )
|∇µ| = 0
(28)
with a first-order central scheme approximation. The evolution of the pose parameters has been carried out using the integral (17) with the following approximation of the arclength ds ds ≈ |∇(µ)|dx.
(29)
Fig. 4. Letter “A.” (Top) a collection of images of the letter “A” in different poses with different missing parts. The support of the missing parts is unknown. (Middle) similarity group (“registration”). (Bottom) estimated template corresponding to the similarity group (“complete shape”).
58
A. Duci et al.
Fig. 5. Letter “A” Evolution. (Top) evolution of the complete shape for t = 0, . . . , 20. (Bottom) evolution of g3 (µ) for t = 0, . . . , 20.
The evolution has been initialized with the following settings µt=0 = γ1 Ti = Bγi − Bγ1
cos θi − sin θi Ri = , sin θi cos θi
(30) with θi = Eγ i OEγ1
where Bγi is the baricenter of γi and Eγi is the principal axis of inertia of the region γ¯i . The value of α has been set between 0 and 1. Ri , Ti are the rotational and translational components of gi = (Ri , Ti ) ∈ SE(2). In Figures 2, 4 some results have been illustrated. γj are the starting curves and µ is the complete shape in an absolute system after the computation. The figures show the computed gj (µ), the estimated rigid motions. Figure 6 shows the method applied to grayscale images of a face, where different portions have been purposefully erased. Figure 8 shows the results of matching a collection of images of the corpus callosum of a patient. One way to further improve this technique is to use richer finite-dimensional groups G that can account for more than simple rotations and translations. Simple examples include the affine and projective groups, for which the derivation is essentially the same, except for a few changes of measure due to the fact that they are not isometric. The experiments show that this method works very well even when the missing part in each image is pretty significant, up to about 20% of the area.
Region Matching with Missing Parts
59
Fig. 6. Faces (Top) a collection of images of the same face in different poses with different missing parts. The support of the missing parts is unknown. (Middle) similarity group, visualized as a “registered” image. (Bottom) estimated template corresponding to the similarity group (“complete image”).
Fig. 7. Face evolution. (Top) evolution of the complete image for t = 0, . . . , 189. (Bottom) evolution of g5 (µ) for t = 0, . . . , 189.
60
A. Duci et al.
Fig. 8. Corpus Callosum. (Top) a collection of images of the same corpus callosum in different poses with different missing parts. The support of the missing parts is unknown. (Middle) similarity group, visualized as a “registered” image. (Bottom) estimated template corresponding to the similarity group (“complete image”).
Fig. 9. Corpus Callosum evolution. (Top) evolution of the complete image for t = 0, . . . , 199. (Bottom) evolution of g2 (µ) for t = 0, . . . , 199.
Region Matching with Missing Parts
61
References 1. R. Azencott, F. Coldefy, and L. Younes. A distance for elastic matching in object recognition. Proc. 13th Intl. Conf. on Patt. Recog, 1:687–691, 1996. 2. S. Belongie, J. Malik, and J. Puzicha. Matching shapes. In Proc. of the IEEE Intl. Conf. on Computer Vision, 2001. 3. D. Bereziat, I. Herlin, and L. Younes. Motion detection in meteorological images sequences: Two methods and their comparison. In Proc. of the SPIE, 1997. 4. M. Berger and G. Gerig. Deformable area-based template matching with application to low contrast imagery, 1998. 5. M. Burl, T. Leung, and P. Perona. Face localization via shape statistics. In Proc. Intl. Workshop on automatic face and gesture recognition, pages 154–159, Zurich, June 1995. IEEE Computer Soc. 6. T. K. Carne. The geometry of shape spaces. Proc. of the London Math. Soc. (3) 61, 3(61):407–432, 1990. 7. H. Chui and A. Rangarajan. A new algorithm for non-rigid point matching. In Proc. of the IEEE Intl. Conf. on Comp. Vis. and Patt. Recog., pages 44–51, 2000. 8. M. Fischler and R. Elschlager. The representation and matching of pictorial structures. IEEE Transactions on Computers, 22(1):67–92, 1973. 9. U. Grenander. General Pattern Theory. Oxford University Press, 1993. 10. U. Grenander and M. I. Miller. Representation of knowledge in complex systems. J. Roy. Statist. Soc. Ser. B, 56:549–603, 1994. 11. S. H. Kang, T. F. Chan, and S. Soatto. Multiple image inpainting. In Proc. of the 3DPVT, Padova, IT, June 2002. 12. D. G. Kendall. Shape manifolds, procrustean metrics and complex projective spaces. Bull. London Math. Soc., 16, 1984. 13. B. Kimia, A. Tannebaum, and S. Zucker. Shapes, shocks, and deformations i: the components of two-dimensional shape and the reaction-diffusion space. Int’l J. Computer Vision, 15:189–224, 1995. 14. R. Kimmel and A. Bruckstein. Tracking level sets by level sets: a method for solving the shape from shading problem. Computer Vision, Graphics and Image Understanding, (62)1:47–58, 1995. 15. R. Kimmel, N. Kiryati, and A. M. Bruckstein. Multivalued distance maps for motion planning on surfaces with moving obstacles. IEEE Trans. Robot. & Autom., 14(3):427–435, 1998. 16. M. Lades, C. Borbruggen, J. Buhmann, J. Lange, C. von der Malsburg, R. Wurtz, and W. Konen. Distortion invariatn object rcognition in the dynamic link architecture. IEEE Trans. on Computers, 42(3):300–311, 1993. 17. H. Le and D. G. Kendall. The riemannian structure of euclidean shape spaces: a novel environment for statistics. The Annals of Statistics, 21(3):1225–1271, 1993. 18. R. Malladi, R. Kimmel, D. Adalsteinsson, V. Caselles G. Sapiro, and J. A. Sethian. A geometric approach to segmentation and analysis of 3d medical images. In Proc. Mathematical Methods in Biomedical Image Analysis Workshop, pages 21–22, 1996. 19. R. Malladi, J. A. Sethian, and B. C. Vemuri. Shape modeling with front propagation: A level set approach. IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(2):158–175, 1995. 20. K. V. Mardia and I. L. Dryden. Shape distributions for landmark data. Adv. appl. prob., 21(4):742–755, 1989. 21. M. I. Miller and L. Younes. Group action, diffeomorphism and matching: a general framework. In Proc. of SCTV, 1999.
62
A. Duci et al.
22. C. Nastar, B. Moghaddam, and A. Pentland. Generalized image matching: Statistical learning of physically-based deformations. In Proceedings of the Fourth European Conference on Computer Vision (ECCV’96), Cambridge, UK, April 1996. 23. S. Osher and J. Sethian. Fronts propagating with curvature-dependent speed: algorithms based on hamilton-jacobi equations. J. of Comp. Physics, 79:12–49, 1988. 24. X. Pennec. Multiple Registration and Mean Rigid Shapes - Application to the 3D case. In I.L. Dryden K.V. Mardia, C.A. Gill, editor, Image Fusion and Shape Variability Techniques (16th Leeds Annual Statistical (LASR) Workshop), pages 178–185, july 1996. 25. Anand Rangarajan, Haili Chui, and Eric Mjolsness. A new distance measure for non-rigid image matching. In Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 237–252, 1999. 26. C. Samson, L. Blanc-Feraud, G. Aubert, and J. Zerubia. A level set model for image classification. In in International Conference on Scale-Space Theories in Computer Vision, pages 306–317, 1999. 27. K. Siddiqi, A. Shokoufandeh, S. Dickinson, and S. Zucker. Shock graphs and shape matching, 1998. 28. P. Thompson and A. W. Toga. A surface-based technique for warping threedimensional images of the brain. IEEE Trans. Med. Imaging, 15(4):402–417, 1996. 29. R. C. Veltkamp and M. Hagedoorn. State of the art in shape matching. Technical Report UU-CS-1999-27, University of Utrecht, 1999. 30. A. Yezzi and S. Soatto. Stereoscopic segmentation. In Proc. of the Intl. Conf. on Computer Vision, pages 59–66, 2001. 31. L. Younes. Computable elastic distances between shapes. SIAM J. of Appl. Math., 1998. 32. A. Yuille. Deformable templates for face recognition. J. of Cognitive Neurosci., 3(1):59–70, 1991. 33. S. Zhu, T. Lee, and A. Yuille. Region competition: Unifying snakes, region growing, energy /bayes/mdl for multi-band image segmentation. In Int. Conf. on Computer Vision, pages 416–423, 1995.
A
Group Action Derivation Details ∂ ∂ g(x)d x = ∇f (y) g(g −1 (y))d y ∂ξi ∂ξi µ ¯ g(¯ µ)
∂ ∂ f (y) g(g −1 (y)), N d s − f (y)∇y · g(g −1 (y)) d y = ∂ξi ∂ξi ∂g(¯ µ) g(¯ µ)
∂ ∂ ∗ −1 f (g(x)) g(x), g N d s + ∇y · g(g (y)) d y = ∂ξi ∂ξi µ g(¯ µ)∩¯ γi ∂ ∂ ∗ ∗ g(x), g N d s + g(x), g N d s =− ∂ξi ∂ξi µ∩g −1 (¯ γi ) ∂(¯ µ∩g −1 (¯ γi )) ∂ = g(x), g ∗ N d s ∂ξi µ ¯ ∩g −1 (γi )
∂W = ∂ξi
∇f (g(x))
What Energy Functions Can Be Minimized via Graph Cuts? Vladimir Kolmogorov and Ramin Zabih Computer Science Department, Cornell University, Ithaca, NY 14853
[email protected],
[email protected]
Abstract. In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper we characterize the energy functions that can be minimized by graph cuts. Our results are restricted to energy functions with binary variables. However, our work generalizes many previous constructions, and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration and scene reconstruction. We present three main results: a necessary condition for any energy function that can be minimized by graph cuts; a sufficient condition for energy functions that can be written as a sum of functions of up to three variables at a time; and a general-purpose construction to minimize such an energy function. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible, and then follow our construction to create the appropriate graph.
1
Introduction and Summary of Results
Many of the problems that arise in early vision can be naturally expressed in terms of energy minimization. The computational task of minimizing the energy is usually quite difficult, as it generally requires minimizing a non-convex function in a space with thousands of dimensions. If the functions have a restricted form they can be solved efficiently using dynamic programming [2]. However, researchers typically have needed to rely on general purpose optimization techniques such as simulated annealing [3,10], which is extremely slow in practice. In the last few years, however, a new approach has been developed based on graph cuts. The basic technique is to construct a specialized graph for the energy function to be minimized, such that the minimum cut on the graph also minimizes the energy (either globally or locally). The minimum cut in turn can be computed very efficiently by max flow algorithms. These methods have been successfully used for a wide variety of vision problems including image restoration [7,8,12,14], stereo and motion [4,7,8,13,16,20,21], voxel occupancy [23], multicamera scene reconstruction [18] and medical imaging [5,6,15]. The output of A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 65–81, 2002. c Springer-Verlag Berlin Heidelberg 2002
66
V. Kolmogorov and R. Zabih
these algorithms is generally a solution with some interesting theoretical quality guarantee. In some cases [7,12,13,14,20] it is the global minimum, in other cases a local minimum in a strong sense [8] that is within a known factor of the global minimum. The experimental results produced by these algorithms are also quite good, as documented in two recent evaluations of stereo algorithms using real imagery with dense ground truth [22,24]. Minimizing an energy function via graph cuts, however, remains a technically difficult problem. Each paper constructs its own graph specifically for its individual energy function, and in some of these cases (especially [8,16,18]) the construction is fairly complex. The goal of this paper is to precisely characterize the class of energy functions that can be minimized via graph cuts, and to give a general-purpose graph construction that minimizes any energy function in this class. Our results play a key role in [18], provide a significant generalization of the energy minimization methods used in [4,5,6,8,12,15,23], and show how to minimize an interesting new class of energy functions. In this paper we only consider energy functions involving binary-valued variables. At first glance this restriction seems severe, since most work with graph cuts considers energy functions that involve variables with more than two possible values. For example, the algorithms presented in [8] for stereo, motion and image restoration use graph cuts to address the standard pixel labeling problem that arises in early vision. In a pixel labeling problem the variables represent individual pixels, and the possible values for an individual variable represent, e.g., its possible displacements or intensities. However, many of the graph cut methods that handle multiple possible values actually consider a pair of labels at a time. Even though we only address binary-valued variables, our results therefore generalize the algorithms given in [4,5,6,8,12,15,23]. As an example, we will show in section 4.1 how to use our results to solve the pixel-labeling problem, even though the pixels have many possible labels. An additional argument in favor of binary-valued variables is that any cut effectively assigns one of two possible values to each node of the graph. So in a certain sense any energy minimization construction based on graph cuts relies on intermediate binary variables. 1.1
Summary of Our Results
In this paper we consider two classes of energy functions. Let {x1 , . . . , xn }, xi ∈ {0, 1} be a set of binary-valued variables. We define the class F 2 to be functions that can be written as a sum of functions of up to 2 variables at a time, E i (xi ) + E i,j (xi , xj ). (1) E(x1 , . . . , xn ) = i
i<j
We define the class F 3 to be functions that can be written as a sum of functions of up to 3 variables at a time, E(x1 , . . . , xn ) = E i (xi ) + E i,j (xi , xj ) + E i,j,k (xi , xj , xk ). (2) i
i<j
i<j
What Energy Functions Can Be Minimized via Graph Cuts?
67
Obviously, the class F 2 is a strict subset of the class F 3 . The main result in this paper is a precise characterization of the functions in F 3 that can be minimized using graph cuts, together with a graph construction for minimizing such functions. Moreover, we give a necessary condition for all other classes which must be met for a function to be minimized via graph cuts. Our results also identify an interesting class of class of energy functions that have not yet been minimized using graph cuts. All of the previous work with graph cuts involves a neighborhood system that is defined on pairs of pixels. In the language of Markov Random Fields [10,19], these methods consider firstorder MRF’s. The associated energy functions lie in F 2 . Our results allow for the minimization of energy functions in the larger class F 3 , and thus for neighborhood systems involve triples of pixels. 1.2
Organization
The rest of the paper is organized as follows. In section 2 we give an overview of graph cuts. In section 3 we formalize the problem that we want to solve. Section 4 contains our main theorem for the class of functions F 2 and shows how it can be used. Section 5 contains our main theorems for other classes. Proofs of our theorems, together with the graph constructions, are deferred to section 6, with some additional details deferred to a technical report [17]. A summary of the actual graph constructions os given in the appendix.
2
Overview of Graph Cuts
Suppose G = (V, E) is a directed graph with two special vertices (terminals), namely the source s and the sink t. An s-t-cut (or just a cut as we will refer to it later) C = S, T is a partition of vertices in V into two disjoint sets S and T , such that s ∈ S and t ∈ T . The cost of the cut is the cut is the sum of costs of all edges that go from S to T : c(u, v). c(S, T ) = u∈S,v∈T,(u,v)∈E
The minimum s-t-cut problem is to find a cut C with the smallest cost. Due to the theorem of Ford and Fulkerson [9] this is equivalent to computing the maximum flow from the source to sink. There are many algorithms which solve this problem in polynomial time with small constants [1,11]. It is convenient to denote a cut C = S, T by a labeling f mapping from the set of the nodes V − {s, t} to {0, 1} where f (v) = 0 means that v ∈ S, and f (v) = 1 means that v ∈ T . We will use this notation later.
3
Defining Graph Representability
Let us consider a graph G = (V, E) with terminals s and t, thus V = {v1 , . . . , vn , s, t}. Each cut on G has some cost; therefore, G represents the energy
68
V. Kolmogorov and R. Zabih
function mapping from all cuts on G to the set of nonnegative real numbers. Any cut can be described by n binary variables x1 , . . . , xn corresponding to nodes in G (excluding the source and the sink): xi = 0 when vi ∈ S, and xi = 1 when vi ∈ T . Therefore, the energy E that G represents can be viewed as a function of n binary variables: E(x1 , . . . , xn ) is equal to the cost of the cut defined by the configuration x1 , . . . , xn (xi ∈ {0, 1}). Note that the configuration that minimizes E will not change if we add a constant to E. We can efficiently minimize E by computing the minimum s-t-cut on G. This naturally leads to the question: what is the class of energy functions E for which we can construct a graph that represents E? We can also generalize our construction. Above we used each node (except the source and the sink) for encoding one binary variable. Instead we can specify a subset V0 = {v1 , . . . , vk } ⊂ V − {s, t} and introduce variables only for the nodes in this set. Then there may be several cuts corresponding to a configuration x1 , . . . , xk . If we define the energy E(x1 , . . . , xk ) as the minimum among the costs of all such cuts, then the minimum s-t-cut on G will again yield the configuration which minimizes E. We will summarize graph constructions that we allow in the following definition. Definition 1. A function E of n binary variables is called graph-representable if there exists a graph G = (V, E) with terminals s and t and a subset of nodes V0 = {v1 , . . . , vn } ⊂ V −{s, t} such that for any configuration x1 , . . . , xn the value of the energy E(x1 , . . . , xn ) is equal to a constant plus the cost of the minimum s-t-cut among all cuts C = S, T in which vi ∈ S, if xi = 0, and vi ∈ T , if xi = 1 (1 ≤ i ≤ n). We say that E is exactly represented by G, V0 if this constant is zero. The following lemma is an obvious consequence of this definition. Lemma 2. Suppose the energy function E is graph-representable by a graph G and a subset V0 . Then it is possible to find the exact minimum of E in polynomial time by computing the minimum s-t-cut on G. In this paper we will give a complete characterization of the classes F 2 and F in terms of graph representability, and show how to construct graphs for minimizing graph-representable energies within these classes. Moreover, we will give a necessary condition for all other classes which must be met for a function to be graph-representable. Note that it would be suffice to consider only the class F 3 since F 2 ⊂ F 3 . However, the condition for F 2 is simpler so we will consider it separately. 3
4
The Class F 2
Our main result for the class F 2 is the following theorem.
What Energy Functions Can Be Minimized via Graph Cuts?
69
Theorem 3. Let E be a function of n binary variables from the class F 2 , i.e. it can be written as the sum E(x1 , . . . , xn ) = E i (xi ) + E i,j (xi , xj ). i
i<j
Then E is graph-representable if and only if each term E i,j satisfies the inequality E i,j (0, 0) + E i,j (1, 1) ≤ E i,j (0, 1) + E i,j (1, 0).
4.1
Example: Pixel-Labeling via Expansion Moves
In this section we show how to apply this theorem to solve the pixel-labeling problem. In this problem, are given the set of pixels P and the set of labels L. The goal is to find a labeling l (i.e. a mapping from the set of pixels to the set of labels) which minimizes the energy E(l) = Dp (lp ) + Vp,q (lp , lq ) p∈P
p,q∈N
where N ⊂ P × P is a neighborhood system on pixels. Without loss of generality we can assume that N contains only ordered pairs p, q for which p < q (since we can combine two terms Vp,q and Vq,p into one term). We will show how our method can be used to derive the expansion move algorithm developed in [8]. This problem is shown in [8] to be NP-hard if |L| > 2. [8] gives an approximation algorithm for minimizing this energy. A single step of this algorithm is an operation called an α-expansion. Suppose that we have some current configuration l0 , and we are considering a label α ∈ L. During the α-expansion operation a pixel p is allowed either to keep its old label lp0 or to switch to a new label α: lp = lp0 or lp = α. The key step in the approximation algorithm presented in [8] is to find the optimal expansion operation, i.e. the one that leads to the largest reduction in the energy E. This step is repeated until there is no choice of α where the optimal expansion operation reduces the energy. [8] constructs a graph which contains nodes corresponding to pixels in P. The following encoding is used: if f (p) = 0 (i.e., the node p is in the source set) then lp = lp0 ; if f (p) = 1 (i.e., the node p is in the sink set) then lp = α. Note that the key technical step in this algorithm can be naturally expressed as minimizing an energy function involving binary variables. The binary variables correspond to pixels, and the energy we wish to minimize can be written formally as Dp (lp (xp )) + Vp,q (lp (xp ), lq (xq )), (3) E(xp1 , . . . , xpn ) = p∈P
p,q∈N
where
∀p ∈ P
lp (xp ) =
lp0 , α,
xp = 0 xp = 1.
70
V. Kolmogorov and R. Zabih
We can demonstrate the power of our results by deriving an important restriction on this algorithm. In order for the graph cut construction of [8] to work, the function Vp,q is required to be a metric. In their paper, it is not clear whether this is an accidental property of the construction (i.e., they leave open the possibility that a more clever graph cut construction may overcome this restriction). Using our results, we can easily show this is not the case. Specifically, by theorem 1, the energy function given in equation 3 is graph-representable if and only if each term Vp,q satisfies the inequality Vp,q (lp (0), lq (0)) + Vp,q (lp (1), lq (1)) ≤ Vp,q (lp (0), lq (1)) + Vp,q (lp (1), lq (0)) or
Vp,q (β, γ) + Vp,q (α, α) ≤ Vp,q (β, α) + Vp,q (α, γ)
where β = lp0 , γ = lq0 . If Vp,q (α, α) = 0, then this is the triangle inequality: Vp,q (β, γ) ≤ Vp,q (β, α) + Vp,q (α, γ) This is exactly the constraint on Vp,q that was given in [8].
5
More General Classes of Energy Functions
We begin with several definitions. Suppose we have a function E of n binary variables. If we fix m of these variables then we get a new function E of n − m binary variables; we will call this function a projection of E. The notation for projections is as follows. Definition 4. Let E(x1 , . . . , xn ) be a function of n binary variables, and let I, J be a disjoint partition of the set of indices {1, . . . , n}: I = {i(1), . . . , i(m)}, J = {j(1), . . . , j(n − m)}. Let αi(1) , . . . , αi(m) be some binary constants. A projection E = E[xi(1) = αi(1) , . . . , xi(m) = αi(m) ] is a function of n − m variables defined by E (xj(1) , . . . , xj(n−m) ) = E(x1 , . . . , xn ), where xi = αi for i ∈ I. We say that we fix variables xi(1) , . . ., xi(m) . Now we give a definition of regular functions. Definition 5. • All functions of one variable are regular. • A function E of two variables is called regular if E(0, 0)+E(1, 1) ≤ E(0, 1)+ E(1, 0). • A function E of more than two variables is called regular if all projections of E of two variables are regular. Now we are ready to formulate our main theorem for F 3 .
What Energy Functions Can Be Minimized via Graph Cuts?
71
Theorem 6. Let E be a function of n binary variables from F 3 , i.e. it can be written as the sum E i (xi ) + E i,j (xi , xj ) + E i,j,k (xi , xj , xk ). E(x1 , . . . , xn ) = i
i<j
i<j
Then E is graph-representable if and only if E is regular. Finally, we give a necessary condition for all other classes. Theorem 7. Let E be a function of binary variables. If E is not regular then E is not graph-representable.
6
Proofs
6.1
Basic Lemmas
Definition 8. The functional π will be a mapping from the set of all functions (of binary variables) to the set of real numbers which is defined as follows. For a function E(x1 , . . . , xn ) n (Πi=1 (−1)xi ) E(x1 , . . . , xn ). π(E) = x1 ∈{0,1},...,xn ∈{0,1}
For example, for a function E of two variables π(E) = E(0, 0) − E(0, 1) − E(1, 0) + E(1, 1). Note that a function E of two variables is regular if and only if π(E) ≤ 0. It is trivial to check the following properties of π. Lemma 9. • π is linear, i.e. for a scalar c and two functions E , E of n variables π(E + E ) = π(E ) + π(E ) and π(c · E ) = c · π(E ). • If E is a function of n variables that does not depend on at least one of the variables then π(E) = 0. The next two lemmas provide “building blocks” for constructing graphs for complex functions. Lemma 10. Let I = {1, . . . , n}, I = {i (1), . . . , i (n )} ⊂ I, I = {i (1), . . . , i (n )} ⊂ I be sets of indices. If the functions E (xi (1) , . . . , xi (n ) ) and E (xi (1) , . . . , xi (n ) ) are graph-representable, then so is the function E(x1 , . . . , xn ) = E (xi (1) , . . . , xi (n ) ) + E (xi (1) , . . . , xi (n ) ).
72
V. Kolmogorov and R. Zabih
Proof. Let us assume for simplicity of notation that E and E are functions of all n variables: E = E (x1 , . . . , xn ), E = E (α1 , . . . , αn ). By the definition of graph respresentability, there exist constants K , K , graphs G = (V , E ), G = (V , E ) and the set V0 = {v1 , . . . , vn }, V0 ⊂ V − {s, t}, V0 ⊂ V − {s, t} such that E + K is exactly represented by G , V0 and E + K is exactly represented by G , V0 . We can assume that the only common nodes of G and G are V0 ∪ {s, t}. Let us construct the graph G = (V, E) as the combined graph of G and G : V = V ∪ V , E = E ∪ E . It is rather straightforward to show that G, V0 exactly represent E+(K +K ) (and, therefore, E is graph-representable). Due to space limitations, the proof is omitted but is contained in a technical report [17]. Lemma 11. Suppose E and E are two functions of n variables such that xk = 0 E(x1 , . . . , xn ), E (x1 , . . . , xn ) = ∀x1 , . . . , xn E(x1 , . . . , xn ) + C, xk = 1, for some constants k and C (1 ≤ k ≤ n). Then • E if graph-representable if and only if E is graph-representable; • E is regular if and only if E is regular. Proof. Let us introduce the following function E C : 0, C E (x1 , . . . , xn ) = ∀x1 , . . . , xn C,
xk = 0 xk = 1.
We need to show that E C is graph-representable for any C then the first part of the lemma will follow from the lemma 3 since E ≡ E +E C and E ≡ E +E −C . It is easy to construct a graph which represents E C . The set of nodes in this graph will be {v1 , . . . , vn , s, t} and the set of edges will include the only edge (s, vk ) with the capacity C (if C ≥ 0) or the edge (vk , t) with the capacity −C (if C < 0). It is trivial to check that this graph exactly represents E C (in the former case) or E C + C (in the latter case). Now let us assume that one of the functions E and E is regular, for example, E. Consider a projection of E of two variables: E [xi(1) = αi(1) , . . . , xi(m) = αi(m) ], where m = n − 2 and {i(1), . . . , i(m)} ⊂ {1, . . . , n}. We need to show that this function is regular, i.e. that the functional π of this function is nonpositive. Due to the linearity of π we can write π(E [xi(1) = αi(1) , . . . , xi(m) = αi(m) ]) = = π(E[xi(1) = αi(1) , . . . , xi(m) = αi(m) ])
+
+ π(E C [xi(1) = αi(1) , . . . , xi(m) = αi(m) ]). The first term is nonpositive by assumption, and the second term is 0 by lemma 2.
What Energy Functions Can Be Minimized via Graph Cuts?
6.2
73
Proof of Theorems 1 and 2: The Constructive Part
In this section we will give the constructive part of the proof: given a regular energy function from class F 3 we will show how to construct a graph which represents it. We will do it in three steps. First we will consider regular functions of two variables, then regular functions of three variables and finally regular functions of the form as in the theorem 2. This will also prove the constructive part of the theorem 1. Indeed, suppose a function is from the class F 2 and each term in the sum satisfies the condition given in the theorem 1 (i.e. regular). Then each term is graph-representable (as we will show in this section) and, hence, the function is graph-representable as well according to the lemma 3. The other direction of theorems 1 and 2 as well as the theorem 3 will be proven in the section 6.3. Functions of two variables. Let E(x1 , x2 ) be a function of two variables represented by a table E=
E(0, 0) E(0, 1) E(1, 0) E(1, 1)
Lemma 4 tells us that we can add a constant to any column or row without affecting theorem 2. Thus, without loss of generality we can consider only functions E of the form E=
0A 0 0
(we subtracted a constant from the first row to make the upper left element zero, then we subtracted a constant from the second row to make the bottom left element zero, and finally we subtracted a constant from the second column to make the bottom right element zero). π(E) = −A ≤ 0 since we assumed that E is regular; hence, A is non-negative. Now we can easily construct a graph G which represents this function. It will have four vertices V = {v1 , v2 , s, t} and one edge E = {(v1 , v2 )} with the cost c(v1 , v2 ) = A. It is easy to see that G, V0 = {v1 , v2 } represent E since the only case when the edge (v1 , v2 ) is cut (yielding a cost A) is when v1 ∈ S, v2 ∈ T , i.e. when x1 = 0, x2 = 1. Note that we did not introduce any additional nodes for representing binary interactions of binary variables. This is in contrast to the construction in [8] which added auxiliary nodes for representing energies that we just considered. Our construction yields a smaller graph and, thus, the minimum cut can potentially be computed faster. Functions of three variables. Now let us consider a regular function E of three variables. Let us represent it as a table
74
V. Kolmogorov and R. Zabih
E(0, 0, 0) E(0, 0, 1) E(0, 1, 0) E(0, 1, 1) E= E(1, 0, 0) E(1, 0, 1) E(1, 1, 0) E(1, 1, 1) Two cases are possible: Case 1. π(E) ≥ 0. We can apply transformations described in lemma 4 and get the following function: 0 0 E= 0 A3
0 A1 A2 A0
It is easy to check that these transformations preserve the functional π. Hence, A = A0 − (A1 + A2 + A3 ) = −π(E) ≤ 0. By applying the regularity constraint to the projections E[x1 = 0], E[x2 = 0], E[x3 = 0] we also get A1 ≤ 0, A2 ≤ 0, A3 ≤ 0. We can represent E as the sum of functions 0 0 0 0 0 0 0 0 0 A1 0 0 0 0 0 0 + + + E= 0 0 0 A2 0 0 0 0 0 A1 0 A2 A3 A3 0A We need to show that all terms here are graph-representable, then lemma 3 will imply that E is graph-representable as well. The first three terms are regular functions depending only on two variables and thus are graph-representable as was shown in the previous section. Let us consider the last term. The graph G that represents this term can be constructed as follows. The set of nodes will contain one auxilary node u: V = {v1 , v2 , v3 , u, s, t}. The set of edges will consist of directed edges E = {(v1 , u), (v2 , u), (v3 , u), (u, t)} with capacities A = −A. It is easy to check that G, V0 = {v1 , v2 , v3 } exactly represent the function E (x1 , x2 , x3 ) = E(x1 , x2 , x3 ) + A ; the proof is contained in [17]. Case 2. π(E) < 0. This case is similar to the case 1. We can transform the energy to A0 A E= 2 A1 0
A3 A1 0 A2 0 A3 A3 A0 0 0 0 A2 0 0 0 0 0 = + + + 0 A1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
where A = A0 − (A1 + A2 + A3 ) = π(E) < 0 and A1 ≤ 0, A2 ≤ 0, A3 ≤ 0 since E is regular. The first three terms are regular functions of two variables and the last term can be represented by the graph G = (V, E) where V = {v1 , v2 , v3 , u, s, t} and E = {(u, v1 ), (u, v2 ), (u, v3 ), (s, u)}; capacities of all edges are −A.
What Energy Functions Can Be Minimized via Graph Cuts?
75
Functions of many variables. Finally let us consider a regular function E which can be written as E i,j,k (xi , xj , xk ), E(x1 , . . . , xn ) = i<j
where i, j, k are indices from the set {1, . . . , n} (we omitted terms involving functions of one and two variables since they can be viewed as functions of three variables). Although E is regular, each term in the sum need not necessarily be regular. However we can “regroup” terms in the sum so that each term will be regular (and, thus, graph-representable). This can be done using the following lemma and a trivial induction argument. Definition 12. Let E i,j,k be a function of three variables. The functional N (E i,j,k ) is defined as the number of projections of two variables of E i,j,k with the positive value of the functional π. Note that N (E i,j,k ) = 0 exactly when E i,j,k is regular. Lemma 13. Suppose the function E of n variables can be written as E i,j,k (xi , xj , xk ), E(x1 , . . . , xn ) = i<j
where some of the terms are not regular. Then it can be written as ˜ i,j,k (xi , xj , xk ), E E(x1 , . . . , xn ) = i<j
where
˜ i,j,k ) < N (E
i<j
N (E i,j,k ).
i<j
Proof. For the simplicity of notation let us assume that the term E 1,2,3 is not regular and π(E 1,2,3 [x3 = 0]) > 0 or π(E 1,2,3 [x3 = 1]) > 0 (we can ensure this by renaming indices). Let Ck =
max π(E 1,2,k [xk = αk ])
αk ∈{0,1}
C3 = −
n
k ∈ {4, . . . , n}
Ck
k=4
Now we will modify the terms E 1,2,3 , . . ., E 1,2,n as follows: ˜ 1,2,k ≡ E 1,2,k − R[Ck ] E
k ∈ {3, . . . , n}
where R[C] is the function of two variables x1 and x2 defined by the table R[C] =
0 0 0C
76
V. Kolmogorov and R. Zabih
˜ i,j,k ≡ E i,j,k , (i, j) = (1, 2)). We have (other terms are unchanged: E ˜ i,j,k (xi , xj , xk ) E E(x1 , . . . , xn ) = n
i<j
n
since k=3 Ck = 0 and k=3 R[Ck ] ≡ 0. If we consider R[C] as a function of n variables and take a projection of two variables where the two variables that are not fixed are xi and xj (i < j), then the functional π will be C, if (i, j) = (1, 2), and 0 otherwise since in the latter case a projection actually depends on at most one variable. Hence, the only projections of two variables that could have changed their value of the ˜ 1,2,k ˜ 1,2,k [x3 = α3 , . . . , xn = αn ], k ∈ {3, . . . , n}, if we treat E functional π are E 1,2,k 1,2,k ˜ ˜ as functions of n variables, or E [xk = αk ], if we treat E as functions of three variables. First let us consider terms with k ∈ {4, . . . , n}. We have π(E 1,2,k [xk = αk ]) ≤ Ck , thus ˜ 1,2,k [xk = αk ]) = π(E 1,2,k [xk = αk ]) − π(R[Ck ][xk = αk ]) ≤ Ck − Ck = 0 π(E Therefore we did not introduce any nonregular projections for these terms. ˜ 1,2,3 [x3 = α3 ]). We can write Now let us consider the term π(E ˜ 1,2,3 [x3 = α3 ]) = π(E 1,2,3 [x3 = α3 ]) − π(R[C3 ][x3 = α3 ]) = π(E n n 1,2,3 [x3 = α3 ]) − (− Ck ) = π(E 1,2,k [xk = αk ]) = π(E k=4
k=3
where αk = arg maxα∈{0,1} π(E 1,2,k [xk = α]), k ∈ {4, . . . , n}. The last expression is just π(E[x3 = α3 , . . . , xn = αn ]) and is nonpositive since E is regular by ˜ 1,2,3 [x3 = 1]) are both ˜ 1,2,3 [x3 = 0]) and π(E assumption. Hence, values π(E nonpositive and, therefore, the number of nonregular projections has decreased. 6.3
Proof of Theorem 3
In this section we will prove a necessary condition for graph representability: if a function of binary variables is graph-representable then it is regular. It will also imply the corresponding directions of the theorems 1 and 2. Note that theorem 1 needs a little bit of reasoning, as follows. Let us consider a graph-representable function E from the class F 2 : E(x1 , . . . , xn ) = E i (xi ) + E i,j (xi , xj ) i
i<j
E is regular as we will prove in this section. It means that the functional π of any projection of E of two variables is nonpositive. Let us consider a projection where the two variables that are not fixed are xi and xj . By lemma 2 the value of the functional π of this projection is equal to π(E i,j ) (all other terms yield zero). Hence, all terms E i,j are regular, i.e. they satisfy the condition in the theorem 1.
What Energy Functions Can Be Minimized via Graph Cuts?
77
Definition 14. Let G = (V, E) be a graph, v1 , . . . , vk be a subset of nodes V and α1 , . . . , αk be binary constants whose values are from {0, 1}. We will define the graph G[x1 = α1 , . . . , xk = αk ] as follows. Its nodes will be the same as in G and its edges will be all edges of G plus additional edges corresponding to nodes v1 , . . . , vk : for a node vi , we add the edge (s, vi ), if αi = 0, or (vi , t), if αi = 1, with an infinite capacity. It should be obvious that these edges enforce constraints f (v1 ) = α1 , . . ., f (vk ) = αk in the minimum cut on G[x1 = α1 , . . . , xk = αk ], i.e. if αi = 0 then vi ∈ S, and if αi = 1 then vi ∈ T . (If, for example, αi = 0 and vi ∈ T then the edge (s, vi ) must be cut yielding an infinite cost, so it would not the minimum cut.) Now we can give a definition of graph representability which is equivalent to the definition 1. This new definition will be more convenient for the proof. Definition 15. We say that the function E of n binary variables is exactly represented by the graph G = (V, E) and the set V0 ⊂ V if for any configuration α1 , . . . , αn the cost of the minimum cut on G[x1 = α1 , . . . , xk = αk ] is E(α1 , . . . , αn ). Lemma 16. Any projection of a graph-representable function is graphrepresentable. Proof. Let E be a graph-representable function of n variables, and the graph G = (V, E) and the set V0 represents E. Suppose that we fix variables xi(1) , . . . , xi(m) . It is straightforward to check that the graph G[xi(1) = αi(1) , . . . , xi(m) = αi(m) ] and the set V0 = V0 − {vi(1) , . . . , vi(m) } represent the function E = E[xi(1) = αi(1) , . . . , xi(m) = αi(m) ]. This lemma implies that it suffices to prove theorem 3 only for energies of two variables. Let E(x1 , x2 ) be a graph-representable function of two variables. Let us represent this function as a table: E=
E(0, 0) E(0, 1) E(1, 0) E(1, 1)
Lemma 4 tells us that we can add a constant to any column or row without affecting theorem 3. Thus, without loss of generality we can consider only functions E of the form E=
0 0 0A
(we subtracted a constant from the first row to make the upper left element zero, then we subtracted a constant from the second row to make the bottom left element zero, and finally we subtracted a constant from the second column to make the upper right element zero).
78
V. Kolmogorov and R. Zabih
We need to show that E is regular, i.e. that π(E) = A ≤ 0. Suppose this is not true: A > 0. Suppose the graph G and the set V0 = {v1 , v2 } represent E. It means that there is a constant K such that G, V0 exactly represent E (x1 , x2 ) = E(x1 , x2 ) + K: E =
K K K K +A
The cost of the minimum s-t-cut on G is K (since this cost is just the minimum entry in the table for E ); hence, K ≥ 0. Thus the value of the maximum flow from s to t in G is K. Let G 0 be the residual graph obtained from G after pushing the flow K. Let E 0 (x1 , x2 ) be the function exactly represented by G 0 , V0 . By the definition of graph representability, E (α1 , α2 ) is equal to the value of the minimum cut (or maximum flow) on the graph G[x1 = α1 , x2 = α2 ]. The following sequence of operations shows one possible way to push the maximum flow through this graph. • First we take the original graph G and push the flow K; then we get the residual graph G 0 . (It is equivalent to pushing flow through G[x1 = α1 , x2 = α2 ] where we do not use edges corresponding to constraints x1 = α1 and x2 = α2 ). • Then we add edges corresponding to these constraints; then we get the graph G 0 [x1 = α1 , x2 = α2 ]. • Finally we push the maximum flow possible through the graph G 0 [x1 = α1 , x2 = α2 ]; the amount of this flow is E 0 (α1 , α2 ) according to the definition of graph representability. The total amount of flow pushed during all steps is K + E 0 (α1 , α2 ); thus, E (α1 , α2 ) = K + E 0 (α1 , α2 ) or
E(α1 , α2 ) = E 0 (α1 , α2 )
We proved that E is exactly represented by G 0 , V0 . The value of the minimum cut/maximum flow on G 0 is 0 (it is the minimum entry in the table for E); thus, there is no augmenting path from s to t in G 0 . However, if we add edges (v1 , t) and (v2 , t) then there will be an augmenting path from s to t in G 0 [x1 = α1 , x2 = α2 ] since E(1, 1) = A > 0. Hence, this augmenting path will contain at least one of these edges and, therefore, either v1 or v2 will be in the path. Let P be the part of this path going from the source until v1 or v2 is first encountered. Without loss of generality we can assume that it will be v1 . Thus, P is an augmenting path from s to v1 which does not contain edges that we added, namely (v1 , t) and (v2 , t). Finally let us consider the graph G 0 [x1 = 1, x2 = 0] which is obtained from 0 G by adding edges (v1 , t) and (s, v2 ) with infinite capacities. There is an augmenting path {P, (v1 , t)} from the source to the sink in this graph; hence, the minimum cut/maximum flow on it greater than zero, or E(1, 0) > 0. We get a contradiction.
What Energy Functions Can Be Minimized via Graph Cuts?
79
Acknowledgements. We thank Olga Veksler and Yuri Boykov for their careful reading of this paper, and for valuable comments which greatly improved its readibility. We also thank Ian Jermyn for helping us clarify the paper’s motivation. This research was supported by NSF grants IIS-9900115 and CCR-0113371, and by a grant from Microsoft Research.
Appendix: Summary of Graph Constructions We now summarize the graph constructions used for regular functions. The notation D(v, c) means that we add an edge (s, v) with the weight c if c > 0, or an edge (v, t) with the weight −c if c < 0. Regular Functions of One Binary Variable Recall that all functions of one variable are regular. For a function E(x1 ), we construct a graph G with three vertices V = {v1 , s, t}. There is a single edge D(v1 , E(1) − E(0)). Regular Functions of Two Binary Variables We now show how to construct a graph G for a regular function E(x1 , x2 ) of two variables. It will contain four vertices: V = {v1 , v2 , s, t}. The edges E are given below. • D(v1 , E(1, 0) − E(0, 0)); • D(v2 , E(1, 1) − E(1, 0)); • (v1 , v2 ) with the weight −π(E). Regular Functions of Three Binary Variables We next show how to construct a graph G for a regular function E(x1 , x2 , x3 ) of three variables. It will contain five vertices: V = {v1 , v2 , v3 , u, s, t}. If π(E) ≥ 0 then the edges are • • • • • • •
D(v1 , E(1, 0, 1) − E(0, 0, 1)); D(v2 , E(1, 1, 0) − E(1, 0, 0)); D(v3 , E(0, 1, 1) − E(0, 1, 0)); (v2 , v3 ) with the weight −π(E[x1 = 0]); (v3 , v1 ) with the weight −π(E[x2 = 0]); (v1 , v2 ) with the weight −π(E[x3 = 0]); (v1 , u), (v2 , u), (v3 , u), (u, t) with the weight π(E).
If π(E) < 0 then the edges are • • • • • • •
D(v1 , E(1, 1, 0) − E(0, 1, 0)); D(v2 , E(0, 1, 1) − E(0, 0, 1)); D(v3 , E(1, 0, 1) − E(1, 0, 0)); (v3 , v2 ) with the weight −π(E[x1 = 1]); (v1 , v3 ) with the weight −π(E[x2 = 1]); (v2 , v1 ) with the weight −π(E[x3 = 1]); (u, v1 ), (u, v2 ), (u, v3 ), (s, u) with the weight −π(E).
80
V. Kolmogorov and R. Zabih
References 1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. 2. Amir Amini, Terry Weymouth, and Ramesh Jain. Using dynamic programming for solving variational problems in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(9):855–867, September 1990. 3. Stephen Barnard. Stochastic stereo matching over scale. International Journal of Computer Vision, 3(1):17–32, 1989. 4. S. Birchfield and C. Tomasi. Multiway cut for stereo and motion with slanted surfaces. In International Conference on Computer Vision, pages 489–495, 1999. 5. Yuri Boykov and Marie-Pierre Jolly. Interactive organ segmentation using graph cuts. In Medical Image Computing and Computer-Assisted Intervention, pages 276–286, 2000. 6. Yuri Boykov and Marie-Pierre Jolly. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. In International Conference on Computer Vision, pages I: 105–112, 2001. 7. Yuri Boykov, Olga Veksler, and Ramin Zabih. Markov Random Fields with efficient approximations. In IEEE Conference on Computer Vision and Pattern Recognition, pages 648–655, 1998. 8. Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222–1239, November 2001. 9. L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962. 10. S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721–741, 1984. 11. A. Goldberg and R. Tarjan. A new approach to the maximum flow problem. Journal of the Association for Computing Machinery, 35(4):921–940, October 1988. 12. D. Greig, B. Porteous, and A. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, 51(2):271–279, 1989. 13. H. Ishikawa and D. Geiger. Occlusions, discontinuities, and epipolar lines in stereo. In European Conference on Computer Vision, pages 232–248, 1998. 14. H. Ishikawa and D. Geiger. Segmentation by grouping junctions. In IEEE Conference on Computer Vision and Pattern Recognition, pages 125–131, 1998. 15. Junmo Kim, John Fish, Andy Tsai, Cindy Wible, Ala Willsky, and William Wells. Incorporating spatial priors into an information theoretic approach for fMRI data analysis. In Medical Image Computing and Computer-Assisted Intervention, pages 62–71, 2000. 16. Vladimir Kolmogorov and Ramin Zabih. Visual correspondence with occlusions using graph cuts. In International Conference on Computer Vision, pages 508–515, 2001. 17. Vladimir Kolmogorov and Ramin Zabih. What energy functions can be minimized via graph cuts? Technical report CUCS-TR2001-1857, Cornell Computer Science Department, November 2001. 18. Vladimir Kolmogorov and Ramin Zabih. Multi-camera scene reconstruction via graph cuts. In European Conference on Computer Vision, 2002. 19. S. Li. Markov Random Field Modeling in Computer Vision. Springer-Verlag, 1995.
What Energy Functions Can Be Minimized via Graph Cuts?
81
20. S. Roy. Stereo without epipolar lines: A maximum flow formulation. International Journal of Computer Vision, 1(2):1–15, 1999. 21. S. Roy and I. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In International Conference on Computer Vision, 1998. 22. Daniel Scharstein and Richard Szeliski. A taxonomy and evaluation of dense twoframe stereo correspondence algorithms. Technical Report 81, Microsoft Research, 2001. To appear in IJCV. An earlier version appears in CVPR 2001 Workshop on Stereo Vision. 23. Dan Snow, Paul Viola, and Ramin Zabih. Exact voxel occupancy with graph cuts. In IEEE Conference on Computer Vision and Pattern Recognition, pages 345–352, 2000. 24. Richard Szeliski and Ramin Zabih. An experimental comparison of stereo algorithms. In B. Triggs, A. Zisserman, and R. Szeliski, editors, Vision Algorithms: Theory and Practice, number 1883 in LNCS, pages 1–19, Corfu, Greece, September 1999. Springer-Verlag.
Multi-camera Scene Reconstruction via Graph Cuts Vladimir Kolmogorov and Ramin Zabih Computer Science Department, Cornell University, Ithaca, NY 14853
[email protected],
[email protected]
Abstract. We address the problem of computing the 3-dimensional shape of an arbitrary scene from a set of images taken at known viewpoints. Multi-camera scene reconstruction is a natural generalization of the stereo matching problem. However, it is much more difficult than stereo, primarily due to the difficulty of reasoning about visibility. In this paper, we take an approach that has yielded excellent results for stereo, namely energy minimization via graph cuts. We first give an energy minimization formulation of the multi-camera scene reconstruction problem. The energy that we minimize treats the input images symmetrically, handles visibility properly, and imposes spatial smoothness while preserving discontinuities. As the energy function is NP-hard to minimize exactly, we give a graph cut algorithm that computes a local minimum in a strong sense. We handle all camera configurations where voxel coloring can be used, which is a large and natural class. Experimental data demonstrates the effectiveness of our approach.
1
Introduction
Reconstructing an object’s 3-dimensional shape from a set of cameras is a classic vision problem. In the last few years, it has attracted a great deal of interest, partly due to a number of new applications both in vision and in graphics that require good reconstructions. While the problem can be viewed as a natural generalization of stereo, it is considerably harder. The major reason for this is the difficulty of reasoning about visibility. In stereo matching, most scene elements are visible from both cameras, and it is possible to obtain good results without addressing visibility constraints. In the more general scene reconstruction problem, however, very few scene elements are visible from every camera, so the issue of visibility cannot be ignored. In this paper, we approach the scene reconstruction problem from the point of view of energy minimization. Energy minimization has several theoretical advantages, but has generally been viewed as too slow for early vision to be practical. Our approach is motivated by some recent work in early vision, where fast energy minimization algorithms have been developed based on graph cuts [6,7,12,14,20,21]. These methods give strong experimental results in practice, as documented in two recent evaluations of stereo algorithms using real imagery with dense ground truth [22,27]. A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 82–96, 2002. c Springer-Verlag Berlin Heidelberg 2002
Multi-camera Scene Reconstruction via Graph Cuts
83
The energy that we minimize has three important properties: – it treats the input images symmetrically, – it handles visibility properly, and – it imposes spatial smoothness while also preserving discontinuities. We begin with a review of related work. In section 3 we give a precise definition of the problem that we wish to solve, and define the energy that we will minimize. Section 4 describes how we use graph cuts to compute a strong local minimum of this energy. Experimental data is presented in section 5. Some details of the graph cut construction are deferred to the appendix, along with a proof that computing the global minimum of the energy is NP-hard.
2
Related Work
The problem of reconstructing a scene from multiple cameras has received a great deal of attention in the last few years. One extensively-explored approach to this problem is voxel occupancy. In voxel occupancy [18,25] the scene is represented as a set of 3-dimensional voxels, and the task is to label the individual voxels as filled or empty. Voxel occupancy is typically solved using silhouette intersection, usually from multiple cameras but sometimes from a single camera with the object placed on a turntable [8]. It is known that the output of silhouette intersection even without noise is not the actual 3-dimensional shape, but rather an approximation called the visual hull [17]. 2.1
Voxel Coloring and Space Carving
Voxel occupancy, however, fails to exploit the consistent appearance of a scene element between different cameras. This constraint, called photo-consistency, is obviously quite powerful. Two well-known recent algorithms that have used photo-consistency are voxel coloring [23] and space carving [16]. Voxel coloring makes a single pass through voxel space, first computing the visibility of each voxel and then its color. There is a constraint on the camera geometry, namely that no scene point is allowed to be within the convex hull of the camera centers. As we will see in section 3, our approach handles all the camera configurations where voxel coloring can be used. Space carving is another voxel-oriented approach that uses the photo-consistency constraint to prune away empty voxels from the volume. Space carving has the advantage of allowing arbitrary camera geometry. One major limitation of voxel coloring and space carving is that they lack a way of imposing spatial coherence. This is particularly problematic because the image data is almost always ambiguous. Another (related) limitation comes from the fact that these methods traverse the volume making “hard” decisions concerning the occupancy of each voxel they analyze. Because the data is ambiguous, such a decision can easily be incorrect, and there is no easy way to undo such a decision later on.
84
2.2
V. Kolmogorov and R. Zabih
Energy Minimization Approaches
Our approach to the scene reconstruction problem is to generalize some recently developed techniques that give strong results for stereo matching. It is well known that stereo, like many problems in early vision, can be elegantly stated in terms of energy minimization [19]. The energy minimization problem has traditionally been solved via simulated annealing [2,11], which is extremely slow in practice. In the last few years powerful energy minimization algorithms have been developed based on graph cuts [6,7,12,14,21]. These methods are fast enough to be practical, and yield quite promising experimental results for stereo [22, 27]. Unlike simulated annealing, graph cut methods cannot be applied to an arbitrary energy function; instead, for each energy function to be minimized, a careful graph construction must be developed. In this paper, instead of building a special purpose graph we will use some recent results [15] that give graph constructions for a quite general class of energy functions. While energy minimization has been widely used for stereo, only a few papers [13,20,24] have used it for scene reconstruction. The energy minimization formalism has several advantages. It allows a clean specification of the problem to be solved, as opposed to the algorithm used to solve it. In addition, energy minimization naturally allows the use of soft constraints, such as spatial coherence. In an energy minimization framework, it is possible to cause ambiguities to be resolved in a manner that leads to a spatially smooth answer. Finally, energy minimization avoids being trapped by early hard decisions. Although [20] and [24] use energy minimization via graph cuts, their focus is quite different from ours. [20] uses an energy function whose global minimum can be computed efficiently via graph cuts; however, the spatial smoothness term is not discontinuity preserving, and so the results tend to be oversmoothed. Visibility constraints are not used. [24] computes the global minimum of a different energy function as an alternative to silhouette intersection (i.e., to determine voxel occupancy). Their approach does not deal with photoconsistency at all, nor do they reason about visibility. Our method is perhaps closest to the work of [13], which also relies on graph cuts. They extend the work of [7], which focused on traditional stereo matching, to allow an explicit label for occluded pixels. While the energy function that they use is of a similar general form to ours, they do not treat the input images symmetrically. While we effectively compute a disparity map with respect to each camera, they compute a disparity map only with respect to a single camera. [26] also proposed the use of disparity maps for each camera, in an energy minimization framework. Their optimization scheme did not rely on graph cuts, and their emphasis was on the two-camera stereo problem. They also focused on handling transparency, which is an issue that we do not address. Another approach is to formulate the problem in terms of level sets, and to solve a system of partial differential equations using numerical techniques [9]. The major distinction between this approach and our work is that their problem formulation is continuous while ours is discrete. The discrete energy
Multi-camera Scene Reconstruction via Graph Cuts
85
minimization approach is known to lead to strong results for two-camera stereo [22,27], and is therefore worth investigating for multiple cameras. In [14] we proposed a (two camera) stereo algorithm that shares a number of properties with the present work. That method treats the input images symmetrically, and is based on graph cuts for energy minimization. It properly handles the limited form of visibility constraint that arises with two cameras (namely, occlusions). The major difference is that [14] is limited to the case of two cameras, while the multi-camera problem is much more difficult.
3
Problem Formulation
Suppose we are given n calibrated images of the same scene taken from different viewpoints (or at different moments of time). Let Pi be the set of pixels in the camera i, and let P = P1 ∪ . . . ∪ Pn be the set of all pixels. A pixel p ∈ P corresponds to a ray in 3D-space. Consider the point of the first intersection of this ray with an object in the scene. Our goal is to find the depth of this point for all pixels in all images. Thus, we want to find a labeling f : P → L where L is a discrete set of labels corresponding to different depths. In the current implementation of our method, labels correspond to increasing depth from a fixed camera. A pair p, l where p ∈ P, l ∈ L corresponds to some point in 3D-space. We will refer to such pairs as 3D-points. The limitation of our method is that there must exist a function D : R3 → R such that for all scene points P and Q, P occludes Q in a camera i only if D(P ) < D(Q). This is exactly the constraint used in voxel coloring [23]. If such a function exists then labels correspond to level sets of this function. In our current implementation, we make a slightly more specific assumption, which is that the cameras must lie in one semiplane looking at the other semiplane. The interpretation of labels will be as follows: each label corresponds to a plane in 3D-space, and a 3D-point p, l is the intersection of the ray corresponding to the pixel p and the plane l. Let us introduce the set of interactions I consisting of (unordered) pairs of 3D-points p1 , l1 , p2 , l2 “close” to each other in 3D-space. We will discuss several criteria for “closeness” later. In general, I can be an arbitrary set of pairs of 3D-points satisfying the following constraint: – Only 3D-points at the same depth can interact, i.e.if {p1 , l1 , p2 , l2 } ∈ I then l1 = l2 . Now we will define the energy function that we minimize. It will consist of three terms: E(f ) = Edata (f ) + Esmoothness (f ) + Evisibility (f ) The data term will impose photo-consistency. It is D(p, q) Edata (f ) = p,f (p),q,f (q)∈I
(1)
86
V. Kolmogorov and R. Zabih
where D(p, q) is a non-positive value depending on intensities of pixels p and q. It can be, for example, D(p, q) = min{0, (Intensity(p) − Intensity(q))2 − K} for some constant K > 0. Since we minimize the energy, terms D(p, q) that we sum will be small. These terms are required to be non-negative for technical reasons that will be described in section 4.2. Thus, pairs of pixels p, q which come from the same scene point according to the configuration f will have similar intensities, which causes photo-consistency. The smoothness term involves a notion of neighborhood; we assume that there is a neighborhood system on pixels N ⊂ {{p, q} | p, q ∈ P} This can be the usual 4-neighborhood system: pixels p = (px , py ) and q = (qx , qy ) are neighbors if they are in the same image and |px − qx | + |py − qy | = 1. We will write the smoothness term as V{p,q} (f (p), f (q)) Esmoothess (f ) = {p,q}∈N
We will require the term V{p,q} to be a metric. This imposes smoothness while preserving discontinuities, as long as we pick an appropriate robust metric. For example, we can use the robustified L1 distance V (l1 , l2 ) = min(|l1 − l2 |, K) for constant K. The last term will encode the visibility constraint: it will be zero if this constraint is satisfied, and infinity otherwise. We can write this using another set of interactions Ivis which contains pairs of 3D-points violating the visibility constraint: Evisibility (f ) = ∞ p,f (p),q,f (q)∈Ivis
We require the set Ivis to meet following condition: – Only 3D-points at different depths can interact, i.e. if {p1 , l1 , p2 , l2 } ∈ Ivis then l1 = l2 . The visibility constraint says that if a 3D-point p, l is present in a configuration f (i.e. l = f (p)) then it “blocks” views from other cameras: if a ray corresponding to a pixel q goes through (or close to) p, l then its depth is at most l. Again, we need a definition of “closeness”. We will use the set I this part of the construction of Ivis . The set Ivis can then be defined as follows: it will contain all pairs of 3D-points p, l, q, l such that p, l and q, l interact (i.e. they are in I) and l > l. An important issue is the choice of the sets of interactions I. This basically defines a discretization. It can consist, for example, of pairs of 3D-points
Multi-camera Scene Reconstruction via Graph Cuts l=2
l=3
C1
87
q
p
C2 Depth labels
Fig. 1. Example of pixel interactions. There is a photo-consistency constraint between the red round point and the blue round point, both of which are at the same depth (l = 2). The red round point blocks camera C2’s view of the green square point at depth l = 3. Color figures are available in the electronic version of this paper.
{p, l, q, l} such that the distance in 3D-space between these points is less than some threshold. However, with this definition of closeness the number of interactions per pixel may vary greatly from pixel to pixel. Instead, we chose the following criterion: if p is a pixel in the image i, q is a pixel in the image j and i < j then the 3D-points p, l, q, l interact if the closest pixel to the projection of p, l onto the image j is q. Of course, we can include only interactions between certain images, for example, taken by neighboring cameras. Note that it makes sense to include interactions only between different cameras. An example of our problem formulation in action is shown in figure 1. There are two cameras C1 and C2. There are 5 labels shown as black vertical lines. As in our current implementation, labels are distributed by increasing distance from a fixed camera. Two pixels, p from C1 and q from C2 are shown, along with the red round 3D-point q, 2 and the blue round 3D-point p, 2. These points share the same label, and interact (i.e., {p, 2, q, 2} ∈ I). So there is a photoconsistency term between them. The green square point q, 3 is at a different label (greater depth), but is behind the red round point. The pair of 3D-points {p, 2, q, 3} is in Ivis . So if the ray p from camera C1 sees the red round point p, 2, the ray q from C2 cannot see the green square point q, 3. We show in the appendix that minimizing our energy is an NP-hard problem. Our approach, therefore, is to constuct an approximation algorithm based on graph cuts that finds a strong local minimum.
88
4
V. Kolmogorov and R. Zabih
Graph Construction
We now show how to efficiently minimize E among all configurations using graph cuts. The output of our method will be a local minimum in a strong sense. In particular, consider an input configuration f and a disparity α. Another configuration f is defined to be within a single α-expansion of f when for all pixels p ∈ P either f (p) = f (p) or f (p) = α. This notion of an expansion was proposed by [7], and forms the basis for several very effective stereo algorithms [3,7,13,14]. Our algorithm is very straightforward; we simply select (in a fixed order or at random) a disparity α, and we find the unique configuration within a single α-expansion move (our local improvement step). If this decreases the energy, then we go there; if there is no α that decreases the energy, we are done. Except for the problem formulation and the choice of energy function, this algorithm is identical to the methods of [7,14]. One restriction on the algorithm is that the initial configuration must satisfy the visibility constraint. This will guarantee that all subsequent configurations will satisfy this constraint as well, since we minimize the energy, and configurations that do not satisfy the visibility constraint have infinite energy. The critical step in our method is to efficiently compute the α-expansion with the smallest energy. In this section, we show how to use graph cuts to solve this problem. 4.1
Graph Cuts
Let G = V, E be a weighted graph with two distinguished terminal vertices {s, t} called the source and sink. A cut C = V s , V t is a partition of the vertices into two sets such that s ∈ V s and t ∈ V t . (Note that a cut can also be equivalently defined as the set of edges between the two sets.) The cost of the cut, denoted |C|, equals the sum of the weights of the edges between a vertex in V s and a vertex in V t . The minimum cut problem is to find the cut with the smallest cost. This problem can be solved very efficiently by computing the maximum flow between the terminals, according to a theorem due to Ford and Fulkerson [10]. There are a large number of fast algorithms for this problem (see [1], for example). The worst case complexity is low-order polynomial; however, in practice the running time is nearly linear for graphs with many short paths between the source and the sink, such as the one we will construct. We will use a result from [15] which says that for energy functions of binary variables of the form E i,j (xi , xj ) (2) E(x1 , . . . , xn ) = i<j
it is possible to construct a graph for minimizing it if and only if each term E i,j satisfies the following condition: E i,j (0, 0) + E i,j (1, 1) ≤ E i,j (0, 1) + E i,j (1, 0)
(3)
Multi-camera Scene Reconstruction via Graph Cuts
89
If these conditions are satisfied then the graph G is constructed as follows. We add a node vi for each variable xi . For each term E i,j (xi , xj ) we add edges which are given in the appendix. Every cut on such a graph corresponds to some configuration x = (x1 , . . . , xn ), and vice versa: if vi ∈ V s then xi = 0, otherwise xi = 1. Edges on a graph were added in such a way that the cost of any cut is equal to the energy of the corresponding configuration plus a constant. Thus, the minimum cut on G yields the configuration that minimizes the energy. 4.2
α-Expansion
In this section we will show how to convert our energy function into the form of equation 2. Note that it is not necessary to use only terms E i,j for which i < j since we can swap the variables if necessary without affecting condition 3. Although pixels can have multiple labels and in general cannot be represented by binary variables, we can do it for the α-expansion operation. Indeed, any configuration f within a single α-expansion of the initial configuration f can be encoded by a binary vector x = {xp |p ∈ P} where f (p) = f (p) if xp = 0, and f (p) = α if xp = 1. Let us denote a configuration defined by a vector x as f x . Thus, we have the energy of binary variables: ˜ ˜data (x) + E ˜smoothness (x) + E ˜visibility (x) E(x) =E where
˜data (x) = Edata (f x ), E ˜smoothness (x) = Esmoothness (f x ), E ˜visibility (x) = Evisibility (f x ). E
Let’s consider each term separately, and show that each satisfies condition (3). 1. Data term. ˜data (x) = D(p, q) = T (f x (p) = f x (q) = l) · D(p, q) E p,f x (p),q,f x (q)∈I
p,l,q,l∈I
where T (·) is 1 if its argument is true and 0 otherwise. Let’s consider a single term E p,q (xp , xq ) = T (f x (p) = f x (q) = l) · D(p, q). Two cases are possible: 1A. l =α. If at least one of the labels f (p), f (q) is not l then E p,q ≡ 0. Suppose that f (p) = f (q) = l. Then E(xp , xq ) is equal to D(p, q), if xp = xq = 0, and is zero otherwise. We assumed that D(p, q) is non-positive, thus, condition (3) holds: E p,q (0, 0) + E p,q (1, 1) = D(p, q) ≤ 0 = E p,q (0, 1) + E p,q (1, 0) 1B. l = α. If at least one of the labels f (p), f (q) is α then E p,q depends only on at most one variable so condition (3) holds. (Suppose, for example, that f (q) = α, then f x (q) = α for any value of xq and, thus, E p,q (xp , 0) = E p,q (xp , 1) and E p,q (0, 0) + E p,q (1, 1) = E p,q (0, 1) + E p,q (1, 0).)
90
V. Kolmogorov and R. Zabih
Now suppose that both labels f (p), f (q) are not α. Then E(xp , xq ) is equal to D(p, q), if xp = xq = 1, and is zero otherwise. We assumed that D(p, q) is non-positive, thus, condition (3) holds: E p,q (0, 0) + E p,q (1, 1) = D(p, q) ≤ 0 = E p,q (0, 1) + E p,q (1, 0) 2. Smoothness term. ˜smoothness (x) = E
V{p,q} (f x (p), f x (q)).
{p,q}∈N
Let’s consider a single term E p,q (xp , xq ) = V{p,q} (f x (p), f x (q)). We assumed that V{p,q} is a metric; thus, V{p,q} (α, α) = 0 and V{p,q} (f (p), f (q)) ≤ V{p,q} (f (p), α)+ V{p,q} (α, f (q)), or E p,q (1, 1) = 0 and E p,q (0, 0) ≤ E p,q (0, 1) + E p,q (1, 0). Therefore, condition (3) holds. 3. Visibility term. ˜visibility (x) = ∞ E p,f x (p),q,f x (q)∈Ivis
=
T (f x (p) = lp ∧ f x (q) = lq ) · ∞.
p,lp ,q,lq ∈Ivis
Let’s consider a single term E p,q (xp , xq ) = T (f x (p) = lp ∧ f x (q) = lq ) · ∞. E p,q (0, 0) must be zero since it corresponds to the visibility cost of the initial configuration and we assumed that the initial configuration satisfies the visibility constraint. Also E p,q (1, 1) is zero (if xp = xq = 1, then f x (p) = f x (q) = α and, thus, the conditions f x (p) = lp and f x (q) = lq cannot both be true since Ivis includes only pairs of 3D-points at different depths). Therefore, condition (3) holds since E p,q (0, 1) and E p,q (1, 0) are non-negative.
5
Experimental Results
Some details of our implementation are below. The planes for labels were chosen to be orthogonal to the main axis of the middle camera, and to increase with depth. The labels are distributed so that disparities depend on labels approximately linearly. The depth difference between planes was chosen in such a way that a label change by one results in disparity change by at most one both in x and y directions. We selected the labels α in random order, and kept this order for all iterations. We performed three iterations. (The number of iterations until convergence was at most five but the result was practically the same). We started with an initial solution in which all pixels are assigned to the label having the largest depth. For our data term D we made use of the method of Birchfield and Tomasi [4] to handle sampling artifacts, with a slight variation: we compute intensity intervals for each band (R,G,B) using four neighbors, and then take the average
Multi-camera Scene Reconstruction via Graph Cuts
91
data penalty. (We used color images; results for grayscale images are slightly worse). The constant K for the data term was chosen to be 30. We used a simple Potts model for the smoothness term: lq U{p,q} if lp = (4) V{p,q} (lp , lq ) = 0 otherwise The choice of U{p,q} was designed to make it more likely that a pair of adjacent pixels in one image with similar intensities would end up with similar disparities. For pixels {p, q} ∈ N the term U{p,q} was implemented as an empirically selected decreasing function of ∆I(p, q) as follows: (5) U{p,q} = 3λ if ∆I(p, q) < 5 λ otherwise where ∆I(p, q) is the average of values |Intensity(p) − Intensity(q)| for all three bands (R,G,B). Thus, the energy depends only on one parameter λ. For different images we picked λ empirically. We performed experiments on three datasets: the ’head and lamp’ image from Tsukuba University, the flower garden sequence and the Dayton sequence. We used 5 images for the Tsukuba dataset (center, left, right, top, bottom), 8 images for the flower garden sequence and 5 images for the Dayton sequence. For the Tsukuba dataset we performed two experiments: in the first one we used four pairs of interacting cameras (center-left, center-right, center-top, center-bottom), and in the second one we used all 10 possible pairs. For the flower garden and Dayton sequences we used 7 and 4 interacting pairs, respectively (only adjacent cameras interact). The table below show image dimensions and running times obtained on 450MHz UltraSPARC II processor. We used the max flow algorithm of [5], which is specifically designed for the kinds of graphs that arise in vision. Source code for this algorithm is available on the web from http://www.cs.cornell.edu/People/vnk. dataset Tsukuba Tsukuba Flower garden Dayton
number of number of image number of images interactions size labels 5 4 384 x 288 16 5 10 384 x 288 16 8 7 352 x 240 16 5 4 384 x 256 16
running time 369 secs 837 secs 693 secs 702 secs
We have computed the error statistics for the Tsukuba dataset, which are shown in the table below. We determined the percentage of the pixels where the algorithm did not compute the correct disparity (the “Errors” column), or a disparity within ±1 of the correct disparity (“Gross errors”). For comparison, we have included the results from the best known algorithm for stereo reported in [27], which is the method of [7]. The images are shown in 2, along with the areas where we differ from ground truth (black is no difference, gray is a difference of ±1, and white is a larger difference). Inspecting the image shows that we in general achieve greater accuracy at discontinuities; for example, the camera in the background and the lamp
92
V. Kolmogorov and R. Zabih
are more accurate. The major weakness of our output is in the top right corner, which is an area of low texture. The behavior of our method in the presence of low texture needs further investigation. Errors Gross errors 4 interactions 6.13% 2.75% 10 interactions 4.53% 2.30% 3.99% Boykov-Veksler-Zabih [7] 9.76% We have also experimented with the parameter sensitivity of our method for the Tsukuba dataset using 10 interactions. Since there is only one parameter, namely λ in equation 5, it is easy to experimentally determine the algorithm’s sensitivity. The table below shows that our method is relatively insensitive to the exact choice of λ. λ 2 5 10 20 40 Error 4.67% 4.53% 5.28% 5.78% 8.27% Gross errors 2.43% 2.30% 2.30% 2.23% 2.86%
6
Extensions
It would be interesting to extend our approach to more general camera geometries, for example the case when cameras look at the object in the center from all directions. Labels could then correspond to spheres. More precisely, there would be two labels per sphere corresponding to the closest and farthest intersection points. Acknowledgements. This research was supported by NSF grants IIS-9900115 and CCR-0113371, and by a grant from Microsoft Research. We also thank Rick Szeliski for providing us with some of the imagery used in section 5. Appendix: Edges for Terms E i,j In this section we show how to add edges for a term E i,j in the equation 2 assuming that condition (3) holds. This is a special case of a more general construction given in [15]. – if E(1, 0) > E(0, 0) then we add an edge (s, vi ) with the weight E(1, 0) − E(0, 0), otherwise we add an edge (vi , t) with the weight E(0, 0) − E(1, 0); – if E(1, 0) > E(1, 1) then we add an edge (vj , t) with the weight E(1, 0) − E(1, 1), otherwise we add an edge (s, vj ) with the weight E(1, 1) − E(1, 0); – the last edge that we add is (vi , vj ) with the weight E(0, 1) + E(1, 0) − E(0, 0) − E(1, 1). We have omitted indices i, j in E i,j for simplicity of notation. Of course it is not necessary to add edges with zero weights. Also, when several edges are added from one node to another, it is possible to replace them with one edge with the weight equal to the sum of weights of individiual edges.
Multi-camera Scene Reconstruction via Graph Cuts
93
Center image
Ground truth
Our results - 4 interactions
Our results - 10 interactions
Boykov-Veksler-Zabih results [7]
Comparison of our results with ground truth
Fig. 2. Results on Tsukuba dataset.
Appendix: Minimizing Our Energy Function Is NP-Hard It is shown in [7] that the following problem, referred to as Potts energy minimization, is NP-hard. We are given as input a set of pixels S with a neighborhood system N ⊂ S × S, and a set of label values L and a non-negative function C : S × L → + . We seek the labeling f : S → Lthat minimizes EP (f ) = C(p, f (p)) + T (f (p) = f (q)). (6) p∈P
{p,q}∈N
94
V. Kolmogorov and R. Zabih
Middle image
Our results
Fig. 3. Results on the flower garden sequence.
Middle image
Our results
Fig. 4. Results on the Dayton sequence.
We now sketch a proof that an arbitrary instance of the Potts energy minimization problem can be encoded as a problem minimizing the energy E defined in equation 1. This shows that the problem of minimizing E is also NP-hard. We start with a Potts energy minimization problem consisting of S, V, N and C. We will create a new instance of our energy minimization problem as follows. There will be |L| + 1 images. The first one will be the original image S, and for each each label l ∈ L there will be an image Pl . For each pixel p ∈ S there will be a pixel in Pl which we will denote as pl ; thus, |Pl | = |S| for all labels l ∈ L. The set of labels L, the neighborhood system N and the smoothness function V{p,q} will be the same as in the Potts energy minimization problem: V{p,q} (lp , lq ) = T (lp = lq ),
{p, q} ∈ N
The set of interactions I will include all pairs {p, l, pl , l}, where p ∈ S, l ∈ L. The corresponding cost will be D(p, pl ) = C(p, l) − Kp where Kp is a constant which ensures that all costs D(p, pl ) are non-positive (for example, Kp = maxl∈L C(p, l)). There will be no visibility term (i.e. the set of
Multi-camera Scene Reconstruction via Graph Cuts
95
interactions Ivis will be empty). The instance of our minimization problem is now completely specified. Any labeling f : S → Lcan be extended to the labeling f¯ : P → Lif we set f¯(pl ) = l, pl ∈ Pl . It is easy to check that E(f¯) = EP (f ) − K where K = p∈S Kp is a constant. Moreover, there is no labeling f¯ : P → L with the smaller value of the energy E such that f¯ (p) = f¯(p) for all pixels p ∈ S. Thus, the global minimum f¯ of the energy E will yield the global minimum of the Potts energy EP (we need to take the restriction of f¯ on S).
References 1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. 2. Stephen Barnard. Stochastic stereo matching over scale. International Journal of Computer Vision, 3(1):17–32, 1989. 3. S. Birchfield and C. Tomasi. Multiway cut for stereo and motion with slanted surfaces. In International Conference on Computer Vision, pages 489–495, 1999. 4. Stan Birchfield and Carlo Tomasi. A pixel dissimilarity measure that is insensitive to image sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(4):401–406, April 1998. 5. Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of mincut/max-flow algorithms for energy minimization in computer vision. In International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 2134 of LNCS, pages 359–374. Springer-Verlag, September 2001. 6. Yuri Boykov, Olga Veksler, and Ramin Zabih. Markov Random Fields with efficient approximations. In IEEE Conference on Computer Vision and Pattern Recognition, pages 648–655, 1998. 7. Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222–1239, November 2001. 8. R. Cipolla and A. Blake. Surface shape from the deformation of apparent contours. International Journal of Computer Vision, 9(2):83–112, November 1992. 9. O.D. Faugeras and R. Keriven. Complete dense stereovision using level set methods. In European Conference on Computer Vision, 1998. 10. L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962. 11. S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721–741, 1984. 12. H. Ishikawa and D. Geiger. Occlusions, discontinuities, and epipolar lines in stereo. In European Conference on Computer Vision, pages 232–248, 1998. 13. S.B. Kang, R. Szeliski, and J. Chai. Handling occlusions in dense multi-view stereo. In IEEE Conference on Computer Vision and Pattern Recognition, 2001. Expanded version available as MSR-TR-2001-80.
96
V. Kolmogorov and R. Zabih
14. Vladimir Kolmogorov and Ramin Zabih. Visual correspondence with occlusions using graph cuts. In International Conference on Computer Vision, pages 508–515, 2001. 15. Vladimir Kolmogorov and Ramin Zabih. What energy functions can be minimized via graph cuts? In European Conference on Computer Vision, 2002. Also available as Cornell CS technical report CUCS-TR2001-1857. 16. K.N. Kutulakos and S.M. Seitz. A theory of shape by space carving. International Journal of Computer Vision, 38(3):197–216, July 2000. 17. A. Laurentini. The visual hull concept for silhouette-based image understanding. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(2):150–162, February 1994. 18. W.N. Martin and J.K. Aggarwal. Volumetric descriptions of objects from multiple views. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(2):150– 158, March 1983. 19. Tomaso Poggio, Vincent Torre, and Christof Koch. Computational vision and regularization theory. Nature, 317:314–319, 1985. 20. S. Roy. Stereo without epipolar lines: A maximum flow formulation. International Journal of Computer Vision, 1(2):1–15, 1999. 21. S. Roy and I. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In International Conference on Computer Vision, 1998. 22. Daniel Scharstein and Richard Szeliski. A taxonomy and evaluation of dense twoframe stereo correspondence algorithms. Technical Report 81, Microsoft Research, 2001. To appear in IJCV. An earlier version appears in CVPR 2001 Workshop on Stereo Vision. 23. S.M. Seitz and C.R. Dyer. Photorealistic scene reconstruction by voxel coloring. International Journal of Computer Vision, 35(2):1–23, November 1999. 24. Dan Snow, Paul Viola, and Ramin Zabih. Exact voxel occupancy with graph cuts. In IEEE Conference on Computer Vision and Pattern Recognition, pages 345–352, 2000. 25. R. Szeliski. Rapid octree construction from image sequences. Computer Vision, Graphics and Image Processing, 58(1):23–32, July 1993. 26. R. Szeliski and P. Golland. Stereo matching with transparency and matting. In International Conference on Computer Vision, pages 517–523, 1998. 27. Richard Szeliski and Ramin Zabih. An experimental comparison of stereo algorithms. In B. Triggs, A. Zisserman, and R. Szeliski, editors, Vision Algorithms: Theory and Practice, number 1883 in LNCS, pages 1–19, Corfu, Greece, September 1999. Springer-Verlag.
A Markov Chain Monte Carlo Approach to Stereovision Julien S´en´egas12 1 2
Centre de G´eostatistique, Ecole des Mines de Paris, 35 rue Saint-Honor´e, 77305 Fontainebleau Cedex, France Istar, 2600 route des Crˆetes, BP282 06905 Sophia-Antipolis Cedex, France
[email protected]
Abstract. We propose Markov chain Monte Carlo sampling methods to address uncertainty estimation in disparity computation. We consider this problem at a postprocessing stage, i.e. once the disparity map has been computed, and suppose that the only information available is the stereoscopic pair. The method, which consists of sampling from the posterior distribution given the stereoscopic pair, allows the prediction of large errors which occur with low probability, and accounts for spatial correlations. The model we use is oriented towards an application to mid-resolution stereo systems, but we give insights on how it can be extended. Moreover, we propose a new sampling algorithm relying on Markov chain theory and the use of importance sampling to speed up the computation. The efficiency of the algorithm is demonstrated, and we illustrate our method with the computation of confidence intervals and probability maps of large errors, which may be applied to optimize a trajectory in a three dimensional environment. Keywords: stereoscopic vision, digital terrain models, disparity, uncertainty estimation, sampling algorithms, Bayesian computation, inverse problems
1
Introduction
In this paper, we address the problem of assessing the uncertainty of depth estimates computed from a stereo system. We exclude the possibility of using any external source of information on the observed scene, i.e. only the radiometric information provided by the stereoscopic pair will be used. The application we have in mind is the certification of digital terrain models for the aircraft industry, but the methods we propose here are quite general and can be applied to any stereo system with some adaptations of the model used. 1.1
Errors in Stereovision
A stereo system consists of two cameras observing the same scene from two different points. With this set-up, a left and right image are obtained. A physical A. Heyden et al. (Eds.): ECCV 2002, LNCS 2352, pp. 97–111, 2002. c Springer-Verlag Berlin Heidelberg 2002
98
J. S´en´egas
point M projects onto the image plane of each camera. These projections form a pair of homologous points, and their coordinates in each image plane can be expressed as a function of the stereo system parameters (mainly the baseline b and the focal length f ) and the coordinates of M . The principle of depth estimation from stereovision relies on the inversion of this relation. An extensive introduction to three dimensional computer vision and depth from stereo can be found in [10]. Many different techniques are used for depth computation, depending on the type of sensors and the nature of the scene. However, they generally consist of the following steps. First, the stereo system parameters are computed, using calibration methods (see [8] for an example). It is then possible to reproject the images in the epipolar geometry, in which two homologous points have the same vertical coordinate. The difference between their horizontal coordinates is called the disparity. Hence, the rectification step reduces the search of homologous points to a mono-dimensional one (along the rows of the images). The stereo problem itself amounts then to the computation of the disparity map, which is done by matching pixels (or features) in the left image with the corresponding pixels in the right image [9]. Lastly, the computation of the real world coordinates, the triangulation, follows from the disparity map and the geometry of the stereo system. Uncertainty in depth estimates arises from errors or approximations in each step described above, however it is important to distinguish between these errors. Calibration, rectification and triangulation rely on geometric relations verified by the stereo system. Even if these are only approximations of the true geometric constraints, the errors associated with them can be controlled and their range computed. For instance, quantization errors, which come from the knowledge of the image points coordinates at fixed positions only, with a precision equal to half the sampling interval δ [20], depend only on the stereo system parameters. Possibly, the precision can be improved by modifying the stereo system: for example, an increase of the product bf enables to obtain more accurate depth estimates [20]. In opposition, matching errors are strongly dependent on the nature of the radiometric information, and cannot be entirely controlled by the design of the stereo system. The reason for this lies in the implicit matching assumption that pairs of homologous points can be identified. In many situations, violations of this assumption are encountered: the geometric deformations induced by the projections may be strong, the images are corrupted by sensor noise or the radiometric information itself may be ambiguous (existence of repetitive features, lack of texture in the images,...). As a result, matching errors are likely to be dependent on the specific features in the images and to vary strongly over the disparity map. 1.2
A Stochastic Approach
A convenient framework to handle uncertainty in disparity computation is to consider the disparity D and the stereoscopic pair Y = (I1 , I2 ), as random
A Markov Chain Monte Carlo Approach to Stereovision
99
functions. This approach has been successfully applied in a Bayesian context to compute disparity estimates [1]. However, to our knowledge, the problem of uncertainty assessment has been only partly handled, mostly through the computation of standard deviation [23,16]. Standard deviation estimates give only a rough idea of the range of possible errors, and are not appropriate to describe large errors, which appear with very low probability and are spatially correlated. Therefore, specific methods have to be proposed. Typically, if we consider an object in motion in a 3D environment, one must find the path to a given target which minimizes the risk of collisions. Such problems require the computation of the whole conditional probability distribution πD (d|Y = y) of the disparity D given the stereoscopic pair Y . Note that once πD (d|Y = y) is known, we can easily compute the corresponding probability distributions for the real world coordinates, using the geometric transformation of the stereo system. This motivates the choice of the disparity as variable of interest. The main contribution of this paper is to propose a theoretically founded approach to the problem of uncertainty assessment in disparity computation. Especially, we show in Sect. 2 that this problem amounts to sample from the posterior distribution πD and to use Monte Carlo integrations. We also explicit the model πD used for computation, but point out that this one is very dependent on the application. We give insight on how this model can be adapted to specific applications. On the opposite, the sampling algorithms we propose in Sect. 3 are quite general and can be used for different forms of probability models πD . The only restriction is a gaussian assumption for the prior model. Lastly, in Sect. 4, we illustrate our methods with an application to the study of a stereoscopic pair of SPOT images. In the sequel, we will assume that an estimate dˆ of the disparity has been already computed, for example with a correlation based algorithm. This means that the algorithms we propose in the sequel are not used for disparity computation, but only for uncertainty assessment. One reason is that Monte Carlo algorithms are computationally cumbersome. Another reason is that we are interested in the uncertainty which is intrinsic to the radiometric information. Indeed, we consider the uncertainty estimation mostly at a postprocessing stage, and would like to propose a method that is widely independent of the disparity computation itself.
2
Stochastic Framework: Stereovision as an Inverse Problem
Let Y = (I1 , I2 ) be a stereoscopic pair in the epipolar geometry. We consider a physical point M , and its projections m1 with coordinates (u1 , v1 ) in I1 and m2 , with coordinates (u2 , v2 ) in I2 . The epipolar constraint imposes v1 = v2 and we can define the disparity in the reference system of I1 as the difference: d(u1 , v1 ) = u2 − u1
(1)
100
J. S´en´egas
Therefore, a pair of homologous points is fully defined by the coordinates (u, v) of m1 in I1 and the disparity d(u, v). Note that a symmetric definition of disparity in the cyclopean image is possible, see [1]. Although we proceed with definition 1, the approach we propose is readily applicable to this alternative definition. This purely geometric presentation however corresponds to the direct problem, where the coordinates of the homologous points are known. In practice, these are to be found, and generally a loss function Cu,v (d), which expresses the similarity of the images in the neighborhood of I1 (u, v) and I2 (u + d, v), is used [9]. The estimate dˆ of the “true” disparity is then taken to be the value which maximizes Cu,v (d), possibly under some constraints, i.e.: ˆ v) = arg max Cu,v (d) d(u, d
(2)
Therefore, when computing the disparity, and whatever method is used, one must move from a purely geometric definition 1 to an optimization criterion 2. In other words, disparity computation in stereovision is an inverse problem, and therefore, the result is only an estimate of the underlying disparity. This estimate is sensible to the amount of noise in the stereoscopic pair, but, even if perfect signal is assumed, uncertainty remains, because of the ambiguity of the information, due to occlusions, repetitive features, lack of texture in the images,... The Bayesian framework [3] is well adapted to inverse problems. Bayesian inference has been widely used in image analysis [2], and efficient algorithms have been proposed to solve the restoration problem, as in [13]. More recently, this formalism has been applied to the stereo-reconstitution problem [23,1]. Let πD (d|Y = y) be the posterior (or conditional) probability of the disparity D given the stereoscopic pair Y = y. Using Bayes relation, this one can be expressed by means of the conditional distribution of Y given D = d, πY (y|D = d), and the marginal distributions πD (d) and πY (y). Since here Y is known and remains equal to y, πY (y) is a constant, and we can introduce the likelihood L(y|D = d) = πY π(y|D=d) , which can be computed up to a multiplicative conY (y) stant, and for clarity, we denote g(d) = πD (d) the prior distribution. With these notations, the posterior distribution writes: πD (d|Y = y) = L(y|D = d)g(d)
(3)
In stereovision, this formalism has been mostly applied to compute an estimate of the disparity, through maximum a posteriori (MAP) estimation [1], where the maximization of πD (d|Y = y) is used as criterion. However, here, we are interested in the computation of the whole posterior distribution πD (d|Y = y). Especially, for any πD −measurable function h, we would like to compute the integral: EπD (h) =
h(z)πD (z|Y = y)dz
(4)
With an appropriate choice of h, every probability concerning D can be computed. For example, with h(d) = 1|d−d|≥s where dˆ is an estimate of the disparity, ˆ
A Markov Chain Monte Carlo Approach to Stereovision
101
we obtain the probability that the estimation error D− dˆ is greater than a threshold s: ˆ ≥ s) = πD (z|Y = y)dz (5) P (|D − d| ˆ |z−d|≥s
In the following, we explicit the computation of 4 and derive an expression for πD . 2.1
MCMC Methods
In practice, the numerical computation of 4 is not possible since πD is a function of n variables, where n is the size of the image. Another reason is that πD is known only up to a multiplicative factor. A solution is provided by Monte Carlo integration which evaluates the integral in 4 by drawing samples {zi , i = 1, ..., m} from πD and then approximating m
EπD (h) ≈
1 h(zi ) m i=1
(6)
The laws of large numbers ensure that the approximation can be made as accurate as desired by increasing the sample size m. Monte Carlo methods were used in similar problems [11,7], but mostly to compute map estimates. We show in this paper that more information can be extracted from the posterior distribution. A method to draw samples from πD consists of building a Markov chain having πD as its stationary distribution. In practice, the problem amounts to determine a transition probability kernel which ensures the convergence to πD . This is the principle of the well known Metropolis-Hastings algorithm [15] or the popular Gibbs sampler [13]. For a detailed introduction to Markov chain theory, the interested reader is referred to [18] and [24]. Practical applications of Markov chain Monte Carlo can be found in [14]. As a conclusion, assessment of disparity uncertainty and disparity estimation are two very different problems, and the former requires the development of specific methods. Uncertainty can be assessed under a Bayesian framework by drawing samples from the posterior distribution of the disparity given the stereoscopic pair. Two points remain to be solved: the specification of the model, which is treated in Sect. 2.2, and the choice of a sampling algorithm, which is the subject of Sect. 3. 2.2
Model Derivation
We need to specify the likelihood term L(y|D = d), which describes the relation between the images of the pair at fixed disparity, and the prior model g, which reflects the spatial structure of the disparity. Let us point out that the choice of the probability model πD is specific to the application, i.e. to the type of images recorded and the nature of the scene observed. In our case, we use
102
J. S´en´egas
stereoscopic pairs of SPOT images for the computation of mid-resolution digital terrain models (with a ground resolution approximately equal to 10 m). We first derive an expression for the image model (likelihood) and then for the disparity model (prior). A common modeling for the likelihood [1] consists of assuming that the recorded intensity I for a specific feature is the same for both images I1 and I2 and sensor noise is additive. Therefore, for fixed disparity d, the relation between I1 and I2 writes: I1 (u, v) − I2 (u + d(u, v), v) = η(u, v)
(7)
where η(u, v) can be interpreted as the residual between the intensities after a correction on the coordinates with the disparity. The choice of the image model amounts hence to the modeling of η, and especially its spatial correlation. If we assume the residual η to be uncorrelated gaussian noise with mean µ and standard deviation κ, as in [4,6,1], we end up with the following expression of the likelihood: (ηij − µ)2 L(y|D = d) ∝ exp − (8) 2κ2 i,j The assumption of uncorrelated noise η may be questioned. Especially, one may argue that if the deformations induced by the stereo system are relatively important, the residual η will show strong patterns. Therefore, this point is very dependent on the setting of the stereo system and the nature of the scene. For satellite images at mid-resolution, these deformations may be neglected in a first approach, and the assumption of uncorrelated gaussian noise is reasonable. However, this is definitely a challenging aspect of the problem. Note that, as we have an estimate dˆ of the disparity, we can compute from I1 ˆ v), v). Hence, and I2 an estimate of the residual ηˆ(u, v) = I1 (u, v) − I2 (u + d(u, the model parameters µ and κ can be estimated by maximum likelihood. For the disparity model, we adopt a gaussian random function framework, which is relatively common [23,4,1]. Under the gaussian assumption, the prior distribution is entirely specified by the mean m and the spatial covariance C. ˆ for example under These parameters can be estimated from the disparity map d, an assumption of spatial stationarity [5]. Finally, the prior distribution g takes the following form: 1 −1 g(d) ∝ exp − (d − m) C (d − m) (9) 2 Here again, let us point out that the choice of the prior model is dependent on the application. Especially, the behavior of the covariance at the origin will reflect the smoothness of the disparity: for example, a model with a linear behavior (such as Brownian motion [1]) is liable to reproduce discontinuities. Our experience is that covariances which are differentiable at the origin (such as the
A Markov Chain Monte Carlo Approach to Stereovision
103
cubic covariance) are well adapted in the case of mid-resolution stereo systems. However, for high-resolution applications, such as urban or indoor scenes, other models may be chosen. For example, in [1], Belhumeur proposes to model directly the discontinuities at the edges of objects through Poisson processes. More generally, one may argue that for such applications, stochastic geometric models, which directly take into account the form of objects, may be better adapted. Such models were applied to building detection [12] and road extraction [22]. Let us point out that, although we made the gaussian assumption for the prior distribution g, the posterior distribution is not necessarily gaussian. The nature of the posterior distribution depends largely on the likelihood term L, which is not a quadratic form of d. For example, the presence of repetitive features in the stereoscopic pair would result in a multimodal posterior distribution.
3
Sampling Algorithm
In this section we expose the details of the sampling algorithm. We recall that the probability distribution to be sampled from is of the form: π(z|Y = y) = L(y|Z = z)g(z)
(10)
where L(y|Z = z) is the likelihood function, which may be known up to multiplicative factor, and g(z) is the prior distribution. 3.1
Markov Chain Sampling Algorithms
As stated previously, iterative Markov chain algorithms have to be used. In our case, the difficulty lies in the form of the likelihood term L(Y |D = d), which cannot be approximated efficiently and is expected to vary strongly with the coordinates (u, v). The Gibbs sampler, which in combination with Markov random fields models is very popular in image analysis, relies on the use of conditional densities of the form π(zS |z−S ), where S is a subspace of the grid to be simulated and −S its complementary part [3]. Unfortunately, because of the expression of the distribution πD , it is not possible to sample directly from the conditional distributions. Other alternatives are Metropolis-Hastings algorithms [14] and variants such as discretized Langevin diffusions [19]. The principle of the Metropolis-Hastings algorithm is to generate a transition kernel q(z, from the current state z to the state z from a proposal transition
z ), )q(z ,z) and to accept this transition with probability a(z, z ) = min 1, π(z π(z)q(z,z ) . The efficiency of this algorithm relies merely on the proposal transition kernel q, but when the target distribution π cannot be easily approximated, optimal choices of q are not possible, and very often an ad hoc transition kernel is used, like in the independence sampler or the random walk [14].
104
3.2
J. S´en´egas
A New Sampling Algorithm
These difficulties have led us to propose a new sampling algorithm which makes use of the target distribution π to generate the transitions. Let us assume that the prior distribution g(z) denotes now a gaussian distribution. The algorithm is based on the following remark. Let W1 and W2 be two independent gaussian processes with zero mean and covariance C (which we denote W1 , W2 ∼ g). Then, for any θ ∈ [0, 2π[, the linear combination W (θ) = W1 cos θ + W2 sin θ is also a gaussian process with zero mean and covariance C. We propose to use this relation, together with an appropriate choice of θ, to build the transitions of a Markov chain Z = (Zk , k ≥ 0). The algorithm is the following: 1. sample w ∼ g, 2. compute the proposal transitions: 2π 2π + w sin i , zi = zk cos i m m
∀i = 0, m − 1
(11)
and the corresponding transition probabilities: L(y|Z = zi ) a(z, zi ) = m−1 , j=0 L(y|Z = zj )
∀i = 0, m − 1
(12)
3. choose zi ∼ a(z, zi ) and set zk+1 = zi . We prove in [21] that the Markov chain built according to this algorithm has π as stationary distribution. A comparison study of this algorithm with the independence sampler and the Langevin diffusion can be found in [21]. The interesting feature of this algorithm is that at each iteration, a whole path of possible transitions is proposed, in opposition to a single one in the Metropolis-Hastings algorithm, and this is done at a low computational cost since it only requires the computation of linear combinations of the form 11. Therefore, transitions are likely to occur more often, which improves mixing within the chain and speeds up the convergence. An illustration of this feature is displayed on Fig. 1. 3.3
Size Reduction and Importance Sampling
For large grids, the computational burden of Markov chain algorithms can become very cumbersome. Gaussian samples can be generated very quickly (with algorithms such as those relying on the Fast Fourier Transform [5]), but the transition rate of the Markov chain tends to decrease drastically with the grid size, so that the sampling algorithm must be run longer to achieve convergence. To cope with this difficulty, we propose to split the sampling in two consecutive phases. Consider a subgrid S of the total sampling grid G and its complementary −S in
1.0
A Markov Chain Monte Carlo Approach to Stereovision
105
0.05 0.06
0.5
0.07
0.12
0.11 0.1 0.09 0.08
y 0.0
0.08 0.07 0.06
-0.5
0.05 0.04 0.03
-1.0
0.02 0.01
-1.0
-0.5
0.0 x
0.5
1.0
Fig. 1. Path of possible transitions generated from the current point and an independent simulation (black dots). The target distribution, displayed in the background with level lines, is a bigaussian distribution. The circles along the path, which correspond each to a different value of θ, are proportional to the transition probability a(z, zi ).
G. zS denotes the restriction of the vector z to S. The posterior distribution π can be decomposed as follows: π(z|Y = y) =
L(y|Z = z) g(z−S |ZS = zS )L(y|ZS = zS )g(zS ) L(y|ZS = zS )
(13)
The term L(y|ZS = zS )g(zS ) is the posterior distribution π(zS |Y = y) on S, whereas g(z−S |ZS = zS ) is the conditional distribution of the gaussian vector z−S given zS (this is the conditional distribution which is used in the Gibbs sampler). Sampling from this conditional distribution can be done directly and very efficiently using an algorithm such as conditioning by kriging [5]. The first L(y|Z=z) term w = L(y|Z is a correction factor which shall be used to weight the S =zS ) samples in the Monte Carlo integration. We end up with the following algorithm: 1. run the Markov chain algorithm on the subgrid S, i 2. for each generated sample zSi , generate z−S using the conditional gaussian i ) the sample on distribution g(z−S |ZS = zS ), and construct zi = (zSi , z−S the total grid G, L(y|Z=zi ) 3. compute the weight wi = L(y|Z i , S =zS ) 4. compute the integral 1 Eπ (h) ≈ m
i=1
m
wi
wi h(zi ) .
(14)
i=1
The last step is an application of importance sampling theory [14]. One may run the risk that all weights wi but a few become equal to 0, and only a few samples take the total weight. This could happen if the distribution used for sampling π (z|Y = y) = π(zS |Y = y)g(z−S |ZS = zS ) and the target distribution
106
J. S´en´egas
π(z|Y = y) are very different. In our case, this should be avoided due to the strong spatial correlations exhibited by the disparity D. The idea is that if we know the disparity on a subgrid S, then we are able to compute accurate estimates of D on the total grid G, and correct fluctuations can be reproduced by sampling from the conditional distribution g(z−S |ZS = zS ). An overview of the sampling algorithm is shown on Fig. 2. Markov chain
Importance
Monte Carlo
sampling
sampling
integration
Left
Probability
Image
Σ
map
Stereoscopic pair
Right Image
Fig. 2. Overview of the sampling algorithm. First, the Markov chain sampling algorithm is run on a sub-grid, conditional to the stereoscopic pair. Then, for each generated sample, the whole grid is generated. Lastly, the Monte Carlo integration is performed.
4
Experimental Results
We have applied the model of Sect. 2.2 and the sampling algorithms introduced in Sect. 3 to the study of a stereoscopic pair of rectified SPOT images of the Marseille area, of size 512 × 512 pixels (Fig. 3). A disparity map (Fig. 3) has been computed using a correlation based algorithm. 2000 samples have been generated. Using the importance sampling algorithm, the size of the sampling grid has been reduced to 64 × 64, yielding thus a size reduction factor equal to 64. To illustrate the efficiency of the sampling algorithms, we run a Metropolis-Hastings algorithm (denoted as MH) on the total grid, then the sampling algorithm of Sect. 3 (denoted TCP for transitions along continuous paths), first on the total grid, and then on the reduced grid with the importance sampling method (denoted further TCPIS). We compared the computation time required to generate 100 samples with at least 10 state transitions between two samples, assuming that these conditions ensure similar convergence properties. Computations were performed on a SUN Ultra 60 computer with a 400 Mhz ULTRA SPARC II processor. The results are shown on Tab. 1. The TCP algorithm allows to reduce the computation time by a factor 10 in comparison to the independence Metropolis-Hastings sampler. The size reduction coupled with
A Markov Chain Monte Carlo Approach to Stereovision
(a) One image of the stereoscopic pair
107
(b) Disparity
Fig. 3. One rectified image of the stereoscopic pair (Marseille area, France) and the corresponding disparity (right) Table 1. Comparison of computation time for MH, TCP and TCPIS. MH TCP TCPIS CPU time (sec.) 642571 55454 1326
the importance sampling algorithm (TCPIS) allows to reduce again the computation time, by a factor 40. The overall computation time is still relatively large (a few hours for our case study), but the TCPIS algorithm allows a tremendous gain in comparison with crude sampling algorithms. The application we aim at is the detection of possible large errors; that is, given an error threshold s, which are the pixels for which disparity errors larger than s are likely to occur? This is typically the type of questions one may face in applications in the aircraft industry. This problem can be formulated as the computation of the probability P (D− dˆ ≥ s), and, for a given risk α, the location ˆ v) ≥ s) ≤ α, which correspond to of the pixels (u, v) for which P (D(u, v) − d(u, the safe area. Figure 4 displays the probability maps obtained for s = 2 and s = 3. The probability of errors varies strongly with the location (u, v), that is why usual methods estimating error ranges over a large domain are not appropriate for such applications. It is then possible to threshold these maps to a given risk value, say 0.1%, to identify the safe areas. In real applications however, it is not realistic to consider that such information is required for every pixel. For example, if one thinks of an object in motion over a domain, then one must guarantee that no collision occurs along
108
J. S´en´egas
Fig. 4. Probability map of positive errors larger than 2 (left) and 3 (right) pixels. One scale unit on the vertical axis equals 10%.
its trajectory. Hence, we need to consider a whole domain, and compute the probability that no error greater than a given threshold s occurs in this domain, with a probability 1 − α. Since errors are spatially correlated, this is not equal to the product of the corresponding probabilities over the domain. We point out that this type of computation definitely requires the knowledge of the entire multivariate distribution πD and not only the marginal distribution of a given pixel. For this purpose, we divided the disparity map in 64 sub-domains of equal surface, and computed the probability that errors larger than 3 (respectively 4) pixels occur anywhere in the sub-domain (Fig. 5). Thus, as previously, it is possible to determine the safe areas as the sub-domains for which this probability is lower than α = 0.1%. The results obtained are rather pessimistic: the 3 pixel threshold map has only 2 safe domains, this contrasts with the situation we would have expected from the right map displayed on Fig. 4. This surprising result emphasizes the importance of spatial correlations and justifies the use of Monte Carlo methods, although they are computationally demanding. We consider now the opposite situation, which is often encountered in practice: a risk value α is given, and one needs to compute a confidence interval [Zinf , Zsup ] for the variable Z such that P (Z ∈ [Zinf , Zsup ]) ≥ 1 − α. An example of the use of confidence intervals in a different context of computer vision can be found in [17]. To derive a confidence interval, we propose to make use of the min and max of the disparity samples. Indeed, for n + 1 independent identically distributed random variables Zi , we have the following result: P (Zn+1 ∈ [min Zi , max Zi ]) = i≤n
i≤n
n−1 n+1
(15)
A Markov Chain Monte Carlo Approach to Stereovision
109
Fig. 5. Probability map of positive errors larger than 3 (left) and 4 (right) pixels in a subdomain. One scale unit on the vertical axis equals 10%.
Therefore, for any risk value α, we can choose the smallest integer n such that n−1 n+1 ≥ 1 − α and compute for each pixel the min and the max of the n samples. The confidence interval has then the form of two embedding surfaces. In order to validate our results, we have used a reference disparity map obtained from high resolution images, which has been degraded to the SPOT resolution. Using this reference map, it is possible to compute the percentage of points lying in the confidence interval computed previously and to compare this value to the theoretical value given by 15. The risk value was set equal to 0.1%, and therefore we used n = 2000 samples to construct the confidence interval. From the reference map, we found that 0.11% of the total points fell outside the confidence interval, which is in very good agreement with the theoretical value 0.1%. Moreover, the mean size over the grid of the computed disparity interval is 4.4 pixels: although the risk value is very small, the precision given by the confidence interval is reasonable. Therefore, the method proposed in this paper allows to compute accurate statistics.
5
Conclusion
In this paper, we have considered the problem of assessing the uncertainty of a disparity map with only the use of the stereoscopic pair as information. Since the usual standard deviation approach does not permit to handle the case of large errors which occur with very low probability and are spatially correlated, specific methods have to be proposed. A solution consists of computing the posterior distribution of the disparity given the stereoscopic pair. Hence, uncertainty assessment amounts to sample from this posterior distribution and to compute the desired probabilities using a Monte Carlo approach. From a
110
J. S´en´egas
practical point of view, a model for the posterior distribution must be chosen, and an efficient sampling algorithm must be used to keep the computation time reasonable. This method is very general and can be applied to different types of stereovision systems, but the choice of the stochastic model is specific to the application. The model explicited in this paper considers an application to the computation of mid-resolution digital terrain models, for which the disparity map can be assumed to vary relatively smoothly and the gaussian assumption is reasonable. For more complex applications, models which take explicitly into account the geometry of the scene may be more appropriate. An important problem is the choice of the sampling algorithm. The algorithm we propose considers the case of gaussian priors, which is quite general. It is based on the construction of a continuous path of possible transitions, and compared to standard sampling algorithms such as the independence sampler proves very competitive. Moreover, we have shown that the computation can be tremendously speeded up by first running the Markov chain on a subgrid and then generating conditionally the samples on the whole grid. This Markov chain Monte Carlo approach has been applied to the study of a stereoscopic pair of SPOT images. The results show that the disparity statistics are highly non-stationary. This is due to the nature of the radiometric information itself. These statistics can be used to determine the safe areas, for which large errors occur with probability inferior to a given risk value, or to compute precise confidence intervals. The range of applications is however brighter: for example, they may be used to optimize a functional over the domain under study. We think especially of the motion of an object in a three-dimensional environment, for which the path to a given target has to be optimized and collisions avoided.
References [1] P.N. Belhumeur. A Bayesian approach to binocular stereopsis. International Journal of Computer Vision, 19(3):237–262, 1996. [2] J. Besag. On the statistical analysis of dirty pictures (with discussion). J. Roy. Statist. Soc. Ser. B, 48:259–302, 1986. [3] J. Besag, P. Green, D. Higdon, and K. Mengersen. Bayesian computation and stochastic systems. Statistical Science, 10(1):3–66, 1995. [4] C. Chang and S. Chatterjee. Multiresolution stereo - A Bayesian approach. IEEE International Conference on Pattern Recognition, 1:908–912, 1990. [5] J.P. Chil`es and P. Delfiner. Geostatistics: Modeling Spatial Uncertainty. Wiley and Sons, 1999. [6] I.J. Cox. A maximum likelihood n-camera stereo algorithm. International Conference on Computer Vision and Pattern Recognition, pages 733–739, 1994. [7] F. Dellaert, S. Seitz, S. Thrun, and C. Thorpe. Feature correspondance: A Markov chain Monte Carlo approach. In Advances in Neural Information Processing Systems 13, pages 852–858, 2000.
A Markov Chain Monte Carlo Approach to Stereovision
111
[8] F. Devernay and O. Faugeras. Automatic calibration and removal of distorsions from scenes of structured environments. In Leonid I. Rudin and Simon K. Bramble, editors, Investigate and Trial Image Processing, Proc. SPIE, volume 2567. SPIE, San Diego, CA, 1995. [9] U.R. Dhond and J.K. Aggarwal. Structure from stereo - A review. IEEE Transactions on systems, man and cybernetics, 19(6):1489–1510, 1989. [10] O. Faugeras. Three-Dimensional Computer Vision. Massachussets Institute of Technology, 1993. [11] D. Forsyth, S. Ioffe, and J. Haddon. Bayesian structure from motion. In International Conference on Computer Vision, volume 1, pages 660–665, 1999. [12] L. Garcin, X. Descombes, H. Le Men, and J. Zerubia. Building detection by markov object processes. In Proceedings of ICIP’01, Thessalonik, Greece, 2001. [13] S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6):721–741, 1984. [14] W.R. Gilks, S. Richardson, and D.J. Spiegelhalter. Markov Chain Monte Carlo in Practice. Chapman and Hall, 1996. [15] W.K. Hastings. Monte carlo sampling methods using Markov chains and their applications. Biometrika, 57:97–109, 1970. [16] T. Kanade and M. Okutomi. A stereo matching algorithm with an adaptive window: Theory and experiment. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(9), september 1994. [17] R. Mandelbaum, G. Kamberova, and M. Mintz. Stereo depth estimation: a confidence interval approach. In International Conference on Computer Vision, pages 503–509, 1998. [18] S.P. Meyn and R.L. Tweedie. Markov Chains and Stochastic Stability. SpringerVerlag London, 1993. [19] G.O. Roberts and J.S. Rosenthal. Optimal scaling of discrete approximations to Langevin diffusions. J. Roy. Statist. Soc. Ser. B, 60:255–268, 1998. [20] J.J. Rodriguez and J.K. Aggarwal. Stochastic analysis of stereo quantization error. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(5):467–470, 1990. [21] J. S´en´egas, M. Schmitt, and P. Nonin. Conditional simulations applied to uncertainty assessment in DTMs. In G. Foody and P. Atkinson, editors, Uncertainty in Remote Sensing and GIS. Wiley and Sons, 2002. to appear. [22] R. Stoica, X. Descombes, and J. Zerubia. Road extraction in remote sensed images using a stochastic geometry framework. In Proceedings of MaxEnt’00, Gif Sur Yvette, July 8-13, 2000. [23] R. Szeliski. Bayesian Modeling of Uncertainty in Low-level Vision. Kluwer Academic Publishers, 1989. [24] R.L. Tweedie. Markov chains: Structure and applications. In B. N. Shanbhag and C.R. Rao, editors, Handbook of Statistics 19, pages 817–851. Elsevier Amsterdam, 1998.
A Probabilistic Theory of Occupancy and Emptiness Rahul Bhotika1 , David J. Fleet2 , and Kiriakos N. Kutulakos3 1
Computer Science Department, University of Rochester Rochester, NY 14627, USA
[email protected] 2 Palo Alto Research Center, Palo Alto CA 94304, USA
[email protected] 3 Computer Science Department, University of Toronto Toronto, ON M5S3G4, Canada
[email protected]
Abstract. This paper studies the inference of 3D shape from a set of n noisy photos. We derive a probabilistic framework to specify what one can infer about 3D shape for arbitrarily-shaped, Lambertian scenes and arbitrary viewpoint configurations. Based on formal definitions of visibility, occupancy, emptiness, and photo-consistency, the theoretical development yields a formulation of the Photo Hull Distribution, the tightest probabilistic bound on the scene’s true shape that can be inferred from the photos. We show how to (1) express this distribution in terms of image measurements, (2) represent it compactly by assigning an occupancy probability to each point in space, and (3) design a stochastic reconstruction algorithm that draws fair samples (i.e., 3D photo hulls) from it. We also present experimental results for complex 3D scenes.
1
Introduction
Many applications, from robotics [1] to computer graphics [2] and virtual reality, rely on probabilistic representations of occupancy to express uncertainty about the physical layout of the 3D world. While occupancy has an intuitive and well-defined physical interpretation for every 3D point (i.e., a point is occupied when the scene’s volume contains it), little is known about what probabilistic information regarding occupancy is theoretically computable from a set of n noisy images. In particular, what information about the occupancy and emptiness of space is intrinsic to a set of n stochasticallygenerated photos taken at arbitrary viewpoints? Importantly, how can we answer this question for general scenes whose shape is arbitrary and unknown? This paper outlines a general probabilistic theory of occupancy and emptiness for Lambertian scenes that is intended to handle arbitrary 3D shapes, arbitrary viewpoint configurations and noisy images. Based on formal definitions of several key concepts, namely, visibility, occupancy, emptiness and photo-consistency, our theoretical development yields a formulation of the Photo Hull Distribution. The Photo Hull Distribution is the tightest probabilistic bound on the scene’s true shape that can be inferred from the n input photos. Importantly, we show that the theory leads directly to a stochastic algorithm that (1) draws fair samples from the Photo Hull Distribution and (2) converges