Methods for navigating through a set of images

• US 10,089,762 B2
• Filed: 07/01/2015
• Issued: 10/02/2018
• Est. Priority Date: 07/04/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Mapillary AB (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Solem, Jan Erik, Kuang, Yubin, Gyllenspetz, Johan, Neubauer, Peter
• Primary Examiner(s): Brier, Jeffery A
• Application Number:
  US15/323,963
• Publication Number:
  US 20170200293A1
• Time in Patent Office: 1,189 Days
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: H04N 7/185 from a mobile camera, e.g. for remote control

Abstract

A method for navigating through a set of images depicting a scene comprises providing a graph representation of correlations of the images and receiving input for navigation that includes an indication of a current image and weight information to control weights to be given to a plurality of measures of similarities of edges in the graph. The indication of the current image is used to determine a current node in the graph representation. At least one best ranked transition image is determined related to the current image by an edge from the current node, said determining comprising using the weight information to weigh the plurality of measures of similarities for forming a combined measure of similarity for edges from the current node, and selecting the at least one best ranked transition image based on a comparison of the combined measure of similarity for the edges from the current node.

Claims

1. A computer-implemented method for navigating through a set of images depicting a scene, the method comprising:

receiving the set of images from one or more mobile devices, the images captured by the one or more mobile devices;

providing a graph representation of correlations of the images, the graph representation comprising nodes and edges, wherein the images are stored on a data storage unit and shared by multiple applications, wherein each node of a first set of nodes among the nodes represents an image and comprises image information including at least a geographical position of an image capturing sensor when acquiring the image, image content information describing an object depicted in the image, and image property information, and wherein each edge of a first set of edges among the edges represents a transition between two images and comprises similarity information providing a plurality of measures of similarities between the two images, the plurality of measures of similarities being pre-defined and comprising a geographical distance measure, a measure of difference in image content, and a measure of difference in an image property, the providing of the graph representation comprising analyzing the two images in relation to each other to derive the pre-defined plurality of measures of similarities;

receiving input from at least one of the multiple applications for navigation through the set of images, the input comprising an indication of a current image in the set of images and weight information to control weights to be given to the plurality of measures of similarities of each edge of the first set of edges in the graph representation;

accessing the graph representation, wherein the indication of the current image is used to determine a current node in the graph representation; and

determining, through data processing on a data processing unit, at least one transition image that is related to the current image by an edge among the first set of edges from the current node, the determining comprising

using the weight information to weigh the plurality of measures of similarities for forming a combined measure of similarity for each one of a plurality of edges from the current node; and

selecting the at least one transition image based on a comparison of the combined measure of similarity for the each one of the plurality of edges from the current node.

2. The computer-implemented method according to claim 1, wherein the input for navigation is received from an application enabling a user to navigate through the set of images, the method further comprising sending output to the application, the output comprising an indication of the selected at least one transition image.

3. The computer-implemented method according to claim 2, wherein the similarity information of at least one edge among the first set of edges comprises transition classifier information, the transition classifier information specifying which of a predefined, finite number of classes that the transition between the two images belongs to, and wherein each of the predefined, finite number of classes defines a type of transition between the two images according to a difference in the geographical position of each of the two images and a difference in a viewing angle of the image capturing sensor when acquiring each of the two images.

4. The computer-implemented method according to claim 3, wherein the determining, through data processing on the data processing unit, of at least one transition image comprises determining at least one transition image for each type of transition and the output comprises an indication of the selected at least one transition image for each type of transition.

5. The computer-implemented method according to claim 3, wherein the input for navigation further comprises an indication of a selected type of transition, the determining, through data processing on the data processing unit, of at least one transition image further comprises determining whether the transition classifier information of an edge from the current node corresponds to the selected type of transition, and, in selecting the at least one transition image, only the edges from the current node that correspond to the selected type of transition are considered.

6. The computer-implemented method according to claim 1, wherein the image property information comprises information of brightness of the image and/or color properties of the image.

7. The computer-implemented method according to claim 1, wherein the image information of at least one node among the first set of nodes further comprises metadata information acquired by a sensor different than the image capturing sensor, the metadata information comprising a compass direction of the image capturing sensor when the image associated with the at least one node was acquired, and wherein the similarity information of at least one edge among the first set of edges further comprises a measure of difference in the metadata information.

8. A computer-implemented method for navigating through a set of images depicting a scene, the method comprising:

receiving the set of images from one or more mobile devices, the images captured by the one or more mobile devices;

providing a graph representation of correlations of the images, the graph representation comprising nodes and edges, wherein the images are stored on a data storage unit and shared by multiple applications, wherein each node of a first set of nodes among the nodes represents an image and comprises image information including at least a geographical position of an image capturing sensor when acquiring the image, image content information describing an object depicted in the image, and image property information, and wherein each edge of a first set of edges among the edges represents a transition between two images and comprises similarity information providing a plurality of measures of similarities between the two images, the plurality of measures of similarities being pre-defined and comprising a geographical distance measure, a measure of difference in image content, and a measure of difference in an image property, the providing of the graph representation comprising analyzing the two images in relation to each other to derive the pre-defined plurality of measures of similarities;

receiving input from at least one of the multiple applications for navigation through the set of images, the input comprising an indication of a start geographical position, an indication of a target geographical position, and weight information to control weights to be given to the plurality of measures of similarities of each edge of the first set of edges in the graph representation;

accessing the graph representation, wherein the start geographical position is used to determine a set of possible start nodes in the graph representation, the possible start nodes each having a geographical position within a distance of the start geographical position that is smaller than a set threshold, and wherein the target geographical position is used to determine a set of possible target nodes in the graph representation, the possible target nodes each having a geographical position within a distance of the target geographical position that is smaller than a set threshold; and

determining, through data processing on a data processing unit, a path among a set of possible paths, each of the possible paths leading from a start node within the set of possible start nodes to a target node within the set of possible target nodes, and comprising one or more edges among the first set of edges connecting the start node to the target node, the determining comprising

using the weight information to weigh the plurality of measures of similarities for forming a combined measure of similarity for each of the edges of the possible paths;

determining a sum of the combined measures of similarity for the one or more edges of each of the possible paths; and

selecting the path based on a comparison of the sum of the combined measures of similarity for each of the possible paths.

9. The computer-implemented method according to claim 8, wherein the indication of a start geographical position comprises an indication of a start node, and the indication of a target geographical position comprises an indication of a target node, the start geographical position being indicated by the start node and the target geographical position being indicated by the target node.

10. The computer-implemented method according to claim 8, wherein the image information of at least one node among the first set of nodes further comprises metadata information acquired by a sensor different than the image capturing sensor, the metadata information comprising a compass direction of the image capturing sensor when the image associated with the at least one node was acquired, and wherein the similarity information of at least one edge among the first set of edges further comprises a measure of difference in the metadata information.

11. The computer-implemented method according to claim 10, wherein the metadata information of the at least one node further comprises a sequence identifier defining that the image associated with the at least one node is acquired as part of a temporal sequence of images, and wherein the measure of difference in the metadata information accounts for whether the images associated with the measure of difference are part of a common temporal sequence.

12. A computer-implemented method of adding an image to a set of images depicting a scene, the method comprising:

receiving the set of images from one or more mobile devices, the images captured by the one or more mobile devices;

providing a graph representation of correlations of the images, the graph representation comprising nodes and edges, wherein the images are stored on a data storage unit and shared by multiple applications, wherein each node of at least a first set of nodes among the nodes represents an image and comprises image information including at least a geographical position of an image capturing sensor when acquiring the image, image content information describing an object depicted in the image, and image property information, and wherein each edge of at least a first set of edges among the edges represents a transition between two images and comprises similarity information providing a plurality of measures of similarities between the two images, the plurality of measures of similarities being pre-defined and comprising a geographical distance measure, a measure of difference in image content, and a measure of difference in an image property, the providing of the graph representation comprising analyzing the two images in relation to each other to derive the pre-defined plurality of measures of similarities;

receiving a current image that is to be added to the set of images and information of a geographical position and a viewing angle of an image capturing sensor when acquiring the current image;

extracting, through data processing on a data processing unit, image content information and image property information from the current image;

forming, through data processing on the data processing unit, a current node in the graph representation, the current node representing the current image and including at least the geographical position of an image capturing sensor when acquiring the current image, image content information describing an object depicted in the current image, and image property information of the current image;

determining, through data processing on the data processing unit, a subset of the set of images in the graph representation to which the current image is related, the determining of the subset comprising;

finding a candidate image in the set of images that is related to the current image based on at least a determination that a difference between the current image and the candidate image according to a first pre-defined measure of similarity is smaller than a first set threshold;

determining a second pre-defined measure of similarity between the current image and the candidate image;

selecting the candidate image as part of the subset based on a determination that the difference between the current image and the candidate image according to at least the second pre-defined measure of similarity is smaller than a second set threshold; and

for each image in the subset;

determining similarity information between the current image and the image in the subset, wherein the similarity information includes transition classifier information specifying which of a predefined, finite number of classes that the transition between the current image and the image in the subset belongs to, and wherein each of the predefined, finite number of classes defines a type of transition between two images according to a difference in the geographical position of each of the two images and a difference in a viewing angle of the image capturing sensor when acquiring each of the two images; and

forming an edge in the graph representation representing the transition between the current image and the image in the subset, the edge comprising the determined similarity information between the current image and the image in the subset.

13. The computer-implemented method according to claim 12, further comprising forming, through data processing on the data processing unit, a combined measure of similarity for an edge in the graph representation, wherein the combined measure of similarity is capable of being controlled on demand by using input of weight information to weigh the plurality of measures of similarities in forming the combined measure of similarity for the edge.

14. The computer-implemented method according to claim 12, further comprising receiving the current image from an application adapted to capture images for the graph representation, the application being arranged in a device comprising an image capturing sensor configured to acquire an image for the graph representation, the application being further arranged to acquire metadata from one or more other sensors in the device to connect the metadata to the acquired image.