Generating navigation data

• US 9,689,687 B2
• Filed: 03/13/2013
• Issued: 06/27/2017
• Est. Priority Date: 03/19/2012
• Status: Active Grant

• Current Assignee: Chancellor Masters & Scholars of The University of Cambridge (University of Cambridge)
• Original Assignee: Chancellor Masters & Scholars of The University of Cambridge (University of Cambridge)
• Inventors: Churchill, Winston Samuel, Newman, Paul Michael
• Primary Examiner(s): Jen, Ian
• Application Number:
  US14/386,278
• Publication Number:
  US 20150057921A1
• Time in Patent Office: 1,567 Days
• Field of Search: 701430
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 30/194 References adjustable by an adaptive method, e.g. learning
• CPC Class Codes: G09B 29/004 Map manufacture or repair; Tear or ink or water resistant maps; Long-life maps printing processes for maps B41M3/02; by permanently attaching map sections to sheets B42B7/00

Abstract

Navigation data is generated by receiving (502) a new experience data set (321) relating to a new experience capture. At least one stored experience data set (320) relating to at least one previous experience capture is also received (504). An experience data set includes a set of nodes, with each node comprising a series of visual image frames taken over a series of time frames. A candidate set of said nodes is obtained (506) from the stored experience data set that potentially matches a said node in the new experience data set, and then a check (508) if performed to see if a node in the candidate set matches the node in the new experience data set. If the result of the checking is positive then data relating to the matched nodes is added (510) to a place data set useable for navigation, the place data set indicating that said nodes in different said experience data sets relate to a same place.

Claims

1. A method of generating navigation data, the method including:

receiving

a new experience data set relating to a new experience capture, and

at least one stored experience data set relating to at least one previous experience capture,

each of the new experience data set and the at least one stored experience data set including a set of nodes, each said node comprising a series of visual image frames relating to a geographical location taken over a series of time frames;

obtaining a candidate set of said nodes from the at least one stored experience data set that potentially relate to a same geographical location of a said node in the new experience data set;

checking whether the geographical location of a said node in the candidate set matches the geographical location of the node in the new experience data set; and

responsive to the matching, adding, to a place data set usable for navigation, a topological link that relates the node in the candidate set to the matched node in the new experience data set.

2. A method according to claim 1, wherein the new experience data set comprises data received from a sensor operating online on a vehicle and the method is performed subsequently offline on a computing device.

3. A method according to claim 1, wherein obtaining the candidate set of nodes includes:

finding any said node from the at least one stored experience data set that relates to the same geographical location of a said node in the new experience data set, the nodes both corresponding to a same time reference k; and

adding a said node from the stored experience data set with a time reference k+1 to the candidate set.

4. A method according to claim 1 wherein obtaining the candidate set of nodes includes:

finding any said node from the place data set that relates to a same geographical location of a said node in the new experience data set; and

adding a neighbouring said node from the place data set to the candidate set.

5. A method according to claim 1, wherein obtaining the candidate set of nodes includes:

finding any said node from the at least one stored experience data set that potentially relates to a same geographical location of a said node in the new experience data set according to an image matching algorithm; and

adding the found node to the candidate set.

6. A method according to claim 5, wherein the image matching algorithm comprises FAB-MAP.

7. A method according to claim 1, wherein obtaining the candidate set of nodes includes:

finding any said node from the at least one stored experience data set that potentially relates to a same geographical location of a said node in the new experience data set according to geographical location indicators; and

adding the found node to the candidate set.

8. A method according to claim 7, wherein a said geographical location indicator is based on geographical data produced during capture of the experience data using a Global Positioning System device.

9. A method according to claim 1, wherein checking whether a node in the candidate set matches the node in the new experience data set includes:

creating a window of nodes ({m_c}_w) either side of a said node in the candidate set;

computing transforms from the node (m*) in the new experience data set to each said node in the window;

if all the transforms are valid then computing translations from the node (m*) in the new experience data set to each said node in the window ({m_c}_w); and

if a local minima is found between the node (m*) in the new experience data set and a said node in the window ({m_c}_w) then the node in the window with a smallest said translation is returned as matching the node (m*) in the new experience data set.

10. A method according to claim 1, wherein a said experience data set further includes data relating to landmarks and the method further includes:

computing a transform from a said image frame (F_k) of a said node in the new experience data set to said nodes in the stored experience data set having landmarks from a region surrounding a previous position of the node in the new experience data set.

11. A method according to claim 10, wherein computing the transform is performed in parallel for a plurality of said image frames in the new experience data set.

12. A method according to claim 10, further including:

identifying said landmarks in a said experience data set using a FAST corner extractor technique; and

using a Brief Robust Independent Elementary Features technique to associate corresponding said landmarks in different said experience data sets.

16. A method according to claim 7, wherein a said geographical location indicator is based on geographical data produced during capture of the experience data.

13. Apparatus configured to generate navigation data, the apparatus including:

a device configured to receive

a new experience data set relating to a new experience capture, and

at least one stored experience data set relating to at least one previous experience capture,

each of the new experience data set and the at least one stored experience data set including a set of nodes, each said node comprising a series of visual image frames relating to a geographical location taken over a series of time frames;

a device configured to obtain a candidate set of said nodes from the at least one stored experience data set that potentially relate to a same geographical location of a said node in the new experience data set; and

a device configured to check whether the geographical location of a said node in the candidate set matches the geographical location of the node in the new experience data set, and responsive to the matching, to add, to a place data set usable for navigation, a topological link that relates the node in the candidate set to the matched node in the new experience data set.

14. Apparatus according to claim 13, wherein the place data set is used for navigation by a navigation device on board a vehicle.

15. Apparatus according to claim 13, wherein the new experience data set comprises data received from a sensor operating online on a vehicle and the devices comprise one or more computing devices.

17. A non-transitory computer program product comprising computer code that when executed by one or more processors cause a process to be carried out, the process comprising:

receiving

a new experience data set relating to a new experience capture, and

at least one stored experience data set relating to at least one previous experience capture,

each of the new experience data set and the at least one stored experience data set including a set of nodes, each said node comprising a series of visual image frames relating to a geographical location taken over a series of time frames;

obtaining a candidate set of said nodes from the at least one stored experience data set that potentially relate to a same geographical location of a said node in the new experience data set;

checking whether the geographical location of a said node in the candidate set matches the geographical location of the node in the new experience data set; and

responsive to the matching, adding, to a place data set usable for navigation, a topological link that relates the node in the candidate set to the matched node in the new experience data set.

18. A non-transitory computer program product according to claim 17, wherein the new experience data set comprises data received from a sensor operating online on a vehicle and the process is performed subsequently offline on a computing device.

19. A non-transitory computer program product according to claim 17, wherein a said experience data set further includes data relating to landmarks and the process further includes:

computing a transform from a said image frame (F_k) of a said node in the new experience data set to said nodes in the stored experience data set having landmarks from a region surrounding a previous position of the node in the new experience data set;

identifying said landmarks in a said experience data set using a FAST corner extractor technique; and

using a Brief Robust Independent Elementary Features technique to associate corresponding said landmarks in different said experience data sets.

20. A non-transitory computer program product according to claim 19, wherein computing the transform is performed in parallel for a plurality of said image frames in the new experience data set.