Preface ......................................................... v
1 Introduction ................................................. 1
1.1 Gestalt Theory and Computer Vision ...................... 1
1.2 Basic Principles of Computer Vision ..................... 3
2 Gestalt Theory .............................................. 11
2.1 Before Gestaltism: Optic-Geometric Illusions ........... 11
2.2 Grouping Laws and Gestalt Principles ................... 13
2.2.1 Gestalt Basic Grouping Principles ............... 13
2.2.2 Collaboration of Grouping Laws .................. 17
2.2.3 Global Gestalt Principles ....................... 19
2.3 Conflicts of Partial Gestalts and the Masking
Phenomenon ............................................. 21
2.3.1 Conflicts ....................................... 21
2.3.2 Masking ......................................... 22
2.4 Quantitative Aspects of Gestalt Theory ................. 25
2.4.1 Quantitative Aspects of the Masking
Phenomenon ...................................... 25
2.4.2 Shannon Theory and the Discrete Nature of
Images .......................................... 27
2.5 Bibliographic Notes .................................... 29
2.6 Exercise ............................................... 29
2.6.1 Gestalt Essay ................................... 29
3 The Helmholtz Principle ..................................... 31
3.1 Introducing the Helmholtz Principle: Three Elementary
Examples ............................................... 31
3.1.1 A Black Square on a White Background ............ 31
3.1.2 Birthdays in a Class and the Role of
Expectation ..................................... 34
3.1.3 Visible and Invisible Alignments ................ 36
3.2 The Helmholtz Principle and ε-Meaningful Events ........ 37
3.2.1 A First Illustration: Playing Roulette with
Dostoievski ..................................... 39
3.2.2 A First Application: Dot Alignments ............. 41
3.2.3 The Number of Tests ............................. 42
3.3 Bibliographic Notes .................................... 43
3.4 Exercise ............................................... 44
3.4.1 Birthdays in a Class ............................ 44
4 Estimating the Binomial Tail ................................ 47
4.1 Estimates of the Binomial Tail ......................... 47
4.1.1 Inequalities for  (l,k,p) ....................... 49
4.1.2 Asymptotic Theorems for {1,k,p) =  [S1 ≥ k] .... 50
4.1.3 A Brief Comparison of Estimates for (l,k,p) .... 50
4.2 Bibliographic Notes .................................... 52
4.3 Exercises .............................................. 52
4.3.1 The Binomial Law ................................ 52
4.3.2 Hoeffding's Inequality for a Sum of Random
Variables ....................................... 53
4.3.3 A Second Hoeffding Inequality ................... 55
4.3.4 Generating Function ............................. 56
4.3.5 Large Deviations Estimate ....................... 57
4.3.6 The Central Limit Theorem ....................... 60
4.3.7 The Tail of the Gaussian Law .................... 63
5 Alignments in Digital Images ................................ 65
5.1 Definition of Meaningful Segments ...................... 65
5.1.1 The Discrete Nature of Applied Geometry ......... 66
5.1.2 The A Contrario Noise Image ..................... 67
5.1.3 Meaningful Segments ............................. 70
5.1.4 Detectability Weights and Underlying
Principles ...................................... 72
5.2 Number of False Alarms ................................. 74
5.2.1 Definition ...................................... 74
5.2.2 Properties of the Number of False Alarms ........ 75
5.3 Orders of Magnitudes and Asymptotic Estimates .......... 76
5.3.1 Sufficient Condition of Meaningfulness .......... 77
5.3.2 Asymptotics for the Meaningfulness Threshold
k(l) ............................................ 78
5.3.3 Lower Bound for the Meaningfulness Threshold
k(l) ............................................ 80
5.4 Properties of Meaningful Segments ...................... 81
5.4.1 Continuous Extension of the Binomial Tail ....... 81
5.4.2 Density of Aligned Points ....................... 83
5.5 About the Precision p .................................. 86
5.6 Bibliographic Notes .................................... 87
5.7 Exercises .............................................. 91
5.7.1 Elementary Properties of the Number of False
Alarms .......................................... 91
5.7.2 A Continuous Extension of the Binomial Law ...... 91
5.7.3 A Necessary Condition of Meaningfulness ......... 92
6 Maximal Meaningfulness and the Exclusion Principle .......... 95
6.1 Introduction ........................................... 95
6.2 The Exclusion Principle ................................ 97
6.2.1 Definition ...................................... 97
6.2.2 Application of the Exclusion Principle to
Alignments ...................................... 98
6.3 Maximal Meaningful Segments ........................... 100
6.3.1 A Conjecture About Maximality .................. 102
6.3.2 A Simpler Conjecture ........................... 103
6.3.3 Proof of Conjecture 1 Under Conjecture 2 ....... 105
6.3.4 Partial Results About Conjecture 2 ............. 106
6.4 Experimental Results .................................. 109
6.5 Bibliographical Notes ................................. 112
6.6 Exercise .............................................. 113
6.6.1 Straight Contour Completion .................... 113
7 Modes of a Histogram ....................................... 115
7.1 Introduction .......................................... 115
7.2 Meaningful Intervals .................................. 115
7.3 Maximal Meaningful Intervals .......................... 119
7.4 Meaningful Gaps and Modes ............................. 122
7.5 Structure Properties of Meaningful Intervals .......... 123
7.5.1 Mean Value of an Interval ...................... 123
7.5.2 Structure of Maximal Meaningful Intervals ...... 124
7.5.3 The Reference Interval ......................... 126
7.6 Applications and Experimental Results ................. 127
7.7 Bibliographic Notes ................................... 129
7.8 Exercises ............................................. 129
7.8.1 Kullback-Leibler Distance ...................... 129
7.8.2 A Qualitative a Contrario Hypothesis ........... 130
8 Vanishing Points ........................................... 133
8.1 Introduction .......................................... 133
8.2 Detection of Vanishing Points ......................... 133
8.2.1 Meaningful Vanishing Regions ................... 134
8.2.2 Probability of a Line Meeting a Vanishing
Region ......................................... 135
8.2.3 Partition of the Image Plane into Vanishing
Regions ........................................ 137
8.2.4 Final Remarks .................................. 141
8.3 Experimental Results .................................. 144
8.4 Bibliographic Notes ................................... 145
8.5 Exercises ............................................. 150
8.5.1 Poincare-Invariant Measure on the Set of
Lines .......................................... 150
8.5.2 Perimeter of a Convex Set ...................... 150
8.5.3 Crofton's Formula ..............................
9 Contrasted Boundaries ...................................... 153
9.1 Introduction .......................................... 153
9.2 Level Lines and the Color Constancy Principle ......... 153
9.3 A Contrario Definition of Contrasted Boundaries ....... 159
9.3.1 Meaningful Boundaries and Edges ................ 159
9.3.2 Thresholds ..................................... 162
9.3.3 Maximality ..................................... 163
9.4 Experiments ........................................... 164
9.5 Twelve Objections and Questions ....................... 168
9.6 Bibliographic Notes ................................... 174
9.7 Exercise .............................................. 175
9.7.1 The Bilinear Interpolation of an Image ......... 175
10 Variational or Meaningful Boundaries? ...................... 177
10.1 Introduction .......................................... 177
10.2 The "Snakes" Models ................................... 177
10.3 Choice of the Contrast Function g ..................... 180
10.4 Snakes Versus Meaningful Boundaries ................... 185
10.5 Bibliographic Notes ................................... 188
10.6 Exercise .............................................. 188
10.6.1 Numerical Scheme ............................... 188
11 Clusters ................................................... 191
11.1 Model ................................................. 191
11.1.1 Low-Resolution Curves .......................... 191
11.1.2 Meaningful Clusters ............................ 193
11.1.3 Meaningful Isolated Clusters ................... 193
11.2 Finding the Clusters .................................. 194
11.2.1 Spanning Tree .................................. 194
11.2.2 Construction of a Curve Enclosing a Given
Cluster ........................................ 194
11.2.3 Maximal Clusters ............................... 196
11.3 Algorithm ............................................. 196
11.3.1 Computation of the Minimal Spanning Tree ....... 196
11.3.2 Detection of Meaningful Isolated Clusters ...... 197
11.4 Experiments ........................................... 198
11.4.1 Hand-Made Examples ............................. 198
11.4.2 Experiment on a Real Image ..................... 198
11.5 Bibliographic Notes ................................... 198
11.6 Exercise .............................................. 201
11.6.1 Poisson Point Process .......................... 201
12 Binocular Grouping ......................................... 203
12.1 Introduction .......................................... 203
12.2 Epipolar Geometry ..................................... 204
12.2.1 The Epipolar Constraint ........................ 204
12.2.2 The Seven-Point Algorithm ...................... 204
12.3 Measuring Rigidity .................................... 205
12.3.1 F-rigidity ..................................... 205
12.3.2 A Computational Definition of Rigidity ......... 206
12.4 Meaningful Rigid Sets ................................. 207
12.4.1 The Ideal Case (Checking Rigidity) ............. 207
12.4.2 The Case of Outliers ........................... 208
12.4.3 The Case of Nonmatched Points .................. 210
12.4.4 A Few Remarks .................................. 214
12.5 Algorithms ............................................ 215
12.5.1 Combinatorial Search ........................... 215
12.5.2 Random Sampling Algorithm ...................... 216
12.5.3 Optimized Random Sampling Algorithm (ORSA) ..... 217
12.6 Experiments ........................................... 217
12.6.1 Checking All Matchings ......................... 217
12.6.2 Detecting Outliers ............................. 219
12.6.3 Evaluation of the Optimized Random Sampling
Algorithm ...................................... 219
12.7 Bibliographic Notes ................................... 222
12.7.1 Stereovision ................................... 222
12.7.2 Estimating the Fundamental Matrix from Point
Matches ........................................ 223
12.7.3 Robust Methods ................................. 224
12.7.4 Binocular Grouping ............................. 224
12.7.5 Applications of Binocular Grouping ............. 225
12.8 Exercise .............................................. 225
12.8.1 Epipolar Geometry .............................. 225
13 A Psychophysical Study of the Heimholtz Principle .......... 227
13.1 Introduction .......................................... 227
13.2 Detection of Squares .................................. 227
13.2.1 Protocol ....................................... 227
13.2.2 Prediction ..................................... 228
13.2.3 Results ........................................ 230
13.2.4 Discussion ..................................... 231
13.3 Detection of Alignments ............................... 231
13.3.1 Protocol ....................................... 232
13.3.2 Prediction ..................................... 233
13.3.3 Results ........................................ 233
13.4 Conclusion ............................................ 234
13.5 Bibliographic Notes ................................... 235
14 Back to the Gestalt Programme .............................. 237
14.1 Partial Gestalts Computed So Far ...................... 237
14.2 Study of an Example ................................... 240
14.3 The Limits of Every Partial Gestalt Detector .......... 242
14.3.1 Conflicts Between Gestalt Detectors ............ 242
14.3.2 Several Straight Lines or Several Circular
Arcs? .......................................... 244
14.3.3 Influence of the A-contrario Model ............. 246
14.4 Bibliographic Notes ................................... 247
15 Other Theories, Discussion ................................. 249
15.1 Lindenbaum's Theory ................................... 249
15.2 Compositional Model and Image Parsing ................. 250
15.3 Statistical Framework ................................. 252
15.3.1 Hypothesis Testing ............................. 252
15.3.2 Various False Alarms or Error Rates Compared
to NFA ......................................... 253
15.3.3 Comparison with Signal Detection Theory ........ 254
15.4 Asymptotic Thresholds ................................. 255
15.5 Should Probability Be Maximized or Minimized? ......... 256
References .................................................... 261
Index ......................................................... 271
|
