System and method for labeling feature clusters in frames of image data for optical navigation

• US 8,094,937 B2
• Filed: 04/17/2007
• Issued: 01/10/2012
• Est. Priority Date: 04/17/2007
• Status: Active Grant

• Current Assignee: PixArt Imaging Incorporated
• Original Assignee: Avago Technologies ECBU IP Singapore Pte Limited (Broadcom, Inc.)
• Inventors: Teoh, Edward Kah Ching, Tan, Zi Hao
• Primary Examiner(s): Le, Brian Q
• Assistant Examiner(s): BEKELE, MEKONEN T
• Application Number:
  US11/736,072
• Publication Number:
  US 20080260249A1
• Time in Patent Office: 1,729 Days
• Field of Search: 382/103, 382/153, 382/180, 342 62- 66, 342160-169, 348/113, 348116-119, 701/28, 702 92- 95, 244 315- 316, 244/3.19
• US Class Current: 382/180
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/11 Region-based segmentation

Abstract

A system and method for labeling feature clusters in frames of image data for optical navigation uses distances between feature clusters in a current frame of image data and feature clusters in a previous frame of image data to label the feature clusters in the current frame of image data using identifiers associated with the feature cluster in the previous frame of image data that have been correlated with the feature clusters in the current frame of image data.

Claims

1. A method for labeling feature clusters in frames of image data for optical navigation, said method comprising:

electronically capturing beacon light sources in said frames of image data as said feature clusters using an image sensor with an electronic imaging sensor array of an optical navigation system, said frames of image data including a current frame of image data and a previous frame of image data that are captured at different times;

identifying current feature clusters in said current frame of image data;

correlating said current feature clusters in said current frame of image data with previous feature clusters in said previous frame of image data based on distances between said current and previous feature clusters such that a current feature cluster in said current frame of image data and a previous feature cluster in said previous frame of image data that both correspond to the same beacon light source are correlated with each other; and

labeling each of said current feature clusters with an identifier associated with one of said previous feature clusters that has been correlated with that current feature cluster,

wherein at least one of said identifying, said correlating and said labeling is performed by a navigation engine in one of an integrated circuit and a processor of said optical navigation system.

2. The method of claim 1 further comprising computing centroids of said current feature clusters in said current frame of image data, said distances between said current feature clusters and said previous feature clusters being distances between said centroids of said current feature clusters and centroids of said previous feature clusters.

3. The method of claim 1 wherein said identifying includes assigning provisional identifiers for said current feature clusters and wherein said labeling includes replacing a provisional identifier of each of said current feature clusters with said identifier associated with one of said previous feature clusters that has been correlated with that current feature cluster.

4. The method of claim 1 wherein said correlating includes correlating a particular current feature cluster of said current feature clusters with a particular previous feature cluster of said previous feature clusters based on a distance between said particular current and previous feature clusters, said distance between said particular current and previous feature clusters being the shortest distance between any of said current feature clusters and any of said previous feature clusters.

5. The method of claim 4 wherein said correlating includes correlating another current feature cluster of said current feature clusters with another previous feature cluster of said previous feature clusters based on a distance between said another current and previous feature clusters, said distance between said another current and previous feature clusters being the shortest distance between any of said current feature clusters and any of said previous feature clusters excluding said distance between said particular current and previous feature clusters.

6. The method of claim 1 wherein said correlating includes associating one of said current feature clusters with one of said previous feature clusters based on a distance between said one of said current feature clusters and said one of said previous feature clusters, said distance between said one of said current feature clusters and said one of said previous feature clusters being the shortest distance between said one of said current feature clusters and any of said previous feature clusters or between said one of said previous feature clusters and any of said current feature clusters.

7. The method of claim 6 wherein said correlating includes correlating a particular current feature cluster of said current feature clusters with an associated previous feature cluster of said previous feature clusters in which a distance between said particular current feature cluster and said associated previous feature clusters is the longest distance between any associated current and previous feature clusters.

8. The method of claim 7 further comprising marking said particular current feature cluster and said associated previous feature cluster as used so that said particular current feature cluster and said associated previous feature cluster are not considered when correlating another feature cluster of said current feature clusters with another feature cluster of said previous feature clusters.

9. A method for labeling feature clusters in frames of image data for optical navigation, said method comprising:

electronically capturing beacon light sources in said frames of image data as said feature clusters using an image sensor with an electronic imaging sensor array of an optical navigation system, said frames of image data including a current frame of image data and a previous frame of image data that are captured at different times;

identifying current feature clusters in said current frame of image data;

correlating said current feature clusters in said current frame of image data with previous feature clusters in said previous frame of image data based on distances between said current and said previous feature clusters such that a current feature cluster in said current frame of image data and a previous feature cluster in said previous frame of image data that both correspond to the same beacon light source are correlated with each other, including associating each current feature cluster of said current feature clusters with one of said previous feature clusters that is closest to that current feature cluster and correlating a particular current feature cluster of said current feature clusters with an associated previous feature cluster of said previous feature clusters in which a distance between said particular current feature cluster and said associated previous feature cluster is the longest distance between any associated current and previous feature clusters; and

labeling each of said current feature clusters with an identifier associated with one of said previous feature clusters that has been correlated with that current feature cluster,

wherein said identifying, said correlating and said labeling are performed by a navigation engine in one of an integrated circuit and a processor of an optical navigation system.

10. The method of claim 9 further comprising marking said particular current feature cluster and said associated previous feature cluster as used so that said particular current feature cluster and said associated previous feature cluster are not considered when correlating another current feature cluster of said current feature clusters with another previous feature cluster of said previous feature clusters.

11. A system for optical navigation, said system comprising:

an image sensor with an electronic imaging sensor array configured to capture frames of image data, said frames of image data including a current frame of image data and a previous frame of image data that are captured at different times; and

a navigation engine operatively connected to said image sensor, said navigation engine being configured to identify current feature clusters in said current frame of image data and correlate said current feature clusters in said current frame of image data with previous feature clusters in said previous frame of image data based on distances between said current and previous feature clusters such that a current feature cluster in said current frame of image data and a previous feature cluster in said previous frame of image data that both correspond to the same beacon light source are correlated with each other, said navigation engine being further configured to label each of said current feature clusters with an identifier associated with one of said previous feature clusters that has been correlated with that current feature cluster.

12. The system of claim 11 wherein said navigation engine is further configured to compute centroids of said current feature clusters in said current frame of image data, said distances between said current feature clusters and said previous feature clusters being distances between said centroids of said current feature clusters and centroids of said previous feature clusters.

13. The system of claim 11 wherein said navigation engine is configured to assign provisional identifiers to said current feature clusters and replace a provisional identifier of each of said current feature clusters with said identifier associated with one of said previous feature clusters that has been correlated with that current feature cluster.

14. The system of claim 11 wherein said navigation engine is configured to correlate a particular current feature cluster of said current feature clusters with a particular previous feature cluster of said previous feature clusters based on a distance between said particular current and previous feature clusters, said distance between said particular current and previous feature clusters being the shortest distance between any of said current feature clusters and any of said previous feature clusters.

15. The system of claim 14 wherein said navigation engine is configured to correlate another current feature cluster of said current feature clusters with another previous feature cluster of said previous feature clusters based on a distance between said another current and previous feature clusters, said distance between said another current and previous feature clusters being the shortest distance between any of said current feature clusters and any of said previous feature clusters excluding said distance between said particular current and previous feature clusters.

16. The system of claim 11 wherein said navigation engine is configured to associate one of said current feature clusters with one of said previous feature clusters based on a distance between said one of said current feature clusters and said one of said previous feature clusters, said distance between said one of said current feature clusters and said one of said previous feature clusters being the shortest distance between said one of said current feature clusters and any of said previous feature clusters or between said one of said previous feature clusters and any of said current feature clusters.

17. The system of claim 16 wherein said navigation engine is configured to correlate a particular current feature cluster of said current feature clusters with an associated feature cluster of said previous feature clusters in which a distance between said particular current and previous feature clusters is the longest distance between any associated current and previous feature clusters.

18. The system of claim 17 wherein said navigation engine is further configured to mark said particular current feature cluster and said associated previous feature cluster as used so that said particular current feature cluster and said associated previous feature cluster are not considered when correlating another feature cluster of said current feature clusters with another feature cluster of said previous feature clusters.

19. The system of claim 11 further comprising an optical filter positioned in front of said image sensor to selectively transmit light from beacon light sources to capture said beacon light sources as said current feature clusters in said current frame of image data.