Efficient Validation of Matching Hypotheses
using Mahalanobis Distance
J.M.M. Montiel and L. Montano
Dpto. Informática e Ingeniería de Sistemas Centro Politécnico Superior.
University of Zaragoza, María de Luna 3, E50015 Zaragoza Spain,
Tel. 34 (976) 76 19 75, Fax. 34 (976) 76 18 61
The validation of matching hypotheses using Mahalanobis distance is extensively utilized in robotic applications, and in general dataassociation techniques. The Mahalanobis distance, defined by the innovation and its covariance, is compared with a threshold defined by the chisquare distribution to validate a matching hypothesis; the validation test is a timeconsuming operation. This paper presents an efficient computation for this test. The validation test implies a computational overhead for two reasons: first, because of covariance matrix inversion, and second because the computation of the covariance and innovation terms are also expensive operations, in fact, more expensive than the inversion itself. The method described here can be summarized as an incremental, nondecreasing computation for the Mahalanobis distance; if the incrementally computed value exceeds the threshold then the computation is stopped. The elements of covariance and innovation, and the matrix inversion itself, are only computed if they are used; progressivity is the major advantage of the method. The method is based upon the squarerootfree Cholesky's factorization. In addition, a lower bound for the Mahalanobis distance is proposed. This lower bound has two advantages: it can be progressively computed, and it is greater than the classical trace lower bound.
Key words: Mahalanobis distance, dataassociation, gate validation, matching.