Automated fitting of interior maps to general maps

• US 8,817,049 B2
• Filed: 04/29/2011
• Issued: 08/26/2014
• Est. Priority Date: 04/29/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ofek, Eyal, Gal, Ran
• Primary Examiner(s): Nguyen, Hau
• Assistant Examiner(s): Gray, Ryan M
• Application Number:
  US13/097,956
• Publication Number:
  US 20120274642A1
• Time in Patent Office: 1,215 Days
• Field of Search: None
• US Class Current: 345/649
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Amalgamated maps, comprising interior maps overlaid on venues indicated in general maps can be automatically generated. Initially, interior maps can be obtained through targeted network searches, whose search results can be filtered to retain those that are most likely useable interior maps. A bounding polygon is generated for both interior map and venue exterior from general map. Subsequently, directional histograms representing orientations of lines in bounding polygons are generated and compared to automatically identify a rotation to align the interior map with the venue exterior from the general map. Anchor points are identified to locally deform the interior map, preserving internal structures, to better align with the venue exterior. Once aligned, the interior map can be combined with the general map, forming an amalgamated map. Updated geocoding can be performed based on locations of establishments in the venue as indicated by the interior map.

Claims

1. One or more computer-readable storage media comprising computer-executable instructions for generating an amalgamated map from a general map and at least one interior map of at least one venue that is represented in the general map, the computer-executable instructions directed to steps comprising:

generating, from a graphical image representing the at least one interior map, a first bounding polygon for the at least one interior map;

generating, from a graphical image representing the general map, a second bounding polygon for a representation, in the general map, of the at least one venue corresponding to the at least one interior map;

identifying, with the first and second bounding polygons, a transformation of the at least one interior map to align the at least one interior map with the representation, in the general map, of the at least one venue, wherein the at least one interior map and the at least one venue in the general map are misaligned prior to the transformation;

applying the identified transformation to the at least one interior map; and

generating the amalgamated map by incorporating the transformed at least one interior map with the representation of the at least one venue in the general map.

2. The computer-readable storage media of claim 1, wherein the computer-executable instructions for identifying the transformation comprise computer-executable instructions for identifying a rotation to be applied to the at least one interior map to align the at least one interior map with the representation, in the general map, of the at least one venue.

3. The computer-readable storage media of claim 2, wherein the computer-executable instructions for identifying the rotation comprise computer-executable instructions for generating a first directional histogram of the first bounding polygon;

generating a second directional histogram of the second bounding polygon;

rotating the first bounding polygon until the first directional histogram optimally aligns with the second directional histogram; and

identifying the rotation of the first bounding polygon as the transformation of the at least one interior map.

4. The computer-readable storage media of claim 1, wherein the computer-executable instructions for applying the identified transformation comprise computer-executable instructions for applying a local deformation to the at least one interior map, the local deformation changing the at least one interior map while preserving an internal structure of the at least one interior map.

5. The computer-readable storage media of claim 4, wherein the computer-executable instructions for identifying the transformation comprise computer-executable instructions for receiving user input aligning portions of the first bounding polygon with portions of the second bounding polygon, the user-aligned portions of the first bounding polygon serving as anchor points for the local deformation.

6. The computer-readable storage media of claim 4, wherein the computer-executable instructions for identifying the transformation comprise computer-executable instructions for:

utilizing a Turn Angle Sum mechanism to identify matching segments between the first and second bounding polygons; and

aligning matching segments of the first bounding polygon with matching segments of the second bounding polygon, the aligned matching segments of the first bounding polygon serving as anchor points for the local deformation.

7. The computer-readable storage media of claim 4, wherein the preserving the interior structure of the at least one interior map during the local deformation comprises:

preserving parallelism of lines shown as parallel in the at least one interior map;

preserving right angles shown in the at least one interior map; and

preserving relative sizing of establishments in the at least one interior map.

8. The computer-readable storage media of claim 1, comprising further computer-executable instructions for converting the at least one interior map from a raster image to a vector-based image.

9. The computer-readable storage media of claim 1, wherein the computer-executable instructions for generating the first bounding polygon comprise computer-executable instructions for excluding text, thereby enabling a determination of the first bounding polygon to proceed inward, towards a center of the interior map, through the text.

10. The computer-readable storage media of claim 1, wherein the computer-executable instructions for generating the first bounding polygon comprise computer-executable instructions for excluding disconnected structures, thereby enabling a determination of the first bounding polygon to proceed inward, towards a center of the interior map, through the disconnected structures.

11. The computer-readable storage media of claim 1, comprising further computer-executable instructions for:

searching for images associated with an identification of the at least one venue and at least one map-centric keyword;

receiving images in response to the searching;

filtering the received images to remove low resolution images;

filtering the received images to remove images with a wide color spectrum; and

selecting, from among the images remaining after the filtering, the at least one interior map.

12. The computer-readable storage media of claim 1, comprising further computer-executable instructions for:

obtaining, from the incorporated and transformed internal map, identifiers of at least some establishments of the at least one venue whose locations are depicted in the internal map; and

geocoding a more accurate location of the at least some of the establishments as the locations depicted in the incorporated and transformed internal map as it is incorporated in the amalgamated map.

13. A method for generating an amalgamated map from a general map and at least one interior map of at least one venue that is represented in the general map, the method comprising the steps of:

generating, from a graphical image representing the at least one interior map, a first bounding polygon for the at least one interior map;

generating, from a graphical image representing the general map, a second bounding polygon for a representation, in the general map, of the at least one venue corresponding to the at least one interior map;

identifying, with the first and second bounding polygons, a transformation of the at least one interior map to align the at least one interior map with the representation, in the general map, of the at least one venue, wherein the at least one interior map and the at least one venue in the general map are misaligned prior to the transformation;

applying the identified transformation to the at least one interior map; and

generating the amalgamated map by incorporating the transformed at least one interior map with the representation of the at least one venue in the general map.

14. The method of claim 13, wherein the identifying the transformation comprises identifying a rotation to be applied to the at least one interior map to align the at least one interior map with the representation, in the general map, of the at least one venue.

15. The method of claim 14, wherein the identifying the rotation comprises:

generating a first directional histogram of the first bounding polygon;

generating a second directional histogram of the second bounding polygon;

rotating the first bounding polygon until the first directional histogram optimally aligns with the second directional histogram; and

identifying the rotation of the first bounding polygon as the transformation of the at least one interior map.

16. The method of claim 13, wherein the applying the identified transformation comprises applying a local deformation to the at least one interior map, the local deformation changing the at least one interior map while preserving an internal structure of the at least one interior map.

17. The method of claim 16, wherein the preserving the interior structure of the at least one interior map during the local deformation comprises:

preserving parallelism of lines shown as parallel in the at least one interior map;

preserving right angles shown in the at least one interior map; and

preserving relative sizing of establishments in the at least one interior map.

18. The method of claim 13, wherein the generating the first bounding polygon comprises excluding text, thereby enabling a determination of the first bounding polygon to proceed inward, towards a center of the interior map, through the text.

19. The method of claim 13, wherein the generating the first bounding polygon comprises excluding disconnected structures, thereby enabling a determination of the first bounding polygon to proceed inward, towards a center of the interior map, through the disconnected structures.

20. An amalgamated map stored on one or more computer-readable storage media and generated by a method comprising the steps of:

generating, from a graphical image representing the at least one interior map, a first bounding polygon for the at least one interior map;

generating, from a graphical image representing the general map, a second bounding polygon for a representation, in the general map, of the at least one venue corresponding to the at least one interior map;

identifying, with the first and second bounding polygons, a transformation of the at least one interior map to align the at least one interior map with the representation, in the general map, of the at least one venue, wherein the at least one interior map and the at least one venue in the general map are misaligned prior to the transformation;

applying the identified transformation to the at least one interior map; and

generating the amalgamated map by incorporating the transformed at least one interior map with the representation of the at least one venue in the general map.