A Theory of Shape Identification

Front Cover
Springer Science & Business Media, Aug 28, 2008 - Mathematics - 264 pages
2 Reviews

Recent years have seen dramatic progress in shape recognition algorithms applied to ever-growing image databases. They have been applied to image stitching, stereo vision, image mosaics, solid object recognition and video or web image retrieval. More fundamentally, the ability of humans and animals to detect and recognize shapes is one of the enigmas of perception.

The book describes a complete method that starts from a query image and an image database and yields a list of the images in the database containing shapes present in the query image. A false alarm number is associated to each detection. Many experiments will show that familiar simple shapes or images can reliably be identified with false alarm numbers ranging from 10-5 to less than 10-300. 

Technically speaking, there are two main issues. The first is extracting invariant shape descriptors from digital images. Indeed, a shape can be seen from various angles and distances and in various lights. A shape can even be partially occluded by other shapes and still be identifiable. Because the extraction step is so crucial, three acknowledged shape descriptors, SIFT, MSER and LLD, are introduced.

The second issue is deciding whether two shape descriptors are identifiable as the same shape or not. A perceptual principle, the Helmholtz principle, is the cornerstone of this decision. It asserts that two shapes can be identified if the probability, that their resemblance may be due to chance, is very small. Not only may this principle be useful in this identification step, but it is also used throughout the complete system that will be presented: from the extraction of shape descriptors in digital images to their grouping in whole shapes.

These decisions rely on elementary stochastic geometry and compute a false alarm number. The lower this number, the more secure the identification. The description of the processes, the many experiments on digital images and the simple proofs of mathematical correctness are interlaced so as to make a reading accessible to various audiences, such as students, engineers, and researchers.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
1
12 Shape Invariants and Consequences
4
13 General Overview
9
132 Shape Element Encoding
11
134 Grouping
12
Extracting Image boundaries
13
Extracting Meaningful Curves from Images
15
22 Matas et al Maximally Stable Extremal Regions MSER
17
72 A Contrario Cluster Validity
131
722 Meaningful Groups
132
73 Optimal Merging Criteria
136
74 Computational Issues
140
742 Indivisibility and Maximality
142
Object Grouping Based on Elementary Features
143
751 Segments
144
752 DNA Image
146

23 Meaningful Boundaries
18
232 Maximal Boundaries
19
24 A Mathematical Justification of Meaningful Contrasted Boundaries
21
25 Multiscale Meaningful Boundaries
26
26 Adapting Boundary Detection to Local Contrast
27
261 Local Contrast
29
262 Experiments on Locally Contrasted Boundaries
30
27 Bibliographic Notes
32
272 Meaningful Boundaries vs Haralicks Detector
33
273 Level Lines and Shapes
34
274 Tree of Shapes FLST and MSER
35
Level Line Invariant Descriptors
36
Robust Shape Directions
40
311 Flat Parts Detection Algorithm
42
312 Reduction to a Parameterless Method
43
313 The Algorithm
44
32 Experiments
45
322 Flat Parts Correspond to Salient Features
47
33 Curve Smoothing and the Reduction of the Number of Bitangent Lines
49
34 Bibliographic Notes
54
342 ScaleSpace and Curve Smoothing
57
Invariant Level Line Encoding
61
412 Application to the MSER Normalization Method
64
413 Geometric Global Normalization Methods
65
42 SemiLocal Normalization and Encoding
66
421 Similarity Invariant Normalization and Encoding Algorithm
67
422 Affine Invariant Normalization and Encoding Algorithm
70
423 Typical Number of LLDs in Images
71
43 Bibliographic Notes
73
432 Global Features and Global Normalization
74
433 Local and SemiLocal Features
75
Recognizing Level Lines
78
A Contrario Decision the LLD Method
81
512 Detection Terminology
83
52 The Background Model
85
521 Deriving Statistically Independent Features from Level Lines
87
53 Testing the Background Model
89
54 Bibliographic Notes
91
542 A Contrario Methods
92
Meaningful Matches Experiments on LLD and MSER
93
611 A Toy Example
94
612 Perspective Distortion
98
613 A More Difficult Problem
101
614 Slightly Meaningful Matches between Unrelated Images
104
615 Camera Blur
105
62 Recognition Relative to Context
113
63 Testing A Contrario MSER Global Normalization
116
633 Global Matches of NonLocally Encoded LLDs
118
Grouping Shape Elements
126
Hierarchical Clustering and Validity Assessment
129
76 Bibliographic Notes
148
Grouping Spatially Coherent Meaningful Matches
150
82 Describing Transformations
153
822 The Affine Transformation Case
154
83 Meaningful Transformation Clusters
155
the Similarity Case
157
84 Experiments
158
85 Bibliographic Notes
161
Experimental Results
167
92 Experiments
168
922 Valbonne Church
173
93 Occlusions
177
94 Stroboscopic Effect
179
The SIFT Method
183
The SIFT Method
184
1011 ScaleSpace Extrema
186
1012 Accurate Key Point Detection
187
1013 Orientation Assignment
188
1014 Local Image Descriptor
189
102 Shape Element Stability versus SIFT Stability
190
1022 Experiments
191
1023 Some Conclusions Concerning Stability
195
103 SIFT Descriptors Matching versus LLD A Contrario Matching
196
1031 Measuring Matching Performance
198
1032 Experiments
201
104 Conclusion
207
1053 Matching and Grouping
208
Securing SIFT with A Contrario Techniques
209
112 Using a Background Model for SIFT
210
113 Meaningful SIFT Matching
214
1132 Matching
215
1133 Choosing Sample Points
218
114 The Detection Algorithm
219
Securing SIFT Detections
220
115 Bibliographic Notes
224
Keynotes
225
A12 Iterative Methods for Partitional Clustering
227
A13 Hierarchical Clustering Methods
228
A14 Cluster Validity Analysis and Stopping Rules
231
A2 Three classical methods for object detection based on spatial coherence
235
A22 Geometric Hashing
236
A23 A RANSACbased Approach
237
A3 On the Negative Association of Multinomial Distributions
239
Algorithms
243
B2 Improved MSER Method Summary
244
B3 Improved SIFT Method Summary
245
References
247
Index
255
Copyright

Other editions - View all

Common terms and phrases

About the author (2008)

Jean-Michel Morel (PhD 1980) is Professor of Applied Mathematics at the Ecole Normale Supérieure de Cachan since 1997. He started his career in 1979 as assistant professor in Marseille Luminy, then moved in 1984 to University Paris Dauphine where he was promoted professor in 1992. His research is focused since 1990 on the mathematical analysis of image analysis and processing. He has received the Philip Morris Prize of Mathematics (1991), the Junior Institut Universitaire de France (1992), Prix Sciences et Défense (1996), Classe exceptionnelle 2001 and three IEEE best paper awards (ICIP 97, ICASSP 05, and CVPR 05.) He has coauthored with S. Solimini a book on Variational Methods in Image Segmentation (Birkhäuser 1994) and with Agnès Desolneux and Lionel Moisan a book on Computation Gestalt Theory (Springer, 2008). He has advised 31 PhD’s and is associate editor of five journals in applied mathematics and image analysis. He is also the editor in charge of Applied Mathematics for Springer Lecture Notes of Mathematics. Since 2002, Jean-Michel Morel belongs to the ISI list of highly cited mathematicians (http://isihighlycited.com/).

Frédéric Sur is assistant professor of mathematics and computer science at Ecole des Mines de Nancy and conducts his research at Loria laboratory. His research interest is computer vision, from low-level features definition to structure and motion problems. He defended his PhD thesis in applied mathematics and image analysis in 2004 at Ecole Normale Supérieure de Cachan. Then he held a postdoctoral position on statistical learning theory at Loria.

José-Luis Lisani received the Ph.D.degree on applied mathematics by the Universities of Paris-Dauphine (France) and of Illes Balears (Spain) in 2001. He is currently assistant professor of applied mathematics at the University of Illes Balears (Spain) and collaborates with the CMLA laboratory at ENS Cachan (France) and Cognitech Inc. (USA). His current research interests include image and video processing with applications to video-surveillance, database indexing and 3D images analysis.

Pablo Musé received the Ph.D. degree in applied mathematics from Ecole Normale Supérieure de Cachan, France, in 2004. From 2005 to 2006 he was with Cognitech, Inc., Pasadena, CA, USA, where he worked on computer vision and image processing applications. Then he held a postdoctoral position on applied mathematics at the Seismological Laboratory, California Institute of Technology. Since 2008, he has been an assistant professor of electrical engineering at the Facultad de Ingeniería, Universidad de la República, Uruguay. His research interests include signal and image processing and analysis.

Frédéric Cao is researcher in applied mathematics and computer vision, with INRIA, France. He obtained a PhD in 2000, then successively worked for the French Defence Agency, INRIA (National Institute of research in Computer Science), Cognitech Inc. He is currently with DxO Labs, as Research Director. His topics of research are shape recognition, motion analysis or digital photography. He is author of a book on geometric curve evolution and image processing, published as a volume of Lecture Notes in Mathematics, Springer.