System and method for improving the precision of localization estimates

• US 6,970,796 B2
• Filed: 03/01/2004
• Issued: 11/29/2005
• Est. Priority Date: 03/01/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tashev, Ivan
• Primary Examiner(s): Nghiem, Michael
• Assistant Examiner(s): LE, JOHN H
• Application Number:
  US10/791,252
• Publication Number:
  US 20050192768A1
• Time in Patent Office: 638 Days
• Field of Search: 702/85, 702/94, 702/95, 702/127, 702/150, 702/188, 342/450, 382/128, 382/239, 382/243, 382/284, 414/788.1, 435/6
• US Class Current: 702/94
• CPC Class Codes: G01S 7/00 Details of systems according to groups G01S13/00, G01S15/00, G01S17/00

Abstract

Precision and reliability of localization estimates derived from conventional localization systems are improved through a system and method for post-processing of initial localization data, even in environments which may include noise, reflections, or other interference. Such localization systems include conventional sound source localization (SSL) systems based on microphone array inputs, radio source location systems based on directional antenna array inputs, etc. In general, this post-processing system and method applies statistical real-time clustering to initial localization estimates, and then uses this real-time clustering in a multi-stage process to generate new localization estimates having improved precision and reliability relative to the initial localization estimates.

Claims

1. A method for automatically improving precision of initial localization estimates, comprising:

generating an initial set of localization data comprising a plurality of localization estimates;

dividing a work volume into a predetermined number of overlapping regions;

assigning each localization estimate to any corresponding one or more of the overlapping regions to form one or more clusters of localization estimates in one or more of the overlapping regions;

estimating positions of objects represented by each cluster of localization estimates;

determining whether any of the objects are duplicate objects by comparing the estimated object positions for clusters in overlapping regions;

eliminating each duplicate object; and

providing each remaining estimated object position to populate a set of position estimates, said set of position estimates representing a set of improved localization estimates relative to the initial set of localization estimates.

2. The method of claim 1 further comprising computing a confidence level for each position estimate in the set of position estimates.

3. The method of claim 1 wherein a lifetime is associated with each localization estimate, and wherein any localization estimate having an expired lifetime is excluded from the initial set of localization data.

4. The method of claim 3 wherein the lifetime is computed as a function of estimated object motions.

5. The method of claim 3 wherein each cluster of localization estimates has a separate lifetime, with the lifetime of each cluster being computed as a function of estimated object motions.

6. The method of claim 1 wherein the set of position estimates is used to initialize any subsequent estimating of positions of objects represented by each cluster of localization estimates.

7. The method of claim 1 wherein the number of overlapping regions is user definable.

8. The method of claim 1 wherein the amount of overlap is user definable.

9. The method of claim 1 further comprising using a weight-based threshold to determine whether particular clusters actually represent objects prior to estimating positions of objects represented by each cluster of localization estimates.

10. The method of claim 1 wherein a criterion for determining whether any of the objects are duplicate objects is a function of a computed distance between any two or more potential objects.

11. A method for automatically generating a set of new position estimates from a set of initial position estimates, comprising using a computing device to:

form one or more clusters of initial position estimates by assigning each initial position estimate in the set of initial position estimates to one or more corresponding overlapping regions covering a work volume being monitored by a receiving array;

compute new position estimates from each cluster of initial position estimates;

compare the new position estimates from each cluster to determine whether any of the position estimates represent a position of a duplicate object;

eliminate new position estimates representing duplicate objects by discarding each new position estimates having a lower computed weight than a corresponding duplicate position estimate; and

provide each remaining new position estimate to populate a set of new position estimates.

12. The method of claim 11 wherein estimates older than a predetermined amount of time are automatically removed from the set of initial position estimates prior to forming clusters of initial position estimates.

13. The method of claim 12 wherein the predetermined amount of time is computed by estimating function of estimated object motions generated from position estimates over time.

14. The method of claim 11 further comprising computing a confidence level for each new position estimate used to populate the set of new position estimates.

15. The method of claim 11 wherein the number of overlapping regions and amount of overlap is user definable.

16. The method of claim 11 further wherein computing new position estimates from each cluster of initial position estimates is only performed for clusters having a computed weight which exceeds a predetermined threshold.

17. A computer-readable medium having computer executable instructions for automatically increasing a reliability and precision of initial localization estimates derived from a receiving array, said computer executable instructions comprising:

generating a set of initial localization estimates from an input received from a receiving array;

dividing a work volume covered by the receiving array into a set of at least partially overlapping sections;

assigning each initialization estimate to one or more of the overlapping sections to create one or more clusters of initial localization estimates within one or more of the overlapping sections;

identifying any of the overlapping regions wherein clusters of the initial localization estimates represent potential objects;

estimating positions of the potential objects in each overlapping region which includes a cluster representing a potential object;

comparing each estimated position to determine whether any of the estimated positions represents a position of a duplicate potential object;

eliminating estimated positions representing duplicate potential objects; and

providing each remaining estimated position to a set of estimated positions representing new localization estimates having increased reliability and precision relative to the initial localization estimates.

18. The computer-readable medium of claim 17 further comprising computing a confidence level for each estimated position provided to the set of estimated positions.

19. The computer-readable medium of claim 17 wherein a lifetime is associated with each localization estimate, and wherein generating the set of initial localization estimates further comprises excluding any localization estimate whose current age is greater than the associated lifetime.

20. The computer-readable medium of claim 17 wherein the number of overlapping regions and amount of overlap is user definable.

21. The computer-readable medium of claim 17 wherein identifying any of the overlapping regions wherein clusters of the initial localization estimates represent potential objects further comprises:

computing a weight for each cluster;

comparing the weight to a predetermined weight threshold; and

excluding any cluster whose weight is less than the predetermined weight threshold.