A Theory of Shape Identification

    Contents




    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 Topographie Map                          15
         2.2 Matas et al. Maximally Stahle 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 Bibliographie 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




v jjj                                                                     Contents

Part II Level Line Invariant Descriptors

3       Robust Shape Directions                                                  41
        3.1 Fiat Parts of Level Lines                                            41
            3.1.1 Fiat 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 Fiat Parts                     44
        3.2 Experiments                                                          45
            3.2.1 Experimental Validation of the Fiat Part Algorithm             45
            3.2.2 Fiat Parts Correspond to Salient Features                      47
        3.3 Curve Smoothing and the Reduction of the Number
            of Bitangent Lines                                                   49
        3.4 Bibliographie Notes                                                  54
            3.4.1 Detecting Fiat 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 Geometrie 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 Bibliographie Notes                                                  73
             4.3.1 Geometrie Invariance and Shape Recognition                    73
             4.3.2 Global Features and Global Normalization                      74
             4.3.3 Local and Semi-Local Features                                 75

 Part HI 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 Bibliographie Notes                                                  91
            5.4.1 Shape Distances                                                91
            5.4.2 A Contrario Methods                                             92
Contents                                                                     ix

6    Meaningful Matches: Experiments on LLD and MSER                         93
     6.1 Semi-Local Meaningful Matches                                       93
         6.1.1 AToyExample                                                   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 Bibliographie 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 Bibliographie Notes                                                161
                                                                        Contents
x



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

PartV 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 Bibliographie 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 Bibliographie Notes                                              224
Contents                                                                  xi

A    Keynotes                                                            225
     A. 1 Cluster Analysis Reader's Digest                               225
          A.1.1 Partitional Clustering Methods                           225
          A.1.2 Iterative Methods for Partitional Clustering             227
          A.1.3 Hierarchical Clustering Methods                          228
          A.1.4 Cluster Validity Analysis and Stopping Rules             231
     A.2 Three classical methods for object detection based on spatial
          coherence                                                      235
          A.2.1 The Generalized Hough Transform                          235
          A.2.2 Geometrie Hashing                                        236
          A.2.3 A RANSAC-based Approach                                  237
     A.3 On the Negative Association of Multinomial Distributions        239

B    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