Geometry-Driven Diffusion in Computer Vision Computational Imaging and Vision Managing Editor: MAX A. VIERGEVER Utrecht University, Utrecht, The Netherlands Editorial Board: OLIVIER D. FAUGERAS, INRIA, Sophia-Antipolis, France JAN J. KOENDERINK, Utrecht University, Utrecht, The Netherlands STEPHEN M. PIZER, University of North Carolina, Chapel Hili, USA SABURO TSUJI, Osaka University, Osaka, Japan STEVEN W. ZUCKER, McGill University, Montnial, Canada Volume 1 Geometry-Driven Diffusion in Computer Vision Edited by Bart M. ter Haar Romeny 3D Computer Vision Research Group. Utrecht University. Utrecht, The Netherlands SPRINGER-SCIENCE+BUSINESS MEDIA, B.Y. Library of Congress Calaloging-in-Publication Data Geometry-driven diffusion in computer vision I edited by Bart M. ter Haar Romeny. p. cm. -- (Computational imaging and vision i v. 1) Inc 1 udes index. ISDN 978-90-481-4461-7 ISBN 978-94-017-1699-4 (eBook) DOI 10.1007/978-94-017-1699-4 1. Computer viSlon. 2. Geometry. 3. Image processing- -Mathematlcs. 1. Haar Romeny, Bart M. ter. II. Series. TA1634.G47 1994 006.4'2'01516--dc20 94-31768 CIP ISBN 978-90-481-4461-7 Reprinted 1999 03-0199-100-ts Printed on acid-frec paper 02-0897 -90 ts AII Rights Reserved © 1994 Springer Science+Business Media Dordrecht OriginalIy published by Kluwer Academic Publishers in 1994 No part of thc material protected by this copyright notice may be reproduced or utilized in any form ar by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner. Table of Contents Preface xiii Foreword xvii Contributors xxi 1 LINEAR SCALE-SPACE I: BASIC THEORY 1 Tony Lindeberg and Bart M. ter Haar Romeny 1 Introduction. . . . . . . . . . . . . .. . 1 1.1 Early visual operations .... . 3 2 M ulti-scale representation of image data 3 3 Early multi-scale representations 5 3.1 Quad tree . 6 3.2 Pyramids ........ . 7 4 Linear scale-space ....... . 10 5 Towards formalizing the scale-space concept 13 5.1 Continuous signals: Original formulation . 13 5.2 Inner scale, outer scale and scale-space 14 j 5.3 Causality ................. . 15 5.4 Non-creation of local extrema ...... . 16 5.5 Semi-group and continuous scale parameter 17 5.6 Scale invariance and the Pi theorem .... 18 5.7 Other special properties of the Gaussian kernel 24 6 Gaussian derivative operators . . . . . . . . . . . . . . 24 6.1 Infinite differentiability ............ . 27 6.2 Multi-scale N-jet representation and necessity . 27 6.3 Scale-space properties of Gaussian derivatives . 28 6.4 Directional derivatives . . . .. 29 7 Discrete scale-space. . . . . . . . . . . . . . . . . . . 29 7.1 N on-creation of local extrema . . . . . . . . . 29 7.2 Non-enhancement and infinitesimal generator 33 7.3 Discrete derivative approximations ..... . 35 8 Scale-space operators and front-end vision . . . . . . 35 8.1 Scale-space: A canonical visual front-end model . 36 8.2 Relations to biological vision 36 8.3 Foveal vision ................... . 37 vi 2 LINEAR SCALE-SPACE II: EARLY VISUAL OPERATIONS 39 Tony Lindeberg and Bart M. ter Haar Romeny 1 Introduetion ................ . 39 2 Multi-seale feature deteetion in seale-spaee ....... 40 2.1 Differential geometry and differential invariants . 40 2.2 Feature deteetion from differential singularities 44 2.3 Seale selection ................. 49 2.4 Cues to surfaee shape (texture and disparity) 52 3 Behaviour aeross seales: Deep strueture .. . . . . . 54 3.1 Iso-intensity linking .......... 54 0 • • • 3.2 Feature based linking (differential singularities) 55 3.3 Bifureations in seale-spaee ....... 57 0 4 Seale sampling 57 0 0 •• 0 •••• 0 • 0 ••••• 0 4.1 Natural seale parameter: Effective seale 58 5 Regularization properties of seale-spaee kern eis 59 6 Related multi-seale representations 60 6.1 Wavelets ... 60 0 •• 0 •• 0 ••• 0 • • 6.2 Tuned seale-spaee kern eIs . . . . . . 61 7 Behaviour aeross seales: Statistieal analysis 63 7.1 Deereasing number of Ioeal e~rema 63 7.2! Noise propagation in seale-spaee derivatives 64 8 Non-uniform smoothing ......... 67 0 • • • • • 8.1 Shape distortions in eomputation of surfaee shape. 67 8.2 Outlook ......... 69 0 • • • • • • • • • • • • • • 9 Appendix: Mathematiea example 4th-order junction deteetor 71 3 ANISOTROPIC DIFFUSION 73 Pietro Perona, Takahiro Shiota and Jitendra Malik 1 Introduetion ................... . 73 2 Anisotropie diffusion . . . . . . . . . . . . . . . 77 3 Implementation and diserete maximum principle 79 4 Edge Enhaneement ............... . 86 5 Continuous model and well-posedness question 88 4 VECTOR-VALUED DIFFUSION 93 Ross Whitaker and Guido Gerig 1 Introduetion ....... 93 0 0 2 Vector-valued diffusion .. . 94 2.1 Veetor-valued images. 94 vii 2.2 Diffusion with multiple features. . . . . . . . . . 94 2.3 Diffusion in a feature space . . . . . . . . . . . . 95 2.4 Application: Noise reduction in multi-echo MRI . 99 3 Geometry-limited diffusion. . . . . . . . 102 4 The Iocal geometry of grey-scale images 103 5 Diffusion of Image Derivatives. . 103 6 First-order geometry and creases . 105 6.1 Creases........... 105 6.2 A shape metric for creases . 107 6.3 Results........... 109 6.4 The diffused Hessian . . . . 111 6.5 Application: Characterization of blood vessel centerlines 112 6.6 Application: Characterization of sulcogyral pattern of - the human brain . . . . . . . . . . . . . . . . . . . . . 113 6.7 Combining information of zero and first-order - corners 115 7 Invariance............ 116 7.1 Geometrie invariance. . . . . . 116 7.2 Higher-order geometry . . . . . 119 8 Spectra-limited diffusion and text ure . 119 8.1 Texture . . . . . . . . . . . . . 120 8.2 Blurring the envelopes of functions 123 8.3 Variable-cond uctance diffusion . 125 8.4 Patchwise Fourier decomposition 128 8.5 Multi-valued diffusion 130 8.6 Dissimilarity 131 8.7 Results 132 9 Conclusions..... 133 5 BAYESIAN RATIONALE FOR THE VARIATIONAL FORMULATION 135 David Mumford 1 Introduction ....... . 135 2 Four Probabilistic Models 137 2.1 The Ising model . 137 2.2 The Cartoon Model 138 2.3 The Theater Wing Model 141 2.4 The Spectrogram Model . 143 viii 6 VARIATIONAL PROBLEMS WITH A FREE DISCONTINUITY SET 147 Antonio Leaci and Sergio Solimini 1 Introduction ......... . 147 2 Main questions about the functional 148 3 Density estimates .... 149 4 Rectifiability estimates . . . . . . . . 151 7 MINIMIZATION OF ENERGY FUNCTIONAL WITH CURVE-REPRESENTED EDGES 155 Niklas Nordström 1 Introduction .................. . 155 1.1 The Mumford and Shah Problem .. . 156 1.2 The Fixed Discontinuity Set Problem 156 1.3 Outline of the Existence Proof . 158 1.4 Admissible Image Segments ..... . 159 1.5 Admissible Image Segmentations .. . 162 1.6 Compact Image Segmentation Spaces 164 1.7 Concluding Remarks ......... . 166 8 APPROXIMATION, COMPUTATION, AND DISTORTION IN THE VARIATIONAL FORMULATION 169 Thomas Riehardson and Sanjoy Mitter 1 Introduction ............ . 169 2 Approximation via r-Convergence 172 3 Minimizing Ec •..•••...•• 176 4 Remarks on Energy Functionals, Associated Non-Linear Diffusions and Stochastic Quantization . 178 5 Scale, Noise, and Accuracy ..... . 179 6 Edge Focusing via Scaling . . . . . . . 182 7 Discretization and Parameter Choices 184 8 Simulation Results . . . . . . . . . . . 187 9 COUPLED GEOMETRY-DRIVEN DIFFUSION EQUATIONS FOR LOW-LEVEL VISION 191 Mare Proesmans, Erie Pauwels and Lue van Gool 1 Introduction and basic philosophy ............... 191 1.1 Energy minimization and systems of coupled diffusion equations ..................... '. ... 191 1X 1.2 Harnessing Perona & Malik's anisotropie diffusion 194 1.3 Systems of eoupled geometry-driven diffusions. 197 2 Diffusion based on seeond order smoothing ...... . 199 2.1 Introduction ................... . 199 2.2 Diffusion and edge-enhancing using seeond-order smoothing .......... . 200 2.3 Extension to two dimensions 202 3 Applieation to multispeetral images 204 4 Application to optical ftow 206 4.1 Introduction ........ . 206 4.2 The optical ftow equations .. 207 4.3 Sueeessive approximation of the velocity field 209 4.4 Diseontinuities and non-linear diffusion 212 4.5 Integration...... 214 4.6 Experimental Results ......... . 215 5 Applieation to stereo .............. . 221 5.1 The simplified ease of a ealibrated stereo rig . 221 5.2 Extension to a general disparity field . 223 6 Conclusion ...................... . 227 10 MORPHOLOGICAL APPROACH TO MULTISCALE ANALYSIS: FROM PRINCIPLES TO EQUATIONS 229 Luis Alvarez and Jean-Michel Morel 1 Introduction........... 229 2 Image multiseale analysis . . . 231 2.1 A short story of the subject 231 2.2 The visual pyramid as an algorithm 232 2.3 What is the input of the visual pyramid ? 232 2.4 What is the output of the visual pyramid ? 233 2.5 What basic principles must obey the visual pyramid? 234 3 Axiomatization ofimage multiscale analysis and classification of the main models. .................. 237 4 Shape multiscale analyses . . . . . . . . . . . . . . . . 240 4.1 The fundamental equation of Shape Analysis 241 5 Relation between image and shape multiscale analyses 242 6 Multiscale segmentation . . . . . . . . . . . . . . . . . 243 7 Movies multiscale analysis . . . . . . . . . . . . . . . . 246 1 Appendix A. The "fundamental theorem" of image analysis .. 250 2 Appendix B. Proof of the scale normalization lemma.. . 251 3 Appendix C. Classification of shape multiseale analyses. . .. 253 x 11 DIFFERENTIAL INVARIANT SIGNATURES AND FLOWS IN COMPUTER VISION: A SYMMETRY GROUP APPROACH 255 Peter Olver, Guillermo Sapiro and Allen Tannenbaum 1 Introduetion ............. . · 256 2 Basie Invariant Theory. . ..... . · 258 2.1 Veetor Fields and One-Forms · 258 2.2 Lie Groups ..... . · 260 2.3 Prolongations .... . · 271 2.4 Differential Invariants .277 3 Invariant Flows . . . . . . . . · 280 3.1 Special Differential Invariants . · 280 3.2 Geometrie Invariant Flow Formulation . · 282 3.3 Uniqueness of Invariant Heat Flows · 285 3.4 Euelidean Invariant Flows . · 289 3.5 Affine Invariant Flows ....... . · 290 3.6 Projeetive Invariant Flows ..... . · 293 3.7 Similarity and Full Affine Invariant Flows · 296 4 Geometrie Heat Flows Without Shrinkage · 298 4.1 Area Preserving Euelidean Flow · 299 4.2 Area Preserving Affine Flow . · 301 4.3 Length Preserving Flows. . · 303 5 Invariant Geometrie Surfaee Flows · 304 6 Conclusions . . . . . . . . . . . . . · 306 12 ON OPTIMAL CONTROL METHODS IN COMPUTER VISION AND IMAGE PROCESSING 307 Benjamin Kimia, Allen Tannenbaum and Steven Zucker 1 Introduetion ............................ 308 2 Generalized or "Weak" Solutions of Conservation Equations . 309 3 Hamilton-Jaeobi Equation . . 310 3.1 Viseosity Solutions . . . . . . . . . . . . . 313 3.2 Eikonal Equation . . . . . . . . . . . . . . 314 3.3 Derivation of Hamilton-Jaeobi Equation . 316 4 Optieal Flow ..... . . . . . . . . . . . . . . . 317 4.1 Euler-Lagrange equation for optieal fiow . . 318 5 Shape-from-Shading....... . 319 6 Computational Theory of Shape . 322 6.1 Evolution Equations . . . . 323 6.2 Conservation Laws . . . . . 325 6.3 Diffusion Equation and Image Smoothing . 328