Line tracking with automatic model initialization by graph matching and cycle detection

Patent metadata

Field	Value
Publication number	US-9582896-B2
Application number	US-201213416721-A
Country	US
Kind code	B2
Filing date	Mar 9, 2012
Priority date	Sep 2, 2011
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

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.

First claim

What is claimed is:

1. A method comprising:
capturing an image of an object to be tracked;
detecting a plurality of lines in the image of the object;
computing all intersection points of the plurality of lines;
using the intersection points to identify connected lines;
forming a group of lines from the connected lines in 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:
constructing a graph from 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.

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

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

7. The method of claim 4 , 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.

8. 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.

9. 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, compute all intersection points of the plurality of lines, use the intersection points to identify connected lines, form a group of lines from the connected lines in the plurality of lines, and use the group of lines to track the object.

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

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

12. The apparatus of claim 9 , 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; generate an interesting subgraph using connections between each pair of intersection points; and form the group of lines from the interesting subgraph.

13. The apparatus of claim 12 , 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.

14. The apparatus of claim 12 , 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.

15. The apparatus of claim 12 , 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.

16. The apparatus of claim 9 , 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.

17. 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 computing all intersection points of the plurality of lines;
means for using the intersection points to identify connected lines;
means for forming a group of lines from the connected lines in the plurality of lines; and
means for using the group of lines to track the object.

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

19. The apparatus of claim 17 , 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 generating an interesting subgraph using connections between each pair of intersection points; and
means for forming the group of lines from the interesting subgraph.

20. The apparatus of claim 17 , 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.

21. A non-transitory computer-readable medium including instructions stored thereon and that are executable by one or more processors, comprising:
instructions to detect a plurality of lines in an image of an object to be tracked that is captured with a camera;
instructions to compute all intersection points of the plurality of lines;
instructions to use the intersection points to identify connected lines;
instructions to form a group of lines from the connected lines in the plurality of lines; and
instructions to use the group of lines to track the object.

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

23. The non-transitory computer-readable medium of claim 21 , wherein forming the group of lines from the plurality of lines comprises:
instructions to construct a graph from the plurality of lines;
instructions to generate an interesting subgraph using connections between each pair of intersection points; and
instructions to form the group of lines from the interesting subgraph.

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

Assignees

• Yi Sheng
• Swaminathan Ashwin
• Jiang Bolan
• Najafi Shoushtari Seyed Hesameddin
• Qualcomm Inc

Inventors

• Yi Sheng
• Swaminathan Ashwin
• Jiang Bolan
• Najafi Shoushtari Seyed Hesameddin

Classifications

• G06T2207/10016

  Video; Image sequence · CPC title

• G06T7/251 Primary

  involving models · CPC title

• G06T7/2046 Primary

  Physics · mapped topic

• G06T7/20 Primary

  Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51) · CPC title