 | A theory of shape identification / Cao F., Lisani J.-L., Morel J.-M., Muse P., Sur F.; ed. by Morel J.-M., Takens F., Teissier B. - Berlin, Heidelberg: Springer-Verlag, 2008. - 257 p.: ill. - (Lecture notes in mathematics; 1948). - Ref.: p.247-254. - Ind.: p.255-257. - ISBN 978-3-540-68480-0; ISSN 0075-8434
|
1. Introduction ................................................. 1
1.1. A Single Principle ...................................... 1
1.2. Shape Invariants and Consequences ....................... 4
1.2.1. Shape Distortions ................................ 4
1.3. General Overview ........................................ 9
1.3.1. Extraction of Shape Elements ..................... 9
1.3.2. Shape Element Encoding .......................... 11
1.3.3. Recognition of Shape Elements ................... 11
1.3.4. Grouping ........................................ 12
1.3.5. Algorithm Synopsis .............................. 12
Part I Extracting Image boundaries
2. Extracting Meaningful Curves from Images .................... 15
2.1. The Level Lines Tree, or Topographic Map ............... 15
2.2. Matas et al. Maximally Stable Extremal Regions
(MSER) ................................................. 17
2.3. Meaningful Boundaries .................................. 18
2.3.1. Contrasted Boundaries ........................... 18
2.3.2. Maximal Boundaries .............................. 19
2.4. A Mathematical Justification of Meaningful
Contrasted Boundaries .................................. 21
2.4.1. Interpretation of the Number of False Alarms .... 21
2.5. Multiscale Meaningful Boundaries ....................... 26
2.6. Adapting Boundary Detection to Local Contrast .......... 27
2.6.1. Local Contrast .................................. 29
2.6.2. Experiments on Locally Contrasted Boundaries .... 30
2.7. Bibliographic Notes .................................... 32
2.7.1. Edge Detection .................................. 32
2.7.2. Meaningful Boundaries vs. Haralick's Detector ... 33
2.7.3. Level Lines and Shapes .......................... 34
2.7.4. Tree of Shapes, FLST, and MSER .................. 35
2.7.5. Extracting Shapes from Images ................... 35
Part II Level Line Invariant Descriptors
3. Robust Shape Directions ..................................... 41
3.1. Flat Parts of Level Lines .............................. 41
3.1.1. Flat Parts Detection Algorithm .................. 42
3.1.2. Reduction to a Parameterless Method ............. 43
3.1.3. The Algorithm ................................... 44
3.1.4. Some Properties of the Detected Flat Parts ...... 44
3.2. Experiments ............................................ 45
3.2.1. Experimental Validation of the Flat Part
Algorithm ....................................... 45
3.2.2. Flat Parts Correspond to Salient Features ....... 47
3.3. Curve Smoothing and the Reduction of the Number
of Bitangent Lines ..................................... 49
3.4. Bibliographic Notes .................................... 54
3.4.1. Detecting Flat Parts in Curves .................. 54
3.4.2. Scale-Space and Curve Smoothing ................. 57
4. Invariant Level Line Encoding ............................... 61
4.1. Global Normalization and Encoding ...................... 61
4.1.1. Global Affine Normalization ..................... 61
4.1.2. Application to the MSER Normalization Method .... 64
4.1.3. Geometric Global Normalization Methods .......... 65
4.2. Semi-Local Normalization and Encoding .................. 66
4.2.1. Similarity Invariant Normalization and
Encoding Algorithm .............................. 67
4.2.2. Affine Invariant Normalization and Encoding
Algorithm ....................................... 70
4.2.3. Typical Number of LLDs in Images ................ 71
4.3. Bibliographic Notes .................................... 73
4.3.1. Geometric Invariance and Shape Recognition ...... 73
4.3.2. Global Features and Global Normalization ........ 74
4.3.3. Local and Semi-Local Features ................... 75
Part III Recognizing Level Lines
5. A Contrario Decision: the LLD Method ........................ 81
5.1. A Contrario Models ..................................... 81
5.1.1. Shape Model or Background Model? ................ 81
5.1.2. Detection Terminology ........................... 83
5.2. The Background Model ................................... 85
5.2.1. Deriving Statistically Independent Features
from Level Lines ................................ 87
5.3. Testing the Background Model ........................... 89
5.4. Bibliographic Notes .................................... 91
5.4.1. Shape Distances ................................. 91
5.4.2. A Contrario Methods ............................. 92
6. Meaningful Matches: Experiments on LLD and MSER ............. 93
6.1. Semi-Local Meaningful Matches .......................... 93
6.1.1. A Toy Example ................................... 94
6.1.2. Perspective Distortion .......................... 98
6.1.3. A More Difficult Problem ....................... 101
6.1.4. Slightly Meaningful Matches between
Unrelated Images ............................... 104
6.1.5. Camera Blur .................................... 105
6.2. Recognition Relative to Context ....................... 113
6.3. Testing A Contrario MSER (Global Normalization) ....... 116
6.3.1. Global Affine Invariant Recognition. A Toy
Example ........................................ 116
6.3.2. Comparing Similarity and Affine Invariant
Global Recognition Methods ..................... 116
6.3.3. Global Matches of Non-Locally Encoded LLDs ..... 118
Part IV Grouping Shape Elements
7. Hierarchical Clustering and Validity Assessment ............ 129
7.1. Clustering Analysis ................................... 129
7.2. A Contrario Cluster Validity .......................... 131
7.2.1. The Background Model ........................... 131
7.2.2. Meaningful Groups .............................. 132
7.3. Optimal Merging Criteria .............................. 136
7.3.1. Local Merging Criterion ........................ 136
7.4. Computational Issues .................................. 140
7.4.1. Choosing Test Regions .......................... 140
7.4.2. Indivisibility and Maximality .................. 142
7.5. Experimental Validation: Object Grouping Based
on Elementary Features ................................ 143
7.5.1. Segments ....................................... 144
7.5.2. DNA Image ...................................... 146
7.6. Bibliographic Notes ................................... 148
8. Grouping Spatially Coherent Meaningful Matches ............. 151
8.1. Why Spatial Coherence Detection? ...................... 151
8.2. Describing Transformations ............................ 153
8.2.1. The Similarity Case ............................ 153
8.2.2. The Affine Transformation Case ................. 154
8.3. Meaningful Transformation Clusters .................... 155
8.3.1. Measuring Transformation Dissimilarity ......... 155
8.3.2. Background Model: the Similarity Case .......... 157
8.4. Experiments ........................................... 158
8.5. Bibliographic Notes ................................... 161
9. Experimental Results ....................................... 167
9.1. Visualizing the Results ............................... 167
9.2. Experiments ........................................... 168
9.2.1. Multiple Occurrences of a Logo ................. 168
9.2.2. Valbonne Church ................................ 173
9.2.3. Tramway ........................................ 175
9.3. Occlusions ............................................ 177
9.4. Stroboscopic Effect ................................... 179
Part V The SIFT Method
10.The SIFT Method ............................................ 185
10.1.A Short Guide to SIFT Encoding ........................ 185
10.1.1.Scale-Space Extrema ............................ 186
10.1.2.Accurate Key Point Detection ................... 187
10.1.3.Orientation Assignment ......................... 188
10.1.4.Local Image Descriptor ......................... 189
10.1.5.SIFT Descriptor Matching ....................... 189
10.2.Shape Element Stability versus SIFT Stability ......... 190
10.2.1.An Experimental Protocol ....................... 190
10.2.2.Experiments .................................... 191
10.2.3.Some Conclusions Concerning Stability .......... 195
10.3.SIFT Descriptors Matching versus LLD A Contrario
Matching .............................................. 196
10.3.1. Measuring Matching Performance ................ 198
10.3.2. Experiments ................................... 201
10.4.Conclusion ............................................ 207
10.5.Bibliographic Notes ................................... 207
10.5.1.Interest Points of an Image .................... 207
10.5.2.Local Descriptors .............................. 207
10.5.3.Matching and Grouping .......................... 208
11.Securing SIFT with A Contrario Techniques .................. 209
11.1.A Contrario Clustering of SIFT Matches ................ 209
11.2.Using a Background Model for SIFT ..................... 210
11.3.Meaningful SIFT Matching .............................. 214
11.3.1.Normalization .................................. 214
11.3.2.Matching ....................................... 215
11.3.3.Choosing Sample Points ......................... 218
11.4.The Detection Algorithm ............................... 219
11.4.1.Experiments: Securing SIFT Detections .......... 220
11.5.Bibliographic Notes ................................... 224
A. Keynotes ................................................... 225
A.l. Cluster Analysis Reader's Digest ...................... 225
A.l.l. Partitional Clustering Methods ................. 225
A.1.2. Iterative Methods for Partitional Clustering ... 227
A.1.3. Hierarchical Clustering Methods ................ 228
A.2. Three classical methods for object detection based
on spatial coherence .................................. 235
A.2.1. The Generalized Hough Transform ................ 235
A.2.2. Geometric Hashing .............................. 236
A.2.3. A RANSAC-based Approach ........................ 237
A.3. On the Negative Association of Multinomial
Distributions ......................................... 239
В. Algorithms ................................................. 243
B.l. LLD Method Summary .................................... 243
B.2. Improved MSER Method Summary .......................... 244
B.3. Improved SIFT Method Summary .......................... 245
References .................................................... 247
Index ......................................................... 255
|
|
