Unsupervised thresholds for shape matching

Shape recognition systems usually order a fixed number of best matches to each query, but do not address or answer the two following questions: Is a query shape in a given database ? How can we be sure that a match is correct ? This communication deals with these two key points. A database being given, with each shape S and each distance δ, we associate its number of false alarms NFA(S, δ), namely the expectation of the number of shapes at distance δ in the database. Assume that NFA(S, δ) is very small with respect to 1, and that a shape S′ is found at distance δ from S in the database. This match could not occur just by chance and is therefore a meaningful detection. Its explanation is usually the common origin of both shapes. Experimental evidence will show that NFA(S, δ) can be predicted accurately.