Efficient validation of matching hypotheses using Mahalanobis distance

The validation of matching hypotheses using Mahalanobis distance is extensively utilized in robotic applications, and in general data-association techniques. The Mahalanobis distance, defined by the innovation and its covariance, is compared with a threshold defined by the chi-squared distribution to validate a matching hypothesis; the validation test is a time-consuming 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, non-decreasing 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 square-root-free 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. (C) 1998 Elsevier Science Ltd. All rights reserved.