EFFICIENT VALIDATION OF MATCHING HYPOTHESES USING MAHALANOBIS DISTANCE

The validation of matching hypotheses using Mahalanobis distance is ex tensively utilized in robotic applications, and in general data-associ ation techniques. The Mahalanobis distance, defined by the innovation and its covariance, is compared with a threshold defined by the chi-sq uared distribution to validate a matching hypothesis; the validation t est is a time-consuming operation. This paper presents an efficient co mputation for this test. The validation test implies a computational o verhead 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 in cremental, non-decreasing computation for the Mahalanobis distance; if the incrementally computed value exceeds the threshold then the compu tation is stopped. The elements of covariance and innovation, and the matrix inversion itself, are only computed if they are used; progressi vity is the major advantage of the method. The method is based upon th e square-root-free Cholesky's factorization. In addition, a lower boun d for the Mahalanobis distance is proposed. This lower bound has two a dvantages: it can be progressively computed, and it is greater than th e classical trace lower bound. (C) 1998 Elsevier Science Ltd. All righ ts reserved.