Shape Reconstruction from Apparent Contours: Theory and Algorithms

Contents
Introduction
	References
1 A Variational Model on Labelled Graphs with Cuspsand Crossings
	1.1 The Reconstruction Problem
	1.2 The Mumford–Shah Model
	1.3 The Nitzberg–Mumford Model
	1.4 Other Curvature-Depending Functionals
	1.5 The Variational Model on Labelled Graphs
	References
2 Stable Maps and Morse Descriptions of an Apparent Contour
	2.1 Stability of Maps
	2.2 Stable Maps from a Two-Manifold to the Plane
	2.3 Ambient Isotopies
	2.4 Ambient Isotopic and Diffeomorphically Equivalent Apparent Contours
	2.5 Morse Descriptions of an Apparent Contour
		2.5.1 Genericity of Morse Lines in Case of No Cusps
		2.5.2 Morse Lines in Case of Cusps: Markers
		2.5.3 The Morse Description
		2.5.4 Recovering the Shape from a Morse Description
	References
3 Apparent Contours of Embedded Surfaces
	3.1 Three-Dimensional Scenes
		3.1.1 Splitting of R3
	3.2 Apparent Contours of Embedded Surfaces
	3.3 The Function f
	3.4 Labelling an Apparent Contour: The Function d-Sigma
	3.5 Ambient Isotopic and Diffeomorphically Equivalent Labelled Apparent Contours
	3.6 Visible Contours
	References
4 Solving the Completion Problem
	4.1 Some Concepts from Graph Theory
		4.1.1 Contour Graphs and Visible Contour Graphs
	4.2 Complete Contour Graphs and Labelling
	4.3 Statement of the Completion Theorem
	4.4 Morse Descriptions of a Visible Contour Graph
		4.4.1 Localization
	4.5 Proof of the Completion Theorem
		4.5.1 Analysis at the Global Maximum and at Local Maxima
		4.5.2 Analysis at Terminal Points
		4.5.3 Analysis at T-Junctions
		4.5.4 Analysis at Local Minima and at the GlobalMinimum
	4.6 Examples
	References
5 Topological Reconstruction of a Three-Dimensional Scene
	5.1 Statement of the Reconstruction Theorem
		5.1.1 Depth-Equivalent Scenes
	5.2 Proof of Existence
		5.2.1 Glueing
		5.2.2 Smooth Local Embedding of T in R3
		5.2.3 Smooth Global Embedding of M in R3
			5.2.3.1 Partition of Unity
		5.2.4 Definition of the 3D-Shape
	5.3 Proof of Uniqueness
	5.A Appendix
	References
6 Completeness of Reidemeister-Type Moves on Labelled Apparent Contours
	6.1 Moves on a Labelled Apparent Contour
		6.1.1 List of All Simple Rules
	6.2 Stratifications and Stratified Morse Functions
		6.2.1 Stratifications Induced by a Stable Map
	6.3 Informal Statement
	6.4 Rigorous Statement
	6.5 Proof of the Completeness Theorem
	6.6 Completeness of Moves
	References
7 Invariants of an Apparent Contour
	7.1 Definition of B(appcon(phi))
	7.2 Definition of BL(appcon(φ))
	7.3 Coincidence Between B(appcon(phi)) and BL(appcon(φ))
		7.3.1 Proof of Coincidence Up to a Constant
		7.3.2 Proof of Coincidence
	7.4 Euler–Poincaré Characteristic of dE
	7.5 Cell Complexes and Fundamental Groups
		7.5.1 Cell Complexes
		7.5.2 Fundamental Groups
	7.6 Alexander Polynomials and Invariantsof Fundamental Groups
	7.7 Free Differential Calculus
	7.8 Links with Two Components: Deficiency One
	7.9 Surfaces with Genus 2: Deficiency Two
	References
8 Elimination of Cusps
	8.1 Embedding Sign of a Cusp
	8.2 Connectable Cusps in an Open Set
	8.3 Statement of the Elimination Theorem
	8.4 Proof of the Elimination Theorem
	8.5 Application to Closed Embedded Surfaces
	References
9 The Program ``Visible\'\'
	9.1 An Example
	9.2 Encoding a Morse Description of the Visible Contour
		9.2.1 Encoding the Morse Events
		9.2.2 Implicit Orientation
		9.2.3 The ``e\'\' Region Marking
	9.3 Using the Program
	9.4 Encoding a Morse Description of the Constructed Apparent Contour
	9.5 Some Examples
	Reference
10 The Program ``Appcontour\'\': User\'s Guide
	10.1 An Overview of the Software
	10.2 Region Description
		10.2.1 Extended Arcs
			10.2.1.1 Streaming the Description of an Arc
		10.2.2 Describing a Region
			10.2.2.1 Streaming the Description of a Region
		10.2.3 Completeness of the Region Description
	10.3 Encoding an Apparent Contour with Labelling
		10.3.1 Region Description as a Stream of Characters
		10.3.2 Morse Description
		10.3.3 Knot Description
	10.4 The Rules (Reidemeister-Type Moves)
		10.4.1 Simple Rules
			10.4.1.1 The K Rules (kasanie)
			10.4.1.2 The T Rules
			10.4.1.3 The L Rule (Lip)
			10.4.1.4 The B Rule (Beak-to-Beak)
			10.4.1.5 The S Rule (Swallow\'s Tail)
			10.4.1.6 The C Rule (Cusp-Fold)
		10.4.2 A Nonlocal Effect of the B Rule
		10.4.3 Composite Rules
			10.4.3.1 The CR0 Composite Rule (B-1S)
			10.4.3.2 The CR1 Composite Rule
			10.4.3.3 The CR2 Composite Rule
			10.4.3.4 The CR3 Composite Rules
			10.4.3.5 The CR4 Composite Rules
			10.4.3.6 The A1 Composite Rule
			10.4.3.7 The A2 Composite Rule
			10.4.3.8 The TI Composite Rule
		10.4.4 Inverse Rules
	10.5 Surgeries on Apparent Contours
		10.5.1 Vertical Surgery
		10.5.2 Horizontal Surgery
	10.6 Canonical Description and Comparison
		10.6.1 On the Isomorphism Problem for Graphs
		10.6.2 The ``Regions\'\' Graph: R-Graph
		10.6.3 The Depth-First Search of an R-Graph
		10.6.4 The Canonization Procedure
			10.6.4.1 Canonical Description of an Extended Arc
			10.6.4.2 Sorting Non-Equivalent Arcs
			10.6.4.3 Using DFS and Lexicographic Comparison
			10.6.4.4 Sorting Regions and Arcs
			10.6.4.5 Postprocessing
		10.6.5 Comparison of Apparent Contours
	10.7 Fundamental Groups and Cell Complexes
		10.7.1 Computing the Euler–Poincaré Characteristic and the Number of Connected Components
		10.7.2 Fundamental Groups
		10.7.3 Invariants of Finitely Presented Groups and the Alexander Polynomial
		10.7.4 Alexander Polynomials and Alexander Ideals in Two Indeterminates
			10.7.4.1 Canonization of a Laurent Polynomial
			10.7.4.2 Canonization of a Laurent Ideal
	10.8 The Mendes Graph
	10.9 Invariants
		10.9.1 Euler–Poincaré Characteristic
		10.9.2 Bennequin Invariant
		10.9.3 Examples of Invariants Computation
			10.9.3.1 Projective Plane
			10.9.3.2 Milnor Curve and Millett Immersion
			10.9.3.3 Torus
			10.9.3.4 A knotted Genus-2 Surface
	10.10 contour Reference Guide
		10.10.1 Informational Commands
		10.10.2 Operating Commands
		10.10.3 Conversion and Standardization Commands
		10.10.4 Cell Complex and Fundamental Group Commands
		10.10.5 Options Specific to Fundamental GroupComputations
		10.10.6 Common Options
		10.10.7 Direct Input of a Finitely Presented Group or an Alexander Ideal
	10.11 showcontour Reference Guide
		10.11.1 Producing a Proper Morse Description
		10.11.2 From the Morse description to a polygonal drawing
		10.11.3 Discrete Optimization of the Polygonal Drawing
		10.11.4 Dynamic Smoothing of the Polygonal
	10.12 Using contour in Scripts
		10.12.1 contour_interact.sh
		10.12.2 contour_describe.sh
		10.12.3 contour_transform.sh
	10.13 Example: knotted Surface of Genus 2
	10.14 Example: Knots in a Solid Torus
	10.15 Example: Klein Bottle and the ``House with Two Rooms\'\'
	10.16 Example: Mixed Internal/External Knot
	10.17 Using appcontour on Apparent Contours WithoutLabelling
		10.17.1 Haefliger Sphere
		10.17.2 Boy Surface
		10.17.3 Milnor Curve
		10.17.4 Millett curve
		10.17.5 Klein bottle
	10.A Appendix: Practical Canonization of Laurent Polynomials
		10.A.1 One-Dimensional Support
		10.A.2 Two-Dimensional Support
	References
11 Variational Analysis of the Model on Labelled Graphs
	11.1 The Action Functional
		11.1.1 Graphs with Cusps and Curvature in Lp
		11.1.2 The Functional
		11.1.3 A Notion of Convergence
	11.2 Lower Semicontinuity
	11.3 On the Lower Semicontinuous Envelope of the Action
		11.3.1 Limits of Labellings
		11.3.2 Sufficient Conditions: An Example
	11.A Appendix A: Systems of Curves
		11.A.1 Curves of Class pwrcp
		11.A.2 Systems of Curves
		11.A.3 Parametrizations of Complete Contour Graphs
	11.B Appendix B: Convergence and Compactnessof Systems of Curves
		11.B.1 Convergence
	References
Nomenclature
Index