BITMAP ARRAY FOR OPTIMALLY DISTRIBUTING MAP DATA CONTENT TO WIRELESS COMMUNICATIONS DEVICES

• US 20080268822A1
• Filed: 08/10/2007
• Published: 10/30/2008
• Est. Priority Date: 04/25/2007
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Johnson, Eric, Xi, Xiaming
• Granted Patent: US 8,483,947 B2
• Time in Patent Office: Days
• US Class Current: 455/414.2
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G01C 21/3896 Transmission of map data from central databases
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2207/30181 Earth observation
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

A method of distributing map data from a map server to a wireless communications device entails generating a bitmap array representative of the vector map data for a given zoom level, computing attributes of the bitmap array to determine which map features to retain and which map features to suppress, and then transmitting to the wireless device only the map data for the map features to be retained. By counting the number of bitmap cells representing a polygonal map feature such as a park, lake, or island, the approximate area is quickly estimated. If the area falls below a threshold, the map data for the small polygon is discarded. Similarly, if a polyline map feature overlaps (or is too proximate to) another polyline map feature, one of the polyline map features is discarded. The map data actually transmitted is thus reduced, thereby economizing bandwidth without unduly sacrificing map detail.

Claims

1. A method of distributing map data from a map server to a wireless communications device, the method comprising steps of:

obtaining vector map data in response to a request for map data received at the map server from the wireless communications device;

generating a bitmap array representative of the vector map data for a particular location specified in the request;

computing attributes of the bitmap array to determine which map features are to be retained and which map features are to be omitted; and

transmitting to the wireless communications device only the map data for the map features to be retained.

2. The method as claimed in claim 1 wherein the step of computing attributes of the bitmap array comprises a step of determining whether any polygonal map features are to be omitted.

3. The method as claimed in claim 2 wherein the step of determining whether any polygonal map features are to be removed comprises steps of calculating the total number of bitmap cells in the bitmap array for each polygonal map feature to thus approximate its polygonal area and determining whether the total number of bitmap cells is less than a polygonal area threshold below which the polygonal map feature is to be omitted.

4. The method as claimed in claim 1 wherein the step of computing attributes comprises steps of:

marking bitmap cells in the bitmap array corresponding to a first map feature;

marking bitmap cells in the bitmap array corresponding to a second map feature provided that the bitmap cells to be marked for the second map feature do not coincide with the bitmap cells already marked for the first map feature, thus providing a tally of marked cells and unmarked cells for the second map feature with respect to the first map feature; and

comparing a ratio of the marked cells to the unmarked cells against a threshold to determine whether the second map feature is considered to overlap the first map feature.

5. The method as claimed in claim 4 further comprising a step of prioritizing the map features based on metadata characteristics of the map features so as to determine an appropriate order of priority for populating the cells of the bitmap array.

6. The method as claimed in claim 5 wherein the map features are roadways and wherein the step of prioritizing is done according to one or more of a plurality of factors consisting of:

a class of the roadway, an importance rating of the roadway, a speed limit associated with the roadway, and a length of the roadway.

7. The method as claimed in claim 1 wherein the step of computing attributes comprises steps of:

marking bitmap cells in the bitmap array corresponding to a first map feature while also marking neighbouring bitmap cells to define a buffer of buffer cells immediately on each side of the bitmap cells corresponding the first map feature;

marking bitmap cells in the bitmap array corresponding to a second map feature provided that the bitmap cells to be marked for the second map feature do not coincide with the bitmap cells already marked for the first map feature or with the buffer cells of the first map feature, thus providing a tally of marked cells and unmarked cells for the second map feature with respect to the first map feature and its buffer; and

comparing a ratio of the marked cells to the unmarked cells against a threshold to determine whether the second map feature is considered to either overlap or be too proximate to the first map feature.

8. The method as claimed in claim 1 wherein the map data transmitted to the wireless communications device comprises only the vector map data for the map features to be retained.

9. The method as claimed in claim 1 wherein the map data transmitted to the wireless communications device comprises the bitmap data generated by collapsing the vector map data into the bitmap array.

10. The method as claimed in claim 1 wherein the map data is pre-processed on the map server for a plurality of different zoom levels.

11. The method as claimed in claim 1 wherein the map data is processed in real-time on the map server.

12. The method as claimed in claim 1 further comprising a step of enabling a user to adjust performance of map rendering on the device by tuning one or more of a plurality of tuneable parameters in order to adjust a degree of map detail to be provided, wherein the parameters include a bitmap size, a bitmap resolution, a threshold for determining when a map feature is to be omitted and a width of a buffer for determining when a map feature is to be omitted because of its excessive proximity to another map feature.

13. A computer program product comprising code which, when loaded into memory and executed on a processor of a map server, is adapted to perform the steps of:

obtaining vector map data in response to a request for map data received at the map server from the wireless communications device;

generating a bitmap array representative of the vector map data for a zoom level specified in the request;

computing attributes of the bitmap array to determine which map features are to be retained and which map features are to be omitted; and

transmitting to the wireless communications device only the map data for the map features to be retained.

14. The computer program product as claimed in claim 13 wherein the step of computing attributes of the bitmap array comprises a step of determining whether any polygonal map features are to be omitted.

15. The computer program product as claimed in claim 14 wherein the step of determining whether any polygonal map features are to be removed comprises steps of calculating the total number of bitmap cells in the bitmap array for each polygonal map feature to thus approximate its polygonal area and determining whether the total number of bitmap cells is less than a polygonal area threshold below which the polygonal map feature is to be omitted.

16. The computer program product as claimed in claim 13 wherein the step of computing attributes comprises steps of:

marking bitmap cells in the bitmap array corresponding to a first map feature;

marking bitmap cells in the bitmap array corresponding to a second map feature provided that the bitmap cells to be marked for the second map feature do not coincide with the bitmap cells already marked for the first map feature, thus providing a tally of marked cells and unmarked cells for the second map feature with respect to the first map feature; and

comparing a ratio of the marked cells to the unmarked cells against a threshold to determine whether the second map feature is considered to overlap the first map feature.

17. A map server for distributing map data to the wireless communications devices, the server comprising:

a data port for receiving a request from the wireless communications device for map data; and

a processor coupled to memory to;

process the request and obtain vector map data in response to the request for map data;

generate a bitmap array representative of the vector map data for a zoom level specified in the request;

compute attributes of the bitmap array to determine which map features are to be retained and which map features are to be omitted; and

transmit to the wireless communications device, via the data port, only the map data for the map features to be retained.

18. The map server as claimed in claim 17 wherein the bitmap array is used to determine whether any polygonal map features are to be omitted.

19. The map server as claimed in claim 18 wherein the total number of bitmap cells in the bitmap array for each polygonal map feature is calculated to thus approximate its polygonal area so as to determine whether the total number of bitmap cells is less than a polygonal area threshold below which the polygonal map feature is to be omitted.

20. The map server as claimed in claim 17 wherein the map features are analyzed by:

marking bitmap cells in the bitmap array corresponding to a first map feature;

marking bitmap cells in the bitmap array corresponding to a second map feature provided that the bitmap cells to be marked for the second map feature do not coincide with the bitmap cells already marked for the first map feature, thus providing a tally of marked cells and unmarked cells for the second map feature with respect to the first map feature; and

comparing a ratio of the marked cells to the unmarked cells against a threshold to determine whether the second map feature is considered to overlap the first map feature.

21. The map server as claimed in claim 17 wherein the map features are analyzed by:

marking bitmap cells in the bitmap array corresponding to a first map feature while also marking neighbouring bitmap cells to define a buffer of buffer cells immediately on each side of the bitmap cells corresponding the first map feature;

marking bitmap cells in the bitmap array corresponding to a second map feature provided that the bitmap cells to be marked for the second map feature do not coincide with the bitmap cells already marked for the first map feature or with the buffer cells of the first map feature, thus providing a tally of marked cells and unmarked cells for the second map feature with respect to the first map feature and its buffer; and

comparing a ratio of the marked cells to the unmarked cells against a threshold to determine whether the second map feature is considered to either overlap or be too proximate to the first map feature.

22. The map server as claimed in claim 17 wherein the map server transmits to the wireless communications device only the vector map data for the map features to be retained.

23. The map server as claimed in claim 17 wherein the map server transmits to the wireless communications device the bitmap data generated by collapsing the vector map data into the bitmap array.

24. The map server as claimed in claim 17 wherein the map server stores pre-processed map data for a plurality of different zoom levels.

25. The map server as claimed in claim 17 wherein the map server processes the map data in real-time.

26. The map server as claimed in claim 17 comprising a plurality of tuneable parameters in order to vary map detail, wherein the parameters include a bitmap size, a bitmap resolution, a threshold for determining when a map feature is to be omitted and a width of a buffer for determining when a map feature is to be omitted because of its excessive proximity to another map feature.

27. A wireless communications device comprising:

an input device for enabling a user to request map data;

a processor coupled to memory for communicating a request to a map server; and

a display for displaying a map rendered from map data received from the map server, the map server transmitting only the map data associated with map features that are to be retained after processing the map data using a bitmap array from which attributes of the map features are computed in order to determine whether to retain or omit map features.

28. A method of processing vector map data in a map server, the method comprising steps of:

generating a bitmap array representative of the vector map data for a particular location specified in a request for map data received by the map server;

computing attributes of the bitmap array to determine which map features are to be retained and which map features are to be omitted; and

making available for transmission to a wireless communications device only the map data for the map features to be retained.