Mathematical Optimization in Computer Graphics and Vision
Regular price
30.500 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Contentsv
- List of Figuresxv
- Prefacexxi
- Acknowledgmentsxxiv
- Chapter 1. Computer Graphics1
- 1.1 What is Computer Graphics?1
- 1.1.1 Related Areas2
- 1.1.2 Is There Something Missing?4
- 1.2 Mathematical Modeling and Abstraction Paradigms6
- 1.2.1 Terrain Representation9
- 1.2.2 Image Representation10
- 1.3 Graphical Objects12
- 1.3.1 Revisiting the Diagram15
- 1.4 Description, Representation, and Reconstruction15
- 1.4.1 Description16
- 1.4.2 Representation17
- 1.4.3 Reconstruction17
- 1.4.4 Semantics and Reconstruction20
- 1.5 Comments and References21
- Bibliography24
- Chapter 2. Optimization: An Overview25
- 2.1 What is Optimization?25
- 2.1.1 Classification of Optimization Problems27
- 2.2 Classification Based on the Nature of Solution28
- 2.2.1 Continuous Optimization Problems28
- 2.2.2 Discrete Optimization Problems29
- 2.2.3 Combinatorial Optimization Problems31
- 2.2.4 Variational Optimization Problems32
- 2.3 Other Classifications33
- 2.3.1 Classification Based on Constraints33
- 2.3.2 Classification Based on the Objective Function34
- Linear Programs34
- 2.4 The Problem of Posing Problems35
- 2.4.1 Well-Posed Problems36
- 2.4.2 Problem Reduction40
- 2.5 How to Solve It?40
- 2.5.1 Global Versus Local Solutions41
- 2.5.2 NP3-Complete Problems41
- 2.6 Comments and References41
- Bibliography42
- Chapter 3. Optimization and Computer Graphics43
- 3.1 A Unified View of Computer Graphics Problems43
- 3.1.1 The Classification Problem44
- 3.2 Geometric Modeling46
- 3.2.1 Model Reconstruction47
- 3.3 Visualization48
- 3.4 Computer Vision49
- 3.5 The Virtual Camera50
- 3.5.1 Camera Specification52
- 3.6 Image Processing53
- 3.6.1 Warping and Morphing54
- 3.7 Image Analysis57
- 3.7.1 Edge Detection58
- 3.7.2 Character Recognition60
- 3.8 Animation and Video61
- 3.9 Comments and References62
- Bibliography62
- Chapter 4. Variational Optimization63
- 4.1 Variational Problems63
- 4.1.1 Solve the Variational Problem Directly66
- 4.1.2 Reduce to a Continuous Optimization Problem66
- 4.1.3 Reduce to a Discrete Optimization Problem67
- 4.2 Applications in Computer Graphics68
- 4.2.1 Variational Modeling of Curves68
- 4.3 Comments and References76
- Bibliography76
- Chapter 5. Continuous Optimization77
- 5.1 Optimality Conditions79
- 5.1.1 Convexity and Global Minima85
- 5.2 Least Squares87
- 5.2.1 Solving Least Squares Problems90
- 5.3 Algorithms92
- 5.3.1 Newton’s Method92
- 5.3.2 Unidimensional Search Algorithms94
- 5.3.3 Conjugate Gradient96
- 5.3.4 Quasi-Newton Algorithms97
- 5.3.5 The Levenberg–Marquardt Algorithm98
- 5.4 Constrained Optimization101
- 5.4.1 Optimality Conditions101
- 5.4.2 Least Squares with Linear Constraints104
- 5.4.3 Algorithms105
- Penalty and Barrier Methods106
- Projected Gradient Methods108
- 5.5 Linear Programming109
- 5.5.1 Simplex Algorithm for Linear Programs113
- 5.5.2 The Complexity of the Simplex Method114
- 5.6 Applications in Graphics115
- 5.6.1 Camera Calibration115
- 5.6.2 Registration and Color Correction for a Sequence of Images121
- 5.6.3 Visibility for Real-Time Walk-Through124
- 5.7 Comments and References127
- Bibliography128
- Chapter 6. Combinatorial Optimization133
- 6.1 Introduction133
- 6.1.1 Solution Methods in Combinatorial Optimization134
- 6.1.2 Computational Complexity136
- 6.2 Description of Combinatorial Problems137
- 6.2.1 Graphs137
- 6.2.2 Adjacency Matrix138
- 6.2.3 Incidence Matrix139
- 6.2.4 Networks140
- 6.3 Dynamic Programming141
- 6.3.1 Constructing the State of the Problem145
- 6.3.2 Remarks About General Problems146
- 6.3.3 Problems of Resource Allocation147
- Knapsack Problem147
- 6.4 Shortest Paths in Graphs148
- 6.4.1 Shortest Paths in Acyclic Oriented Graphs148
- 6.4.2 Directed Graphs Possibly with Cycles149
- Definition of the Problem150
- 6.4.3 Dijkstra Algorithm151
- 6.5 Integer Programming152
- 6.5.1 Linear and Integer Programming153
- 6.5.2 Minimum Cost Flow Problem154
- 6.5.3 Linear Programs with Integer Solutions155
- Specific cases156
- 6.6 Graph Cuts156
- 6.6.1 Equivalence Between Min-Cut and Max-Flow157
- 6.6.2 The Labeling Problem159
- 6.6.3 Representing Energy Functions with Graphs160
- 6.6.4 The Expansion-Move Algorithm163
- 6.7 Branch-and-Bound Methods167
- 6.7.1 Characteristics168
- 6.8 Applications in Computer Graphics168
- 6.8.1 Image Quantization169
- Quantization170
- Quantization Using Dynamic Programming173
- Final Remarks175
- 6.8.2 Interactive Visualization177
- Optimization of Level of Details180
- Final Remarks184
- 6.8.3 Shortest Paths184
- Shortest Paths in Neighborhood Graphs186
- Final Remarks188
- 6.8.4 Surface Reconstruction188
- Some Definitions188
- Optimization Methods for Contour Reconstruction189
- Final Remarks194
- 6.8.5 Stereo194
- The Geometry of Stereo Reconstruction195
- Stereo correspondence with graph cuts198
- Final Remarks202
- 6.9 Comments and References203
- Bibliography204
- Chapter 7. Global Optimization209
- 7.1 Two Extremes209
- 7.2 Local Search210
- 7.3 Stochastic Relaxation211
- 7.4 Genetic Algorithms212
- 7.4.1 Genetic and Evolution212
- 7.4.2 Genetic Algorithms for Optimization213
- 7.4.3 The Traveling Salesman Problem215
- 7.4.4 Optimization of a Univariate Function216
- 7.5 Guaranteed Global Optimization218
- 7.5.1 Branch-and-Bound Methods220
- 7.5.2 Accelerating Interval Branch-and-Bound Methods222
- 7.5.3 Constrained Optimization223
- 7.6 Range Analysis224
- 7.6.1 Interval Arithmetic226
- The Dependency Problem228
- 7.6.2 Affine Arithmetic229
- 7.7 Examples in Computer Graphics232
- 7.7.1 Designing a Stable Table232
- 7.7.2 Curve Fitting233
- 7.7.3 Collision Detection235
- 7.7.4 Surface Intersection236
- 7.7.5 Implicit Curves and Surfaces236
- 7.7.6 Adaptive Approximation of Parametric Surfaces239
- 7.8 Comments and References241
- Bibliography243
- Chapter 8. Probability and Optimization245
- 8.1 Background245
- 8.1.1 The Second Law of Thermodynamics245
- 8.1.2 Information and Measures248
- 8.2 Information Theory249
- 8.2.1 Basic Principles249
- 8.2.2 Properties of Entropy251
- 8.3 Measuring Mutual Information253
- 8.3.1 Conditional Entropy253
- 8.3.2 Mutual Information255
- 8.3.3 Divergence256
- 8.3.4 Continuous Random Variables257
- 8.4 Optimization and Entropy258
- 8.4.1 Principle of Maximum Entropy„MaxEnt258
- 8.4.2 Distributions Obtained with MaxEnt261
- 8.4.3 Principles of Optimization by Entropy263
- 8.5 Applications265
- 8.5.1 Symbol Coding265
- 8.5.2 Decision Trees267
- 8.6 Comments and References268
- Bibliography269
- Index271
Mathematical optimization is used in nearly all computer graphics applications, from computer vision to animation. This book teaches readers the core set of techniques that every computer graphics professional should understand in order to envision and expand the boundaries of what is possible in their work.
Study of this authoritative reference will help readers develop a very powerful tool- the ability to create and decipher mathematical models that can better realize solutions to even the toughest problems confronting computer graphics community today.
*Distills down a vast and complex world of information on optimization into one short, self-contained volume especially for computer graphics
*Helps CG professionals identify the best technique for solving particular problems quickly, by categorizing the most effective algorithms by application
*Keeps readers current by supplementing the focus on key, classic methods with special end-of-chapter sections on cutting-edge developments
Study of this authoritative reference will help readers develop a very powerful tool- the ability to create and decipher mathematical models that can better realize solutions to even the toughest problems confronting computer graphics community today.
*Distills down a vast and complex world of information on optimization into one short, self-contained volume especially for computer graphics
*Helps CG professionals identify the best technique for solving particular problems quickly, by categorizing the most effective algorithms by application
*Keeps readers current by supplementing the focus on key, classic methods with special end-of-chapter sections on cutting-edge developments