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

• US 9,183,438 B1
• Filed: 03/14/2013
• Issued: 11/10/2015
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Dhein, Brendan Edward
• Primary Examiner(s): Patel, Nirav G
• Application Number:
  US13/828,797
• Time in Patent Office: 971 Days
• Field of Search: None
• US Class Current: 1/1
• 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. Areas defined by map coordinates and corresponding to viewports from previously executed user queries are determined. The areas are overlaid on a geographic map portion having a fixed grid of points. Each point is assigned a weighted scores based on the number of areas that overlay each point. A polygon enclosing a set of points having weighted scores above a threshold is determined, and the region enclosed by the polygon is identified as 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 geographic areas corresponding to a plurality of viewports associated with a geographic map, the plurality of viewports having been previously used by a plurality of users to view a portion of the geographic map;

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

overlaying the plurality of geographic areas corresponding to the plurality of viewports with the portion of the geographic map, each of the plurality of geographic areas overlaying zero or more of the plurality of grid points;

scoring, by one or more processors, each of the plurality of grid points based on a number of the plurality of geographic areas that overlay each of the grid points;

determining, by one or more processors, a polygon enclosed by a set of the plurality of grid points based on the scores of the grid points;

identifying, by one or more processors, the polygon as defining a salient region of the geographic map;

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.

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

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

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

increasing the score of the nearest grid point by a fractional amount that depends on the distance between the nearest grid point and the first geographic area.

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

4. The computer-implemented method of claim 1, wherein determining a polygon enclosed by a set of the plurality of grid points based on the scores of the grid points further comprises:

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

iteratively identifying a second set 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 set, the second threshold being lower than the first threshold; and

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

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

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

one or more processors; and

a non-transitory tangible memory accessible by the one or more processors and having executable computer code stored thereon, the computer code comprising a set of instructions that causes the one or more processors to perform the following;

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

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

overlaying the plurality of geographic areas corresponding to the plurality of viewports with the portion of the geographic map, each of the plurality of geographic areas overlaying zero or more of the plurality of grid points;

scoring, by the one or more processors, each of the plurality of grid points based on a number of the plurality of geographic areas that overlay each of the grid points;

determining, by the one or more processors, a polygon enclosed by a set of the plurality of grid points based on the scores of the grid points;

identifying, by the one or more processors, the polygon as defining a salient region of the geographic map;

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

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

7. The system of claim 6, the computer code further comprising a set of instructions that causes the one or more processors to perform the following:

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

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

increasing the score of the nearest grid point by a fractional amount that depends on the distance between the nearest grid point and the first geographic area.

8. The system of claim 6, wherein determining a polygon enclosed by the set of the plurality of grid points based on the scores of the grid points comprises determining a connected set of grid points having a score above a threshold by an advancing front determination.

9. The system of claim 6, wherein determining a polygon enclosed by a set of the plurality of grid points based on the scores of the grid points further comprises:

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

iteratively identifying a second set 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 set, the second threshold being lower than the first threshold; and

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

10. The system of claim 6, wherein the plurality of areas comprise a plurality of rectangles.

11. 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 geographic areas corresponding to a plurality of viewports associated with a geographic map, the plurality of viewports having been previously used by a plurality of users to view a portion of the geographic map;

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

overlaying the plurality of geographic areas corresponding to the plurality of viewports with the portion of the geographic map, each of the plurality of geographic areas overlaying zero or more of the plurality of grid points;

scoring, by one or more processors, each of the plurality of grid points based on a number of the plurality of geographic areas that overlay each of the grid points;

determining, by one or more processors, a polygon enclosed by a set of the plurality of grid points based on the scores of the grid points, wherein determining a polygon enclosed by the set of the plurality of grid points based on the scores of the grid points comprises determining a connected set of grid points having a score above a threshold by an advancing front determination; and

identifying, by one or more processors, the polygon as defining a salient region of the geographic map.

12. The computer-implemented method of claim 11, 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.

13. The computer-implemented method of claim 11, comprising:

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

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

increasing the score of the nearest grid point by a fractional amount that depends on the distance between the nearest grid point and the first geographic area.

14. The computer-implemented method of claim 11, wherein determining a polygon enclosed by the set of the plurality of grid points based on the scores of the grid points comprises:

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

iteratively identifying a second set 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 set, the second threshold being lower than the first threshold; and

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

15. The computer-implemented method of claim 11, wherein the plurality of areas comprise a plurality of rectangles.

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

one or more processors; and

a non-transitory tangible memory accessible by the one or more processors and having executable computer code stored thereon, the computer code comprising a set of instructions that causes the one or more processors to perform the following;

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

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

overlaying the plurality of geographic areas corresponding to the plurality of viewports with the portion of the geographic map, each of the plurality of geographic areas overlaying zero or more of the plurality of grid points;

scoring, by the one or more processors, each of the plurality of grid points based on a number of the plurality of geographic areas that overlay each of the grid points;

determining, by the one or more processors, a polygon enclosed by a set of the plurality of grid points based on the scores of the grid points, wherein determining a polygon enclosed by the set of the plurality of grid points based on the scores of the grid points comprises determining a connected set of grid points having a score above a threshold by an advancing front determination; and

identifying, by the one or more processors, the polygon as defining a salient region of the geographic map.

17. The system of claim 16, the computer code further comprising a set of instructions that causes the one or more processors to perform the following:

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

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

18. The system of claim 16, the computer code further comprising a set of instructions that causes the one or more processors to perform the following:

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

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

increasing the score of the nearest grid point by a fractional amount that depends on the distance between the nearest grid point and the first geographic area.

19. The system of claim 16, wherein determining a polygon enclosed by the set of the plurality of grid points based on the scores of the grid points comprises:

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

iteratively identifying a second set 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 set, the second threshold being lower than the first threshold; and

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

20. The system of claim 16, wherein the plurality of areas comprise a plurality of rectangles.