Systems, methods, and computer-readable media for determining a salient region of geographic map

• US 9,977,959 B2
• Filed: 10/07/2015
• Issued: 05/22/2018
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Dhein, Brendan Edward
• Primary Examiner(s): Patel, Nirav G
• Application Number:
  US14/877,535
• Publication Number:
  US 20160026860A1
• Time in Patent Office: 958 Days
• Field of Search: None
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

Provided are systems, methods, and computer-readable media for determining a salient region of a geographic map. Geographic areas corresponding to viewports are determined using map coordinates corresponding to perimeters of those viewports. Grid points, and the geographic areas, are overlaid on a portion of the geographic map. Each point is assigned a score based at least on the number of geographic areas overlaying that point. A polygon defined by a subset of the grid points is determined based on the scores, and the polygon is identified as defining a salient region of the geographic map.

Claims

1. A computer-implemented method for determining a salient region of a geographic map, the method comprising:

obtaining, by one or more processors, a plurality of viewports associated with a geographic map, the plurality of viewports having been previously used by a plurality of users to view at least some of a portion of the geographic map;

determining, by one or more processors and using map coordinates corresponding to perimeters of the plurality of viewports, a plurality of geographic areas corresponding to the plurality of viewports;

overlaying, by one or more processors, a plurality of grid points arranged in a fixed grid on the portion of the geographic map;

overlaying, by one or more processors, the plurality of geographic areas corresponding to the plurality of viewports on the portion of the geographic map;

determining, by one or more processors and for each of the plurality of grid points, a score based at least in part on how many of the plurality of geographic areas overlay the grid point;

generating, by one or more processors, data indicative of a salient region of the geographic map, at least in part by

determining, based on the determined scores for the plurality of grid points, a polygon defined by a subset of the plurality of grid points, and

identifying, the polygon as defining the salient region of the geographic map; and

storing the generated data indicative of the salient region in a memory for further processing.

2. The computer-implemented method of claim 1, comprising:

determining that a first one of the plurality of geographic areas does not overlay any of the plurality of grid points; and

identifying a nearest grid point from among the plurality of grid points, and a distance between the nearest grid point and the first one of the geographic areas,

wherein determining the score for the nearest grid point is further based on the distance between the nearest grid point and the first geographic area.

3. The computer-implemented method of claim 1, wherein determining the polygon defined by the subset of the plurality of grid points based on the determined scores for the plurality of grid points comprises determining a connected set of grid points each having a score above a threshold by an advancing front determination.

4. The computer-implemented method of claim 1, wherein determining the polygon defined by the subset of the plurality of grid points based on the determined scores for the plurality of grid points comprises:

identifying a first subset of the plurality of grid points having a score that is higher than a first threshold, the first subset defining the seeds of an advancing front;

iteratively identifying a second subset of the plurality of grid points having a score that is higher than a second threshold and that surround the grid points in the first subset, the second threshold being lower than the first threshold; and

connecting the plurality of grid points in the second subset to determine the polygon.

5. The computer-implemented method of claim 1, wherein the plurality of geographic areas comprises a plurality of rectangles.

6. The computer-implemented method of claim 1, further comprising:

comparing, by one or more processors, a feature of the geographic map to the salient region; and

determining, by one or more processors, whether the feature has changed based on the comparison.

7. A system for determining a salient region of a geographic map, the system comprising:

one or more processors; and

a non-transitory memory storing computer code, the computer code comprising a set of instructions that, when executed by the one or more processors, causes the one or more processors to;

obtain a plurality of viewports associated with a geographic map, the plurality of viewports having been previously used by a plurality of users to view at least some of a portion of the geographic map,

determine, using map coordinates corresponding to perimeters of the plurality of viewports, a plurality of geographic areas corresponding to the plurality of viewports,

overlay a plurality of grid points arranged in a fixed grid on the portion of the geographic map,

overlay the plurality of geographic areas corresponding to the plurality of viewports on the portion of the geographic map,

determine, for each of the plurality of grid points, a score based at least in part on how many of the plurality of geographic areas overlay the grid point,

generate data indicative of a salient region of the geographic map, at least in part by

determining, based on the determined scores for the plurality of grid points, a polygon defined by a subset of the plurality of grid points, and

identifying the polygon as defining a salient region of the geographic map, and

store the generated data indicative of the salient region in a memory for further processing.

8. The system of claim 7, wherein the set of instructions causes the one or more processors to:

determine that a first one of the plurality of geographic areas does not overlay any of the plurality of grid points; and

identify a nearest grid point from among the plurality of grid points, and a distance between the nearest grid point and the first one of the geographic areas,

wherein the score for the nearest grid point is further based on the distance between the nearest grid point and the first geographic area.

9. The system of claim 7, wherein the set of instructions causes the one or more processors to determine the polygon defined by the subset of the plurality of grid points based on the determined scores for the plurality of grid points at least in part by determining a connected set of grid points each having a score above a threshold by an advancing front determination.

10. The system of claim 7, wherein the set of instructions causes the one or more processors to determine the polygon defined by the subset of the plurality of grid points based on the determined scores for the plurality of grid points at least in part by:

identifying a first subset of the plurality of grid points having a score that is higher than a first threshold, the first subset defining the seeds of an advancing front;

iteratively identifying a second subset of the plurality of grid points having a score that is higher than a second threshold and that surround the grid points in the first subset, the second threshold being lower than the first threshold; and

connecting the plurality of grid points in the second subset to determine the polygon.

11. The system of claim 7, wherein the plurality of geographic areas comprises a plurality of rectangles.

12. The system of claim 7, wherein the set of instructions further causes the one or more processors to:

compare a feature of the geographic map to the salient region; and

determine whether the feature has changed based on the comparison.

13. A non-transitory computer-readable storage medium storing computer code, the computer code comprising a set of instructions that, when executed by one or more processors, causes the one or more processors to:

obtain a plurality of viewports associated with a geographic map, the plurality of viewports having been previously used by a plurality of users to view at least some of a portion of the geographic map;

determine, using map coordinates corresponding to perimeters of the plurality of viewports, a plurality of geographic areas corresponding to the plurality of viewports;

overlay a plurality of grid points arranged in a fixed grid on the portion of the geographic map;

overlay the plurality of geographic areas corresponding to the plurality of viewports on the portion of the geographic map;

determine, for each of the plurality of grid points, a score based at least in part on how many of the plurality of geographic areas overlay the grid point;

generate data indicative of a salient region of the geographic map, at least in part by

determining, based on the determined scores for the plurality of grid points, a polygon defined by a subset of the plurality of grid points, and

identifying the polygon as defining a salient region of the geographic map; and

store the generated data indicative of the salient region in a memory for further processing.

14. The non-transitory computer-readable storage medium of claim 13, wherein the set of instructions causes the one or more processors to:

determine that a first one of the plurality of geographic areas does not overlay any of the plurality of grid points; and

identify a nearest grid point from among the plurality of grid points, and a distance between the nearest grid point and the first one of the geographic areas,

wherein the score for the nearest grid point is further based on the distance between the nearest grid point and the first geographic area.

15. The non-transitory computer-readable storage medium of claim 13, wherein the set of instructions causes the one or more processors to determine the polygon defined by the subset of the plurality of grid points based on the determined scores for the plurality of grid points at least in part by determining a connected set of grid points each having a score above a threshold by an advancing front determination.

16. The non-transitory computer-readable storage medium of claim 13, wherein the set of instructions causes the one or more processors to determine the polygon defined by the subset of the plurality of grid points based on the determined scores for the plurality of grid points at least in part by:

identifying a first subset of the plurality of grid points having a score that is higher than a first threshold, the first subset defining the seeds of an advancing front;

iteratively identifying a second subset of the plurality of grid points having a score that is higher than a second threshold and that surround the grid points in the first subset, the second threshold being lower than the first threshold; and

connecting the plurality of grid points in the second subset to determine the polygon.

17. The non-transitory computer-readable storage medium of claim 13, wherein the set of instructions further causes the one or more processors to:

compare a feature of the geographic map to the salient region; and

determine whether the feature has changed based on the comparison.