METHODS FOR NAVIGATING THROUGH A SET OF IMAGES

• US 20170200293A1
• Filed: 07/01/2015
• Published: 07/13/2017
• 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
• Granted Patent: US 10,089,762 B2
• Time in Patent Office: 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; receiving input for navigation through the set of images, said input comprising an indication of a current image in the set of images and weight information to control weights to be given to a plurality of measures of similarities of edges in the graph; accessing the graph representation, wherein the indication of the current image is used to determine a current node in the graph representation; and determining at least one best ranked transition image that is 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 method for navigating through a set of images depicting a scene, the method comprising:

providing a graph representation of correlations of the images, the graph representation comprising nodes and edges, 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 comprising a geographical distance measure, a measure of difference in image content, and a measure of difference in an image property;

receiving input 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 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 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 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 method according to claim 3, wherein the determining 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 method according to claim 3, wherein the input for navigation further comprises an indication of a selected type of transition, the determining 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 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 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 method for navigating through a set of images depicting a scene, the method comprising:

providing a graph representation of correlations of the images, the graph representation comprising nodes and edges, 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 comprising a geographical distance measure, a measure of difference in image content, and a measure of difference in an image property;

receiving input 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 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. A 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. A 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 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 method of adding an image to a set of images depicting a scene, the method comprising:

providing a graph representation of correlations of the images, the graph representation comprising nodes and edges, 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 comprising a geographical distance measure, a measure of difference in image content, and a measure of difference in an image property;

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 image content information and image property information from the current image;

forming 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 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; and

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 method according to claim 12, further comprising forming 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 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.