LINE TRACKING WITH AUTOMATIC MODEL INITIALIZATION BY GRAPH MATCHING AND CYCLE DETECTION

• US 20130057700A1
• Filed: 03/09/2012
• Published: 03/07/2013
• Est. Priority Date: 09/02/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Yi, Sheng, Swaminathan, Ashwin, Jiang, Bolan, Najafi Shoushtari, Seyed Hesameddin
• Granted Patent: US 9,582,896 B2
• Time in Patent Office: Days
• US Class Current: 348/169
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/251 involving models

Abstract

A vision based tracking system in a mobile platform tracks objects using groups of detected lines. The tracking system detects lines in a captured image of the object to be tracked. Groups of lines are formed from the detected lines. The groups of lines may be formed by computing intersection points of the detected lines and using intersection points to identified connected lines, where the groups of lines are formed using connected lines. A graph of the detected lines may be constructed and intersection points identified. Interesting subgraphs are generated using the connections and the group of lines is formed with the interesting subgraphs. Once the groups of lines are formed, the groups of lines are used to track the object, e.g., by comparing the groups of lines in a current image of the object to groups of lines in a previous image of the object.

Claims

1. A method comprising:

capturing an image of an object to be tracked;

detecting a plurality of lines in the image of the object;

forming a group of lines from the plurality of lines; and

using the group of lines to track the object.

2. The method of claim 1, wherein the group of lines comprises connected lines.

3. The method of claim 2, wherein the connected lines form a closed figure.

4. The method of claim 1, wherein forming the group of lines from the plurality of lines comprises:

computing all intersection points of the plurality of lines;

using the intersection points to identify connected lines; and

forming the group of lines with the connected lines.

5. The method of claim 1, wherein forming the group of lines from the plurality of lines comprises:

constructing a graph from the plurality of lines;

computing all intersection points of the plurality of lines;

generating an interesting subgraph using connections between each pair of intersection points; and

forming the group of lines from the interesting subgraph.

6. The method of claim 5, further comprising detecting the object to be tracked by matching a reference model of the object to the interesting subgraph.

7. The method of claim 5, wherein using the group of lines to track the object comprises matching a reference model of the object to the interesting subgraph.

8. The method of claim 5, wherein generating the interesting subgraph comprises:

repeatedly splitting the graph and each resulting subgraph into two until each resulting subgraph contains one cycle; and

reporting resulting subgraphs that contain one cycle as interesting subgraphs.

9. The method of claim 1, wherein using the group of lines to track the object comprises using the group of lines to compare a current image of the object to a previous image of the object.

10. An apparatus comprising:

a camera;

a processor connected to the camera, the processor configured to detect a plurality of lines in an image captured by the camera of an object to be tracked, form a group of lines from the plurality of lines, and use the group of lines to track the object.

11. The apparatus of claim 10, wherein the group of lines comprises connected lines.

12. The apparatus of claim 11, wherein the connected lines form a closed figure.

13. The apparatus of claim 10, wherein the processor is configured to form the group of lines from the plurality of lines by being configured to compute all intersection points of the plurality of lines, use the intersection points to identify connected lines, and form the group of lines with the connected lines.

14. The apparatus of claim 10, wherein the processor is configured to form the group of lines from the plurality of lines by being configured to construct a graph from the plurality of lines;

compute all intersection points of the plurality of lines;

generate an interesting subgraph using connections between each pair of intersection points; and

form the group of lines from the interesting subgraph.

15. The apparatus of claim 14, wherein the processor is further configured to detect the object to be tracked by being configured to match a reference model of the object to the interesting subgraph.

16. The apparatus of claim 14, wherein the processor is configured to use the group of lines to track the object by being configured to match a reference model of the object to the interesting subgraph.

17. The apparatus of claim 14, wherein the processor is configured to generate the interesting subgraph by being configured to repeatedly split the graph and each resulting subgraph into two until each resulting subgraph contains one cycle;

and report resulting subgraphs containing one cycle as interesting subgraphs.

18. The apparatus of claim 10, wherein the processor is configured to use the group of lines to track the object by being configured to compare a current image of the object captured by the camera to a previous image of the object captured by the camera.

19. An apparatus comprising:

means for capturing an image of an object to be tracked;

means for detecting a plurality of lines in the image of the object;

means for forming a group of lines from the plurality of lines; and

means for using the group of lines to track the object.

20. The apparatus of claim 19, wherein the group of lines comprises connected lines that form a closed figure.

21. The apparatus of claim 19, wherein the means for forming the group of lines from the plurality of lines comprises:

means for computing all intersection points of the plurality of lines;

means for using the intersection points to identify connected lines; and

means for forming the group of lines with the connected lines.

22. The apparatus of claim 19, wherein the means for forming the group of lines from the plurality of lines comprises:

means for constructing a graph from the plurality of lines;

means for computing all intersection points of the plurality of lines;

means for generating an interesting subgraph using connections between each pair of intersection points; and

means for forming the group of lines from the interesting subgraph.

23. The apparatus of claim 19, wherein the means for using the group of lines to track the object comprises means for using the group of lines to compare a current image of the object to a previous image of the object.

24. A non-transitory computer-readable medium including program code stored thereon, comprising:

program code to capture an image of an object to be tracked;

program code to detect a plurality of lines in the image of the object;

program code to form a group of lines from the plurality of lines; and

program code to use the group of lines to track the object.

25. The non-transitory computer-readable medium of claim 24, wherein the group of lines comprises connected lines that form a closed figure.

26. The non-transitory computer-readable medium of claim 24, wherein the program code to form the group of lines from the plurality of lines comprises:

program code to compute all intersection points of the plurality of lines;

program code to use the intersection points to identify connected lines; and

program code to form the group of lines with the connected lines.

27. The non-transitory computer-readable medium of claim 24, wherein forming the group of lines from the plurality of lines comprises:

program code to construct a graph from the plurality of lines;

program code to compute all intersection points of the plurality of lines;

program code to generate an interesting subgraph using connections between each pair of intersection points; and

program code to form the group of lines from the interesting subgraph.

28. The non-transitory computer-readable medium of claim 24, wherein the program code to use the group of lines to track the object comprises program code to use the group of lines to compare a current image of the object to a previous image of the object.